Cutting planes for mixed-integer conic programming
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.
Lieu
Pavillon André-Aisenstadt
Campus de l'Université de Montréal
Montréal QC H3T 1J4
Canada