PROGRAM
Monday 9Chair:  Michael Jünger 
08:3009:00  Oktay Günlük  Lattice Closures of Polyhedra  Abstract: We define the kdimensional lattice closure of a polyhedral mixedinteger set to be the intersection of the convex hulls of all possible relaxations of the set obtained by choosing up to k integer vectors \pi_1,...,\pi_k and requiring <\pi_1,x>,...,<\pi_k,x> to be integral. The kdimensional lattice closure of a rational polyhedral mixedinteger set is known to be polyhedral when k=1, and we extend this result to all k>1. We also construct a set with n>k integer variables such that finitely many iterations of the kdimensional lattice closure does not give the integer hull. We show that valid inequalities from unbounded, fulldimensional, convex latticefree sets cannot give the integer hull either. 
  
09:0009:30  Dabeen Lee  On the Rational Polytopes with Chvatal Rank 1  In this paper, we study the following problem: given a polytope P with Chvatal rank 1, does P contain an integer point? Boyd and Pulleyblank observed that this problem is in the complexity class NP intersect coNP, an indication that it is probably not NPcomplete.
We solve this problem in polynomial time for polytopes arising from the satisfiability problem of a given formula with at least three literals per clause, for simplices whose integer hull can be obtained by adding at most a constant number of Chvatal inequalities, and for rounded polytopes. We prove that any closed convex set whose Chvatal closure is empty has an integer width of at most n, and we give an example showing that this bound is tight within an additive constant of 1.
The promise that a polytope has Chvatal rank 1 seems hard to verify though. We prove that deciding emptiness of the Chvatal closure of a given rational polytope P is NPcomplete, even when P is contained in the unit hypercube or is a rational simplex, and even when P does not contain any integer point. This has two implications: (i) It is NPhard to decide whether a given rational polytope P has Chvatal rank 1, even when P is contained in the unit cube or is a rational simplex; (ii) The optimization and separation problems over the Chvatal closure of a given rational polytope contained in the unit hypercube or of a given rational simplex are NPhard. These results improve earlier complexity results of Cornuejols and Li and Eisenbrand. Finally, we prove that, for any positive integer k, it is NPhard to decide whether adding at most k Chvatal inequalities is su?cient to describe the integer hull of a given rational polytope.
This is joint work with Gerard Cornuejols and Yanjun Li. 
  
09:3010:00  Stefan Weltge  Polytopes in the 0/1Cube with Bounded ChvátalGomory Rank  Let S \subseteq \{0,1\}^n and R be any polytope contained in [0,1]^n with R \cap \{0,1\}^n = S. We prove that R has bounded ChvátalGomory rank (CGrank) provided that S has bounded pitch and bounded gap, where the pitch is the minimum integer p such that all pdimensional faces of the 0/1cube have a nonempty intersection with S, and the gap is a measure of the size of the facet coefficients of conv(S). Let H[S] denote the subgraph of the ncube induced by the vertices not in S. We prove that if H[S] does not contain a subdivision of a large complete graph, then both the pitch and the gap are bounded. By our main result, this implies that the CGrank of R is bounded as a function of the treewidth of H[S]. We also prove that if S has pitch 3, then the CGrank of R is always bounded. Both results generalize a recent theorem of Cornuéjols and Lee (2016), who proved that the CGrank is always bounded if the treewidth of H[S] is at most 2.
This is joint work with Yohann Benchetrit, Samuel Fiorini and Tony Huynh. 
  
Chair:  Gerhard Reinelt 
10:3011:30  Rolf Möhring  Integrating Scheduling and Routing in Logistics  A Real World Project  We introduce, discuss, and solve a hard practical optimization problem that deals with routing bidirectional traffic on the Kiel Canal, which is the world’s busiest artificial waterway with more passages than the Panama and Suez Canal together. The problem arises from scarce resources (sidings) that are the only locations where large ships can pass each other in opposing directions. This requires decisions on who should wait for whom (scheduling), in which siding to wait (packing) and when and how far to steer a ship between sidings (routing), and all this for online arriving ships at both sides of the canal. We have developed a combinatorial algorithm that provides a unified view of routing and scheduling that combines simultaneous (global) and sequential (local) solution approaches to allocate scarce network resources to a stream of online arriving vehicles in a collisionfree manner. Computational experiments on real traffic data with results obtained by human expert planners show that our combinatorial algorithm improves upon manual planning by 25%. It was subsequently used to identify bottlenecks in the canal and to make suggestions for enlarging the capacity of critical sections of the canal to make it suitable for future traffic demands. The combination of routing and scheduling (without the packing) leads to a new class of scheduling problems dealing with scheduling bidirected traffic on a path, and we will also address recent complexity and approximation results for this class. The lecture is based on joint work with Elisabeth Lübbecke and Marco Lübbecke. 
  
11:3012:00  Martin Schmidt  Optimal Price Zones of Electricity Markets: A MixedInteger Multilevel Model and Global Solution Approaches  Mathematical modeling of economic market design often leads to mixedinteger nonlinear multilevel optimization problems for which no generalpurpose solvers exist and which are intractable in general. In this work, we consider the splitting of a market area in different zones such that the resulting market design yields welfareoptimal outcomes. This modeling leads to a challenging multilevel problem that contains a graph partitioning problem with multicommodity flow connectivity constraints and nonlinearities due to proper economic modeling. Furthermore, it has highly symmetric solutions. We develop different problemtailored solution approaches. In particular, we present an extended KKT transformation approach as well as a generalized Benders approach that both yield globally optimal solutions. Both methods, enhanced with techniques such as symmetry breaking and primal heuristics, are evaluated in detail on academic as well as realistic instances. It turns out that our approaches lead to effective solution methods for the difficult optimization tasks presented here, where the problemspecific generalized Benders approach performs considerably better than the methods based on KKT transformation. 
  
Chair:  Giovanni Rinaldi 
17:3018:00  Lars Schewe  Penalty Alternating Direction Methods for MixedInteger Optimization: A New View on Feasibility Pumps  Feasibility pumps are highly effective primal heuristics for
mixedinteger linear and nonlinear optimization.
However, despite their success in practice there are only few works
considering their theoretical properties.
We show that feasibility pumps can be seen as alternating
direction methods applied to special reformulations of the original
problem, inheriting the convergence theory of these methods.
Moreover, we propose a novel penalty framework that encompasses
this alternating direction method, which allows us to refrain from random
perturbations that are applied in standard versions of feasibility
pumps in case of failure.
We present a convergence theory for the new penalty based alternating
direction method and compare the new variant of the feasibility
pump with existing versions in an extensive numerical study for
mixedinteger linear and nonlinear problems.

  
18:0018:30  Ambros Gleixner  Verifying Integer Programming Results  Software for mixedinteger linear programming can return incorrect results for a number of reasons, one being the use of inexact floatingpoint arithmetic. Even solvers that employ exact arithmetic may suffer from programming or algorithmic errors, motivating the desire for a way to produce independently verifiable certificates of claimed results. Due to the complex nature of stateoftheart MILP solution algorithms, the ideal form of such a certificate is not entirely clear. We propose a certificate format designed to allow for simple and compact verification code: a list of statements that can be sequentially checked using a limited number of inference rules. We present a supplementary verification tool VIPR for compressing and checking these certificates independently of how they were created. We report computational results on a selection of mixedinteger linear programming instances from the literature. To this end, we have extended the exact rational version of the MIP
solver SCIP to produce such certificates. This is joint work with Kevin Cheung and Daniel Steffy. 
  
18:3019:00  Andreas Tillmann  Sparse Signal Reconstruction with Integrality Constraints  Motivated by diverse applications in signal processing, the efficient solution of the combinatorial problem to find the sparsest exact or approximate solution to an underdetermined linear system has been the focus of a vast amount of research over the past decade. In this work, we investigate conditions for the unique recoverability of sparse integervalued signals from few linear measurements by pursuing the objective of minimizing the number of nonzero components, the socalled l0norm, or its popular l1norm substitute. Our results for different types of integrality constraints and possible variable bounds show that the additional prior knowledge of signal integrality allows for recovering more signals than what can be guaranteed by the established recovery conditions from (continuous) compressed sensing. In some numerical experiments, we investigate checking the recovery conditions; it turns out that the corresponding (mixed) integer programs are quite hard to solve in practice. Nevertheless, although those problems are all NPhard in general (even with an l1objective), mediumsized instances of l0 and l1minimization IPs with binary variables can be solved exactly within reasonable time. This is joint work with JanHendrik Lange, Marc Pfetsch and Bianca Seib. 
  
19:0019:30  Kathrin Klamroth  Multiobjective Unconstrained Combinatorial Optimization: Weight Space Decomposition, Arrangements of Hyperplanes and Zonotopes  We consider a particularly simple class of multiobjective unconstrained combinatorial optimization problems (MUCO) given by $\operatorname{vmin}\{Cx :\,x\in\{0,1\}^n\}$ with $C\in\mathbb{Z}^{m\times n}$, i.e., with positive and negative cost coefficients. In this case, there is a one to one correspondence between (1) the extreme supported nondominated solution vectors of MUCO, (2) a weight space decomposition, (3) the cells of an associated arrangement of hyperplanes, and (4) the nondominated extreme points of a corresponding zonotope. While the interrelation between (1) and (2) holds for general multiobjective combinatorial optimization problems, (3) and (4) rely on the special structure of MUCO. We take advantage of these relations for efficiently computing the set of extreme supported solutions. As a side effect, nonextreme supported solutions can easily be identified in the arrangement of hyperplanes. Furthermore, for multiobjective knapsack problems with some positive and some negative cost coefficients, the weight space decomposition of a corresponding unconstrained instance of MUCO can be used to initialize a multiobjective dichotomic search. The efficiency of this approach depends on the constraint slackness of the knapsack problem. 
  
Tuesday 10Chair:  Christoph Helmberg 
08:3009:30  Leo Liberti  Undecidability and Hardness in MINLP  MINLP is the most general of the MP formulations (barring blackbox). Because of the usual tradeoff between generality and efficiency, MINLP is very difficult to solve in practice. This tutorial will explore the theoretical side of computational difficulty: I will show that MINLP is, in general, an unsolvable problem. Moreover, many of the interesting solvable subcases are hard to solve. I shall argue that unsolvability stems from integrality constraints or the presence of some transcendental functions in the formulation. I shall also present some results on NPhardness of polynomial MINLPs in continuous variables. 
  
09:3010:00  Fritz Bökler  OutputSensitive Complexity of Multiobjective Combinatorial Optimization  We study outputsensitive algorithms and complexity for multiobjective combinatorial optimization problems.
In this computational complexity framework, an algorithm for a general enumeration problem is regarded efficient if it is outputsensitive, i.e., its running time is bounded by a polynomial in the input and the output size.
We provide both practical examples of MOCO problems for which such an efficient algorithm exists as well as problems for which no efficient algorithm exists under mild complexity theoretic assumptions. 
  
Chair:  Bernard Fortz 
10:3011:00  Rico Zenklusen  A Strongly Polynomial Algorithm for Bimodular Integer Linear Programming  We show that any integer linear program (ILP) defined by a constraint matrix whose subdeterminants are all within {2,1,0,1,2} can be solved efficiently; even in strongly polynomial time. This is a natural extension of the wellknown fact that ILPs with totally unimodular (TU) constraint matrices are polynomialtime solvable, which readily follows by the natural integrality of polytopes defined by a TU constraint matrix and integral righthand sides.
To derive our result we combine several techniques. In particular, we first show how to reduce the problem to a particular parityconstraint ILP over a TU constraint matrix. We then leverage Seymour's decomposition of TU matrices to break this parityconstrained ILP into simpler base problems. Finally, we show how these base problems can be solved efficiently by combinatorial optimization techniques, including parityconstrained submodular minimization, and how to derive an optimal solution to the initial ILP from optimal solutions to base problems.
This is joint work with Stephan Artmann and Robert Weismantel. 
  
11:0011:30  Aleksandr Kazachkov  From Final Point Cuts to VPolyhedral Cuts  Generating cutting planes for mixedinteger programs from valid general disjunctions, containing multiple inequalities per term, has been an active topic of inquiry in recent years. We investigate this idea from the perspective of the generalized intersection cut paradigm, of using a properly selected set of points and rays to generate cuts. Our framework, called final point cuts, is a strict extension of the existing paradigm, as previous approaches have only applied to generating cuts from convex sets.
We discuss theoretical properties of final point cuts and implement a particular variant of the method. The computational results indicate promising practical potential for this approach. 
  
11:3012:00  Andreas Wierz  A General Analysis of the PrimalDual Greedy Algorithm  Integer programs $\min{cx : Ax \geq r, x \geq 0, x integral}$ with all coefficients in $A$ positive are called covering problems. For many problems of this form, simple greedy algorithms obtain good or optimum solutions. Famous examples for such systems are contrapolymatroids (optimum), or the knapsack covering problem (2approximation).
We discuss characterizations (in terms of structural properties) of the system $(A,r)$, such that a primaldual greedy algorithm always obtains a feasible solution with bounded approximation ratio. Note that we are interested in such characterizations independent of the cost function. Our characterizations contain both previously mentioned problems (with their respective approximation guarantee) as special cases and extend to a larger class of problems.
(Joint work with Britta Peis and José Verschae) 
  
Chair:  Robert Weismantel 
17:3018:30  Egon Balas  Recent Developments in Disjunctive Programming 
  
18:3019:00  Matthias Walter  Complete Description of Matching Polytopes with One Linearized Quadratic Term for Bipartite Graphs  We consider, for complete bipartite graphs, the convex hulls of characteristic vectors of matchings, extended by a binary number indicating whether the matching contains two specific edges. This polytope is associated to the quadratic matching problem with a single linearized quadratic term. We provide a complete irredundant inequality description, which settles a conjecture by Klein (Ph.D. thesis, TU Dortmund, 2015). 
  
19:0019:30  Lena Hupp  Mixed Integer Reformulations of Robust bMatching Problems  Using Few Integer Variables  In the talk we consider robust twostage (bipartite) bmatching problems with one or several knapsack constraints that link the first stage solution to the second stage solution. Applications of such robust twostage bipartite bmatching problems are for example in Air Traffic Management (ATM). In ATM an efficient planning of runway utilization is one of
the main challenges.
Thereby, uncertainty and inaccuracy often lead to deviations from the actual plan or schedule. By using ideas from robust optimization this uncertainty can be incorporated into the initial computation of the plans. More precisely, each aircraft needs to be assigned to a time slot at the first stage before the uncertainty reveals. If an uncertain scenario occurs the plan might become infeasible and the aircraft need to be replanned in the second stage. To this end, second stage solutions are desired, that do not differ too much from the first stage plan. The restriction of the replanning action may be modeled by one or several special knapsack constraints. A straight forward way is to formulate the resulting twostage bipartite bmatching problem with one or several knapsack constraints as a binary linear integer program (IP).
Following the idea of Bader et al.* we show how to reformulate the IP formulations of the twostage bipartite $b$matching problems as mixed integer programming problems that only use few integer variables. To preserve integrality, an appropriate so called affine TU decomposition of the constraint matrix needs to be found. In the case of the twostage bipartite $b$matching problem with only one knapsack constraint, we give such an affine TU decomposition and show that a MIP reformulation can be given where the number of integral variables only depends on the number of times slots. For the twostage bipartite bmatching problem with several knapsack constraints an appropriate affine TU decomposition cannot be derived in a straight forward way. We give a similar decomposition of the constraint matrix and prove that this decomposition preserves integrality and thus allows a MIP reformulation with less integer variables.
In a computational study we show that
when compared to
solving the IP formulation that only uses binary variables,
root bounds and cpu times can significantly be
improved, when the reformulated MIPs are solved. Moreover, several instances could only be solved when the MIP reformulations are used.
*Jörg Bader, Robert Hildebrand, Robert Weismantel, Rico Zenklusen. Mixed Integer Reformulations of Integer Programs and the Affine TUdimension of a Matrix. Preprint, (2016). 
  
Wednesday 11Chair:  JuanJosé SalazarGonzález 
08:3009:00  Alberto Del Pia  On Decomposability of Multilinear Sets  We consider the Multilinear set defined as the set of binary points satisfying a collection of multilinear equations. Such sets appear in factorable reformulations of many types of nonconvex optimization problems, including binary polynomial optimization. In this talk, we study the decomposability properties of Multilinear sets. Utilizing an equivalent hypergraph representation, we derive necessary and sufficient conditions under which a Multilinear set is decomposable based on the structure of pairwise intersection hypergraphs. Finally, we propose a polynomialtime algorithm to optimally decompose a Multilinear set into simpler subsets. 
  
09:0009:30  David de Laat  Using Polynomial Optimization to Bound Matrix Factorization Ranks  In this talk I will explain how polynomial optimization can be used to compute lower bounds on matrix factorization ranks. First I will show how we can use noncommutative polynomial optimization to compute lower bounds on the cpsdrank (completely positive semidefinite rank) of a matrix. The cpsdrank of a matrix A is the smallest integer d for which A can be written as the Gram matrix of positive semidefinite d by d matrices. Then I will show how we can use these ideas to also compute lower bounds on the cprank and nonnegative rank of a matrix, and I will compare this to existing techniques.
Joint work with Sander Gribling and Monique Laurent 
  
09:3010:00  Sven Mallach  Compact Linearization for Binary Quadratic Problems subject to Assignment Constraints  We present new necessary and sufficient conditions to carry out a compact linearization approach for a general class of binary quadratic problems subject to assignment constraints. After proving correctness, we discuss how a minimally sized linearization can be obtained in practice. The underlying combinatorial optimization problem can be expressed as a mixedinteger linear program that has, under certain circumstances, a totally unimodular constraint matrix. It's general complexity is however not fully clear, making it interesting to introduce it to the audience. 
  
Chair:  Annegret Wagler 
10:3011:30  Michele Conforti  The Infinite Models in Integer Programming  The infinite models in integer programming can be described as the convex hull of some points or as the intersection of halfspaces derived from valid functions. In this paper we study the relationships between these two descriptions. Our results have implications for finite dimensional corner polyhedra.
One consequence is that nonnegative continuous
functions suffice to describe finite dimensional corner polyhedra with rational data. We also discover new facts about corner polyhedra with nonrational data. Joint work with Amitabh Basu, Marco Di Summa and Joseph Paat. 
  
11:3012:00  Tilo Wiedera  Approximation Limits and Algorithms in Practice for the Maximum Planar Subgraph Problem  The Maximum Planar Subgraph Problem asks for a planar subgraph with maximum edge cardinality. It is known to be MaxSNPhard and the best approximation ratio of 4/9 could not be improved since almost 20 years.
We report on an exploratory study on the relative merits of approaches in practice, focusing on observed runtime, solution quality, and implementation complexity. Surprisingly, a seemingly only theoretically strong approximation forms the foundation of the strongest choice.
In addition, We explore general classes of approximation algorithms and derive bounds on the achievable ratios as well as hardness results for thereby arising subproblems. 
  
Chair:  Mathieu Van Vyve 
17:3018:30  Andrea Lodi  On (big) data, optimization and learning  In this talk I review a couple of applications on Big Data that I personally like and I try to explain my point of view as a Mathematical Optimizer  especially concerned with discrete (integer) decisions  on the subject. I advocate a tight integration of Machine Learning and Mathematical Optimization (among others) to deal with the challenges of decisionmaking in Data Science. For such an integration I try to answer three questions: 1) what can optimization do for machine learning? 2) what can machine learning do for optimization? 3) which new applications can be solved by the combination of machine learning and optimization? 
  
18:3019:00  Fabio Furini  Social Network Analysis and Community Detection by Decomposing a Graph into Relaxed Cliques  In social network analysis (SNA), relationships between members of a network are encoded in an undirected graph where vertices represent the members of the network and edges indicate the existence of a relationship. One important task in SNA is community detection, that is, clustering the members into communities such that relatively few edges are in the cutsets, but relatively many are internal edges. The clustering is intended to reveal hidden or reproduce known features of the network, while the structure of communities is arbitrary. We propose decomposing a graph into the minimum number of relaxed cliques as a new method for community detection especially conceived for cases in which the internal structure of the community is important. Cliques, that is, subsets of vertices inducing complete subgraphs can model perfectly cohesive communities, but often they are overly restrictive because many real communities form dense, but not complete subgraphs. Therefore, different variants of relaxed cliques have been defined in terms of vertex degree and distance, edge density, and connectivity. They allow to impose applicationspecific constraints a community has to fulfill such as familiarity and reachability among members and robustness of the communities. Standard compact formulations fail in finding optimal solutions even for small instances of such decomposition problems. Hence, we propose a framework for solving to optimality the problem of partitioning/covering a graph with any type of relaxed clique based on a DantzigWolfe reformulation and branchandprice techniques. Extensive computational results demonstrate the effectiveness of all components of the algorithms and the validity of our approach when applied to social network instances from the literature. 
  
19:0019:30  Achill Schürmann  Linear Symmetries in Integer Convex Optimization  Standard techniques for integer optimization problems appear to work often quite poorly on symmetric problems. Despite some special approaches developed over the last decade, there is no good general approach to make use of symmetries so far. In this talk we give a brief survey about linear symmetry groups of convex optimizations problems (as for instance found in MIPLIB 2010) and we present some ideas to exploit these symmetries based on group specific reformulations.

  
Thursday 12Chair:  Marc Uetz 
08:3009:00  Dirk Oliver Theis  Extension Complexity of Spanning Tree  Bad News on Lower Bounds  The Minimum Spanning Tree problem (on a complete graph with n nodes) has, next to the classical, exponential size LP formulation, an "extended formulation" by Martin (1991) of size O(n^3). It is an open question whether or not this can be improved to o(n^3).
The only known lower bound is the (trivial) dimension bound, \Omega(n^2). In this talk, we show that the "combinatorial" lower bounds (related to nondeterministic communication complexity) fail for the Spanning Tree polytope: The fooling set bound is O(n^2); the rectangle covering bound is O(n^2 log n). 
  
09:0009:30  Daniel Schmidt  Integer Programming Formulations for the Steiner Forest Problem  The Steiner Forest problem admits several distinct formulations as an Integer Linear Program (ILP). We perform an experimental study on the effectiveness of these formulations and present an ILP formulation that is based on Edmond's tree polytope. To the best of our knowledge, this tree polytope based formulation has not been studied previously. 
  
09:3010:00  Pietro Saccardi  Geometric Steiner Tree Packing with Density Constraints  We present a new approach for embedding Steiner trees into the plane, subject to density constraints. The application is global routing in VLSI design, where connections are modeled as rectilinear Steiner trees. Traditional global routing partitions the plane into rectilinear tiles, whose centers gives rise to a grid graph. It thereby embeds Steiner trees into the grid graph where edges are subject to capacity constraints. However, in this approach the original terminal position is lost, leading to inaccurate length estimates and unfavorable topologies in detailed routing. In contrast, we always consider the exact terminal position. We subdivide the plane into rhomboidal tiles, and we assign them a price based on relative wire density across several routing phases. We show that we can find a minimum cost path between two terminals (where the cost of a path is proportional to its length and the tile's price), by reducing the geometrical problem to a shortest path in graphs. We can thus exploit the MinMax Resource Sharing algorithm to minimize relative wire density globally. We demonstrate this in practice by efficiently solving large instances (with 10^6 nets and 10^7 tiles), and using the computed solution as a starting point for further routing algorithms. This was joint work with Nicolai Hähnle. 
  
Chair:  Karen Aardal 
10:3011:30  Frank Vallentin  Solving Semidefinite Programs for Packing Problems 
  
11:3012:00  Markus Sinnl  Interdiction Games and Monotonicity  Twoperson interdiction games represent an important modeling concept for applications in marketing, defending critical infrastructure, stopping nuclear weapons projects or preventing drug smuggling.
In this talk, we present an exact branchandcut algorithm for interdiction games, under the assumption that feasible solutions of the follower problem satisfy a certain monotonicity property. Prominent examples from literature that fall into this category are knapsack interdiction, matching interdiction, and packing interdiction problems. We also show how practicallyrelevant interdiction variants of the facility location and prizecollecting problems can be modeled in our setting. Our branchandcut algorithm uses a solution scheme akin to Benders decomposition, based on a family of socalled interdiction cuts. We present modified and lifted versions of these cuts along with exact and heuristic procedures for the separation of interdiction cuts, and heuristic separation procedures for the other versions. In addition, we derive further valid inequalities and present a new heuristic procedure.
We computationally evaluate the proposed algorithm on a benchmark of 360 knapsack interdiction instances from literature, including 27 instances for which the optimal solution was not known. Our approach is able to solve each of them to optimality within about one minute of computing time on a standard PC (in most cases, within just seconds), and is up to 4 orders of magnitude faster than any previous approach from the literature. To further assess the effectiveness of our branchandcut algorithm, an additional computational study is performed on 144 randomly generated instances based on 0/1 multidimensional knapsack problems.
The work is joint work with M. Fischetti, I. Ljubic and M. Monaci. 
  
Chair:  Gautier Stauffer 
17:3018:30  Martine Labbé  Bilevel Optimisation, Pricing Problems and Stackeberg Games  Bilevel optimisation problems consist in constraint optimisation problems in which a subset of variables constitute the optimal solution of second optimisation problem. They correspond to situations in which two groups of decisions are taken sequentially.
A first part of this talk will present the main aspects, properties and algorithms for bilevel optimization problems with a particular attention to the bilevel linear ones.
The second part will focus on bilevel problems with bilinear objectives and in particular on Pricing and Stackelberg problems. 
  
18:3019:00  Viktor Bindewald  Robust Assignments with Vulnerable Nodes  Reallife optimization problems require making upfront decisions before all parameters of the problem have been disclosed. This talk deals with the Robust Assignment Problem (RAP) which models situations in which certain resources are vulnerable and may become unavailable after the solution has been chosen.
Such problems arise in scheduling and staff rostering, where a set of tasks needs to be assigned to the available set of resources (personnel or machines), in a way that all tasks have assigned resources, and no
two tasks share the same resource. In this setting the unavailability can be caused e.g. by an employee's sickness, or machine failure.
The goal is to choose a minimumcost collection of resources (nodes in the corresponding bipartite graph) so that if any vulnerable node becomes unavailable, the remaining part of the solution still contains sufficient nodes to perform all tasks.
The talk focuses on algorithms and hardness results for RAP.
Joint work with David Adjiashvili and Dennis Michaels. 
  
19:0019:30  Miriam Schlöter  Fast and MemoryEfficient Algorithms for Evacuation Problems  Fast and MemoryEfficient Algorithms for Evacuation Problems
We study two classical flow over time problems that capture the essence of evacuation planning. Given a network with capacities and transit times on the arcs and sources/sinks with supplies/demands, a \emph{quickest transshipment} sends the supplies from the sources to meet the demands at the sinks as quickly as possible. In a 1995 landmark paper, Hoppe and Tardos describe the first strongly polynomial time algorithm solving the quickest transshipment problem. Their algorithm relies on repeatedly calling an oracle for parametric submodular function minimization.
We present a somewhat simpler and more efficient algorithm for the quickest transshipment problem. Our algorithm (i)~relies on only one parametric submodular function minimization and, as a consequence, has considerably improved running time, (ii)~uses not only the solution of a submodular function minimization but actually exploits the underlying algorithmic approach to determine a quickest transshipment as a convex combination of simple lexmax flows over time, and (iii)~in this way determines a structurally easier solution in the form of a generalized temporally repeated flow.
Our second main result is an entirely novel algorithm for computing \emph{earliest arrival transshipments}, which feature a particularly desirable property in the context of evacuation planning. An earliest arrival transshipment ~which in general only exists in networks with a single sink~ is a quickest transshipment maximizing the amount of flow which has reached the sink for every point in time simultaneously. In contrast to previous approaches, our algorithm solely works on the given network and, as a consequence, requires only polynomial space.

  
Chair:  The Organizers 
20:4521:15  Michael Jünger, Gerhard Reinelt, and Giovanni Rinaldi  The Aussois C.O.W.  Brief reminiscences of the first 21 editions of the Workshop. 
  
Friday 13Chair:  Paolo Ventura 
08:3009:00  Joachim Schauer  The Data Arrangement Problem on Binary Trees  The data arrangement problem on regular trees (DAPT) consists in assigning the vertices of a given graph G, called the guest graph, to the leaves of a dregular tree T, called the host graph, such that the sum of the pairwise distances of all pairs of leaves in T which correspond to the edges of G is minimized. Luczak and Noble [02] have shown that this problem is NPhard for every fixed d greater than or equal to 2. We show that DAPT remains NPhard even if the guest graph is a tree, an issue which was posed as an open question in by Luczak and Noble [02]. Moreover we deal with the special case of DAPT where both the guest and the host graph are binary regular trees and provide a 1.015approximation algorithm for this special case. The analysis of the approximation algorithm involves an auxiliary problem which is interesting on its own, namely the kbalanced partitioning problem (kBPP) for binary regular trees and particular choices of k. 
  
09:0009:30  Michele Monaci  Reformulation Heuristics for Generalized Interdiction Problems  We consider a subfamily of mixedinteger linear bilevel problems that we call Generalized Interdiction Problems. This class of problems has a number of important practical applications and includes, among others, the relevant family of problems known as interdiction problems, i.e., zerosum Stackelberg games. We propose a new heuristic scheme for generalized interdiction problems, based on a singlelevel and compact mixedinteger linear programming reformulation of the problem. We describe a very basic version of our heuristic, which is very simple to implement and produces very good results in practice. We also introduce two more sophisticated variants, that sometimes yield improved solutions in slightly longer computing times. We report an extensive computational analysis on various classes of test instances from the literature, showing that our heuristics proved extremely effective on a large number of instances, often providing an optimal solution within negligible computing time.
(joint work with M. Fischetti and M. Sinnl)

  
09:3010:00  Sara Mattia  Staffing and Scheduling Flexible Call Centers by TwoStage Robust Optimization  We study the shift scheduling problem in a multishift, flexible call center. Differently from previous approaches, the staffing levels ensuring the desired quality of service are considered uncertain, leading to a twostage robust integer program with rightandside uncertainty. We show that, in our setting, modeling the correlation of the demands in consecutive time slots is easier than in other staffing approaches. The complexity issues of a Benders type reformulation are investigated and a branchandcut algorithm is devised. The approach can efficiently solve realworld problems from an Italian call center and effectively support managers decisions. In
fact, we show that robust shifts have very similar costs to those evaluated by the traditional (deterministic) method while ensuring a higher level of protection against uncertainty. 
  
Chair:  Volker Kaibel 
10:3011:00  Tobias Hofmann  Periodic Event Scheduling and its Industrial Application  The talk will be about a variant of the periodic event scheduling problem introduced by Serafini and Ukovich.
The focus will be on its cycle periodicity formulation as well as its application in the context of scheduling robot based manufacturing lines. 
  
11:0012:00  Jack Edmonds  Understanding EP and PPA: Can it be Hard to Find, if it's Easy to Recognize and you Know it's There? 
  
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.) 