数分割問題
数分割問題(number partitioning problem)とは，以下のように定義される問題である．
$n$個のアイテムから成る有限集合 $N$ と個々のアイテム $i \in N$ のサイズ $w_i(\geq 0)$ が与えられたとき， アイテムの2分割で，各分割（以下ではこれを分割 $1,2$ とよぶ）に含まれているサイズの合計がなるべく均等になるものを求める．
問題を明確化するために，数分割問題を整数最適化問題として定式化しておく． アイテム$i$ が，分割$1$ に含まれているとき $1$， 分割$2$ に含まれているとき $0$ の $0$-$1$ 変数 $x_i$ を導入する． 問題の目的は，分割$1$ に含まれるアイテムのサイズの合計と，サイズの合計の半分 $T = \sum_{i \in N} w_i/2$ からのずれを 最小化することと言い換えることができる．$T$ との差を表す実数変数 $s$ を導入すると，数分割問題は以下のように定式化できる．
$$ \begin{array}{l l l} minimize & |s| & \\ s.t. & \sum_{i \in N} w_i x_i - s = T & \\ & x_i \in \{0,1\} & \forall i \in N \\ & s \in \mathbf{R} & \end{array} $$目的関数の絶対値は線形ではないが，2つの非負の実数変数 $s^+, s^- (\geq 0)$ を導入し， $$ s \leq s^+ $$ $$ -s \leq s^- $$ の制約の下で， $$ s^+ +s^- $$ を最小化することによって，線形に変形できる．
差分法
この近似解法は，Karmarkar-Karp によって1982年に提案されたものであり， 差分操作（differencing）を用いることから差分法（differencing method）とよばれている．
差分操作とは，2つのアイテムを異なる分割に入れることを決定することである． 具体的には，2つのアイテムのうち，サイズの大きい方から小さい方を引いたサイズをもつアイテムを生成し， もとの2つのアイテムを消去する． Karmarkar-Karpの差分法では，サイズの大きいアイテムを2つ選択し，差分操作を繰り返す． アルゴリズムは，以下のようになる．
- アイテムをサイズの大きい順に並べたリストを作る．
- 残りのアイテム数が $2$ 以上なら，以下を繰り返す：
- $i:=$ サイズが最大のアイテム
- $j:=$ 2番目にサイズが大きいアイテム
- サイズ $w_k:= w_i-w_j$ のアイテム $k$ を生成する．
- $i,j$ をリストから除き， $k$ を加える．
上のアルゴリズムは，サイズの大きい順にアイテムを保管するためのリストとしてヒープを用いれば $O(n \log n)$ 時間で終了する． 得られた解は，アルゴリズムの途中で，差分操作の際の情報を保管することによって復元できる．
コードを以下に示す．詳細については，拙著「メタヒューリスティクスの数理」（共立出版）を参照されたい．
data = [int(random.random() * 10000.0) for i in range(200)]
n = len(data)
print("differencing_construct: case of two partitions")
obj, p1, p2 = differencing_construct(data)
print("Objective function=", obj)
print(p1)
print(p2)
分割数が $3$以上の場合の差分法
ここでは，分割数 $m$ が $3$以上の場合の数分割問題を考える． まず，差分法の拡張を考えよう．
各分割にアイテムの部分集合を割り振ったものを部分解とよぶ． 各アイテムを適当な分割に割り振り，他の $m-1$個の分割はすべて空の部分解から始める． 各分割に割り振られたアイテムのサイズの合計を，分割のサイズとよぶ． 部分解は，分割のサイズを $m$ 個並べたものとして表現される． ここでは便宜上非減少順に並べるものとする． 最初の部分解は，$n$個（アイテムの個数）だけあり，$(0,0,\ldots,0,w_i)$ と表現される． 部分解のサイズを，最大の分割のサイズから最小の分割のサイズを減じたもの（分割のサイズの最大差）と定義する．
部分解を大きい順に保管するリスト（ヒープ）を作成し，大きいものから2つ取り出して差分操作を行う． 取り出した部分解を $x_1,x_2$ とする．新しい部分解は，分割のサイズの最大差を最小にするように， 以下のように生成される．$x_1$ の最もサイズの大きい分割と $x_2$ の最もサイズの小さい分割に含まれている アイテムを入れた新しい分割を生成する．次に，$x_1$ の2 番目に大きい分割と $x_2$ の2番目に小さい分割から 新しい分割を生成する．以下同様に繰り返し，最後に $x_1$ の最も小さい分割と $x_2$ の最も大きい分割を合わせる． このようにして生成された新しい部分解を $x_1, x_2$ のかわりにヒープに挿入し， ヒープに含まれる要素の数が $1$ になるまで繰り返す．
コードは以下のようになる．
def multi_differencing_construct(data, m):
"""partition a list of items with the differencing method for more than two partitions"""
n = len(data)
# create a heap to hold tuples with the information required by the algorithm
# each 3-tuple has (a,b,c) where
# a -- label
# b -- list of the lists of items on each partition
# c -- sum of the weights on each partition (for ordering them)
# eg: heap = [(-4, [[10], [8, 5], [14]], [10, 13, 14]), (-1, [[], [], [1]], [0, 0, 1]), ...]
# print("log of the execution with multi_differencing_construct:")
heap = []
for i in range(n):
datum = data[i]
part = [[] for p in range(m)] # initially, all partitions are empty
sums = [0 for p in range(m)]
part[-1].append(datum) # insert one item on the last partition
sums[-1] = datum # update the sum of weights for last partition
label = -datum # as the heap is in increasing order
heappush(heap, (label, part, sums))
# differencing method
while len(heap) > 1:
# join two elements with largest weights in the heap
label1, part1, sums1 = heappop(heap)
label2, part2, sums2 = heappop(heap)
# on each element sort the sets of items by the
# corresponding sum
tmp = []
for p in range(m):
part = part1[p] + part2[-1 - p] # join the lists of items by reverse order
sums = sums1[p] + sums2[-1 - p] # update the sum of weights in each list
tmp.append((sums, part))
tmp.sort() # sort by increasing order of weights
sums = [i for (i, _) in tmp] # extract the sum of item's weights
part = [p for (_, p) in tmp] # extract the lists of items
label = (
sums[0] - sums[-1]
) # the new label is the different between the farthest sums of weights
heappush(heap, (label, part, sums))
# last element of the heap has the two partitions, the sums
# difference between the two partitions (i.e., the objective)
obj, part, sums = heappop(heap)
obj = -obj
return obj, part, sums
複数装置スケジューリング問題
分割数 $m$が3以上の数分割問題は，$m$台の並列機械（同じ性能をもつ機械）にアイテムのサイズと同じ処理時間をもつジョブを割り当てる問題と考えることができる． ただし，ジョブの処理は途中で中断してはいけないものと考え，最後のジョブが完了する時刻を最小化することを目的とする． この問題は，複数装置スケジューリング問題（multi-processor scheduling problem）とよばれ，多くのヒューリスティクスが提案 されているが，ここでは最大処理時間ヒューリスティクス（longest processing time (LPT) heuristics）を紹介する．
まず，$m$台の装置に何もジョブが割り振られていない状態から開始する．この場合の，各装置の完了時刻はすべて $0$ である． 次に，ジョブを処理時間（数分割問題においてはアイテムのサイズ）の大きい順に並べ，順に取り出す． 取り出されたジョブが，最も完了時刻の早い（同点は適当に破る）装置に割り振られ，処理を開始する． 割り振られた装置の完了時刻は，ジョブの処理時間だけ大きくなる．この操作をすべてのジョブが割り振られるまで繰り返す．
このヒューリスティクスは，最悪の場合の性能保証が示された最初の例であり， 常に最適値の $\frac{4}{3}-\frac{1}{3m}$倍以下の近似値を算出することが 示されている． ちなみに，差分法も最適値の $\frac{4}{3}-\frac{1}{3m}$倍以下の近似値を算出することが示されている．
コードは以下のようになる．
分割数（機械の台数）が $5$ の場合の差分法と最大処理時間ヒューリスティクスを比較する．
m = 5
print(f"differencing_construct: case of {m} partitions")
obj, part, sums = multi_differencing_construct(data, m)
print("Obj=",obj, "Sums=",sums)
print("\nlongest processing time heuristic""")
obj, part, sums = longest_processing_time(data, m)
print("Obj=", obj, "Sums=",sums)
結果を図示する関数 show_nppを作り，結果を描画する．
obj, part, sums = multi_differencing_construct(data, m)
fig = show_npp(part)
plotly.offline.plot(fig);
obj, part, sums = longest_processing_time(data, m)
fig = show_npp(part)
plotly.offline.plot(fig);
ビンパッキング問題を利用した解法
数分割問題は，ビンパッキング問題と類似の構造をしている． ビンパッキング問題においては，ビンのサイズ（割り振られるアイテムのサイズの合計の上限）を固定して， ビンの個数（分割数）を最小化したが， 数分割問題においては，分割数 $m$ を固定して，分割に含まれるアイテムのサイズの合計を均等化する点が異なる．
ビンパッキングに対しては，以下のfirst fit decreasingヒューリスティクスが有効であることが知られている．
アイテムをサイズの非増加順に並べ，その順にビンに詰めていく． このとき，アイテムは詰め込み可能な最小添字のビンに詰めるものとする． どのビンに入れてもサイズの上限 $B$ を超えてしまうなら， 新たなビンを用意し，そこに詰める．
数分割問題は，ビンパッキング問題のfirst fit decreasingヒューリスティクスをサブルーチンとして解くことができる．この解法は，multifit法と呼ばれ，以下のように記述できる．
ビンのサイズ $B$ を適当な値にを固定すると，ビンの個数を最小化する問題は，ビンパッキング問題になる． これをfirst fit decreasingヒューリスティクスで解き， そのときのビンの数が分割数 $m$ より大きいときには，ビンのサイズを大きくし，小さいときにはビンのサイズを小さくして， 再びビンパッキング問題を解く．最良のビンのサイズは，適当な方法（たとえば2分探索）で得ることができるので， 分割数 $m$ に対する最小のビンのサイズが，数分割問題の近似解になる．
このヒューリスティクスに対する性能保証は，$m=2$ のとき $8/7$，$m=3$ のとき $15/13$，$m=4,5,6,7$ のとき $20/17$， $m \geq 8$ のとき $13/11$ であることが示されている． 差分法は，最悪値解析の観点ではmultifitにやや劣るが，平均的には最大処理時間ヒューリスティクスやmultifitより優れた性能を 示すことが知られている．
以下のコードのFFD（first fit decreasingヒューリスティクス）は，ビンパッキングの章で用いたものと同じである．
m = 5
obj, part, sums = multi_fit(data, m)
print("Obj=",obj, "Sums=", sums)
fig = show_npp(part)
plotly.offline.plot(fig);
