On modelling hard combinatorial optimisation problems as linear programs: refutations of the 'unconditional impossibility' claims

Moustapha Diaby, Mark H. Karwan and Lei Sun

International Journal of Operational Research, 2021, vol. 40, issue 2, 261-278

Abstract: There has been a series of developments in the recent literature (by essentially a same 'circle' of authors) with the absolute/unconditioned (implicit or explicit) claim that there exists no abstraction of an NP-complete combinatorial optimisation problem in which the defining combinatorial configurations [such as 'tours' in the case of the travelling salesman problem (TSP) for example] can be modelled by a polynomial-sized system of linear constraints. The purpose of this paper is to provide general as well as specific refutations for these recent claims.

Keywords: linear programming; combinatorial optimisation; computational complexity; travelling salesman problem; TSP; P vs. NP . (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=113505 (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:ijores:v:40:y:2021:i:2:p:261-278

Access Statistics for this article

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