New Reoptimization Techniques applied to Steiner Tree Problem

Given an instance of an optimization problem together with an optimal solution for it, a reoptimization problem asks for a solution for a locally modified input instance. In this paper we develop new reoptimization techniques and apply them to the Steiner Tree Problem. Our techniques significantly improve the previous results and apply to a variety of reoptimization problems.     

Reoptimization of the metric deadline TSP

The reoptimization version of an optimization problem deals with the following scenario: Given an input instance together with an optimal solution for it, the objective is to find a high-quality solution for a locally modified instance.In this paper, we investigate several reoptimization variants of the traveling salesman problem with deadlines in metric graphs (Δ-DlTSP). The objective in the Δ-DlTSP is to find a minimum-cost Hamiltonian cycle in a complete undirected graph with a metric edge cost function which visits some of its vertices before some prespecified deadlines. As types of local modifications, we consider insertions and deletions of a vertex as well as of a deadline.We prove the hardness of all of these reoptimization variants and give lower and upper bounds on the achievable approximation ratio which are tight in most cases.     

Reoptimizing the 0-1 knapsack problem

In this paper we study the problem where an optimal solution of a knapsack problem on n items is known and a very small number k of new items arrive. The objective is to find an optimal solution of the knapsack problem with n+k items, given an optimal solution on the n items (reoptimization of the knapsack problem). We show that this problem, even in the case k=1, is NP-hard and that, in order to have effective heuristics, it is necessary to consider not only the items included in the previously optimal solution and the new items, but also the discarded items. Then, we design a general algorithm that makes use, for the solution of a subproblem, of an α-approximation algorithm known for the knapsack problem. We prove that this algorithm has a worst-case performance bound of , which is always greater than α, and therefore that this algorithm always outperforms the corresponding α-approximation algorithm applied from scratch on the n+k items. We show that this bound is tight when the classical Ext-Greedy algorithm and the algorithm are used to solve the subproblem. We also show that there exist classes of instances on which the running time of the reoptimization algorithm is smaller than the running time of an equivalent PTAS and FPTAS.     

Updating Network Flows Given Multiple,Heterogeneous Arc Attribute Changes

A dual ascent reoptimization technique is proposed for updating optimal flows for the minimum cost network flow problem (MCNFP) given any number of simultaneous, heterogeneous changes to the network attributes (i.e. supply at nodes, arc costs and arc capacities) and the optimal solutions to the prior primal and dual problems. Significant savings in computation time can be achieved through the use of reoptimization in place of solving a new MCNFP from scratch as each new problem instance (i.e. set of network attribute updates) arises. The proposed technique can be implemented with polynomial worst-case computational complexity. Extensive numerical experiments were designed and conducted to assess the computational benefits of employing the proposed reoptimization technique as compared with solution from scratch using comparable classic implementations of the original algorithms. This work was motivated by the need for the real-time provision of evacuation instructions to people seeking quick egress from a large sensor-equipped building that has come under attack by natural or terrorist forces, but has broad applicability.     

Dynamic traveling salesman problem with stochastic release dates

The dynamic traveling salesman problem with stochastic release dates (DTSP-srd) is a problem in which a supplier has to deliver parcels to its customers. These parcels are delivered to its depot while the distribution is taking place. The arrival time of a parcel to the depot is called its release date. In the DTSP-srd, release dates are stochastic and dynamically updated as the distribution takes place. The objective of the problem is the minimization of the total time needed to serve all customers, given by the sum of the traveling time and the waiting time at the depot. The problem is represented as a Markov Decision Process and is solved through a reoptimization approach. Two models are proposed for the problem to be solved at each stage. The first model is stochastic and exploits the entire probabilistic information available for the release dates. The second model is deterministic and uses an estimation of the release dates. An instance generation procedure is proposed to simulate the evolution of the information to perform computational tests. The results show that a more frequent reoptimization provides better results across all tested instances and that the stochastic model performs better than the deterministic model. The main drawback of the stochastic model lies in the computational time required to evaluate a solution, which makes an iteration of the heuristic substantially more time-consuming than in the case where the deterministic model is used.     

Algorithms for multiplayer multicommodity flow problems

We investigate the multiplayer multicommodity flow problem: several players have different networks and commodities over a common node set. Pairs of players have contracts where one of them agrees to route the flow of the other player (up to a given capacity) between two specified nodes. In return, the second player pays an amount proportional to the flow value. We show that the social optimum can be computed by linear programming, and we propose algorithms based on column generation and Lagrangian relaxation. In contrast, we prove that it is hard to decide if an equilibrium solution exists, although some natural conditions guarantee its existence.     

Sensitivity analysis of the optimum to perturbation of the profit of a subset of items in the binary knapsack problem

In this paper, we study the sensitivity of the optimum of the binary knapsack problem to perturbations of the profit of a subset of items. In order to stabilize the optimal solution, two cases are distinguished. The first case represents a subset of items whose perturbation can be done individually. The second case represents a subset of items where perturbing the profit of each item requires the perturbation of the profit of the other items. We will study the impact of the results obtained on an instance of the binary knapsack problem while considering the various cases.     

An integrated model for logistics network design

In this paper we introduce a new formulation of the logistics network design problem encountered in deterministic, single-country, single-period contexts. Our formulation is flexible and integrates location and capacity choices for plants and warehouses with supplier and transportation mode selection, product range assignment and product flows. We next describe two approaches for solving the problem---a simplex-based branch-and-bound and a Benders decomposition approach. We then propose valid inequalities to strengthen the LP relaxation of the model and improve both algorithms. The computational experiments we conducted on realistic randomly generated data sets show that Benders decomposition is somewhat more advantageous on the more difficult problems. They also highlight the considerable performance improvement that the valid inequalities produce in both solution methods. Furthermore, when these constraints are incorporated in the Benders decomposition algorithm, this offers outstanding reoptimization capabilities.     

Easy capacitated facility location problems,with connections to lot-sizing

In this note, we consider the capacitated facility location problem when the transportation costs of the instance satisfy the Monge property. We show that a straightforward dynamic program finds the optimal solution when the demands are polynomially bounded. When demands are not polynomially bounded, we give a fully polynomial-time approximation scheme by adapting an algorithm and analysis of Van Hoesel and Wagelmans (2001).     

Issues in the implementation of the DSD algorithm for the traffic assignment problem

In this paper we consider the practical implementation of the disaggregated simplicial decomposition (DSD) algorithm for the traffic assignment problem. It is a column generation method that at each step has to solve a huge number of quadratic knapsack problems (QKP). We propose a Newton-like method to solve the QKP when the quadratic functional is convex but not necessarily strictly. Our O(n) algorithm does not improve the complexity of the current methods but extends them to a more general case and is better suited for reoptimization and so a good option for the DSD algorithm. It also allows the solution of many QKP’s simultaneously in a vectorial or parallel way.     

Polyhedral results for the edge capacity polytope

Network loading problems occur in the design of telecommunication networks, in many different settings. For instance, bifurcated or non-bifurcated routing (also called splittable and unsplittable) can be considered. In most settings, the same polyhedral structures return. A better understanding of these structures therefore can have a major impact on the tractability of polyhedral-guided solution methods. In this paper, we investigate the polytopes of the problem restricted to one arc/edge of the network (the undirected/directed edge capacity problem) for the non-bifurcated routing case.?As an example, one of the basic variants of network loading is described, including an integer linear programming formulation. As the edge capacity problems are relaxations of this network loading problem, their polytopes are intimately related. We give conditions under which the inequalities of the edge capacity polytopes define facets of the network loading polytope. We describe classes of strong valid inequalities for the edge capacity polytopes, and we derive conditions under which these constraints define facets. For the diverse classes the complexity of lifting projected variables is stated.?The derived inequalities are tested on (i) the edge capacity problem itself and (ii) the described variant of the network loading problem. The results show that the inequalities substantially reduce the number of nodes needed in a branch-and-cut approach. Moreover, they show the importance of the edge subproblem for solving network loading problems. Received: September 2000 / Accepted: October 2001?Published online March 27, 2002     

Asymptotic Results for Random Multidimensional Assignment Problems

The multidimensional assignment problem (MAP) is an NP-hard combinatorial optimization problem occurring in applications such as data association and target tracking. In this paper, we investigate characteristics of the mean optimal solution values for random MAPs with axial constraints. Throughout the study, we consider cost coefficients taken from three different random distributions: uniform, exponential and standard normal. In the cases of uniform and exponential costs, experimental data indicates that the mean optimal value converges to zero when the problem size increases. We give a short proof of this result for the case of exponentially distributed costs when the number of elements in each dimension is restricted to two. In the case of standard normal costs, experimental data indicates the mean optimal value goes to negative infinity with increasing problem size. Using curve fitting techniques, we develop numerical estimates of the mean optimal value for various sized problems. The experiments indicate that numerical estimates are quite accurate in predicting the optimal solution value of a random instance of the MAP.     

A simulated annealing algorithm with the random compound move for the sequential partitioning problem of directed acyclic graphs

In this paper, we present an approach for finding a minimum cost partition of the nodes of a directed acyclic graph into subsets of a given size, subject to the constraint that the precedence relationships among the elements are satisfied, based on the concept of simulated annealing. Simulated annealing is generally applicable, and can be used to obtain solutions arbitrarily close to an optimum. However, the standard simulated annealing approach with a conventional neighbourhood structure does not yield good solutions for this problem, since this is a multiple partitioning problem and the number of subsets is not fixed. For this problem, we develop an effective neighbourhood structure and a new acceptance criterion. We also assess the effectiveness of the developed algorithm. The results show that this proposed algorithm outperforms, in terms of solution quality, any other algorithm using tabu search. The computational time of the procedure is proportional to the number of nodes in the graph.     

Modeling cooperation on a class of distribution problems

In this paper we study models of cooperation between the nodes of a network that represents a distribution problem. The distribution problem we propose arises when, over a graph, a group of nodes offers certain commodity, some other nodes require it and a third group of nodes neither need this material nor offer it but they are strategically relevant to the distribution plan. The delivery of one unit of material to a demand node generates a fixed profit, and the shipping of the material through the arcs has an associated cost. We show that in such a framework cooperation is beneficial for the different parties. We prove that the cooperative situation arising from this distribution problem is totally balanced by finding a set of stable allocations (in the core of an associated cooperative game). In order to overcome certain fairness problems of these solutions, we introduce two new solution concepts and study their properties.     

Bin covering with a general profit function: approximability results

In the recent paper (Benk? et al. 2010) we introduced a new problem that we call Bin Packing/Covering with Delivery, or BP/CD for short. Mainly we mean under this expression that we look for not only a good, but a “good and fast” packing or covering. In the present paper we investigate the offline case. For the analysis, a novel view on “offline optimum” is introduced, which appears to be relevant concerning all problems where a final solution is ordering-dependent. We prove that if the item sizes are not allowed to be arbitrarily close to zero, then an optimal offline solution can be found in polynomial time. On the other hand, for unrestricted problem instances, no polynomial-time algorithm can achieve an asymptotic approximation ratio better than 6/7 if $P\ne NP$ .     

The Dissipation Inequality for Differential-Algebraic Systems

We discuss the infinite time-horizon linear-quadratic optimal control problem for differential-algebraic equations. In contrast to previous approaches we do not impose any assumptions on the system except for impulse controllability. In particular, we show that the optimal control problem is feasible if and only if a dissipation inequality has a solution. Moreover, we discuss conditions under which the problem has a minimizing (instead of only an infimizing) solution and furthermore, when this minimizing solution is unique. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On structure-oriented hybrid two-stage iteration methods for the large and sparse blocked system of linear equations

In this paper, we first present a class of structure-oriented hybrid two-stage iteration methods for solving the large and sparse blocked system of linear equations, as well as the saddle point problem as a special case. And the new methods converge to the solution under suitable restrictions, for instance, when the coefficient matrix is positive stable matrix generally. Numerical experiments for a model generalized saddle point problem are given, and the results show that our new methods are feasible and efficient, and converge faster than the Classical Uzawa Method.     

关于最短路问题的一个双目标优化问题

本文研究了一个双目标最短路问题的变形问题,在该变形问题中,一个目标函数还是路的长度,另一个目标函数则是路的容量,在Pareto-optimal最优解的意义下,本文给出了一个时间复杂性为O（n^3 )的算法,在字典序最优解的意义下,本文给出了一个时间复杂性为O(n^3)的算法。     

On the existence and uniqueness of a generalized solution of the mixed problem for the wave equation with the second and third boundary conditions

We prove the uniqueness of a generalized solution of an initial-boundary value problem for the wave equation with boundary conditions of the third and second kind. In addition, we find a closed-form expression for the analytic solution of that problem with zero initial data. The result plays an important role in the investigation of the boundary control problem. We show how to use the obtained solution for the investigation of the boundary control problem in the case of subcritical time intervals for which the solution of the boundary control problem, if it exists at all, is unique. We obtain necessary and sufficient conditions for the existence of a unique solution in a class admitting the existence of finite energy.     

On Pareto optima,the Fermat-Weber problem,and polyhedral gauges

This paper deals with multiobjective programming in which the objective functions are nonsymmetric distances (derived from different gauges) to the points of a fixed finite subset of ⁿ. It emphasizes the case in which the gauges are polyhedral. In this framework the following result is known: if the gauges are polyhedral, then each Pareto optimum is the solution to a Fermat—Weber problem with strictly positive coefficients. We give a new proof of this result, and we show that it is useful in finding the whole set of efficient points of a location problem with polyhedral gauges. Also, we characterize polyhedral gauges in terms of a property of their subdifferential.A simplified version of the results of this paper has been presented at the International Symposium on Infinite Dimensional Linear Programming, September 1984, Cambridge, England.