切出し問題（Cutting Stock Problem）

固定長 $L$ の同一の棒が $M$ 本と、ペア $(l_j,c_j)$ ($0\leq j\leq N-1$) で指定される $N$ 件の注文が与えられるとします。ここで $l_j$ は必要な長さ、$c_j$ は注文 $j$ の必要数量です。 切出し問題は、$M$ 本の棒をどのように切断すればすべての注文を満たせるかを決定することを目的とします。

一般に、切出し問題は使用する棒の本数を最小化する最小化問題として定式化されます。 簡単のため、この例では $M$ 本の棒で $N$ 件のすべての注文を満たせるかどうかを判定する実行可能性問題を考えます。

$x_{i,j}$ ($0\leq i\leq M-1, 0\leq j\leq N-1$) を棒 $i$ から切り出す注文 $j$ のピース数とします。 以下の制約を満たす必要があります。

注文制約：

各注文 $j$ について、すべての棒に割り当てられたピースの合計は $c_j$ に等しくなければなりません：

\[\begin{aligned} \sum_{i=0}^{M-1}x_{i,j} &= c_j & &(0\leq j\leq N-1) \end{aligned}\]

棒制約

各棒 $i$ について、割り当てられたピースの合計長は $L$ を超えてはなりません：

\[\begin{aligned} \sum_{j=0}^{N-1}l_jx_{i,j} &\leq L & &(0\leq i\leq M-1) \end{aligned}\]

PyQBPPプログラム

以下のPyQBPPプログラムは、長さ $L=60$ の $M=6$ 本の棒と以下の $N=4$ 件の注文に対する実行可能な切断計画を求めます：

注文 $j$	0	1	2	3
長さ $l_j$	13	23	8	11
数量 $c_j$	10	4	8	6

この切出し問題のPyQBPPプログラムは以下のとおりです：

import pyqbpp as qbpp

L = 60
l = qbpp.array([13, 23, 8, 11])
c = qbpp.array([10, 4, 8, 6])
N = len(l)
M = 6

# 棒 i から切り出される注文 j のピース数を表す整数変数 x[i][j] を生成
upper = [[c[j] for j in range(N)] for i in range(M)]
x = qbpp.var("x", shape=(M, N), between=(0, upper))

# 注文制約：各注文について合計ピース数が c[j] と等しくなければならない
order_fulfilled_count = qbpp.vector_sum(x, axis=0)
order_constraint = order_fulfilled_count == c

# 棒制約：各棒で使用される合計長は L を超えてはならない
bar_length_used = qbpp.expr(shape=M)
for i in range(M):
    bar_length_used[i] = qbpp.sum(x[i] * l)
bar_constraint = (0 <= bar_length_used) & (qbpp.same <= L)

f = qbpp.sum(order_constraint) + qbpp.sum(bar_constraint)
f.simplify_as_binary()

solver = qbpp.EasySolver(f)
sol = solver.search(time_limit=10.0, target_energy=0)

for i in range(M):
    pieces = "  ".join(str(sol(x[i][j])) for j in range(N))
    used = sol(bar_length_used[i])
    print(f"Bar {i}:  {pieces}   used = {used}, waste = {L - used}")

for j in range(N):
    fulfilled = sol(order_fulfilled_count[j])
    print(f"Order {j} fulfilled = {fulfilled}, required = {c[j]}")

このプログラムは整数変数の M$\times$N 行列 x を作成します。 upper は各要素 upper[i][j] が c[j] である M$\times$N の入れ子のリストで、これを qbpp.var("x", shape=(M, N), between=(0, upper)) の上限に渡すと、各エントリ x[i][j] は c[j] 以下の非負整数値をとります。

制約は以下のように定義されます：

• order_fulfilled_count: qbpp.vector_sum(x, axis=0) で x の列ごとの和をとった $N$ 個の式の配列で、order_fulfilled_count[j] は注文 $j$ について生産されたピースの合計数を表します。
• order_constraint: すべての $j$ に対して order_fulfilled_count[j] == c[j] を強制する $N$ 個の制約式の配列です。
• bar_length_used: $M$ 個の式の配列で、bar_length_used[i] は棒 $i$ で使用された合計長 qbpp.sum(x[i] * l) を表します。
• bar_constraint: すべての $i$ に対して 0 <= bar_length_used[i] <= L を強制する $M$ 個の制約式の配列です。
• f: qbpp.sum() で合計した、すべての制約式の和です。f.simplify_as_binary() を呼び出した後、Easy Solverはターゲットエネルギー0（すなわちすべての制約が満たされた状態）の解を探索します。

以下の出力は実行可能解の例です：

Bar 0:  2  0  0  3   used = 59, waste = 1
Bar 1:  4  0  1  0   used = 60, waste = 0
Bar 2:  1  1  3  0   used = 60, waste = 0
Bar 3:  0  0  4  2   used = 54, waste = 6
Bar 4:  2  1  0  1   used = 60, waste = 0
Bar 5:  1  2  0  0   used = 59, waste = 1
Order 0 fulfilled = 10, required = 10
Order 1 fulfilled = 4, required = 4
Order 2 fulfilled = 8, required = 8
Order 3 fulfilled = 6, required = 6

$N=4$ 件のすべての注文が $M=6$ 本の棒で満たされていることがわかります。

$M=5$ に設定すると、ソルバーは以下の実行不可能な解を返し、すべての注文が満たされていません：

Bar 0:  4  0  1  0   used = 60, waste = 0
Bar 1:  0  0  6  1   used = 59, waste = 1
Bar 2:  2  1  0  1   used = 60, waste = 0
Bar 3:  2  0  0  3   used = 59, waste = 1
Bar 4:  1  2  0  0   used = 59, waste = 1
Order 0 fulfilled = 9, required = 10
Order 1 fulfilled = 3, required = 4
Order 2 fulfilled = 7, required = 8
Order 3 fulfilled = 5, required = 6

qbpp.cons() で制約を表す

注文制約と長さ制約は、qbpp.cons() で囲むことで制約として印を付けられます。 変更は、制約の配列を qbpp.cons() で囲むことと、整数変数を integer= で宣言するネイティブ整数変数にすることです。ネイティブ整数変数はバイナリ変数に展開されず、ソルバーが整数のまま探索します。 qbpp.cons() は制約の配列を合計するので、qbpp.sum(...) は不要になります。 sol(bar_length_used[i]) や sol(order_fulfilled_count[j]) による報告を含む 残りの部分はそのままです:

import pyqbpp as qbpp

L = 60
l = qbpp.array([13, 23, 8, 11])
c = qbpp.array([10, 4, 8, 6])
N = len(l)
M = 6

# 各バー i から切り出す注文 j の個数を表す整数変数 x[i][j] を作成
upper = [[c[j] for j in range(N)] for i in range(M)]
x = qbpp.var("x", shape=(M, N), integer=(0, upper))

# 注文制約: 各注文の総個数は c[j] と等しくなければならない
order_fulfilled_count = qbpp.vector_sum(x, axis=0)
order_constraint = qbpp.cons(order_fulfilled_count == c)

# 長さ制約: 各バーで使用する総長は L を超えてはならない
bar_length_used = qbpp.expr(shape=M)
for i in range(M):
    bar_length_used[i] = qbpp.sum(x[i] * l)
bar_constraint = qbpp.cons((0 <= bar_length_used) & (qbpp.same <= L))

f = order_constraint + bar_constraint
f.simplify()

solver = qbpp.EasySolver(f)
sol = solver.search(time_limit=10.0, target_energy=0)

for i in range(M):
    pieces = "  ".join(str(sol(x[i][j])) for j in range(N))
    used = sol(bar_length_used[i])
    print(f"Bar {i}:  {pieces}   used = {used}, waste = {L - used}")

for j in range(N):
    fulfilled = sol(order_fulfilled_count[j])
    print(f"Order {j} fulfilled = {fulfilled}, required = {c[j]}")

このプログラムは、例えば次のような実行可能な切り出し計画を見つけます:

Bar 0:  3  0  1  1   used = 58, waste = 2
Bar 1:  2  1  0  1   used = 60, waste = 0
Bar 2:  3  0  1  1   used = 58, waste = 2
Bar 3:  1  2  0  0   used = 59, waste = 1
Bar 4:  1  1  3  0   used = 60, waste = 0
Bar 5:  0  0  3  3   used = 57, waste = 3
Order 0 fulfilled = 10, required = 10
Order 1 fulfilled = 4, required = 4
Order 2 fulfilled = 8, required = 8
Order 3 fulfilled = 6, required = 6

2つの定式化は等価です。制約を qbpp.cons() で囲むことで、バンドルされた ソルバーがそれらを制約として扱います。f.cons(sol) は違反した制約の本数を 返します（実行可能な計画では 0）。