セットアップ付きナップサック問題の提案解法

提案解法では、深さ優先探索による分枝限定法を採用し、上界値の評価には連続緩和法、

下界値の取得には局所探索法によるヒューリスティックスを使用する。また、前処理とし て釘付けテストを行って、分枝限定法による木探索を効率化する。この手法的枞組みは、0

－1ナップサック問題の標準的手法の枞組みに従っているが、各要素手法においては（KPS１）

向けの特殊化を行っている。また、対象問題の大規模性を考慮して、簡潔かつ高速なアル ゴリズムを採用している。

この枞組みに従って、以下では、後述するダイナミック・リストを採用した全体・仮想ナ ップサック項目の構築方法について述べた後、連続緩和法による上界値の評価、ヒューリ スティックによる強力な下界値の取得、釘付けテスト、およびダイナミック・リンク方式 を採用した分枝限定法による高速な厳密解探索法について順に述べ、最後に全体手順を示 す。

4.3.3.1 全体・仮想ナップサック項目の構築

まず、全体ナップサック項目を以下のように構築する。

① 各グループの構成項目を効率(

e

kj)の高い順番で整列する。

②(6)式にもとづいて、各グループの仮想項目0とその属性(P^k0,T^k0,E^{k0)を決定する。}

③各グループの仮想項目を(7)式を満たすように挿入した上で、すべてのグループの全項 目を効率 の高い順番でマージする。

但し、あるグループが0に固定されている(選択されていない)場合には、当該グループに 対し①②③は実行されない。また、あるグループが 1 に固定されている(選択されている) 場合には②は実行されず、③においては当該グループの構成項目がマージされる。

全体ナップサック項目は、項目群の一時的削除(unlink)と再連結(relink)を高速に行える よう特殊な２重リンク・リスト構造(以 降 、ダイナミック・リストと称す)として実装されて いる。項目の整列には、高速なQuickSortを使用する。

次に、全体ナップサック項目からすべてのグループの仮想構成項目を一時的削除(unlink) して、仮想ナップサック項目を構築する。以降では、仮想ナップサック項目を整列された 順に番号付けした連続形の仮想ナップサック問題を次のように簡潔に表現する。

（ＬＶKPS’） max

Σ

j∈N

r

j

x

j (12)

s.t.

Σ

j∈N

w

j

x

j ≤ T ⁽¹³⁾

0 ^≤

x

j≤1 ^(j∈N) (14)

ここで、N={1,2,…,n}は仮想ナップサック項目の全体集合とする。

4.3.3.2 連続緩和法による上界値の評価

セットアップ付きナップサック問題（KPS１）の上界値を、連続ナップサック問題（ＬＶKPS’）

より求める。（ＬＶKPS’）の最適解とその値は、以下に示す貪欲法(GreedyMethod)［1］により 得られる。

(１)ブレイク項目の探索

制約条件(13)を満足させる範囲で効率の良い順の項目選択を行い、制約に違反する最

初の項目b(ブレイク項目)を求める。

Wb-1≤T<Wb-1+

w

b ここで、Wk=

Σ

j=1~k

w

j とする。

注）ブレイク項目は、整列された仮想ナップサック項目から線形探索により求められる。ブレ イク項目を整列せずに求める方法［11、20］も提案されているが、仮想項目を（6）式で決定する際 に項目を陽に整列する必要があることを考慮して、この方法は採用しない。

(２)最適解と最適上界値の決定

貪欲法により最適解は、

x

j=1 ( j=1~b^–1 )、

x

b=(T^–Wb-1)

/ w

^b、

x

j=0 ( j=b+1~n)で与 えられる。

x

bは制約条件(13)を等号で満たすように決定されている。

この最適解に応じて、最適値は

z

^–=

Σ

j=1~b-1

r

j+

r

b

x

b となる。

この方法の特徴は、線形時間で良い上界値が得られる点にあり、問題例によっては、唯一 の小数解である

x

bが整数となることもある。なお、整数値を持つ目的関数を対象とする場 合、実数値で与えられる上界値は整数値に丸める(切捨て)ことができるので、以降で引用す

るDantzig上界値

z

^–は整数変換されたものを指すこととする。

以上に示した連続緩和解から得られる（ＬKPS）の解は、次の３タイプに分類できる。

①ブレイク項目が小数値fをとり、あるグループkの仮想項目である場合 グループk以外の変数は整数値をとり、グループkでは下記を満たす。

y

k=

x

kj= f(j=1,...,jk0)、

x

kj=0(j=jk0+1,...,nk)

②ブレイク項目が小数値fをとり、あるグループkの純項目j^kである場合 グループk以外の変数は整数値をとり、グループkでは下記を満たす。

y

k=

x

kj=1(j=1,...,jk–1)、

x

kj= f(j=jk)、

x

kj=0(j=jk+1,...,nk)

③ブレイク項目が整数値をとる場合 すべての変数は整数値をとる。

4.3.3.3 ヒューリスティックによる下界値の取得

ブレイク項目を得る手順においては、（KPS１）の上界値とともにその実行可能解である下 界値も同時に得られるのが利点である。すなわち、ブレイク項目の解を0に設定した解

x

j=1 ( j=1~b^–1 )、

x

j=0 ( j=b~n)に変換式(11)を適用した解が（KPS１）の実行可能解であることは明 らかである。これはブレイク解と称され、効率の良い順で項目を選択した解であることよ り貪欲解とも言うことができる。ブレイク解の値_–

z

G=

Σ

j=1~b-1

r

j がDantzig上界値

z

^–と一致す れば、緩和法の原理より（KPS１）の最適解が得られたことになる。この状況はまれに発生す るが、一般には両者は一致せず、両者の値の差が大きいケースも多い。この差は整数ギャ ップと呼ばれる。

整数ギャップが存在する場合、提案解法ではブレイク解をもとに局所探索を行い、さらに 良い実行可能解を得る方法を実行する。局所探索法として、コアの概念［11、20、22］を活 用したスワップ近傍を下記(１) (２)のように線形時間で探索する。ここで、コアとは「0－1ナ ップサック問題の最適解がブレイク解に近く、両者の相違もブレイク項目の限られた周辺 に現れることが多い。」という観察から名付けられた名称である。但し（KPS１）では、ブレイ ク解に含まれる仮想項目と純項目の値間にグループ制約式(3)という依存関係があるので、

この条件および4.3.3.2で示した（ＬKPS）の解の分類を考慮して局所探索を行う。

(１)ブレイク項目より後半の探索

ブレイク項目の解を0 に設定し、容量残 T^–Wb-1以内の作業時間(

w

j)を持つ項目 群( j=b+1~b+c)に対し、利益総和(_–

z

G+

r

j)が最大となる追加項目を探す。

但し、追加項目の候補として下記の条件をさらに課す。

a)ブレイク項目が純項目の場合

1)追加項目とブレイク項目の所属グループが同じであること。

2)追加項目とブレイク項目の所属グループが異なる場合には、

・追加項目が、選定されたグループの純項目であること。もしくは、

・追加項目が、選定されていないグループの仮想項目であること。

b)ブレイク項目が仮想項目の場合： a2)の条件を適用。

(２)ブレイク項目より前半の探索

ブレイク項目の解を1 に設定し、容量不足 Wb–T以上の作業時間(

w

j)を持つ項目 群( j=b^–1~b^–c)に対し、利益総和(_–

z

G+

r

b–

r

j)が最大となる削除項目を探す。

但し、削除項目の候補として下記の条件をさらに課す。

c)ブレイク項目が純項目の場合

1)削除項目とブレイク項目の所属グループが同じである場合には、

・削除項目が純項目であること。

2)削除項目とブレイク項目の所属グループが異なる場合には、

・削除項目が純項目であること。もしくは、

・削除項目が仮想項目で、その所属グループの純項目が存在しないこと。

d)ブレイク項目が仮想項目の場合： c2)の条件を適用。

以上の２方向局所探索で得られた最良の実行可能解をヒューリスティック解_–

z

Hとして採 用 す る 。 こ こ で 、c は 仮 定 さ れ た コ ア サ イ ズ で あ り 、 提 案 解 法 で は 経 験 値 と し て c=max(0.1ns ,20)、 ns=

Σ

k∈Knk と設定している。このヒューリスティックは強力で、無相 関または弱相関の大規模問題例では、0.1%未満の整数ギャップをもたらす解を探しだすこ とが多い。但し、分枝限定法においてすべての木ノードで局所探索を行うと、全体の探索 ノード数は減尐するものの計算時間は増加する傾向があるので、数値実験の結果に基づい て、ルート問題(元問題)で上記コアサイズを使用し、そこから派生する子問題では高速化の ためにc=max(0.005ns ,10)を使用する。

4.3.3.4 釘付けテスト

上下界値が得られると、仮想ナップサック項目の変数値を0または1に永久固定する釘付 けテスト［6,8,12,14］が実行できる。釘付けテストの原理は、線形計画法(単体法)の理論より、

（ＬＶKPS’）の下記最適タブローから説明することができる。

目的関数値

z

₌

z

^–+

Σ

j∈N+

r

^–j(

x

j–1)+

Σ

j∈N‾

r

^–j

x

j+

r

^–s

x

s

ここで、

r

^–j≡

r

j–λ^*

w

jは限界利益を示し、λ^*は(13)式に対する双対変数の最適値(

r

b

/ w

^b)であ

る。また、N⁺={ j｜

r

^–j≥0,j∈N^–b}、N^‾={ j｜

r

^–j≤0,j∈N^–b}である。

なお、

x

sは(13)式のスラック変数を示し、

r

s=0、

w

s=1である。

明らかに、上記最適タブローが示す最適解、

x

j=1 for

r

^–j≥0、

x

j=0 for

r

^–j≤0 は、（ＬＶKPS’）

の解に一致している。

したがって、この限界利益を使用して、次の感度分析を行うことができる。

・

r

^–j>0である

x

jの値を1から0に変更すると、目的関数は+

r

^–jだけ減尐する。

・

r

^–j<0である

x

jの値を0から1に変更すると、目的関数は–

r

^–jだけ減尐する。

よって、この感度分析の結果より、次の釘付けテストが可能となる。

・

r

^–j>0である

x

jに対し、

z

^––

r

^–j≤_–

z

Hであれば、

x

jの値を1に固定できる。

・

r

^–j<0である

x

jに対し、

z

^–+

r

^–j≤_–

z

Hであれば、

x

jの値を0に固定できる。

但し、この釘付けテストは、仮想項目と純項目の値間にはグループ制約式(3)という依存 関係があるので、（KPS１）には無条件適用できない。しかしながら、制約式(3)を、両項目間 の優务関係(15)であると捉えなおして、考慮に入れることできる。

x

kj≤

y

k ：

x

kj=1 ^⇒

y

k=1,

y

k=0 ^⇒

x

kj=0 (j∈Nk ,k^∈K) ⁽¹⁵⁾ この観点より、最終的な釘付けテストとして下記が得られる。

・グループkのある純項目(

x

kj)の値が 1に固定されれば、仮想項目(

y

k)の値も 1に

固定できる。すなわち、グループkを選定することが決定される。

・グループkの仮想項目(

y

k)の値が0に固定されれば、すべての純項目(

x

kj)の値も0 に固定できる。すなわち、グループkを選定しないことが決定される。

・グループkの仮想項目(

y

k)の値が1 に固定されれば、そのすべての純項目(

x

kj)の 値は未定のままで、グループkを選定することが決定される。

・グループkのある純項目(

x

kj)の値が0に固定されれば、グループkの選定・非選定 は決定できないが、当該純項目を削除することができる。

以上の釘付けテストは、上界値

z

^–と下界値_–

z

Hのギャップが尐ない場合に有効に作用し、無 相関の大規模問題例では、大半の変数が固定される傾向にある。弱相関の大規模問題例で は、多くの変数が固定されるケースもあるが、全く固定されないケースもあるなど、デー タに依存する傾向が見られる。

4.3.3.5 分枝限定法による厳密解の探索

提案解法では、深さ優先探索に基づく分枝限定法を採用している。一般に、深さ優先木探 索の実装方法として、ノードの探索順番を操作するためにスタック構造を陽に利用する方 法と再帰的呼び出しを行う方法が通常採用される。但し、両方法ともスタックに要するメ モリとその管理に伴うオーバーヘッド時間が必要であり、大規模問題ではメモリ不足をも たらすことがある。したがって提案解法では、再帰的呼び出しを繰り返し手順で代替する 方法［5、9、33］を（KPS１）用に改造・改良することにより、メモリレスで高速な木探索を実 現している。

分枝限定法では、“B&B=Enumeration+Fathoming”の原理に基づいて、グループ変数

y

の値を順番に固定(分枝)しながら、終端を行いつつ間接列挙を行う(図１)。各グループ変数 は、まず深さ優先で順次 1 に固定され、終端が行われると、次に、0 に固定されるグループ 変数の位置へバックトラックする。バックトラックされた位置で 0 固定を行い、そこから 再び同じ手順の探索が再帰的に進行する。この探索中に、すべてのグループ変数の値が固 定された場合には、１に固定されたグループの構成項目のみで構成される 0－1ナップサッ ク問題を（KPS１）の実行可能問題として解いた後、前記と同様のバックトラックを行う。バ ックトラックする位置がすべて検査され新たな位置が存在しなければ、分枝限定法を完了 する。

したがって、グループ変数の固定状態に応じた木ノードqにおける部分問題の構造は、以 下のように示される。

（KPSq） max

Σ

k∈K2

Σ

j∈N‟_k

p

kj

x

kj+

Σ

k∈K1

Σ

j∈Nk

p

kj

x

kj –

Σ

k∈K2

c

k

y

k –

Σ

k∈K1

c

k

s.t.

Σ

k∈K2

Σ

j∈N‟_k

t

kj

x

kj+

Σ

k∈K1

Σ

j∈Nk

t

kj

x

kj+

Σ

k∈K2

s

k

y

k ≤ T–

Σ

k∈K1

s

k

x

kj≤

y

k (j∈N‟k ,k^∈K²)

ドキュメント内 保全コスト平準化に向けた (ページ 87-96)