A complexidade mais rápida conhecida para o algoritmo combinatório de ILP?

Gostaria de saber qual é o algoritmo mais conhecido, em termos de notação Big- , para resolver a Programação Linear Inteira? $O$

Eu sei que o problema é completo, então não estou esperando nada polinomial. E eu sei que existem muitas heurísticas e outras que são usadas em aplicações práticas como o CPLEX, mas estou mais interessado na complexidade formal e de pior caso de um algoritmo exato. $NP$

Alguns problemas -Complete ter algoritmos em tempo onde e é um polinomial. Cobertura de vértice, conjunto independente e 3SAT se enquadram nessa categoria, mas SAT geral e TSP não (tanto quanto sabemos). $NP$ $O(b^n p(n))$ $1 < b < 2$ $p$

Podem ser feitas afirmações sobre Programação Inteira ou sub-instâncias específicas?

Se alguém tiver uma referência para o problema relacionado da aritmética do Quantificador Livre de Presburger, eu também estaria muito interessado nisso.

algorithms complexity-theory reference-request np-complete integer-programming jmite
fonte

Aardal, Karen, Robert Weismantel e Laurence A. Wolsey. "Abordagens não padronizadas para programação inteira." Matemática Aplicada Discreta 123.1 (2002): 5-74. dá muitas referências. Talvez você possa encontrar a resposta olhando para elas ou rastreando os artigos mais recentes que citam esta. Veja a Seção 2 em particular.

21415 Juho

Qual é a diferença entre e ?

O ({1.1}^{n})

$O(1.1^{n})$

O (99^{n})

$O(99^{n})$

22615 greybeard #

@greybeard, não muito para P vs NP, mas muito em termos de tratabilidade da vida real, dependendo das constantes, faz uma enorme diferença.

jmite

Eu gostaria de ter esperado por um lembrete inicial de que, dado e , uma diferença em resulta em um conjunto diferente de funções, enquanto uma em não e consequentemente é abstraída .

O (b^{n})

$O(b^n)$

O (c n)

$O(cn)$

b

$b$

c

$c$

greybeard

@jmite Concluído. A referência foi útil para você ou você conseguiu encontrar algumas informações novas?

Juho18

Pelo que posso dizer pesquisando, a pesquisa definitiva parece ser:

Aardal, Karen, Robert Weismantel e Laurence A. Wolsey. "Abordagens não padronizadas para programação inteira." Matemática Aplicada Discreta 123.1 (2002): 5-74.

Em particular, a Seção 2.1 discute a programação inteira em dimensão limitada e apresenta algoritmos devido a diferentes autores. De fato, a pesquisa lista muitas referências e discute algumas implementações práticas.

Para um número fixo de variáveis, a programação linear inteira é passível de solução polinomial no tempo pelo algoritmo de Lenstra.

Juho
fonte

bem, mas qual é o algoritmo mais rápido conhecido?

vzn

@ vzn Eu não sei, isso é no máximo uma resposta que abrange "sub-instâncias específicas".

Juho

A complexidade mais rápida conhecida para o algoritmo combinatório de ILP?

Respostas: