resultados confusos de dois modelos com complexidade diferente

Question

Tenho dois modelos que tratam do mesmo problema.

o primeiro é:

o segundo é:

para instâncias diferentes para o mesmo tamanho (n = 30), encontrei os seguintes resultados (a primeira coluna à esquerda é para o primeiro modelo, a segunda coluna é para o segundo modelo).

Parece ilógico que um modelo com o (n3) variáveis ​​e restrições consuma menos tempo do que um modelo com o (n2) variáveis ​​e restrições. Esses resultados podem ser explicados? ou o uso de múltiplas variáveis ​​binárias em vez de variáveis ​​baixas poderia reduzir o tempo?

Answer 1

Existem várias explicações possíveis (não mutuamente exclusivas). O modelo maior pode ter um relaxamento contínuo mais rígido. (Você pode testar isso relaxando as restrições de integralidade e resolvendo ambos os LPs.) Supondo que você esteja usando um solucionador que tem um estágio de pré-resolução, pode haver algo no primeiro modelo que permite que o pré-resolvedor aperte as coisas de uma maneira que não pode fazer em o segundo modelo. O solucionador pode gerar cortes que são mais produtivos no primeiro modelo do que no segundo (ou não disponíveis / não relevantes no segundo). Além disso, pode haver um elemento de sorte envolvido (especialmente se sua comparação de tempo for baseada em uma única instância de problema).

Programas inteiros são bestas perversas.