Ambiente de programação inteira
Resolva um pequeno programa linear inteiro com ramificação e limite exatos e consulte cada nó da pesquisa. O melhor ponto só é indicado como ótimo demonstrado quando toda a árvore tiver sido explorada.
Os programas estão limitados a 4.000 caracteres e 40 linhas, 8 variáveis e 8 restrições com duas ou mais variáveis; o limite de nós vai de 1 a 5.000 e a pesquisa também termina após 3.000.000 de passos de aritmética exata. Tudo é calculado no seu dispositivo num processo em segundo plano com um limite de 15 segundos. Pode descarregar um relatório JSON e um CSV de nós. Primeira linha: maximize ou minimize e a função objetivo. Depois, uma restrição por linha. Até 4 000 caracteres. Reveja as definições antes de executar.
Seu resultado
Ambiente de programação inteira
- Escreva a função objetivo na primeira linha, como maximize 5x + 4y.
- Adicione uma restrição por linha, limites como x, y >= 0 e, opcionalmente, linhas como integer x ou binary z.
- Defina o limite de nós e execute a pesquisa.
- Consulte o estado, a melhor solução atual, o melhor limite e a diferença; depois descarregue o relatório JSON ou o CSV de nós.
O que esperar
Os programas estão limitados a 4.000 caracteres e 40 linhas, 8 variáveis e 8 restrições com duas ou mais variáveis; o limite de nós vai de 1 a 5.000 e a pesquisa também termina após 3.000.000 de passos de aritmética exata. Tudo é calculado no seu dispositivo num processo em segundo plano com um limite de 15 segundos. Pode descarregar um relatório JSON e um CSV de nós.
Ramificação e limite
Cada nó resolve exatamente a relaxação linear pelo método simplex. Uma variável inteira fracionária é dividida em dois ramos: x <= floor e x >= ceiling. Os nós são eliminados quando a relaxação é inviável ou não pode superar a melhor solução inteira encontrada. Método: Wolsey, Integer Programming, 2.ª edição, capítulo 7 (2020).
O significado de «provado»
Quando todos os nós tiverem sido resolvidos ou eliminados com um limite exato, a solução incumbente está provada como ótima ou o problema está provado como inviável. Se o limite de nós ou de passos interromper a pesquisa antes disso, a incumbente é apenas o melhor ponto encontrado até então; o relatório apresenta o melhor limite e a diferença entre ambos.
Regras de entrada
As variáveis são inteiras, salvo se indicar algumas como contínuas com integer x, y. As restrições de uma só variável tornam-se limites. Uma relaxação ilimitada interrompe a pesquisa, pois o programa inteiro poderá ser ilimitado ou inviável.