Python en optimisation

introduction

Dans mon entreprise, je développe des logiciels utilisant la technologie d'optimisation des combinaisons (par exemple, minimiser les coûts de transport en logistique). Dans le passé, je créais des modèles d'optimisation en utilisant C ++ et C #, mais de nos jours, j'utilise souvent Python. Ici, nous allons introduire Python dans l'optimisation.

Avantages de Python

Les raisons d'utiliser Python sont les suivantes.

--Facile à comprendre. Le modèle par formule mathématique et le modèle par Python étant proches, vous pouvez vous concentrer sur une description plus essentielle et créer un modèle facile à maintenir. sample.png

On dit que Python s'exécute plus lentement que les langages de compilation tels que C ++. Cependant, en optimisation, Python est principalement utilisé pour la création de modèles (modélisation), et un logiciel dédié (solveur) écrit en C ++ etc. est utilisé pour l'exécution d'algorithmes d'optimisation. Par conséquent, même si vous utilisez Python pour l'optimisation, le temps d'exécution n'a pas beaucoup d'importance.

La modélisation d'optimisation utilise principalement les packages PuLP et pandas.

--PuLP est un package de modélisation mathématique et pandas est un package d'analyse de données. --Pandas convient au traitement des données qui peuvent être représentées dans un tableau parmi les données incluses dans le modèle, et peut décrire un traitement compliqué d'une manière facile à comprendre. De plus, les pandas utilisent numpy en interne. --Numpy utilise une bibliothèque d'algèbre linéaire hautement optimisée écrite en C ou Fortran et peut calculer efficacement les calculs matriciels.

À propos de PuLP

Pour résoudre le problème d'optimisation mathématique, procédez comme suit:

--Créer un modèle mathématique avec le modeleur

Solver est un logiciel qui prend un modèle mathématique en entrée, résout le modèle mathématique et génère la valeur (solution) d'une variable.

image.png

PuLP est un logiciel créé par le projet COIN et sera un modeleur. Avec PuLP, vous pouvez utiliser divers solveurs tels que CBC, Gurobi et GLPK. Par défaut, CBC est utilisé. Lorsque vous installez PuLP, CBC est installé en même temps.

--CBC: COIN Project Free Solver (abréviation de COIN-OR Branch and Cut) https://projects.coin-or.org/Cbc --Gurobi: solveur commercial haute performance http://www.gurobi.com/ --GLPK: solveur gratuit GNU www.gnu.org/software/glpk/

Le problème que PuLP peut gérer est le problème d'optimisation des nombres entiers mixtes. Le problème d'optimisation d'entiers mixtes est un type de problème d'optimisation mathématique et présente les caractéristiques suivantes.

--Représenté à l'aide de variables continues (nombre réel) et de variables entières

Si vous souhaitez en savoir plus, veuillez consulter le site de référence.

Comment utiliser PuLP

Considérez le problème suivant.

problème


Je souhaite créer beaucoup de produits chimiques X et Y qui peuvent être synthétisés à partir des matériaux A et B.
Pour faire 1 kg de X, il vous faut 1 kg de A et 3 kg de B.
Pour faire 1 kg de Y, il vous faut 2 kg de A et 1 kg de B.
Le prix de X et Y est de 100 yens par kg.
Pour maximiser la somme des prix de X et Y lorsque le matériau A ne pèse que 16 kg et B ne pèse que 18 kg
Découvrez combien de X et de Y doivent être créés.

prob.png

Le modèle mathématique du problème est le suivant. Représenter un modèle mathématique avec une expression s'appelle la formalisation.

formula.png

Modélisons cela avec PuLP et résolvons-le.

python3


from pulp import *
m = LpProblem(sense=LpMaximize) #Modèle mathématique
x = LpVariable('x', lowBound=0) #variable
y = LpVariable('y', lowBound=0) #variable
m += 100 * x + 100 * y #Fonction objective
m += x + 2 * y <= 16 #Contrainte limite supérieure du matériau A
m += 3 * x + y <= 18 #Contrainte limite supérieure du matériau B
m.solve() #Exécutez le solveur
print(value(x), value(y)) # 4, 6

Ce qui suit est une brève explication dans l'ordre.

Importation de package

from pulp import *

Créer un modèle mathématique

Pour les problèmes de minimisation: m = LpPrblem () Pour les problèmes de maximisation: m = LpProblem (sense = LpMaximize)

Créer des variables

Variable continue: x = LpVariable (nom de la variable, lowBound = 0) 0-1 Variable: x = LpVariable (nom de la variable, cat = LpBinary) Liste des variables continues: x = [LpVariable (i-ième nom de variable, lowBound = 0) pour i dans la plage (n)] Les noms de variable doivent être différents

Définition de la fonction objectif

m + = expression

Ajouter une condition de contrainte

m + = expression == expression m + = expression <= expression m + = expression> = expression

Exemple d'expression

2 * x + 3 * y - 5

Sum: lpSum (liste de variables) Produit interne: lpDot (liste des coefficients, liste des variables)

Exécutez le solveur

m.solve()

Valeurs des variables, expressions et fonctions objectives

valeur (variable), valeur (expression), valeur (m.objectif)

À propos de la combinaison de PuLP et de pandas

Combiner PuLP et pandas et gérer les variables (LpVariable) dans une table pandas (DataFrame) rend la formulation plus facile à comprendre.

Prenons l'exemple du problème de l'optimisation des transports.

Problème d'optimisation du transport

Je souhaite transporter des pièces d'un groupe d'entrepôts vers un groupe d'usines. J'aimerais trouver un plan qui minimise les frais de transport.

--Je souhaite déterminer la quantité de transport du groupe de magasins au groupe d'usine → Variable --Je veux minimiser les frais de transport → Fonction objective

Frais de transport Usine de montage
F1 F2 F3 F4 Approvisionnement
Entrepôt W1 10 10 11 17 35
W21619121441
W31512141242
Demande 28 29 31 25

Paramètres des paramètres

Définissez les paramètres requis. (Les chiffres sont les mêmes que dans le tableau précédent)

python3


import numpy as np, pandas as pd
from itertools import product
from pulp import *
np.random.seed(1)
nw, nf = 3, 4
pr = list(product(range(nw),range(nf)))
La fourniture= np.random.randint(30, 50, nw)
demande= np.random.randint(20, 40, nf)
Les frais de livraison= np.random.randint(10, 20, (nw,nf))

Modèle mathématique sans pandas

Les variables sont accessibles par des indices.

python3


m1 = LpProblem()
v1 = {(i,j):LpVariable('v%d_%d'%(i,j), lowBound=0) for i,j in pr}
m1 += lpSum(Les frais de livraison[i][j] * v1[i,j] for i,j in pr)
for i in range(nw):
    m1 += lpSum(v1[i,j] for j in range(nf)) <=La fourniture[i]
for j in range(nf):
    m1 += lpSum(v1[i,j] for i in range(nw)) >=demande[j]
m1.solve()
{k:value(x) for k,x in v1.items() if value(x) > 0}
>>>
{(0, 0): 28.0,
 (0, 1): 7.0,
 (1, 2): 31.0,
 (1, 3): 5.0,
 (2, 1): 22.0,
 (2, 3): 20.0}

Modèle mathématique utilisant des pandas

Les variables sont accessibles par les attributs de table. Commençons par créer une table.

python3


a = pd.DataFrame([(i,j) for i, j in pr], columns=['Entrepôt', 'usine'])
a['Les frais de livraison'] = Les frais de livraison.flatten()
a[:3]
Entrepôt Usine Frais de transport
00010
10110
20211

Faisons un modèle mathématique de la même manière.

python3


m2 = LpProblem()
a['Var'] = [LpVariable('v%d'%i, lowBound=0) for i in a.index]
m2 += lpDot(a.Les frais de livraison, a.Var)
for k, v in a.groupby('Entrepôt'):
    m2 += lpSum(v.Var) <=La fourniture[k]
for k, v in a.groupby('usine'):
    m2 += lpSum(v.Var) >=demande[k]
m2.solve()
a['Val'] = a.Var.apply(value)
a[a.Val > 0]
Entrepôt Usine Frais de transport Var Val
0 0 0 10 v0 28.0
1 0 1 10 v1 7.0
6 1 2 12 v6 31.0
7 1 3 14 v7 5.0
9 2 1 12 v9 22.0
11 2 3 12 v11 20.0

Les expressions utilisant des indices devaient se souvenir de la signification des indices. Cependant, la combinaison de PuLP et de pandas rend le modèle mathématique plus facile à comprendre, comme indiqué ci-dessous.

Site de référence

c'est tout

Recommended Posts

Python en optimisation
Résoudre les problèmes d'optimisation avec Python
Quadtree en Python --2
CURL en Python
Métaprogrammation avec Python
Python 3.3 avec Anaconda
Géocodage en python
SendKeys en Python
Méta-analyse en Python
Unittest en Python
Optimisation des paramètres de systole FX en Python
GPyOpt, un package d'optimisation bayésienne en Python
Époque en Python
Discord en Python
Allemand en Python
DCI en Python
tri rapide en python
nCr en python
N-Gram en Python
Programmation avec Python
Plink en Python
Constante en Python
FizzBuzz en Python
Sqlite en Python
Étape AIC en Python
LINE-Bot [0] en Python
CSV en Python
Assemblage inversé avec Python
Réflexion en Python
Constante en Python
nCr en Python.
format en python
Scons en Python 3
Puyopuyo en python
python dans virtualenv
PPAP en Python
Quad-tree en Python
Réflexion en Python
Chimie avec Python
Hashable en Python
DirectLiNGAM en Python
LiNGAM en Python
Aplatir en Python
Aplatir en python
J'ai essayé d'utiliser l'optimisation bayésienne de Python
Liste triée en Python
AtCoder # 36 quotidien avec Python
Texte de cluster en Python
AtCoder # 2 tous les jours avec Python
Daily AtCoder # 32 en Python
Daily AtCoder # 6 en Python
Daily AtCoder # 18 en Python
Modifier les polices en Python
Motif singleton en Python
Opérations sur les fichiers en Python
Lire DXF avec python
Daily AtCoder # 53 en Python
Séquence de touches en Python