New valid inequalities for the fixed-charge and single-node flow polytopes

The most effective software packages for solving mixed 0–1linear programs use strong valid linear inequalities derived from polyhedral theory. We introduce a new procedure which enables one to take known valid inequalities for the knapsack polytope, and convert them into valid inequalities for the fixed-charge and single-node flow polytopes. The resulting inequalities are very different from the previously known inequalities (such as flow cover and flow pack inequalities), and define facets under certain conditions.     

On the graphical relaxation of the symmetric traveling salesman polytope

The Graphical Traveling Salesman Polyhedron (GTSP) has been proposed by Naddef and Rinaldi to be viewed as a relaxation of the Symmetric Traveling Salesman Polytope (STSP). It has also been employed by Applegate, Bixby, Chvátal, and Cook for solving the latter to optimality by the branch-and-cut method. There is a close natural connection between the two polyhedra. Until now, it was not known whether there are facets in TT-form of the GTSP polyhedron which are not facets of the STSP polytope as well. In this paper we give an affirmative answer to this question for n ≥ 9. We provide a general method for proving the existence of such facets, at the core of which lies the construction of a continuous curve on a polyhedron. This curve starts in a vertex, walks along edges, and ends in a vertex not adjacent to the starting vertex. Thus there must have been a third vertex on the way.      

A new class of facets for the Latin square polytope

Latin squares of order n have a 1-1 correspondence with the feasible solutions of the 3-index planar assignment problem (3PAP_n). In this paper, we present a new class of facets for the associated polytope, induced by odd-hole inequalities.     

On the complete set packing and set partitioning polytopes: Properties and rank 1 facets

This paper studies two polytopes: the complete set packing and set partitioning polytopes, which are both associated with a binary $n$-row matrix having all possible columns. Cuts of rank 1 for the latter polytope play a central role in recent exact algorithms for many combinatorial problems, such as vehicle routing. We show the precise relation between the two polytopes studied, characterize the multipliers that induce rank 1 clique facets and give several families of multipliers that yield other facets.     

Lifting the knapsack cover inequalities for the knapsack polytope

Valid inequalities for the knapsack polytope have proven to be very useful in exact algorithms for mixed-integer linear programming. In this paper, we focus on the knapsack cover inequalities, introduced in 2000 by Carr and co-authors. In general, these inequalities can be rather weak. To strengthen them, we use lifting. Since exact lifting can be time-consuming, we present two fast approximate lifting procedures. The first procedure is based on mixed-integer rounding, whereas the second uses superadditivity.     

Facets of the clique partitioning polytope

A subsetA of the edge set of a graphG = (V, E) is called a clique partitioning ofG is there is a partition of the node setV into disjoint setsW ¹,,W ^k such that eachW _i induces a clique, i.e., a complete (but not necessarily maximal) subgraph ofG, and such thatA = _i=1 ^k 1{uv|u, v W _i ,u v}. Given weightsw ^e for alle E, the clique partitioning problem is to find a clique partitioningA ofG such that _eA w _e is as small as possible. This problem—known to be-hard, see Wakabayashi (1986)—comes up, for instance, in data analysis, and here, the underlying graphG is typically a complete graph. In this paper we study the clique partitioning polytope of the complete graphK _n , i.e., is the convex hull of the incidence vectors of the clique partitionings ofK _n . We show that triangles, 2-chorded odd cycles, 2-chorded even wheels and other subgraphs ofK _n induce facets of. The theoretical results described here have been used to design an (empirically) efficient cutting plane algorithm with which large (real-world) instances of the clique partitioning problem could be solved. These computational results can be found in Grötschel and Wakabayashi (1989).     

A note on the continuous mixing set

The continuous mixing set is , where w₁,…,w_n>0 and f₁,…,f_n∈ℜ. Let m=|{w₁,…,w_n}|. We show that when w₁|?|w_n, optimization over S can be performed in time O(n^m+1), and in time O(nlogn) when w₁=?=w_n=1.     

Some facets of the simple plant location polytope

We relate the simple plant location problem to the vertex packing problem and derive several classes of facets of their associated integer polytopes.This work was supported by NSF Grant ENG 79-02506.     

Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs

The Asymmetric Travelling Salesman Problem with Replenishment Arcs (RATSP) is a new class of problems arising from work related to aircraft routing. Given a digraph with cost on the arcs, a solution of the RATSP, like that of the Asymmetric Travelling Salesman Problem, induces a directed tour in the graph which minimises total cost. However the tour must satisfy additional constraints: the arc set is partitioned into replenishment arcs and ordinary arcs, each node has a non-negative weight associated with it, and the tour cannot accumulate more than some weight limit before a replenishment arc must be used. To enforce this requirement, constraints are needed. We refer to these as replenishment constraints.In this paper, we review previous polyhedral results for the RATSP and related problems, then prove that two classes of constraints developed in V. Mak and N. Boland [Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs, Technical Report TR M05/03, School of Information Technology, Deakin University, 2005] are, under appropriate conditions, facet-defining for the RATS polytope.     

Solution of and bounding in a linearly constrained optimization problem with convex,polyhedral objective function

A dual method is presented to solve a linearly constrained optimization problem with convex, polyhedral objective function, along with a fast bounding technique, for the optimum value. The method can be used to solve problems, obtained from LPs, where some of the constraints are not required to be exactly satisfied but are penalized by piecewise linear functions, which are added to the objective function of the original problem. The method generalizes an earlier solution technique developed by Prékopa (1990). Applications to stochastic programming are also presented.This research was supported by the National Science Foundation, Grant No. DMS-9005159.Corresponding author.     

On the set covering polytope: I. All the facets with coefficients in {0, 1, 2}

While the set packing polytope, through its connection with vertex packing, has lent itself to fruitful investigations, little is known about the set covering polytope. We characterize the class of valid inequalities for the set covering polytope with coefficients equal to 0, 1 or 2, and give necessary and sufficient conditions for such an inequality to be minimal and to be facet defining. We show that all inequalities in the above class are contained in the elementary closure of the constraint set, and that 2 is the largest value ofk such that all valid inequalities for the set covering polytope with integer coefficients no greater thank are contained in the elementary closure. We point out a connection between minimal inequalities in the class investigated and certain circulant submatrices of the coefficient matrix. Finally, we discuss conditions for an inequality to cut off a fractional solution to the linear programming relaxation of the set covering problem and to improve the lower bound given by a feasible solution to the dual of the linear programming relaxation.Research supported by the National Science Foundation through grant ECS-8503198 and the Office of Naval Research through contract N0001485-K-0198.     

On the partial order polytope of a digraph

We introduce the partial order polytope of a digraphD, defined as the convex hull of the incidence vectors of all transitive acyclic arc sets ofD. For this polytope we prove some classes of inequalities to be facet-defining and show that there is a polynomial separation algorithm for each of these classes. The results imply a polynomial separation algorithm for a class of valid inequalities of the clique partitioning polytope that includes the two-chorded odd cycle inequalities. The polyhedral results concerning the partial order polytope are of interest since a cutting plane based algorithm to solve the maximum weighted transitive acyclic subdigraph problem can be used to solve the maximum weighted acyclic subdigraph problem, the maximum weighted linear ordering problem and a flexible manufacturing problem. For the acyclic subdigraph polytope we show that the separation of simplet-reinforcedk-fence-inequalities is -complete.     

A lifting procedure for the asymmetric traveling salesman polytope and a large new class of facets

Given any family of valid inequalities for the asymmetric traveling salesman polytopeP(G) defined on the complete digraphG, we show that all members of are facet defining if the primitive members of (usually a small subclass) are. Based on this result we then introduce a general procedure for identifying new classes of facet inducing inequalities forP(G) by lifting inequalities that are facet inducing forP(G), whereG is some induced subgraph ofG. Unlike traditional lifting, where the lifted coefficients are calculated one by one and their value depends on the lifting sequence, our lifting procedure replaces nodes ofG with cliques ofG and uses closed form expressions for calculating the coefficients of the new arcs, which are sequence-independent. We also introduce a new class of facet inducing inequalities, the class of SD (source-destination) inequalities, which subsumes as special cases most known families of facet defining inequalities.Research supported by Grant DDM-8901495 of the National Science Foundation and Contract N00014-85-K-0198 of the U.S. Office of Naval Research.Research supported by M.U.R.S.T., Italy.     

A comparative study of decomposition algorithms for stochastic combinatorial optimization

This paper presents comparative computational results using three decomposition algorithms on a battery of instances drawn from two different applications. In order to preserve the commonalities among the algorithms in our experiments, we have designed a testbed which is used to study instances arising in server location under uncertainty and strategic supply chain planning under uncertainty. Insights related to alternative implementation issues leading to more efficient implementations, benchmarks for serial processing, and scalability of the methods are also presented. The computational experience demonstrates the promising potential of the disjunctive decomposition (D ²) approach towards solving several large-scale problem instances from the two application areas. Furthermore, the study shows that convergence of the D ² methods for stochastic combinatorial optimization (SCO) is in fact attainable since the methods scale well with the number of scenarios.     

Adaptive discretization of convex multistage stochastic programs

We propose a new scenario tree reduction algorithm for multistage stochastic programs, which integrates the reduction of a scenario tree into the solution process of the stochastic program. This allows to construct a scenario tree that is highly adapted on the optimization problem. The algorithm starts with a rough approximation of the original tree and locally refines this approximation as long as necessary. Promising numerical results for scenario tree reductions in the settings of portfolio management and power management with uncertain load are presented.