きっかけ

「洗濯物、干しておいて」と言われて、干しながら考えたもの。

洗濯物問題

座標 p=[-3, -2, -1, 0, 1, 2, 3] に重量 w=[7, 8, 9, 11, 13, 15, 17] の洗濯物を1つずつ順番に干した時に、重心位置の絶対値が最小になる干し方を求めよ

定式化

定式化の仕方については、組合せ最適化を使おうを参考のこと。

変数	$x_{ijk} \in \{0, 1\}$	$i$番目に位置$j$に洗濯物$k$を干すかどうか
	$y$	重心位置の絶対値
目的関数	$y$	$\rightarrow$ 最小
制約条件	$\sum^n_{i=0}{ \sum_j{ \sum_k{ p[j] ~ w[k] ~ x_{ijk}} } } \le y$	$\forall n \in \{0, 1, \dots \}$
	毎回置くこと全ての位置に置くこと全ての洗濯物を置くこと

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

位置座標0にはいつ置いてもいいので、最初に置くことにしている。また、次は左右どちらでもいいので、左に固定している。

結果表示

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

最適解は複数あるようなので、おそらく局所探索法などの近似解法の方が有効だろう。

追記

定式化において pandas を使うと下記のように見やすくなる。

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] # 座標
w = [5, 6, 7, 9, 10, 11, 12] # 重量
r = range(len(p)) # 範囲
m = LpProblem() # 数理モデル
t = pd.DataFrame([(i, j, k, addvar(cat=LpBinary))
    for i in r for j in r for k in r], columns=['順番', '位置', '重量', 'x'])
y = addvar() # 重心位置の絶対値
m += y # 目的関数
for n in r:
    m += Σ('順番=={n}') == 1 # 順番 n で置くこと
    m += Σ('位置=={n}') == 1 # 位置 n に置くこと
    m += Σ('重量=={n}') == 1 # 洗濯物 n を置くこと
    if n:
        # 重心位置の絶対値が y 以下
        m += Σ('順番<={n}', lambda q: p[q.位置] * w[q.重量] * q.x) <= y
        m += Σ('順番<={n}', lambda q: -p[q.位置] * w[q.重量] * q.x) <= y
m += Σ('順番==0 & 位置==3') == 1 # 順番 0 に 位置 3 に置くこと
m += Σ('順番==1 & 位置<=2') == 1 # 順番 1 に 位置が 2 以下に置くこと
m.solve()
print(LpStatus[m.status], value(m.objective))