O famoso artigo de 1983 de H. Lenstra Programação inteira com um número fixo de variáveis afirma que programas inteiros com um número fixo de variáveis são solucionáveis no polinômio no tempo no comprimento dos dados.
Eu interpreto isso da seguinte maneira.
- A programação inteira, em geral, ainda é NP-completa, mas se meu tamanho típico de problema em questão (digamos cerca de 10.000 variáveis, um número arbitrário de restrições) for possível na prática, eu poderia construir um algoritmo que seja escalonado polinomialmente no número de restrições, mas não em o número de variáveis e restrições.
- O resultado também é aplicável à programação binária, pois posso forçar qualquer número inteiro para 0-1 adicionando uma restrição apropriada.
Minha interpretação está correta?
Esse resultado tem implicações práticas? Ou seja, existe uma implementação disponível ou é usada em solucionadores populares como CPLEX, Gurobi ou Mosek?
Algumas citações do artigo:
Esse comprimento pode, para nossos propósitos, ser definido como n · m · log (a + 2), onde a denota o máximo dos valores absolutos dos coeficientes de A e b. De fato, não é provável que exista um algoritmo polinomial, pois o problema em questão é NP-completo
[...]
Foi conjecturado [5], [10] que para qualquer valor fixo de n existe um algoritmo polinomial para a solução do problema de programação linear inteira. No presente artigo, provamos essa conjectura exibindo esse algoritmo. O grau do polinômio pelo qual o tempo de execução do nosso algoritmo pode ser limitado é uma função exponencial de n.
fonte
Respostas:
O algoritmo mais rápido atual é na verdade linear no comprimento do programa linear inteiro para cada valor fixo de . Em sua tese de doutorado, Lokshtanov (2009) resume bem os resultados de Lenstra (1983), Kannan (1987) e Frank & Tardos (1987) pelo seguinte teorema.n
Assim, o problema é um parâmetro fixo linear parametrizado pelo número de variáveis.
1) Sim, a Programação Linear Inteira é "ainda" NP-completa. O tempo de execução do resultado teórico acima depende apenas linearmente do número de restrições, por isso é bem dimensionado no número de restrições. No entanto, não conheço nenhuma implementação real desse algoritmo.
2) Sim, fazer as variáveis assumirem valores binários é simples como você observou.
Atualizar. A dependência de pode realmente ser aprimorada no tempo de execução da Programação Linear Inteira. Baseado em Clarkson (1995) e Eisenbrand (2003) (veja os comentários abaixo), pode-se obter um algoritmo com tempo de execução onde é o número de restrições é o número máximo de bits necessário para codificar uma restrição ou a função objetivo.L
fonte
Aqui estão alguns pontos em relação às implicações práticas dos resultados do tipo Lenstra e possíveis implementações no CPLEX, Gurobi, etc. isto é, hiperplanos ao longo dos quais a largura do politopo não é muito grande (polinômio em variáveis e tamanho dos dados). Mas Mahajan e Ralphs (pré-impressão aqui ) mostraram que o problema de selecionar uma disjunção ideal é NP-completo. Portanto, parece difícil criar implementações praticamente eficientes dessa classe de algos.
A maioria dos algos implementados em pacotes como o CPLEX pode ser classificada como métodos de ramificação e corte. Essa família de técnicas geralmente funciona bem em instâncias de IP que são viáveis e geralmente conseguem encontrar soluções quase ideais. Mas o foco dos algos do tipo Lenstra está nos piores casos de instâncias de IP que são inviáveis para começar, e o objetivo é provar sua inviabilidade inteira (e eles estudam a complexidade dessa tarefa). AFAIK, não há classe de problemas com relevância prática que se encaixem nessa descrição. Portanto, o pessoal do CPLEX / Gurobi provavelmente não implementaria algos do tipo Lenstra tão cedo.
fonte