J'ai un problème de programmation linéaire entier qui prend très longtemps à résoudre par les solveurs que j'ai essayés (CPLEX, CBC), même s'ils trouvent la solution optimale au début. Ils prennent juste une éternité pour le prouver complètement.Suggestion d'une limite inférieure pour un solveur ILP
Il est facile de calculer une borne inférieure triviale pour la valeur objective de mon problème de minimisation, mais dans la sortie de CPLEX (colonne Best Bound) je peux voir qu'elle ne se rapproche même pas longtemps. Il trouve de très bonnes solutions presque immédiatement, mais il pense à tort que la solution optimale pourrait être bien meilleure. Maintenant, je dois admettre que je ne sais pas vraiment comment ces solveurs fonctionnent, mais il semble qu'ils perdent du temps à essayer d'améliorer les limites inférieures ridiculement faibles, en cherchant des solutions incroyablement optimistes. Donc mes questions sont:
Pourrait dire au solveur une limite inférieure décente de l'objectif l'aider à courir plus vite?
Si oui, quels solveurs peuvent accepter une borne inférieure connue fournie comme entrée supplémentaire?
A titre d'illustration, je colle les premières lignes de la sortie de CPLEX d'une course par exemple (qui va beaucoup plus longtemps, sans aucune amélioration supplémentaire de l'objectif et une amélioration très lent de la meilleure limite):
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap
0 0 -388.6997 178 -388.6997 9
* 0+ 0 297.0000 -388.6997 9 230.88%
* 0+ 0 275.0000 -388.6997 9 241.35%
0 2 -388.6997 178 275.0000 -387.8106 9 241.02%
* 20+ 20 185.0000 -307.6363 80 266.29%
* 30+ 30 135.0000 -307.6363 90 327.88%
* 30+ 30 94.0000 -307.6363 90 427.27%
* 60+ 60 90.0000 -307.6363 120 441.82%
* 160+ 126 77.0000 -307.6363 272 499.53%
* 200+ 93 12.0000 -307.4836 325 ---
300 182 -135.2988 107 12.0000 -268.6638 466 ---
1200 934 -50.6022 85 12.0000 -206.2938 1480 ---
2197 1755 -96.9612 93 12.0000 -189.8013 2470 ---
3226 2600 -2.8316 87 12.0000 -179.9669 3480 ---
4374 3521 -156.2442 110 12.0000 -170.4183 4567 ---
5490 4421 -128.0871 97 12.0000 -167.3696 5623 ---
6971 5603 -147.5022 108 12.0000 -162.4180 7055 ---
8739 6997 -103.5374 113 12.0000 -156.3532 8673 ---
Je voudrais pouvoir dire au solveur de ne pas la peine de chercher des solutions avec un objectif inférieur à 10 (parce que je peux prouver que beaucoup avec une méthode plus simple) et surtout pas avec une valeur objective négative (parce que ce n'est pas même possible dans mon modèle).
(1) Vous pouvez toujours ajouter une contrainte qui rend toutes les solutions plus bas que votre a priori connu lié infaisable. Ce serait assez (2) En ce qui concerne les solveurs commerciaux, j'ai lu plus d'une fois, que les développeurs pensent que c'est souvent contre-productif. Mais peut-être que cela vous aide dans votre cas (et malheureusement je ne peux pas fournir un lien, peut-être google pour la question dans la liste de diffusion de gurobi). (3) En fonction de ce que vous réalisez, vous pouvez ajuster vos options de solveur. Gurobi a MIPFocus comme option. Peut-être que vous pouvez réaliser cela aussi. Par exemple, de nombreuses coupures pour mieux prouver les limites; plus d'heuristiques pour des bonnes solutions plus rapides – sascha
Comment avez-vous trouvé la borne inférieure triviale? Avez-vous simplement relâché les contraintes d'intégralité et résolu le programme linéaire (réel)? –
@sascha Ajout de la contrainte sur l'objectif n'a pas aidé, mais je vais regarder dans Gurobi et (3), merci. Ce pourrait être exactement ce dont j'ai besoin. –