Geometric methods

Combinatorics has developped its own tools, sometimes based on advanced techniques from classical mathematics. Several examples showed that tools from linear algebra, number theory, or a geometric tools including Integer Linear Programming can help solving hard problems. Solutions of combinatorial problems using these tools are often simple and elegant, and sometimes yield fundamental result and efficient algorithms. A specific tool, which has proven to be particularly powerful, is based on the following idea: we can associate to any combinatorial object (matchings, travelling salesman tours, ...) a vector in a natural way. Optimizing on the combinatorial objects then becomes the same as optimizing on the convex hull of the associated vectors (using basic properties of Linear Programming). This is the starting point of Polyhedral Combinatorics.

However the constraints of this convex hull are not necessarily easy to determine. This is the main object of important research, both theoretical and applied, often in connection with integer linear problems. Our team contributes to this research, for instance in the study of Hilbert cones, Carathéodory number, or a conjecture of Berge and Linial on the cover of the vertices of a graph by cycles. These studies sometimes lead to the design of branch and cut algorithms to find optimal solutions. Recently these algorithms found some interesting applications in problems of Bin packing, Cutting stock, multiprocessor scheduling, ...

Other tools from geometry have been succesfully used in combinatorics: for instance, kernels in graphs are connected to topological results of Scarf (and game theory). Binary clutters, an abstract generalization of circuit spaces in graphs, have been applied to solve many problems, like postman problems, or multiflows. We have been particularly interested in paintshop scheduling, a scheduling problem of the automotive industry that consists in optimizing the painting sequence in a series of cars. Recently, we discovered deep connections of this problem with combinatorial topology and polyhedral geometry. These connections allowed a better understanding of the complexity of the problem, which is quite non conventional.