Second-order cover inequalities

We introduce a new class of second-order cover inequalities whose members are generally stronger than the classical knapsack cover inequalities that are commonly used to enhance the performance of branch-and-cut methods for 0–1 integer programming problems. These inequalities result by focusing attention on a single knapsack constraint in addition to an inequality that bounds the sum of all variables, or in general, that bounds a linear form containing only the coefficients 0, 1, and –1. We provide an algorithm that generates all non-dominated second-order cover inequalities, making use of theorems on dominance relationships to bypass the examination of many dominated alternatives. Furthermore, we derive conditions under which these non-dominated second-order cover inequalities would be facets of the convex hull of feasible solutions to the parent constraints, and demonstrate how they can be lifted otherwise. Numerical examples of applying the algorithm disclose its ability to generate valid inequalities that are sometimes significantly stronger than those derived from traditional knapsack covers. Our results can also be extended to incorporate multiple choice inequalities that limit sums over disjoint subsets of variables to be at most one.      

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     

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 using an automatic scheme for obtaining the convex hull defining inequalities of a Weismantel 0–1 knapsack constraint

In this short note we obtain the full set of inequalities that define the convex hull of a 0–1 knapsack constraint presented in Weismantel (1997). For that purpose we use our O(n) procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates, as well as our schemes for coefficient increase based tightening cover induced inequalities and coefficient reduction based tightening general 0–1 knapsack constraints.     

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.     

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.      

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.     

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     

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     

O(n) Procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates

Summary In this paper, we describe computationally efficient procedures for identifying all maximal cliques and non-dominated selected subsets of extensions of minimal covers and alternates that are implied by single 0–1 knapsack constraints. The induced inequalities are satisfied by and 0–1 feasible solution to the knapsack constraint, but are tipically violated by fractional solutions. In addition, the procedures described here are used in conjunction with other constraints to further tighten LP relaxations of 0–1 programs. The complexity of the procedures isO(n). Part of this work has been done while the author was at IBM Research, T.J. Watson Research Center, NY, USA.     

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.     

Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes

Cover inequalities are commonly used cutting planes for the 0–1 knapsack problem. This paper describes a linear-time algorithm (assuming the knapsack is sorted) to simultaneously lift a set of variables into a cover inequality. Conditions for this process to result in valid and facet-defining inequalities are presented. In many instances, the resulting simultaneously lifted cover inequality cannot be obtained by sequentially lifting over any cover inequality. Some computational results demonstrate that simultaneously lifted cover inequalities are plentiful, easy to find and can be computationally beneficial.     

Cutting planes for integer programs with general integer variables

We investigate the use of cutting planes for integer programs with general integer variables. We show how cutting planes arising from knapsack inequalities can be generated and lifted as in the case of 0–1 variables. We also explore the use of Gomory's mixed-integer cuts. We address both theoretical and computational issues and show how to embed these cutting planes in a branch-and-bound framework. We compare results obtained by using our cut generation routines in two existing systems with a commercially available branch-and-bound code on a range of test problems arising from practical applications. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Corresponding author.This research was partly performed when the author was affiliated with CORE, Université Catholique de Louvain.     

Cover and Pack Inequalities for (Mixed) Integer Programming

We review strong inequalities for fundamental knapsack relaxations of (mixed) integer programs. These relaxations are the 0-1 knapsack set, the mixed 0-1 knapsack set, the integer knapsack set, and the mixed integer knapsack set. Our aim is to give a unified presentation of the inequalities based on covers and packs and highlight the connections among them. The focus of the paper is on recent research on the use of superadditive functions for the analysis of knapsack polyhedra. We also present some new results on integer knapsacks. In particular, we give an integer version of the cover inequalities and describe a necessary and sufficient facet condition for them. This condition generalizes the well-known facet condition of minimality of covers for 0-1 knapsacks. The author is supported, in part, by NSF Grants 0070127 and 0218265.     

On tightening cover induced inequalities

Here we describe computationally efficient procedures for tightening cover induced inequalities by using 0–1 knapsack constraints and, if available, cliques whose variables are included in the cover. An interesting application is the case where the cover is implied by the knapsack constraint. The tightening is achieved by increasing the coefficients of the cover inequality. The new constraint is 0–1 equivalent to and LP tighter than the original one. The computational complexity of the procedures is O(n log n), where n is the number of variables in the cover.     

Valid inequalities for the multi-dimensional multiple-choice 0–1 knapsack problem

This paper presents a study of the polytope defined by the minimizing form of the binary knapsack inequality, which is a greater-than-or-equal-to constraint, augmented by disjoint generalized upper bound constraints. A set of valid inequalities, called $\alpha$-cover inequalities, is characterized and dominance relationships among them are established. Both sequential and sequence-independent lifting procedures are presented to tighten an $\alpha$-cover inequality that is not facet defining. Computational results aimed at evaluating the strength of the non-dominated, sequentially, and sequence-independent lifted $\alpha$-cover inequalities are provided.     

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.     

Facet inequalities from simple disjunctions in cutting plane theory

The duality between facets of the convex hull of disjunctive sets and the extreme points of reverse polars of these sets is utilized to establish simple rules for the derivation of all facet cuts for simple disjunctions, namely, elementary disjunctions in nonnegative variables. These rules generalize the cut generation procedure underlying polyhedral convexity cuts with negative edge extensions. The latter are also shown to possess some interesting properties with respect to a biextremal problem that maximizes the distance, from the origin, of the nearest point feasible to the cut. A computationally inexpensive procedure is given to generate facet cuts for simple disjunctions which are dominant with respect to any specified preemptive ordering of variables.     

Cutting plane algorithms for 0-1 programming based on cardinality cuts

We present new valid inequalities for 0-1 programming problems that work in similar ways to well known cover inequalities. Discussion and analysis of these cuts is followed by their revision and use in integer programming as a new generation of cuts that excludes not only portions of polyhedra containing noninteger points, also parts with some integer points that have been explored in search of an optimal solution. Our computational experimentations demonstrate that this new approach has significant potential for solving large scale integer programming problems.     

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.