direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Workshop: Combinatorial Optimization

Lupe

Goal

Combinatorial Optimization is an active research area that developed from the rich interaction among many mathematical fields, including combinatorics, graph theory, geometry, optimization, probability, theoretical computer science, and many others. It combines algorithmic and complexity analysis with a mature mathematical foundation and it yields both basic research and applications in manifold areas. The goal of this two-day workshop was to discover new connections, identify and explore emerging breakthrough areas, and discuss the most recent developments.

Organizers

Volker Kaibel (U Magdeburg)

Martin Skutella (TU Berlin)

Program

Thursday, September 26, 2019

  • 12:30-14:00 Speakers' Lunch
  • 14:00-15:00 Gerhard J. Woeginger (RWTH Aachen)
    The Dimension of a Simple Game (slides)
  • 15:00-15:30 Ágnes Cseh (Hungarian Academy of Sciences)
    Optimal Kidney Exchange with Immunosuppressants (slides)
  • 15:30-16:00 Marc Uetz (U Twente)
    Equilibria for (Some) Atomic Congestion Games (slides)
  • 16:00-16:30 Coffee Break
  • 16:30-17:00 Fritz Eisenbrand (EPF Lausanne)
    Integer Programs with Block Structure  
  • 17:00-18:00 Michele Conforti (U Padova)
    Cutting Planes and Branch-and-Bound
  • 18:00-19:30 Break
  • 19:30- Workshop Dinner (invitation only)

 

Friday, September 27, 2019

  • 9:00-10:00 Britta Peis (RWTH Aachen)
    On Matroids, Greedy Systems, and Primal-Dual Algorithms (slides)
  • 10:00-10:30 Angelika Wiegele (U Klagenfurt)
    Trivial Results using Complicated Methods (slides)
  • 10:30-11:00 Coffee Break
  • 11:00-11:30 Andrea Lodi (Poly Montréal)
    Generalized Surrogate Duality for Mixed-Integer Nonlinear Programs (slides)
  • 11:30-12:00 Leen Stougie (CWI Amsterdam)
    Fixed-Order Scheduling on Parallel Machines (slides)
  • 12:00-13:30 Lunch Break
  • 13:30-14:00 Ekkehard Köhler (BTU Cottbus-Senftenberg)
    This Cannot be The End!
  • 14:00-15:00 Tom McCormick (UBC Vancouver)
    Combinatorial versus Ellipsoid Polynomial Algorithms (slides)

Support

Lupe

We acknowledge support by the Berlin Mathematics Research Center MATH+.

Abstracts

Gerhard J. Woeginger (RWTH Aachen)

Title: The Dimension of a Simple Game (slides)

Abstract: Simple games are monotone set systems that are used to model certain voting situations in social choice theory. Alan Taylor and William Zwicker (1993) introduced the dimension of a simple game as a measure for the distance from a weighted majority game.  The talk discusses several combinatorial and algorithmic questions around this Taylor-Zwicker dimension; all introduced concepts are illustrated by examples from the real world.

 

Ágnes Cseh (Hungarian Academy of Sciences)

Title: Optimal Kidney Exchange with Immunosuppressants (slides)

Abstract: The deployment of centralized matching algorithms for efficient exchange of donated kidneys is a major success story of market design. In the standard kidney exchange problem, blood- or tissue-type incompatibility between a patient and a donor makes a transplant impossible. However, novel technological advances on potent immunosuppressant drugs can lift this barrier.
We present a general computational framework to study kidney exchange with immunosuppressants. In contrast to the standard kidney exchange problem, our problem also involves the decision about which patients get immunosuppressants to make them compatible with originally incompatible kidneys. Our main contribution is a set of general algorithms that provide flexibility in terms satisfying meaningful purposes.

 

Marc Uetz (U Twente)

Title: Equilibria for (Some) Atomic Congestion Games (slides)

Abstract: Some 20 years after publication of the three foundational papers in algorithmic game theory, it is well known that outcomes that arise as equilibrium solutions of a game played by selfish players, may be suboptimal in terms of a central objective function. Congestion games, and more specifically network routing games are the showcase problems in this area, just like the TSP in combinatorial optimization. The talk gives a selection of known and some recent results for atomic congestion games. It is based on joint and ongoing work with J. Correa, J. de Jong, B. de Keijzer, W. Kern, and M. Klimm.

 

Fritz Eisenbrand (EPF Lausanne)

Title: Integer Programs with Block Structure

Abstract: Integer programs in block structure, especially N-fold integer programs, have received considerable attention in the recent literature, especially in the community that deals with fixed parameter tractability. In this talk, I survey some results on N-fold integer programs and outline a new approach with the currently best known running time. The talk is based on joint work with Jana Slovjecsek and Robert Weismantel.

 

Michele Conforti (U Padova)

Title: Cutting Planes and Branch-and-Bound

Abstract: Cutting plane and Branch-and-Bound methods were designed several decades to solve  integer programs and are the backbone of every state of the art solver. While these methods were the subject of extensive  computational testing, the theoretical evaluation of these methods is still in progress. We present some of the questions that we think are relevant and give an overview  the literature. We then present some results regarding integer programming in the plane and some examples that highlight the comparative behavior of cutting planes versus branch-and-bound.
This is joint work with Marco Di Summa (Padova), Amitabh Basu, and Hongyi Yang (Johns Hopkins).

 

Britta Peis (RWTH Aachen)

Title: On Matroids, Greedy Systems, and Primal-Dual Algorithms (slides)

Abstract: Matroids are known to be exactly those combinatorial structures  for which a simple primal-dual greedy algorithm "works" in the sense that the solutions returned by the algorithm are guaranteed to be optimal.
The same simple primal-dual greedy algorithm is often applied to more general classes of capacitated packing and covering problems, like, e.g., set cover and knapsack cover, to mention just a few.
In the first part of the talk, we identify necessary and sufficient conditions to guarantee feasibility of the solutions returned by the primal-dual algorithm.  Moreover, we show that the performance guarantee for such "greedy systems" can be easily determined by  some instance-specific parameter.
In the second part of the talk, we present a primal-dual algorithm which solves the following generalization of weighted matroid intersection in strongly polynomial time: given two matroids on the same ground set, find two bases, one in each matroid, minimising the sum of two distinct cost functions, so that the size of their intersection is equal to some given parameter k.
(Based on joint work with Stefan Lendl, Veerle Tan-Timmermans, Jose Verschae, and Andreas Wierz.)

 

Angelika Wiegele (U Klagenfurt)

Title: Trivial Results using Complicated Methods (slides)

Abstract: In 1968 Vizing conjectured that the product of the domination number of two graphs is always smaller or equal to the domination number of the product graph. Today, we still don't know whether this conjecture is true or not.
In this talk we will investigate a completely new way of tackling Vizing's conjecture. First we will build an algebraic model of the conjecture with some parameters. Then we will translate Vizing's conjecture for these parameters into the question of whether a specific polynomial is nonnegative over a specific ideal. Then we will do another reformulation to the question of whether a specific polynomial is a sum-of-squares polynomial on a certain level of the sos-hierarchy and discuss how we can use semidefinite programming to answer these kind of questions.
We obtain results on graphs, for which the combinatorics is fairly trivial. But we provide a proof of concept of our new method to tackle Vizing's conjecture.
This is joined work with Elisabeth Gaar, Daniel Krenn, and Susan Margulies.

 

Andrea Lodi (Polytechnique Montréal)

Title: Generalized Surrogate Duality for Mixed-Integer Nonlinear Programs (slides)

Abstract: The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global optimality with spatial branch-and-bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, these relaxations are usually required to be convex. Nonetheless, current optimization solvers can often handle a moderate presence of non-convexities efficiently, which opens the door for the use of potentially tighter non-convex relaxations. One way to construct such a relaxation is by aggregating nonlinear constraints of the problem into a single non-convex constraint. The resulting relaxation is called surrogate relaxation, which is similar to the well-known Lagrangian relaxation but provides stronger dual bounds in general. In this talk, we make use of the surrogate dual in a non-convex setting and show the benefits and challenges such relaxation can have in general MINLPs. Additionally, we present a generalization of the surrogate relaxation that allows for multiple aggregations of non-convex constraints. Based on a known Benders-type approach, we present an algorithm that can solve our generalized surrogate relaxation, along with several computational enhancements for improving its practical performance. Finally, we conduct extensive computational experiments on instances of the MINLPLib using the global solver SCIP.
(Joint work with Maxime Gasse, Ambros Gleixner, Benjamin Müller, Gonzalo Muñoz)

 

Leen Stougie (CWI Amsterdam)

Title: Fixed-Order Scheduling on Parallel Machines (slides)

Abstract: We consider an extremely simple, yet challenging, scheduling principle that arises in many logistic and service applications. Given a sequence of jobs and a set of machines, we need to dispatch the jobs one by one over the machines, where for each machine the ordering of the original sequence is preserved. Hence, each machine must handle the jobs in a first-in first-out (FIFO) order. Each job has a processing time and weight and the goal is to minimize the weighted sum of completion times, where the completion time of a job is the total processing time of the jobs preceding the job (including the job itself) on the same machine. The FIFO-ordering restriction is common in multi-server queuing theory, where the task assignment problem is concerned with the same question, except that jobs arrive stochastically over time. Our problem can be seen as asking for the optimal way of dispatching jobs from a single queue over m server queues under complete information of the processing times, essentially unzipping a single queue into m queues. Our scheduling problem appears to be highly resistant to all techniques for (approximate) scheduling under other models. A big obstacle is that moving even a single pair of jobs onto the same machine can have a catastrophic effect on the objective function if the order is fixed. We establish a constant factor approximation algorithm for this (strongly NP-hard) problem and a QPTAS for the special case of unit processing times. We notice that the complexity of the latter version of the problem is intriguingly unknown.
This is based on work in collaboration with Thomas Bosman, Dario Frascaria, Neil Olver, and Rene Sitters

 

Ekkehard Köhler (BTU Cottbus-Senftenberg)

Title: This Cannot be The End!

Abstract: End vertices of graph searches can exhibit strong structural properties and are crucial for many graph algorithms. The problem of deciding whether a given vertex of a graph is an end-vertex of a particular search has been studied by various authors before. It has been shown that this problem is in fact NP-complete for LBFS already on weakly chordal graphs. A similar result exists for BFS.
In this talk we show that the end-vertex problem is NP-complete for MNS on weakly chordal graphs and for MCS on general graphs. Moreover, building on previous results, we show that this problem is linear for various searches on split and unit interval graphs.
This is joint work with Jesse Beisegel, Carolin Denkert, Matjaž Krnc, Nevena Pivač, Robert Scheffler, Martin Strehler.

 

Tom McCormick (UBC Vancouver)

Title: Combinatorial versus Ellipsoid Polynomial Algorithms (slides)

Abstract: The Ellipsoid Algorithm is a useful way to prove that a problem has a polynomial algorithm, but such algorithms don't work well in practice. Hence, we should be trying to find "combinatorial" polynomial algorithms for such problems.  There are also cases where we already have a combinatorial polynomial algorithm, but we don't have the "dual" description of the underlying polyhedra. In this talk I'll describe some notable successes (Submodular Function Minimization, Abstract Flow, Lattice Polyhedra), and some open problems (Subtour Elimination, 2-Dimensional Precedence-Constrained Scheduling), and I'll make some suggestions on how to attack such open problems.

Lupe

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe