Existe na prática um limite para o número de restrições em um problema de programação linear?

8

Eu sou novo na programação linear e formulei um programa linear (LP) com ordem de variáveis ​​e restrições, embora a matriz de restrição seja extremamente esparsa.10131013

Eu queria saber se um LP dessa escala é tratável ou não?

stressed_geek
fonte
Presumo que você queira dizer 1013 variáveis ​​e 1013 restrições?
precisa
Sim, desculpe pela formatação incorreta.
stressed_geek

Respostas:

9

10 5 10 61013 está além dos recursos disponíveis nos maiores supercomputadores de hoje, devido principalmente aos limites de memória. Os maiores problemas que eu já vi praticamente resolvidos tiveram da ordem de linhas e colunas, mas o fator mais importante tende a ser o número de nonzeros, onde estamos apenas resolvendo problemas com nonzeros. Consulte a página de benchmarks paralelos de Mittelman para ter uma ideia do que os melhores solucionadores comerciais e disponíveis gratuitamente podem fazer em uma variedade de problemas desse tamanho.105106

Aron Ahmadia
fonte
6

Um grande número de restrições de desigualdade é geralmente tratável por técnicas de geração de restrições, processando a cada momento apenas um número limitado de restrições e adicionando restrições violadas na solução atual ao conjunto de restrições (excluindo as fortemente satisfeitas). Mas nos casos que eu vi, isso exige que o número de variáveis ​​não-slack também seja limitado.

Portanto, a questão é se você pode reformular seu problema de forma que o problema em si ou seu dual possua muito menos variáveis ​​do que restrições.

Edit: Veja também o trabalho recente de Nesterov sobre '' Métodos de subgradiente para problemas de otimização em grande escala '', http://dial.academielouvain.be/vital/access/services/Download/boreal:107876/PDF_01 . Sua técnica funciona em circunstâncias favoráveis ​​com uma complexidade de se os requisitos de precisão forem moderados.O(nlogn)

Arnold Neumaier
fonte
3

Meu comentário sobre a resposta de Aron ficou muito longo, mas eu gostaria de aumentar sua resposta:

Eu gosto de trazer o exemplo de benchmarks paralelos. Vários comentários para adicionar aqui. Todos os quatro solucionadores testados são comerciais, mas têm licenças acadêmicas gratuitas disponíveis. Além disso, o teste interrompe o tempo de execução às 25.000s, ou ~ 8h, que é arbitrário e depende muito de restrições de recursos externos (ou seja, em uma empresa, as pessoas podem não estar dispostas a esperar mais de um dia por resultados; na academia, algumas pessoas podem executar suas simulações por meses). O teste é executado em uma única máquina quad-core, o que não é indicativo, para mim, do desempenho de ponta.

Quando eu estava procurando por dados para responder a essa pergunta, encontrei artigos há mais de 10 anos que estavam resolvendo problemas de aproximadamente o mesmo tamanho, o que me sugere que talvez possamos melhorar agora com a infraestrutura que temos. Certamente não variáveis, mas com base na escala de métodos de pontos interiores , se a álgebra linear e o paralelismo foram implementados bem, e você teve tempo e um cluster de tamanho modesto, não vejo por que você não conseguiu resolver um problema com ou talvezn 3,5 10 7 10 81013n3.5107 108variáveis ​​(somente se você tivesse uma estrutura especial, poderia explorar métodos de decomposição como a decomposição de Benders ou Dantzig-Wolfe, além de algoritmos de geração de plano de corte). (Acrescentarei que estou ignorando o efeito de restrições, que complicam as coisas dependendo de quantos bits são armazenados; esse efeito apenas torna as estimativas abaixo mais pessimistas.)

Acredito que o GAMS tenha uma implementação paralela e, como usa solucionadores como CPLEX, Gurobi, MOSEK e Xpress (ou seja, os quatro solucionadores na referência que Aron cita), não vejo por que não se pode executar instâncias paralelas desses solucionadores (na verdade, eu sei que isso é possível para o CPLEX e o Gurobi). Os fatores limitantes serão a memória (porque a memória é cara) e a comunicação mais do que o poder de processamento, uma vez que um programa linear reduz, em última análise, a construção e resolução de um sistema de equações lineares repetidamente (uma simplificação excessiva maciça, sim, mas a álgebra linear é algo que saber paralelizar).

Mas variáveis ​​são demais. Supondo que a memória e a comunicação não eram um objeto, você precisaria pegar o maior problema no benchmark e escalar o tempo de execução nessa máquina por um fator de aproximadamente antes de explorar a estrutura especial que seu problema específico pode causar. ter. Isso não quer dizer que você não possa tentar resolvê-lo aproximadamente usando os métodos sugeridos pelo professor Neumaier, mas uma solução para otimizar é provavelmente impossível sem esperar muito tempo, usando um computador enorme e com uma implementação escalável de um O solucionador de LP sintonizado naquele computador enorme. 10 2410131024

Como uma estimativa aproximada de magnitude, o Intel Core 2 Quad usado na referência de Aron pode operar a uma velocidade máxima de 40 gigaflops. Supondo que você estivesse no Jaguar, o supercomputador do Oak Ridge National Lab, e que pudesse usar toda a máquina (extremamente improvável, mas vamos sonhar alto), você teria aproximadamente 2 petaflops na ponta dos dedos (com base nos números TOP 500 aqui , ou aproximadamente 50000 vezes a capacidade de computação, sem contar as penalidades devido a comunicação, limitações de memória ou o fato de ninguém nunca correr na velocidade máxima (nem mesmo o benchmark LINPACK).

Passar de para variáveis ​​significa aproximadamente um fator de 10.000 aumentos, que você pode conceber dividir entre um cluster de 50-100 máquinas e esperar um mês (supondo que você esteja disposto a esperar, você tem as máquinas e, novamente, a memória e a comunicação não são limitantes, todas com grandes "ses"). Passar de para variáveis ​​significa ir da área de trabalho para usar todo o Jaguar e esperar aproximadamente a anos. (E, novamente, esses efeitos também ignoram o fato de que você terá mais restrições!) 10 7 10 6 10 13 10 17 10 18106107106101310171018

Geoff Oxberry
fonte
Eu começaria com uma estimativa de quanto tempo levaria em um supercomputador, mas um dos problemas é que muitos dos solucionadores de LP mais rápidos dependem de uma decomposição de Cholesky e isso acabará com o uso de memória devido ao preenchimento. no. Além disso, essas máquinas implementam paralelismo de memória compartilhada, mas o verdadeiro paralelismo de memória distribuída é, por qualquer motivo, um tanto raro nos solucionadores de LP comerciais no momento.
Aron Ahmadia
A complexidade do método do ponto interior é apenas para problemas densos. Os solucionadores de LPs esparsos comerciais resolvem rotineiramente os LPs com vários milhões de variáveis ​​se estes tiverem um padrão de esparsidade favorável. O(n3.5)
Arnold Neumaier
@ArnoldNeumaier: Concordado. Ouvi em segunda mão que as companhias aéreas resolvem problemas dessa escala. A análise acima é uma estimativa de ordem de magnitude, é claro, e eu só vi a análise de complexidade computacional para o caso denso. Suspeito que o caso esparso tenha um fator de pelo menos ; nesse caso, as terríveis estimativas de tempo exigidas acima diminuiriam de acordo, mas ainda assim permaneceriam inaceitavelmente altas. O(n2.5)
precisa
@AronAhmadia: Concordado. Tudo o que vejo nos manuais do solucionador são fatorações de Cholesky densas ou esparsas, usadas para resolver o sistema de métodos de barreira. Ninguém usa métodos de subespaço de Krylov, nem vi paralelismo de memória distribuída (isto é, baseada em MPI). Não vejo problemas de otimização (com a possível exceção de problemas com restrições de PDE) resolvidos em supercomputadores. Talvez eu não esteja olhando para os papéis certos.
perfil completo de Geoff Oxberry
A pior complexidade dos métodos de ponto interior são as iterações , mas, na prática, o número de iterações é tipicamente de 30 a 50, independente da dimensão (ou talvez crescendo com seu log). Assim, na prática, métodos IP densos escalam com e métodos IP esparsos com , onde é o número médio de entradas em uma linha do fator Cholesky. - Mas é claro que os problemas com são muito maiores do que qualquer coisa que tenha sido resolvida até agora. O(n3)O(ne2)en=10 13O(n)O(n3)O(ne2)en=1013
Arnold Neumaier
0

É uma pergunta antiga, mas ei, há mais de 25 anos alguém já podia resolver um problema de restrição de 1,1 milhão e 2,6 milhões de variáveis ​​em 3h em um cluster de PC. http://www.maths.ed.ac.uk/~gondzio/CV/finance.pdf

Gostaria de ver as equações geradoras, talvez seja inteligente fazer uma decomposição séria antes de você jogar esse problema nos algoritmos, e gostaria de dizer como profissional que talvez seja inteligente mastigá-lo antes de alimentar o hardware. Também soa como o tamanho que induziria a erros numéricos na formulação, devido à precisão e memória limitadas do computador.

Sergio Lucero
fonte