Limits to the scope of applicability of extended formulations theory for LP models of combinatorial optimisation problems

Moustapha Diaby and Mark H. Karwan

International Journal of Mathematics in Operational Research, 2017, vol. 10, issue 1, 18-33

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. (search for similar items in EconPapers)
Date: 2017
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=80739 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijmore:v:10:y:2017:i:1:p:18-33

Access Statistics for this article

More articles in International Journal of Mathematics in Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().