Algorithme pour faire Minimisation en programmation Entier

Question

Je comprends que faire la minimisation dans la programmation entière est un problème très complexe. Mais ce qui rend ce problème si difficile?

Si je devais (tentative) d'écrire un algorithme pour le résoudre, qu'est-ce que je dois prendre en compte? Je ne suis au courant de la technique de séparation et à destination de la résoudre et je me demande quel genre de barrages routiers je faire face lors d'une tentative d'appliquer cette technique programatically.

Answer 1

Comme dit l'autre, les problèmes sont très difficiles et il n'y a pas de solution simple, ni algorithme simple qui applique à toutes les classes de problèmes.

La façon « classique » de résoudre les problèmes est de faire une branche et lié et appliquer l'algorithme simplex à chaque noeud, comme vous le dites dans votre question. Cependant, je ne recommand vous-même si la mise en œuvre que vous n'êtes pas un expert.

En ce qui concerne un grand nombre de méthodes numériques, il est très difficile de l'obtenir à droite (bonnes valeurs de paramètres, bonnes Optimisations), et beaucoup ont été fait (voir CPLEX, COIN_OR, etc).

Il est pas que vous ne pouvez pas le faire:. La partie de branche et lié est assez straigtforward, mais sans tous les trucs de votre programme sera vraiment lent

En outre, vous aurez besoin d'une mise en œuvre et simplex ce n'est pas quelque chose que vous voulez vous faire:. Vous devrez utiliser une troisième partie lib de toute façon

Très probablement, wether

• si votre ensemble de données ne sont pas si grand (essayez!), Et vous n'êtes pas intéressé à le résoudre très vite: utiliser quelque chose comme COIN-OR ou lp_solve avec la méthode par défaut, il fonctionne;
• si votre ensemble de données est vraiment grand (et / ou vous avez besoin de trouver une solution rapidement à chaque fois), vous devez travailler avec un expert dans ce domaine.

Mon point principal est que les gens expérimentés seront savoir quel algorithme fonctionnera mieux sur votre problème, Wich forme du modèle sera le plus facile à résoudre, la méthode à appliquer et quel genre de Optimisations vous pouvez essayer.

Si vous êtes intéressé par ces problèmes, je recommande ce livre pour une introduction au calcul derrière tout cela (avec beaucoup d'exemples). Il est incroyablement expansive, donc vous pouvez aller à une bibliothèque au lieu de l'acheter: Nemhauser et Wolsey.

Answer 2

Je me demande quel genre de barrages routiers je faire face lors d'une tentative d'appliquer cette technique programatically.

Aucun en particulier (en supposant une mise en œuvre assez simple sans beaucoup de trucs). Les algorithmes ne sont pas compliqué -. Ils sont complexe , qui est une différence fondamentale

Des techniques telles que la branche et liée ou branche et essayer de couper à tailler l'arbre de recherche et d'accélérer ainsi le temps d'exécution. Mais l'arbre tout problème est cependant de façon exponentielle grande, d'où le problème.

Answer 3

Programmation entière est . Voilà pourquoi il est si difficile.

Il y a un tutoriel que vous pourriez être intéressé.

Answer 4

La première chose que vous faites avant de résoudre un problème d'optimisation mathématique est vous classer par catégorie. Sauf cas particuliers, la plupart du temps, les problèmes de programmation entiers seront np dur. Ainsi, au lieu d'utiliser un « algorithme », vous utiliserez une « heuristique ». La solution finale, vous trouverez ne sera pas un optimum garanti, mais ce sera une très bonne solution pour les problèmes de la vie réelle.

Votre barrage routier principal vos compétences en programmation. la programmation heuristiques nécessite un bon niveau de compréhension de la programmation. Ainsi, au lieu de programmer votre propre heuristique vous êtes mieux d'utiliser ensemble bien connu (par exemple, COIN-OR, gratuit). De cette façon, vous pouvez vous concentrer sur votre problème au lieu de l'heuristique.