Combinatorial Optimization consists in finding the best solution among a finite (but typically very large) number of choices. It is a branch of Mathematical Programming, which covers all methods used to determine the optimium of a function under various constraints. The purpose is to minimize a function over a finite, but usually very large set, whose mathematical properties are not easy to characterize. Investigating such characterizations, and the optimization algorithms using them, is the base of the work of our team. We use our expertise in this domain to investigate new problems (purely theoretical ones or some having industrial applications), to analyze them and extract fundamental properties that could be used to solve them or show that their resolution is hard. We develop theoretical tools enabling us to solve a wide variety of problems with adequate methods (exact, heuristics, approximation algorithms, ...) that can be generic or tailor-made.
These results and the related activities - seminars, international projects, lectures and teaching, exchange programs for young researchers - make Grenoble an attractive center in this field and more generally in Discrete Mathematics.
For the hardest problems in Combinatorial Optimization, algorithms are usually preceded by theorems revealing the structure of the problem, or giving a "good" characterization, which justifies the answer. We develop these theorems as well as their algorithmic consequences, or the negative results orienting the research to approximation algorithms.
From the theoretical point of view, we are interested in mathematical objects the solutions of which contribute to a knowledge library, ready to be used when needed. Therefore, we work on Matching theory (T-joins, mmaxfix covers), disjoint paths in graphs (routing, multi flows) or packing and covering problems. and from Network flow theory. The objects we study are widely used and any theoretical progress on them has immediate applied consequences.
Polyhedral Methods Combinatorics has developed its own methods, which may also draw upon advanced tools from classical mathematics. Numerous examples demonstrate that a tool from linear algebra, number theory, or geometry, including integer programming, can unlock the solution to a difficult problem. Proofs constructed in this way are often simple and elegant, sometimes leading to fundamental and algorithmically efficient results. One particularly powerful tool is based on an original idea: associating a vector—often the object's natural "incidence" vector—with a combinatorial object (such as matchings, traveling salesman tours, or vehicle routes). Optimizing over the desired objects is equivalent to optimizing over their convex hull, thanks to the fundamental properties of linear programming. This is the foundational concept of Polyhedral Combinatorics.
 |
 |
 |
However, the constraints defining this convex hull are not necessarily easy to determine. This constitutes a significant area of theoretical and applied research, often leading to integer linear programming problems. The team contributes to this research—for instance, by studying Hilbertian cones and Carathéodory numbers, or by investigating a conjecture by Berge and Linial regarding the covering of graph vertices by cycles. Such work sometimes leads to the development of branch-and-cut algorithms for finding optimal solutions. For example, the study of graph "kernels" leads to topological results by Scarf, which also connect to game theory. "Binary clutters"—an abstract generalization of graph "cycle spaces"—have enabled the resolution of a wide variety of problems (such as those involving postman tours and multicommodity flows) and have led to progress on the "paintshop scheduling" problem, a production scheduling challenge in the automotive industry that involves optimizing the painting sequence for a series of cars.
We are interested in several aspects of the field: structural, algorithmically, and extremal graph theory.
Optimization problems that we study often involve graphs, in connection with concepts such as colorings, flows, matchings, T-joins, tours, and arborescences. The graphs themselves may incorporate additional information that must be taken into account, such as an underlying metric or an embedding into a surface—or, more generally, into a topological space. Solving these problems draws upon a wide range of tools from graph theory and combinatorial optimization—such as matroids, submodular functions, polyhedral combinatorics, linear programming (including integer programming), and semidefinite programming—as well as tools from probability, topology, geometry, linear algebra, and group theory.
When a graph is very large, using standard exact algorithms is not feasible, as even quadratic (or linear) complexity becomes prohibitive. One might therefore choose to sacrifice some precision to drastically reduce complexity, aiming for sublinear running times. This is the approach chosen in property testing: given a property P and a graph G, the goal is to determine very efficiently whether G satisfies property P or is "far" from doing so (leaving the intermediate case undecided, when G narrowly fails to satisfy P). For instance, determining whether a graph is far from being triangle-free is closely linked to problems in additive combinatorics and Szemerédi's regularity lemma.
We leverage advances in structural and extremal properties to develop efficient algorithms for solving discrete optimization problems. Beyond the question of whether a solution exists, we also investigate the set of solutions itself—either by seeking to enumerate them rapidly or by attempting to understand the geometry of the solution space (e.g., is it possible to transition between any two solutions via a sequence of small local modifications?). This drives research into combinatorial enumeration and reconfiguration, areas pursued by several team members, which are linked to topics such as statistical physics and sometimes require advanced topological tools.
The graphs under study are sometimes embedded in metric spaces (such as in the Traveling Salesperson Problem) or topological spaces (for instance, planar or surface embeddings), or have exceptional algebraic properties (such as Cayley graphs); consequently, the algorithmic techniques employed must take these additional structures into account. The resulting techniques thus align more closely with geometry, topology, or group theory than with standard combinatorial methods.
Below are some illustrations :
In addition to the theoretical study of combinatorial problems and their algorithmic complexity, the team focuses on using mathematical programming to solve large-scale industrial problems, employing in particular integer linear programming, column generation, and Lagrangian relaxations. These applications are implemented in part through the co-supervision of CIFRE PhD theses with industrial partners.
