数理最適化セミナーのご案内

2.6 集合被覆問題

　集合Uとその部分集合の族および各部分集合に対応するコストが与えられているものとします．この時，全てのUの要素をカバーするように部分集合の族から部分集合を選び，その際にかかるコストを最小にするという問題が集合被覆問題です．応用例には乗務員スケジューリング問題などがあります．なお集合被覆問題の場合，Uの各要素について複数個の部分集合でカバーすることを許しています．このことに関連して，複数個の部分集合でカバーすることを許さない場合，集合分割問題と呼ばれ，選挙区の設定問題などに応用されています．

例題

　ある企業はA，B，C，D，E，F，Gの7つのエリアがある都市で宅配便の配達事業を始めるため，配達員を採用することになりました．この都市には配達員の候補は10人いて，各人が配達できるエリアおよび配達を依頼した際にかかるコストは次の表のようになっています．

候補者 配達可能エリア コスト
佐藤 A，B，C 200
鈴木 A，D，F 280
高橋 B，E 175
田中 C，D，E，F，G 560
渡辺 A，F 205
伊藤 B，D，F 245
山本 D 80
中村 C，G 195
小林 C，F，G 265
斉藤 B，E，G 190

　

　この時，最も少ないコストで7つのエリアすべてに配達するためには誰を採用すると良いでしょうか．ただし，配達可能エリアの一部のみを依頼する（例：伊藤にBとDのみ依頼する）ことはできないものとします．

　この例題の変数は，各候補者について「採用する」もしくは「採用しない」という状態を表現できるものとなります．よって，ここでは各候補者に対し採用する場合は1，採用しない場合は0を取るような変数$x_{(候補者)}$を導入します．

　この時，目的関数はどのように表すことができるでしょうか．まず，佐藤を例に実際にかかるコストを表現します．佐藤を採用した場合（$x_{佐藤} = 1$の場合）には200のコストがかかります．一方，採用しなかった場合（$x_{佐藤} = 0$の場合）は佐藤については何もコストがかかりません．言い換えると，かかったコストが0であるということになります．よって，先ほど導入した変数を用い2つの場合をまとめると，佐藤については実際には$200x_{佐藤}$のコストがかかったと表現できます．他の候補者に対しても同様に実際のコストを表し，その総和を取ると実際にかかった総コストとなります．この総コストが，最小化することになる目的関数です．

　制約条件については，「各エリアに1人以上配置されている」という条件を式で表現することになります．例えば，エリアAの場合佐藤・鈴木・渡辺の中から1人以上採用することで条件を満たすことができます．このことを式で表すと$x_{佐藤} + x_{鈴木} + x_{渡辺} \ge 1$となります．他のエリアについても同様に考えることで制約条件を表現できます．

　以上のことから，この例題は0-1整数計画問題として次のように定式化できます．

0-1変数
$x_{佐藤}$, $x_{鈴木}$, $x_{高橋}$, $x_{田中}$, $x_{渡辺}$, $x_{伊藤}$, $x_{山本}$, $x_{中村}$, $x_{小林}$, $x_{斉藤}$ 各候補者について採用する時1，採用しない時0を取る変数
　
目的関数（最小化）
$200x_{佐藤} + 280x_{鈴木} + 175x_{高橋} + 560x_{田中} + 205x_{渡辺} + 245x_{伊藤} + 80x_{山本} + 195x_{中村} + 265x_{小林} + 190x_{斉藤}$ 総コストの最小化
　
制約
$x_{佐藤} + x_{鈴木} + x_{渡辺} \ge 1$ エリアAで配達可能にする
$x_{佐藤} + x_{高橋} + x_{伊藤} + x_{斉藤} \ge 1$ エリアBで配達可能にする
$x_{佐藤} + x_{田中} + x_{中村} + x_{小林} \ge 1$ エリアCで配達可能にする
$x_{鈴木} + x_{田中} + x_{伊藤} + x_{山本} \ge 1$ エリアDで配達可能にする
$x_{高橋} + x_{田中} + x_{斉藤} \ge 1$ エリアEで配達可能にする
$x_{鈴木} + x_{田中} + x_{渡辺} + x_{伊藤} + x_{小林} \ge 1$ エリアFで配達可能にする
$x_{田中} + x_{中村} + x_{小林} + x_{斉藤} \ge 1$ エリアGで配達可能にする

　この定式化した結果についてそのままC++SIMPLEで記述すると次のようになります．

// 変数の宣言
IntegerVariable x_sato(name = "佐藤", type = binary);
IntegerVariable x_suzuki(name = "鈴木", type = binary);
IntegerVariable x_takahashi(name = "高橋", type = binary);
IntegerVariable x_tanaka(name = "田中", type = binary);
IntegerVariable x_watanabe(name = "渡辺", type = binary);
IntegerVariable x_ito(name = "伊藤", type = binary);
IntegerVariable x_yamamoto(name = "山本", type = binary);
IntegerVariable x_nakamura(name = "中村", type = binary);
IntegerVariable x_kobayashi(name = "小林", type = binary);
IntegerVariable x_saito(name = "斉藤", type = binary);

// 目的関数の設定
Objective total_cost(type = minimize);
total_cost = 200 * x_sato + 280 * x_suzuki + 175 * x_takahashi +
             560 * x_tanaka + 205 * x_watanabe + 245 * x_ito +
             80 * x_yamamoto + 195 * x_nakamura + 265 * x_kobayashi +
             190 * x_saito;

// 各エリアに 1 人以上配置する
x_sato + x_suzuki + x_watanabe >= 1;
x_sato + x_takahashi + x_ito + x_saito >= 1;
x_sato + x_tanaka + x_nakamura + x_kobayashi >= 1;
x_suzuki + x_tanaka + x_ito + x_yamamoto >= 1;
x_takahashi + x_tanaka + x_saito >= 1;
x_suzuki + x_tanaka + x_watanabe + x_ito + x_kobayashi >= 1;
x_tanaka + x_nakamura + x_kobayashi + x_saito >= 1;

// 終了条件に関する設定
options.maxtim = 10;

// 求解し解を出力する
solve();
x_sato.val.print();
x_suzuki.val.print();
x_takahashi.val.print();
x_tanaka.val.print();
x_watanabe.val.print();
x_ito.val.print();
x_yamamoto.val.print();
x_nakamura.val.print();
x_kobayashi.val.print();
x_saito.val.print();
total_cost.val.print();

　この記述を見て分かるように，このままですと修正が大変ですし汎用的でもありません．このため，汎用的になるように定式化した結果を見直すことにします．

　前節のナップサック問題の時と同様に「候補者の集合」および「エリアの集合」という概念を導入します．また，各候補者のコストは定数として外部から与えることにします．

　さらに，制約条件についても見直します．例えば，エリアAに1人以上配置されているという制約条件$x_{佐藤} + x_{鈴木} + x_{渡辺} \ge 1$については，ほかの候補者も考慮すると

\[1x_{佐藤} + 1x_{鈴木} + 0x_{高橋} + 0x_{田中} + 1x_{渡辺} + 0x_{伊藤} + 0x_{山本} + 0x_{中村} + 0x_{小林} + 0x_{斉藤} \ge 1\]

と記述できます．ここで，この式の各変数についている係数0または1を外部から定数として与えることにします．また，他の地域についても同様に定数を導入します．すると，各エリアに対する制約条件は全て同じ枠組みで定式化できます．その結果，C++SIMPLEでは一般的な形での記述で対応でき，よりわかりやすいものになります．

　以上のことを反映し，汎用化させた結果は以下のようになります．

集合
$Man = \{佐藤, 鈴木, 高橋, 田中, 渡辺, 伊藤, 山本, 中村, 小林, 斉藤\} $ 候補者集合
$Area = \{ A, B, C, D, E, F, G\} $ エリア集合
　
0-1変数
$x_i, i \in Man$ 候補者iを採用する時1，採用しない時0を取る変数
　
定数
$deliver_{\rm ij}, i \in Man, j \in Area$ 候補者iがエリアjに配達可能な時1，不可能な時0を取る
$cost_i, i \in Man$ 候補者iを採用した際のコスト
　
目的関数（最小化）
$\displaystyle \sum_{i \in Man} cost_i x_i$ 総コストの最小化
　
制約
$\displaystyle \sum_{i \in Man} deliver_{\rm ij} x_i \ge 1, \forall j \in Area$ すべてのエリアで配達可能になるようにする

　これをC++SIMPLEで記述すると，次のようになります．なお，制約条件についてはデータファイルの内容をもとに各エリアに対して自動的に生成されます．

// 集合と添字
Set Man;
Element i(set = Man);
Set Area;
Element j(set = Area);

// パラメータ
Parameter deliver(name = "配達可能エリア", index = (i, j));
Parameter cost(name = "コスト", index = i);

// 変数
IntegerVariable x(name="採用", index = i, type = binary);

// 目的関数
Objective total_cost(name = "総コスト", type = minimize);
total_cost = sum(cost[i] * x[i], i);

// 各エリアに配置する
sum(deliver[i, j] * x[i], i) >= 1;

// 終了条件に関する設定
options.maxtim = 10;

// 求解
solve();

// 結果出力
x.val.print();
total_cost.val.print();

　実行させる際には，次の配達可能エリアを表すcsvファイル（areadata_cover2.csv）とコストを表すdatファイル（costdata_cover2.dat）を与えます．

配達可能エリア, A, B, C, D, E, F, G
佐藤, 1, 1, 1, 0, 0, 0, 0
鈴木, 1, 0, 0, 1, 0, 1, 0
高橋, 0, 1, 0, 0, 1, 0, 0
田中, 0, 0, 1, 1, 1, 1, 1
渡辺, 1, 0, 0, 0, 0, 1, 0
伊藤, 0, 1, 0, 1, 0, 1, 0
山本, 0, 0, 0, 1, 0, 0, 0
中村, 0, 0, 1, 0, 0, 0, 1
小林, 0, 0, 1, 0, 0, 1, 1
斉藤, 0, 1, 0, 0, 1, 0, 1
コスト =
[佐藤] 200
[鈴木] 280
[高橋] 175
[田中] 560
[渡辺] 205
[伊藤] 245
[山本] 80
[中村] 195
[小林] 265
[斉藤] 190
;

　このモデルファイルを実行させることにより，佐藤・伊藤・斉藤の3人を採用すると良く，この場合の総コストは635であるということが分かります．

　

　ここで，Nuorium Optimizerの解法について少し述べておきます．今回の例題では厳密解法を用い求解をしました．一方で，0-1整数計画問題の場合には近似解法であるwcspを用い近似解を求めることもできます．wcspを用いた際の近似解を求めたい場合には，C++SIMPLEモデル中のsolve();より前に

options.method = "wcsp";

と記述します．wcspの詳細につきましてはNuorium Optimizerマニュアルを参考にしてください．

　なお，この例題では終了条件に関する定数を設定しています．具体的には，モデルファイルに

options.maxtim = 10;

と記述することで，最大で10秒間実行し終了するということを設定しています．この記述が無いと，wcspを用いた場合にはユーザが停止を命じない限り実行は停止しません．

　

　最後に，この3人を採用した場合，エリアBは3人とも担当可能になっています．このようなダブりを許さないように，例題に「1つのエリアはちょうど1人で担当する」という制約を加えてみるとどのようになるでしょうか．これは先ほどのC++SIMPLEモデル中の制約条件「sum(deliver[i, j] * x[i], i) >= 1;」を「sum(deliver[i, j] * x[i], i) == 1;」とすることで表現できます．モデルを書き換えた後に実行すると，鈴木・高橋・中村を採用すると良く，この場合の総コストは650であるという結果が得られます．

2.5 ナップサック問題
2.7 最大流問題

 

 

上に戻る