[PYTHON] J'ai essayé d'optimiser le séchage du linge

Déclencheur

On m'a dit de «sécher le linge» et j'y ai pensé en le séchant.

Problème de lessive

Séchez le linge avec un poids w = [7, 8, 9, 11, 13, 15, 17] un par un aux coordonnées p = [-3, -2, -1, 0, 1, 2, 3]. Trouvez la méthode de séchage qui minimise la valeur absolue du centre de gravité lorsque

Formulation

Pour la méthode de formulation, reportez-vous à Utiliser l'optimisation des combinaisons.

Essayez de résoudre avec python

python

from pulp import * # pip install pulp
def addvar(lowBound=0, var_count=[0], *args, **kwargs):
    var_count[0] += 1
    return LpVariable('v%d' % var_count[0], lowBound=lowBound, *args, **kwargs)

p = [-3, -2, -1, 0, 1, 2, 3]
w = [5, 6, 7, 9, 10, 11, 12]
r = range(len(p))
m = LpProblem()
x = [[[addvar(cat=LpBinary) for _ in r] for _ in r] for _ in r]
y = addvar()
m += y
for n in r:
    m += lpSum(x[n][j][k] for j in r for k in r) == 1
    m += lpSum(x[i][n][k] for i in r for k in r) == 1
    m += lpSum(x[i][j][n] for i in r for j in r) == 1
    if n:
        m += lpSum(p[j] * w[k] * x[i][j][k]
                   for i in range(n+1) for j in r for k in r) <= y
        m += lpSum(-p[j] * w[k] * x[i][j][k]
                   for i in range(n+1) for j in r for k in r) <= y
m += lpSum(x[0][len(p) // 2][k] for k in r) == 1
m += lpSum(x[1][j][k] for j in range(len(p) // 2) for k in r) == 1
%time m.solve()
print(LpStatus[m.status], value(m.objective))
>>>
Wall time: 2 s
Optimal 10.0

Puisqu'il peut être placé à la coordonnée de position 0 à tout moment, il est placé en premier. De plus, le suivant peut être à gauche ou à droite, il est donc fixé à gauche.

Affichage des résultats

for i in r:
    for j in r:
        for k in r:
            if value(x[i][j][k]) > 0.5:
                print(i, j, k)
>>>
0 3 6
1 2 4
2 5 3
3 1 2
4 6 0
5 0 1
6 4 5

Puisqu'il semble y avoir plusieurs solutions optimales, une solution approximative telle qu'une méthode de recherche locale est probablement plus efficace.

Postscript

L'utilisation de pandas dans la formulation permet de voir plus facilement ce qui suit.

py3

import pandas as pd
from pulp import * # pip install pulp
def addvar(lowBound=0, var_count=[0], *args, **kwargs):
    var_count[0] += 1
    return LpVariable('v%d' % var_count[0], lowBound=lowBound, *args, **kwargs)
def Σ(s, f=None):
    if not f:
        return lpSum(t.query(s.format(**globals())).x)
    return lpSum(t.query(s.format(**globals())).apply(f, axis=1))

p = [-3, -2, -1, 0, 1, 2, 3] #Coordonner
w = [5, 6, 7, 9, 10, 11, 12] #poids
r = range(len(p)) #intervalle
m = LpProblem() #Modèle mathématique
t = pd.DataFrame([(i, j, k, addvar(cat=LpBinary))
    for i in r for j in r for k in r], columns=['Commande', 'position', 'poids', 'x'])
y = addvar() #Valeur absolue du centre de gravité
m += y #Fonction objective
for n in r:
    m += Σ('Commande=={n}') == 1 # Commande n で置くこと
    m += Σ('position=={n}') == 1 # position n に置くこと
    m += Σ('poids=={n}') == 1 #Mettre le linge n
    if n:
        #La valeur absolue du centre de gravité est y ou moins
        m += Σ('Commande<={n}', lambda q: p[q.position] * w[q.poids] * q.x) <= y
        m += Σ('Commande<={n}', lambda q: -p[q.position] * w[q.poids] * q.x) <= y
m += Σ('Commande==0 &position==3') == 1 # Commande 0 にposition 3 に置くこと
m += Σ('Commande==1 &position<=2') == 1 # Commande 1 にpositionが 2 以下に置くこと
m.solve()
print(LpStatus[m.status], value(m.objective))