背景
ノートPCでオンライン会議をしようとしています。
ノートPCの位置が低いので、カメラの角度が下からになっています。
急いでノートPCの高さを高くしたいのですが、手元で使えるのがいくつかの書籍しかないです。
ノートPCは書籍より大きいので、書籍を2列に積む必要があります。また、2列の書籍の高さが違うとバランスが悪いので、2列の書籍の高さは同じくらいにしたいです。
問題
いくつかの書籍を2列に積んでなるべく高くしてください。
そのとき2列の書籍の高さの差は1ミリメートルまでにしてください。
考え方
組合せ最適化を使って解きます。
手順としては、問題を定式化して、Pythonでモデルを作成してソルバーで解きます。
「最適化におけるPython」も参考にしてください。
定式化
- 入力パラメーター
-
books：各書籍の高さ -
limit：2列の高さの差の上限
-
- 変数
-
obj：2列の高さのうち低い方 -
suml：左の列の高さ -
sumr：右の列の高さ -
vl：各書籍ごとに左の列に積むかどうか（0:積まない、1:積む） -
vr：各書籍ごとに右の列に積むかどうか（0:積まない、1:積む）
-
- 目的関数：2列の高さのうち低い方を最大化
- 制約条件
-
objはsumlとsumrのうち小さい方（1） -
sumlは左の列の高さ（2） -
sumrは右の列の高さ（3） -
sumlとsumrの差がlimit以下（4） - 書籍は左右のどちらかにしか置けない（5）
-
Pythonで解いてみよう
入力パラメーターは、乱数で適当に作成します。
import random
from ortoolpy import model_max, addvars, addbinvars, lpDot, value
random.seed(1)
books = [random.randint(10, 20) for _ in range(20)] # 本の厚さ（ミリメートル）
limit = 1 # 左右の高さの差の許容値（ミリメートル）
n = len(books)
m = model_max() # 数理モデル
obj, suml, sumr = addvars(3) # 低い方の高さ、左の高さ、右の高さ
vl = addbinvars(n) # 左に本を置くか
vr = addbinvars(n) # 右に本を置くか
m += obj # 目的関数（なるべく高くする）
m += obj <= suml # (1)
m += obj <= sumr # (1)
m += suml == lpDot(books, vl) # (2)
m += sumr == lpDot(books, vr) # (3)
m += suml - sumr <= limit # (4)
m += sumr - suml <= limit # (4)
for vli, vri in zip(vl, vr):
m += vli + vri <= 1 # (5)
m.solve() # ソルバーで求解
print(f'{m.status = }')
print(f'{value(suml) = }')
print(f'{value(sumr) = }')
print(f'{[int(value(vli) - value(vri)) for vli, vri in zip(vl, vr)]}')
lpDot(X, Y)は、XとYの内積です。つまりlpDot(books, vl)は、左の列の高さになります。
出力
m.status = 1
value(suml) = 149.0
value(sumr) = 148.0
[-1, -1, -1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, -1, -1, 1, 1, -1]
m.status = 1は「最適解が得られている」という意味です。
value(X)は変数Xの値を取得します。
左の列の高さは149ミリメートル、右の列の高さは148ミリメートルで、差は1ミリメートルになっています。
最後のリストは、1が左の列に置いて、-1が右の列に置くことを表しています。
余談
上記は0.1秒で計算できますが、limitを0にすると、計算時間は24秒になります（240倍）。
このように、組合せ最適化では、ちょっとパラメーターが変わると計算時間が大きく変わることがあります。
limitを色々変えたいときは、「ビンパッキング問題の解き方」のような工夫が必要かもしれません。