Polyhedra and Convex Hulls
I study polyhedra arising from combinatorial optimization problems. My research aims to describe the convex hull of solutions via a system of linear inequalities. These inequalities can then be used in exact resolution algorithms to tighten bounds and drastically reduce solving times.
A central question is determining under what conditions a system of inequalities defines an integral polyhedron—that is, a polyhedron all of whose vertices have integer coordinates. This property is crucial, since finding an integer solution that satisfies the system's inequalities while maximizing a linear function then reduces to solving a linear program in continuous variables, which is polynomial-time solvable (provided the system's constraints can be separated in polynomial time). The property of (box-)total dual integrality generally provides a sufficient condition for a system to define such an integral polyhedron. My research focuses on characterizing the conditions under which linear systems are (box-)totally dual integral.
Efficient Algorithms
I develop algorithms for solving large-scale combinatorial optimization problems. The efficiency of these algorithms depends heavily on how the problem is formulated. Indeed, a single problem often admits many mixed-integer linear programming formulations, and the choice of formulation dramatically affects the efficiency of the resolution algorithm.
Likewise, a single mixed-integer linear problem can be solved by multiple algorithms. I work on adding valid inequalities to strengthen the linear relaxation, yielding better bounds and reducing the solution space to be explored. I also develop algorithms based on decomposing the problem into subproblems linked by linear constraints.
Machine Learning for Mixed-Integer Linear Programming
I work on using machine learning to improve exact solvers for mixed-integer linear programming problems. Although these algorithms are exact, they rely on numerous heuristic components (such as primal heuristics for finding high-quality feasible solutions), whose efficiency greatly impacts the overall performance of the exact algorithm. The idea is to use machine learning to specialize these heuristics for specific problem classes by leveraging data from previously solved instances of the same type.
My work focuses in particular on predicting dual solutions for Lagrangian relaxation, which yields dual bounds and thereby accelerates the resolution of mixed-integer linear programming problems.
