Relaxation et complexité de deux formulations
J'ai deux formulations MILP différentes pour le même problème de planification avec la même complexité mais avec des temps d'exécution différents. Pourquoi est-il recommandé de comparer les versions assouplies de chaque formulation pour en déduire le temps de fonctionnement (et plus précisément la taille de l'arbre B&B)?
Quel est l'avantage de considérer les modèles décontractés au lieu des modèles originaux?
J'ai aussi d'autres questions:
Est-ce que tous les problèmes de planification sont NP-difficiles? Sinon, comment déterminer si un problème est NP-difficile ou non?
Une formulation avec des variables entières et binaires est appelée programme entier ou programme linéaire mixte entier?
Réponses
Pourquoi est-il recommandé de comparer les versions assouplies de chaque formulation pour en déduire le temps de fonctionnement (et plus précisément la taille de l'arbre B&B)?
Généralement, mieux (= plus serré) est la relaxation d'un modèle d'optimisation d'entiers, mieux devrait fonctionner une approche de solution d'arbre de marque et lié à ce modèle. Néanmoins, il existe des problèmes NP-difficiles pour lesquels le coût de la relaxation linéaire est égal au coût d'une solution entière optimale. En effet, malgré un coût égal à la solution entière optimale, la solution relâchée peut être très fractionnaire, n'apportant alors aucune information perspicace pour la recherche d'un entier. En conclusion, le simple fait de regarder la valeur de la relaxation linéaire ne vous renseignera pas autant sur le temps d'exécution de la résolution du modèle entier d'origine (par B&B ou toute autre approche).
Est-ce que tous les problèmes de planification sont NP-difficiles? Sinon, comment déterminer si un problème est NP-difficile ou non?
Certains problèmes d'ordonnancement sont faciles à résoudre, par des algorithmes combinatoires en temps polynomial (ou même en temps linéaire). Mais ces problèmes sont généralement très basiques, pas réalistes OU des problèmes comme vous pouvez trouver dans l'industrie. Par exemple, voici un article sur un problème aussi simple. Pour en savoir plus sur la dureté NP, consultez la page Wikipedia sur le sujet ; c'est un bon point de départ. Vous trouverez également de nombreuses ressources sur le Web.
L'écart initial peut être un indicateur mais pas un très bon. J'ai vu de nombreux problèmes commencer par une limite serrée et ne jamais s'améliorer, et j'ai également vu de nombreux problèmes commencer par un écart horrible qui s'améliore très rapidement.
Honnêtement, il n'y a aucun moyen de savoir à l'avance, nous devons simplement essayer de résoudre toutes les formulations que nous pouvons proposer, jusqu'à ce que nous trouvions celle qui fonctionne.