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.
| Original language | English |
|---|---|
| Pages (from-to) | 261-278 |
| Number of pages | 18 |
| Journal | International Journal of Operational Research |
| Volume | 40 |
| Issue number | 2 |
| DOIs | |
| State | Published - 2021 |
Keywords
- Combinatorial optimisation
- Computational complexity
- Linear programming
- P vs. NP
- Travelling salesman problem
- TSP
Fingerprint
Dive into the research topics of 'On modelling hard combinatorial optimisation problems as linear programs: Refutations of the 'unconditional impossibility' claims'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver