Lifted flow cover inequalities for mixed 0-1 integer programs

We investigate strong inequalities for mixed 0-1 integer programs derived from flow cover inequalities. Flow cover inequalities are usually not facet defining and need to be lifted to obtain stronger inequalities. However, because of the sequential nature of the standard lifting techniques and the complexity of the optimization problems that have to be solved to obtain lifting coefficients, lifting of flow cover inequalities is computationally very demanding. We present a computationally efficient way to lift flow cover inequalities based on sequence independent lifting techniques and give computational results that show the effectiveness of our lifting procedures. Received May 15, 1996 / Revised version received August 7, 1998 Published online June 28, 1999     

New valid inequalities for the fixed-charge and single-node flow polytopes

The most effective software packages for solving mixed 0–1linear programs use strong valid linear inequalities derived from polyhedral theory. We introduce a new procedure which enables one to take known valid inequalities for the knapsack polytope, and convert them into valid inequalities for the fixed-charge and single-node flow polytopes. The resulting inequalities are very different from the previously known inequalities (such as flow cover and flow pack inequalities), and define facets under certain conditions.     

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.     

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     

Lifting the knapsack cover inequalities for the knapsack polytope

Valid inequalities for the knapsack polytope have proven to be very useful in exact algorithms for mixed-integer linear programming. In this paper, we focus on the knapsack cover inequalities, introduced in 2000 by Carr and co-authors. In general, these inequalities can be rather weak. To strengthen them, we use lifting. Since exact lifting can be time-consuming, we present two fast approximate lifting procedures. The first procedure is based on mixed-integer rounding, whereas the second uses superadditivity.     

A branch-and-cut algorithm for solving the Non-Preemptive Capacitated Swapping Problem

This paper models and solves a capacitated version of the Non-Preemptive Swapping Problem. This problem is defined on a complete digraph G=(V,A), at every vertex of which there may be one unit of supply of an item, one unit of demand, or both. The objective is to determine a minimum cost capacitated vehicle route for transporting the items in such a way that all demands are satisfied. The vehicle can carry more than one item at a time. Three mathematical programming formulations of the problem are provided. Several classes of valid inequalities are derived and incorporated within a branch-and-cut algorithm, and extensive computational experiments are performed on instances adapted from TSPLIB.     

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.     

n-step mingling inequalities: new facets for the mixed-integer knapsack set

The n-step mixed integer rounding (MIR) inequalities of Kianfar and Fathi (Math Program 120(2):313–346, 2009) are valid inequalities for the mixed-integer knapsack set that are derived by using periodic n-step MIR functions and define facets for group problems. The mingling and 2-step mingling inequalities of Atamtürk and Günlük (Math Program 123(2):315–338, 2010) are also derived based on MIR and they incorporate upper bounds on the integer variables. It has been shown that these inequalities are facet-defining for the mixed integer knapsack set under certain conditions and generalize several well-known valid inequalities. In this paper, we introduce new classes of valid inequalities for the mixed-integer knapsack set with bounded integer variables, which we call n-step mingling inequalities (for positive integer n). These inequalities incorporate upper bounds on integer variables into n-step MIR and, therefore, unify the concepts of n-step MIR and mingling in a single class of inequalities. Furthermore, we show that for each n, the n-step mingling inequality defines a facet for the mixed integer knapsack set under certain conditions. For n?=?2, we extend the results of Atamtürk and Günlük on facet-defining properties of 2-step mingling inequalities. For n ≥ 3, we present new facets for the mixed integer knapsack set. As a special case we also derive conditions under which the n-step MIR inequalities define facets for the mixed integer knapsack set. In addition, we show that n-step mingling can be used to generate new valid inequalities and facets based on covers and packs defined for mixed integer knapsack sets.     

Capacitated facility location: Separation algorithms and computational experience

We consider the polyhedral approach to solving the capacitated facility location problem. The valid inequalities considered are the knapsack cover, flow cover, effective capacity, single depot, and combinatorial inequalities. The flow cover, effective capacity and single depot inequalities form subfamilies of the general family of submodular inequalities. The separation problem based on the family of submodular inequalities is NP-hard in general. For the well known subclass of flow cover inequalities, however, we show that if the client set is fixed, and if all capacities are equal, then the separation problem can be solved in polynomial time. For the flow cover inequalities based on an arbitrary client set and general capacities, and for the effective capacity and single depot inequalities we develop separation heuristics. An important part of these heuristics is based on the result that two specific conditions are necessary for the effective cover inequalities to be facet defining. The way these results are stated indicates precisely how structures that violate the two conditions can be modified to produce stronger inequalities. The family of combinatorial inequalities was originally developed for the uncapacitated facility location problem, but is also valid for the capacitated problem. No computational experience using the combinatorial inequalities has been reported so far. Here we suggest how partial output from the heuristic identifying violated submodular inequalities can be used as input to a heuristic identifying violated combinatorial inequalities. We report on computational results from solving 60 medium size problems. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

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.     

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     

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.     

A multi-item production planning model with setup times: algorithms, reformulations, and polyhedral characterizations for a special case

 We study a special case of a structured mixed integer programming model that arises in production planning. For the most general case of the model, called PI, we have earlier identified families of facet–defining valid inequalities: (l, S) inequalities (introduced for the uncapacitated lot–sizing problem by Barany, Van Roy, and Wolsey), cover inequalities, and reverse cover inequalities. PI is 𝒩𝒫–hard; in this paper we focus on a special case, called PIC. We describe a polynomial algorithm for PIC, and we use this algorithm to derive an extended formulation of polynomial size for PIC. Projecting from this extended formulation onto the original space of variables, we show that (l, S) inequalities, cover inequalities, and reverse cover inequalities suffice to solve the special case PIC by linear programming. We also describe fast combinatorial separation algorithms for cover and reverse cover inequalities for PIC. Finally, we discuss the relationship between our results for PIC and a model studied previously by Goemans. Received: December 13, 2000 / Accepted: December 13, 2001 Published online: October 9, 2002 RID="★" ID="★" Some of the results in this paper have appeared in condensed form in Miller et al. (2001). Key words. mixed integer programming – polyhedral combinatorics – production planning – capacitated lot–sizing – fixed charge network flow – setup times 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.     

Separation algorithms for 0-1 knapsack polytopes

Valid inequalities for 0-1 knapsack polytopes often prove useful when tackling hard 0-1 Linear Programming problems. To generate such inequalities, one needs separation algorithms for them, i.e., routines for detecting when they are violated. We present new exact and heuristic separation algorithms for several classes of inequalities, namely lifted cover, extended cover, weight and lifted pack inequalities. Moreover, we show how to improve a recent separation algorithm for the 0-1 knapsack polytope itself. Extensive computational results, on MIPLIB and OR Library instances, show the strengths and limitations of the inequalities and algorithms considered.     

On the set covering polytope: II. Lifting the facets with coefficients in {0, 1, 2}

In an earlier paper (Mathematical Programming 43 (1989) 57–69) we characterized the class of facets of the set covering polytope defined by inequalities with coefficients equal to 0, 1 or 2. In this paper we connect that characterization to the theory of facet lifting. In particular, we introduce a family of lower dimensional polytopes and associated inequalities having only three nonzero coefficients, whose lifting yields all the valid inequalities in the above class, with the lifting coefficients given by closed form expressions.The research underlying this report was supported by Grant ECS-8601660 of the National Science Foundation, Contract N00014-85-K-0198 with the Office of Naval Research, and Grant AFOSR-870292 of the Air Force Office of Scientific Research.     

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.     

Solving the path cover problem on circular-arc graphs by using an approximation algorithm

A path cover of a graph G=(V,E) is a family of vertex-disjoint paths that covers all vertices in V. Given a graph G, the path cover problem is to find a path cover of minimum cardinality. This paper presents a simple O(n)-time approximation algorithm for the path cover problem on circular-arc graphs given a set of n arcs with endpoints sorted. The cardinality of the path cover found by the approximation algorithm is at most one more than the optimal one. By using the result, we reduce the path cover problem on circular-arc graphs to the Hamiltonian cycle and Hamiltonian path problems on the same class of graphs in O(n) time. Hence the complexity of the path cover problem on circular-arc graphs is the same as those of the Hamiltonian cycle and Hamiltonian path problems on circular-arc graphs.     

Unique lifting of integer variables in minimal inequalities

This paper contributes to the theory of cutting planes for mixed integer linear programs (MILPs). Minimal valid inequalities are well understood for a relaxation of an MILP in tableau form where all the nonbasic variables are continuous; they are derived using the gauge function of maximal lattice-free convex sets. In this paper we study lifting functions for the nonbasic integer variables starting from such minimal valid inequalities. We characterize precisely when the lifted coefficient is equal to the coefficient of the corresponding continuous variable in every minimal lifting (This result first appeared in the proceedings of IPCO 2010). The answer is a nonconvex region that can be obtained as a finite union of convex polyhedra. We then establish a necessary and sufficient condition for the uniqueness of the lifting function.