[PYTHON] I tried to optimize while drying the laundry

Trigger

I was told to "dry the laundry" and thought about it while drying it.

Laundry problem

Dry the laundry with the weight w = [7, 8, 9, 11, 13, 15, 17] one by one at the coordinates p = [-3, -2, -1, 0, 1, 2, 3]. Find the drying method that minimizes the absolute value of the center of gravity when

Formulation

For the formulation method, refer to Use Combinatorial Optimization.

Try to solve with 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

Since it can be placed at position coordinate 0 at any time, it is placed first. Also, the next one can be left or right, so it is fixed to the left.

Result display

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

Since there seem to be multiple optimal solutions, an approximate solution such as a local search method is probably more effective.

Postscript

Using pandas in the formulation makes it easier to see as follows.

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] #Coordinate
w = [5, 6, 7, 9, 10, 11, 12] #weight
r = range(len(p)) #range
m = LpProblem() #Mathematical model
t = pd.DataFrame([(i, j, k, addvar(cat=LpBinary))
    for i in r for j in r for k in r], columns=['Order', 'position', 'weight', 'x'])
y = addvar() #Absolute value of the center of gravity position
m += y #Objective function
for n in r:
    m += Σ('Order=={n}') == 1 # Order n で置くこと
    m += Σ('position=={n}') == 1 # position n に置くこと
    m += Σ('weight=={n}') == 1 #Putting laundry n
    if n:
        #The absolute value of the center of gravity position is y or less
        m += Σ('Order<={n}', lambda q: p[q.position] * w[q.weight] * q.x) <= y
        m += Σ('Order<={n}', lambda q: -p[q.position] * w[q.weight] * q.x) <= y
m += Σ('Order==0 &position==3') == 1 # Order 0 にposition 3 に置くこと
m += Σ('Order==1 &position<=2') == 1 # Order 1 にpositionが 2 以下に置くこと
m.solve()
print(LpStatus[m.status], value(m.objective))