"POC days" - Polyhedra and Combinatorial Optimization
Every two years the French research group "POC" Polyhedra and Combinatorial Optimization" organizes a workshop in France: the "POC days", called JPOC.
For 2021, this workshop will be organized using visio and some of the talks will be given in English.
This webpage will gather (and translate) the information about the English talks of POC days.
To see the website of the Poc days (in French): JPOC12
Click here for the visio link using zoom for the two day.
POC days: June 24 et 25 juin 2021
JPOC Schedule
Two days POC schedule (some talks are in French)
Invited speakers and videos of the talks
Amitabh Basu (Johns Hopkins University, USA) - Thursday June 24 at 14h00 in France (12h00 GMT)
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) - Friday June 25 at 16h30 in France (14h30 GMT)
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) - Thursday June 24 at 16h30 in France (14h30 GMT)
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) - Friday June 25 at 14h00 in France (12h00 GMT)
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.