Back to activities
GERAD seminar

Cutting planes for mixed-integer conic programming

iCalendar

Sep 20, 2019   11:00 AM — 12:00 PM

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 organizer

Location

Room 4488
André-Aisenstadt Building
Université de Montréal Campus
2920, chemin de la Tour Montréal QC H3T 1J4 Canada

Associated organization

Research Axes

Research applications