Relaxamento e complexidade de duas formulações

Question

Tenho duas formulações de MILP diferentes para o mesmo problema de agendamento com a mesma complexidade, mas com tempos de execução diferentes. Por que é recomendado comparar as versões relaxadas de cada formulação para deduzir o tempo de execução (e mais precisamente sobre o tamanho da árvore do B&B)?

Qual é a vantagem de considerar os modelos relaxados em vez dos modelos originais?

Também tenho outras perguntas:

• Todos os problemas de agendamento são NP-difíceis? Caso contrário, como determinar se um problema é NP-difícil ou não?

• Uma formulação com variáveis ​​inteiras e binárias é chamada de programa inteiro ou programa linear inteiro misto?

Answer 1

Por que é recomendado comparar as versões relaxadas de cada formulação para deduzir o tempo de execução (e mais precisamente sobre o tamanho da árvore do B&B)?

Geralmente, melhor (= mais rígido) é o relaxamento de um modelo de otimização inteiro, melhor deve funcionar uma abordagem de solução de árvore de marca e limite para este modelo. No entanto, existem alguns problemas NP-difíceis para os quais o custo da relaxação linear é igual ao custo de uma solução inteira ótima. Na verdade, apesar de ter um custo igual à solução de número inteiro ideal, a solução relaxada pode ser altamente fracionária, não trazendo nenhuma informação perspicaz para a busca de um número inteiro. Em conclusão, apenas olhar para o valor da relaxação linear não irá informá-lo muito sobre o tempo de execução da resolução do modelo inteiro original (por B&B ou qualquer outra abordagem).

Todos os problemas de agendamento são NP-difíceis? Caso contrário, como determinar se um problema é NP-difícil ou não?

Alguns problemas de escalonamento são fáceis de resolver, por algoritmos combinatórios de tempo polinomial (ou mesmo tempo linear). Mas esses problemas são geralmente muito básicos, não realistas OU problemas como você pode encontrar no setor. Por exemplo, aqui está um artigo sobre um problema tão fácil. Para aprender sobre NP-dureza, dê uma olhada na página da Wikipedia sobre o assunto ; Este é um bom ponto de partida. Você também encontrará muitos recursos na web.

Answer 2

A lacuna inicial pode ser um indicador, mas não muito bom. Já vi muitos problemas começarem com um limite rígido e nunca melhorarem, e também vi muitos problemas começarem com uma lacuna horrenda que melhora muito rapidamente.

Honestamente, não há como saber com antecedência, só temos que tentar resolver todas as formulações que pudermos fazer, até encontrarmos uma que funcione.