Francois Margot
Most of my research is related to Integer Linear Programming (ILP) problems.
If you have no idea what this means and have some time on your hands, you
might want to look at this introduction to ILP.
I am also working on Mixed Integer Non Linear Programming
(MINLP)
in a joint project IBM-CMU.
- 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. Examples are:
- 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.
- Branch-and-cut: Design and implementation of an
efficient Branch-and-Cut for Combinatorial problems (Steiner Trees, Single
Machine Scheduling, egde coloring of graphs a.o.).
For general (0, 1) integer linear programs: study of new cut generation
procedures and new heuristics for finding good feasible solutions.
Study of highly symmetric (0,1)-ILP problems and use of isomorphisms
in implicit enumerations.
- 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
- the full dimensional cells in an arrangement
- minimally non ideal matrices
- the k best solutions of a ratio problem on the hypercube.
Back to main page