Extended Formulations for Advanced Mixed Integer Convex Optimization
Abstract
Mixed integer convex optimization (MICONV) combines the use of integer variables and convex constraints to model a wide range of pro"blems in electronics, chemical engineering, sustainability, design, logistics, finance and defense. It is the natural extension of b""oth convex optimization and mixed integer linear programming (MILP). Convex optimization is theoretically and practically tractable,"" and convex optimization problems can be readily solved by various methods. On the other hand, although theoretically hard MILP is r"outinely used to solve a wide range of practical problems thanks to advanced commercial solvers that include more than 50 years of theoretical and technical developments. While the combination of convex optimization and MILP techniques to solve MICONV problems is" straightforward, MICONVsolvers have historically been significantly less effective than their MILP and convex optimization counter""parts. However, we have recently reported on a substantial improvement in the effectiveness of general-purpose MICONVthanks to the"" use of so-called extended formulations. The objective of this project is to further develop theoretical, algorithmic and technical" results concerning such extended formulations to make MICONV as accessible and practical as MILP and convex optimization. A definin"g characteristic of extended formulations is the use of auxiliary variables, and in the context of MICONV wecan identify two subcla"sses of extended formulations. The first subclass uses some integer auxiliary variables to model logical conditions or the selection among alternative convex constraints. Such mixed integer programming (MIP)extended formulations are at the core of the modeling fl"exibility of MICONV. While there are many techniques to construct such extended MIP formulations, MICONV formulations are not nearly" as well understood as MILPformulations. In this project we will use tools from convex analysis and integer lattices to develop MICONV formulations that are amicable to solution with state-of-the-art MICONV algorithms. The second subclass of extended formulationsonly uses continuous auxiliary variables and corresponds to linear programming (LP) or nonlinear programming (NLP) extended formulations. Such extended LP/NLP formulations can be used to construct economical polyhedralapproximations of the convex constraints. In" turn, such approximations can be used to develop effective algorithms for MICONV, which solve a sequence of MILP and convex optimiz""ation problems. In this project we will use tools from MILP, convex optimization and convex analysis to improve and expand the appli"cability of a prototype algorithm with such characteristics. The resulting algorithm and associated modeling techniques should leadto an effective and accessible way to solve a wide range of MICONV problems including mixed integer semi-definite programming problems.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jan 23, 2018
- Source ID
- N000141812079
Entities
People
- Juan Pablo Vielma
Organizations
- Massachusetts Institute of Technology
- Office of Naval Research
- United States Navy