Title: Limits to the scope of applicability of extended formulations theory for LP models of combinatorial optimisation problems
Authors: Moustapha Diaby; Mark H. Karwan
Addresses: OPIM Department, University of Connecticut, Storrs, CT 06268, USA ' Department of Industrial and Systems Engineering, University at Buffalo – The State University of New York, Buffalo, NY 14260, USA
Abstract: The purpose of this paper is to bring to attention and to make a contribution to the issue of defining/clarifying the scope of applicability of extended formulations (EFs) theory. Specifically, we show that EFs theory is not valid for relating the sizes of descriptions of polytopes when the sets of the descriptive variables for those polytopes are disjoint, and that new definitions of the notion of 'projection' upon which some of the recent extended formulations works [such as Kaibel (2011), Fiorini et al. (2011, 2012a, 2012b, 2013), Faenza et al. (2012), Gillis and Glineur (2012) and Kaibel and Walter (2014), for example] have been based can cause those works to over-reach in their conclusions.
Keywords: extended formulations theory; combinatorial optimisation; computational complexity; linear programming; polytopes.
DOI: 10.1504/IJMOR.2017.080739
International Journal of Mathematics in Operational Research, 2017 Vol.10 No.1, pp.18 - 33
Received: 12 Nov 2014
Accepted: 12 Feb 2015
Published online: 06 Dec 2016 *