整数計画問題入門¶

1. はじめに¶

線形計画問題入門では、生産計画問題を

$$ \begin{align} \max \ \ & z = 3x_1 + 5x_2 \\ \text{s.t. } \ \ & x_1 + 7x_2 \leq 140, \quad 2x_1 + 4x_2 \leq 100, \quad 3x_1 + 2x_2 \leq 120, \\ & x_1 \geq 0, \ x_2 \geq 0 \end{align} $$

と定式化して解いた。本資料では、この定式化を一般形に抽象化する記法を学んだうえで、変数に整数条件を課した整数計画問題(integer programming problem)へ進む。整数計画問題の代表例としてナップサック問題を定式化し、0-1変数の表現力を見る。

学習目標¶

  1. 線形計画問題をシグマ記法による一般形で書ける。
  2. 線形計画問題と整数計画問題の違いを説明できる。
  3. ナップサック問題を0-1整数計画問題として定式化できる。

2. 記号による抽象化とシグマ記法¶

上の生産計画問題の定式化は、原料3つ、製品2つで、しかも表の数値のときの問題しか表せていない。どんな問題設定にも適用できる形式で表現するために、一般形による記述を導入する。

  1. 定数を記号($c_i, a_{ji}, b_j$)に置き換える。
  2. 変数の数を $n$、制約式の数を $m$ とする。
  3. 総和はシグマ($\Sigma$)で記述する。

$$ \begin{align} \max \ \ & z = \sum_{i=1}^{n} c_i x_i \\ \text{s.t. } \ \ & \sum_{i=1}^{n} a_{ji} x_i \leq b_j, \quad j = 1, \dots, m, \\ & x_i \geq 0, \quad i = 1, \dots, n. \end{align} $$

$\sum_{i=1}^{n} c_i x_i$ は「$c_1 x_1$ から $c_n x_n$ までを足し上げる」という意味であり、制約式は $m$ 本を1行で表している。生産計画問題は、この一般形に

$$ m = 3, \ n = 2, \quad c_1 = 3, \ c_2 = 5, \quad a_{11} = 1, \ a_{12} = 7, \ b_1 = 140, \quad a_{21} = 2, \ a_{22} = 4, \ b_2 = 100, \quad a_{31} = 3, \ a_{32} = 2, \ b_3 = 120 $$

を代入したものである。変数が10,000個、制約式が100,000本あっても、問題の記述はこの一般形で済む。記号で抽象化しておけば、問題設定(データ)が変わってもモデルはそのまま使える。実務ではこのデータの部分を表(CSVファイルなど)で管理し、プログラムで読み込んで定式化する。研究室の教材でも、係数はリストやCSVで持ち、モデルは一般形のまま書くという方針で統一している。

3. 線形計画問題と整数計画問題¶

線形計画問題と整数計画問題は、目的関数と制約条件が1次式で表される点は同じであり、変数の取れる値だけが違う。

変数 得意なこと 苦手なこと
線形計画問題 実数 大規模でも現実的な時間で解ける 個数や状態(選ぶ/選ばない)を表せない
整数計画問題 整数 モノの個数や状態を表現できる 大規模だと現実的な時間で解けない

実数の変数で表せるのは連続的な量(液体の量、時間など)だけであり、「何個作るか」「選ぶか選ばないか」のような数え上げは整数の変数でなければ表せない。一方で、整数条件が入ると問題は格段に難しくなる。線形計画問題の最適解を丸めて整数にしても整数計画問題の最適解になるとは限らないことは、ビンパッキング問題入門の第3節で実際に確かめている。

整数計画問題を厳密に解く代表的なアルゴリズムが分枝限定法(branch and bound method)である。詳しい仕組みは授業で扱う。以降では、整数計画問題ならではの定式化の道具である0-1変数を、ナップサック問題を通じて学ぶ。

4. 整数計画問題の一例: ナップサック問題¶

次のような問題を考えてみる。貨物輸送にあたり、箱にいくつかの品物を効率よく詰め込みたい。

  • 品物は $n$ 個あり、各品物には $1 \sim n$ の番号が付与されている。
  • 品物 $i$ の重さを $a_i$ [kg]、輸送価値を $c_i$ とする($i = 1, \dots, n$)。
  • 箱には $b$ [kg] までしか品物を詰めることができない。

このとき、輸送価値の合計を最大化するにはどの品物を選べばよいか。具体例として次のデータを使う(品物名は対応表であり、モデルの中では品物IDだけを使う)。

品物ID 品物名 1個あたりの価値 $c_i$ 1個あたりの重さ $a_i$ [kg]
1 書籍セット 120 10
2 ワークステーション 250 21
3 プリンター 185 16
4 モニター 100 9
5 バッテリー 130 12
6 ケーブル 80 7

箱の容量は $b = 60$ [kg] とする。

4.1 変数の定義¶

この問題は「品物 $i$ を箱に入れるか、入れないか」を決める問題である。そこで品物 $i$ の状態を表す変数 $x_i$ を

$$ x_i = \begin{cases} 1: \ \text{品物} i \text{を箱に入れる} \\ 0: \ \text{その他} \end{cases} $$

と定義する。決定変数が0か1しか取らない問題は0-1整数計画問題と呼ばれ、実務上よく用いられる。

4.2 目的関数と制約条件¶

目的は「箱に入れる品物の価値の合計の最大化」である。品物 $i$ の価値 $c_i$ と $x_i$ の積を足し合わせると、選ばれた品物($x_i = 1$)の価値だけが合計に加算され、選ばれなかった品物($x_i = 0$)は無視される。条件は「箱に入れる品物の重さの合計が容量以下」であり、同じ仕掛けで $a_i x_i$ の総和が $b$ 以下と書ける。まとめると次のようになる。

$$ \begin{align} \max \ \ & z = \sum_{i=1}^{n} c_i x_i \\ \text{s.t. } \ \ & \sum_{i=1}^{n} a_i x_i \leq b, \\ & x_i \in \{0, 1\}, \quad i = 1, \dots, n. \end{align} $$

表の値を代入して展開すると

$$ \begin{align} \max \ \ & z = 120x_1 + 250x_2 + 185x_3 + 100x_4 + 130x_5 + 80x_6 \\ \text{s.t. } \ \ & 10x_1 + 21x_2 + 16x_3 + 9x_4 + 12x_5 + 7x_6 \leq 60, \\ & x_i \in \{0, 1\}, \quad i = 1, \dots, 6 \end{align} $$

である。ナップサック問題以外の0-1整数計画問題も、基本的にこれと類似の形に帰着する。

4.3 PuLP で解く¶

PuLP による実装手順(CSVからのデータ読み込み、LPファイルの出力を含む)はナップサック問題入門で丁寧に扱っているので、ここでは結果の確認だけ行う。なおGoogle Colab で実行する際には、次のセルの2行目のコメントを外して実行すること。

In [1]:
# Google Colab の場合は2行目のコメントを外して実行: ライブラリインストール(1回だけ)
# !pip install pulp
In [2]:
import pulp

c = [120, 250, 185, 100, 130, 80]  # 品物の価値
a = [10, 21, 16, 9, 12, 7]         # 品物の重さ [kg]
b = 60                             # 箱の容量 [kg]
n = len(c)

prob = pulp.LpProblem('knapsack', pulp.LpMaximize)
x = [pulp.LpVariable(f'x_{i + 1}', cat=pulp.LpBinary) for i in range(n)]
prob += pulp.lpSum(c[i] * x[i] for i in range(n))
prob += pulp.lpSum(a[i] * x[i] for i in range(n)) <= b

prob.solve(pulp.PULP_CBC_CMD(msg=0))
print('求解結果:', pulp.LpStatus[prob.status])
print('選んだ品物:', [i + 1 for i in range(n) if x[i].varValue > 0.5])
print('合計重量:', sum(a[i] for i in range(n) if x[i].varValue > 0.5), '[kg]')
print('最大の合計価値: z =', int(pulp.value(prob.objective)))

求解結果: Optimal
選んだ品物: [1, 2, 3, 5]
合計重量: 59 [kg]
最大の合計価値: z = 685

最適解は品物1、2、3、5(書籍セット、ワークステーション、プリンター、バッテリー)を選ぶ組合せであり、合計重量59 kg、合計価値685である。

5. 0-1変数による表現¶

0-1変数は非常に強力で、添え字を増やすことで多種多様な状態を表現できる。

  • 製品 $i$ を生産するか、しないか: $x_i$
  • 地域 $i$ に商業施設 $j$ を建築するか、しないか: $x_{ij}$
  • 従業員 $i$ を曜日 $w$ の時間 $t$ のシフトに割り当てるか、割り当てないか: $x_{iwt}$

例えば $x_{ij}$ は地域と施設の組合せの数($m \times n$ 個)だけ変数を用意することになる。研究室で扱う施設配置問題(LSCP、MCLP、FCLM など)や時間割編成問題は、すべてこの0-1変数による表現の上に成り立っている。

6. 課題¶

ビンパッキング問題を定式化する。$n$ 個の荷物があり、荷物 $j$ のサイズを $s_j$ とする。$n$ 個の荷物を、容量が $S$ の容器に詰め込むことを考える。すべての荷物を詰め込むために複数の容器を使うことができる。ただし、1つの容器に詰め込む荷物サイズの合計は $S$ を超えてはいけない。容器は $m$ 個あり、どれもサイズは $S$ とする。$n$ 個すべての荷物を詰め込むのに必要な、最小の容器の個数を求める問題を、整数計画問題として定式化せよ。

ヒントを挙げる。

  • 決定変数は2種類必要である。「荷物 $j$ を容器 $i$ に詰めるか/詰めないか」を表す $x_{ij}$ と、「容器 $i$ を使うか/使わないか」を表す $y_i$ である。
  • 制約条件は、「容器 $i$ に詰める荷物サイズの合計($s_j x_{ij}$ の和)は $S y_i$ 以下」と「荷物 $j$ は必ず1つの容器に詰め込む($x_{ij}$ の容器についての合計が必ず1)」の2種類である。
  • 目的関数は $y_i$ の合計の最小化である。

定式化ができたら、ビンパッキング問題入門に進むこと。そこでは容器ごとに容量が異なる一般形の定式化と、PuLP による実装、数値例を使った課題を扱っている。

7. 注意事項¶

  • 「なぜ右辺が $S y_i$ なのか($S$ ではだめなのか)」を、$y_i = 0$ と $y_i = 1$ を代入して確かめること。この仕掛けはビンパッキング問題入門の第4節でも解説している。
  • 理解できない場合には指導教員まで相談すること。