Binary Extended Formulations
From MaRDI portal
Abstract: We analyze different ways of constructing binary extended formulations of mixed-integer problems with bounded integer variables and compare their relative strength with respect to split cuts. We show that among all binary extended formulations where each bounded integer variable is represented by a distinct collection of binary variables, what we call "unimodular" extended formulations are the strongest. We also compare the strength of some binary extended formulations from the literature. Finally, we study the behavior of branch-and-bound on such extended formulations and show that branching on the new binary variables leads to significantly smaller enumeration trees in some cases.
This page was built for publication: Binary Extended Formulations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6295997)
