### Mixed Integer Linear Programming:

- Branch-and-cut: Design and implementation of efficient Branch-and-cut algorithms for combinatorial problems. Theoretical development and implementation of techniques using isomorphism for solving highly symmetric integer linear programs.
- Cut generation: Study of new cut generation procedures (intersection cuts, variants of Gomory Cuts). Development of testing procedures for cut generators.
- Heuristics: New heuristics for finding good feasible solutions.

### Mixed Integer Nonlinear Programming:

- Convex mixed integer nonlinear programs:
- Participation in the development of Bonmin, an Open Source software implementing a framework for outer-approximation algorithms, nonlinear branch-and-bound algorithms and hybrid algorithms.
- Development of a Feasible Pump heuristic.

- Nonconvex mixed integer nonlinear programs:
- Participation in the development of Couenne, an Open Source software implementing a framework for convexification and linearization.

- Convex mixed integer nonlinear programs:
### Stochastic Optimization:

Stochastic optimization is a very broad research area, and I am particularly interested in the problem of devising bounds on optimal solutions. It is an important practical task, as for many problems, it is possible to compare heuristic policies on the basis of a simulation of their performance, while it is difficult to assess how close to optimality these policies are.

- Approximate Linear Programming:
- I develop techniques to derive strong approximate linear programming formulations of stochastic problems. Applications in routing, natural gas storage, and finance.

- Chance Constrained Problems:
- I study reformulations of stochastic programs where some constraints have random coefficients and must be satisfied with a given probability. These problems are known as "stochastic programs with random technology matrix". These reformulations yield non-convex trilinear programs with a very specific structure. We study and implement algorithms to solve this type of problems. Applications in revenue management, energy, and health policy.

- Approximate Linear Programming:
### Polyhedral combinatorics:

- Polyhedral compositions: Study of basic operations that preserve integrality for polytopes. Interpretation in polyhedral terms of dynamic programming algorithms for solving combinatorial problems on families of graphs defined by compositions.
- Integral polyhedra: Complete linear programming formulations
for combinatorial problems: tree polytope, polytope of two disjoint
paths on 2-tree graphs, polytope of the 2-node-connected Steiner
subgraphs for W
_{4}-free graphs, polyhedron of weakly k-majorized vectors, polyhedron of min-up/min-down sequences. - Ideal matrices and packing matrices. Let A be an mxn (0,1) matrix.
A is ideal if the polyhedron {x | A x >= 1, x >= 0} is integral.
A packs if
{min e
^{T}x | A x >= 1, x in {0, 1}^{n}} = {max y^{T}e | y A <= 1, y in {0, 1}^{m}}. Ideal matrices are to covering systems the equivalent of perfect matrices to packing systems.

### Enumeration problems:

- Design of efficient algorithms, i.e. algorithm with worst-case complexity bounded by a polynomial in the input size and the output size. Examples are the enumeration of the vertices and faces of a polytope, of the full dimensional cells in an arrangement, of minimally non ideal matrices, of the k best solutions of a ratio problem on the hypercube.

Back to main page