Home
Organizers
Registration
Speakers
Program
Posters
Hotel
Sponsors
Contact Us
Egon Balas and Anureet Saxena
Optimizing over the Split Closure
The polyhedron defined by all the split cuts obtainable directly (i.e. without iterated cut generation) from the LP-relaxation P of a mixed integer program (MIP) is termed the split closure of the MIP. This paper deals with the problem of optimizing over the split closure. This is accomplished by repeatedly solving the following separation problem: given a fractional point, say x, find a rank-1 split cut violated by x or show that none exists. We show that this separation problem can be formulated as a parametric mixed integer linear program (PMILP) with a single parameter in the objective function and the right hand side. We develop an algorithmic framework to deal with the resulting PMILP by creating and maintaining a dynamically updated grid of parameter values, and use the corresponding mixed integer programs to generate rank 1 split cuts. Our approach was implemented in the COIN-OR framework using the CPLEX 9.0 as the general purpose MIP solver. We report our computational results on well-known benchmark instances from MIPLIB 3.0 and Capacitated Warehouse Location Problems from OR-Lib.
Our computational results show that rank-1 split cuts close more than 98% of the duality gap on 14 out of 33 mixed integer instances from MIPLIB 3.0. More than 75% of the duality gap can be closed on additional 11 instances. Rank-1 split cuts close more than 75% of the duality gap on 13 out of 25 pure integer programming instances from MIPLIB 3.0. On average, rank 1 split cuts close about 71% of the duality gap on these instances. We also report our results on two sets of real-world Capacitated Warehouse Location Problem (CWLP) instances from OR-Lib. The first set has 37 instances, each one having 50 customers and 16-50 warehouses. The second set has 12 instances with 1000 customers and 100 warehouses. The split closure closes 100% of the duality gap on all the 37 instances from the first set, and on average about 93% of the duality gap on the 12 instances from the second set. We also gathered statistics on the support size of the disjunctions generated (which affects the density of the resulting cut) and the average size (absolute value) of their coefficients. They turn out to be surprisingly small. This is a joint work with Egon Balas.
Juan Pablo Vielma
A Constructive Characterization of the Split Closure of a Mixed Integer Linear Program
PDF
Two independent proofs of the polyhedrality of the split closure of Mixed Integer Linear Program have been previously presented. Unfortunately neither of these proofs is constructive. In this paper, we present a constructive version of this proof. We also show that split cuts dominate a family of inequalities introduced by Koeppe and Weismantel.
Miroslav Karamanov and Gerard Cornuejols
Cutting Planes Selection
Cutting planes have proved their important role for improving the performance of branch and bound. Present day general purpose MIP solves implement many cut generators. Current power of computers allows generation of a large number of these cuts in a short time. Unfortunately, adding many cuts can be detrimental both to the solution time of the resulting LP and the numerical stability. A procedure that selects a small subset of the pool of generated cuts preserving (to a large extent) the cutting power of the large pool would be beneficial. We report our advance in this direction.
Enrico Malaguti, Michele Monaci and Paolo Toth
A Set-Covering Based Approach for a Weighted Vertex Coloring Problem
We approach a weighted version of the well known Vertex Coloring Problem (VCP) where each vertex i of a graph G has associated a positive weight w(i). Like in the classical VCP, one has to assign a color to each vertex i in such a way that colors on adjacent vertices are different. The objective is to minimize the sum of the costs of colors used, where in this problem the cost of each color is the maximum weight of the vertices that are assigned the color itself. The problem is known to be NP-hard and arises in practical scheduling applications, where it is also known as Time Slot Scheduling of Compatible Jobs. We present a two-phase approach to the problem based on the "Set-Covering" (SC) formulation, in which variables are associated with feasible assignments of a color (i.e., each column corresponds to a stable set). In the first phase (column generation) we generate a large amount of feasible solutions by means of fast greedy heuristics designed for the problem; every generated solution can be improved using two fast post optimization procedures, the first based on the optimal solution of an Integer Linear Programming model, the second on the solution of an Assignment Problem; in the second phase (column optimization) an associated set-covering instance is solved by using a Lagrangian-based heuristic algorithm from the literature. Computational results on instances from the literature are reported.
Valentina Cacchiani, Alberto Caprara and Paolo Toth
Non-Cyclic Train Timetabling and Comparability Graphs
PDF
A common approach to Non-Cyclic Train Timetabling is based on a discretization of the time horizon and the determination of timetables as paths in a suitable space-time graph. Previous methods were based on the definition of an ILP formulation with variables associated with nodes and arcs of this space-time graph, and the Lagrangian relaxation of the so-called track capacity constraints, as the solution of the associated LP relaxation is very time consuming. In this talk we present an alternative (canonical) ILP formulation, with variables associated with paths in the space-time graph, whose LP relaxation can be solved within acceptable computing time by using both column generation and separation of the track capacity constraints. The latter calls for a stable set of maximum weight in a (non-perfect) graph given by the edge intersection of a comparability graph and a complete k-partite graph. We discuss methods to find stable sets and cliques of maximum weight in such a graph.
Jean-Philippe P Richard and Bo Zeng
Constructive Methods to Build Superadditive Functions over Rm
One-dimensional superadditive lifting functions have been shown to be very useful in the derivation of strong cuts from single constraints and simple MIP models. For more general problems with multiple constraints, like in the GUB knapsack problem, lifting valid inequalities usually requires the derivation of strong superadditive functions defined over Rm. In this poster, we give several simple procedures to construct superadditive functions over Rm that are based on a few basic operations on lower-dimensional superadditive functions. The resulting functions are typically stronger then their lower-dimensional counterparts. We illustrate the application of these procedures on different examples including lifted cover inequalities for disjoint cardinality constrained knapsack problems (which include GUB knapsack as a special case), overlapping cardinality constrained knapsack problems and specific knapsack problems with multiple disjoint side constraints. (joint work with Jean-Philippe P Richard)
Shubhashis Ghosh and Ryan Hayward
On Mixed Integer Program Heuristics
Many real world optimization problems can be formulated as a Mixed Integer Program (MIP). In general, finding optimal, or even feasible, MIP solutions is NP-hard. To date, heuristic MIP algorithms are of roughly two types: those that seek a feasible solution, and those that seek an optimal solution. Here we present a new MIP heuristic ``Pivot and Gomory Cut'', which seeks only a feasible solution within an allotted time, integrates Gomory cuts into the bounded variable revised simplex pivoting framework similar to that used in the classic Pivot and Complement heuristic of Balas and Martin. When compared on a standard library of MIPs compiled from sources such as MipLib, this new heuristic is competitive with the recent Feasibility Pump heuristic of Fischetti et al.
In order to generate another set of MIP benchmarks, we present a new class of (experimentally) ``feasibility-hard'' 0-1 MIP instances similar to the optimality-hard instances of Cornuejols and Dawande. Our new heuristic outperforms both Feasibility Pump and ILOG Cplex 9.13 (in both its default and feasibility setting) on this new class of instances in finding a feasible solution.
William Cook, Ricardo Fukasawa, and Marcos Goycoolea
Effectiveness of different cut selection
rules
PDF
Within a Branch-and-Cut framework, one is often faced with the dilemma of choosing, among a large set of cuts generated by a separation oracle, a reasonably sized subset. The problem of selecting such a subset, which Padberg and Rinaldi (1991) called a "central issue in the area of polyhedral cutting-plane algorithms", has received scant attention in research literature. In this work, we consider this problem from several different points of view and present experimental results illustrating the effectiveness of different cut selection rules for TSPLIB and MIPLIB problems.
Ming Zhao and Ismael de Farias
The polar of a simple mixed-integer set
We present a polar approach to study the convex hull P of a set that generalizes the mixed-integer rounding (MIR) set of Nemhauser and Wolsey and the mixing-MIR set of Gunluk and Pochet. We give a compact full inequality description of the polar of P. Our description is minimal, i.e. all inequalities in it define facets of the polar (i.e. they give the extreme points and rays of P.) In the worst case, the number of inequalities in our description grows exponentially. However, under some natural assumptions, it grows polynomially. We give a polynomial-time separation algorithm over the polar and we show that optimization over P can be performed in polynomial time. Finally, we discuss some generalizations.
Jim Luedtke and George Nemhauser
Planning Activities with Start-Time Dependent Variable Costs
PDF
We present a multiple period planning model, motivated by an industrial application, in which the variable costs of activities over the entire horizon are determined by the technology available when an activity is begun. It is assumed that future technology will improve, leading to lower variable costs if the start-time of the activity is delayed. This leads to a minimization problem with a nonconvex objective. Formulations and valid inequalities are presented that can be used to solve the problem in a branch-and-cut framework.
Santanu S. Dey and Jean-Philippe P. Richard
Facets for Two-Dimensional Mixed Integer Infinite
Group Problem
< a href="posters/Dey.pdf">PDF
In 2003, Gomory and Johnson studied one-dimensional infinite group problems in the paper entitled `T-space and cutting plane'. They also raised the question of studying facets of higher dimensional infinite group problems, in an attempt to use information from multiple constraints to generate stronger inequalities for general mixed integer programs. In this research we study the two-dimensional mixed integer infinite group problem (2DMIIGP) and introduce tools to analyze functions over the two dimensional infinite group. We present two different constructions that yield the first known families of facet-defining inequalities for 2DMIIGP. The first construction uses valid inequalities of the one dimensional integer infinite group problem as building blocks for creating inequalities for the two-dimensional integer infinite group problem. This construction also provides a complete characterization of the continuous piecewise linear facets of the two-dimensional group problem that have exactly two gradients. The second construction has three gradients and yields facet-defining inequalities of 2DMIIGP whose continuous coefficients are not dominated by any one-dimensional mixed integer group cut generated from the individual constraints.
Gabor Pataki and Anureet Saxena
A General Framework for Intersection Cuts
Given a polyhedron P and a vertex $\bar{x}$, we define the basis cone at $\bar{x}$ as the cone that arises by extending the edges of P from $\bar{x}$.
An intersection cut from the disjunctive set
D = { x | xi=0 V xi=1 }over P can be viewed in 3 equivalent ways.
We examine to what extent these 3 notions generalize, and remain equivalent, when D is replaced by a general disjunction. If all terms in D have one row only, 1) and 2) remain equivalent, with one caveat: in 2), for some rays, we must intersect D with the reverse of the ray. The possibility of deriving such "bidirectional" intersection cuts has been mentioned in an unpublished note of Balas. The equivalence with 3) also holds under some additional conditions.
We discuss the extensions when the terms are defined by possibly more than one row. In particular, we give a complete characterization of the optimal solution set of the cut generation LP in the case, when only the sum of disjunctive multipliers is bounded.
Sanjeeb Dash and Oktay Gunluk
On the strength of Gomory mixed-integer cuts as group cuts
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. The master cyclic group polyhedron has a rich polyhedral structure and a very natural question to ask is whether or not it has other facets that would lead to useful cutting planes for mixed-integer programs. We call such cuts "group cuts", and in this paper we study whether any non-GMI group cuts are useful when used in conjunction with GMI cuts. For many practical problem instances, we numerically show that once GMI cuts from different rows of the optimal simplex tableau are added to the formulation, all other group cuts from the same tableau rows are satisfied.
Kumar Abhishek, Sven Leyffer, and Jeff Linderoth
FilMINT: A Solver for Mixed Integer Nonlinear
Programs
PDF
We introduce a Mixed Integer Nonlinear Programming (MINLP) solver that implements a linearization-based algorithm in a branch-and-cut framework. We make use of the advanced features of the MILP framework, including cutting planes, primal heuristics, branching and node selection rules, for solving the problem. We show how to use the framework to add and manage the various kinds of linearizations. The solver FilMINT (FILter-Mixed INTeger optimizer) uses MINTO's branch-and-cut framework for solving the MILP, and uses Filter-SQP, an active-set solver, for solving the nonlinear problems. We focus on solving convex MINLP problems, while also coming up with heuristics to handle nonconvexity. The results of the detailed computational experiments are presented, highlighting the effectiveness of the solver framework.