July 25 - 29, 2005
Conflict analysis for infeasible subproblems is one of the key ingredients in modern SAT solvers to cope with large real-world instances. In contrast, it is common practice for today's mixed integer programming solvers to just discard infeasible subproblems and the information they reveal.
In this talk we try to remedy this situation by generalizing SAT infeasibility analysis to mixed integer programming. We present heuristics for branch-and-cut solvers to generate valid inequalities from the current infeasible subproblem and the associated branching information. SAT techniques can then be used to strengthen the resulting cuts. We performed computational experiments which show the potential of our method: On feasible MIP instances, the number of required branching nodes was reduced by 50% in the geometric mean. However, the total solving time increased by 20%. On infeasible MIPs arising in the context of chip verification, the number of nodes was reduced by 90%,thereby reducing the solving time by 60%.
In the MaxFS problem, given an infeasible linear system
Ax>=b, one wishes to find a feasible subsystem containing
a maximum number of inequalities. This NP-hard problem
has interesting applications in a variety of fields. In
some challenging applications in telecommunications and
computational biology one faces very large MaxFS
instances with up to millions of inequalities in
thousands of variables. We propose to tackle large-scale
instances of MaxFS using randomized and thermal variants
of the classical relaxation method for solving systems of
linear inequalities. We establish lower bounds on the
probability that these methods identify an optimal
solution within a given number of iterations. These
bounds, which are expressed as a function of a condition
number of the input data, imply that with probability 1
these randomized methods identify an optimal solution
after
finitely many iterations. Computational results obtained
for medium- to large-scale instances arising in the design
of linear classifiers, in the planning of digital video
broadcasts and in the modelling of the energy functions
driving protein folding, indicate that an efficient
implementation of such a method perform very well in
practice.
Joint work with P. Belotti and R. Hauser.
Joint work with Yves Pochet.
We consider the following question: Is it possible to replace a constraint
of a MIP formulation with a new and tighter inequality? We
show that, if there is a valid inequality, which dominates a constraint
of the formulation, then there is a coefficient in the formulation that
can be strengthened. We also show that an algorithm, which is based
on strengthening one coefficient at a time, stops after a finite number
of strengthening steps. We give examples for which the difference between
the quality of the original formulation and a resulting strengthened
formulation is relatively large: on some problems, the effect of
modifying the coefficients in the original formulation is larger than the
effect of adding a large number of cutting planes (in terms of amount
of integrality gap closed). For instance, on one MIPLIB instance, all
of the integrality gap is closed by strengthening the coefficients in the
initial formulation while optimizing over the first Chvatal closure only
closes 61% of the integrality gap. We also solve another "hard" instance
to optimality by strengthening coefficients in every round of a
cutting plane algorithm based on mixed integer Gomory cuts and split
cuts. The same cutting plane algorithm was unable to solve this instance
without including the strengthening step. The instance was only
recently solved with an approach based on the first Chvatal closure.
We finish by demonstrating how coefficient strengthening can be
used to design a model for a production scheduling problem. First, an
initial formulation of a small problem is produced, and the coefficients
in this formulation are strengthened with expensive techniques. The
resulting formulation is then evaluated by tracing the logic of each
strengthened coefficient. The result is a new understanding of how to
build a tight formulation of the problem. We believe this suggests that
it might be of interest to construct a tool for strengthening coefficients.
In a recent joint paper with Michael Perregaard a
precise correspondence was established between lift-and-project
cuts for mixed 0-1 programs, simple disjunctive cuts
(intersection cuts) and mixed-integer Gomory cuts. The
correspondence maps members of one family onto members of the
others. It also establishes a many-to-one mapping between bases
of the higher-dimensional cut generating linear program (CGLP)
and bases of the linear programming relaxation of the given
mixed integer program. As a result, an algorithm is developed
that solves (CGLP) without explicitly constructing it, by
mimicking the pivoting steps of the higher dimensional (CGLP)
simplex tableau by certain pivoting steps in the lower
dimensional LP simplex tableau. Due to the smaller problem size
and the vastly reduced number of pivots needed by the new
algorithm, it finds a deepest lift-and-project cut typically in
a fraction of the time needed by the original (CGLP)-based
algorithm.
The new cut generating procedure can also be interpreted as an
algorithm for systematically strengthening mixed integer Gomory
(MIG) cuts. Starting with a MIG cut from a given source row k
of the optimal LP simplex tableau, a certain sequence of pivots
is performed, each of which results in a new simplex tableau,
generally neither primal nor dual feasible, such that the MIG
cut from the same source row k is guaranteed to be stronger (in
terms of the amount by which it cuts off the LP optimum) then
the previous MIG cut. In other words, if S is the set of all
bases (feasible or not) of the LP relaxation, this procedure
finds a member B of S such that the MIG cut from row k of the
simplex tableau associated with B is strongest over all bases
in S.
After extensive computational testing, the new procedure has
been incorporated in the MIP module of the commercial code
XPRESS, where it serves as the default cut generating routine.
1. Funding issues
Is IP research still fundable?
Differences between US and Europe
2. Raising IP's profile
Does the profile need to be raised? If so, how?
New application areas?
3. Cultivating a research community
How to increase collaboration
Differences between US and Europe
4. IP research directions--What are "the next big ideas?"
5. IP education
6. The next conference?
Does this conference have its own niche? (IPCO/MPS/etc.)
When?
Where?
During the past decade several major power blackouts affected North America, Europe and South America. It is quite likely (in fact, expected) that more serious events will take place in the future, with potentially very damaging consequences to economies and public health. Rather than being the result of particular economic or operational factors, the blackouts can be seen as caused by the inherent complexity entailed by modern transmission networks, which comprise thousands of nodes and links and span very large geographical areas.
In this talk we will describe ongoing work on solving a number of optimization models related to the design, maintenance and operation of electrical power transmission networks. This is joint work with Sara Mattia (Rome).
In this talk we discuss the polyhedral structure of the convex hull of the integer single node flow set with two possible values for the upper bounds on the arc flows. These mixed integer sets may arise as substructure of more complex mixed integer sets that model the feasible solutions of real application problems such as network design, location and lotsizing. We give a complete description of this special integer single node flow polyhedron based on the generalization of the description of the integer single node flow polyhedron with two arcs. All the coefficients of the facet-defining inequalities can be computed in polynomial time adapting a known algorithm from Hirschberg and Wong (1976) for the two integer knapsack problem. We report on computational experience.
Joint work with Agostinho Agra.
Given a set of continuous variables and for each variable a constant,
a cardinality constraint requires that no less than a specified number
of variables is equal to their corresponding constants. Cardinality
constraints appear in several applications, such as feature selection
in data mining. I will present a polyhedral study of problems with
cardinality constraints and a branch-and-cut approach to solve them.
In particular, I will present a few unusual properties of these
polyhedra.
Joint work with Ming Zhao.
For the solution of hard integer programs with
branch-and-cut
algorithms it is a necessity to check during the separation
phase for
violated inequalities of the stable set relaxation of the
instances
conflict graph. These conflict graphs turn out to be sparse.
For instance the majority (39/60) of the new and difficult
MIPLIB2003 integer programs contain
large substructures with constraints of type
x
_{i} 1
for
binary variables.
A stable set in a graph G=(V,E) is a set of pairwise
nonadjacent
vertices. A common approach for finding a maximum weight
stable set
of G is
to optimize over the convex hull STAB(G) of the incidence
vectors of stable sets; this approach requires
knowledge of strong valid inequalities and algorithms to
separate
them.
We present an O(|V|
^{2}|E|+|V|
^{3}log |V|)
separation
algorithm
for the nonsimple 1-wheel inequalities
(Cheng and Cunningham, 1995), which is faster than the
previously known
O(|V|
^{4}) algorithm. In particular this is faster
for
the sparse instances coming from the conflict graphs of
general
integer programs.
This poster describes a heuristic method for mixed integer programming
(MIP), and its incorporation into PICO, a highly parallel
branch-and-bound MIP solver. The heuristic performs pivot-based
rounding with the help of a concave integrality merit function. The
surrounding branch-and-bound environment begins with a synchronous
"ramp-up" phase, and then transitions to asynchronous tree-parallel
search. During ramp-up, there are several ways of inducing
parallelism: using multiple alternative merit functions, and
partitioning the search space by prospective branching. I discuss how
to combine these two approaches and how to prospectively branch on
multiple layers of variables, along with implementation and
computational results for the PICO MIP solver.
Edmonds showed in 1965 that the convex hull of all matchings of a
graph can be obtained by applying one round of Gomory-Chv'atal cutting
planes to the fractional matching polytope. More precisely, he showed
that this convex hull can be described by non-negativity, degree and
odd-set constraints.
15 years later, Minty and Sbihi showed that a
maximum-cardinality stable set in a claw-free graph can be computed in
polynomial time, thereby generalizing Edmonds' algorithm for maximum
cardinality matching. Since then, it is a long standing open problem
to find an explicit description of the stable set polytope of
claw-free graphs.
In this talk we show that the convex hull of stable sets of quasi-line
graphs is obtainable by applying one round of split cuts. The class
of quasi-line graphs is a proper superclass of line graphs and a
proper subclass of claw-free graphs for which it is known that not all
facets have 0/1 normal vectors. The necessary split-cuts are a
generalization of Edmonds' odd-set inequalities, called clique family
inequalities.
Joint work with G. Oriolo, P. Ventura and G. Stauffer.
In the first part of the talk, we use facets of simple mixed-integer sets with three variables to derive a parametric family of valid inequalities for general mixed-integer sets. We call these inequalities "two-step MIR inequalities" as they can be derived by applying the simple mixed-integer rounding (MIR) principle of Wolsey (1998) twice.
In the second part, we study the shooting experiment of Gomory which computationally identifies "important" facets of the cyclic group polyhedra. This idea has recently been re-considered by Evans (2002) and Gomory, Johnson and Evans (2003). We present computational results that suggest that MIR and two-step MIR inequalities are important.
In the last part of the talk, we present computational experience with general mixed-integer programs.
Joint work with Sanjeeb Dash at IBM Research.
Given a complete graph G=(V,E) with edge weight on each edge, we consider the problem of partitioning the vertices of graph G into subcliques that have at least S vertices, so as to minimize the total weight of the edges that have both endpoints in the same subclique. In this poster, we consider using branch-and-price method to solve the problem. We demonstrated the necessity of cutting planes for this problem and suggested effective ways of adding cutting planes in the branch-and-price framework. The NP hard pricing problem is solved as an integer programming problem. We present some preliminary computational results on large randomly generated problems.
Joint work with Gerard Cornuejols.
This paper considers a modification of the branch-and-cut
algorithm for Mixed Integer Linear Programming problems
where branching is performed on general disjunctions rather
than on variables. We introduce a procedure for selecting
promising disjunctions based on a heuristic measure of
disjunction quality. This measure exploits the relation
between branching disjunctions and intersection cuts. In
this work, we focus on disjunctions defining mixed integer
Gomory cuts. The procedure is tested on instances from the
literature. Experiments show that the proposed procedure is
more efficient than branching on variables for a majority of
the instances. The metrics we consider are solution time and
tree size for the instances that could be solved to
optimality within a given time limit, and integrality gap
closed for the remaining instances.
We consider the general integer program P: max {c'x : Ax=b; x
nonnegative integer}
which has a well-known abstract dual optimization problem stated in
terms of superadditive
functions. Using a linear program equivalent to P, introduced recently,
we show that its dual
can be interpreted as a simplified and more tractable form of the
abstract dual, and identifies
a subclass of superadditive functions, sufficient to consider in the
abstract dual. This class
of superadditive functions is also used to characterize the integer
hull of the convex polytope
{x : Ax=b; x nonnegative}.
In recent years a lot of work has been devoted to general-purpose methods for finding good heuristic solutions to Integer and Mixed Integer Linear Programs (MIPs). Some of these methods are now successfully integrated in commercial and non commercial MIP solvers. We review these results, compare some of the techniques, discuss advantages and drawbacks and we try to give a flavor of what has still to be done in the area.
Industrial switching involves moving materials on rail cars within
or between industrial complexes and connecting with other rail
carriers. Planning tasks include the making up of trains with a
minimum shunting effort, the feasible and timely routing through an
in-plant rail network on short paths, and assigning and scheduling
of locomotives under safety and network capacity aspects. A human
planner must often resort to routine and simple heuristics, not
least for the reason of unavailability of computer aided
suggestions. In this project we propose mixed integer programming
models to capture the whole process at once in order to obtain
optimal or provably good solutions. Column generation allows us to
work with linear programming relaxations with a huge number of
variables. This popular technique has almost attained an industry
standard level and usually enables one to set up appropriate models
quickly. The challenge hides in the actual implementation which
still needs tailoring to the particular application. Our work is
based on practical data from a German in-plant railroad.
This talk is an overview of techniques used to handle problems with symmetries. For problems modeled as integer linear programs (ILP), three essentially different and mutually exclusive approaches have been used: Reformulations, symmetry-breaking inequalities, and isomorphism pruning.
Reformulation is mostly used to handle problems where the symmetries come from the set of all permutations of a set of objects, inducing a permutation group on the variables. Some (or most) symmetries are removed from the formulations and additional branching strategies become available. The price to pay is that the reformulation has an exponential number of variables that must be handled by column generation techniques.
Adding symmetry breaking inequalities is probably the most natural way to try to handle symmetries. Several papers report strong improvements when using the best possible symmetry breaking set of inequalities. Methods for deriving such sets have been devised, but little is known about finding the most efficient set.
Isomorphism pruning is based on the theory of isomorphism-free backtracking procedure for enumeration problems. When coupled with a Branch-and-Cut algorithm, additional options for generating isomorphism-related cuts and setting variables are available. Improvements of several orders of magnitude for running time and enumeration tree size have been observed on highly symmetric 0-1 problems. Extensions of the techniques to ILP with variables bounded to a small set and to ILP corresponding to coloring problems are also available.
We present a restructuring of the computations in Lenstra's methods for solving mixed integer linear programs. A concept of Adjoint lattices is introduced and used for this purpose. This allows us to develop branching on hyperplane algorithms in the space of original variables, without requiring any dimension reduction for pure or mixed integer programs. Reduced lattice basis are also computed in the space of original variables. Based on these results we give a new natural heuristic way of generating branching hyperplanes, and discuss its relationship with recent reformulation techniques of Aardal and Lenstra. We show that the reduced basis available at the root node has useful information on the branching hyperplanes for the generalized branch-and-bound tree. Our development allows us to give algorithms for mixed convex integer programs with properties similar to those for the mixed integer linear programs. Implementation of this algorithm in a prototype software system "IMPACT" is described. Computational results are presented on difficult knapsack and market split problems using this approach.
We propose a very simple preconditioning method for integer programming feasibility
problems: applying basis reduction to the constraint matrix, to make its columns shorter in
euclidean norm, and more orthogonal. Our approach -- termed column basis reduction, and abbreviated as CBR --
simplifies and generalizes the reformulation technique proposed for
equality constrained IPs by Aardal, Hurkens, Lenstra and others.
We describe a family of IP instances, called decomposable knapsack problems,
that generalize the ones proposed by Jeroslow, Chvatal and Todd, Avis, Aardal and Lenstra,
and Wolsey. We prove that 1) they need an exponential number of nodes
to solve, when branch-and-bound branching on individual variables is applied;
2) after the application of column basis reduction, a constant number of nodes suffice.
A subclass of decomposable knapsack problems is called cascade problems.
They were created to illustrate the surprising fact, that in hard IPs
a "thin" direction is sometimes not the best to branch on.
Besides having this structure, the cascade problems
-- despite having only one dense constraint -- are as difficult for commercial MIP solvers,
as the well-known marketshare problems.
Our computational study shows
that most difficult IPs recently used to test nontraditional IP algorithms
-- subset sum, strongly correlated knapsack problems, the marketshare problems, and our cascade problems --
become easy for a commercial IP solver after our preconditioning is applied.
Joint work with Bala Krishnamoorthy at Washington State University.
Several disjunctive cuts for mixed integer programs are (directly or
indirectly) based on imposing a simple disjunction where a single
fractional variable is required to be rounded either up or down to its
nearest integer value. Two well-known cut families based on such a
disjunction is Gomory's mixed integer cut and the lift-and-project cuts
from the 1990s. Both cut classes involves strengthening by considering
the integrality of other variables. This strengthening can be
interpreted as a modification of the underlying simple disjunction.
Later research into disjunctive cuts have taken this idea of
strengthening the underlying disjunction even further.
The most common method for solving a mixed integer program is by
branch-and-bound. Almost all such available codes branch on a single
variable at a time. For general mixed integer programs, where the
integer variables are allowed a wider range than simple 0-1 variables,
such a simple branching scheme can often lead to an explosion in the
number of nodes the code has to search. In this talk I examine the
feasibility of applying the ideas for strengthening cuts to the simple
branching disjunctions for the purpose of creating better mixed integer
branches. Results from computational tests on a variety of public
benchmark problems, using an implementation based on the Xpress-MP
solver, will be used to demonstrate the effects of such strengthened
branches.
National Statistical Agencies needs automatic tools for detecting
errors in records not satisfying a set of consistency rules.
The topic is known as Statistical Data Editing, and a very
interesting Optimization Problem is the so-called Error Localization
Problem.
It concerns finding the minimum number of fields in an invalid record
such that by modifying these values the new record satisfies all the rules.
It is an NP-hard problem because the "Minimum Weight Solution to Linear
Equations"
is a particular case. Also the Error Localization Problem is very important
in Signal Processing (the problem is then called "Basis Selection Problem"),
where information must be encoded and sent, or received and decoded,
through a Telecommunication Network.
We present an exact method, based on a Benders' decomposition approach,
solving instances with up to 100 fields and 40 edits. We also produce
a variant of this approach to solve heuristically larger instances.
Some procedures of this descending search make use of the Farkas' Lemma
in Linear Programming. Computational experience on randomly
generated instances shows that the approach can deal with
instances of up to 1000 fields and 400 edits.
The generality of the consistency rules makes the Error Localization Problem
very close to a general Mixed Integer Programming. Still, there is some
structure.
Therefore, we will open a discussion to the audience on how new results in
Mixed Integer Programming could help solving Error Localization Problems,
and viceversa!
This is part of a joint research work with Jorge Riera-Ledesma, University
of La Laguna, Tenerife, Spain.
The polyhedron defined by all the split cuts obtainable directly (i.e.
without iterated cut generation) from the LP-relaxation 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. By the equivalence of
optimization and separation, we can restrict our attention to the following
separation problem: given a fractional point, say x, find a 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
discuss a branch and bound algorithm for PMILP, based on solving a
parametric linear program at every node of the search tree, while using
warm-start basis information. Further, we recast the PMILP as the problem of
minimizing a function that is the infimum of a family of convex functions.
As a result, for several sub-classes of split cuts, the PMILP can be
deparameterized. Implementation and experimentation is under way.
A terminating algorithm is developed for the problem of
finding the point of smallest norm in the convex hull of a given
finite point set in a finite dimensional space. The proposed
algorithm mimics Ph. Wolfe's algorithm (Wolfe'76) developed for
the Euclidean norm and shares all of its basic properties. The
proposed algorithm has great potential as a numerical mechanism
to generating consecutive deepest disjunctive cuts in integer programming.
We propose a new formulation for the capacitated minimum spanning tree problem that leads to a robust branch-and- cut-and-price algorithm. The formulation allows the use of cuts expressed over a very large set of variables, without changing the pricing subproblem or increasing the size of LPs that are actually solved. Cuts over those variables can be quite strong, and generalize many previous know families of cuts, including capacity, root cutsets and multistars. Computation results on benchmark instances from the OR-Library show very significant improvements over previously known algorithms, specially on non-unitary weight instances.
Joint work with D.Andrade, R.Fukasawa, J.Lysgaard and M.Poggi de Aragao.
In Branch-and-Price algorithms, implementing the branching scheme can be
challenging. Branching constraints may imply modifications to the pricing
problem. This is a main concern for the development of a generic
branch-and-price code that should run using only the pricing oracle
provided by the user. The issue has not stop people from using
Branch-and-Price. Firstly, branching is straightforward for many
applications (we shall
characterize the class of problem for which this is the
case). Then, Ryan and Foster (1981) proposed a scheme for applications
that can be reformulated as a set covering problem.
Beyond that, a general scheme was presented by Vanderbeck (2000) but
it may result in significant modifications to the pricing problem. An
alternative is the scheme of
Villeneuve et al. (2003) that consists in applying branching in the
original formulation, but this introduces symmetry in the
Dantzig-Wolfe reformulation when the problem structure involves
several identical blocks. The branching scheme presented here builds on
the aboves.
It can be can be implemented using only the oracle provided for the
original pricing problem.
Branching constraints are not dualized in a Lagrangian way but are
convexified in the
subproblem.
This talk deals with mixed integer optimization problems defined by
linear constraints and a polynomial function as the objective function.
We present motivating examples, illustrate techniques that reduce
the problem to a mixed integer linear program and discuss complexity results.
An algorithm is prersented that is based on Barvinok's rational
function theory, i.e., lattice points in polyhedra
are encoded through rational functions.
It turns out that under the assumption that the number of variables is fixed,
our algorithm leads to a fully polynomial time approximation scheme.
The results of this talk are based on joint work with
Raymond Hemmecke, Matthias Koeppe and Jesus De Loera.
Very little is known about the polyhedral structure of
even simple mixed integer programs. Here we study a very simple
set, called the mixing set. This set and valid inequalities for
it were proposed by Gunluk and Pochet in an effort to explain and
understand why the same procedure of "mixing mixed integer
rounding (MIR) inequalities" gave valid inequalities for many
different variants of the constant capacity lot-sizing problem,
and subsequently Miller and Wolsey took this abstraction a little
further by considering the intersection of mixing sets plus
certain additional constraints.
In this talk we pursue this effort at abstraction by considering
two "abstract sets"
that are generalizations of the mixing set.
We show that, modulo a
slight restriction, the convex hulls of both sets are obtained
with mixing inequalities. This is joint work with Michele Conforti
and Marco di Summa.
Turning back to lot-sizing, we show that a constant capacity
problem with production time windows, and surprisingly both a
multi-item problem with a joint set-up variable, and a class of
single item problems with varying capacities can also be solved by
mixing. The latter is joint work with Yves Pochet.
PDF file with formulations
We give necessary and sufficient conditions for the local optimal
solutions of the minimum sum-of-squares clustering problem and its
continuous relaxation. Especially, we show that the objective function of
the mixed integer program is concave and each local solution of its
continuous relaxation is integer. We then adapt Tuy's concavity cuts to
the continuous relaxation to search for a global optimal solution of the
clustering problem. Numerical results show that our algorithm general
gives a better solution than the popular k-means method starting from the
same point without increasing computation time too much. (In the
proceedings of the 5th SIAM international conference on data mining.
http://optlab.mcmaster.ca/~xiay/papers/ssqeproced.pdf Presentation slides
available at http://optlab.mcmater.ca/~xiay/papers/ssqeslides.pdf