A combinatorial optimization problem consists in determining a best solution among a discrete set of solutions, called feasible solutions. In general, such a set is finite but huge, and is described implicitly, i.e., by means of a list of constraints that any feasible solution must satisfy. In order to formalize the notion of a best solution, some function, called the objective function, is considered. It associates a real value to each solution, and a best, or optimal, solution, is then a feasible solution minimizing or maximizing this objective function. In particular, combinatorial optimization deals with practical problems such as optimizing the design and operating of production systems, or, more generally, optimizing the decision making process of a company.
The research work carried out in the Combinatorial optimization (OC) team covers two main topics: Mathematical programming and applications and Graphs and optimization.
« Mathematical programming and applications »
This topic is essentially about discrete optimization (either linear or non linear). This kind of very general models can be used to formulate almost every single combinatorial optimization problem. Such problems are generally hard to solve, and, in many cases, only small ones can be solved efficiently. The researchers of the OC team that work on this topic aim at acquiring a better understanding of these problems, in order to be able to solve them more efficiently. They are also interested in solving efficiently practical optimization problems related to different fields: telecommunications, transport, energy, environment, etc. Finally, another aspect of interest is the one of finding robust optimal solutions for such problems. Indeed, in an industrial setting, it is usually more relevant to look for a “robust” solution, which will perform rather well in any possible situation, instead of looking for an “optimal” one for a very specific case. The OC team has already worked on the problem of computing such solutions, as the notion of robustness is a very rich and useful one.
« Graphs and optimization »
Graphs are mathematical tools which play a central role in Operational Research. They can be used to model various types of systems. Finding an optimal solution then generally consists in identifying an optimal structure in a graph. Because of the sizes of the associated real instances, even a powerful computer is not sufficient to provide an optimal solution within a reasonable amount of time. In order to make such a solution easier to find, one often needs to prove structural properties of optimal solutions, and then, whenever this is possible, use them to design efficient algorithms to solve the problem, either exactly, or approximately. The researchers of the OC team that work on this topic aim at applying this approach to some graph optimization problems, that are general enough to model many real-life situations. They are also interested in approximation algorithms, parameterized algorithms, and online algorithms.