背景

ノート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を色々変えたいときは、「ビンパッキング問題の解き方」のような工夫が必要かもしれません。