PROGRAM
Monday 9Chair: | Michael Jünger |
08:30-09:00 | Oktay Günlük | Lattice Closures of Polyhedra | Abstract: We define the k-dimensional lattice closure of a polyhedral mixed-integer 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 k-dimensional lattice closure of a rational polyhedral mixed-integer 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 k-dimensional lattice closure does not give the integer hull. We show that valid inequalities from unbounded, full-dimensional, convex lattice-free sets cannot give the integer hull either. |
| | |
09:00-09: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 co-NP, an indication that it is probably not NP-complete.
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 NP-complete, 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 NP-hard 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 NP-hard. These results improve earlier complexity results of Cornuejols and Li and Eisenbrand. Finally, we prove that, for any positive integer k, it is NP-hard 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:30-10:00 | Stefan Weltge | Polytopes in the 0/1-Cube with Bounded Chvátal-Gomory 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átal-Gomory rank (CG-rank) provided that S has bounded pitch and bounded gap, where the pitch is the minimum integer p such that all p-dimensional faces of the 0/1-cube 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 n-cube 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 CG-rank of R is bounded as a function of the treewidth of H[S]. We also prove that if S has pitch 3, then the CG-rank of R is always bounded. Both results generalize a recent theorem of Cornuéjols and Lee (2016), who proved that the CG-rank 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:30-11: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 collision-free 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:30-12:00 | Martin Schmidt | Optimal Price Zones of Electricity Markets: A Mixed-Integer Multilevel Model and Global Solution Approaches | Mathematical modeling of economic market design often leads to mixed-integer nonlinear multilevel optimization problems for which no general-purpose 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 welfare-optimal outcomes. This modeling leads to a challenging multilevel problem that contains a graph partitioning problem with multi-commodity flow connectivity constraints and nonlinearities due to proper economic modeling. Furthermore, it has highly symmetric solutions. We develop different problem-tailored 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 problem-specific generalized Benders approach performs considerably better than the methods based on KKT transformation. |
| | |
Chair: | Giovanni Rinaldi |
17:30-18:00 | Lars Schewe | Penalty Alternating Direction Methods for Mixed-Integer Optimization: A New View on Feasibility Pumps | Feasibility pumps are highly effective primal heuristics for
mixed-integer 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
mixed-integer linear and nonlinear problems.
|
| | |
18:00-18:30 | Ambros Gleixner | Verifying Integer Programming Results | Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point 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 state-of-the-art 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 mixed-integer 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:30-19: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 integer-valued signals from few linear measurements by pursuing the objective of minimizing the number of nonzero components, the so-called l0-norm, or its popular l1-norm 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 NP-hard in general (even with an l1-objective), medium-sized instances of l0- and l1-minimization IPs with binary variables can be solved exactly within reasonable time. This is joint work with Jan-Hendrik Lange, Marc Pfetsch and Bianca Seib. |
| | |
19:00-19: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:30-09:30 | Leo Liberti | Undecidability and Hardness in MINLP | MINLP is the most general of the MP formulations (barring black-box). Because of the usual trade-off 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 sub-cases 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 NP-hardness of polynomial MINLPs in continuous variables. |
| | |
09:30-10:00 | Fritz Bökler | Output-Sensitive Complexity of Multiobjective Combinatorial Optimization | We study output-sensitive 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 output-sensitive, 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:30-11: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 well-known fact that ILPs with totally unimodular (TU) constraint matrices are polynomial-time solvable, which readily follows by the natural integrality of polytopes defined by a TU constraint matrix and integral right-hand sides.
To derive our result we combine several techniques. In particular, we first show how to reduce the problem to a particular parity-constraint ILP over a TU constraint matrix. We then leverage Seymour's decomposition of TU matrices to break this parity-constrained ILP into simpler base problems. Finally, we show how these base problems can be solved efficiently by combinatorial optimization techniques, including parity-constrained 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:00-11:30 | Aleksandr Kazachkov | From Final Point Cuts to V-Polyhedral Cuts | Generating cutting planes for mixed-integer 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:30-12:00 | Andreas Wierz | A General Analysis of the Primal-Dual 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 (2-approximation).
We discuss characterizations (in terms of structural properties) of the system $(A,r)$, such that a primal-dual 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:30-18:30 | Egon Balas | Recent Developments in Disjunctive Programming |
| | |
18:30-19: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:00-19:30 | Lena Hupp | Mixed Integer Reformulations of Robust b-Matching Problems - Using Few Integer Variables | In the talk we consider robust two-stage (bipartite) b-matching problems with one or several knapsack constraints that link the first stage solution to the second stage solution. Applications of such robust two-stage bipartite b-matching 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 two-stage bipartite b-matching 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 two-stage 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 two-stage 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 two-stage bipartite b-matching 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 TU-dimension of a Matrix. Preprint, (2016). |
| | |
Wednesday 11Chair: | Juan-José Salazar-González |
08:30-09: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 pair-wise intersection hypergraphs. Finally, we propose a polynomial-time algorithm to optimally decompose a Multilinear set into simpler subsets. |
| | |
09:00-09: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 cpsd-rank (completely positive semidefinite rank) of a matrix. The cpsd-rank 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 cp-rank and nonnegative rank of a matrix, and I will compare this to existing techniques.
Joint work with Sander Gribling and Monique Laurent |
| | |
09:30-10: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 mixed-integer 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:30-11: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 non-rational data. Joint work with Amitabh Basu, Marco Di Summa and Joseph Paat. |
| | |
11:30-12: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 MaxSNP-hard 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:30-18: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 decision-making 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:30-19: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 application-specific 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 Dantzig-Wolfe reformulation and branch-and-price 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:00-19: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:30-09: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:00-09: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:30-10: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 Min-Max 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:30-11:30 | Frank Vallentin | Solving Semidefinite Programs for Packing Problems |
| | |
11:30-12:00 | Markus Sinnl | Interdiction Games and Monotonicity | Two-person 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 branch-and-cut 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 practically-relevant interdiction variants of the facility location and prize-collecting problems can be modeled in our setting. Our branch-and-cut algorithm uses a solution scheme akin to Benders decomposition, based on a family of so-called 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 branch-and-cut 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:30-18: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:30-19:00 | Viktor Bindewald | Robust Assignments with Vulnerable Nodes | Real-life 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 minimum-cost 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:00-19:30 | Miriam Schlöter | Fast and Memory-Efficient Algorithms for Evacuation Problems | Fast and Memory-Efficient 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 lex-max 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:45-21: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:30-09: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 d-regular 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 NP-hard for every fixed d greater than or equal to 2. We show that DAPT remains NP-hard 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.015-approximation algorithm for this special case. The analysis of the approximation algorithm involves an auxiliary problem which is interesting on its own, namely the k-balanced partitioning problem (kBPP) for binary regular trees and particular choices of k. |
| | |
09:00-09:30 | Michele Monaci | Reformulation Heuristics for Generalized Interdiction Problems | We consider a subfamily of mixed-integer 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., zero-sum Stackelberg games. We propose a new heuristic scheme for generalized interdiction problems, based on a single-level and compact mixed-integer 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:30-10:00 | Sara Mattia | Staffing and Scheduling Flexible Call Centers by Two-Stage Robust Optimization | We study the shift scheduling problem in a multi-shift, flexible call center. Differently from previous approaches, the staffing levels ensuring the desired quality of service are considered uncertain, leading to a two-stage robust integer program with right-and-side 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 branch-and-cut algorithm is devised. The approach can efficiently solve real-world 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:30-11: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:00-12: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 1958-2008. Jünger, M.; Liebling, Th.M.; Naddef, D.; Nemhauser, G.L.; Pulleyblank, W.R.; Reinelt, G.; Rinaldi, G.; Wolsey, L.A. (Eds.) |
|
AUSSOIS 2004 (published 2006) |
 |
Combinatorial Optimization: Theory and Computation The Aussois Workshop 2004. Liebling, Th.M.; Naddef, D.; Wolsey, L.A. (Eds.) |
|
AUSSOIS 2001 (published 2003) |
 |
Combinatorial Optimization -- Eureka, You Shrink!Jünger, M.; Reinelt, G.; Rinaldi, G. (Eds.) |
|
AUSSOIS 2000 (published 2003) |
 |
The Aussois 2000 workshop in combinatorial optimizationLiebling, Th.M.; Naddef, D.; Wolsey, L.A. (Eds.) |