Embora a programação linear de número inteiro misto (MILP) seja realmente NP-completa, existem instâncias solucionáveis (não triviais) da programação linear de número inteiro misto.
NP-complete significa que a programação linear inteira mista é:
a) solucionável em tempo polinomial com uma máquina de Turing não determinística (a parte NP)
b) tempo polinomial redutível a 3-SAT (a parte completa; pelo resto da discussão, essa parte realmente não importa)
O ( 2n)n
Essa afirmação não significa que instâncias "pequenas" sejam intratáveis. Infelizmente, não posso fazer uma declaração precisa do que significa pequeno para uma instância do MILP. Resolvo problemas que têm 3.000 ou mais variáveis de decisão binária em uma base rotineira. Dependendo da formulação do problema, os problemas podem levar menos de 0,01 segundos (que é o caso de problemas relativamente pouco restritos) ou mais de uma hora (que é o caso de problemas em que muitas restrições estão ativas), porque os problemas parecem ter estrutura favorável. Posso dizer que os solucionadores de LP de ponta podem resolver LPs com vários milhões de variáveis de decisão contínuas e que, sem estrutura especial, é altamente improvável que haja uma instância de problema com algo em torno de 1.000 a 10,
Se você acha que possui uma instância solucionável do MILP, convém usar um algoritmo de ramificação e vinculação ou ramificação e corte. As melhores implementações são o CPLEX e o Gurobi . Ambos são produtos comerciais que possuem licenciamento acadêmico gratuito, se você procurar o suficiente. Se você realmente precisa de um solucionador de código-fonte aberto, os projetos na comunidade COIN-OR são mais apropriados, embora os pacotes de código-fonte possam ser exigentes às vezes. Os projetos mais relevantes seriam o solucionador de ramificação e corte do CBC , o solucionador SYMPHONY , o solucionador de preço de corte do BCP e o solucionador de ramo e corte da ABACUS . Todos esses projetos exigirão vários pacotes do COIN-OR, devido à sua estrutura modular.
Se você deseja a opção de tentar vários solucionadores, sua melhor aposta é usar a Interface Solver aberta do COIN-OR . Esteja ciente de que partes desta interface apenas permitem definir opções básicas do solucionador e que, para definir opções avançadas, você deve consultar as listas de correio do COIN-OR para obter mais detalhes. Os solucionadores MILP comerciais são MUITO (às vezes uma ordem de magnitude ou mais) mais rápidos que os solucionadores de código aberto. Outra opção para prototipagem é o uso de uma linguagem de modelagem algébrica como GAMS ou AMPL . Ambos os pacotes de software são comerciais, mas possuem versões de avaliação que podem ser usadas em pequenas instâncias de problemas. Para instâncias de problemas maiores, você pode enviar arquivos GAMS ou AMPL para o diretórioServidor NEOS a ser resolvido; esse servidor está disponível ao público.
Se você tiver uma instância suficientemente grande do MILP, nenhum desses solucionadores funcionará bem. Você pode relaxar as variáveis inteiras em variáveis contínuas, resolver o problema e, em seguida, arredondar para a coleção mais próxima de variáveis inteiras, que é uma solução viável para a instância do problema. Uma solução ideal do relaxamento LP do seu MILP lhe dará um limite mais baixo no valor da função objetivo ideal do seu MILP (assumindo minimização, é claro), e uma solução viável do seu MILP lhe dará um limite superior no objetivo ideal valor da função do seu MILP.
Se você tiver realmente sorte e sua matriz de restrições for totalmente desimodular , poderá usar um solucionador de LP para gerar soluções inteiras para o seu MILP e resolver seu problema com eficiência, apesar do tamanho grande. Outras classes de problemas têm algoritmos de aproximação rápida, como problemas de mochila e problemas de estoque de corte . Algoritmos especializados de decomposição do MILP também existem para problemas com estrutura especial, embora eu não esteja familiarizado com os detalhes, pois esses tópicos são um pouco especializados e estão fora do escopo da minha tese.
Não estou ciente de um esquema de aproximação de tempo totalmente polinomial (FPTAS) especificamente para MILP, embora exista um FPTAS de uma classe de problema que inclui MILP (consulte este documento) Minha recomendação seria usar um dos solucionadores de programação linear com números inteiros mistos acima, em conjunto com um limite de tempo e tolerâncias apropriadas em intervalos de otimização. Isso forneceria a melhor solução possível para o seu MILP dentro do prazo e, se o solucionador terminar com êxito antes do prazo, a solução viável seria ideal dentro das tolerâncias de intervalo de otimização definidas. Esse curso de ação ainda daria limites à qualidade da solução, porque sua solução viável seria um limite superior e o solucionador poderia fornecer um limite inferior apropriado. Não é garantido que o limite esteja dentro de um determinado fator de solução ideal, mas, novamente, qualquer FPTAS se tornará mais caro à medida que a aproximação se tornar melhor.
A coisa mais importante que você pode fazer antes de se decidir por uma formulação MILP é escolher a formulação mais forte possível; Você pode encontrar conselhos sobre como escolher formulações fortes em Introdução à otimização linear de Bertsimas e Tsitsiklis. A idéia principal é escolher uma formulação cujas restrições definam um politopo que seja o mais próximo possível do casco convexo da formulação (veja também as notas do curso ). Escolher uma formulação forte pode fazer uma enorme diferença no tempo necessário para resolver um problema.
