Les méthodes de point intérieur fonctionnent en suivant le chemin central vers une solution optimale. Lorsque vous modifiez la fonction objectif, la solution optimale de la version précédente du problème est loin du chemin central pour le nouveau problème, il faut donc plusieurs itérations pour revenir au chemin central et doit en outre revenir à un centre assez bien centré Solution. Ensuite, vous devez travailler sur le chemin vers une nouvelle solution optimale. Vous pouvez tout aussi bien démarrer la méthode du point intérieur à partir d'un point arbitraire.
En comparaison, la méthode simplex (primale ou double) se déplace de sommet en sommet de l'ensemble réalisable. Dans le cas typique, un changement raisonnablement faible de l'objectif se traduira par une nouvelle solution optimale qui n'est qu'à quelques pivots simplex.
... ajouté à l'explication intuitive ci-dessus pour donner plus de détails ...
Dans la pratique informatique, l'expérience n'a tout simplement pas montré d'avantage substantiel pour les méthodes de démarrage à point intérieur primal-double à chaud. Ce n'est pas une caractéristique des codes largement utilisés comme CPLEX et Gurobi (les sociétés qui produisent ces packages seraient certaines d'ajouter une telle fonctionnalité si cela en valait la peine), et il y a relativement peu d'articles discutant des stratégies pour les méthodes de démarrage à point chaud. .
Deux références que je recommanderai sont:
EA Yildirim et S. Wright. Stratégies de démarrage à chaud dans les méthodes de point intérieur pour la programmation linéaire. SIAM Journal on Optimization 12: 782-810, 2002. Cet article donne de belles limites théoriques sur certaines stratégies de démarrage à chaud. Voir
http://pages.cs.wisc.edu/~swright/papers/YilW02a.pdf
Un article ultérieur co-écrit par Yildirim donne quelques résultats de calcul, mais les auteurs admettent que le démarrage à froid est souvent plus rapide dans leurs tests que le démarrage à chaud:
E. John et EA Yildirim. Mise en œuvre de stratégies de démarrage à chaud dans les méthodes de point intérieur pour la programmation linéaire en dimension fixe. Optimisation informatique et applications. 41: 151-183, 2008. Voir
http://link.springer.com/article/10.1007/s10589-007-9096-y
