No.185
直 接 KP→ 0 1KP模 索 中
k -
飯 田 浩 志
年 月
2017 2
小 樽 商 科 大 学 商 学 部 社 会 情 報 学 科
直接 kKP → 0–1KP 模索中
飯田浩志
∗
古典的 組合 最適化問題
0–1
問題(0–1KP)
亜種,
詰 得 品数k
以下 強kKP ,
元0–1KP
戻 変換 考.
迂回,
又別 問題挟
変換 提案 居
,
直接 変換,
無駄 省 簡素 ̶ 少 項数,
小 係数 持 ̶変換結果0–1KP
目指 度.
残念,
未 成果 得 居.
:
組合 最適化,
問題,
項数制約1
古典的
0–1
問題(
以降, 0–1KP) exact
解法,
分野 権威Martello,
Pisinger and Toth
三氏 手Management Science
誌1999
年 発表 以降,
出拝察
.
当該解法,
強相関0–1
問題等 困難 構造 持0–1KP
変種
,
解 完成 域. , kKP 0–1KP
変換 多少 意味,
考.
本題 這入 前, 0–1KP
其 亜種kKP
就 簡単 記.
0–1KP ,
共 正整数 価値 重量 属性 持 大量 品物(
項) ,
背嚢(
)
重量制限(
容量)
内 価値最大 詰 問題̶ 容量 重項
,
全項 這入 場合 除外 ̶,
式 書N := { 1, 2, . . . , n}
z ∗ := max { ∑
j∈N p j x j | ∑
j∈N w j x j ⩽ c, x j ∈ { 0, 1 }} p j , w j
項j ∈ N
価値 重量, 0–1
変数x j
其 選択(x j = 1)/
非選択 夫夫 表.
加,
与 項 総数n,
容量c .
特,
以下 出 『解』 文言,
項 選択 同 ̶通常, n
次元x := (x j ) j ∈ N
解 呼本稿
x j = 1 ⇔ j ∈ S
見做 集合S ( ⊆ N)
解 呼.
中,
制約 満 解実行可能
(feasible)
云.
最大z ∗
最適値,
実現(
最適)
解 実行可能. , ∑
j∈N x j
詰 項 総数 示,
先 同一視,
解x
項数其
∑
j x j
指.
0–1KP ,
詰 項数k
以下 課 亜種kKP,
狭k even (i.e., ∑
j x j = k)
制限
E-kKP . kKP
一旦別 問題 経由0–1KP
変換,
拙稿[3, 4]
都合四種 言及
.
本稿,
変換後,
少 項数,
小 係数 目標,
直接 変換 模索.
∗
E-mail address: [email protected]
1
2 重量 工夫
以下
→
表記,
変換 示.
失敗例 一:
拙稿[2] E- k KP → 0–1KP P
削除
kKP → 0–1KP
得.
拙稿[2]
提案E-kKP → 0–1KP , p 1 ⩾ p 2 ⩾ · · · ⩾ p n w 1 ⩽ w 2 ⩽ · · · ⩽ w n
仮定(
孰 項 並 替 指示)
下, E-kKP
一 実行可能解 与 価値pmin
使P := W := max { ∑ k−1
j=1 p j − pmin + 1, c − ∑ k+1
j=1 w j + 1, 0 }
且(p j ′ , w j ′ ) :=
(p j + P, w j + W), c ′ := c + kW . P
変換後 得0–1KP
最適解 項数k
以上
,
逆W k
以下.
拙稿[2]
指摘, E-kKP → 0–1KP
単P
消kKP → 0–1KP .
本節 簡単
w 1 ⩽ w 2 ⩽ · · · ⩽ w n
仮定. ∑ k+1
j=1 w j > c
其 儘0–1KP
解 良.
状況 人工的 作 出,
先W := max {c − ∑ k+1
j=1 w j + 1, 0 } , w j ′ := w j + W , c ′ := c + kW
操作 ̶∑ k+1
j=1 w j ′ = ∑ k+1
j=1 w j + ( k + 1) W ⩾ kW + c + 1 = c ′ + 1. W = 0
其c − ∑ k+1
j=1 w j + 1 ⩽ 0
含意,
実際W = 0
可.
操作 欠点,
項数ℓ < k
重量制限超過 解 変換後
(k − ℓ)W slack feasible ( ⩽ c ′ )
転 得(
詳細,
例 交 後述
). ,
項数ℓ < k
解,
価値penalty
課,
論外.
項数ℓ
解最適
.
,
拙稿[2]
提示, > c
拘⩽ c ′ kKP
具体例(instance)
再掲:
j 1 2 3 4 5 6 w j 1 1 1 2 3 3
c 5
k 3
(1)
W = max {c − ∑ k+1
j=1 w j + 1, 0 } = 1 , w 5 + w 6 > c w 5 ′ + w 6 ′ = 8 ⩽ c + kW
残念;
此処 欲
w 5 ′ + w 6 ′ > c ′
満kKP → 0–1KP
枠組.
拙稿[3]
最初 変換,
項 数j < k
就c ′ := c + jW ,
項数k
未満 場合 容量 項数 応 変 対処(
結果
, 0–1KP
̶rubber knapsack [5, p. 416]).
以外 術*1 .
云,
c + kW
各w j W
加 上k
上界 自然, W = 0 { 1, 2, 3, 4 }
詰 得W ⩾ 1
必須*2 ,
鯔 此 操作w 5 ′ + w 6 ′ ⩽ c ′
避 得*3 ,
何 別 工夫方 好
.
失敗 得 指針
,
項数k
超 一律 排除, k
以下 儘 手 加 云.
式 書,
∑
j
w j x j + max
∑
j
x j − k, 0
× c ⩽ c
*1 思
,
各項 足W
係数 可変, (1 + max { k − ∑
j
x
j, 0 } / ∑
j
x
j)W .
此,
項 重量 整数性 保証,
以前∑
j
x
j 決(見 )
解 方自体 工夫 必要.
*2定義
W ⩾ 0 , W ̸ = 0 W ⩾ 1 (前述 , W = 0 c < ∑
k+1j=1
w
j 暗喩).
実際,原点 立 返, 5 + 4W = ∑
k+1j=1
w
j+ (k + 1)W > c
′= 5 + 3W W > 0
導.
蛇足 若 軽 方 四 重量和6 W > −1
得W = 0
可.*3
w
5′+ w
6′= c + 1 + 2W ⩽ c + 3W = c
′2
.
変形,
∑
j
w j x j ⩽ min
k − ∑
j
x j , 0
× c + c = min
c
k + 1 − ∑
j
x j
, c
此,
拙稿[3]
二番目,
項数⩽ k
容量c
後0 c( ∑
j x j )
持 潰 問題(
後述)
経由 同 発想,
新 知見 得 居.
,
先kKP (1)
於,
解{ 1, 2, 3, 4 } { 5, 6 } infeasible (
捨)
方策,
如何.
3 価値 工夫
,
前節 取 上,
重量W
用 操作 此 以上 望.
価値 操作 補,
拙稿[3]
三 目 紹介kKP → E-kKP → 0–1KP . ,
価値 操作,
最適解 項数
k
以上 引 上,
項数ℓ < k
解 重量W
持 項(k − ℓ)
附加得
, > c
解> c ′
導 ̶E-kKP
項数k
解 対象,
項 加項数
k
未満 附⩽ c ′
最適.
他,
価値 何 別働
.
元
kKP ,
項数k
未満 且> c
解 負 価値 持 考.
変換前 重量∑
j w j ′ x j − W ∑
j x j ,
例(k − ∑
j x j ) × max { ∑
j w j ′ x j − W ∑
j x j − c, 0 } × ∑
j p j
価値 引 佳*4
其
0–1KP
離.
単純0–1KP
解,
変換 意味*5 .
何 他 手.
4
話題
.
潰 問題(CKP)
新 解法 提案 由[1]. CKP
重量制限 定数c
,
詰 項 総数 定義域 単調非増加 函数c( ∑
j x j ) *6 ,
実k KP , j ⩽ k
c(j) = c
後= 0 c( · )
持CKP
同値.
恐 効率的 手法, kKP
直接解場合
CKP
解 場合 比較 一興 思.
此 特異c( · )
利用,
何 当該手法 効率 高tips
引 出.
参考文献
[1] Federico Della Croce, Fabio Salassa and Rosario Scatamacchia, A new exact approach for the 0–1 Collapsing Knapsack Problem. European J Oper Res, 9 Dec 2016, in press, http://dx.doi.org/
10.1016/j.ejor.2016.12.009.
*4
⩽ c
′= c + kW
見,
項数k ⩽ c
出, (k − ∑
j
x
j)
無 可.*5選択 項 組
,
単純∑
j
p
jx
j 計算 一手間加,
多少0–1KP
解法 手 入 避 度
.
*6項 詰 文字通 潰 容量 小
,
即, c(1) ⩾ c(2) ⩾ · · · ⩾ c(n).
別 見方,
各項 詰 厳重 個包装 必要