A Cutting-Surface Theory for Mixed-Integer Conic Programs

Event Sponsor: 
Mathematics and Computing Science Seminar
Start Date: 
Jan 18 2016 - 10:30am
Building/Room: 
Building 240/Room 1406-1407
Location: 
Argonne National Laboratory
Speaker(s): 
Sercan Yildiz
Speaker(s) Title: 
Wilkinson Interviewee - MCS
Host: 
Sven Leyffer

Mixed-integer conic programming (MICP) is a natural generalization of conic programming and mixed-integer linear programming (MILP) where a linear objective function is optimized over the intersection of a regular--possibly nonlinear--cone with an affine subspace subject to integrality constraints. The combined modeling power of integer variables and conic constraints makes MICP an attractive modeling framework for optimization under uncertainty as well as engineering design and statistical learning. However, the development of practical solution methods for MICP remains a challenge.
 
In this talk, we discuss our recent developments in the design of algorithmic tools for MICP. Inspired by the pivotal role of disjunctive cutting-planes in the algorithmic advances for MILP, we develop the theory of disjunctive cutting-surfaces for mixed-integer second order cone programming (MISOCP). To this end, we consider two-term disjunctions on the second-order cone and its affine cross-sections. The resulting nonconvex sets are of fundamental importance in MISOCP where they can be used to derive valid inequalities that strengthen the problem formulation. We identify the cases where the convex hull of the disjunction can be completely characterized with a single second-order conic inequality, allowing efficient computation with second-order cone programming in a cutting-surface algorithm framework. This talk is based on joint works with Fatma Kilinc-Karzan and Gerard Cornuejols.