Surrogate-RLT cuts for zero–one integer programs

In this paper, we consider the class of 0–1 integer problems and develop an effective cutting plane algorithm that gives valid inequalities called surrogate-RLT cuts (SR cuts). Here we implement the surrogate constraint analysis along with the reformulation–linearization technique (RLT) to generate strong valid inequalities. In this approach, we construct a tighter linear relaxation by augmenting SR cuts to the problem. The level-\(d\) SR closure of a 0–1 integer program is the polyhedron obtained by intersecting all the SR cuts obtained from RLT polyhedron formed over each set of \(d\) variables with its initial formulation. We present an algorithm for approximately optimizing over the SR closure. Finally, we present the computational result of SR cuts for solving 0–1 integer programming problems of well-known benchmark instances from MIPLIB 3.0.     

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.     

On Valid Inequalities for Mixed Integer p-Order Cone Programming

We discuss two families of valid inequalities for linear mixed integer programming problems with cone constraints of arbitrary order, which arise in the context of stochastic optimization with downside risk measures. In particular, we extend the results of Atamtürk and Narayanan (Math. Program., 122:1–20, 2010, Math. Program., 126:351–363, 2011), who developed mixed integer rounding cuts and lifted cuts for mixed integer programming problems with second-order cone constraints. Numerical experiments conducted on randomly generated problems and portfolio optimization problems with historical data demonstrate the effectiveness of the proposed methods.     

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.     

Intersection cuts for convex mixed integer programs from translated cones

We develop a general framework for linear intersection cuts for convex integer programs with full-dimensional feasible regions by studying integer points of their translated tangent cones, generalizing the idea of Balas (1971). For proper (i.e, full-dimensional, closed, convex, pointed) translated cones with fractional vertices, we show that under certain mild conditions all intersection cuts are indeed valid for the integer hull, and a large class of valid inequalities for the integer hull are intersection cuts, computable via polyhedral approximations. We also give necessary conditions for a class of valid inequalities to be tangent halfspaces of the integer hull of proper translated cones. We also show that valid inequalities for non-pointed regular translated cones can be derived as intersection cuts for associated proper translated cones under some mild assumptions.     

Solving a multicoloring problem with overlaps using integer programming

This paper presents a new generalization of the graph multicoloring problem. We propose a Branch-and-Cut algorithm based on a new integer programming formulation. The cuts used are valid inequalities that we could identify to the polytope associated with the model. The Branch-and-Cut system includes separation heuristics for the valid inequalities, specific initial and primal heuristics, branching and pruning rules. We report on computational experience with random instances.     

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.     

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.     

Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra

 We consider stochastic programming problems with probabilistic constraints involving random variables with discrete distributions. They can be reformulated as large scale mixed integer programming problems with knapsack constraints. Using specific properties of stochastic programming problems and bounds on the probability of the union of events we develop new valid inequalities for these mixed integer programming problems. We also develop methods for lifting these inequalities. These procedures are used in a general iterative algorithm for solving probabilistically constrained problems. The results are illustrated with a numerical example. Received: October 8, 2000 / Accepted: August 13, 2002 Published online: September 27, 2002 Key words. stochastic programming – integer programming – valid inequalities     

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.      

Valid inequalities for MIPs and group polyhedra from approximate liftings

In this paper, we present an approximate lifting scheme to derive valid inequalities for general mixed integer programs and for the group problem. This scheme uses superadditive functions as the building block of integer and continuous lifting procedures. It yields a simple derivation of new and known families of cuts that correspond to extreme inequalities for group problems. This new approximate lifting approach is constructive and potentially efficient in computation. J.-P. P. Richard was supported by NSF grant DMI-348611.     

bc–opt: a branch-and-cut code for mixed integer programs

A branch-and-cut mixed integer programming system, called bc–opt, is described, incorporating most of the valid inequalities that have been used or suggested for such systems, namely lifted 0-1 knapsack inequalities, 0-1 gub knapsack and integer knapsack inequalities, flowcover and continuous knapsack inequalities, path inequalities for fixed charge network flow structure and Gomory mixed integer cuts. The principal development is a set of interface routines allowing these cut routines to generate cuts for new subsets or aggregations of constraints. The system is built using the XPRESS Optimisation Subroutine Library (XOSL) which includes a cut manager that handles the tree and cut management, so that the user only essentially needs to develop the cut separation routines. Results for the MIPLIB3.0 library are presented - 37 of the instances are solved very easily, optimal or near optimal solution are produced for 18 other instances, and of the 4 remaining instances, 3 have 0, +1, -1 matrices for which bc–opt contains no special features. Received May 11, 1997 / Revised version received March 8, 1999?Published online June 11, 1999     

Polyhedral results for the Equitable Coloring Problem

In this work we study the polytope associated with a 0/1 integer programming formulation for the Equitable Coloring Problem. We find several families of valid inequalities and derive sufficient conditions in order to be facet-defining inequalities. We also present computational evidence of the effectiveness of including these inequalities as cuts in a Branch & Cut algorithm.     

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.     

Modelling either-or relations in integer programming

Logical relations occur frequently in integer programming problems and are modelled by introducing binary variables in association with linear expressions. Applications requiring constraints involving precedence, exclusion, implication and other conditions give rise to the logical relations OR and IMPLIES in the models. These relations will be considered in this paper from a modelling point of view and formulations investigated for situations where the logical variables link sets of integer variables. Valid inequalities (cuts) that can be added to a model will be developed for a number of the formulations and the computational benefits of these cuts will be considered from an experimental point of view by considering the performance of sets of problem instances. New formulations and combinations of older established formulations will be considered. It will be contended that tight formulations may not always be the most successful.     

Conic mixed-integer rounding cuts

A conic integer program is an integer programming problem with conic constraints. Many problems in finance, engineering, statistical learning, and probabilistic optimization are modeled using conic constraints. Here we study mixed-integer sets defined by second-order conic constraints. We introduce general-purpose cuts for conic mixed-integer programming based on polyhedral conic substructures of second-order conic sets. These cuts can be readily incorporated in branch-and-bound algorithms that solve either second-order conic programming or linear programming relaxations of conic integer programs at the nodes of the branch-and-bound tree. Central to our approach is a reformulation of the second-order conic constraints with polyhedral second-order conic constraints in a higher dimensional space. In this representation the cuts we develop are linear, even though they are nonlinear in the original space of variables. This feature leads to a computationally efficient implementation of nonlinear cuts for conic mixed-integer programming. The reformulation also allows the use of polyhedral methods for conic integer programming. We report computational results on solving unstructured second-order conic mixed-integer problems as well as mean–variance capital budgeting problems and least-squares estimation problems with binary inputs. Our computational experiments show that conic mixed-integer rounding cuts are very effective in reducing the integrality gap of continuous relaxations of conic mixed-integer programs and, hence, improving their solvability. This research has been supported, in part, by Grant # DMI0700203 from the National Science Foundation.     

How to Extend the Concept of Convexity Cuts to Derive Deeper Cutting Planes

A new type of cutting plane, termed a decomposition cut, is introduced that can be constructed under the same assumptions as the well-known convexity cut. Therefore it can be applied in algorithms (e.g. cutting plane, branch-and-cut) for various problems of global optimization, such as concave minimization, bilinear programming, reverse-convex programming, and integer programming. In computational tests with cutting plane algorithms for concave minimization, decomposition cuts were shown to be superior to convexity cuts.     

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.     

Strong valid inequalities for fluence map optimization problem under dose-volume restrictions

Fluence map optimization problems are commonly solved in intensity modulated radiation therapy (IMRT) planning. We show that, when subject to dose-volume restrictions, these problems are NP-hard and that the linear programming relaxation of their natural mixed integer programming formulation can be arbitrarily weak. We then derive strong valid inequalities for fluence map optimization problems under dose-volume restrictions using disjunctive programming theory and show that strengthening mixed integer programming formulations with these valid inequalities has significant computational benefits.     

Lifting for conic mixed-integer programming

Lifting is a procedure for deriving valid inequalities for mixed-integer sets from valid inequalities for suitable restrictions of those sets. Lifting has been shown to be very effective in developing strong valid inequalities for linear integer programming and it has been successfully used to solve such problems with branch-and-cut algorithms. Here we generalize the theory of lifting to conic integer programming, i.e., integer programs with conic constraints. We show how to derive conic valid inequalities for a conic integer program from conic inequalities valid for its lower-dimensional restrictions. In order to simplify the computations, we also discuss sequence-independent lifting for conic integer programs. When the cones are restricted to nonnegative orthants, conic lifting reduces to the lifting for linear integer programming as one may expect.