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

Authors: Moustapha Diaby; Mark H. Karwan; Lei Sun

Addresses: OPIM Department, University of Connecticut, Storrs, CT 06268, USA ' Department of Industrial and Systems Engineering, SUNY at Buffalo, Amherst, NY 14260, USA ' Department of Industrial and Systems Engineering, SUNY at Buffalo, Amherst, NY 14260, USA

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.

DOI: 10.1504/IJOR.2021.113505

International Journal of Operational Research, 2021 Vol.40 No.2, pp.261 - 278

Received: 20 May 2017
Accepted: 29 May 2018
Published online: 09 Mar 2021 *

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