Amitabh Basu

(Johns Hopkins University, USA)

Jeudi 24 juin 14h00-15h00

Concrete complexity bounds for optimizing over integers

We discuss the complexity of the two main ingredients in integer optimization algorithms: cutting planes and branch-and-bound. We prove upper and lower bounds on the efficiency of these algorithms, when efficiency is measured in terms of complexity of the LPs that are solved. More precisely, we focus on the sparsity of the LPs and the number of LPs as measures of complexity. We also give general conditions under which combining branching and cutting into a branch-and-cut algorithm can do exponentially better than pure cutting planes or pure branch-and-bound. Time permitting, some connections to mathematical logic and proof complexity will be discussed.

Ricardo Fukasawa

(University of Waterloo, Canada)

Vendredi 25 juin 16h30-17h30

IP formulations for vehicle routing with stochastic demands

The deterministic vehicle routing problem consists on finding the cheapest set of routes to serve a set of customers, each with a fixed demand, subject to respecting capacity constraints on each route. In the stochastic variant, demands are considered random variables. Most approaches for such problems assume independence of such random variables. We discuss progress in formulating the problem as an integer program without such assumptions.

Maya Jakobine Stein

(Universidad de Chile, Chili)

Jeudi 24 juin 16h30-17h30

Minimum degrees and tree subgraphs

This talk is a survey of the history and recent developments on questions related to tree subgraphs of graphs having large minimum degree. The starting point is the following easy observation: Any graph of minimum degree at least k contains any trees on k+1 vertices as a subgraph. This can be shown by just greedily embedding the tree in a connected way. Several attempts have been made to relax the conditions in different ways. For instance, it is possible to drop the minimum degree condition to 2k/3 if a maximum degree condition is imposed at the same time, or if certain other conditions on the host graph, or on the tree are added. We will also consider recent extensions of this type of question to directed graphs and hypergraphs.

Laura Sanita

(TU Eindhoven, Netherlands)

Vendredi 25 juin 14h00-15h00

On the diameter and the circuit-diameter of polytopes

The diameter of a polytope P is the maximum length of a shortest path between a pair of vertices of P, when one is allowed to walk on the edges (1-dimensional faces) of P. Despite decades of studies, it is still not known whether the diameter of a d-dimensional polytope with n facets can be bounded by a polynomial function of n and d. This is a fundamental open question in discrete mathematics, motivated by the (still unknown) existence of a polynomial pivot rule for the Simplex method for solving Linear Programs. A generalized notion of diameter, recently introduced in the literature, is that of circuit-diameter, defined as the maximum length of a shortest path between two vertices of P, where the path can use all edge directions (called circuits) that can arise by translating some of the facets of P. In this talk, I will discuss some algorithmic and complexity results related to the diameter and the circuit-diameter of polytopes, highlighting important open questions.