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

In an earlier paper (Mathematical Programming 43 (1989) 57–69) we characterized the class of facets of the set covering polytope defined by inequalities with coefficients equal to 0, 1 or 2. In this paper we connect that characterization to the theory of facet lifting. In particular, we introduce a family of lower dimensional polytopes and associated inequalities having only three nonzero coefficients, whose lifting yields all the valid inequalities in the above class, with the lifting coefficients given by closed form expressions.The research underlying this report was supported by Grant ECS-8601660 of the National Science Foundation, Contract N00014-85-K-0198 with the Office of Naval Research, and Grant AFOSR-870292 of the Air Force Office of Scientific Research.     

Restricted 2-factor polytopes

The optimal k-restricted 2-factor problem consists of finding, in a complete undirected graph K _n , a minimum cost 2-factor (subgraph having degree 2 at every node) with all components having more than k nodes. The problem is a relaxation of the well-known symmetric travelling salesman problem, and is equivalent to it when ≤k≤n−1. We study the k-restricted 2-factor polytope. We present a large class of valid inequalities, called bipartition inequalities, and describe some of their properties; some of these results are new even for the travelling salesman polytope. For the case k=3, the triangle-free 2-factor polytope, we derive a necessary and sufficient condition for such inequalities to be facet inducing. Received March 4, 1997 / Revised version received September 7, 1998?Published online November 9, 1999     

On the 0/1 knapsack polytope

This paper deals with the 0/1 knapsack polytope. In particular, we introduce the class ofweight inequalities. This class of inequalities is needed to describe the knapsack polyhedron when the weights of the items lie in certain intervals. A generalization of weight inequalities yields the so-called “weight-reduction principle” and the class of extended weight inequalities. The latter class of inequalities includes minimal cover and (l,k)-configuration inequalities. The properties of lifted minimal cover inequalities are extended to this general class of inequalities.     

Facets of the knapsack polytope derived from disjoint and overlapping index configurations

Necessary and sufficient conditions for a class of facets of the knapsack polytope which contain fractional coefficients are derived. These inequalities are based upon disjoint and overlapping minimal covers and (1, k)-configurations.     

Exploring the Relationship Between Max-Cut and Stable Set Relaxations

The max-cut and stable set problems are two fundamental -hard problems in combinatorial optimization. It has been known for a long time that any instance of the stable set problem can be easily transformed into a max-cut instance. Moreover, Laurent, Poljak, Rendl and others have shown that any convex set containing the cut polytope yields, via a suitable projection, a convex set containing the stable set polytope. We review this work, and then extend it in the following ways. We show that the rounded version of certain `positive semidefinite' inequalities for the cut polytope imply, via the same projection, a surprisingly large variety of strong valid inequalities for the stable set polytope. These include the clique, odd hole, odd antihole, web and antiweb inequalities, and various inequalities obtained from these via sequential lifting. We also examine a less general class of inequalities for the cut polytope, which we call odd clique inequalities, and show that they are, in general, much less useful for generating valid inequalities for the stable set polytope. As well as being of theoretical interest, these results have algorithmic implications. In particular, we obtain as a by-product a polynomial-time separation algorithm for a class of inequalities which includes all web inequalities.     

On the first Chvátal closure of the set covering polyhedron related to circulant matrices

We study the set covering polyhedron related to circulant matrices. In particular, our goal is to characterize the first Chvátal closure of the usual fractional relaxation. We present a family of valid inequalities that generalizes the family of minor inequalities previously reported in the literature. This family includes new facet-defining inequalities for the set covering polyhedron.     

Alternative formulations for the Set Packing Problem and their application to the Winner Determination Problem

An alternative formulation for the set packing problem in a higher dimension is presented. The addition of a new family of binary variables allows us to find new valid inequalities, some of which are shown to be facets of the polytope in the higher dimension. We also consider the Winner Determination Problem, which is equivalent to the set packing problem and whose special structure allows us to easily implement these valid inequalities in a very easy way. The computational experiments illustrate the performance of the valid inequalities and obtain good results.     

Valid inequalities and facets of the capacitated plant location problem

Recently, several successful applications of strong cutting plane methods to combinatorial optimization problems have renewed interest in cutting plane methods, and polyhedral characterizations, of integer programming problems. In this paper, we investigate the polyhedral structure of the capacitated plant location problem. Our purpose is to identify facets and valid inequalities for a wide range of capacitated fixed charge problems that contain this prototype problem as a substructure.The first part of the paper introduces a family of facets for a version of the capacitated plant location problem with a constant capacity for all plants. These facet inequalities depend on the capacity and thus differ fundamentally from the valid inequalities for the uncapacited version of the problem.We also introduce a second formulation for a model with indivisible customer demand and show that it is equivalent to a vertex packing problem on a derived graph. We identify facets and valid inequalities for this version of the problem by applying known results for the vertex packing polytope.This research was partially supported by Grant # ECS-8316224 from the National Science Foundation's Program in Systems Theory and Operations Research.     

A cutting plane algorithm for the capacitated facility location problem

The Capacitated Facility Location Problem (CFLP) is to locate a set of facilities with capacity constraints, to satisfy at the minimum cost the order-demands of a set of clients. A multi-source version of the problem is considered in which each client can be served by more than one facility. In this paper we present a reformulation of the CFLP based on Mixed Dicut Inequalities, a family of minimum knapsack inequalities of a mixed type, containing both binary and continuous (flow) variables. By aggregating flow variables, any Mixed Dicut Inequality turns into a binary minimum knapsack inequality with a single continuous variable. We will refer to the convex hull of the feasible solutions of this minimum knapsack problem as the Mixed Dicut polytope. We observe that the Mixed Dicut polytope is a rich source of valid inequalities for the CFLP: basic families of valid CFLP inequalities, like Variable Upper Bounds, Cover, Flow Cover and Effective Capacity Inequalities, are valid for the Mixed Dicut polytope. Furthermore we observe that new families of valid inequalities for the CFLP can be derived by the lifting procedures studied for the minimum knapsack problem with a single continuous variable. To deal with large-scale instances, we have developed a Branch-and-Cut-and-Price algorithm, where the separation algorithm consists of the complete enumeration of the facets of the Mixed Dicut polytope for a set of candidate Mixed Dicut Inequalities. We observe that our procedure returns inequalities that dominate most of the known classes of inequalities presented in the literature. We report on computational experience with instances up to 1000 facilities and 1000 clients to validate the approach.     

The symmetric quadratic traveling salesman problem

In the quadratic traveling salesman problem a cost is associated with any three nodes traversed in succession. This structure arises, e.g., if the succession of two edges represents energetic conformations, a change of direction or a possible change of transportation means. In the symmetric case, costs do not depend on the direction of traversal. We study the polyhedral structure of a linearized integer programming formulation of the symmetric quadratic traveling salesman problem. Our constructive approach for establishing the dimension of the underlying polyhedron is rather involved but offers a generic path towards proving facetness of several classes of valid inequalities. We establish relations to facets of the Boolean quadric polytope, exhibit new classes of polynomial time separable facet defining inequalities that exclude conflicting configurations of edges, and provide a generic strengthening approach for lifting valid inequalities of the usual traveling salesman problem to stronger valid inequalities for the symmetric quadratic traveling salesman problem. Applying this strengthening to subtour elimination constraints gives rise to facet defining inequalities, but finding a maximally violated inequality among these is NP-complete. For the simplest comb inequality with three teeth the strengthening is no longer sufficient to obtain a facet. Preliminary computational results indicate that the new cutting planes may help to considerably improve the quality of the root relaxation in some important applications.     

Using rank-1 lift-and-project closures to generate cuts for 0–1 MIPs, a computational investigation

Various techniques for building relaxations and generating valid inequalities for pure or mixed integer programming problems without special structure are reviewed and compared computationally. Besides classical techniques such as Gomory cuts, Mixed Integer Rounding cuts, lift-and-project and reformulation–linearization techniques, a new variant is also investigated: the use of the relaxation corresponding to the intersection of simple disjunction polyhedra (i.e. the so-called elementary closure of lift-and-project cuts). Systematic comparative computational results are reported on series of test problems including multidimensional knapsack problems (MKP) and MIPLIB test problems. From the results obtained, the relaxation based on the elementary closure of lift-and-project cuts appears to be one of the most promising.     

The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities

The graphical relaxation of the Traveling Salesman Problem is the relaxation obtained by requiring that the salesman visit each city at least once instead of exactly once. This relaxation has already led to a better understanding of the Traveling Salesman polytope in Cornuéjols, Fonlupt and Naddef (1985). We show here how one can compose facet-inducing inequalities for the graphical traveling salesman polyhedron, and obtain other facet-inducing inequalities. This leads to new valid inequalities for the Symmetric Traveling Salesman polytope. This paper is the first of a series of three papers on the Symmetric Traveling Salesman polytope, the next one studies the strong relationship between that polytope and its graphical relaxation, and the last one applies all the theoretical developments of the two first papers to prove some new facet-inducing results.This work was initiated while the authors were visiting the Department of Statistics and Operations Research of New York University, and continued during several visits of the first author at IASI.     

A polyhedral study of the generalized vertex packing problem

The traditional vertex packing problem defined on an undirected graph identifies the largest weighted independent set of nodes, that is, a set of nodes whose induced subgraph contains no edges. In this paper, we examine a generalized vertex packing problem (GVP-k) in which k ``violations' to the independent set restriction are permitted, whereby k edges may exist within the subgraph induced by the chosen set of nodes. A particular context in which such problems arise is in the national airspace planning model of Sherali, Smith, and Trani (2000), where a set of flight-plans need to be composed for various flights subject to conflict, workload, and equity considerations. The GVP-k structure arises in modeling the air-traffic control sector workload restrictions, which stipulate that for each sector and during each discretized time-slot, the number of aircraft conflicts that would need to be resolved should not exceed k, for some k≥1. We derive several classes of facetial valid inequalities for GVP-k for certain specially structured subgraphs, identifying polynomial-sized convex hull representations for some of these cases. Related constraint generation routines are also developed, and some computational results are provided to demonstrate the efficacy of utilizing the proposed valid inequalities in solving GVP-k for different values of k.     

Generating facets for the cut polytope of a graph by triangular elimination

The cut polytope of a graph arises in many fields. Although much is known about facets of the cut polytope of the complete graph, very little is known for general graphs. The study of Bell inequalities in quantum information science requires knowledge of the facets of the cut polytope of the complete bipartite graph or, more generally, the complete k-partite graph. Lifting is a central tool to prove certain inequalities are facet inducing for the cut polytope. In this paper we introduce a lifting operation, named triangular elimination, applicable to the cut polytope of a wide range of graphs. Triangular elimination is a specific combination of zero-lifting and Fourier–Motzkin elimination using the triangle inequality. We prove sufficient conditions for the triangular elimination of facet inducing inequalities to be facet inducing. The proof is based on a variation of the lifting lemma adapted to general graphs. The result can be used to derive facet inducing inequalities of the cut polytope of various graphs from those of the complete graph. We also investigate the symmetry of facet inducing inequalities of the cut polytope of the complete bipartite graph derived by triangular elimination.      

Lift-and-project cuts and perfect graphs

We analyze the application of lift-and-project to the clique relaxation of the stable set polytope. We characterize all the inequalities that can be generated through the application of the lift-and-project procedure, introduce the concept of 1-perfection and prove its equivalence to minimal imperfection. This characterization of inequalities and minimal imperfection leads to a generalization of the Perfect Graph Theorem of Lovász, as proved by Aguilera, Escalante and Nasini [1].Mathematics Subject Classification:05C17, 90C57     

Uncapacitated Euclidean Hub Location: Strengthened Formulation,New Facets and a Relax-and-cut Algorithm

The multiple allocation uncapacitated hub location problem is considered. This problem arises in transportation systems when several locations send and receive passengers and/or express packages and the performance of these systems can be improved by using transshipment points (hubs), where the passengers/packages are collected and distributed. An Integer Programming formulation, the one giving the best computational results until now, serves as a basis for the solution method. Using the fact that the transportation costs between hubs satisfy the triangle inequality, an analysis of the set of solutions that are not candidates to be optimal is carried out and, as a consequence, the formulation of the problem can be strengthened by means of powerful valid inequalities obtained through the study of the intersection graph of an associated set packing problem. The algorithm developed uses the most promising of these inequalities in a Lagrangian relaxation context to reduce the size of the branching tree and improve the computational times. This improvement is shown by means of a computational study, where a set of instances are optimally solved with low computational effort.     

On the 0, 1 facets of the set covering polytope

In this paper, we consider inequalities of the form _jx_j , where _j equals 0 or 1, and is a positive integer. We give necessary and sufficient conditions for such inequalities to define facets of the set covering polytope associated with a 0, 1 constraint matrixA. These conditions are in terms of critical edges and critical cutsets defined in the bipartite incidence graph ofA, and are in the spirit of the work of Balas and Zemel on the set packing problem where similar notions were defined in the intersection graph ofA. Furthermore, we give a polynomial characterization of a class of 0, 1 facets defined from chorded cycles of the bipartite incidence graph. This characterization also yields all the 0, 1 liftings of odd-hole inequalities for the simple plant location polytope.Research partially supported by NSF grant ECS-8601660 and AFORS grant 87-0292.     

Multiprocessor scheduling under precedence constraints: Polyhedral results

We consider the problem of scheduling a set of tasks related by precedence constraints to a set of processors, so as to minimize their makespan. Each task has to be assigned to a unique processor and no preemption is allowed. A new integer programming formulation of the problem is given and strong valid inequalities are derived. A subset of the inequalities in this formulation has a strong combinatorial structure, which we use to define the polytope of partitions into linear orders. The facial structure of this polytope is investigated and facet defining inequalities are presented which may be helpful to tighten the integer programming formulation of other variants of multiprocessor scheduling problems. Numerical results on real-life problems are presented.