PROGRAM
Monday 714:45-15:30 | William Cook | 50+ Years of Combinatorial Integer Programming |
| | |
16:00-16:45 | Laurence Wolsey | Decomposition and Reformulation in Integer Programming |
| | |
Chair: | George Nemhauser and William Pulleyblank |
17:00-19:45 | The Pioneers | Panel: 50 Years of Integer Programming |
| | |
Tuesday 8Chair: | Giovanni Rinaldi |
08:30-09:15 | Ralph Gomory | 40 Years of Corner Polyhedra |
| | |
09:15-09:45 | Ricardo Fukasawa | Numerically Accurate Gomory Mixed Integer Cuts | The validity of Gomory Mixed Integer Cuts
relies on the correctness of
arithmetic calculations, which is not guaranteed in floating point arithmetic used by modern computers.
In practice, numerical tolerances and low rank cuts are used to try to overcome this problem.
These measures, however, do not guarantee that the resulting cuts will be valid.
In this work we propose solutions to always generate valid cuts, and analyze the trade-offs in working harder to generate them. |
| | |
09:45-10:15 | Adam Letchford | Separation Algorithms for the 0-1 Knapsack Polytope | It has been known for some time that valid inequalities for the 0-1 knapsack polytope can be used effectively as cutting planes for general 0-1 linear programs. We present some new results on the separation problems associated with these inequalities. We give:
1. An exact separation algorithm for the extended cover inequalities of Balas (1975) that runs in O(nb) time, where n is the number of items and b is the capacity of the knapsack.
2. A remarkably effective separation heuristic for the lifted cover inequalities of Balas (1975) and Wolsey (1975), that runs in O(n^2) time.
3. An exact separation algorithm for the weight inequalities of Weismantel (1997) that runs in O((n+a')b) time, where a' is the weight of the largest item.
4. An exact separation algorithm for the 0-1 knapsack polytope itself.
Computational experiments on MIPLIB instances have given interesting and very encouraging results.
This talk is based on joint work with Konstantinos Kaparis, University of Southampton. |
| | |
Chair: | Gerhard Reinelt |
10:45-11:15 | Matteo Fischetti | Looking inside Gomory | We discuss an implementation of the lexicographic version of Gomory's fractional cutting plane method and of two heuristics mimicking the latter one. In computational testing on a battery of
MIPLIB problems we compare the performance of these variants with that of the standard Gomory algorithm, both in the single-cut and in the multi-cut (rounds of cuts) version, and show that they provide a radical improvement over the standard procedure. In particular, we report the exact solution of ILP instances from MIPLIB such as stein15, stein27, and bm23, for which the standard Gomory cutting plane algorithm is not able to close more than a tiny fraction of the integrality gap.
(Joint work with Egon Balas and Arrigo Zanette) |
| | |
11:15-11:45 | Francisco Barahona | On the Integrality of the Facility Location Polytope | We study a system of linear inequalities
associated with the uncapacitated facility location problem.
We show that this system defines a polytope with integer
extreme points if and only if the graph does not contain a
certain type of odd cycles. We give a polynomial algorithm to recognize this type of cycles.
We also derive odd cycle inequalities
and give a separation algorithm. |
| | |
11:45-12:15 | Mourad Baïou | On the Linear Relaxation of the p-Median Problem | We study a well-known linear programming relaxation of the p-median problem. We characterize all directed graphs for which this system of inequalities defines an integral polytope. This shows that for these graphs the p-median problem is easy to solve. We also have a polynomial algorithm that recognizes this class of graphs. |
| | |
Chair: | Laurence Wolsey |
17:15-18:00 | Jean-Philippe Richard | Group Relaxations for Integer Programming | In this talk, we give a review of the group relaxation approach for the solution of mixed integer programs. We first survey the seminal work of Gomory and Johnson on finite and infinite group problems. Second, we describe the different tools that have been proposed for the study of group problems, including newer results that have been introduced for group problems with multiple constraints. Third, we discuss the recent computational work of various authors regarding the corner polyhedron and group cuts. We conclude with remarks and possible directions of future research with respect to the group approach. |
| | |
18:00-18:30 | Santanu Dey | Facets of High-Dimensional Infinite Group Problem | One way to construct the Gomory Mixed Integer Cuts (GMIC) is the following: (a) Create a single-row group relaxation of a MIP. (b) Fix the integer variables to zero and generate a minimal cut with respect to the continuous variables. (c) Then lift the integer variables into this cut. Recently, Andersen et al. (2006), Borozan and Cornuejols (2007), and Cornu\'ejols and Margot (2007) characterized the minimal and extreme inequalities for the two-row group relaxation in which the integer variables are fixed to zero. In this talk, we consider ways to lift the integer variables into these cuts (i.e., generating cuts similar to the GMIC, except now using two rows). |
| | |
18:30-19:00 | Kati Wolter | C-MIR Approach for Flow Cover Cuts | Different classes of valid inequalities for the 0-1 single node flow set have been studied in the literature and superadditive lifting procedures have been suggested to strengthen them. This includes generalized flow cover inequalities. Furthermore, it is well known that particular complemented mixed integer rounding (c-MIR) inequalities for certain mixed knapsack relaxations of the 0-1 single node flow set are at least as strong as special cases of generalized flow cover inequalities.
The branch-and-cut framework SCIP incorporates a cutting plane separator which utilizes this approach. In this talk, we introduce our separation heuristic for the so-called c-MIR flow cover cuts and present computational results concerning the impact of different aspects of the algorithm. Computational experiments have shown that our final separator helps to improve the overall performance of SCIP even if it is used in combination with the general c-MIR separator. |
| | |
19:00-19:30 | Andrea Tramontani | Experiments with Split Cuts | Joint work with Andrea Lodi and Matteo Fischetti.
Split cuts are a famous class of disjunctive cuts for mixed
integer linear programs. By fixing a priori the disjunction, split
cuts can be separated by solving a so called Cut Generating Linear
Program (CGLP). The CGLP is however defined on a polyhedral cone
which needs to be truncated by means of some normalization
conditions, and different normalization conditions yield very
different cuts. Another important class of valid inequalities are
Mixed Integer Gomory (MIG) cuts. Violated MIG cuts can be read
from the optimal simplex tableau without any computational effort.
We recall the correspondence between MIG cuts from the simplex
tableau and basic solutions of the CGLP, and we investigate the
impact of the normalization on the separated inequalities. We
compare different normalization conditions showing that even the
most effective ones can ``select" optimal basic solutions of the
CGLP corresponding to very weak cuts. In particular, we show that
redundant constraints hurt the separation procedure, since they
create many ``weak" vertices of the CGLP and can cheat the
normalization in selecting ``strong" cuts. A computational
analysis is reported and
discussed. |
| | |
Wednesday 9Chair: | Paolo Toth |
08:30-09:15 | François Margot | Symmetry in Integer Programming |
| | |
09:15-09:45 | Ugo Pietropaoli | A New Algorithm for the Stable Set Problem in Claw-free Graphs |
| | |
09:45-10:15 | Claudio Gentile | Gear Composition and the Stable Set Problem | We present a new graph composition that produces a graph $G$ from a given graph $H$ and a fixed graph $B$ called gear and we study its polyhedral properties.
This composition yields counterexamples to a conjecture on the facial structure of $STAB(G)$ when $G$ is claw-free.
(Joint work with A. Galluccio and P. Ventura) |
| | |
Chair: | Martin Grötschel |
10:45-11:15 | Klaus Truemper | A Linear SAT Algorithm for Certain 2CNF/3CNF Formulas | NOTE: If there is pressure, forget about this talk and give the slot to others.
If you would like to hear the talk:
We define a satisfiability problem
called 3IFFSAT that is a particular
case of SAT. The instances consist
of a combination of 2CNF and 3CNF
clauses. The problem 3IFFSAT
is NP-complete. But for a subclass that
arises from certain applications, the problem can be solved in linear time using logic decomposition techniques. |
| | |
11:15-11:45 | Annegret Wagler | From Experimental Data to Biological Models | Biology and molecular medicine are two areas of research with a high potential of discovering fundamental mechanisms that may influence our way of thinking about the living cell or the human body. So far, the majority of results discovered in these areas are based on intuitive interpretation of experimental or statistical data. A key question is whether mathematics can contribute to advance these fields.
In this talk we shall give a clear positive answer by presenting an exact mathematical approach to a fundamental problem in systems biology, namely, to the problem of reconstructing structure and function of causal interaction networks of biological systems from experimental data. Our approach
provides a provenly complete list of all feasible network alternatives that
account for the experimentally observed mass or signal flux in the system (or ensures that no solution exists using the considered parameters only).
|
| | |
11:45-12:15 | | | |
Chair: | Claude Lemaréchal |
17:15-18:00 | Franz Rendl | Semidefinite Relaxations for Integer Programming |
| | |
18:00-18:30 | Kurt Anstreicher | A Computable Characterization of the Convex Hull of LowDimensional Quadratic Forms | It has recently been shown that a very general class of continuous and discrete NP-hard optimization problems can be formulated as linear problems over the cone of completely positive (CPP) matrices. CPP matrices are also doubly nonnegative (DNN), and up to size 4x4 these matrix classes agree. For the 5x5 case we give a precise characterization of how a matrix that is DNN but not CPP differs from a CPP matrix. We also show how an extreme matrix of this type can be separated from the cone of CPP matrices. (Joint work with Sam Burer and Mirjam Duer) |
| | |
18:30-19:00 | Miguel Anjos | Solving Minimum k-Partition Problems Using Semidefinite Programming | The minimum k-partition (MkP) problem is the problem of partitioning the set of vertices of a graph into k disjoint subsets so as to minimize the total weight of the edges joining vertices in the same partition. We propose a branch-and-cut algorithm based on semidefinite programming (SBC) for the MkP problem. The two key ingredients for this algorithm are: the combination of
semidefinite programming with polyhedral results; and a novel iterative clustering heuristic (ICH) that finds feasible solutions for the MkP problem. The SBC algorithm computes globally optimal solutions for dense graphs with up to 60 vertices, for grid graphs with up to 100 vertices, and for different values of k, providing the best exact approach to date for 3 or more partitions.
This is joint work with Bissan Ghaddar (Waterloo) and Frauke Liers (Cologne).
|
| | |
19:00-19:30 | Ismael de Farias | Branch-and-Cut for Separable Piecewise Linear Optimization | Piecewise linear functions (PLFs) are important on their own and as an approximation to nonlinear functions. Beale and Tomlin showed that modeling PLFs through special ordered sets of type 2 (SOS2) is far superior to using 0-1 variables. Here we give cutting planes that are valid for the SOS2 formulation. Our computational experience shows that our cutting planes reduce tremendously the time required by MIP branch-and-cut and SOS2 branch-and-bound for finding an optimum of a separable PLF subject to linear constraints.
Joint work with Ming Zhao. |
| | |
Thursday 10Chair: | Uwe Zimmermann |
08:30-09:15 | Robert Weismantel | Nonlinear Integer Programming | A central result in the theory of integer optimization states that a system of linear diophantine equations $A x = b$ has no integral solution if and only if there exists a vector in the dual lattice, $y^TA$ integral such that $y^Tb$ is fractional. We extend this result to systems that both have equations and inequalities $\{Ax=b, Cx\leq d\}$.
We show that a certificate of integral infeasibility is a linear system with $\rank(C)$ variables
containing no integral point.
The result also extends to the mixed integer setting. This is joint work with Q. louveaux and K. Andersen. |
| | |
09:15-09:45 | Monique Guignard | The Convex Hull Relaxation for Nonlinear Integer Programming Problems |
| | |
09:45-10:15 | Dennis Michaels | On the Computation of the Convex Envelope for a Nonlinear Function | joint work with Matthias Jach and Robert Weismantel
For deriving strong global bounds on the optimal value of mixed-integer nonlinear optimization problems, the question of determining the convex
and convave envelopes for nonlinear functions is of major interest.
Despite this necessity of having convex and concave envelopes at hand, very little is known in the literature.
The limited availability of formulas for the envelopes is due to the fact that their standard representations are
non-convex optimization problems that are intractable, in general.
In this talk we show how to reduce the problem of computing the envelopes to lower-dimensional optimization problems when
the underlying function meets certain convexity properties. |
| | |
Chair: | Rainer Burkard |
10:45-11:15 | Thomas Magnanti | Minimizing with Concave Cost? | Concave cost minimization arises frequently in practice, yet little seems to be known about how to solve these problems (optimally or approximately). We show how to use methods from fixed cost minimization to solve generic and specilized versions of concave cost minimization problems.
This is joint work with Dan Stratila. |
| | |
11:15-11:45 | Jon Lee | Nonlinear Matroid Optimization and Extensions | We give an efficient algorithmic framework for optimizing the sum of an binary-encoded "external" weight function and an arbitrary function of a fixed number of "internal" weight functions over a set of integer points, when the internal weights are encoded in binary but take only a fixed number of values. The framework yields an efficient algorithm when the integer points come from the bases or independent sets of a matroid/polymatroid or from a multi-dimensional knapsack. We also have an efficient algebraic algorithm for the case of vectorial matroids, when the internal weights are encoded in unary and there is no external weight function. For the case of bases of a matroid, we describe an application to model fitting. Joint work with Robert Weismantel and Shmuel Onn. |
| | |
11:45-12:15 | Antoine Musitelli | Recognition of Binet Matrices | Binet matrices furnish a direct generalization of network matrices and arise from the node-edge incidence matrices of bidirected graphs in the same way as network matrices do from directed graphs. We provide a polynomial-time algorithm for testing whether a given matrix is binet. |
| | |
Chair: | Bernhard Korte |
17:15-18:00 | Michel Balinski | The Majority Judgement | The majority judgement provides a theoretical and practical answer to the problem of finding a mechanism that amalgamates the opinions, evaluations or "preferences" of many individuals into a society's or a jury's opinion, evaluation and rank-ordering of candidates or alternatives. In particular, it does away with the classical paradoxes and impossibilities of traditional social choice theory (including Arrow's). It has been tested in elections and wine competitions. |
| | |
18:00-18:30 | Andreas Schulz | Encouraging Cooperation in Sharing Supermodular Costs | Many problems in combinatorial optimization have supermodular, or
increasing marginal optimal costs. In a cooperative game with
supermodular
costs, the average cost per player increases as the number of players
increases, diminishing the appeal of sharing costs with other
players. This
observation leads us to wonder, "how much do we need to penalize a
coalition
of players for defecting in order to achieve cooperation?" This
notion is
captured in the least core and least core value of a cooperative
game. In
this talk, we consider the computational complexity and
approximation of the
least core value of supermodular cost cooperative games, and
uncover some
structural properties of the least core of these games along the way. |
| | |
18:30-19:00 | Natashia Boland | Constrained Shortest Path Problems | The problem of finding a shortest path in a network, subject to a single additive resource constraint, is the simplest case of a constrained network shortest path problem. Resource constrained shortest path problems abound as subproblems, for example, in column generation for airline planning problems. This talk will review recent progress interleaving Lagrangian relaxation, preprocessing and enumeration, to accelerate solution of such problems. Application to paths in Euclidean space will be discussed, and a network discretization of space presented that can be proved to give paths that converge to globally optimal solutions, even for highly non-convex objectives. |
| | |
19:00-19:30 | Gyula Pap | Node-Capacitated Packing of A-paths |
| | |
Chair: | Michel Balinski, Robert Bixby, Rolf Möhring, and George Nemhauser |
21:00-23:00 | Let's discuss the future of our scientific community! |
| | |
Friday 11Chair: | Rolf Möhring |
08:30-09:15 | Friedrich Eisenbrand | Integer Programming and Number Theory |
| | |
09:15-09:45 | Júlia Pap | Recognizing Conic TDI Systems is Hard |
| | |
09:45-10:15 | Johannes Hatzl | Combinatorial Properties of a Domination Problem with Parity Constraints | We consider various properties of a parity domination problem: given a graph $G$, one is looking for a subset $S$ of the vertex set such that the open/closed neighborhood of each vertex contains an even/odd number of vertices in $S$ (it is prescribed individually for each vertex which of these applies). We define the parameter $s(G)$ to be the number of solvable instances out of $4^n$ possibilities
and study the properties of this parameter. Upper and lower bounds for general graphs and trees
are given as well as a recurrence formula for rooted
trees. Furthermore, we give explicit formulas in several special cases and investigate random graphs. |
| | |
Chair: | Jack Edmonds |
10:45-11:15 | Richard Karp | How Hard are the NP-hard Problems? |
| | |
11:15-11:45 | Peter Gritzmann | Optimal Wire Ordering and Spacing in Low Power Semiconductor Design | A key issue for high integration circuit design in the semiconductor industry are power constraints that stem from the eed for heat removal and reliability or battery lifetime limitations. As the power consumption depends heavily on
the capacitances between adjacent wires, determining the optimal ordering and
spacing of parallel wires is an mportant issue in the design of low power chips.
As it turns out, optimal wire spacing is a convex optimization problem while the combined optimal wire spacing and ordering is a special class of the minimal Hamilton-path problem. While the latter is NP-hard in general, the
present paper provides an $O{N \log N}$ algorithm that solves the underlying coupled ordering and spacing problem for $N$ parallel wires to optimality.
Joint work with Michael Ritter and Paul Zuber |
| | |
11:45-12:15 | Marco Di Summa | Network Formulations of Mixed-Integer Programs | We study the class of mixed-integer sets defined by a totally unimodular constraint matrix with at most two nonzero entries per row. We present a technique to construct an extended formulation for any set $M$ in the family, and we give sufficient conditions for the formulation to be compact. Our technique is based on the explicit enumeration of all possible fractional parts that the continuous variables take over the set of vertices of the convex hull of $M$.
We also illustrate practical applications of our results.
(Joint work with M. Conforti, F. Eisenbrand and L.A. Wolsey.) |
| | |
Chair: | Denis Naddef |
17:15-18:00 | Andrea Lodi | Computation in Integer Programming |
| | |
18:00-18:30 | Thomas McCormick | Strongly Polynomial Algorithms for Bi-Submodular Minimization | (joint with Fabio Tardella, Frieda Granot, and Maurice Queyranne)
We consider the min cut problem when capacities depend on a parameter
$\lam$. There are some classes of this parametric min cut problem
that are known to have the nice structural property that min cuts are
nested in $\lam$, and the nice algorithmic property that all min cuts
can be computed in the same asymptotic time as one call to
Push-Relabel. We extend these results in several directions: we find
three much more general classes of problems for which these two nice
properties continue to hold, and we extend other results with the same
flavor as well.
|
| | |
18:30-19:00 | Michael Ritter | Optimal Flight Scheduling at Airports | For each major airport, a new long-term flight schedule is created every six months using a lengthy process and a lot of manual work. A flight schedule is subject to a set of regulations, the most important being bounds on the number of flights within certain overlapping time windows. The structure of these time windows leads to flight schedules that, although not optimal, cannot accomodate additional flights. In the talk, we present a MIP model for the flight scheduling problem that takes into account all relevevant regulations and demands of the airlines and use a Branch-and-Bound approach to obtain optimal flight schedules. Based on the model, we will also investigate the combinatorics of the rules governing a flight schedule to answer the question why suboptimal flight schedules frequently occur in practice and how the regulations could be modified to obtain better and more robust solutions.
(joint work with Andreas Brieden and Peter Gritzmann) |
| | |
19:00-19:30 | Ulrich Pferschy | ILP-Based Algorithms for a Nurse Scheduling Problem | We consider a complex nurse scheduling problem where a set of more than ten different and overlapping shifts are available, some of them with breaks. Their start and end times do not coincide with given periods of different demand. Beside the legal and contractual constraints on a feasible schedule the individual preferences of different nurses have a high priority. In particular, a block structure of working days and days off is highly desirable.
Two solution procedures are compared: The first one considers the days of the planning horizon iteratively and computes locally optimal daily schedules by solving assignment problems. The second approach models the block structure by a multi-commodity flow problem and solves a simplified model to optimality with CPLEX 11. Neglected constraints are fulfilled by postprocessing.
Tests on real-world instances show that the ILP based solutions are highly satisfactory and dominate the solutions generated by the assignment based algorithm. |
| | |
Aussois C.O.W. Web Pages
Books of the Aussois C.O.W.
AUSSOIS 2008 (published 2012) |
 |
Special Issue: Combinatorial Optimization and Integer Programming. Jünger, M.; Liebling, Th.M.; Naddef, D.; Pulleyblank, W.R.; Reinelt, G.; Rinaldi, G.; Wolsey, L.A. (Eds.) |
|
AUSSOIS 2008 (published 2010) |
 |
50 Years of Integer Programming 1958-2008. Jünger, M.; Liebling, Th.M.; Naddef, D.; Nemhauser, G.L.; Pulleyblank, W.R.; Reinelt, G.; Rinaldi, G.; Wolsey, L.A. (Eds.) |
|
AUSSOIS 2004 (published 2006) |
 |
Combinatorial Optimization: Theory and Computation The Aussois Workshop 2004. Liebling, Th.M.; Naddef, D.; Wolsey, L.A. (Eds.) |
|
AUSSOIS 2001 (published 2003) |
 |
Combinatorial Optimization -- Eureka, You Shrink!Jünger, M.; Reinelt, G.; Rinaldi, G. (Eds.) |
|
AUSSOIS 2000 (published 2003) |
 |
The Aussois 2000 workshop in combinatorial optimizationLiebling, Th.M.; Naddef, D.; Wolsey, L.A. (Eds.) |