Sequential pairing of mixed integer inequalities

We investigate a scheme, called pairing, for generating new valid inequalities for mixed integer programs by taking pairwise combinations of existing valid inequalities. The pairing scheme essentially produces a split cut corresponding to a specific disjunction, and can also be derived through the mixed integer rounding procedure. The scheme is in general sequence-dependent and therefore leads to an exponential number of inequalities. For some important cases, we identify combination sequences that lead to a manageable set of non-dominated inequalities. We illustrate the framework for some deterministic and stochastic integer programs and we present computational results showing the efficiency of adding the new generated inequalities as cuts.     

Generating lift-and-project cuts from the LP simplex tableau: open source implementation and testing of new variants

Lift-and-project cuts for mixed integer programs (MIP), derived from a disjunction on an integer-constrained fractional variable, were originally (Balas et al. in Math program 58:295–324, 1993) generated by solving a higher-dimensional cut generating linear program (CGLP). Later, a correspondence established (Balas and Perregaard in Math program 94:221–245, 2003) between basic feasible solutions to the CGLP and basic (not necessarily feasible) solutions to the linear programming relaxation LP of the MIP, has made it possible to mimic the process of solving the CGLP through certain pivots in the LP tableau guaranteed to improve the CGLP objective function. This has also led to an alternative interpretation of lift-and-project (L&P) cuts, as mixed integer Gomory cuts from various (in general neither primal nor dual feasible) LP tableaus, guaranteed to be stronger than the one from the optimal tableau. In this paper we analyze the relationship between a pivot in the LP tableau and the (unique) corresponding block pivot (sequence of pivots) in the CGLP tableau. Namely, we show how a single pivot in the LP defines a sequence (potentially as long as the number of variables) of pivots in the CGLP, and we identify this sequence. Also, we give a new procedure for finding in a given LP tableau a pivot that produces the maximum improvement in the CGLP objective (which measures the amount of violation of the resulting cut by the current LP solution). Further, we introduce a procedure called iterative disjunctive modularization. In the standard procedure, pivoting in the LP tableau optimizes the multipliers with which the inequalities on each side of the disjunction are weighted in the resulting cut. Once this solution has been obtained, a strengthening step is applied that uses the integrality constraints (if any) on the variables on each side of the disjunction to improve the cut coefficients by choosing optimal values for the elements of a certain monoid. Iterative disjunctive modularization is a procedure for approximating the simultaneous optimization of both the continuous multipliers and the integer elements of the monoid. All this is discussed in the context of a CGLP with a more general normalization constraint than the standard one used in (Balas and Perregaard in Math program 94:221–245, 2003), and the expressions that describe the above mentioned correspondence are accordingly generalized. Finally, we summarize our extensive computational experience with the above procedures.     

Generating Cuts from Surrogate Constraint Analysis for Zero-One and Multiple Choice Programming

This paper presents a new surrogate constraint analysis that givesrise to a family of strong valid inequalities calledsurrogate-knapsack (S-K) cuts. The analytical procedure presentedprovides a strong S-K cut subject to constraining the values ofselected cut coefficients, including the right-hand side. Ourapproach is applicable to both zero-one integer problems and problemshaving multiple choice (generalized upper bound) constraints. We alsodevelop a strengthening process that further tightens the S-K cutobtained via the surrogate analysis. Building on this, we develop apolynomial-time separation procedure that successfully generates anS-K cut that renders a given non-integer extreme point infeasible. Weshow how sequential lifting processes can be viewed in our framework,and demonstrate that our approach can obtain facets that are notavailable to standard lifting methods. We also provide a relatedanalysis for generating fast cuts. Finally, we presentcomputational results of the new S-K cuts for solving 0-1 integerprogramming problems. Our outcomes disclose that the new cuts arecapable of reducing the duality gap between optimal continuous andinteger feasible solutions more effectively than standard liftedcover inequalities, as used in modern codes such as the CPLEX mixed0-1 integer programming solver.     

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 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.     

Strengthening cuts for mixed integer programs

We give a method for strengthening cutting planes for pure and mixed integer programs. The method improves the coefficients of the integer-constrained variables, while leaving unchanged those of the continuous variables. We first state the general principle on which the method is based; then apply it to the class of cuts that can be obtained from disjunctive constraints. Finally, we give simple procedures for calculating the improved coefficients of cats in this class, and illustrate them on a numerical example.     

A note on the MIR closure and basic relaxations of polyhedra

Anderson et al. (2005) [1] show that for a polyhedral mixed integer set defined by a constraint system Ax≥b, along with integrality restrictions on some of the variables, any split cut is in fact a split cut for a basic relaxation, i.e., one defined by a subset of linearly independent constraints. This result implies that any split cut can be obtained as an intersection cut. Equivalence between split cuts obtained from simple disjunctions of the form x_j≤0 or x_j≥1 and intersection cuts was shown earlier for 0/1-mixed integer sets by Balas and Perregaard (2002) [4]. We give a short proof of the result of Anderson, Cornuéjols and Li using the equivalence between mixed integer rounding (MIR) cuts and split cuts.     

On the separation of disjunctive cuts

Disjunctive cuts for Mixed-Integer Linear Programs (MIPs) were introduced by Egon Balas in the late 1970s and have been successfully exploited in practice since the late 1990s. In this paper we investigate the main ingredients of a disjunctive cut separation procedure, and analyze their impact on the quality of the root-node bound for a set of instances taken from MIPLIB library. We compare alternative normalization conditions, and try to better understand their role. In particular, we point out that constraints that become redundant (because of the disjunction used) can produce over-weak cuts, and analyze this property with respect to the normalization used. Finally, we introduce a new normalization condition and analyze its theoretical properties and computational behavior. Along the way, we make use of a number of small numerical examples to illustrate some basic (and often misinterpreted) disjunctive programming features.     

Branching on general disjunctions

This paper considers a modification of the branch-and-cut algorithm for Mixed Integer Linear Programming where branching is performed on general disjunctions rather than on variables. We select promising branching disjunctions based on a heuristic measure of disjunction quality. This measure exploits the relation between branching disjunctions and intersection cuts. In this work, we focus on disjunctions defining the mixed integer Gomory cuts at an optimal basis of the linear programming relaxation. The procedure is tested on instances from the literature. Experiments show that, for a majority of the instances, the enumeration tree obtained by branching on these general disjunctions has a smaller size than the tree obtained by branching on variables, even when variable branching is performed using full strong branching.     

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.     

On optimizing over lift-and-project closures

The strengthened lift-and-project closure of a mixed integer linear program is the polyhedron obtained by intersecting all strengthened lift-and-project cuts obtained from its initial formulation, or equivalently all mixed integer Gomory cuts read from all tableaux corresponding to feasible and infeasible bases of the LP relaxation. In this paper, we present an algorithm for approximately optimizing over the strengthened lift-and-project closure. The originality of our method is that it relies on a cut generation linear programming problem which is obtained from the original LP relaxation by only modifying the bounds on the variables and constraints. This separation LP can also be seen as dual to the cut generation LP used in disjunctive programming procedures with a particular normalization. We study properties of this separation LP, and discuss how to use it to approximately optimize over the strengthened lift-and-project closure. Finally, we present computational experiments and comparisons with recent related works.     

Fenchel decomposition for stochastic mixed-integer programming

This paper introduces a new cutting plane method for two-stage stochastic mixed-integer programming (SMIP) called Fenchel decomposition (FD). FD uses a class of valid inequalities termed, FD cuts, which are derived based on Fenchel cutting planes from integer programming. First, we derive FD cuts based on both the first and second-stage variables, and devise an FD algorithm for SMIP and establish finite convergence for binary first-stage. Second, we derive FD cuts based on the second-stage variables only and use an idea from disjunctive programming to lift the cuts to the higher dimension space including the first-stage variables. We then devise an alternative algorithm (FD-L algorithm) based on the lifted FD cuts. Finally, we report on computational results based on several test instances from the literature involving the special structure of knapsack problems with nonnegative left-hand side coefficients. The results are promising and show that both algorithms can outperform a standard direct solver and a disjunctive decomposition algorithm on large-scale instances. Furthermore, the FD-L algorithm provides better performance than the FD algorithm in general. Since Fenchel cuts can be computationally expensive in general and are best suited for problems with special structure, both algorithms exploit the special structure of the test instances by reducing the size of the cut generation problems based on the number of nonzero components in the non-integer solution that needs to be cut off.     

Practical strategies for generating rank-1 split cuts in mixed-integer linear programming

In this paper we propose practical strategies for generating split cuts, by considering integer linear combinations of the rows of the optimal simplex tableau, and deriving the corresponding Gomory mixed-integer cuts; potentially, we can generate a huge number of cuts. A key idea is to select subsets of variables, and cut deeply in the space of these variables. We show that variables with small reduced cost are good candidates for this purpose, yielding cuts that close a larger integrality gap. An extensive computational evaluation of these cuts points to the following two conclusions. The first is that our rank-1 cuts improve significantly on existing split cut generators (Gomory cuts from single tableau rows, MIR, Reduce-and-Split, Lift-and-Project, Flow and Knapsack cover): on MIPLIB instances, these generators close 24% of the integrality gap on average; adding our cuts yields an additional 5%. The second conclusion is that, when incorporated in a Branch-and-Cut framework, these new cuts can improve computing time on difficult instances.     

Fixing variables and generating classical cutting planes when using an interior point branch and cut method to solve integer programming problems

Branch and cut methods for integer programming problems solve a sequence of linear programming problems. Traditionally, these linear programming relaxations have been solved using the simplex method. The reduced costs available at the optimal solution to a relaxation may make it possible to fix variables at zero or one. If the solution to a relaxation is fractional, additional constraints can be generated which cut off the solution to the relaxation, but donot cut off any feasible integer points. Gomory cutting planes and other classes of cutting planes are generated from the final tableau. In this paper, we consider using an interior point method to solve the linear programming relaxations. We show that it is still possible to generate Gomory cuts and other cuts without having to recreate a tableau, and we also show how variables can be fixed without using the optimal reduced costs. The procedures we develop do not require that the current relaxation be solved to optimality; this is useful for an interior point method because early termination of the current relaxation results in an improved starting point for the next relaxation.     

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.     

Efficient cuts in Lagrangean ‘Relax-and-cut’ schemes

Lagrangean relaxation produces bounds on the optimal value of (mixed) integer programming problems. These bounds, together with integer feasible solution values, provide intervals bracketing the optimal value of the original problem. When the residual gap, i.e., the relative size of the interval, is too large for the approximations to be deemed satisfactory, it is desirable to ‘strengthen’ the Lagrangean bounds. One possible strengthening technique consists of identifying cuts which are violated by the current Lagrangean solution, and dualizing them. Unfortunately not every valid inequality that is currently violated will improve the Lagrangean relaxation bound when dualized. This paper investigates what makes a violated cut ‘efficient’ in improving bounds. It also provides examples of efficient cuts for several (mixed) integer programming problems.     

Partial convexification cuts for 0–1 mixed-integer programs

In this research, we propose a new cut generation scheme based on constructing a partial convex hull representation for a given 0–1 mixed-integer programming problem by using the reformulation–linearization technique (RLT). We derive a separation problem that projects the extended space of the RLT formulation into the original space, in order to generate a cut that deletes a current fractional solution. Naturally, the success of such a partial convexification based cutting plane scheme depends on the process used to tradeoff the strength of the cut derived and the effort expended. Accordingly, we investigate several variable selection rules for performing this convexification, along with restricted versions of the accompanying separation problems, so as to be able to derive strong cuts within a reasonable effort. We also develop a strengthening procedure that enhances the generated cut by considering the binariness of the remaining unselected 0–1 variables. Finally, we present some promising computational results that provide insights into implementing the proposed cutting plane methodology.     

New Branch-and-Cut Algorithm for Bilevel Linear Programming

Linear mixed 0–1 integer programming problems may be reformulated as equivalent continuous bilevel linear programming (BLP) problems. We exploit these equivalences to transpose the concept of mixed 0–1 Gomory cuts to BLP. The first phase of our new algorithm generates Gomory-like cuts. The second phase consists of a branch-and-bound procedure to ensure finite termination with a global optimal solution. Different features of the algorithm, in particular, the cut selection and branching criteria are studied in details. We propose also a set of algorithmic tests and procedures to improve the method. Finally, we illustrate the performance through numerical experiments. Our algorithm outperforms pure branch-and-bound when tested on a series of randomly generated problems. Work of the authors was partially supported by FCAR, MITACS and NSERC grants.     

A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming

 We establish a precise correspondence between lift-and-project cuts for mixed 0-1 programs, simple disjunctive cuts (intersection cuts) and mixed-integer Gomory cuts. The correspondence maps members of one family onto members of the others. It also maps bases of the higher-dimensional cut generating linear program (CGLP) into bases of the linear programming relaxation. It provides new bounds on the number of facets of the elementary closure, and on the rank, of the standard linear programming relaxation of the mixed 0-1 polyhedron with respect to the above families of cutting planes. Based on the above correspondence, we develop an algorithm that solves (CGLP) without explicitly constructing it, by mimicking the pivoting steps of the higher dimensional (CGLP) simplex tableau by certain pivoting steps in the lower dimensional (LP) simplex tableau. In particular, we show how to calculate the reduced costs of the big tableau from the entries of the small tableau and based on this, how to identify a pivot in the small tableau that corresponds to one or several improving pivots in the big tableau. The overall effect is a much improved lift-and-project cut generating procedure, which can also be interpreted as an algorithm for a systematic improvement of mixed integer Gomory cuts from the small tableau. Received: October 5, 2000 / Accepted: March 19, 2002 Published online: September 5, 2002 Research was supported by the National Science Foundation through grant #DMI-9802773 and by the Office of Naval Research through contract N00014-97-1-0196.