On mixed-integer sets with two integer variables

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

Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra

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

A Time Bucket Formulation for the TSP with Time Windows

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

A heuristic to generate rank-1 GMI cuts

Gomory mixed-integer (GMI) cuts are among the most effective cutting planes for general mixed-integer programs (MIP). They are traditionally generated from an optimal basis of a linear programming (LP) relaxation of an MIP. In this paper we propose a heuristic to generate useful GMI cuts from additional bases of the initial LP relaxation. The cuts … Read more

The master equality polyhedron with multiple rows

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

On mixing inequalities: rank, closure and cutting plane proofs

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

Production design for plate products in the steel industry

We describe an optimization tool for a multistage production process for rectangular steel plates. The problem we solve yields a production design (or plan) for rectangular plate products in a steel plant, i.e., a detailed list of operational steps and intermediate products on the way to producing steel plates. We decompose this problem into subproblems … Read more

MIR Closures of Polyhedral Sets

We study the mixed-integer rounding (MIR) closures of polyhedral sets. The MIR closure of a polyhedral set is equal to its split closure and the associated separation problem is NP-hard. We describe a mixed-integer programming (MIP) model with linear constraints and a non-linear objective for separating an arbitrary point from the MIR closure of a … Read more

On a Generalization of the Master Cyclic Group Polyhedron

We study the Master Equality Polyhedron (MEP) which generalizes the Master Cyclic Group Polyhedron and the Master Knapsack Polyhedron. We present an explicit characterization of the polar of the nontrivial facet-defining inequalities for the MEP. This result generalizes similar results for the Master Cyclic Group Polyhedron by Gomory (1969) and for the Master Knapsack Polyhedron … Read more

On the complexity of cutting plane proofs using split cuts

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