8
$\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.

$\endgroup$
  • $\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 '12 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 '12 at 22:35
  • 1
    $\begingroup$ @Raphael: I've updated the question, so you can read something about facets and polytopes. $\endgroup$ – stefan Sep 1 '12 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 '12 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 '12 at 18:32
10
+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.

$\endgroup$
  • $\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 '12 at 17:59
  • $\begingroup$ the surprising part is being able to prove it :) $\endgroup$ – Sasho Nikolov Sep 5 '12 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 '14 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 '14 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 '14 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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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