Embedding Formulations and Complexity for Unions of Polyhedra

• 成果类型: Article
• 署名作者: Vielmaa, Juan Pablo
• 署名单位: Massachusetts Institute of Technology (MIT)
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2017.2856
• 发表日期: 2018
• 页码: 4721-4734
• 关键词: integer programming; Mixed-Integer Programming; mixed-integer modeling; strong formulation; piecewise linear

摘要

It iswell known that selecting a good mixed-integer programming (MIP) formulation is crucial for effectively obtaining a solution with state-of-the art solvers. Although best practices and guidelines for constructing good formulations abound, there is rarely a single systematic construction approach that leads to the best possible formulation. Here, we introduce embedding formulations and complexity as a new MIP formulation paradigm for systematically constructing formulations for disjunctive constraints that are optimal with respect to size. More specifically, they yield the smallest possible ideal formulation (i.e., one whose LP relaxation has integral extreme points) among all formulations that only use 0-1 auxiliary variables. We use the paradigm to characterize optimal formulations for special ordered sets of type 2 and certain piecewise linear functions of two variables. We also show that the resultant formulations can provide a significant computational advantage over all known formulations for piecewise linear functions.