期刊
INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2016
卷 9682, 期 -, 页码 102-113出版社
SPRINGER INTERNATIONAL PUBLISHING AG
DOI: 10.1007/978-3-319-33461-5_9
关键词
-
类别
资金
- Div Of Civil, Mechanical, & Manufact Inn
- Directorate For Engineering [1351619] Funding Source: National Science Foundation
We present a unifying framework for generating extended formulations for the polyhedral outer approximations used in algorithms for mixed-integer convex programming (MICP). Extended formulations lead to fewer iterations of outer approximation algorithms and generally faster solution times. First, we observe that all MICP instances from the MINLPLIB2 benchmark library are conic representable with standard symmetric and nonsymmetric cones. Conic reformulations are shown to be effective extended formulations themselves because they encode separability structure. For mixed-integer conic-representable problems, we provide the first outer approximation algorithm with finite-time convergence guarantees, opening a path for the use of conic solvers for continuous relaxations. We then connect the popular modeling framework of disciplined convex programming (DCP) to the existence of extended formulations independent of conic representability. We present evidence that our approach can yield significant gains in practice, with the solution of a number of open instances from the MINLPLIB2 benchmark library.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据