Trimester Seminar Series

September 29, 2021, 4:30 CEST

Jens Vygen (Universität Bonn)

Traveling Salesman Problems: Approximation Algorithms and Black-Box Reductions

We survey the recent progress on approximation algorithms and integrality ratios for variants of the traveling salesman problem, with a focus on black-box reductions from one problem to another. In particular, we explain recent results for the Path TSP and the Capacitated Vehicle Routing Problem, which are joint works with Vera Traub and Rico Zenklusen and with Jannis Blauth and Vera Traub.

October 6, 2021, 4:30 CEST

Xavier Allamigeon (CMAP, École Polytechnique)

What Tropical Geometry Tells Us about the Complexity of Linear Programming

Smale's 9th problem asks whether linear programming (LP) can be solved in strongly polynomial complexity, i.e., by a polynomial-time algorithm in which the number of arithmetic operations is bounded by a polynomial in the number of numerical entries of the input. We show that a famous class of algorithms for LP, log-barrier interior point methods, are not strongly polynomial, by constructing a family of linear programs with $3r+1$ inequalities in dimension $2r$ for which the number of iterations performed is in $Ω(2^r)$. Our approach is based on tropical geometry. We analyze the tropical central path, which is the piecewise linear limit of the central paths of parameterized families of classical linear programs viewed through "logarithmic glasses." We discuss extensions to other self-concordant barriers, such as the entropic barrier (Bubeck & Eldan, 2015). Joint work with Abdellah Aznag, Pascal Benchimol, Stéphane Gaubert, Yassine Hamdi, and Michael Joswig.

October 20, 2021, 4:30 CEST

Gérard Cornuéjols (CMU)

Total Dual Dyadicness

A rational number is dyadic if it is of the form p/2^k where p is an integer and k is a nonnegative integer. Dyadic numbers are important for numerical computations because they have a finite binary representation, and therefore dyadic numbers can be represented exactly on a computer in floating-point arithmetic. In this talk we discuss when a linear system Ax <= b is totally dual dyadic, that is, for all integral vectors w for which min ( yb : yA = w, y >= 0} has a solution, it has a dyadic optimal solution. This is joint work with Ahmad Abdi, Bertrand Guenin and Levent Tuncel.

October 27, 2021, 4:30 CEST

Stephan Held (University of Bonn)

Local Search With Learned Constraints for Last Mile Routing

I will describe the models and algorithms behind our code that was winning the Amazon Last Mile Routing Research Challenge. The task of the challenge was to predict how drivers would plan their driving routes by learning from historical data. The optimization method we employ utilizes a simple and efficient penalty-based local-search algorithm, first developed by Helsgaun to extend the LKH traveling salesman problem code to general vehicle-routing models. We further develop his technique to handle multi-level cluster and disjunctive order constraints that can be learned from an analysis of historical data. The simplicity of the method may make it suitable for further applications where machine learning can discover rules that are expected (or desired) in high-quality solutions. This is joint work with William Cook and Keld Helsgaun.

November 3, 2021, 4:30 CEST

Martin Nägele (ETH Zurich)

Congruency-constrained TU problems beyond the bimodular case

A long-standing open question in Integer Programming is whether integer programs with constraint matrices with bounded subdeterminants are efficiently solvable. An important special case thereof are congruency-constrained integer programs of the form

min {<c,x>: Tx ≤ b, <\gamma, x> ≡ r (mod m), x∈Z^n }

with a totally unimodular constraint matrix T. Such problems have been shown to be polynomial-time solvable for m=2, which led to an efficient algorithm for integer programs with bimodular constraint matrices, i.e., full-rank matrices whose n by n subdeterminants are bounded by two in absolute value. Whereas these advances heavily relied on existing results on well-known combinatorial problems with parity constraints, new approaches are needed beyond the bimodular case, i.e., for m>2. We make first progress in this direction through several new techniques. In particular, we show how to efficiently decide feasibility of congruency-constrained integer programs with a totally unimodular constraint matrix for m=3. Furthermore, for general moduli m, our techniques also allow for identifying flat directions of infeasible problems, and deducing bounds on the proximity between solutions of the problem and its relaxation.This is joint work with Richard Santiago and Rico Zenklusen.

November 24, 2021, 4:30 CEST

Karthik Chandrasekaran (UIUC)

Partitioning over Submodular Structures

In submodular k-partitioning problems, the input is a submodular set function (given via an evaluation oracle) along with a fixed positive integer k (e.g., k = 2, 3, 4, …) and the goal is to partition the ground set into k non-empty parts so as to minimize certain natural objectives of interest. Submodular k-partitioning generalizes partitioning problems over several interesting structures including graphs and hypergraphs. The case of 2-partitioning corresponds to the classic and well-studied submodular minimization problem which is polynomial-time solvable. In this talk, I will outline recent progress towards polynomial-time solvability of submodular k-partitioning for fixed constants k>=3.

November 25, 2021, 4:30 CEST

Kristóf Bérczi (Eötvös University, Budapest)

Structural properties of matroid base families

Given matroids M and N, we call N a reduction of M if every independent set of N is also independent in M. In this talk, we present several open questions related to the reduction of matroids to partition matroids. In particular, we explain how such reductions could help us in answering (at least partially) some of the long-standing open problems on base families, such as the conjecture of Aharoni and Berger on the covering number of intersections of matroids, White's conjecture on compatible base sequences, or Gabow's conjecture on cyclic orderings.