Research
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.
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 W4-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 eT x | A x >= 1, x in {0, 1}n} = {max yT 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