Given a valid inequality for the mixed integer infinite group relaxation, a lifting based approach is presented that can be used to strengthen this inequality. Bounds on the solution of the corresponding lifting problem and some necessary conditions for the lifted inequality to be minimal for the mixed integer infinite group relaxation are presented. Finally, … Read more
A simple relaxation of two rows of a simplex tableau is a mixed integer set consisting of two equations with two free integer variables and non-negative continuous variables. Recently Andersen et al. (2007) and Cornuejols and Margot (2007) showed that the facet-defining inequalities of this set are either split cuts or intersection cuts obtained from … Read more
Recently minimal and extreme inequalities for continuous group relaxations of general mixed integer sets have been characterized. In this paper, we consider a stronger relaxation of general mixed integer sets by allowing constraints, such as bounds, on the free integer variables in the continuous group relaxation. We generalize a number of results for the continuous … Read more
In recent years there has been growing interest in generating valid inequalities for mixed-integer programs using sets with 2 or more constraints. In particular, Andersen et.al (2007) and Borozan and Cornue’jols (2007) study sets defined by equations that contain exactly one integer variable per row. The integer variables are not restricted in sign. Cutting planes … Read more
Interior point methods have proven very successful at solving linear programming problems. When an explicit linear programming formulation is either not available or is too large to employ directly, a column generation approach can be used. Examples of column generation approaches include cutting plane methods for integer programming and decomposition methods for many classes of … Read more
Abstract: 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 … Read more
In this paper, we develop a convexification tool that enables the construction of convex hulls for orthogonal disjunctive sets using convex extensions and disjunctive programming techniques. A distinguishing feature of our technique is that, unlike most applications of disjunctive programming, it does not require the introduction of new variables in the relaxation. We develop and … Read more
In this note, we present a simple geometric argument to determine a lower bound on the split rank of intersection cuts. As a first step of this argument, a polyhedral subset of the lattice-free convex set that is used to generate the intersection cut is constructed. We call this subset the restricted lattice-free set. It … Read more
Lagrangian relaxation is commonly used to generate bounds for mixed-integer linear programming problems. However, when the number of dualized constraints is very large (exponential in the dimension of the primal problem), explicit dualization is no longer possible. In order to reduce the dual dimension, different heuristics were proposed. They involve a separation procedure to dynamically … Read more
Integer programs defined by two equations with two free integer variables and nonnegative continuous variables have three types of nontrivial facets: split, triangle or quadrilateral inequalities. In this paper, we compare the strength of these three families of inequalities. In particular we study how well each family approximates the integer hull. We show that, in … Read more