On linear programming formulations for the TSP polytope

Next week I am planning to give a talk on our recent paper which is joint work with Samuel Fiorini, Serge Massar, Hans Raj Tiwary, and Ronald de Wolf where we consider linear and semidefinite extended formulations and we prove that any linear programming formulation of the traveling salesman polytope has super-polynomial size (independent of P-vs-NP). From the abstract:

We solve a 20-year old problem posed by M. Yannakakis and prove that there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the maximum cut problem and the stable set problem. These results follow from a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs.

The history of this problem is quite interested. From Gerd Woeginger’s P-versus-NP page (See also Mike Trick’s blog post on Swart’s attempts):

In 1986/87 Ted Swart (University of Guelph) wrote a number of papers (some of them had the title: “P=NP”) that gave linear programming formulations of polynomial size for the Hamiltonian cycle problem. Since linear programming is polynomially solvable and Hamiltonian cycle is NP-hard, Swart deduced that P=NP.

In 1988, Mihalis Yannakakis closed the discussion with his paper “Expressing combinatorial optimization problems by linear programs” (Proceedings of STOC 1988, pp. 223-228). Yannakakis proved that expressing the traveling salesman problem by a symmetric linear program (as in Swart’s approach) requires exponential size. The journal version of this paper has been published in Journal of Computer and System Sciences 43, 1991, pp. 441-466.

In his paper, Yannakakis posed the question whether one can show such a lower bound unconditionally, i.e., without the symmetry assumption and Yannakakis conjectured that symmetry ‘should not help much’. This sounded reasonable however no proof was known. In 2010, to the surprise of many, Kaibel, Pashkovich, and Theis proved that there exist polytopes whose symmetric extension complexity (the number of facets of the polytope) is super-polynomial, whereas there exists asymmetric extended formulations that use only polynomially many inequalities; i.e., symmetry does matter. On top of that, the considered polytopes were closely related to the matching polytope (used by Yannakakis to establish the TSP result) which rekindled the discussion on the (unconditional) extension complexity of the travelling salesman polytope and Kaibel asked whether 0/1-polytopes have extended formulations with a polynomial number of inequalities in general or if there exist 0/1-polytopes that need a super-polynomial number of facets in any extension. Beware! This is not in contradiction or related to the P-vs.-NP question as we only talk about the number of inequalities and not the encoding length of the coefficients. This was settled by Rothvoss in 2011 by a very nice counting argument: there are 0/1-polytopes that need a super-polynomial number of inequalities in any extension.

To make the following slightly more formal, let ${P \subseteq {\mathbb R}^n}$ be a polytope (of some dimension). Then an extended formulation for ${P}$ is another polytope ${Q \subseteq {\mathbb R}^\ell}$ such that there exists a linear projection ${\pi}$ with ${\pi(Q) = P}$ . The size of an extension ${Q}$ is now the number of facets of ${Q}$ and the extension complexity of ${P}$ (denoted by: ${\text{xc}(P)}$ ) is the minimum ${\ell}$ such that there exists an extension of size ${\ell}$ . We are interested in ${\text{xc}(P)}$ where ${P}$ is the travelling salesman polytope. Our proof heavily relies on a connection between the extension complexity of a polytope and communication complexity (the basic connection was made by Yannakakis and it was later extended by Faenza, Fiorini, Grappe, and Tiwary and Fiorini, Kaibel, Pashkovich, Theis in 2011). In fact, suppose that we have an inner and outer description of our polytope ${P}$ , say ${P = \text{conv}\{v_1, \dots v_n\} = \{x \in {\mathbb R}^n \mid Ax \leq b\}}$ . Then we can define the slack matrix ${S(P)}$ as ${S_{ij} = b_i -A_i v_j}$ , i.e., the slack of the vertices with respect to the inequalities. The extension complexity of a polytope is now equal to the nonnegative rank of ${S}$ which is essentially equivalent to determining the best protocol to compute the entries of ${S}$ in expectation (Alice gets a row index and Bob a column index). The latter can be bounded from below by the non-deterministic communication complexity and we use a certain matrix ${M_{ab} = (1-a^Tb)^2}$ which has large non-deterministic communication complexity (see de Wolf 2003). This matrix is special as it constitutes the slack for some valid inequalities for the correlation polytope which eventually leads to a exponential lower bound for the extension complexity of the correlation polytope. The latter is affine isomorphic to the cut polytope. Then via a reduction-like mechanism similar lower bounds are established for the stable set polytope ( ${\text{xc(stableSet)} = 2^{\Omega(n^{1/2})}}$ ) for a certain family of graphs and then we use the fact that the TSP polytope contains any stable set polytope as a face (Yannakakis) for suitably chosen parameters and we obtain ${\text{xc(TSP)} = 2^{\Omega(n^{1/4})}}$ .

Here are the slides:

Written by Sebastian

January 5, 2012 at 3:17 pm

Posted in Announcements, mathematics, Talks

14 Responses

Subscribe to comments with RSS.

Awesome. I can’t wait to see the talk. Although I think you’ll make the rest of us look bad. 🙂

Jeff Linderoth

January 5, 2012 at 8:04 pm

Reply
[…] programming formulation (symmetric or not) of the TSP is exponentially sized. Sebastian’s blog post has a very nice description of some recent history (including the astonishing result that sometimes […]

Michael Trick’s Operations Research Blog : Super Exciting News on Super Polynomiality of LP Formulations of the TSP Polytope

January 5, 2012 at 9:20 pm

Reply
Nice Article…

thanks for share..

adi saputra

January 6, 2012 at 8:57 am

Reply
Congratulations, Sebastian!

Jakub Marecek

January 6, 2012 at 12:57 pm

Reply
Cool result. Us poor operations research people are confused about the relationship between this result and the fact that linear programming is P-complete. See the discussion at http://mat.tepper.cmu.edu/blog/?p=1587 . In short: Intro states: “Therefore, it is impossible to prove P = NP by giving a polynomial-size LP for any of these problems.” But LP is P-complete so how they can prove “there are no polynomial-size LPs for TSP” without also proving P != NP or NP not in P/poly?

What aspect are we missing (see the full thread for more confused aspects)?

Michael Trick (@miketrick)

January 7, 2012 at 8:28 am

Reply
- Our result does not imply P != NP ! The reason for this, on a slightly imprecise level, is the following. The TSP-polytope itself does not “constitute” a decision problem and NP and P are _only_ about decision problem; a polynomial time computation is formally not necessary in P although we often sloppily say so. Now HC is about testing whether a graph contains a Hamiltonian Cycle. In order to decide HC with the TSP polytope we need to
  
  a) either assign high costs to the edges that are not in our graph of consideration and add a objective function cut to the TSP polytope so that the threshold separates between tours only using edges that are in our graph and the rest (when optimizing),
  b) or we could fix edge variables to 0.
  
  Both cases are equivalent as what we really have to do is to consider an appropriate face of the TSP polytope that corresponds to our graph. This is however a different polytope and we do not make a statement about this one.
  
  So if you would have a poly-size LP for the TSP then you can also decide HC. However the converse does not hold necessarily.
  
  I hope this clarifies the question?
  
  Sebastian
  
  January 7, 2012 at 5:43 pm
  
  Reply
Nice article.

The question has come up in a discussion on Mike Trick’s blog: Does this result imply that P!=NP? If not, why not?

Thanks.

Matthew Saltzman

January 7, 2012 at 4:51 pm

Reply
- see above – reply to Mike’s question.
  
  Sebastian
  
  January 7, 2012 at 5:44 pm
  
  Reply
The answer kinda helps, though I think I am missing something fundamental. Here is the logic presented:

(1) Liner Programming is P complete,

(2) Therefore every problem in P has a polynomial-sized linear programming formulation, but

(3) The Traveling Salesman problem has no polynomial-sized linear programming formulation, so

(4) The TSP is not in P

One of these steps is wrong.Which is it? I suspect it is (2), but I can’t tease out the answer from your response.

Michael Trick

January 7, 2012 at 8:27 pm

Reply
- I assume that by “the TSP” we mean the problem of, given a weight vector w on a complete graph, compute the tour with minimal cost.
  
  The problem is that the TSP problem is neither in P nor in NP because it is not a decision problem – (4) is not a consequence of (3) but (4) always holds. We have to ask a question to make it a decision problem: Given a weight vector w does there exists a tour of costs at most k? Then we have a “decision version” of the TSP which is NP-complete by a reduction from HC. In the polyhedral setting this means that we cut the TSP polytope with an objective function cut. We have
  
  1) the TSP polytope has no poly-size LP formulation
  2) however, for the TSP polytope with an obj cut we don’t know.
  
  Sebastian
  
  January 10, 2012 at 8:14 am
  
  Reply
  - While this is definitely one reason why your (very nice!) result does not prove P \neq NP, I think there is an even more elementary and more serious issue.
    
    Note first that the P-completeness of LP is irrelevant here. Under polynomial time reductions every problem in P is (trivially) P-complete. LP is P-complete under logspace reductions and that is relevant only if our goal was to show that some problem is unlikely to be in NC^{i} for some constant i.
    
    Leaving that aside, I claim that even if you could prove that the TSP polytope with an objective cut does not have a poly-size LP formulation for any non-trivial objective cut, that would still not prove P \neq NP. It’s a simple quantifier issue:
    
    * P-completeness of LP means: if (a decision version of) TSP is in P, then there exists a polynomial time algorithm M s.t. for every instance (G, k) of TSP, M(G, k) outputs a linear program P which is feasible if and only if the smallest TSP tour of G has value at most k.
    
    So this says that for every yes-instance of the TSP problem we can find some feasible polysize LP formulation. But that is trivial. We could just take the supposed polytime algorithm for TSP and let it output {x: 0<= x <= 1} on yes instances and {x: 0<= x; x <= -1} on no instances. To make it even more trivial, Michael's argument does not even take uniformity into consideration, i.e. the argument does not mention that all LPs need to be generated by the same polytime algorithm.
    
    * A result like yours shows that no *single* LP formulation solves *all* TSP instances. Even if you could prove that adding an objective cut does not lead to the existence of a polysize LP formulation, that would still not be enough: you would be just showing that we cannot solve TSP by starting from a *single* TSP LP formulation and adding objective cuts to it.
    
    In other words, P completeness means "for all instances there exist an equivalent polysize LP formulation" (which is trivial). The negation of this would be "there exists an instance for which we cannot find any equivalent LP formulation" (which is trivially false). A result like yours says "for all LP formulations there exists an instance that is not solved by it" (which is awesome!).
    
    Sasho
    
    August 4, 2012 at 8:35 pm
  - Hi Sasho, thanks for your nice comment. Yes indeed – there many more problems when trying to go from our result to P \neq NP. It is exactly as you say, our result implies that for all small LP formulations there exists an instance that cannot be solved by it (here in the optimization sense first). Also as you pointed out, here we are talking about a “single” LP and about directly solving it. We are not talking about potential sequences of LPs or separation that uses an LP. I think one has to take the result really at face value and every “consequence” one might think it implies has to be extremely carefully checked.
    
    Sebastian
    
    August 5, 2012 at 8:57 am
[…] On linear programming formulations for the TSP polytope (spokutta.wordpress.com) […]

A geek with a hat » Minimum substring cover problem

May 13, 2012 at 2:51 am

Reply
[…] assumption). Just last year, it was finally shown that Yannakakis’ technical assumption is not needed; there is no CEF for the traveling salesman problem. These papers are fascinating on their own, but […]

2013: The year of (nonexistent) extended formulations | Farkas' Dilemma

December 30, 2013 at 7:07 pm

Reply

Sebastian Pokutta's Blog