Mingling: mixed-integer rounding with bounds

Mixed-integer rounding (MIR) is a simple, yet powerful procedure for generating valid inequalities for mixed-integer programs. When used as cutting planes, MIR inequalities are very effective for mixed-integer programming problems with unbounded integer variables. For problems with bounded integer variables, however, cutting planes based on lifting techniques appear to be more effective. This is not surprising as lifting techniques make explicit use of the bounds on variables, whereas the MIR procedure does not. In this paper we describe a simple procedure, which we call mingling, for incorporating variable bound information into MIR. By explicitly using the variable bounds, the mingling procedure leads to strong inequalities for mixed-integer sets with bounded variables. We show that facets of mixed-integer knapsack sets derived earlier by superadditive lifting techniques can be obtained by the mingling procedure. In particular, the mingling inequalities developed in this paper subsume the continuous cover and reverse continuous cover inequalities of Marchand and Wolsey (Math Program 85:15–33, 1999) as well as the continuous integer knapsack cover and pack inequalities of Atamtürk (Math Program 98:145–175, 2003; Ann Oper Res 139:21–38, 2005). In addition, mingling inequalities give a generalization of the two-step MIR inequalities of Dash and Günlük (Math Program 105:29–53, 2006) under some conditions.     

Generalized mixed integer rounding inequalities: facets for infinite group polyhedra

We present a generalization of the mixed integer rounding (MIR) approach for generating valid inequalities for (mixed) integer programming (MIP) problems. For any positive integer n, we develop n facets for a certain (n + 1)-dimensional single-constraint polyhedron in a sequential manner. We then show that for any n, the last of these facets (which we call the n-step MIR facet) can be used to generate a family of valid inequalities for the feasible set of a general (mixed) IP constraint, which we refer to as the n-step MIR inequalities. The Gomory Mixed Integer Cut and the 2-step MIR inequality of Dash and günlük  (Math Program 105(1):29–53, 2006) are the first two families corresponding to n = 1,2, respectively. The n-step MIR inequalities are easily produced using periodic functions which we refer to as the n-step MIR functions. None of these functions dominates the other on its whole period. Finally, we prove that the n-step MIR inequalities generate two-slope facets for the infinite group polyhedra, and hence are potentially strong.      

Relations between facets of low- and high-dimensional group problems

One-dimensional infinite group problems have been extensively studied and have yielded strong cutting planes for mixed integer programs. Although numerical and theoretical studies suggest that group cuts can be significantly improved by considering higher-dimensional groups, there are no known facets for infinite group problems whose dimension is larger than two. In this paper, we introduce an operation that we call sequential-merge. We prove that the sequential-merge operator creates a very large family of facet-defining inequalities for high-dimensional infinite group problems using facet-defining inequalities of lower-dimensional group problems. Further, they exhibit two properties that reflect the benefits of using facets of high-dimensional group problems: they have continuous variables’ coefficients that are not dominated by those of the constituent low-dimensional cuts and they can produce cutting planes that do not belong to the first split closure of MIPs. Further, we introduce a general scheme for generating valid inequalities for lower-dimensional group problems using valid inequalities of higher-dimensional group problems. We present conditions under which this construction generates facet-defining inequalities when applied to sequential-merge inequalities. We show that this procedure yields some two-step MIR inequalities of Dash and Günlük.     

Intersection cuts for single row corner relaxations

We consider the problem of generating inequalities that are valid for one-row relaxations of a simplex tableau, with the integrality constraints preserved for one or more non-basic variables. These relaxations are interesting because they can be used to generate cutting planes for general mixed-integer problems. We first consider the case of a single non-basic integer variable. This relaxation is related to a simple knapsack set with two integer variables and two continuous variables. We study its facial structure by rewriting it as a constrained two-row model, and prove that all its facets arise from a finite number of maximal \(\left( \mathbb {Z}\times \mathbb {Z}_+\right) \)-free splits and wedges. The resulting cuts generalize both MIR and 2-step MIR inequalities. Then, we describe an algorithm for enumerating all the maximal \(\left( \mathbb {Z}\times \mathbb {Z}_+\right) \)-free sets corresponding to facet-defining inequalities, and we provide an upper bound on the split rank of those inequalities. Finally, we run computational experiments to compare the strength of wedge cuts against MIR cuts. In our computations, we use the so-called trivial fill-in function to exploit the integrality of more non-basic variables. To that end, we present a practical algorithm for computing the coefficients of this lifting function.     

Generating facets for finite master cyclic group polyhedra using n-step mixed integer rounding functions

The n-step mixed integer rounding (MIR) functions generate n-step MIR inequalities for MIP problems and are facets for the infinite group problems. We show that the n-step MIR functions also directly generate facets for the finite master cyclic group polyhedra especially in many cases where the breakpoints of the n-step MIR function are not necessarily at the elements of the group (hence the linear interpolation of the facet coefficients obtained has more than two slopes).     

On a generalization of the master cyclic group polyhedron

We study the master equality polyhedron (MEP) which generalizes the master cyclic group polyhedron (MCGP) and the master knapsack polyhedron (MKP). We present an explicit characterization of the polar of the nontrivial facet-defining inequalities for MEP. This result generalizes similar results for the MCGP by Gomory (1969) and for the MKP by Araóz (1974). Furthermore, this characterization gives a polynomial time algorithm for separating an arbitrary point from MEP. We describe how facet-defining inequalities for the MCGP can be lifted to obtain facet-defining inequalities for MEP, and also present facet-defining inequalities for MEP that cannot be obtained in such a way. Finally, we study the mixed-integer extension of MEP and present an interpolation theorem that produces valid inequalities for general mixed integer programming problems using facets of MEP.     

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.     

Mixing mixed-integer inequalities

Mixed-integer rounding (MIR) inequalities play a central role in the development of strong cutting planes for mixed-integer programs. In this paper, we investigate how known MIR inequalities can be combined in order to generate new strong valid inequalities.?Given a mixed-integer region S and a collection of valid “base” mixed-integer inequalities, we develop a procedure for generating new valid inequalities for S. The starting point of our procedure is to consider the MIR inequalities related with the base inequalities. For any subset of these MIR inequalities, we generate two new inequalities by combining or “mixing” them. We show that the new inequalities are strong in the sense that they fully describe the convex hull of a special mixed-integer region associated with the base inequalities.?We discuss how the mixing procedure can be used to obtain new classes of strong valid inequalities for various mixed-integer programming problems. In particular, we present examples for production planning, capacitated facility location, capacitated network design, and multiple knapsack problems. We also present preliminary computational results using the mixing procedure to tighten the formulation of some difficult integer programs. Finally we study some extensions of this mixing procedure. Received: April 1998 / Accepted: January 2001?Published online April 12, 2001     

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 based on simple mixed-integer sets

In this paper we use facets of simple mixed-integer sets with three variables to derive a parametric family of valid inequalities for general mixed-integer sets. We call these inequalities two-step MIR inequalities as they can be derived by applying the simple mixed-integer rounding (MIR) principle of Wolsey (1998) twice. The two-step MIR inequalities define facets of the master cyclic group polyhedron of Gomory (1969). In addition, they dominate the strong fractional cuts of Letchford and Lodi (2002).     

A polyhedral study of the cardinality constrained knapsack problem

 A cardinality constrained knapsack problem is a continuous knapsack problem in which no more than a specified number of nonnegative variables are allowed to be positive. This structure occurs, for example, in areas such as finance, location, and scheduling. Traditionally, cardinality constraints are modeled by introducing auxiliary 0-1 variables and additional constraints that relate the continuous and the 0-1 variables. We use an alternative approach, in which we keep in the model only the continuous variables, and we enforce the cardinality constraint through a specialized branching scheme and the use of strong inequalities valid for the convex hull of the feasible set in the space of the continuous variables. To derive the valid inequalities, we extend the concepts of cover and cover inequality, commonly used in 0-1 programming, to this class of problems, and we show how cover inequalities can be lifted to derive facet-defining inequalities. We present three families of non-trivial facet-defining inequalities that are lifted cover inequalities. Finally, we report computational results that demonstrate the effectiveness of lifted cover inequalities and the superiority of the approach of not introducing auxiliary 0-1 variables over the traditional MIP approach for this class of problems. Received: March 13, 2003 Published online: April 10, 2003 Key Words. mixed-integer programming – knapsack problem – cardinality constrained programming – branch-and-cut     

Mixed n-step MIR inequalities: Facets for the n-mixing set

Günlük and Pochet [O. Günlük, Y. Pochet, Mixing mixed integer inequalities. Mathematical Programming 90 (2001) 429–457] proposed a procedure to mix mixed integer rounding (MIR) inequalities. The mixed MIR inequalities define the convex hull of the mixing set $\{(y^1,\dots ,y^m,v)\in {\mathbb{Z}}^m\times {\mathbb{R}}_{+}:{\alpha }_1{y}^i+v\ge {\beta }_i,i=1,\dots ,m\}$ and can also be used to generate valid inequalities for general as well as several special mixed integer programs (MIPs). In another direction, Kianfar and Fathi [K. Kianfar, Y. Fathi, Generalized mixed integer rounding inequalities: facets for infinite group polyhedra. Mathematical Programming 120 (2009) 313–346] introduced the $n$-step MIR inequalities for the mixed integer knapsack set through a generalization of MIR. In this paper, we generalize the mixing procedure to the $n$-step MIR inequalities and introduce the mixed $n$-step MIR inequalities. We prove that these inequalities define facets for a generalization of the mixing set with $n$ integer variables in each row (which we refer to as the $n$-mixing set), i.e. $\{(y^1,\dots ,y^m,v)\in {(\mathbb{Z}\times {\mathbb{Z}}_{+}^{n?1})}^m\times {\mathbb{R}}_{+}:{\sum }_{j=1}^n{\alpha }_j{y}_j^i+v\ge {\beta }_i,i=1,\dots ,m\}$. The mixed MIR inequalities are simply the special case of $n=1$. We also show that mixed $n$-step MIR can generate valid inequalities based on multiple constraints for general MIPs. Moreover, we introduce generalizations of the capacitated lot-sizing and facility location problems, which we refer to as the multi-module problems, and show that mixed $n$-step MIR can be used to generate valid inequalities for these generalizations. Our computational results on small MIPLIB instances as well as a set of multi-module lot-sizing instances justify the effectiveness of the mixed $n$-step MIR inequalities.     

Lifted inequalities for 0\mathord {-}1 mixed-integer bilinear covering sets

In this paper, we study $0\mathord {-}1$ mixed-integer bilinear covering sets. We derive several families of facet-defining inequalities via sequence-independent lifting techniques. We then show that these sets have a polyhedral structure that is similar to that of a certain fixed-charge single-node flow set. As a result, we also obtain new facet-defining inequalities for the single-node flow set that generalize well-known lifted flow cover inequalities from the integer programming literature.     

Lattice-free sets,multi-branch split disjunctions,and mixed-integer programming

In this paper we study the relationship between valid inequalities for mixed-integer sets, lattice-free sets associated with these inequalities and the multi-branch split cuts introduced by Li and Richard (Discret Optim 5:724–734, 2008). By analyzing $n$ -dimensional lattice-free sets, we prove that for every integer $n$ there exists a positive integer $t$ such that every facet-defining inequality of the convex hull of a mixed-integer polyhedral set with $n$ integer variables is a $t$ -branch split cut. We use this result to give a finite cutting-plane algorithm to solve mixed-integer programs. We also show that the minimum value $t$ , for which all facets of polyhedral mixed-integer sets with $n$ integer variables can be generated as $t$ -branch split cuts, grows exponentially with $n$ . In particular, when $n=3$ , we observe that not all facet-defining inequalities are 6-branch split cuts.     

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.     

The 0-1 Knapsack problem with a single continuous variable

Specifically we investigate the polyhedral structure of the knapsack problem with a single continuous variable, called the mixed 0-1 knapsack problem. First different classes of facet-defining inequalities are derived based on restriction and lifting. The order of lifting, particularly of the continuous variable, plays an important role. Secondly we show that the flow cover inequalities derived for the single node flow set, consisting of arc flows into and out of a single node with binary variable lower and upper bounds on each arc, can be obtained from valid inequalities for the mixed 0-1 knapsack problem. Thus the separation heuristic we derive for mixed knapsack sets can also be used to derive cuts for more general mixed 0-1 constraints. Initial computational results on a variety of problems are presented. Received May 22, 1997 / Revised version received December 22, 1997 Published online November 24, 1998