A polyhedral study on 0–1 knapsack problems with disjoint cardinality constraints: Strong valid inequalities by sequence-independent lifting

We study the set of 0–1 integer solutions to a single knapsack constraint and a set of non-overlapping cardinality constraints (MCKP), which generalizes the classical 0–1 knapsack polytope and the 0–1 knapsack polytope with generalized upper bounds. We derive strong valid inequalities for the convex hull of its feasible solutions using sequence-independent lifting. For problems with a single cardinality constraint, we derive two-dimensional superadditive lifting functions and prove that they are maximal and non-dominated under some mild conditions. We then show that these functions can be used to build strong valid inequalities for problems with multiple disjoint cardinality constraints. Finally, we present preliminary computational results aimed at evaluating the strength of the cuts obtained from sequence-independent lifting with respect to those obtained from sequential lifting.     

A complete characterization of disjunctive conic cuts for mixed integer second order cone optimization

We study the convex hull of the intersection of a disjunctive set defined by parallel hyperplanes and the feasible set of a mixed integer second order cone optimization (MISOCO) problem. We extend our prior work on disjunctive conic cuts (DCCs), which has thus far been restricted to the case in which the intersection of the hyperplanes and the feasible set is bounded. Using a similar technique, we show that one can extend our previous results to the case in which that intersection is unbounded. We provide a complete characterization in closed form of the conic inequalities required to describe the convex hull when the hyperplanes defining the disjunction are parallel.     

Some properties of convex hulls of integer points contained in general convex sets

In this paper, we study properties of general closed convex sets that determine the closedness and polyhedrality of the convex hull of integer points contained in it. We first present necessary and sufficient conditions for the convex hull of integer points contained in a general convex set to be closed. This leads to useful results for special classes of convex sets such as pointed cones, strictly convex sets, and sets containing integer points in their interior. We then present a sufficient condition for the convex hull of integer points in general convex sets to be a polyhedron. This result generalizes the well-known result due to Meyer (Math Program 7:223–225, 1974). Under a simple technical assumption, we show that these sufficient conditions are also necessary for the convex hull of integer points contained in general convex sets to be a polyhedron.     

Two row mixed-integer cuts via lifting

Recently Andersen et al. [1], Borozan and Cornuéjols [6] and Cornuéjols and Margot [9] have characterized the extreme valid inequalities of a mixed integer set consisting of two equations with two free integer variables and non-negative continuous variables. These inequalities are either split cuts or intersection cuts derived using maximal lattice-free convex sets. In order to use these inequalities to obtain cuts from two rows of a general simplex tableau, one approach is to extend the system to include all possible non-negative integer variables (giving the two row mixed-integer infinite-group problem), and to develop lifting functions giving the coefficients of the integer variables in the corresponding inequalities. In this paper, we study the characteristics of these lifting functions. We show that there exists a unique lifting function that yields extreme inequalities when starting from a maximal lattice-free triangle with multiple integer points in the relative interior of one of its sides, or a maximal lattice-free triangle with integral vertices and one integer point in the relative interior of each side. In the other cases (maximal lattice-free triangles with one integer point in the relative interior of each side and non-integral vertices, and maximal lattice-free quadrilaterals), non-unique lifting functions may yield distinct extreme inequalities. For the latter family of triangles, we present sufficient conditions to yield an extreme inequality for the two row mixed-integer infinite-group problem.     

Nondifferentiable reverse convex programs and facetial convexity cuts via a disjunctive characterization

Disjunctive Programs can often be transcribed as reverse convex constrained problems with nondifferentiable constraints and unbounded feasible regions. We consider this general class of nonconvex programs, called Reverse Convex Programs (RCP), and show that under quite general conditions, the closure of the convex hull of the feasible region is polyhedral. This development is then pursued from a more constructive standpoint, in that, for certain special reverse convex sets, we specify a finite linear disjunction whose closed convex hull coincides with that of the special reverse convex set. When interpreted in the context of convexity/intersection cuts, this provides the capability of generating any (negative edge extension) facet cut. Although this characterization is more clarifying than computationally oriented, our development shows that if certain bounds are available, then convexity/intersection cuts can be strengthened relatively inexpensively.     

Valid inequalities for mixed integer linear programs

This tutorial presents a theory of valid inequalities for mixed integer linear sets. It introduces the necessary tools from polyhedral theory and gives a geometric understanding of several classical families of valid inequalities such as lift-and-project cuts, Gomory mixed integer cuts, mixed integer rounding cuts, split cuts and intersection cuts, and it reveals the relationships between these families. The tutorial also discusses computational aspects of generating the cuts and their strength. Supported by NSF grant DMI-0352885, ONR grant N00014-03-1-0188 and ANR grant BLAN06-1-138894.     

A study of the quadratic semi-assignment polytope

We study a polytope which arises from a mixed integer programming formulation of the quadratic semi-assignment problem. We introduce an isomorphic projection and transform the polytope to a tractable full-dimensional polytope. As a result, some basic polyhedral properties, such as the dimension, the affine hull, and the trivial facets, are obtained. Further, we present valid inequalities called cut- and clique-inequalities and give complete characterizations for them to be facet-defining. We also discuss a simultaneous lifting of the clique-type facets. Finally, we show an application of the quadratic semi-assignment problem to hub location problems with some computational experiences.     

Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case

We give a new mixed integer programming (MIP) formulation for the quadratic cost partition problem that is derived from a MIP formulation for maximizing a submodular function. Several classes of valid inequalities for the convex hull of the feasible solutions are derived using the valid inequalities for the node packing polyhedron. Facet defining conditions and separation algorithms are discussed and computational results are reported.     

A knapsack intersection hierarchy

We introduce a knapsack intersection hierarchy for strengthening linear programming relaxations of packing integer programs. In level t of the hierarchy, all valid cuts are added for the integer hull of the intersection of all t-row relaxations. This model captures the maximum possible strength of t-row cuts, an approach often used by solvers for small t. We investigate the integrality gap of the strengthened formulations on the all-or-nothing flow problem in trees (also called unsplittable flow on trees).     

Strong conical hull intersection property, bounded linear regularity, Jameson’s property (G), and error bounds in convex optimization

The strong conical hull intersection property and bounded linear regularity are properties of a collection of finitely many closed convex intersecting sets in Euclidean space. These fundamental notions occur in various branches of convex optimization (constrained approximation, convex feasibility problems, linear inequalities, for instance). It is shown that the standard constraint qualification from convex analysis implies bounded linear regularity, which in turn yields the strong conical hull intersection property. Jameson’s duality for two cones, which relates bounded linear regularity to property (G), is re-derived and refined. For polyhedral cones, a statement dual to Hoffman’s error bound result is obtained. A sharpening of a result on error bounds for convex inequalities by Auslender and Crouzeix is presented. Finally, for two subspaces, property (G) is quantified by the angle between the subspaces. Received October 1, 1997 / Revised version received July 21, 1998? Published online June 11, 1999     

On mixed-integer sets with two integer variables

We show that every facet-defining inequality of the convex hull of a mixed-integer polyhedral set with two integer variables is a crooked cross cut (which we defined in 2010). We extend this result to show that crooked cross cuts give the convex hull of mixed-integer sets with more integer variables if the coefficients of the integer variables form a matrix of rank 2. We also present an alternative characterization of the crooked cross cut closure of mixed-integer sets similar to the one on the equivalence of different definitions of split cuts presented in Cook et al. (1990) [4]. This characterization implies that crooked cross cuts dominate the 2-branch split cuts defined by Li and Richard (2008) [8]. Finally, we extend our results to mixed-integer sets that are defined as the set of points (with some components being integral) inside a closed, bounded and convex set.     

A recursive procedure to generate all cuts for 0–1 mixed integer programs

We study several ways of obtaining valid inequalities for mixed integer programs. We show how inequalities obtained from a disjunctive argument can be represented by superadditive functions and we show how the superadditive inequalities relate to Gomory's mixed integer cuts. We also show how all valid inequalities for mixed 0–1 programs can be generated recursively from a simple subclass of the disjunctive inequalities.The research of this author was supported by NSF Contract No. ECS-8540898.     

Generalized intersection cuts and a new cut generating paradigm

Intersection cuts are generated from a polyhedral cone and a convex set S whose interior contains no feasible integer point. We generalize these cuts by replacing the cone with a more general polyhedron C. The resulting generalized intersection cuts dominate the original ones. This leads to a new cutting plane paradigm under which one generates and stores the intersection points of the extreme rays of C with the boundary of S rather than the cuts themselves. These intersection points can then be used to generate in a non-recursive fashion cuts that would require several recursive applications of some standard cut generating routine. A procedure is also given for strengthening the coefficients of the integer-constrained variables of a generalized intersection cut. The new cutting plane paradigm yields a new characterization of the closure of intersection cuts and their strengthened variants. This characterization is minimal in the sense that every one of the inequalities it uses defines a facet of the closure.     

On the exact separation of mixed integer knapsack cuts

During the last decades, much research has been conducted on deriving classes of valid inequalities for mixed integer knapsack sets, which we call knapsack cuts. Bixby et?al. (The sharpest cut: the impact of Manfred Padberg and his work. MPS/SIAM Series on Optimization, pp. 309?C326, 2004) empirically observe that, within the context of branch-and-cut algorithms to solve mixed integer programming problems, the most important inequalities are knapsack cuts derived by the mixed integer rounding (MIR) procedure. In this work we analyze this empirical observation by developing an algorithm to separate over the convex hull of a mixed integer knapsack set. The main feature of this algorithm is a specialized subroutine for optimizing over a mixed integer knapsack set which exploits dominance relationships. The exact separation of knapsack cuts allows us to establish natural benchmarks by which to evaluate specific classes of them. Using these benchmarks on MIPLIB 3.0 and MIPLIB 2003 instances we analyze the performance of MIR inequalities. Our computations, which are performed in exact arithmetic, are surprising: In the vast majority of the instances in which knapsack cuts yield bound improvements, MIR cuts alone achieve over 87% of the observed gain.     

Faces for a linear inequality in 0–1 variables

Given a linear inequality in 0–1 variables we attempt to obtain the faces of the integer hull of 0–1 feasible solutions. For the given inequality we specify how faces of a variety of lower-dimensional inequalities can be raised to give full-dimensional faces. In terms of a set, called a “strong cover”, we obtain necessary and sufficient conditions for any inequality with 0–1 coefficients to be a face, and characterize different forms that the integer hull must take. In general the suggested procedures fail to produce the complete integer hull. Special subclasses of inequalities for which all faces can be generated are demonstrated. These include the “matroidal” and “graphic” inequalities, where a count on the number of such inequalities is obtained, and inequalities where all faces can be derived from lower dimensional faces.     

Lifting inequalities: a framework for generating strong cuts for nonlinear programs

In this paper, we introduce the first generic lifting techniques for deriving strong globally valid cuts for nonlinear programs. The theory is geometric and provides insights into lifting-based cut generation procedures, yielding short proofs of earlier results in mixed-integer programming. Using convex extensions, we obtain conditions that allow for sequence-independent lifting in nonlinear settings, paving a way for efficient cut-generation procedures for nonlinear programs. This sequence-independent lifting framework also subsumes the superadditive lifting theory that has been used to generate many general-purpose, strong cuts for integer programs. We specialize our lifting results to derive facet-defining inequalities for mixed-integer bilinear knapsack sets. Finally, we demonstrate the strength of nonlinear lifting by showing that these inequalities cannot be obtained using a single round of traditional integer programming cut-generation techniques applied on a tight reformulation of the problem.      

Polyhedral annexation in mixed integer and combinatorial programming

Polyhedral annexation is a new approach for generating all valid inequalities in mixed integer and combinatorial programming. These include the facets of the convex hull of feasible integer solutions. The approach is capable of exploiting the characteristics of the feasible solution space in regions both “adjacent to” and “distant from” the linear programming vertex without resorting to specialized notions of group theory, convex analysis or projective geometry. The approach also provides new ways for exploiting the “branching inequalities” of branch and bound.