Facetas conhecidas do politopo Viajante do Problema do Vendedor

Para o método de ramificação e corte, é essencial conhecer muitas facetas dos politopos gerados pelo problema. No entanto, atualmente é um dos problemas mais difíceis de calcular todas as facetas desses polítopos à medida que crescem rapidamente em tamanho.

Para um problema de otimização arbitrário, o politopo usado pelos métodos de ramificação e corte ou também pelos métodos do plano de corte é o casco convexo de todos os vértices possíveis. Um vértice é uma atribuição de todas as variáveis do modelo. Como um exemplo (muito simples): se alguém maximizasse st e então os vértices , e são vértices viáveis. viola a desigualdade e, portanto, não é viável. O problema de otimização (combinatória) seria escolher entre os vértices possíveis. (Nesse caso, obviamente $2\cdot x+y$ $x+y \leq 1$ $0\leq x,y\leq 1.5$ $(0,0)$ $(0,1)$ $(1,0)$ $(1,1)$ $x+y\leq 1.5$ $(1,0)$ é o ideal). O casco convexo desses vértices é o triângulo com exatamente esses três vértices. As facetas deste simples poliepítopo são , e . Observe que a descrição pelas facetas é mais precisa que o modelo. Na maioria dos problemas difíceis - como o TSP - o número de facetas excede o número de desigualdades de modelo em várias ordens de magnitude. $x\geq0$ $y\geq 0$ $x+y\leq 1$

Considerando o problema do vendedor ambulante, para qual número de nós o polítopo é totalmente conhecido e quantas facetas existem. se não estiver completo, quais são os limites inferiores no número de facetas?

Estou particularmente interessado na formulação do chamado caminho hamiltoniano do TSP:

m Eu n \sum_{Eu = 0 0}^{n - 1} (\sum_{j = 0 0}^{Eu - 1} c_{Eu, j} \cdot x_{Eu, j} + \sum_{j = Eu + 1}^{n - 1} c_{Eu, j} \cdot x_{Eu, j})

$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})$ st

\forall i \neq j : 0 \leq x_{i, j} \leq 1

$\forall i \neq j:\ \ 0 \leq x_{i,j}\leq 1$

\forall i \neq j x_{i, j} + x_{j, i} \leq 1

$\forall i \neq j\ \ \ x_{i,j}+x_{j,i}\leq 1$

\forall j \sum_{i = 0 0}^{j - 1} x_{Eu, j} + \sum_{Eu = j + 1}^{n - 1} x_{Eu, j} \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_{Eu = 0 0}^{j - 1} x_{j, Eu} + \sum_{Eu = j + 1}^{n - 1} x_{j, Eu} \leq 1

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

\sum_{Eu = 0 0}^{n - 1} (\sum_{j = 0 0}^{Eu - 1} x_{Eu, j} + \sum_{j = Eu + 1}^{n - 1} x_{Eu, j}) = n - 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$

Se você tiver alguma informação sobre politopos de outras formulações do TSP, sinta-se à vontade para compartilhar isso também.

algorithms optimization linear-programming mathematical-programming traveling-salesman Stefan
fonte

Pessoalmente, não sei ao certo o que significa "politopo de um problema". Mas então, tenho pouco conhecimento em teoria da complexidade.

Raphael

Na verdade, não é uma teoria da complexidade (não fui eu etiquetando essa tag). Na verdade, ainda não existe uma tag adequada para esse tipo de pergunta. Uma etiqueta adequada seria o método de ramificação e corte ou plano de corte. Vou acrescentar algumas informações sobre o que polytope estou falando pouco

Stefan

@ Rafael: Eu atualizei a pergunta, para que você possa ler algo sobre facetas e polítopos.

Stefan

@ stean: Ah, então é apenas o espaço de soluções viáveis. Nesse caso, a pesquisa do TSP é claramente exponencial em tamanho; caso contrário, tínhamos P = NP há muito tempo. Ainda mais, o TSP é geralmente definido em gráficos completos não direcionados, portanto, existem exatamente

n!

$n!$ soluções viáveis. Portanto, não vejo o que mais você procura; talvez eu não tenha um detalhe importante da sua pergunta. Talvez você tenha anotado o LP relaxado, não o IP?

Raphael

@ Rafael, é o casco convexo de soluções viáveis. você está certo de que, a menos que P = NP, este casco convexo tenha exponencialmente muitas facetas. no entanto, o número de vértices não tem nada a ver com isso: o casco convexo dos vetores binários

{0, 1}^{n}

$\{0, 1\}^n$ é o cubo booleano que possui apenas

2 n

$2n$ facetas. além disso, ter muitas facetas exponencialmente também não significa que não há um polítopo de maior dimensão que se projeta para o determinado. por exemplo, pegue o casco convexo dos vetores de base padrão, que tem

2^{n}

$2^n$ facetas, mas é a projeção de um pequeno programa linear.

Sasho Nikolov 5/09/12

Respostas:

Para limites assintóticos, Fiorini, Massar, Pokutta, Tiwari e de Wolf recentemente mostraram limites inferiores exponenciais no número de facetas de qualquer politopo que se projeta no politopo do TSP (o poltope do TSP, sendo o casco convexo das soluções viáveis do TSP). Isso é mais forte do que você solicita e implica que mesmo adicionar variáveis extras não tornará o politopo do TSP eficientemente representável.

O artigo deles segue o clássico de 1988 de Yannakakis, que mostrou o mesmo resultado, mas apenas para politopos que satisfazem uma certa condição de simetria.

Sasho Nikolov
fonte

Obrigado por este link! Certamente é um resultado impressionante, mesmo que fosse estranho ter um bom politopo (= crescimento não exponencial) para um problema de NP.

21413 stefan

a parte surpreendente é ser capaz de provar isso :)

Sasho Nikolov

@stefan afaik Um polopólio polinomial crescente para um problema de NP implicaria P = NP como afirma Rafael acima ... também alguém viu uma declaração / discussão sobre o que seria necessário para estender o Fiorini et al a uma prova de P! = NP?

vzn

a resposta curta é que o resultado é sobre um modelo computacional mais fraco do que as TMs delimitadas por tempo policíclico, e você gostaria de uma versão dele para um modelo que seja tão forte quanto P. para evidências de que formulações estendidas são mais fracas que P, Rothvoss recentemente provou que o políope correspondente tem complexidade de extensão exponencial; no entanto, funções lineares arbitrárias sobre o pólipo correspondente podem ser resolvidas usando o algoritmo de Edmonds ou o método elipsóide.

Sasho Nikolov

tecnicamente, há muitas razões pelas quais os resultados estão longe de P vs NP: os resultados são para uma codificação fixa de soluções de problemas como vetores e não descartam que uma codificação mais inteligente possa permitir formulações de polissização; Além disso, os resultados dizem que, para a codificação fornecida, todo LP compacto falha em alguma função objetiva, mas pode ser possível usar LPs diferentes para diferentes funções objetivas; finalmente, ainda temos limites inferiores essencialmente nenhuma explícitas contra SDPs, e depois há o método elipsóide que pode resolver LPs tamanho exponencial

Sasho Nikolov

Há uma biblioteca chamada SMAPO (abreviação de biblioteca de descrições lineares de SMAlls instâncias de problemas de POlytopes na otimização combinatória) para muitos polítopos, incluindo o TVP simétrico e o TSP gráfico.

Para o STSP, esta é a lista do número de facetas para pequenos politopos

 Nodes in STSP  |  # of facets
----------------+--------------
       6        |         100
       7        |        3437
       8        |      194187
       9        |    42104442
      10        | 51043900866

Stefan
fonte