Partenaires

CNRS
Logo tutelle
Logo tutelle
Logo tutelle


Rechercher

Sur ce site

Sur le Web du CNRS


Accueil du site > Séminaires > Mathématiques des systèmes complexes > Mixed-integer rounding cutting planes for integer programming problems

Vendredi 19 janvier 2007 à 11h

Mixed-integer rounding cutting planes for integer programming problems

Sanjeeb Dash (Research Staff Member, New-York), sanjeebd@us.ibm.com

Résumé : Cutting planes, or linear inequalities satisfied by all integral points in a polyhedron, are very useful in solving integer programming problems. In this talk, we discuss two aspects of the most important class of general cutting planes, namely mixed-integer rounding (MIR) cutting planes. We describe recent results on the separation problem for MIR cutting planes - given a point contained in a polyhedron, test if there exists an MIR cutting plane violated by this point or prove that none exists - and discuss their use in solving integer programs. This is joint work with Oktay Gunluk, and Andrea Lodi. An important aspect of MIR cuts is the following : any integer program, and therefore any problem in NP, can be solved by generating a sequence of MIR cuts. We show that exponentially many MIR cuts are needed in the worst case.

Dans la même rubrique :