2023/04/16 by Diaby, Moustapha, Karwan, Mark, Sun, Lei
#90-08 #90-10 #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2 #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2304.07716
In view of the extended formulations (EFs) developments (e.g. "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"), we focus in this paper on the question of whether it is possible to model an NP-Complete problem as a polynomial-sized linear program. For the sake of simplicity of exposition, the discussions are focused on the TSP. We show that a finding that there exists no polynomial-sized extended formulation of "the TSP polytope" does not (necessarily) imply that it is "impossible" for a polynomial-sized linear program to solve the TSP optimization problem. We show that under appropriate conditions the TSP optimization problem can be solved without recourse to the traditional city-to-city ("travel leg") variables, thereby side-stepping/"escaping from" "the TSP polytope" and hence, the barriers. Some illustrative examples are discussed.