10
$\begingroup$

For the branch-and-cut method, it is essential to know many facets of the polytopes generated by the problem. However, it is currently one of the hardest problems to actually calculate all facets of such polytopes as they rapidly grow in size.

For an arbitrary optimization problem, the polytope used by branch-and-cut or also by cutting-plane-methods is the convex hull of all feasible vertices. A vertex is an assignment of all variables of the model. As a (very simple) example: if one would maximize $2\cdot x+y$ s.t. $x+y \leq 1$ and $0\leq x,y\leq 1.5$ then the vertices $(0,0)$, $(0,1)$ and $(1,0)$ are feasible vertices. $(1,1)$ violates the inequality $x+y\leq 1.5$ and is therefore not feasible. The (combinatorical) optimization problem would be to choose among the feasible vertices. (In this case, obviously $(1,0)$ is the optimum). The convex hull of these vertices is the triangle with exactly these three vertices. The facets of this simple polytope are $x\geq0$, $y\geq 0$ and $x+y\leq 1$. Note that the description through facets is more accurate than the model. In most hard problems - such as the TSP - the number of facets exceeds the number of model inequalities by several orders of magnitude.

Considering the Travelling Salesman Problem, for which number of nodes is the polytope fully known and how much facets are there. if it is not complete, what are lower bounds on the number of facets?

I'm particularly interested in the so-called hamiltonian path formulation of the TSP:

$$min \sum_{i=0}^{n-1}(\sum_{j=0}^{i-1}c_{i,j}\cdot x_{i,j}+\sum_{j=i+1}^{n-1}c_{i,j}\cdot x_{i,j})$$ s.t.

$$\forall i \neq j:\ \ 0 \leq x_{i,j}\leq 1$$ $$\forall i \neq j\ \ \ x_{i,j}+x_{j,i}\leq 1$$ $$\forall j \ \ \sum_{i=0}^{j-1}x_{i,j}+\sum_{i=j+1}^{n-1}x_{i,j}\leq 1$$ $$\forall j \ \ \sum_{i=0}^{j-1}x_{j,i}+\sum_{i=j+1}^{n-1}x_{j,i}\leq 1$$ $$\sum_{i=0}^{n-1}(\sum_{j=0}^{i-1}x_{i,j}+\sum_{j=i+1}^{n-1}x_{i,j})=n-1$$

If you have any information about polytopes of other formulations of the TSP, feel free to share that too.

Improve this question
$\endgroup$
6
  • $\begingroup$ Personally, I am not sure what "polytopes of a problem" means. But then, I have little background in complexity theory. $\endgroup$
    – Raphael ♦
    Sep 1, 2012 at 22:33
  • $\begingroup$ It's not actually complexity theory (it wasn't me tagging this tag). Actually there is no suitable tag for this kind of question yet. A suitable tag would be branch-and-cut or cutting-plane-method. I will add some information about what polytope I'm talking about shortly $\endgroup$
    – stefan
    Sep 1, 2012 at 22:35
  • 1
    $\begingroup$ @Raphael: I've updated the question, so you can read something about facets and polytopes. $\endgroup$
    – stefan
    Sep 1, 2012 at 22:46
  • 1
    $\begingroup$ @stean: Ah, so it's just the space of feasible solutions. In that case, the search of TSP is clearly exponential in size; otherwise we'd had P=NP ages ago. Even more, TSP is usually defined on undirected, complete graphs, so there are exactly $n!$ feasible solutions. So I don't see what else you are looking for; maybe I don't get an important detail of your question. Maybe that you have written down the relaxed LP, not the IP? $\endgroup$
    – Raphael ♦
    Sep 2, 2012 at 13:24
  • 1
    $\begingroup$ @Raphael it's the convex hull of feasible solutions. you are right that unless P=NP this convex hull will have exponentially many facets. however, the number of vertices has nothing to do with that: the convex hull of the binary vectors $\{0, 1\}^n$ is the boolean cube which has only $2n$ facets. moreover, having exponentially many facets also doesn't mean that there isn't a higher dimensional polytope that projects to the given one. for example take the convex hull of of the standard basis vectors, which has $2^n$ facets, but is the projection of a small linear program. $\endgroup$
    – Sasho Nikolov
    Sep 5, 2012 at 18:32

2 Answers 2

Reset to default
11
+25
$\begingroup$

For asymptotic bounds, Fiorini, Massar, Pokutta, Tiwari, and de Wolf recently showed exponential lower bounds on the number of facets of any polytope that projects to the TSP polytope (the TSP polytope, being the convex hull of feasible TSP solutions). This is stronger than what you ask for, and implies that even adding extra variables will not make the TSP polytope efficiently representable.

Their paper is follow up to the classical 1988 paper by Yannakakis, who showed the same result but only for polytopes that satisfy a certain symmetry condition.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you for this link! It is certainly an impressive result, even though it would have been odd to have a nice (=non-exponentially growing) polytope for an NP problem. $\endgroup$
    – stefan
    Sep 5, 2012 at 17:59
  • $\begingroup$ the surprising part is being able to prove it :) $\endgroup$
    – Sasho Nikolov
    Sep 5, 2012 at 18:20
  • $\begingroup$ @stefan afaik a polynomial growing polytope for an NP problem would imply P=NP as raphael states above... also has anyone seen a statement/discussion of what would be reqd to extend the Fiorini et al to a P!=NP proof? $\endgroup$
    – vzn
    Jan 10, 2014 at 20:02
  • $\begingroup$ the short answer is that the result is about a computational model weaker than polytime-bounded TMs, and you'd like a version of it for a model that is as strong as P. for evidence that extended formulations are weaker than P, Rothvoss recently proved that the matching polyope has exponential extension complexity; nevertheless, arbitrary linear functions over the matching polytope can be solved using either Edmonds' algorithm, or the ellipsoid method. $\endgroup$
    – Sasho Nikolov
    Jan 10, 2014 at 20:27
  • $\begingroup$ more technically, there are many reasons why the results are far from P vs NP: the results are for a fixed encoding of problem solutions as vectors, and do not rule out a more clever encoding can allow for polysize formulations; also, the results say that for the given encoding, every compact LP fails on some objective function, but it might be possible to use different LPs for different objective functions; finally, we still have essentially no explicit lower bounds against SDPs, and then there is the ellipsoid method which can solve exponential size LPs $\endgroup$
    – Sasho Nikolov
    Jan 10, 2014 at 20:32
4
$\begingroup$

There is a library called SMAPO (short for library of linear descriptions of SMAll problem instances of POlytopes in combinatorial optimization) for a lot of polytopes including the symmetric TVP as well as the graphical TSP.

For the STSP, this is the list of number of facets for small polytopes

 Nodes in STSP  |  # of facets
----------------+--------------
       6        |         100
       7        |        3437
       8        |      194187
       9        |    42104442
      10        | 51043900866
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.