Mixed-Integer Conic Linear Programming: Challenges and Perspectives
Final rept. 1 Aug 2010-31 Jul 2013
LEHIGH UNIV BETHLEHEM PA
Pagination or Media Count:
Fundamental Disjunctive Conic Cut DCC methodology for Mixed-Integer Conic Linear Optimization MICO was developed. To describe the convex hull of the intersection of a convex set E and a linear disjunction is the fundamental problem, and that served as the core of solution techniques for MICO. It was proved that if there exists a cone K that has the same intersection with the boundary of the disjunction as the convex set E, then the convex hull of the disjunction is the intersection of E with K. While uniqueness of a DCC is proved for general MICO, the existence of such a cone is difficult to prove for the general case. Thorough analysis of a parametric family of quadrics allows to prove the existence and uniqueness of a second order cone, when E is the intersection of an affine space and a second order cone. An efficiently computable method was developed for finding that cone, which provided novel and powerful DCCs for Mixed Integer Second Order Cone Optimization MISOCO, which can be used in branch-and-cut algorithms when solving MISOCO problems. All special and degenerate cases are carefully analyzed and easy to compute criteria are developed to compute a DCC for all cases. Limited, but rigorous computational experiments gave strong indication of the power of the DCCs.
- Operations Research