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 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article