PROGRAM
Monday 7Chair:  Michael Jünger 
08:1508:30    
08:3009:00  Christoph Buchheim  An Exact Algorithm for Quadratic Integer Minimization using Ellipsoidal Relaxations  We propose a branchandbound algorithm for minimizing a not necessarily convex quadratic function over integer variables. The algorithm is based on lower bounds computed as continuous minima of the objective function over appropriate ellipsoids. In the nonconvex case, we use ellipsoids enclosing the feasible region of the problem. In spite of the nonconvexity, these minima can be computed quickly; the corresponding optimization problems are equivalent to trustregion subproblems. We present several ideas that allow to accelerate the solution of the continuous relaxation within a branchandbound scheme and examine the performance of the overall algorithm by computational experiments. 
  
09:0009:30  Emiliano Traversi  Separable nonconvex underestimators for binary quadratic programming  We present a new approach to constrained quadratic binary programming. Dual bounds are computed by choosing appropriate global underestimators of the objective function that are separable but not necessarily convex. Using the binary constraint on the variables, the minimization of this separable underestimator can be reduced to a linear minimization problem over the same set of feasible vectors. For most combinatorial optimization problems, the linear version is considerably easier than the quadratic version. We explain how to embed this approach into a branchandbound algorithm and present experimental results. 
  
09:3010:00  Alberto del Pia  Integer quadratic programming in the plane  The integer quadratic programming problem is formulated as follows.
Let $n$ and $m$ be positive integers, $A$ an $m \times n$matrix with integral coefficients, $b \in \Z^m$, and $f \st \R^n \to \R$ a quadratic polynomial with integral coefficients.
The question is to find a vector $\bar x \in \Z^n$ satisfying the system of $m$ inequalities $Ax \le b$ that minimizes the function $f$.
It is shown that the integer quadratic programming problem with $n=2$ is polynomially solvable. 
  
Chair:  Gerhard Reinelt 
10:3011:00  Samuel Fiorini  Approximation Limits of Linear Programs (Beyond Hierarchies)  We develop a framework for proving approximation limits of polynomialsize linear programs from lower bounds on the nonnegative ranks of suitably de?ned matrices. This framework yields unconditional impossibility results that are applicable to any linear program as opposed to only programs generated by hierarchies. Using our framework, we prove that O(n^{1/2eps} )approximations for CLIQUE require linear programs of size 2^{n^{\Omega(eps)}}. (This lower bound applies to linear programs using a certain encoding of CLIQUE as a linear optimization problem.) Moreover, we establish a similar result for approximations of semide?nite programs by linear programs. Our main technical ingredient is a quantitative improvement of Razborov’s rectangle corruption lemma (1992) for the high error regime, which gives strong lower bounds on the nonnegative rank of certain perturbations of the unique disjointness matrix.
Joint work with Gábor Braun, Sebastian Pokutta and David Steurer. 
  
11:0011:30  Fernando Oliveira  Packings of bodies in Euclidean space  Given a finite list of convex bodies in Euclidean space, a packing is a union of nonoverlapping congruent copies of the bodies given. A natural question concerning packings is how dense they can be made, that is, what is the maximum fraction of space that can be covered by a packing of some given bodies?
I wil show how harmonic analysis and semidefinite programming can be used to give upper bounds for the maximum density of a packing of bodies. In particular I will discuss the case of binary sphere packings, when one considers packings of spheres of two different sizes, and show how the computer can be used to find upper bounds for the densities of such packings.
This is joint work with David de Laat and Frank Vallentin. Paper on arXiv:1206.2608. 
  
11:3012:00  Angelika Wiegele  A new strengthening of semidefinite maxcut relaxations  Semidefinite relaxations proved to be very successful for maxcut. Tightening the basic relaxation for maxcut, underlying the GoemansWilliamson hyperplane
rounding procedure, can be done very efficient by adding the socalled triangleinequalities.
Based on this tightened relaxation we present a further strengthening: We identify submatrices of the optimal matrix $X$ and require thesemsubmatrices to be in the corresponding cut polytope $CUT(K_r)$. The dimension $r$ of the submatrices is chosen small enough (say $r=5$ or $r=6$), so that the resulting
SDP is still fast to compute.
First computational results demonstrate that the bound improves significantly after a few rounds of adding such submatrix constraints, while keeping computation times reasonable. 
  
Chair:  Giovanni Rinaldi 
17:3018:00  Ulrich Pferschy  Knapsack Problems with Conflict and Forcing Constraints on Special Graph Classes  We consider the classical 01 knapsack problem and add binary constraints for pairs of items. These can be either conflict constraints stating that certain pairs of items cannot be simultaneously contained in a feasible solution, or forcing constraints requiring that at least one of the two items of each given pair must be included in the knapsack.
These constraints can be represented by a conflict (or forcing) graph where each item corresponds to a vertex and an edge in the graph corresponds to a conflicting (enforced) pair of items. Note that this problem can also be seen as a weighted independent set problem with an additional budget constraint.
In this talk we will concentrate on the identification of special graph classes as conflict graphs which permit (Fully) Polynomial Approximations Schemes ((F)PTASs). After showing briefly that chordal graphs and graphs of bounded treewidth allow an FPTAS, we present a PTAS for planar conflict graphs based on the method by Baker. In contrast to this positive approximability result, the knapsack problem with a planar forcing graph is inapproximable.
Finally, we also consider clique and modular decompositions of the conflict graph. For a number of graph classes defined by the exclusion of certain induced subgraphs we can show structural results that allow the construction of dynamic programming schemes leading to FPTASs.
joint work with Joachim Schauer 
  
18:0018:30  Andreas Feldmann  Balanced Partitions of Trees and Applications  We study the problem of finding the minimum number of edges that, when cut, form a partition of the vertices into k sets of equal size. This is called the kBALANCED PARTITIONING problem. The problem
is known to be inapproximable within any finite factor on general graphs, while little is known about restricted graph classes.
We show that the kBALANCED PARTITIONING problem remains APXhard even when restricted to unweighted tree instances with constant maximum degree. If instead the diameter of the tree is constant
we prove that the problem is NPhard to approximate within n^c, for any constant c < 1.
If vertex sets are allowed to deviate from being equalsized by a factor of at most 1 + ?, we show that solutions can be computed on weighted trees with cut cost no worse than the minimum attainable when requiring equalsized sets. This result is then extended to general graphs via decompositions into trees and improves the previously best approximation ratio from O(log^{1.5}(n)/?^2) [Andreev and Racke TCS
2006] to O(log n). This also settles the open problem of whether an algorithm exists for which the number of edges cut is independent of ?. 
  
18:3019:00  David Adjiashvili  Timetable Combinatorial Optimization  The timetable variant of a combinatorial optimization (CO) problem is defined as follows. The input specifies an instance of the CO problem comprising a set system (A,F) with ground set A and a collection F of feasible sets, a linear cost function w, a positive integer T and positive integers t_a <= T for every ground set element a. The goal is to find T feasible sets X_1,...,X_T of maximal total cost that satisfy the following duration property. For every ground set element a, the set L_a subset {1,...,T} of indices j such that a is in X_j is a disjoint union of intervals of length t_a.
The class of timetable variant of CO problems corresponding to independence systems is a rich class of problems containing many Knapsack, scheduling and packing problems. For p ~= 1.691 we present a polynomial pqapproximation algorithm for this class of problems whenever the static maximization problem admits a polynomial qapproximation algorithm. For the more general timetable counterpart that also provides upper bounds on the cardinality of L_a for every ground set element a, we show polynomial constant factor approximation algorithms for the case that underlying set system is a Matroid. A combination of combinatorial and LPbased techniques is employed both in the algorithms and in their analysis. 
  
19:0019:30  Maxim Sviridenko  New and Improved Bounds for the Minimum Set Cover Problem  We study the relationship between the approximation factor for the SetCover problem and the parameters $\Delta$ : the maximum cardinality of any subset, and $k$ : the maximum number of subsets containing any
element of the ground set. We show an LP rounding based approximation of $(k1)(1e^{\frac{\ln \Delta}{k1}}) +1$, which is substantially
better than the
classical algorithms in the range $k \approx \ln \Delta$, and also
improves on related
previous works [Krivelevich, Okun]. For the
interesting case when $k = \theta(\log \Delta)$ we also exhibit an integrality
gap which essentially matches our approximation algorithm.
We also prove a hardness of approximation factor of $\Omega\left(\frac{\log
\Delta}{(\log\log \Delta)^2}\right)$ when $k = \theta(\log \Delta)$.
This is the first study of the hardness factor specifically for this range
of $k$ and $\Delta$, and improves on the only other
such result implicitly proved in [Khot, Saket]. 
  
Tuesday 8Chair:  Andrea Lodi 
08:3009:00  Andrea Lodi and Paolo Toth  Remembering Alberto 
  
09:0009:30  Michele Monaci  Optimalitybased Domain Reduction Strategies for Global Optimization  We discuss optimalitybased domain reductions for Global Optimization problems both from the theoretical and from the computational point of view.
When applying an optimalitybased domain reduction we can easily define a lower limit for the reduction which can be attained, but we can hardly guarantee that such limit is reached.
Here, we theoretically prove that, for a nontrivial class of problems, appropriate strategies exist that are always able to reach this lower limit.
On the other hand, we will also show that the same strategies lose this property as soon as we slightly enlarge the class of problems.
Finally, we present some computational experiments with a standard branchandbound approach applied to Linear Multiplicative Programming problems, to establish a good trade off between the quality of the domain reduction (the higher the quality, the lower the number of nodes in the tree), and the computational cost of the domain reduction (thus, the effort per node).
(joint work with Alberto Caprara and Marco Locatelli) 
  
09:3010:00  Valentina Cacchiani  A New Lower Bound for Curriculumbased Course Timetabling  In this paper, we propose a new method to compute lower bounds for Curriculumbased Course Timetabling (CTT), which calls for the best weekly assignment of university course lectures to rooms and time slots. The lower bound is obtained by splitting the objective function into two parts, considering one separate problem for each part of the objective function, and summing up the corresponding optimal values (or, in some cases, lower bounds on these values), found by formulating the two parts as Integer Linear Programs (ILPs). The solution of one ILP is obtained by using a column generation procedure. Experimental results show that the proposed lower bound is often better than the ones found by the previous methods in the literature, and also much better than those found by other new ILP formulations illustrated in this paper. The proposed approach is able to obtain improved lower bounds on realworld benchmark instances from the literature, used in the international timetabling competitions ITC2002 and ITC2007, proving for the first time that some of the bestknown heuristic solutions are indeed optimal (or close to the optimal ones). 
  
Chair:  Paolo Toth 
10:3011:00  Margarida Carvalho  Bilevel Knapsack with interdiction constraints  Bilevel programming research is motivated by the possibility of modelling a wide range of real world problems with an hierarchical structure.
In this presentation and using Alberto Caprara's words, a natural, clean and mathematical challenging bilevel knapsack model is considered.
The model describes an interdiction situation where two decision makers, called leader and follower, have a knapsack of their own; the follower can only choose from those items not packed by the leader; the leader aim is to minimize the maximum profit of the follower. Along with other bilevel knapsack variants, our complexity results will be stated indicating its computational difficulty.
The main focus of the presentation will be in the algorithmic approach developed which is a novel viable way to solve it. Computational results will be presented supporting its efficiency in the instances treated in the literature and rising benchmarks.
Comments about generalizing our method to interdiction problems will be provided. 
  
11:0011:30  Tiziano Parriani  An Analysis of Natural Approaches for Solving MultycommodityFlow Problems  We study the relative performances of three existing approaches to solve the minimumcost linear MultiCommodity Flow Problem (MCFP). The first approach is solving the LP corresponding to the natural nodearc formulation with stateoftheart, generalpurpose commercial software. The second is to take advantage of the blockdiagonal structure with complicating constraints of the LP to develop DantzigWolfe decomposition/column generation approaches. The third is a decompositionbased pricing procedure, proposed by Mamer and McBride, in which the same subproblems of the DW decomposition are used to identify new columns in a reduced master problem that has the same structure of the nodearc formulation. With a particular focus on degeneracy and instability issues of the column generation, different classes of MCFP instances are solved in order to study the connections between the structure of a specific instance and the performances of the most common solving approaches for this class of problems. This may be useful in choosing the correct approach when a particular MCFP shall be solved, as well as improving the effectiveness of the approaches themselves. 
  
11:3012:00  Laura Galli  DelayRobust Event Scheduling  Robust optimisation is a well established concept to deal with uncertainty.
In particular, recoveryrobust models are suitable for realworld contexts, where a certain amount
of recovery – although limited – is often available. In this paper we describe a general
framework to optimise eventbased problems against delay propagation. We also present
a realworld application to train platforming in the Italian railways, in order to show the
practical effectiveness of our framework. 
  
Chair:  Laurence Wolsey 
17:3018:00  Friedrich Eisenbrand  Minimizing the number of lattice points in a translated polygon 
  
18:0018:30  Frederik von Heymann  On the Structure of Reduced Kernel Lattice Bases  In the socalled lattice reformulation of an IP, the variable vector is written as an integer linear combination of kernel lattice basis vectors. This reformulation has been proven useful in several small but very hard instances. We investigate this technique for larger instances with no particular structure and observe that the lattice bases contain an identity matrix as a submatrix. Hence, some of the variables will have a "rich" translation in terms of the lattice basis vectors, and others represent a variable substitution. We present a theoretical analysis of this phenomenon, using probabilistic methods to capture the behavior of randomly generated input. 
  
18:3019:00  András Sebö  Eight Fifth approximation for the path TSP.  A salesman has to visit a list of cities starting in his homecity s and
arriving at his weekend residence t . The place of the new 8/5 ratio
among its predecessors can be explained in terms of the starting
Fibonacci sequence 1, 1, 2, 3, 5, 8, 13 :
Recall that the ratios a_{i+1} / a_i are alternatively below or above the
golden ratio and converge to it.
1 /1 : a ratio that can never be reached.
2/1 : a ratio that can immediatly be reached.
3/2 : conjectured best approximation guarantee. Corresponds to 4/3 for s=t.
For Graph Metrics 3/2 is proved and improved to 7/5 if s=t : Sebo, Vygen
5/3 : the garantee of the adapted Christofides algorithm (Hoogeveen).
8/5 : the new approximation garantee for the most general problem.
The golden ratio (sqrt(5)+1)/2 proved by An, Kleinberg and Shmoys'.
13/8 : weaker ratio for a generalization (to Tjoins) by Cheriyan, Friggstad et Gao.
While the ratio 3/2 for the case s=t has not moved for general metrics in the last nearly
forty years, the corresponding ratio moves down more easily for the path TSP, and
brings in new algorithms and methods of analysis. After a survey of the main ideas for
various versions I sketch the proof of the improved approximation ratio 8/5 for the path
TSP problem with general metrics (and in fact for connected Tjoins).

  
19:0019:30  Giacomo Nannicini  A practical FPTAS for convex stochastic dynamic programs  We propose an efficient Fully PolynomialTime Approximation Scheme (FPTAS) for stochastic convex dynamic programs using the technique of $K$approximation sets and functions introduced by Halman et al. This paper deals with the convex case only, and it has the following contributions: First, we improve on the worstcase running time given by Halman et al. Second, we design an FPTAS with excellent practical performance, and show that it is faster than an exact algorithm even for small problems instances and small approximation factors, becoming orders of magnitude faster as the problem size increases. Third, we show that with careful algorithm design, the errors introduced by floating point computations can be bounded, so that we can provide a guarantee on the approximation factor over an exact infiniteprecision solution. Our computational evaluation is based on randomly generated problem instances coming from applications in supply chain management and finance. 
  
Wednesday 9Chair:  Michele Conforti 
08:3009:00  Zoltán Szigeti  Packing of arborescences with matroid constraints  We provide the directed counterpart of a slight extension of Katoh and Tanigawa's result on rootedtree decompositions with matroid constraints. Our result characterizes digraphs having a packing of arborescences with matroid constraints. It is a proper extension of Edmonds' result on packing of spanning arborescences and implies  using a general orientation result of Frank  the above result of Katoh and Tanigawa. 
  
09:0009:30  Olga Heismann  The Hypergraph Assignment Problem  The hypergraph assignment problem (HAP) is the generalization of the assignment problem on bipartite graphs to bipartite hypergraphs. It serves, in particular, as a universal tool to model several train composition rules in vehicle rotation planning for long distance passenger railways. Even for problems with a small hyperedge size and hypergraphs with a special partitioned structure the HAP is NPhard. We use an integer programming approach and investigate the resulting polyhedron of feasible solutions. Further, we develop combinatorial procedures for heuristic approximation results.

  
09:3010:00  Jannik Matuschke  Degreeconstrained orientations of embedded graphs  We investigate the problem of orienting the edges of an embedded graph
in such a way that the indegrees of both the nodes and faces meet
given values. We show that the number of feasible solutions is bounded by
4^g, where g is the genus of the embedding, and all solutions
can be determined within time O(4^gE^2 + E^3). In particular, for planar graphs the solution is unique if it exists, and in general the problem of finding a feasible orientation is fixedparameter tractable in g. In sharp contrast to these results, we show that the problem becomes NPcomplete even for a fixed genus if only upper and lower bounds on the indegrees are specified instead of exact values. 
  
Chair:  Sebastian Sager 
10:3011:00  Christian Kirches  Perspective Functions, Vanishing Constraints, and Sequential Complementarity Programming for Fast MixedInteger Nonlinear Optimal Control  Logical implications appear in a number of important mixedinteger nonlinear optimal control problems (MIOCPs). Mathematical optimization offers a variety of different formulations that are equivalent for boolean variables, but result in different relaxations. In this article we give an overview over a variety of different modeling approaches, including outer versus inner convexification, generalized disjunctive programming, and vanishing constraints. In addition to the tightness of the respective relaxations, we also address the issue of constraint qualification and the behavior of computational methods for some formulations. As a benchmark, we formulate a truck cruise control problem with logical implications resulting from gearchoice specific constraints. Computational results for this benchmark are used to investigate feasibility gaps, integer feasibility gaps, quality of local solutions, and wellbehavedness of numerical methods for the presented reformulations of the benchmark problem. Vanishing constraints give the most satisfactory results, and we are hence interested in efficient sequential solvers for nonlinear complementarity problems. 
  
11:0011:30  Marcia Fampa  Solution approaches for a nonlinear clustering problem  We discuss different modeling techniques and solution approaches for an application of a nonconvex MINLP clustering problem in Software Engineering.
Numerical results for benchmark instances compare the distinct approaches which include linearization techniques, column generation and global optimization.

  
11:3012:00  Antonio Frangioni  ProjectandLift for the Perspective Reformulation: How Serendipity Brought Us to a Free Lunch  We report on some recent developments in our research about the Perpective Reformulation of certain MixedInteger NonLinear Programs. We start with a brief recall of previous results in the area, pointing out how the whole research line started with a 100% serendipity moment, motivated by trying to prove wrong a referee who was in fact right but for the wrong reasons, and was brought forward in part by a series of other developments motivated by factors such as the need to finding another application to publish the first paper, the need of fending off competing research teams, and finding a good idea as a byproduct of an original one that would never work. All this brought us to a ProjectandLift approach to certain projected reformulations of the Perspective Reformulation which seems to be one of the few authentic violations of the "no free lunch principle": an easy reformulation of a MIQP with the very same size and structure as the original one but with a substantially stronger bound. Apart from providing an overview on a recent and potentially interesting research field in MINLP, we hope that this talk can motivate the audience to making more errors and looking at them with more interest. 
  
Chair:  Uwe Zimmermann 
17:3018:00  Pieter van den Berg  An ambulance location model with stochastic travel times  We describe an ambulance location optimization model that maximizes the expected coverage provided by ambulance vehicles. The service level is measured by the fraction of calls reached within a given time threshold. The response time to a call consists of a random pretrip delay plus a normally distributed travel time. Furthermore, we incorporate the fraction of time that an ambulance is unavailable. The problem is modelled as an integer linear programming problem and is applied on the region of Amsterdam, the Netherlands. Data of the ambulance service in 2010 is used to estimate the parameters of the model. The outcome of the model is an optimal set of locations for the ambulances in order to provide adequate coverage. 
  
18:0018:30  Max Klimm  Competition for resources: The equilibrium existence problem for weighted congestion games  Weighted congestion games are an important class of noncooperative games that constitute an elegant model for the resource usage by selfish users. Unfortunately, they need not possess a pure Nash equilibrium, in general. We give a complete characterization of the maximal set of cost functions that one allow on the resources in order to guarantee the existence of a pure Nash equilibrium. 
  
Chair:  Giovanni Rinaldi 
17:3018:00  Klaus Truemper  Mathematics: Discovered or Constructed?  For more than 2500 years, philosophers have debated whether mathematical results are discovered or constructed. The talks summarizes the wildly differing thoughts, arguments, and conclusions. It also covers explanations how such variety of human thought is possible. 
  
Thursday 10Chair:  François Margot 
08:3009:00  Timm Oertel  Cutting plane methods in integer convex minimization  Minimizing a convex function over the integer points of a bounded convex set is polynomial in fixed dimension. We provide an alternative, short, and geometrically motivated proof of this result. Further, we present an oraclepolynomial algorithm based on a mixed integer linear optimization oracle. 
  
09:0009:30  Michael Poss  Robust combinatorial optimization with variable uncertainty  The budgeted uncertainty polytope suffers from an important drawback: it is overly conservative for vectors with small cardinality. In particular, its probabilistic interpretation is meaningless for combinatorial problems whose solution has a small cardinality compared to the total number of variables.
We introduce in this talk a new model for robust combinatorial optimization where the uncertain parameters belong to the image of multifunctions of the problem variables. Our model overcomes the problem of budgeted uncertainty by providing a probabilistic guarantee independent of the cardinality. Experiments carried out on the knapsack problem show a reduction of the price of robustness by an average factor of 18%, for a little increase in computational time.
We study then the case where only the cost are uncertain and investigate the computational complexity. We show that in many cases, the resulting optimization problems belong to the same complexity class as the original optimization problem, generalizing the result proven by Bertsimas and Sim. 
  
09:3010:00  Sara Mattia  Robust Optimization with Multiple Intervals  Traditionally, when an optimization problem is solved, the parameters of the problem (the constraint coefficients, the right hand sides and the objective coefficients) are supposed to be constant and
fully known. Unfortunately, this is not always the case, as the parameters may be affected by measurement, implementation or estimation
errors and/or they may be subject to change over time. Robust optimization provides a way to take the data uncertainty into account in order to produce robust solutions, i.e. solutions that are resilient to
the variation of the input data. In this talk a generalization of the robust optimization framework proposed by Bertsimas and Sim is presented. The proposed model is based on the reasonable assumption that not all the data realizations occur with the same probability, but some of them are more likely to occur than others. The probabilistic and complexity properties of the original framework are generalized to the new model. 
  
Chair:  Rolf Möhring 
10:3011:00  Lars Schewe  Finding Steiner trees subject to mechanical constraints  or: Routing steam pipes in power plants  Coauthors: Sonja Mars, Jakob Schelbert
We consider finding a Steiner tree subject to mechanical
constraints. The mechanics of the problem are modeled by treating the
edges of the Steiner tree as so called Timoshenko beams. The objective
is to minimize a global measure for the stresses acting on the
structure, the so called compliance. This problem can be reformulated
using known techniques to a mixedinteger secondordercone
program. From the point of view of the application it is, however, of
more interest to consider the case where the stresses need also to be
bounded locally. We will sketch approaches to this variant of the
problem.
The motivation for studying this problem is a realworld problem: Find
the optimal routing of steam pipes in a power plant. These pipes
transport the hot steam from the main boiler to the steam
turbines. They are the part of the plant that is worn down quickest in
the station. Therefore, finding a routing the minimizes the mechanical
stresses that act on these during the lifetime of the plant is
important to increase the lifetime of the plant.
The main focus of this talk will be the modeling and preliminary
results.
Supported by BMBF and Bilfinger.

  
11:0011:30  Markus Leitner  The TwoLevel Diameter Constrained Spanning Tree Problem  In this work, we introduce the TwoLevel Diameter Constrained Spanning Tree Problem (2DMSTP) which generalizes the classical DMSTP by considering two sets of nodes with different latency requirements.
We first observe that any feasible solution to the 2DMSTP can be viewed as a DMST that contains a diameter constrained Steiner tree.
This observation allows us to prove graph theoretical properties related to the centers of each tree which are then exploited to develop mixed integer programming formulations, strengthening valid inequalities, and symmetry breaking constraints.
In particular, we propose a novel modeling approach based on a threedimensional layered graph.
In an extensive computational study we show that a branchandcut based on the latter model is highly effective in practice.

  
11:3012:00    
Chair:  Robert Weismantel 
17:3018:00  Volker Kaibel  Forbidden Vertices  Suppose P is polytope for which one has at hands a complete description either in the original space or by means of an extended formulation and F is a subset of the vertex set X of P. We discuss, when it is possible to derive from the description of P a description of conv(X\F). One of our results is that in case of 0/1polytopes P the extension complexity of conv(X\F) is bounded polynomially in the extension complexity of P and the cardinality of F.
The talk is based on joint work with Shabbir Ahmed, Gustavo Angulo, and Santanu Dey.
(I'd be happy to talk on Monday.) 
  
18:0018:30  Kanstantsin Pashkovich  Extended formulations for stable set polytopes via decomposition  In this talk we present techniques to construct extended formulations for stable set polytopes based on different decomposition rules: cutset decomposition, amalgam decomposition, template decomposition. These techniques lead to compact extended formulations for stable set polytopes of oddsignable capfree graphs. 
  
18:3019:00  Yuri Faenza  Reverse ChvátalGomory rank  We introduce the reverse ChvatalGomory rank r*(P) of an integral polyhedron P, defined as the supremum of the ChvatalGomory ranks of all rational polyhedra whose integer hull is P. A wellknown example in dimension two shows that there exist integral polytopes P with r*(P) equal to infinity. In this talk, we provide a geometric characterization of polyhedra with this property in general dimension, and investigate upper bounds on r*(P) when this value is finite. We also sketch possible extensions, in particular to the reverse split rank.
Joint work with M. Conforti, A. Del Pia, M. Di Summa, and R. Grappe 
  
19:0019:30  Laura Sanità  0/1 polytopes with quadratic Chvátal rank 
  
Friday 11Chair:  Martine Labbé 
08:3009:00  Martin Skutella  Graph Orientation and Network Flows Over Time  NashWilliams' famous orientation theorem states that each undirected graph has an orientation that keeps at least half of the connectivity (rounded down) between any two vertices. We study the related problem of orienting an undirected capacitated graph with given demands and supplies at the nodes so as to maintain a network flow satisfying the demands and supplies. While this task is trivial for classical (static) network flows, it leads to fascinating results when studied in the more general context of network flows over time. In general, an optimal transshipment over time in an undirected graph might have to use an edge in opposite directions at different points in time. Moreover, it is NPcomplete to decide whether there is a feasible transshipment over time that uses each edge in one direction only. Our main result is that there always exists an orientation that allows to satisfy 1/3 of the total supplies and demands and this bound is tight. 
  
09:0009:30  Frank Fischer  Dynamic Graph Generation for Shortest Path Problems in Time Expanded Networks  In discrete optimisation problems the progress of objects over time is frequently modelled by shortest path problems in time expanded networks, but longer time spans or finer time discretisations quickly lead to model sizes that are intractable in practice. With typical objective functions, e.g. early completion time, the arising shortest paths in convex relaxations often lie in a narrow corridor inside these networks. Motivated by this observation, we develop a general dynamic graph generation framework in order to control the networks’ sizes even for infinite time horizons. It can be applied whenever objects need to be routed through a traffic or production network with coupling capacity constraints and with a preference for early paths. Without sacrificing any information compared to the full model, it includes a few additional time steps on top of arcs being used so far. This "frontier" of the graphs can be extended automatically as required by solution processes such as column generation or Lagrangian relaxation. The corresponding algorithm is efficiently implementable and linear in the arcs of the nontimeexpanded network with a factor depending on the basic time offsets of these arcs. We illustrate the benefits of this technique on real world instances of a large scale train timetabling problem.
Joint work with Christoph Helmberg 
  
09:3010:00  Frank Vallentin  Spectral bounds for the chromatic number of an operator 
  
Chair:  Denis Naddef 
10:3011:00  Tom McCormick  Discrete Convexity in Supply Chain Models  Discrete convexity has found application in several supply chain models. We survey some of these models, with a view towards making the supply chain context clear to nonspecialists. In particular, we look at various attempts to model inventory problems in supply chains using discrete convexity. We focus in particular on the paper "OrderBased Cost Optimization in AssembletoOrder Systems" by Lu and Song (OR 2005). A main result in that paper claims that the expected cost of an assemble to order inventory system is Lnatural convex in the base stock levels of each item. We develop a simple example showing that this result is wrong. 
  
11:0011:30  Andrea Cassioli  On Some Recent Advances on the Discrete Molecular Distance Geometry Problem.  The Molecular Distance Geometry Problem (MDGP) is to determine the
embedding in K dimensions of a set of points molecule from some given
information. An MDGP instance can be represented by a weighted,
undirected simple graph G = (V, E). Under certain conditions, the
MDGP can be solved searching a discrete set of points. These
conditions involve the existence of suitable total orderings on V that
guarantee that a minimum number of pairwise distances are known.The
first aim of this talk is to discuss the complexity of the problem of
finding such total order. To tackle reallife instance we must
consider that for same distances only an interval is known. We address
this problem discretizing these inteval distanecs. We propose the use of
techniques from the Clifford algebra to improve the discretization and
the pruning steps. 
  
11:3012:00  Leo Liberti  On Feasibility Based Bounds Tigthening  Mathematical programming problems involving nonconvexities are usually solved to optimality using a spatial BranchandBound (sBB) algorithm. Algorithmic efficiency depends on many factors, among which the widths of the bounding box for the problem variables at each BranchandBound node naturally plays a critical role. The practically fastest boxtightening algorithm is known as FBBT (FeasibilityBased Bounds Tightening): an iterative procedure to tighten the variable ranges. Depending on the instance, FBBT may not converge finitely to its limit ranges, even in the case of linear constraints. Tolerancebased termination criteria yield finite termination, but not in worstcase polynomial time. We model FBBT by using fixedpoint equations in terms of the variable bounding box, and we treat these equations as constraints of an auxiliary mathematical program. We demonstrate that the auxiliary mathematical problem is a linear program, which can of course be solved in polynomial time. We demonstrate the usefulness of our approach by improving the opensource sBB solver Couenne. 
  
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.) 