A Combinatorial Approach for Small and Strong Formulations of Disjunctive Constraints

• 成果类型: Article
• 署名作者: Huchette, Joey; Vielma, Juan Pablo
• 署名单位: Rice University; Massachusetts Institute of Technology (MIT)
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2018.0946
• 发表日期: 2019
• 页码: 793-820
• 关键词: mixed-integer models; branch-and-cut; global optimization; base-2 expansions; binary variables; algorithm; nonconvex; relaxations; PROGRAMS; logic

摘要

A framework is presented for constructing strong mixed-integer programming formulations for logical disjunctive constraints. This approach is a generalization of the logarithmically sized formulations of Vielma and Nemhauser for special ordered sets of type 2 (SOS2) constraints, and a complete characterization of its expressive power is offered. The framework is applied to a variety of disjunctive constraints, producing novel small and strong formulations for outer approximations of multilinear terms, generalizations of special ordered sets, piecewise linear functions over a variety of domains, and obstacle avoidance constraints.