As far as we know, the first polynomial-sized LP models to be proposed for an NP-Complete problem (specifically, the traveling salesman problem (TSP); see Lawler et al. (1985)) are those of Swart (1986; 1987). We do not know of any of the details of those models, but the concensus of the research communities was that their validities were refuted by developments in Yannakakis (1991). The essence of those developments is the showing that “the TSP polytope” does not have a polynomial-sized extended formulation (EF) which is symmetric (Yannakakis (1991)). By “the TSP polytope” it is meant the polytope described using the standard or traditional city-to-city (travel leg) variables (see our 2023 refutation paper below; or Lawler et al. (1985)) .
Over the past decade, some authors have focused on removing the symmetry condition of Yannakakis (1991). In particular, the claim in Fiorini et al. (2011; 2012) is that the traveling salesman and stable set polytopes in the spaces in their natural variables do not have polynomial-sized EFs, regardless of the symmetry condition of Yannakakis (1991). More recently, others (typified by Fiorini et al. (2015), in particular) have made the (implicit or explicit) absolute/unconditioned claim that there exists no abstraction of an NP-Complete COP in which the defining combinatorial configurations (such as “tours” in the case of the TSP for example) can be modeled by a polynomial-sized system of linear constraints. Refutations of these latter claims are given in the three “refutation papers” provided below, on this page.
The aim in the earlier ones of these papers (2017; 2021) was to provide general explanations of why the existing negative extended formulations (EF) results for “the TSP polytope” are not applicable to our developments. We show that the reasons for that non-applicability are the same as those for the case of Martin (1991)’s formulation of the MSTP as it relates to Edmonds’ formulation of the MSTP. Also, Yannakakis (1991, pp. 444-445) discusses the fact that Edmonds (1970)’s formulation of the Minimum Spanning Tree Problem (MSTP) is of exponential size (due to its having “TSP subtour elimination”-like constraints), while Martin (1991)’s formulation which includes Edmonds’ variables (and hence, can be viewed as an extended formulation of Edmonds’ model) is of polynomial size. This fact has been generally considered in the EF literature as an unexplained paradox. A contribution of these earlier (2017; 2021) papers is that they explain this paradox.
The most recent (2023) of the “refutation papers” is much more specific and direct. In it, we show (in theory and with illustrative examples) that provided an EF (polynomial-sized or not) of the Linear Assignment Problem (LAP) polytope (see Burkhard et al. (2009)) is exact and that TSP tour costs can be accurately accounted through linear functions of its descriptive variables, that EF (of the LAP polytope) allows for the solution of the TSP optimization problem, irrespective of whether a further EF of it in the space of the travel leg descriptive variables of “the TSP polytope” projects to “the TSP polytope” or not. Since the feasibility of these conditions for the LAP polytope is not ruled out by any existing result, this means that a finding that “the TSP polytope” does not have an exact polynomial-sized EF does not imply that it is “impossible” for a linear program (polynomial-sized or not) to solve the TSP optimization problem. Part of the issue in this regard is what should/should not be considered a meaningful EF when attempting to make inferences about model sizes, as explained in our 2017 “refutation paper.”
Refutation papers
Diaby, M., M.H. Karwan, and L. Sun (2023). On modeling NP-Complete problems as polynomial-sized linear programs: Escaping/Side-stepping the “barriers.
Diaby, M., M.H. Karwan, and L. Sun (2021). On modeling hard combinatorial optimization problems as linear programs: Refutations of the “unconditional impossibility” claims. International Journal of Operational Research 40:2, pp. 261-278.
Diaby, M. and M.H. Karwan (2017). Limits to the scope of applicability of extended formulations theory for LP models of combinatorial optimization problems. International Journal of Mathematics in Operational Research 10:1, pp. 18-33.
Cited references
Burkard, R., M. Dell’Amico, and S. Martello (2009). Assignment Problems. SIAM (Philadelphia).
Edmonds, J. (1970) “Submodular functions, matroids and certain polyhedra”, in R.K Guy et al. (Eds.): Combinatorial Structures and Their Applications, pp.69–87, Gordon and Breach, New York.
Fiorini, S., S. Massar, S. Pokutta, H.R. Tiwary, and R. de Wolf (2011). Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Bounds. Unpublished (Available at: http://arxiv.org/pdf/1111.0837.pdf).
Fiorini, S., S. Massar, S. Pokutta, H.R. Tiwary, and R. de Wolf (2012). Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Bounds. Proceedings of the 44th ACM Symposium on the Theory of Computing (STOC ’12), New York, NY, pp. 95-106.
Fiorini, S., S. Massar, S. Pokutta, H.R. Tiwary, and R. de Wolf (2015). Exponential Lower Bounds for Polytopes in Combinatorial Optimization. Journal of the ACM 62:2, Article No. 17.
Martin, R.K. (1991) Using separation algorithms to generate mixed integer model reformulations. Operations Research Letters 10:3, pp.119–128.
Yannakakis, M. (1991). Expressing combinatorial optimization problems by linear programming. Journal of Computer and System Sciences 43:3, pp. 441-466.