Title: A Cutting-Surface Theory for Mixed-Integer Conic Programs
Date/Time: December 29, 2015 – 13:00 Tuesday
Place: FENS G032
Abstract: 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 Kılınç Karzan and Gerard Cornuejols.
Bio: Sercan Yıldız is a PhD candidate in Algorithms, Combinatorics, and Optimization in the Tepper School of Business of Carnegie Mellon University. Previously, he received a master's degree in Algorithms, Combinatorics, and Optimization from Carnegie Mellon University and master's and bachelor's degrees in Industrial Engineering from the University of Pittsburgh and Boğaziçi University, respectively. His research centers on operations research, with emphasis on the methodological and practical aspects of integer programming and non-convex optimization.