Retour aux activités
Séminaire du GERAD

Cutting planes for mixed-integer conic programming

iCalendar

20 sept. 2019   11h00 — 12h00

Mathieu Tanneau Polytechnique Montréal, Canada

Mixed-integer conic problems are optimization problems with non-linear convex constraints represented through conic sets, and integer variables. This work is a first step towards the systematic integration of cutting-plane technology in optimization algorithms and solvers for MICP problems.

We investigate the separation of disjunctive cuts for mixed-integer conic problems. Our analysis builds on conic duality, and provides a number of geometrical insights on the separation of cuts in a non-linear setting. First, we formulate a cut-generating conic program (CGCP) that identifies a violated cut or proves that none exist. This naturally extends cut-generating linear programs from the MILP literature. Second, we study the importance of the normalization condition in CGCP, particularly its impact on duality failures. The latter exposes challenges that are specific to non-linear settings. Third, we investigate how disjunctive cuts can be strengthened, and propose a geometric approach which, in a linear setting, reduces to the classical monoidal strengthening of Balas and Jeroslow. Finally, we report preliminary results on the strength of lift-and-project cuts on a number of instances from the CBLIB library. This approach is compared to generating linear cuts with a state-of-the-art MILP solver from an initial polyhedral relaxation of the problem.

Andrea Lodi responsable

Lieu

Salle 4488
Pavillon André-Aisenstadt
Campus de l'Université de Montréal
2920, chemin de la Tour
Montréal QC H3T 1J4
Canada

Organisme associé

Axes de recherche

Applications de recherche