[PYTHON] Résolution des problèmes de sac à dos avec les outils OR de Google - Pratiquer les bases des problèmes d'optimisation combinée

: bow_and_arrow: Objectif de cet article

Vous apprendrez la formulation et la solution du problème du sac à dos, qui est l'un des problèmes typiques du problème d'optimisation de combinaison, à travers un exemple simple. De plus, après la formulation, utilisez les outils OR créés par Google en langage Python comme outil pour trouver réellement la solution, et programmez pour trouver la solution.

: bow_and_arrow: A propos du problème d'optimisation des combinaisons et de sa formulation

Lors de la décision de quelque chose, le problème de la prise en compte du modèle de la combinaison, comme la sélection de choses "sélectionner" ou "ne pas sélectionner", l'extraction des éléments de la condition à partir de l'ensemble des objets, ou leur ordonnancement est appelé le problème d'optimisation de combinaison. Je vais.

Maintenant, soit i ou j un entier partant de 1 comme indiqué ci-dessous, pour les constantes a, b, c connues à l'avance par le problème et la variable x pour laquelle la solution doit être obtenue.

a_i　(i = 1,2,3,...,m)… Constantes pré-connues\\
b_i　(i = 1,2,3,...,m)… Constantes pré-connues\\
x_j　(j = 1,2,3,...,n)… X est un entier

Le problème de trouver une solution sous forme linéaire (polypole d'addition ou de multiplication) à l'aide des constantes et variables ci-dessus est appelé un problème de programmation d'entiers, et est généralement formulé comme suit.

<Exemple de formulation>\hspace{250pt}\\
Fonction objectif: c_1x_1 + c_2x_2 + ... + c_nx_n\\
Condition: un_{i1}x_1 + a_{i2}x_2 + ... + a_{in}x_n ≦ b_i \\Cependant, je= 1,2,...,m\\
x_j est un entier, j=1,2,...,n

La fonction objectif est la valeur à laquelle la solution optimale est trouvée en maximisant ou en minimisant la valeur, et le solveur la calcule automatiquement. Un solveur est un outil pour calculer la solution optimale pour un problème d'optimisation, et comme mentionné au début, OR-Tools est utilisé ici. Utilisez Python pour la programmation.

: bow_and_arrow: Exemple de problème de sac à dos

Le problème du sac à dos est l'un des problèmes typiques (ou standard) du problème d'optimisation des combinaisons. Un problème typique est un problème représentatif qui résume divers problèmes qui existent dans la société tels que la production / distribution, la planification des ventes, le calendrier de travail et le traitement de l'information, et les classe en plusieurs modèles.

Ici, le problème de sac à dos suivant est cité comme exemple du texte de référence (répertorié dans la source), et la solution réelle est recherchée.

: speech_balloon: Problème

Comme indiqué dans le tableau des éléments ci-dessous, il y a 5 éléments, et chaque élément A à E a le sien.\\
Volume a_j et valeur c_Je sais que j.(j est un numéro d'index de 0 à 4)\\
De plus, la capacité du sac à dos est de 12.\\
Je veux décider de la combinaison d'articles à emballer dans le sac à dos à partir de ces articles.\\
Cependant, le volume total des articles sélectionnés ne doit pas dépasser la capacité du sac à dos.\\
Choisissez une combinaison d'éléments qui maximise la somme des valeurs.\\

** Liste des articles **

article	A	B	C	D	E
Numéro d'index j	0	1	2	3	4
Volume aj	3	4	6	1	5
Valeur ci	6	7	8	1	4

: a: ** Réponse **

Considérez le programme. Le contenu du programme suit essentiellement le guide OR-Tools de Google. (https://developers.google.com/optimization)

Écrivez un sort au début du programme.

`knapsack.py`


from __future__ import print_function
from ortools.linear_solver import pywraplp

Puisqu'il est résolu par le solveur de planification d'entiers mixtes, il est déclaré ci-dessous.

`knapsack.py`


# Create the mip solver with the CBC backend.
solver = pywraplp.Solver('simple_mip_program',
    pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

Ensuite, nous définissons des constantes.

`knapsack.py`


#Définition constante=================================================================

#Volume d'article
a = [3,4,6,1,5]
#valeur
c = [6,7,8,1,4]
#Capacité du sac à dos
b = 12

Définissez le volume, la valeur et la capacité du sac à dos de l'article en fonction de l'énoncé du problème ci-dessus. Puisqu'il y a 5 éléments, nous conserverons les valeurs dans un tableau. Les numéros d'éléments doivent être comptés à partir de 0 selon l'index du tableau.

Définissez la variable x.

`knapsack.py`


#Définition variable=================================================================

# 1:Choisir/ 0:Non séléctionné
x = {}
for j in range(5):
    x[j] = solver.BoolVar("x%i" % j)

Déclarez la variable x qui détermine l'élément à choisir ci-dessus. x prend une valeur de 0 ou 1, 1 si vous choisissez un élément, 0 si vous ne le faites pas. Le solveur calcule et décide de la valeur à prendre.

Il est enfin temps de formuler. Dans la formulation, nous définirons l'expression conditionnelle. Dans ce problème, ① Le volume total des articles sélectionnés ne doit pas dépasser la capacité du sac à dos ② Décidez de la combinaison d'éléments qui maximise la somme des valeurs Est une condition. Cette condition est appelée une condition de contrainte, et ce qui est exprimé par une expression est appelé une expression de contrainte.

L'expression de contrainte est définie ci-dessous.

`knapsack.py`


#Expression de contrainte===================================================================

#La somme des volumes des articles sélectionnés ne doit pas dépasser la capacité du sac à dos
solver.Add(solver.Sum([a[j] * x[j] for j in range(len(a))]) <= 12)

#Fonction objective(Maximiser)
#Déterminez la combinaison d'éléments qui maximise la somme des valeurs
solver.Maximize(solver.Sum([c[j] * x[j] for j in range(len(a))]))

Comme indiqué dans l ' au début, les conditions et les fonctions objectives sont définies. Enfin, écrivez une instruction pour calculer la solution.

`knapsack.py`


#Exécution de la solution
status = solver.Solve()

Le calcul d'optimisation est effectué ci-dessus et le solveur calcule la solution optimale. À la suite du calcul, xj est déterminé en j de 0 à 4, et il est clair quel élément sélectionner. Vérifiez le résultat du calcul ci-dessous.

`knapsack.py`


if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
    print('Solution:')
    print('ok')
    print('Objective value =', solver.Objective().Value())
    print("culculate Time = ", solver.WallTime(), " milliseconds")

    #Élément à sélectionner
    print('select item')
    for j in range(len(a)):
        print(j,x[j].solution_value())
    
    #valeur
    print('total value')
    print(sum(c[j] * x[j].solution_value() for j in range(len(a))))

else:
    print('The problem does not have an optimal solution.')

C'est la fin de la programmation. Le résultat réel de l'exécution est le suivant.

Solution: ok Objective value = 17.0 culculate Time = 158 milliseconds select item 0 1.0 1 1.0 2 0.0 3 0.0 4 1.0 total value 17.0

À la suite du calcul d'optimisation, l'élément sélectionne 0,1,4 (A, B, E) et sa valeur est

\begin{eqnarray}

valeur&=&c_0+c_1+c_4\\
&=&6+7+4\\
&=&17

\end{eqnarray}

Il s'est avéré être. C'est tout pour le calcul d'optimisation.

Voici la source complète.

`knapsack.py`


from __future__ import print_function
from ortools.linear_solver import pywraplp

# Create the mip solver with the CBC backend.
solver = pywraplp.Solver('simple_mip_program',
    pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)


#Définition constante=================================================================

#Volume d'article
a = [3,4,6,1,5]
#valeur
c = [6,7,8,1,4]
#Capacité du sac à dos
b = 12

#Définition variable=================================================================

# 1:Choisir/ 0:Non séléctionné
x = {}
for j in range(5):
    x[j] = solver.BoolVar("x%i" % j)

#Expression de contrainte===================================================================

#La somme des volumes des articles sélectionnés ne doit pas dépasser la capacité du sac à dos
solver.Add(solver.Sum([a[j] * x[j] for j in range(len(a))]) <= 12)

#Fonction objective(Maximiser)
#Déterminez la combinaison d'éléments qui maximise la somme des valeurs
solver.Maximize(solver.Sum([c[j] * x[j] for j in range(len(a))]))

#Exécution de la solution
status = solver.Solve()

if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
    print('Solution:')
    print('ok')
    print('Objective value =', solver.Objective().Value())
    print("culculate Time = ", solver.WallTime(), " milliseconds")

    #Élément à sélectionner
    print('select item')
    for j in range(len(a)):
        print(j,x[j].solution_value())
    
    #valeur
    print('total value')
    print(sum(c[j] * x[j].solution_value() for j in range(len(a))))

else:
    print('The problem does not have an optimal solution.')

: bow_and_arrow: Exposition

Cet article est basé sur les exercices décrits dans les textes de référence suivants sur l'optimisation mathématique.

■ Texte de référence "Optimisation mathématique du texte informatique" Takato Kuno, et al. [Auteur] Société de traitement de l'information [modifier |

: bow_and_arrow: Informations connexes

Autres articles liés

: triangular_flag_on_post: Résolution d'exercices de modèle d'optimisation mathématique avec les OR-Tools de Google (1) Le problème de remplissage de masse le plus simple https://qiita.com/ttlabo/items/7e8c93f387814f99931f

: triangular_flag_on_post: [Partie 1] Qu'est-ce que l'optimisation? - Matériel d'étude pour l'apprentissage de l'optimisation mathématique https://qiita.com/ttlabo/items/e6970c6e85cce9ff4e34

: bow_and_arrow: Opinions etc.

Si vous avez des opinions ou des corrections, veuillez nous en informer.