Imperial College London
Portrait Picture

ProfessorRuthMisener

Faculty of Engineering, Department of Computing

Professor in Computational Optimisation
 
 
 
//

Contact

 

+44 (0)20 7594 8315r.misener Website CV

 
 
//

Location

 

379Huxley BuildingSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@inproceedings{Kronqvist:2021,
author = {Kronqvist, J and Misener, R and Tsay, C},
publisher = {arXiv},
title = {Between steps: Intermediate relaxations between big-M and convex hull  formulations},
url = {http://arxiv.org/abs/2101.12708v1},
year = {2021}
}
Download

RIS format (EndNote, RefMan)

TY  - CPAPER
AB  - This work develops a class of relaxations in between the big-M and convexhull formulations of disjunctions, drawing advantages from both. The proposed"P-split" formulations split convex additively separable constraints into Ppartitions and form the convex hull of the partitioned disjuncts. Parameter Prepresents the trade-off of model size vs. relaxation strength. We examine thenovel formulations and prove that, under certain assumptions, the relaxationsform a hierarchy starting from a big-M equivalent and converging to the convexhull. We computationally compare the proposed formulations to big-M and convexhull formulations on a test set including: K-means clustering, P_ball problems,and ReLU neural networks. The computational results show that the intermediateP-split formulations can form strong outer approximations of the convex hullwith fewer variables and constraints than the extended convex hullformulations, giving significant computational advantages over both the big-Mand convex hull.
AU  - Kronqvist,J
AU  - Misener,R
AU  - Tsay,C
PB  - arXiv
PY  - 2021///
TI  - Between steps: Intermediate relaxations between big-M and convex hull  formulations
UR  - http://arxiv.org/abs/2101.12708v1
UR  - http://hdl.handle.net/10044/1/86869
ER  -
Download