日本オペレーションズ・リサーチ学会
2021年 秋季研究発表会

2-A-1

カバー回数が不確実な状況下でのセットマルチカバー問題に対する近似アルゴリズム
05000653 青山学院大学 *高澤 陽太朗

1.

はじめに（上限制約付きの）セットマルチカバー問題
は、基礎的な組合せ最適化問題の一つであるセットカバー問題の自然な一般化として知られている。入力とし台集合 U 、カバー回数 re ∈Z+ (e ∈ U)、部分集合族 S ⊆ 2U 、コスト関数
c : S → Z+ 、部分集合の利用上限 d : S → Z+が与えられたときに、各部分集合の利用上限回数と各要素のカバー回数を満たしつつ、コストを最小化するような各部分集合の利用回数を決める問題である。
本研究ではセットマルチカバー問題において各要素のカバー回数が不確実であるような状況を考える。ここでは、各要素のカバー回数は不確実性を持つものとして確率変数で与えられる。利用上限を満たしつつ各部分集合の利用回数を決める点は通常のセットマルチカ
バー問題と同様であるが、その決定によって定まった各カバー回数がカバー回数の実現値に対して不足している場合、不足 1 単位あたり追加のコストが生じる。問題の目的は、カバーにかかるコストとカバー回数に関する期待不足コストの和を最小化することである。これは 2 段階確率計画問題とよばれる問題で、通常のセットマルチカバー問題の設定に加えて、カバー回数の分布を考慮しつつ部分集合を選ぶ必要がある。この問題は配達員をクラウドソーシングする配達サービスにおける（シフトで働く）従業員のシフトスケジューリングに応用できる [2, 4]。
本研究ではこの問題をシナリオを用いてモデル化し、問題が NP-困難であることを示す。 そして、この問題に対して LP を利用した O(log ∆)-近似アルゴリズムを提案する。た

TAKAZAWA Yotaro

だし、∆ は部分集合の最大サイズ、すなわち、∆ = maxS ∈S |S | である。

2.

シナリオを用いた定式化

セットマルチカバー問題の追加のインプットとして、シナリオ Ω、シナリオ ω ∈ Ω が起こる確率 pω ∈ [0, 1] とその時の要素 e ∈ U のカバー回数 re,ω ∈ Z+ 、要素 e ∈ U のカバー回数の不足分に関するペナルティπe ∈ Z+ が与えれた時、カバー回数が不確実な状況下でのセットマルチカバー問題はシナリオを用いて次のように定式化できる。
∑∑ ∑minimizec(S )xS +πepω ze,ωsubject toS ∈S∑e∈Uω∈ΩS ∈S:e∈S xS + ze,ω ≥ re,ω∀ω ∈ Ω ∀e ∈ U,xS ∈ Z+ ∀S ∈ S,xS ≤ d(S ) ∀S ∈ S,ze,ω ∈ Z+ ∀ω ∈ Ω ∀e ∈ U.

(1)
セットマルチカバー問題はシナリオ数 1 とした時の (1) へ帰着できるため、(1) は NP-困難である。その一方で、(1) は台集合を U ′ ={(e, ω) | e ∈ U, ω ∈ Ω}、要素 (e, ω) ∈ U ′ のカ
バー回数は r(e,ω) = re,ω とした時のセットマルチカバー問題へ帰着できる。セットマルチカ
バー問題に対しては、O(log ∆)-近似アルゴリズムが知られている [1]。そのため、この帰着とこの近似アルゴリズムを利用することで、(1) に対する O(log(∆|Ω|))-近似アルゴリズムを得ることができる。ただし、この帰着を利用したアルゴリズムの近似比がシナリオ数に依存するという課題がある。

3.

アルゴリズム本研究では問題 (1) に対して O(log ∆)-近似アルゴリズムを提案する。アルゴリズムは (1)の LP 緩和と 0-1 制約付きのセットマルチカ
バー問題に対する既存の O(log ∆)-近似アルゴ
リズム [3] を組み合わせたものである。以降では提案アルゴリズムを紹介する。
(1) の LP 緩和問題の最適解を (x∗ , z ∗ ) とする。さらに、(xI , z I ) = (⌊x∗ ⌋, ⌊z ∗ ⌋)、(xF , z F ) =(x∗ − xI , z ∗ − z I ) と定義する。(1) の LP 緩和問
題の最適解の整数部分を固定して、小数部分のみを変数 (y, w) としてもつ以下の LP を考える。

minimize∑c(S )yS +∑πe

S ∈S∑pω we,ωe∈Uω∈Ω∑∑IIS ∈S:e∈S yS
S ∈S:e∈S xS + ze,ω ++we,ω ≥ re,ω ∀ω ∈ Ω ∀e ∈ U,
1 ≥ yS ≥ 0 ∀S ∈ S,
1 ≥ we,ω ≥ 0 ∀ω ∈ Ω ∀e ∈ U.
(2)ある線形計画問題に対して、その任意の問題例に関して最適値の α 倍以下の整数解を多項式時間で出力するアルゴリズムをその問題の LP ベースの α-近似アルゴリズムと呼ぶことにする。提案アルゴリズムは、(2) に対する
LP ベースの α-近似アルゴリズムが存在すると仮定したときに、それを利用して元問題 (1)の解を得るアルゴリズムである。

Algorithm 1
Step 1: (1) の LP 緩和問題を解き、最適解(x∗ , z ∗ ) = (xI + xF , z I + z F ) から問題 (2)を得る。
Step 2: (2) に対する LP-ベースの α-近似アルゴリズムを用いて、問題 (2) の整数解(y A , w A ) を得る。
Step 3: 解として (xA , z A ) = (xI + y A , z I + w A )を出力する。
Algorithm 1 は (1) に対する α-近似アルゴリズムであることは容易に示すことができる。

e∈UFS ∈S:e∈S yS + we ≥ ⌈Xe ⌉subject to1 ≥ yS ≥ 0⌈ZeF ⌉ ≥ we ≥ 0∑

S ∈Ssubject to

そのため、(2) に対して LP ベースの O(log ∆)近似アルゴリズムの存在さえ示せれば、Algorithm1 の枠組みを利用して (1) に対するO(log ∆)-近似アルゴリズムの存在を示すことができる。
そこで、(2) に対して LP ベースの O(log ∆)近似アルゴリズムが存在することを示す。そのために、本研究では (2) が次のような問題に変形できることを示す。
∑∑minimizec(S )yS +Πe we∀e ∈ U,∀S ∈ S,∀e ∈ U.
(3)

ただし、e ∈ U に対してXeI
XeF
ZeF
Πe

∑
I=
S ∈S:e∈S xS∑
F=S ∈S:e∈S xS= ⌈XeF ⌉ − XeF∑= πe ω∈Ω:z∗e,ω >0 pe,ω .

(4)

問題 (3) の整数解を求める問題は、台集合が U 、要素 e ∈ U のカバー回数を ⌈XeF ⌉ とした
0-1 制約付きのセットマルチカバー問題となることがわかり、この問題に対しては LP ベースの O(log ∆)-近似アルゴリズム [3] が知られている。そのため、(2) に対しても LP ベースのO(log ∆)-近似アルゴリズムが存在することが言える。

参考文献[1] Gregory Dobson. Worst-case analysis of greedy heuristics for integer programming with nonnegative data. Mathematics of Operations Research, 7(4):515–531, 1982.
[2] Marlin Ulmer and Martin Savelsbergh. Workforce scheduling in theera of crowdsourced delivery. Transportation Science, 54(4):1113–1133, 2020.
[3] Vijay V Vazirani. Set cover via dual ﬁtting. In Approximation Algorithms, pages 108–117. Springer, 2003.
[4] Baris Yildiz and Martin Savelsbergh. Service and capacity planningin crowd-sourced delivery. Transportation Research Part C: Emerging Technologies, 100:177–199, 2019.