Lifting two-integer knapsack inequalities

In this paper we discuss the derivation of strong valid inequalities for (mixed) integer knapsack sets based on lifting of valid inequalities for basic knapsack sets with two integer variables (and one continuous variable). The basic polyhedra can be described in polynomial time. We use superadditive valid lifting functions in order to obtain sequence independent lifting. Most of these superadditive functions and valid inequalities are not obtained in polynomial time.     

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.     

Sequence Independent Lifting for Mixed Integer Programs with Variable Upper Bounds

We investigate the convex hull of the set defined by a single inequality with continuous and binary variables with variable upper bound constraints. We extend the traditional flow cover inequality, and show that it is valid for a restriction of the set in which some variables are fixed. We also give conditions under which this inequality is facet-defining and, when it is not, we show how it can be lifted to obtain valid inequalities for the entire set using sequence independent lifting. In general, computing the lifting function is NP-hard, but under an additional restriction on the cover we obtain a closed form. Finally, we show how these results imply and extend known results about the single node fixed charge flow polyhedron. This material is based upon work supported by the National Science Foundation under Grant No. 0084826. Received: April 2004     

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.     

Some Classes of Valid Inequalities and Convex Hull Characterizations for Dynamic Fixed-Charge Problems under Nested Constraints

This paper studies the polyhedral structure of dynamic fixed-charge problems that have nested relationships constraining the flow or activity variables. Constraints of this type might typically arise in hierarchical or multi-period models and capacitated lot-sizing problems, but might also be induced among choices of key variables via an LP-based post-optimality analysis. We characterize several classes of valid inequalities and inductively derive convex hull representations in a higher dimensional space using lifting constructs based on the Reformulation-Linearization Technique. Relationships with certain known classes of valid inequalities for single item capacitated lot-sizing problems are also identified.     

A cutting plane algorithm for the capacitated facility location problem

The Capacitated Facility Location Problem (CFLP) is to locate a set of facilities with capacity constraints, to satisfy at the minimum cost the order-demands of a set of clients. A multi-source version of the problem is considered in which each client can be served by more than one facility. In this paper we present a reformulation of the CFLP based on Mixed Dicut Inequalities, a family of minimum knapsack inequalities of a mixed type, containing both binary and continuous (flow) variables. By aggregating flow variables, any Mixed Dicut Inequality turns into a binary minimum knapsack inequality with a single continuous variable. We will refer to the convex hull of the feasible solutions of this minimum knapsack problem as the Mixed Dicut polytope. We observe that the Mixed Dicut polytope is a rich source of valid inequalities for the CFLP: basic families of valid CFLP inequalities, like Variable Upper Bounds, Cover, Flow Cover and Effective Capacity Inequalities, are valid for the Mixed Dicut polytope. Furthermore we observe that new families of valid inequalities for the CFLP can be derived by the lifting procedures studied for the minimum knapsack problem with a single continuous variable. To deal with large-scale instances, we have developed a Branch-and-Cut-and-Price algorithm, where the separation algorithm consists of the complete enumeration of the facets of the Mixed Dicut polytope for a set of candidate Mixed Dicut Inequalities. We observe that our procedure returns inequalities that dominate most of the known classes of inequalities presented in the literature. We report on computational experience with instances up to 1000 facilities and 1000 clients to validate the approach.     

Valid inequalities for the single-item capacitated lot sizing problem with step-wise costs

This paper presents a new class of valid inequalities for the single-item capacitated lot sizing problem with step-wise production costs (LS-SW). Constant sized batch production is carried out with a limited production capacity in order to satisfy the customer demand over a finite horizon. A new class of valid inequalities we call mixed flow cover, is derived from the existing integer flow cover inequalities by a lifting procedure. The lifting coefficients are sequence independent when the batch sizes (V) and the production capacities (P) are constant and when V divides P. When the restriction of the divisibility is removed, the lifting coefficients are shown to be sequence independent. We identify some cases where the mixed flow cover inequalities are facet defining. We propose a cutting plane algorithm for different classes of valid inequalities introduced in the paper. The exact separation algorithm proposed for the constant capacitated case runs in polynomial time. Computational results show the efficiency of the new class mixed flow cover compared to the existing methods.     

Lifting,superadditivity, mixed integer rounding and single node flow sets revisited

In this survey we attempt to give a unified presentation of a variety of results on the lifting of valid inequalities, as well as a standard procedure combining mixed integer rounding with lifting for the development of strong valid inequalities for knapsack and single node flow sets. Our hope is that the latter can be used in practice to generate cutting planes for mixed integer programs. The survey contains essentially two parts. In the first we present lifting in a very general way, emphasizing superadditive lifting which allows one to lift simultaneously different sets of variables. In the second, our procedure for generating strong valid inequalities consists of reduction to a knapsack set with a single continuous variable, construction of a mixed integer rounding inequality, and superadditive lifting. It is applied to several generalizations of the 0–1 single node flow set. This paper appeared in 4OR, 1, 173–208 (2003). The first author is supported by the FNRS as a chercheur qualifié. This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister’s Office, Science Policy Programming. The scientific responsibility is assumed by the authors.     

Lifting the facets of zero–one polytopes

We discuss a procedure to obtain facets and valid inequalities for the convex hull of the set of solutions to a general zero–one programming problem. Basically, facets and valid inequalities defined on lower dimensional subpolytopes are lifted into the space of the original problem. The procedure generalizes the previously known techniques for lifting facets in two respects. First, the general zero–one programming problem is considered rather than various special cases. Second, the procedure is exhaustive in the sense that it accounts for all the facets (valid inequalities) which are liftings of a given lower dimensional facet (valid inequality).     

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     

Lifting valid inequalities for the precedence constrained knapsack problem

This paper considers the precedence constrained knapsack problem. More specifically, we are interested in classes of valid inequalities which are facet-defining for the precedence constrained knapsack polytope. We study the complexity of obtaining these facets using the standard sequential lifting procedure. Applying this procedure requires solving a combinatorial problem. For valid inequalities arising from minimal induced covers, we identify a class of lifting coefficients for which this problem can be solved in polynomial time, by using a supermodular function, and for which the values of the lifting coefficients have a combinatorial interpretation. For the remaining lifting coefficients it is shown that this optimization problem is strongly NP-hard. The same lifting procedure can be applied to (1,k)-configurations, although in this case, the same combinatorial interpretation no longer applies. We also consider K-covers, to which the same procedure need not apply in general. We show that facets of the polytope can still be generated using a similar lifting technique. For tree knapsack problems, we observe that all lifting coefficients can be obtained in polynomial time. Computational experiments indicate that these facets significantly strengthen the LP-relaxation. Received July 10, 1997 / Revised version received January 9, 1999? Published online May 12, 1999     

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.      

On lifted cover inequalities: A new lifting procedure with unusual properties

Lifted cover inequalities are well-known cutting planes for 0–1 linear programs. We show how one of the earliest lifting procedures, due to Balas, can be significantly improved. The resulting procedure has some unusual properties. For example, (i) it can yield facet-defining inequalities even if the given cover is not minimal, (ii) it can yield facet-defining inequalities that cannot be obtained by standard lifting procedures, and (iii) the associated superadditive lifting function is integer-valued almost everywhere.     

Lifted inequalities for 0-1 mixed integer programming: Superlinear lifting

We study the mixed 0-1 knapsack polytope, which is defined by a single knapsack constraint that contains 0-1 and bounded continuous variables, through the lifting of continuous variables fixed at their upper bounds. We introduce the concept of a superlinear inequality and show that, in this case, lifting is significantly simpler than for general inequalities. We use the superlinearity theory, together with the traditional lifting of 0-1 variables, to describe families of facets of the mixed 0-1 knapsack polytope. Finally, we show that superlinearity results can be extended to nonsuperlinear inequalities when the coefficients of the variables fixed at their upper bounds are large.This research was supported by NSF grants DMI-0100020 and DMI-0121495Mathematics Subject Classification (1991): 90C11, 90C27     

On the polyhedral structure of a multi–item production planning model with setup times

 We present and study a mixed integer programming model that arises as a substructure in many industrial applications. This model generalizes a number of structured MIP models previously studied, and it provides a relaxation of various capacitated production planning problems and other fixed charge network flow problems. We analyze the polyhedral structure of the convex hull of this model, as well as of a strengthened LP relaxation. Among other results, we present valid inequalities that induce facets of the convex hull under certain conditions. We also discuss how to strengthen these inequalities by using known results for lifting valid inequalities for 0–1 continuous knapsack problems. Received: 30 October 2000 / Accepted: 25 March 2002 Published online: September 27, 2002 Key words. mixed integer programming – production planning – polyhedral combinatorics – capacitated lot–sizing – fixed charge network flow Some of the results of this paper have appeared in condensed form in ``Facets, algorithms, and polyhedral characterizations of a multi-item production planning model with setup times', Proceedings of the Eighth Annual IPCO conference, pp. 318-332, by the same authors. This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister's Office, Science Policy Programming. The scientific responsibility is assumed by the authors. This research was also supported by NSF Grant No. DMI-9700285 and by Philips Electronics North America.     

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.     

Dynamic knapsack sets and capacitated lot-sizing

 A dynamic knapsack set is a natural generalization of the 0-1 knapsack set with a continuous variable studied recently. For dynamic knapsack sets a large family of facet-defining inequalities, called dynamic knapsack inequalities, are derived by fixing variables to one and then lifting. Surprisingly such inequalities have the simultaneous lifting property, and for small instances provide a significant proportion of all the facet-defining inequalities. We then consider single-item capacitated lot-sizing problems, and propose the joint study of three related sets. The first models the discrete lot-sizing problem, the second the continuous lot-sizing problem with Wagner-Whitin costs, and the third the continuous lot-sizing problem with arbitrary costs. The first set that arises is precisely a dynamic knapsack set, the second an intersection of dynamic knapsack sets, and the unrestricted problem can be viewed as both a relaxation and a restriction of the second. It follows that the dynamic knapsack inequalities and their generalizations provide strong valid inequalities for all three sets. Some limited computation results are reported as an initial test of the effectiveness of these inequalities on capacitated lot-sizing problems. Received: March 28, 2001 / Accepted: November 9, 2001 Published online: September 27, 2002 RID="★" ID="★" Research carried out with financial support of the project TMR-DONET nr. ERB FMRX–CT98–0202 of the European Union. Present address: Electrabel, Louvain-la-Neuve, B-1348 Belgium. Present address: Electrabel, Louvain-la-Neuve, B-1348 Belgium. Key words. knapsack sets – valid inequalities – simultaneous lifting – lot-sizing – Wagner-Whitin costs     

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.     

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.