Between steps: Intermediate relaxations between big-M and convex hull formulations
This work addresses optimization challenges in fields like machine learning and operations research by offering a trade-off between computational efficiency and solution accuracy, though it is incremental as it builds on existing big-M and convex hull formulations.
The paper tackles the problem of formulating relaxations for disjunctions in optimization, developing intermediate 'P-split' formulations that balance model size and relaxation strength, with computational results showing they provide strong outer approximations of the convex hull using fewer variables and constraints than extended convex hull formulations, giving significant computational advantages over big-M and convex hull methods.
This work develops a class of relaxations in between the big-M and convex hull formulations of disjunctions, drawing advantages from both. The proposed "P-split" formulations split convex additively separable constraints into P partitions and form the convex hull of the partitioned disjuncts. Parameter P represents the trade-off of model size vs. relaxation strength. We examine the novel formulations and prove that, under certain assumptions, the relaxations form a hierarchy starting from a big-M equivalent and converging to the convex hull. We computationally compare the proposed formulations to big-M and convex hull formulations on a test set including: K-means clustering, P_ball problems, and ReLU neural networks. The computational results show that the intermediate P-split formulations can form strong outer approximations of the convex hull with fewer variables and constraints than the extended convex hull formulations, giving significant computational advantages over both the big-M and convex hull.