制約 条件

Maximin型 の 目的 函 数 を持 つ ナ ップサ ック 問題 につ い て

飯 田 浩 志

概 要

本 稿 で は,maximin型 の 目的 函 数 を 持 つ,二 つ の ナ ップ サ ッ ク 問 題 を概 観 す る.一 つ は ナ ッ プ サ ッ ク 配 分 問 題,も う ひ と つ はmax‑minO‑1ナ ッ プ サ ッ

ク問 題 で あ る.後 者 は 前 者 の 拡 張 で あ り,後 者 の 前 者 か らの 具 体 的 な構 成 法 に も言 及 す る.

Abstract

Inthispaperwegiveanoverviewoftwoknapsackproblemswithmax‑

imintypeobjectivefunction,onetheknapsacksharingproblemandthe otherthemax‑minO‑1knapsackproblem.Thelatterisanextensionofthe former,andwealsogiveaconcreteconstructionofthelatterwiththefor‑

mer.

キ ー ワ ー ド:組 合 せ 最 適 化(combinatorialoptimization);0‑1ナ ッ プ サ ッ ク 問 題(0‑1knapsackproblem);ナ ッ プ サ ッ ク 配 分 問 題(knapsack sharingproblem);max‑minO‑1ナ ッ プ サ ッ ク 問 題(max‑min O‑1knapsackproblem)

〔209〕

1は じ め に

古 典 的 な組 合 せ 最 適 化 問 題 で あ る0‑1ナ ッ プ サ ッ ク 問 題(以 下,簡 単 の 為 KPと い う)は,1970年 代 か ら盛 ん に研 究 さ れ て きた.KPは,唯 一 の 制 約 条 件 しか 持 た ない 整 数 計 画 問 題 の形 を し て お り,一 見 容 易 に解 き得 る よ う に思 え るが,実 はNP困 難 な 問 題 で あ る こ とは 良 く知 られ て い る.さ て,KPで は, 価 値 と重 量 な る二 つ の 属 性 を持 つ い くつ か の 項(品 物)と,そ れ らを運 ぶ 為 の ナ

ッ プサ ック が 与 え られ る.但 し,ナ ッ プサ ッ ク に は重 量 制 限 が あ り,す べ て の 項 を運 べ る訳 で は な い.こ の 制 約 の 下,そ の価 値 の 総 和 を 最 大 にす る 項 の 組 合 せ を見 つ け る こ とが,KPの 目的 で あ る.KPは,次 の よ う に 定 式 化 され る:

(KP)最 大 化

制約 条件

Σ 解 ゴ

ゴ∈N

ΣW」X」 ≦6 ノ∈N

C」∈{0,1},ゴ ∈N.

本 稿 を通 じて,N:={1,2,̲,nlで あ り,〃 が 項 数 を示 す もの とす る.吻,Wyを そ れ ぞ れ,項 ブ(∈N)の 価 値,重 量 と呼 ぶ.cは ナ ップ サ ッ ク の重 量 制 限 を示 し, 0‑1変 数 勿 が,項 ブの 選 択(吻=1)/非 選 択(錫=0)を 示 す.KPで は,選 択 可 能 な 項 の み を対 象 とす る為 に,す べ て の 項 ブの 重 量 につ い てWy≦cを,先 に 述 べ た よ う に,問 題 自体 を意 味 あ る も の に す る為 に Σブ∈lvWj>cを 前 提 とす る の が 通 例 で あ る.KPの 詳 細 につ い て は,例 え ば,MartelloandToth[5]を 参 照 され た い.

このKPに 拡 張 を 施 し た 問 題 は,数 多 く存 在 す る.そ の 特 殊 な場 合 と して KPを 含 む が 故 に,KPを 拡 張 した 問 題 は す べ てNP困 難 で あ り,一 般 に容 易 に は 解 き得 な い.本 稿 で は,KPの 拡 張 の 中 で も特 に,特 徴 的 なmaximin型 の 目的 函 数(あ る 集 合 の 中 の 最 小 値 を最 大 化 す る)を 持 つ 二 つ の ナ ッ プ サ ッ ク問 題 に 焦 点 を 当 て,こ れ ま で に公 刊 され た 文 献 を も と に,そ れ ら を概 観 す る.一 つ は ナ ッ プ サ ッ ク 配 分 問 題,も う ひ とつ はmax‑minO‑1ナ ップ サ ッ ク 問 題 で

Maximin型 の 目的函 数 を持つ ナ ップサ ック問題 につ いて211

あ る.後 者 は前 者 の 拡 張 で あ り,後 者 の 前 者 か らの 具 体 的 な構 成 法 に も言 及 す る.

2ナ ップサ ック配 分 問 題

本 節 で は,ナ ッ プ サ ッ ク 配 分 問 題(KnapsackSharingProblem,以 下KSP と い う)を 紹 介 す る.KSPは,次 の 式 で 与 え ら れ る:

(KSP)最 大 化

制約 条件

minΣ ,P」X,

1≦k≦7ゴ ∈…Nk

ΣW」X」 ≦c ゴ∈N

.r・」 ∈{0,1},ブ ∈N

ア

uNk=瓦Nk∩Nl=e,k≠1.

k=1

(1)

(2) (3) (4)

KSPで は,KPの 定 義 に 加 え て,〈4):項 の 集 合Nを,rヶ の 排 他 的 な ク ラ ス に 分 割 す る.そ の 上 で,(1):選 択 し た 項 の 価 値 の 和 を ク ラ ス ご と に 算 出 し,そ の

中 の 最 小 値 を 最 大 化 す る,と い う 点 がKPの 拡 張 と な っ て い る.実 際,r=1, i.e.ク ラ ス が 唯 一 の 時,KSPはKPに 一一ikす る.こ こ で は 簡 単 の 為,c及 び す べ て の 勿,吻 は 正 の 整 数 と 仮 定 す る.

例1.500円 玉 一 つ 持 っ て,学 食 に行 く とす る(c=500).各 品 目ブは,赤,緑, 黄 の 食 品 群 に分 け られ て お り,そ の指 数 は 勿 で あ る とす る.但 し,各 品

目 は唯 一 つ の群 に の み 属 す る とす る.ま た,各 品 目 に は 値 段 吻 円 も与 え られ て い る.こ こ で,500円 以 内 で 選 択 した 品 目か ら算 出 し た 三 つ の指 数 そ れ ぞ れ の合 計 の 内,最 小 の もの を 最 大 に す る の がKSPで あ る.大 雑 把 に 言 え ば,ど れ か 一 つ の 群 の指 数 の 合 計 の み が 突 出 して も最 適 解 に は な り 得 ない.バ ラ ンス 良 く品 目 を選 び,赤,緑,黄 全 体 を底 上 げ す る の が 肝 要

で あ る.

Qui・.KSP(1)一(4)で,Σ:。 、minブ∈疏 吻>cの 時,最 適 値 は い く ら に な る か?

一 般 に,分 枝 限 定 法 を適 用 す る に あ た っ て,線 形 緩 和 問 題(連 続 緩 和 問 題 と もい う)を 解 く こ と の重 要性 は,論 を ま た な い だ ろ う.KSPの 線 形 緩 和 問 題, 即 ち,0‑1条 件(3)を0≦ η≦1に 緩 め た 問 題 は,如 何 に して 解 け ば よ い の で あ ろ うか.以 下 で は,Yamadaetal[8]に 沿 っ て,KSPの 線 形 緩 和 問題 へ の 解 法 を概 説 す る.以 降,KSPの 線 形 緩 和 問 題 をC(KSP),そ の最 適 値 を2で 示 す.

まず,各 ク ラス κに つ い て次 の 問 題 を 定 義 す る:

最 大 化 制 約条件

Σ 鋼 ゴ

ゴ∈Nk

ΣW」X」 ≦ck ゴ∈隔

0≦vノ ≦三1,ブ ∈Nk.

(5)

問 題(5)の 最 適 値 を,重 量 制 限ckに 依 存 す る と い う 意 味 で,訪(ck)と 書 く.

以 下,勝 手 な ク ラ ス ん に 属 す る 二 つ の 項 ゴ,ブ∈ 照 に つ い て,ゴ<ブ な ら ば 鳶/吻 ≧ 勿/吻 が 成 立 し て い る も の と仮 定 す る.こ の 仮 定 の 下 で は,問 題(5)

の 最 適 値,即 ち,良 く 知 ら れ たDantzigの 上 界(Dantzig[1])は,即 座 に 求 ま る 事 に 注 意 さ れ た い.

今,五:=min1≦ 底 。Σブ∈N、動 と 置 く.容 易 に 分 か る よ う に,KSPの 最 適 値 は,こ の 五 を 越 え な い.こ こ で,各 ク ラ ス ん に つ い て,ン(・)=ガ を 満 た す 重 量 評(p)を 考 え た 時,即 ち,ノ(τ ん例)=ラ(1≦k≦r)と し た 時:

Σ ζ.〆 ⑳ ≦6で あ る な ら,PがC(KSP)の 最 適 値 と な る;Σ1‑、r%)>cの 時,明 ら か に 乏く ガ で あ り,ま た,最 適 値 乏 を 与 え る 各 ク ラ ス へ の 重 量 配 分

(Ei,i2,̲,iつ に つ い て,次 が 成 立 す る.

ノ(Ek)=2,k=1,2,̲,r

6

=

ン.Σ同

(6)

(7)

Maximin型 の 目的 函 数 を 持 つ ナ ッ プ サ ッ ク 問 題 に つ い て 2ヱ3

は,[8]を 参 照 され た い.

さ て,従 来 の 分 枝 限 定 法 と線 形 緩 和 問 題 に よ る枠 組 以 外 に,KSPの 最 適 値 を 求 め る 術 は な い もの だ ろ うか.本 節 の 残 りで は,[8]の 後 半 で 提 案 さ れ た 効 率 的 なKSPの 最 適 値 の 求 め方 を,少 し詳 し く解 説 す る.

以 降,KSPの 最 適 値 をz*で 示 す.ま ず は じめ に,任 意 の整 数g≧0に つ い て, z*≧zと

Σlb」xブ ≧z,k=1,2,…,ノ ゴeNk

2]w」x」 ≦6

ゴ∈…N

C」∈{0,1},ブ ∈1>

(8)

が 実 行 可 能 解 を 持 つ(feasible)こ と は 同 値 で あ る 事 に 注 意 す る.何 と な れ ば:

ノ ≧gな ら ば,z*の 最 適 性 か ら,(8)は 少 な く と も 一 つ の 実 行 可 能 解,即 ち, Z*を 与 え る 解 を 持 つ;逆 に,(8)が 実 行 可 能 解 を 持 ち 且 つz*<gな ら ば,z*の

最 適 性 に 反 す る.以 降,(8)が 実 行 可 能 解 を 持 つ 時 のzを,到 達 可 能(attainable)

と 呼 ぶ.明 ら か に,到 達 可 能 なzの 最 大 値 がz*を 与 え る.以 下,任 意 の 整

数z≧0の 到 達 可 能 性 を 判 定 す る 方 法 を 示 す.

まず,各 ク ラス ん ご と に次 の 問 題 を定 義 す る:

最 小 化 制約条件

Σ"両

ノ∈Nk

ΣPゴxゴ ≧z ブ∈砺

」C」∈{0,1},ブ ∈N,.

(9)

この 問 題(9)の 最 適 値 を 評(z)と 書 く.換 言 す れ ば,ク ラ スkに つ い て,価 値 の 和 をz以 上 に保 つ 為 の 最 小 の 重 量 和 が 評(g)で あ る.こ こ に,zの 到 達 可 能 性 は 次 と同値 で あ る.

プ

Σc*k(2)≦c

k=1

つ ま り,̀を 各 ク ラ ス に,そ の 価 値 の 和 をz以 上 に 保 つ 為 の 最 小 の 重 量 和 分 だ け 配 分 可 能 で あ れ ば,zは 到 達 可 能 で あ る.ま た,(9)で ヵ:=1一 乃 とお け ば, (9)は

最 大 化 制約条件

Σ ωゴッゴ ー Σ ωノ

ゴ∈Nkゴ ∈ハrk

Σ 鯛 ≦ Σ 為 一2

ゴ∈Nkゴ ∈Nk

巧 ∈{0,1},ブ ∈N,

な るKPに な る の で,(9)の 上/下 界 は 苦 労 な く 求 ま る(例 え ば,Martelloand Toth[6]の 第2節 参 照).こ こ で,各 ク ラ スkそ れ ぞ れ に つ い て 求 め た(9)の 上

界 評(z),下 界gk(2)に つ い て:Σ1.、Ek(z)≦cで あ れ ば2は 到 達 可 能 で あ り, Σ:一 、gk(Z)>Cで あ れ ば 到 達 不 可 能 で あ る と 言 え る;ど ち ら で も な い 場 合, 残 念 な が ら 各 ク ラ ス そ れ ぞ れ に つ い て,与 え ら れ たzを 入 れ た(9)をexactに

が 示 され た.

さて,到 達 可 能/到 達 不 可 能 な二 つ の 組{2L,ZR}(2L+1<ZR)を 考 え る.ま

Maximin型 の 目的 函 数 を 持 つ ナ ップ サ ッ ク 問 題 に つ い て 215

た い.

3Max‑minO‑1ナ ッ プ サ ッ ク 問 題

本 節 で は,max‑minO‑1ナ ッ プ サ ッ ク 問 題(max‑minO‑lknapsackprob‑

1em,以 下MNKと い う)を 紹 介 す る.KPで は 項 の 価 値 勿 は 恒 久 的 で あ っ た が,未 来 に 対 し て 複 数 の 局 面(シ ナ リ オ)を 設 定 し,項 そ れ ぞ れ の 各 局 面 下 で 異 な る 価 値 を 考 慮 す る の がMNKで あ る.MNKは,Yu[9]に よ っ て 提 案 さ れ た.[9]で は,分 枝 限 定 法+最 良 優 先 探 索 に よ る 解 法 も,合 わ せ て 提 案 さ れ て い る.MNKは,次 の 式 で 与 え ら れ る1

(MNK)最 大 化

制約 条件

聖嚥 醐

ΣW」X」 ≦c j∈N

xノ ∈{0,1},ノ ∈N,

(10) (11)

こ こ に,Sは シ ナ リ オ の 集 合 で あ る.各 項 ブ∈Nは 重 量Wjを 持 ち,シ ナ リ オ s∈Sの 下 で 価 値 培 を 持 つ.加 え て,す べ て の 培 及 び 吻 は 正 で あ る と し て 一 般 性 を 失 わ な い.ま た,lSl=1,i.e.シ ナ リ オ が 唯 一 つ の 時,MNKはKPに

1注:[8]で は

,乏 を9Rの 初 期 値 と して い る が,ZR‑ZL=1を ル ー プ の 終 端 条 件 と し て い る 事 等 か ら,鞭 の 整 数 性 を 仮 定 して い る は ず で あ る 。 よ っ て こ こ で は,乏 で は な く1訓 と した.「 刻=2の 時,ii?]は 到 達 可 能 と な る可 能 性 の あ る 事 に 注 意 さ れ た

い.ま た[8]で,手 続 きBinary‑Searchの ル ー プ 処 理 の 前 に,ZR一 範 ≦1を 見 る べ き で あ ろ う.

2[8]に 従 っ てZ

Lの 初 期 値 を計 算 す る の と,ZL:=0と して 二 分 探 索 を い き な り

始 め る の と,実 際 に は どち ら が 速 い だ ろ う か?

一 致 す る.目 的 函 数 働 の 意 味 す る 所 は,す べ て の シ ナ リ オ で そ れ ぞ れ 計 算 し た 中 で の 最 小 の価 値 の 総和 を最 大 に す る項 の選 択 を求 め よ,と い う こ とで あ る.

大 雑 把 に言 え ば,KSPと 同 様,あ る シ ナ リオ に 於 け る価 値 の 総 和 が 突 出 して も, 最 適解 に は な り得 な い.

例2.項 数5,二 つ の シ ナ リ オ か ら な る 簡 単 な 例 を 掲 げ て お く.各 項 ブ∈{1,2,̲,5}に つ き,重 量Wj及 び シ ナ リ オs∈{1,2}の 下 で の 価 値 拶 は

次 の よ う に 与 え ら れ る と す る:

ブ 12

祝ケ

337 84 30 99

1"

y

1622

73 106

2"

ブ

39101

34

加 え て,重 量 制 限c=126と す る.例 え ば,選 択{1,3,4}は ナ ッ プ サ ッ ク に 入 り,vl+v§+遍=101>77・=vi+v§+vZよ り,そ の 最 小 の 価 値 の 総 和 は77で あ る.選 択{1,2,3}は,最 小 の 価 値 の 総 和 が50で あ る の で,な お 悪 い.こ の 例 で は 最 適 値 は122で あ り,そ れ を 与 え る 最 適 解 は{1,51で あ る.

先 の 例1で,一 つ の 品 目 が 唯 一 つ の 食 品 群(赤,緑,黄)に の み 属 す る と い う の は,現 実 に そ ぐ わ な い.各 品 目 に つ い て,赤,緑,黄 三 つ の 群 そ れ ぞ れ に 指 数 を 持 た せ る こ と が よ り 好 ま し い が,こ れ はMNKを 用 い れ ば 定 式 化 で き る.つ ま り,赤,緑,黄 そ れ ぞ れ の 群 を 一 つ の シ ナ リ オ と す れ ば

良 い.

さ て,前 節 で も言 及 した よ う に,一 般 に ナ ップサ ッ ク問 題 に分 枝 限 定 法 を 適 用 す る に あ た っ て は,元 の 問 題 及 び そ の 部 分 問 題(分 岐 の 過 程 で現 れ る,あ る 項 の組 の 選 択/非 選 択 を 決 定 す る事 に よ り,対 象 とす る項 数 を 少 な く した 問 題) の 線 形 緩 和 問題 を解 い て 上 界 を求 め る の が 常 道 で あ る が,MNKの 線 形 緩 和 間

Maximin型 の 目 的 函 数 を持 つ ナ ッ プ サ ッ ク問 題 に つ い て 217 題 の 最 適 値 は,KPに 対 す るDantzigの 上 界 の よ う に 容 易 に 求 ま りそ う も な い.

実 は,[9]で は,線 形 緩 和 で は な くsurrogate緩 和 が 用 い ら れ て い る.MNKの surrogate緩 和 問 題 は,[9]で 示 さ れ た よ う に,KPと し て 書 け る:

ZU(μ)=maxΣ 汐ノ(μ)・X」,V」(μ)=Σ μ。拶

Xゴ ∈NS∈S

制約条件 Σ 鵬 動

ゴ∈N

(13) μ、≧o(s∈s),Σ μ。=1

s∈s

x,∈{0,1},ブ ∈N.

緩 和 問 題 ⑯ に 関 し て は,如 何 に し て 御(μ)を 小 さ ぐ す る よ う に,乗 数 ベ ク ト ル(μ,)。∈sを 決 め る か が 本 質 で あ る.[9]で は,劣 勾 配(subgradient)法 を 用 い て,そ の 繰 り返 し処 理 の 過 程 で 乗 数 ベ ク ト ル を 徐 々 に 強 化 し て い く 手 続 き が 提 案 さ れ て い る.そ の 手 続 き か ら 出 力 さ れ るMNKの 上/下 界 は 非 常 にtightで

あ り,特 筆 に 値 す る.ま た,乗 数 ベ ク トル(μ 、),∈sに つ い て Σ、∈sμ 、=1を 仮 定 す れ ば,ラ グ ラ ン ジ ュ 緩 和 か ら も ⑯ と 同 一 の 式 を 導 け る こ と を 付 言 し て お く(lida[2],p.5参 照).

加 え て,MNKへ のgreedy法 の 適 用 に 関 す る 記 述 が,[2]に あ る.KPに 対 し て は,greedy法 は か な り 良 い 下 界 を 与 え る こ と が 知 ら れ て い る が,MNK に 対 し て 良 好 な 結 果 は 得 ら れ て い な い([2]のTable2と[9]のTable皿 中 の2L を 比 較 さ れ た い).こ れ は,KPの 勿/〃 ブ に 相 当 す る よ う な,MNKに 於 け る 項 の 重 要 度 一efficiency一 を 示 す 尺 度 を 与 え 得 な い 事 に 起 因 す る と 思 わ れ る.さ ら に,⑬ の 乗 数 ベ ク トル の 決 め 方 に 関 す る 一 考 察 が,Iida[3]に あ る.残 念 な が ら,[9]で 提 案 さ れ た そ れ ら 程tightな 上/下 界 を 得 る ま で に は 至 っ て い な い.

話 か わ っ て,こ れ は[9]に も 少 し言 及 さ れ て い る こ と だ が,例1,2か ら も 分 か る よ う に,MNKはKSPの 拡 張 と 考 え る 事 が 出 来 る.以 下 で は,KSPか ら MNKを 具 体 的 に 構 成 し て み よ う.KSP(1)一(4)か らMNK㈲ 一 働 を 次 の よ う

に 構 成 す る:

Sニ{1,2,̲,r}

房一{駕:盤

即 ち,KSPの 一 ク ラ ス をMNKの 一 シ ナ リオ に 対 応 させ る の で あ る.あ る ク ラス ∫に属 す る項 ブ(∈ハ馨)は,対 応 す る シ ナ リオ ∫で の み価 値 勿 を持 つ とす る.

この 時,KSPの 目的 函 数 は

恕 黒鍋 一鯉/〜諦+馳}一 躯癖 賜

で あ り,確 か にMNKの 目的 函 数 と し て 書 け る.以 上 の 事 か ら,KSPをMNK の枠 組 で解 く事 が 可 能 とな る.し か し,KSPは 既 に 高 速 に解 け る 問 題 で あ り, MNKと して 解 くメ リ ッ トは無 い で あ ろ う.

以 上,KSPか らMNKへ の 変 換 を 与 え た が,も し こ の 逆 変 換 を 与 え る こ と が 出 来 れ ば,MNKを 解 くの に有 望 な枠 組 とな る で あ ろ う事 は想 像 に難 くな い.

MNKか らKSPへ の 変 換,即 ち,情 報 量 の よ り少 な い 方 へ の 変 換 な ど存 在 し な い と決 め つ け る の は 早 計 で あ る.実 際,KPの 拡 張 で あ るcollapsingknap‑

sackproblem(CKP)か らKPへ の 変 換 を 定 義 し,KPの 枠 組 でCKPを 解 い た 例 もあ る(Pferschyetal[7コ).

4お わ り に

本 稿 で は,0‑1ナ ッ プ サ ッ ク 問 題 の 数 あ る 拡 張 の 中 で も特 に,特 徴 的 な maximin型 の 目 的 函 数 を 持 つ 二 つ の ナ ッ プ サ ッ ク 問 題 を 概 観 した.一 方 の KSPは 非 常 に良 く研 究 さ れ て お り,n=10000,r=10程 度 の か な り大 規 模 な 問 題 で も,実 用 時 間 以 内 に 解 け る 事 が 示 さ れ て い る.他 方,MNKはn=60,

IS1=30ま で の 実 績 しか な く,よ り大 規 模 な 問 題 を よ り速 く解 け る可 能 性 を秘 め て い る もの と思 わ れ る.と は 言 え,本 文 中 で 述 べ た よ う に,こ の 問 題 の 提 案 者 自身 に よっ て提 案 さ れ た 上/下 界 は 非 常 に強 力 で あ り,こ れ を 打 ち破 る の は

Maximin型 の 目 的 函 数 を持 つ ナ ッ プ サ ッ ク問 題 につ い て 219

で あ る.無 論,KSPの 研 究 も終 っ た 訳 で は な い.

参 考 文 献

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

G.B.Dantzig,"Discrete‑variableextremumproblems,"Opns.1〜es.5(2)266‑277, April1957.

H.Iida,0〃solvingthe〃zczt‑〃zinO一 ヱknmpsackproble〃z,ResearchReport IS‑RR‑97‑0025F,.北 陸 先 端 科 学 技 術 大 学 院 大 学,923‑1292Japan,June1997,

H.Iida,"Anoteonthemax‑minO‑1knapsackproblem,"ノburnalOfCom‑

binatorial())ti〃zization,toappear.

T.Kuno,H.KonnoandE.Zemel,"Alinear‑timealgorithmfbrsolvingcon‑

tinuousmaximinknapsackproblems,'Opns。Res.Lett.10(1)23‑26,Feb.1991.

S.MartelloandP.Toth,KnapsackProble〃zs'Algorith〃 ￠sandComψuter1初 一

plementations,JohnWiley&Sons,Chichester,England,1990.

S.MartelloandP.Toth,"UpperboundsandalgorithmsforhardO‑1knapsack problems;'()pns.1〜es.45(5)768‑778,Sept.‑Oct.1997.

U・PferschyrD・PisingerandG・J・Woeginger,"SimplebutefficientapProaches fortheco11apsingknapsackproblem;'Z)iscreteAppl.Math.77,271‑280,1997.

T.Yamada,M.FutakawaandS.Kataoka,"Someexactalgorithmsfortheknap‑

sacksharingproblem,'Euro.ノ.Opnl.Res.106,177‑183,1998.

G.Yu,"Onthemax‑minO‑lknapsackproblemwithrobustoptimizationappli‑

cations,"()pns.1〜es.44(2)407‑415,March‑April1996.