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)) are those of Swart (1986; 1987). We do not know of any of the details of those models (and cannot, hence, cite the specific references), 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.
In our paper provided below on this page, 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.
Paper
Diaby, M., M.H. Karwan, and L. Sun (2023). On modeling NP-Complete problems as polynomial-sized linear programs: Escaping/Side-stepping the “barriers.”
Cited references
Burkard, R., M. Dell’Amico, and S. Martello (2009). Assignment Problems. SIAM (Philadelphia).
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.
Yannakakis, M. (1991). Expressing combinatorial optimization problems by linear programming. Journal of Computer and System Sciences 43:3, pp. 441-466.