Oktay Gunluk In this paper we study the relationship between valid inequalities for mixed-integer sets, lattice-free sets associated with these inequalities and the multi-branch split cuts introduced by Li and Richard (2008). By analyzing $n$-dimensional lattice-free sets, we prove that for every integer $n$ there exists a positive integer $t$ such that every facet-defining inequality of the … Read more
In a recent paper, Dash, Dey and Gunluk (2010) showed that many families of inequalities for the two-row continuous group relaxation and variants of this relaxation are cross cuts or crooked cross cuts, both of which generalize split cuts. Li and Richard (2008) recently studied t-branch split cuts for mixed-integer programs for integers t >= … Read more
Anderson, Cornuejols and Li (2005) show that for a polyhedral mixed integer set defined by a constraint system Ax >= b, where x is n-dimensional, along with integrality restrictions on some of the variables, any split cut is in fact a split cut for a “basic relaxation”, i.e., one defined by a subset of linearly … Read more
We show that every facet-defining inequality of the convex hull of a mixed-integer polyhedral set with two integer variables is a crooked cross cut (which we defined recently in another paper). We then extend this observation to show that crooked cross cuts give the convex hull of mixed-integer sets with more integer variables provided that … Read more
In this paper, we study the relationship between {\em 2D lattice-free cuts}, the family of cuts obtained by taking two-row relaxations of a mixed-integer program (MIP) and applying intersection cuts based on maximal lattice-free sets in $\R^2$, and various types of disjunctions. Recently, Li and Richard (2007) studied disjunctive cuts obtained from $t$-branch split disjunctions … Read more
The Traveling Salesman Problem with Time Windows (TSPTW) is the problem of finding a minimum-cost path visiting a set of cities exactly once, where each city must be visited within a given time window. We present an extended formulation for the problem based on partitioning the time windows into sub-windows, which we call “buckets”. We … Read more
In this paper we survey recent work on the perspective reformulation approach that generates tight, tractable relaxations for convex mixed integer nonlinear programs (MINLP)s. This preprocessing technique is applicable to cases where the MINLP contains binary indicator variables that force continuous decision variables to take the value 0, or to belong to a convex set. … 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
The master equality polyhedron (MEP) is a canonical set that generalizes the Master Cyclic Group Polyhedron (MCGP) of Gomory. We recently characterized a nontrivial polar for the MEP, i.e., a polyhedron T such that an inequality denotes a nontrivial facet of the MEP if and only if its coefficient vector forms a vertex of T. … Read more
We study the mixing inequalities which were introduced by Gunluk and Pochet (2001). We show that a mixing inequality which mixes n MIR inequalities has MIR rank at most n if it is a type I mixing inequality and at most n-1 if it is a type II mixing inequality. We also show that these … Read more