résultats confus de deux modèles de complexité différente

Question

J'ai deux modèles qui abordent le même problème.

le premier est:

le second est:

pour différentes instances pour la même taille (n = 30) j'ai trouvé les résultats suivants (la première colonne de gauche est pour le premier modèle, la deuxième colonne est pour le deuxième modèle).

Il semble illogique qu'un modèle avec o (n3) variables et contraintes consomme moins de temps qu'un modèle avec o (n2) variables et contraintes. Ces résultats pourraient-ils être expliqués? ou l'utilisation de plusieurs variables binaires au lieu de variables faibles pourrait réduire le temps?

Answer 1

Il existe un certain nombre d'explications possibles (qui ne s'excluent pas mutuellement). Le modèle plus grand peut avoir une relaxation continue plus serrée. (Vous pouvez tester cela en assouplissant les restrictions d'intégralité et en résolvant les deux LP.) En supposant que vous utilisez un solveur qui a une étape de pré-résolution, il peut y avoir quelque chose dans le premier modèle qui permet au pré-solveur de resserrer les choses d'une manière qu'il ne peut pas faire. le deuxième modèle. Le solveur peut générer des coupes plus productives dans le premier modèle que dans le second (ou non disponibles / non pertinentes dans le second). En outre, il peut y avoir un élément de chance impliqué (en particulier si votre comparaison de temps est basée sur une seule instance de problème).

Les programmes entiers sont des bêtes perverses.