We prove that cutting-plane proofs which use split cuts have exponential length in the worst case. Split cuts, defined by Cook, Kannan, Schrijver (1993), are known to be equivalent to a number of other classes of cuts, namely mixed-integer rounding (MIR) cuts, Gomory mixed-integer cuts, and disjunctive cuts. Our result thus implies the exponential worst-case … Read more
The n-step mixed integer rounding (MIR) functions are used to generate n-step MIR inequalities for (mixed) integer programming problems (Kianfar and Fathi, 2006). We show that these functions are sources for generating extreme valid inequalities (facets) for group problems. We first prove the n-step MIR function, for any positive integer n, generates two-slope facets for … Read more
In this paper, we study the set of 0-1 integer solutions to a single knapsack constraint and a set of non-overlapping cardinality constraints (MCKP). This set is a generalization of the traditional 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 … Read more
This paper addresses the problem of finding cutting planes for multi-stage stochastic integer programs. We give a general method for generating cutting planes for multi-stage stochastic integer programs based on combining inequalities that are valid for the individual scenarios. We apply the method to generate cuts for a stochastic version of a dynamic knapsack problem … Read more
Two-step mixed-integer rounding inequalities are valid inequalities derived from a facet of a simple mixed-integer set with three variables and one constraint. In this paper we investigate how to effectively use these inequalities as cutting planes for general mixed-integer problems. We study the separation problem for single constraint sets and show that it can be … Read more
We present new families of valid inequalities for (mixed) integer programming (MIP) problems. These valid inequalities are based on a generalization of the 2-step mixed integer rounding (MIR), proposed by Dash and Günlük (2006). We prove that for any positive integer n, n facets of a certain (n+1)-dimensional mixed integer set can be obtained through … Read more
Gomory mixed-integer (GMI) cuts generated from optimal simplex tableaus are known to be useful in solving mixed-integer programs. Further, it is well-known that GMI cuts can be derived from facets of Gomory’s master cyclic group polyhedron and its mixed-integer extension studied by Gomory and Johnson. In this paper we examine why cutting planes derived from … Read more
We propose an approximate lifting procedure for general integer programs. This lifting procedure uses information from multiple constraints of the problem formulation and can be used to strengthen formulations and cuts for mixed integer programs. In particular we demonstrate how it can be applied to improve Gomory’s fractional cut which is central to Glover’s primal … Read more
An explicit description of the convex hull of solutions to the uncapacitated lot-sizing problem with backlogging, in its natural space of production, setup, inventory and backlogging variables, has been an open question for many years. In this paper, we identify facet-defining inequalities that subsume all previously known valid inequalities for this problem. We show that … Read more
This paper presents a robust branch-cut-and-price algorithm for the Capacitated Minimum Spanning Tree Problem (CMST). The variables are associated to $q$-arbs, a structure that arises from a relaxation of the capacitated prize-collecting arborescence probem in order to make it solvable in pseudo-polynomial time. Traditional inequalities over the arc formulation, like Capacity Cuts, are also used. … Read more