PROGRAM
Monday 714:4515:30  William Cook  50+ Years of Combinatorial Integer Programming 
  
16:0016:45  Laurence Wolsey  Decomposition and Reformulation in Integer Programming 
  
Chair:  George Nemhauser and William Pulleyblank 
17:0019:45  The Pioneers  Panel: 50 Years of Integer Programming 
  
Tuesday 8Chair:  Giovanni Rinaldi 
08:3009:15  Ralph Gomory  40 Years of Corner Polyhedra 
  
09:1509: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 tradeoffs in working harder to generate them. 
  
09:4510:15  Adam Letchford  Separation Algorithms for the 01 Knapsack Polytope  It has been known for some time that valid inequalities for the 01 knapsack polytope can be used effectively as cutting planes for general 01 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 01 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:4511: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 singlecut and in the multicut (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:1511: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:4512:15  Mourad Baiou  On the Linear Relaxation of the pMedian Problem  We study a wellknown linear programming relaxation of the pmedian problem. We characterize all directed graphs for which this system of inequalities defines an integral polytope. This shows that for these graphs the pmedian problem is easy to solve. We also have a polynomial algorithm that recognizes this class of graphs. 
  
Chair:  Laurence Wolsey 
17:1518:00  JeanPhilippe 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:0018:30  Santanu Dey  Facets of HighDimensional Infinite Group Problem  One way to construct the Gomory Mixed Integer Cuts (GMIC) is the following: (a) Create a singlerow 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 tworow 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:3019:00  Kati Wolter  CMIR Approach for Flow Cover Cuts  Different classes of valid inequalities for the 01 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 (cMIR) inequalities for certain mixed knapsack relaxations of the 01 single node flow set are at least as strong as special cases of generalized flow cover inequalities.
The branchandcut framework SCIP incorporates a cutting plane separator which utilizes this approach. In this talk, we introduce our separation heuristic for the socalled cMIR 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 cMIR separator. 
  
19:0019: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:3009:15  Francois Margot  Symmetry in Integer Programming 
  
09:1509:45  Ugo Pietropaoli  A New Algorithm for the Stable Set Problem in Clawfree Graphs 
  
09:4510: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 clawfree.
(Joint work with A. Galluccio and P. Ventura) 
  
Chair:  Martin Grötschel 
10:4511: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 NPcomplete. But for a subclass that
arises from certain applications, the problem can be solved in linear time using logic decomposition techniques. 
  
11:1511: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:4512:15    
Chair:  Claude Lemaréchal 
17:1518:00  Franz Rendl  Semidefinite Relaxations for Integer Programming 
  
18:0018: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 NPhard 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:3019:00  Miguel Anjos  Solving Minimum kPartition Problems Using Semidefinite Programming  The minimum kpartition (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 branchandcut 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:0019:30  Ismael de Farias  BranchandCut 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 01 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 branchandcut and SOS2 branchandbound for finding an optimum of a separable PLF subject to linear constraints.
Joint work with Ming Zhao. 
  
Thursday 10Chair:  Uwe Zimmermann 
08:3009: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:1509:45  Monique Guignard  The Convex Hull Relaxation for Nonlinear Integer Programming Problems 
  
09:4510: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 mixedinteger 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
nonconvex optimization problems that are intractable, in general.
In this talk we show how to reduce the problem of computing the envelopes to lowerdimensional optimization problems when
the underlying function meets certain convexity properties. 
  
Chair:  Rainer Burkard 
10:4511: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:1511:45  Jon Lee  Nonlinear Matroid Optimization and Extensions  We give an efficient algorithmic framework for optimizing the sum of an binaryencoded "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 multidimensional 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:4512:15  Antoine Musitelli  Recognition of Binet Matrices  Binet matrices furnish a direct generalization of network matrices and arise from the nodeedge incidence matrices of bidirected graphs in the same way as network matrices do from directed graphs. We provide a polynomialtime algorithm for testing whether a given matrix is binet. 
  
Chair:  Bernhard Korte 
17:1518: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 rankordering 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:0018: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:3019: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 nonconvex objectives. 
  
19:0019:30  Gyula Pap  NodeCapacitated Packing of Apaths 
  
Chair:  Michel Balinski, Robert Bixby, Rolf Möhring, and George Nemhauser 
21:0023:00  Let's discuss the future of our scientific community! 
  
Friday 11Chair:  Rolf Möhring 
08:3009:15  Friedrich Eisenbrand  Integer Programming and Number Theory 
  
09:1509:45  Júlia Pap  Recognizing Conic TDI Systems is Hard 
  
09:4510: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:4511:15  Richard Karp  How Hard are the NPhard Problems? 
  
11:1511: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 Hamiltonpath problem. While the latter is NPhard 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:4512:15  Marco Di Summa  Network Formulations of MixedInteger Programs  We study the class of mixedinteger 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:1518:00  Andrea Lodi  Computation in Integer Programming 
  
18:0018:30  Tom McCormick  Strongly Polynomial Algorithms for BiSubmodular 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
PushRelabel. 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:3019:00  Michael Ritter  Optimal Flight Scheduling at Airports  For each major airport, a new longterm 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 BranchandBound 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:0019:30  Ulrich Pferschy  ILPBased 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 multicommodity flow problem and solves a simplified model to optimality with CPLEX 11. Neglected constraints are fulfilled by postprocessing.
Tests on realworld 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 19582008. 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 optimization Liebling, Th.M.; Naddef, D.; Wolsey, L.A. (Eds.) 