Le problème de l'optimisation des combinaisons (http://qiita.com/Tsutomu-KKE@github/items/bfbf4c185ed7004b5721) a son propre ensemble de difficultés. Il existe plusieurs méthodes de modélisation pour le même problème, et chaque modèle a ses propres avantages et inconvénients. Comment modéliser est important. Ici, nous allons vous expliquer comment le concevoir, en utilisant le problème de l'emballage des bacs comme exemple.
| Soit une boîte d'une capacité de $ c (\ gt 0) $ et $ n $ bagages $ N = \ {1, \ dots, n \} $. Soit la capacité des bagages $ i \ in N $ $ w_i (\ gt 0) $. Trouvez un assortiment qui minimise le nombre de boîtes nécessaires pour emballer tous vos bagages. |
Par exemple, lorsque vous transportez des objets lourds sur un camion de 10 tonnes, il est difficile de demander le moins de camions possible.
référence [Problème d'emballage de bac-Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%93%E3%83%B3%E3%83%91%E3%83%83%E3%82%AD % E3% 83% B3% E3% 82% B0% E5% 95% 8F% E9% A1% 8C)
Formulons-le tel quel.
| Formulation en une étape | ||
| $ \ mbox {objective} $ | $ \ sum_i {y_i} $ | Nombre de boîtes |
| $ \ mbox {variables} $ | $ x_ {ij} \ in \ {0, 1 \} ~ \ forall i, j $ | S'il faut mettre la boîte $ j $ dans les bagages $ i $ |
| $ y_j \ in \ {0, 1 \} ~ \ forall j $ | S'il faut utiliser la boîte $ j $ | |
| $ \ mbox {sous réserve de} $ | $ \ sum_j {x_ {ij}} = 1 ~ \ forall i $ | Bagages Mettez $ i $ dans l'une des cases |
| $ \ sum_i {w_i x_ {ij}} \ le c ~ \ forall j $ | Remplissez la capacité de la boîte $ j $ | |
| $ x_ {ij} \ le y_j ~ \ forall i, j $ | Contraintes sur $ y $ | |
En fait, cette formulation est difficile à résoudre pour les solveurs et prend beaucoup de temps à calculer.
En conséquence, il est plus rapide de fixer le nombre de cases, de vérifier s'il existe une solution et de modifier le nombre de cases dans la boucle externe.
Les formules A et B lorsque le nombre de cases est fixe sont indiquées ci-dessous.
| Formulation en deux étapes A | ||
| $ \ mbox {objectif} $ | Aucun | |
| $ \ mbox {variables} $ | $ x_ {ij} \ in \ {0, 1 \} ~ \ forall i, j $ | Bagages $ S'il faut mettre la boîte $ j $ dans i $ |
| $ \ mbox {sous réserve de} $ | $ \ sum_j {x_ {ij}} = 1 ~ \ forall i $ | Bagages Mettez $ i $ dans l'une des cases |
| $ \ sum_i {w_i x_ {ij}} \ le c ~ \ forall j $ | Remplissez la capacité de la boîte $ j $ | |
| Formulation en deux étapes B | ||
| $ \ mbox {objectif} $ | $ y $ | Capacité dépassée |
| $ \ mbox {variables} $ | $ x_ {ij} \ in \ {0, 1 \} ~ \ forall i, j $ | S'il faut mettre la boîte $ j $ dans les bagages $ i $ |
| $ y \ ge 0 $ | Dépassement de la capacité | |
| $ \ mbox {sous réserve de} $ | $ \ sum_j {x_ {ij}} = 1 ~ \ forall i $ | Bagages Mettez $ i $ dans l'une des cases |
| $ \ sum_i {w_i x_ {ij}} \ le c + y ~ \ forall j $ | Remplissez la capacité de la boîte $ j $ | |
Il présente les caractéristiques suivantes.
| Formulation | Lorsqu'une solution existe | Quand il n'y a pas de solution |
|---|---|---|
| Formulation en deux étapes A | Très chronophage | Se termine bientôt |
| Formulation en deux étapes B | Se termine bientôt | Très chronophage |
À partir de là, si vous exécutez A et B en parallèle, vous pouvez voir rapidement si une solution existe. Le nombre de boîtes peut être trouvé efficacement en recherchant pendant 2 minutes.
Existe-t-il un moyen rapide d'éviter la parallélisation?
La formulation exacte de la solution est inefficace en raison de la symétrie de la solution (les cases X et Y peuvent être échangées). Par conséquent, dans la pratique, vous utiliserez souvent la méthode de la solution approximative. Il existe une méthode de génération de colonnes comme solution approximative pour résoudre le problème d'emballage des bacs. Bien qu'il s'agisse d'une solution approximative, on peut s'attendre à une précision. Cependant, comme il s'agit d'une méthode compliquée, j'omettrai l'explication. Si vous êtes intéressé, veuillez lire l'article relativement facile à comprendre (Méthode de génération de la première colonne). En Python, la méthode de génération de colonne est effectuée avec ortoolpy.binpacking, qui peut être installé avec "pip install ou toolpy".
D'autres solutions approximatives couramment utilisées sont la méthode gloutonne et la méthode de recherche locale, qui sont omises ici.
Les problèmes d'optimisation combinée sont souvent de l'ordre exponentiel. À partir de là, si le problème peut être divisé, ce sera une solution approximative, mais elle peut être accélérée. En général, [Divisional Governance](https://ja.wikipedia.org/wiki/%E5%88%86%E5%89%B2%E7%B5%B1%E6%B2%BB%E6% Il s'appelle B3% 95).
c'est tout
Recommended Posts