Ideal, non-extended formulations for disjunctive constraints admitting a network representation
成果类型：
Article
署名作者：
Kis, Tamas; Horvath, Marko
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-021-01652-z
发表日期：
2022
页码：
831-869
关键词：
摘要：
In this paper we reconsider a known technique for constructing strong MIP formulations for disjunctive constraints of the form x is an element of boolean OR(m)(i=1) P-i, where the (P)i are polytopes. The formulation is based on the Cayley Embedding of the union of polytopes, namely, Q := conv(boolean OR(m)(i=1) P-i x {epsilon(i)}), where epsilon(i) is the ith unit vector in R-m. Our main contribution is a full characterization of the facets of Q, provided it has a certain network representation. In the second half of the paper, we work-out a number of applications from the literature, e.g., special ordered sets of type 2, logical constraints, the cardinality indicating polytope, union of simplicies, etc., along with a more complex recent example. Furthermore, we describe a new formulation for piecewise linear functions defined on a grid triangulation of a rectangular region D subset of R-d using a logarithmic number of auxilirary variables in the number of gridpoints in D for any fixed d. The series of applications demonstrates the richness of the class of disjunctive constraints for which our method can be applied.