容量制約をもつネットワーク設計問題に対するn分割不等式

容量制約をもつネットワーク設計問題に対する n 分割
不等式
n Partition Inequalities for Capacitated Network Design
Problem
片山 直登 流通経済大学 流通情報学部
平成 27 年 2 月 13 日
1
はじめに
容量 制約 を もつネットワ ー ク 設計問題 (capacitated network design problem；CN D)
は ，ア ー ク 上 の フ ロ ー 量 が ア ー ク 容 量 以 下 で あ る と い う 容 量 制 約 を も つ 設 計 問
題 で あ る ．ア ー ク 容 量 は 通 信 回 線 容 量 や 輸 送 能 力 に 相 当 し ，容 量 制 約 を も た な い
ネットワ ー ク 設 計問題 に 比 べ よ り 現実的 なモデルとな る．容量制約があ るために，
容 量 制 約 を も た な い 問 題 に 比 べ て 最 適 値 と 緩 和 問 題 の 下 界 値 と の ギャップ が 大 き
く な る 傾 向 が あ る ．ま た ，デ ザ イ ン 変 数 を 固 定 し た フ ロ ー 問 題 が タ イ ト な 多 品 種
フ ロ ー 問 題 と な る た め ，実 行 可 能 解 を 求 め る こ と 自 体 に 手 間 が か か る な ど ，難 し
い問 題 と なる．
本 論 文 で は ，向 き の な い ア ー ク を 含 む 容 量 制 約 を も つ ネット ワ ー ク 設 計 問 題 を
対象 と し ，こ の問題 に 対 す る い くつかの妥当不等式を提案する．
2
問題の定式化
は じ め に ，本 研 究 で 対 象 と す る 容 量 制 約 を も つ ネット ワ ー ク 設 計 問 題 の 定 義 を
示す．
定義 2.1 (容量 制 約をも つ ネット ワーク設計問題 CN D) ノ ー ド 集 合 N ，デ ザ イ ン
費用 f ，フロ ー 費 用 c お よ び ア ーク容量 C をも つ向きのない アーク集合 A，需要 d
を も つ 品 種 集 合 K が 与 え ら れ て い る ．こ の と き ，す べ て の ア ー ク 上 の フ ロ ー 量 が
ア ー ク 容 量 以 下 で あ り，フ ロ ー 費 用 と デ ザ イ ン 費 用 の 合 計 を 最 小 に す る ア ー ク 集
合 A′ (⊆ A) と各 品 種の フ ロ ー を 求めよ．
ア ー ク (i, j) 上 の 品 種 k の i か ら j 向 き の 単 位 当 た り の フ ロ ー 費 用 を ckij ，フ ロ ー 量
を 表 す フ ロ ー 変 数 を xkij と す る ．ア ー ク (i, j) の デ ザ イ ン 費 用 を fij ，ア ー ク 容 量 を
Cij と す る ．ア ー ク (i, j) の 0–1 の デ ザ イ ン 変 数 を yij と し ，yij = 1 で あ れ ば ア ー ク
(i, j) を 選 択 し ，yij = 0 で あ れ ば ア ー ク (i, j) を 選 択 し な い こ と を 表 す．ま た ，品 種
k の 需 要 を dk と し ，ノ ー ド n を 端 点 と す る ア ー ク の 他 方 の 端 点 の 集 合 を Nn と す
る．こ のと き ，CN D のア ー ク フ ローによる定式化を示す．
∑
∑ ∑
fij yij
(1)
最小化
(ckij xkij + ckji xkji ) +
(i,j)∈A k∈K
条件
∑
xkin −
i∈Nn
∑
∑
(i,j)∈A
xknj = dkn
∀n ∈ N, k ∈ K
(2)
j∈Nn
(xkij + xkji ) ≤ Cij yij
k∈K
xkij + xkji ≤
xkij ≥ 0, xkji
yij ∈ {0, 1}
dk yij
≥0
∀(i, j) ∈ A
(3)
∀(i, j) ∈ A, k ∈ K
(4)
∀(i, j) ∈ A, k ∈ K
∀(i, j) ∈ A
(1) 式 は 目 的 関 数 で あ り，フ ロ ー 費 用 と デ ザ イ ン 費 用 の 総 和 を 最 小 化 す る ．(2)
式 は フ ロ ー 保 存 式 で あ る ．こ こ で ，dkn は ，ノ ー ド n が 品 種 k の 始 点 Ok で あ れ ば
−dk ，終点 Dk で あ れば dk ，それ 以外のノードであれば 0 である定数である．(3) 式
は ，ア ー ク (i, j) が 存 在 す る と き ，ア ー ク 上 の フ ロ ー 量 の 合 計 が ア ー ク 容 量 以 下 で
あ る こ と を 表 す 容 量 制 約 式 で あ る ．ア ー ク は 向 き を も た な い の で ，ア ー ク (i, j) 上
に は i か ら j 方 向 の フ ロ ー と j か ら i 方 向 の フ ロ ー が 存 在 す る ．(4) 式 は ，ア ー ク
(i, j) が 存 在 す る と き ，品 種 k の フ ロ ー が 最 大 で dk だ け 存 在 す る こ と を 表 す 強 制
制 約 式 で あ る ．dk > Cij で あ る 品 種 の 需 要 が 存 在 す る 場 合 ，こ の 制 約 式 の 右 辺 は
min(dk , Cij )yij に 置 き換 え る こ と ができる．
3
妥当不等式
強 制 制 約 式 を 含 む 定 式 化 で あって も 最 適 値 と 下 界 値 と の ギャップ は 比 較 的 大 き
く，線 形 緩 和 に よって 得 ら れ る 下 界 値 は そ れ ほ ど 良 く は な い ．そ の た め ，CN D に
対 し て 多 く の 妥 当 不 等 式 が 示 さ れ て お り，こ れ ら の 妥 当 不 等 式 を 制 約 と し て 加 え
る こ と に よって ，下 界 値 を 改 善 す る こ と が で き る ．こ こ で は ，向 き の な い 容 量 を
もつ ア ー クを想 定 する ．
容 量 制 約 を も つ ネット ワ ー ク 設 計 問 題 に 対 し て ，多 く の 妥 当 不 等 式 が 提 案 さ
れ て い る ．Magnanti et al. (1993) や Katayama and Kasugai (1993) は ，カット セット
上 の フ ロ ー と 容 量 に 対 す る 切 り 上 げ を 用 い た カット セット 不 等 式 を 示 し て い る ．
Magnanti et al. (1993) は，カットセット不等式に加え，3 ノードに対するカットセッ
ト不 等 式 および 剰 余容 量 不 等 式 を提案している．Chouman et al. (2003) は，最小基
数 不 等 式 ，被 覆 不 等 式 と そ れ ら の 持 ち 上 げ た 不 等 式 を 示 し ，分 離 問 題 と 生 成 方 法
を 示 し て い る ．Chouman and Crainic (2011) は ，フ ロ ー 被 覆 不 等 式 ，フ ロ ー パック
不 等 式 と そ れ ら の 生 成 方 法 を 示 し て い る ．Agarwal (2006) や Agarwal (2014) は ，サ
バイ バ ル ネット ワ ーク 設 計 問 題 に対する 3 および 4 分割不等式を示している．
2
S
S̄
(S, S̄)
図 1: カットセット 不等式
3.1
カットセット不等式
カット セット 上 の ア ー ク 容 量 と フ ロ ー 量 の 関 係 か ら 妥 当 不 等 式 を 導 く こ と が で
き る ．ノ ー ド 集 合 N を S と S̄(= N \S) に 分 割 す る ．S 内 の ノ ー ド と S̄ 内 の ノ ー ド
を 端 点 と す る ア ー ク 集 合 で あ る カット セット (S, S̄) と お く．ま た ，S に 含 ま れ る
ノ ー ド と S̄ に 含 ま れ る ノ ー ド を 始 点 と 終 点 ま た は 終 点 と 始 点 と す る 品 種 の 集 合 を
∑
K(S, S̄) とし，これ ら の品 種 の 需 要 量の和を D(S,S̄) (= k∈K(S,S̄) dk ) とおく．
こ の と き ，K(S, S̄) に 含 ま れ る 品 種 の フ ロ ー は ，カット セット (S, S̄) に 含 ま れ る
ア ー ク 上 を 少 な く と も 1 回 は 通 過 し な け れ ば な ら な い (図 1)．さ ら に ，(S, S̄) 上 に
は ，カット セット 上 を 通 過 す る フ ロ ー 量 以 上 の 容 量 が 必 要 で あ る の で ，次 式 が 成
り立 つ ．
∑
Cij yij ≥
(i,j)∈(S,S̄)
∑
∑
(xkij + xkji ) ≥ D(S,S̄)
∀S ⊂ N
(i,j)∈(S,S̄) k∈K(S,S̄)
カットセット (S, S̄) に含 ま れ る アークのアーク容量の最大値を C(S,S̄) (= max(i,j)∈(S,S̄) Cij )
とお く．
両辺 を C(S,S̄) で 割ると ，次 の 関係が成り立つ．
∑
(i,j)∈(S,S̄)
∑
yij ≥
(i,j)∈(S,S̄)
Cij
yij ≥
C(S,S̄)
∑
∑
(i,j)∈(S,S̄) k∈K(S,S̄)
D(S,S̄)
(xkij + xkji )
≥
C(S,S̄)
C(S,S̄)
∀S ⊂ N
左 辺 は 整 数 値 を と る た め ，次 の カット セット 不 等 式 (Chouman et al. 2003) は 妥 当
不等 式 と なる．
∑
(i,j)∈(S,S̄)
⌈
yij ≥
D(S,S̄)
C(S,S̄)
3
⌉
∀S ⊂ N
1
y12
y13
3
2
y23
図 2: 3 ノードネットワーク
3.2
3 ノード不等式
3 ノ ー ド と 各 ノ ー ド を 端 点 と す る 3 ア ー ク を も ち ，各 ノ ー ド を 始 点・終 点 と す る
3 品種 か ら構 成 される 3 ノー ド の ネットワークを考える (図 2)．このネットワークに
おけ る カットセット不等 式 (Magnanti et al. 1993) は，次の 3 つの式となる．
⌈
y12 + y13
⌉
d12 + d13
≥
,
max (C12 , C13 )
⌈
y12 + y23
⌉
d12 + d23
≥
,
max (C12 , C23 )
y13 + y23
⌈
d13 + d23
≥
max (C13 , C23 )
⌉
これ ら 3 式 の 和を 2 で 割 る こ と に よって，次の 3 ノード不等式を導くことができる．
⌈ (⌈
⌉ ⌈
⌉ ⌈
⌉)⌉
1
d12 + d13
d12 + d23
d13 + d23
y12 + y13 + y23 ≥
+
+
2
max (C12 , C13 )
max (C12 , C23 )
max (C13 , C23 )
⌈
⌉ ⌈
⌉
こ の 妥 当 不 等 式 は ， (d12 + d13 )/ max (C12 , C13 ) + (d12 + d23 )/ max (C12 , C13 ) +
⌈ 12
⌉
(d + d23 )/ max (C12 , C13 ) が奇 数 であれば，有効な妥当不等式となる．
3.3
最小基数不等式
カットセット (S, S̄) に 対 す る 最 小 基数 m(S,S̄) を次のように定義する．
m(S,S̄) = max{h|
h
∑
Cl <
l=1
∑
dk } + 1
k∈K(S,S̄)
こ こ で ，C1 , · · · , C|(S,S̄)| は カット セット (S, S̄) 上 の ア ー ク 容 量 を 降 順 に ソ ー ト し た
∑
も の で あ り， hl=1 Cl は 容 量 の 降 順 で h 番 目 ま で の ア ー ク 容 量 の 和 を とった も の で
あ る ．この た め カット セット (S, S̄) 上に は 少な く と も m(S,S̄) 本の ア ーク が 必 要で あ
り，m(S,S̄) は (S, S̄) の中 で 選 択 す べきアーク数の最小値となる (図 3)．
4
S
S̄
(S, S̄)
m( S, S̄)
図 3: 最小基数
S
S̄
(S, S̄)
E
図 4: カットセット と被覆
し た がって ，次 式の最 小 基 数 不等式 (Chouman et al. 2003) は妥当不等式となる．
∑
yij ≥ m(S,S̄)
(i,j)∈(S,S̄)
3.4
被覆不等式
E を カット セット (S, S̄) の 部 分 集 合 と す る (図 4)．カット セット (S, S̄) か ら E を 除
いた ア ー ク集合 (S, S̄)\E 上で ，K(S, S̄) のすべての需要を流せない，すなわち
∑
Cij < D(S,S̄)
(i,j)∈(S,S̄)\E
であ る と き，E を (S, S̄) の 被 覆 と よ ぶ．このとき，被覆に含まれるアークの少なく
とも 1 本以 上が 選 択さ れ な い と ，フ ローを流せないために実行不可能となる．
ま た ，E に含 ま れ るア ー ク 容 量 の最 小 値 の ア ーク を 加 え た とき に ，K(S, S̄) の す
5
べて の 需 要を流 せ る，す な わ ち
∑
Cij + min Cpq ≥ D(S,S̄)
(p,q)∈E
(i,j)∈(S,S̄)\E
であ る と き，E を (S, S̄) の最 小 被覆とよぶ．
(S, S̄) の す べての 被 覆 E に 対 し て，少なくとも被覆に含まれるアーク 1 本は選択
し な け れ ば な ら な い こ と か ら ，次 の 被 覆 不 等 式 (Chouman et al. 2003) は 妥 当 不 等
式と な る ．
∑
yij ≥ 1
(i,j)∈E
デ ザ イ ン 変 数 の 線 形 緩 和 解 y が 与 え ら れ て い る も の と す る ．次 の 分 離 問 題 を 解 く
こ と に よって ，CN D の 線 形 緩 和 解 を 満 足 し な い 可 能 性 の あ る 被 覆 を 見 つ け る こ
とが で きる ．
ϕ = 最小 化
∑
yij tij
(i,j)∈(S,S̄)
条件
∑
Cij tij >
∑
Cij − D(S,S̄)
(i,j)∈(S,S̄)
(i,j)∈(S,S̄)
tij ∈ {0, 1}
∀(i, j) ∈ (S, S̄)
こ こ で ，ϕ は こ の 分 離 問 題 の 最 適 値 で あ り，tij は ア ー ク (i, j) が 被 覆 E に 含 ま れ れ
ば 1，そう で なけれ ば 0 であ る こ と を表す 0-1 変数である．もし，ϕ < 1 であれば E
は 最 も 緩 和 解 を 満 足 し な い 被 覆 と な り，ϕ ≥ 1 で あ れ ば 緩 和 解 を 満 足 し な い 被 覆
が存 在 し ない．
こ の 分 離 問 題 は 0-1 ナップ サック 問 題 で あ り，比 較 的 容 易 に 最 適 解 を 求 め る こ と
がで き る ．しか し ，膨大 な 数 の カットセットに 対する分離問題を解くためには，よ
り 効 率 的 に 解 く こ と が 必 要 と な る ．そ こ で ，yij を 昇 順 に 並 べ 換 え ，昇 順 に 制 約 を
満 た す ま で 貪 欲 的 に tij = 1 と す る こ と で 近 似 解 を 求 め る と ，効 率 的 に 被 覆 E を 求
める こ と ができ る ．
4
4.1
n 分割不等式
3 分割不等式
3 ノ ー ド 不 等 式 は ，一 般 の ネット ワ ー ク に 拡 張 で き る ．ノ ー ド 集 合 N を S1 ，S2 ，
S3 に 3 分 割 し ，3 ノ ー ド ネット ワ ー ク 上 の ア ー ク を カット セット に 対 応 さ せ る (図
5)．この と き，カットセット (S1 , S̄1 )，(S2 , S̄2 )，(S3 , S̄3 ) に対するカットセット不等式
は次 式 と なる．
6
(S1 , S2 )
S1
S2
(S2 , S3 )
(S1 , S3 )
S3
図 5: 3 分割ネットワーク
∑
⌈
yij ≥
(i,j)∈(S1 ,S̄1 )
D(S1 ,S̄1 )
C(S1 ,S̄1 )
⌉
⌈
∑
,
yij ≥
(i,j)∈(S2 ,S̄2 )
D(S2 ,S̄2 )
C(S2 ,S̄2 )
⌉
,
∑
(i,j)∈(S3 ,S̄3 )
⌈
yij ≥
D(S3 ,S̄3 )
C(S3 ,S̄3 )
⌉
,
3 つ の 式 の 和 を と る と 左 辺 に は 同 じ デ ザ イ ン 変 数 が 2 つ ず つ 含 ま れ ，(S1 , S̄1 ) =
(S1 , S2 ∪ S3 ) などと な るこ と か ら ，次の 3 分割不等式を導くことができる．
∑
∑
∑
yij +
yij +
yij ≥
(i,j)∈(S1 ,S2 )
(i,j)∈(S1 ,S3 )
(i,j)∈(S2 ,S3 )
⌈ (⌈
⌉ ⌈
⌉ ⌈
⌉)⌉
D(S1 ,S̄1 )
D(S2 ,S̄2 )
D(S3 ,S̄3 )
1
+
+
2
C(S1 ,S̄1 )
C(S2 ,S̄2 )
C(S3 ,S̄3 )
⌉
⌉ ⌈
⌉ ⌈
⌈
この 妥 当 不等式 は ， D(S1 ,S̄1 ) /C(S1 ,S̄1 ) + D(S2 ,S̄2 ) /C(S2 ,S̄2 ) + D(S3 ,S̄3 ) /C(S3 ,S̄3 ) が奇
数で あ れ ば，有効な 妥 当 不 等 式 と なる．
4.2
4 分割不等式と n 分割不等式
3 分 割 不 等 式 は ，4 分 割 不 等 式 に 拡 張 で き る ．ノ ー ド 集 合 N を S1 か ら S4 に 4 分
割 す る (図 6)．こ の と き ，カット セット (Sp , S̄p ) に 対 す る カット セット 不 等 式 は 次 式
とな る ．
∑
(i,j)∈(Sp ,S̄p )
⌈
yij ≥
D(Sp ,S̄p )
C(Sp ,S̄p )
⌉
,
∀p = 1, 2, 3, 4
し た がって，次の 4 分割 不 等 式 は妥当不等式となる．
⌈ ∑
⌉⌉
3
4
4 ⌈
∑
∑
∑
D(Sp ,S̄p )
1
yij ≥
2
C(Sp ,S̄p )
p=1 q=p+1 (i,j)∈(Sp ,Sq )
p=1
7
(S1 , S2 )
S1
S2
(S1 , S3 ) (S2 , S3 )
(S1 , S4 )
(S2 , S4 )
S4
S3
(S3 , S4 )
図 6: 4 分 割ネット ワーク
ノ ー ド集 合 N を S1 から Sn に n 個に分割する．このとき，次の n 分割不等式は妥
当不 等 式 となる ．
n−1
∑
n
∑
∑
p=1 q=p+1 (i,j)∈(Sp ,Sq )
n 分割不等式は，
なる ．
5
⌈ ∑
⌉⌉
n ⌈
D(Sp ,S̄p )
1
yij ≥
2
C(Sp ,S̄p )
p=1
⌉
∑n ⌈
p=1 D(Sp ,S̄p ) /C(Sp ,S̄p ) が 奇 数 で あ れ ば ，有 効 な 妥 当 不 等 式 と
3 分割最小基数不等式と n 分割最小基数不等式
n 分 割 不 等 式 と 同 様 に ，最 小 基 数 不 等 式 を 3 分 割 不 等 式 に 拡 張 す る こ と が で き
る．ノ ー ド集 合 N を S1 ，S2 ，S3 に 3 分 割する ．また，カット セット (S, S̄) 上の最小
基 数 を m(S,S̄) と す る ．こ の と き ，カット セット (S1 , S̄1 )，(S2 , S̄2 )，(S3 , S̄3 ) に 対 す る
最小 基 数 不等式 は 次式 と な る ．
∑
∑
∑
yij ≥ m(S1 ,S̄1 ) ,
yij ≥ m(S2 ,S̄2 ) ,
yij ≥ m(S3 ,S̄3 )
(i,j)∈(S1 ,S̄1 )
(i,j)∈(S2 ,S̄2 )
(i,j)∈(S3 ,S̄3 )
これ ら の 式から ，次 の 3 分 割 最 小基数不等式は妥当不等式となる．
⌈
⌉
∑
∑
∑
)
1(
m
+ m(S2 ,S̄2 ) + m(S3 ,S̄3 )
yij +
yij +
yij ≥
2 (S1 ,S̄1 )
(i,j)∈(S1 ,S2 )
(i,j)∈(S1 ,S3 )
(i,j)∈(S2 ,S3 )
同 様 に ，次 の n 分 割 最 小 基 数 不等式は妥当不等式となる．
n−1
∑
n
∑
∑
yij ≥
⌉
⌈ ∑
n
1
m(Sp ,S̄p )
2
p=1
p=1 q=p+1 (i,j)∈(Sp ,Sq )
8
E(s1 ,s2 )
S2
S1
E(s2 ,s3 )
E(s1 ,s3 )
S3
図 7: 3 分割被覆
∑
n 分 最 小 基 数 割 不 等 式 は ， np=1 m(Sp ,S̄p ) が 奇 数 で あ れ ば ，有 効 な 妥 当 不 等 式 と
なる ．
6
3 分割被覆不等式と n 分割被覆不等式
ノ ー ド 集 合 N を S1 ，S2 ，S3 に 3 分 割 す る ．カット セット (Sp , Sq ) の 部 分 集 合 を
E(Sp ,Sq ) と する (図 7)．ただ し ，E(Sp ,Sq ) ∪ E(Sp ,Sr ) がカットセット (Sp , Sq ∪ Sr ) の被覆
であ る も のとす る ．
この と き ，被覆不 等 式 は 次 の よ うになる．
∑
∑
yij ≥ 1,
(i,j)∈E(S1 ,S2 ) ∪E(S1 ,S3 )
∑
yij ≥ 1,
(i,j)∈E(S1 ,S2 ) ∪E(S2 ,S3 )
yij ≥ 1
(i,j)∈E(S1 ,S3 ) ∪E(S2 ,S3 )
E(Sp ,Sq ) ∪ E(Sp ,Sr ) = E(Sp ,S̄p ) より，次の 3 分割被覆不等式を導くことができる．
∑
yij +
(i,j)∈E(S
∑
yij +
(i,j)∈E(S
1 ,S̄1 )
2 ,S̄2 )
∑
yij ≥ 2
(i,j)∈E(S
3 ,S̄3 )
ノ ー ド 集 合 N を S1 か ら Sn に n 個 に 分 割 す る ．カット セット (Sp , Sq ) の 部 分 集 合
E(Sp ,Sq ) におい て ，∪np=1,p̸=q E(Sp ,Sq ) がカットセット (Sp , S̄p ) の被覆であるものとする．
3 分 割被 覆 不等式 と 同様 に ，次 の n 分割被覆不等式は妥当不等式 となる．
n
∑
⌈ ⌉
n
yij ≥
2
∑
p=1 (i,j)∈E(S
p ,S̄p )
n 分割 被 覆不等 式 は，n が 奇 数 で あれば，有効な妥当不等式となる．
9
7
おわりに
本 論 文 で は ，向 き の な い ア ー ク を 含 む 容 量 制 約 を も つ ネット ワ ー ク 設 計 問 題 に
対 す る 3・4 お よ び n 分 割 不 等 式 ，3 お よ び n 最 小 基 数 不 等 式 ，な ら び に 3 お よ び n
被 覆 不 等 式 を 提 案 し た ．本 研 究 で は ，向 き の な い ア ー ク を も つ 問 題 を 対 象 と し ，
妥 当 不 等 式 を 示 し た に と ど まって い る ．今 後 ，向 き の あ る ア ー ク を も つ 問 題 が よ
り一 般 的 である た め，向き の あ るアークをもつ問題への拡張が必要である．また，
提 案 し た 妥 当 不 等 式 を 問 題 へ 追 加 し た 場 合 の 有 効 性 や 分 枝 カット 法 へ の 組 み 込 み
が必 要 で ある．
本研 究 は 科学 研 究費 基 盤 研 究 C(課題 番号 25350454) による成果の一部である．
参考文献
Agarwal, Y. 2006. k-partition-based facets of the network design problem. Networks 47 123–139.
Agarwal, Y. 2014. Design of survivable networks using three- and four-partition facets. Operations
Research 61 199–213.
Chouman, M., T. G. Crainic. 2011. Commodity representations and cutset-based inequalities for
multicommodity capacitated fixed-charge network design. Tech. Rep. CIRRELT-2011-56,
Centre de recherche sur les transports,Université de Montréal.
Chouman, M., T. G. Crainic, B. Gendron. 2003. A cutting-plane algorithm based on cutset inequalities for multicommodity capacitated fixed charge network design. Tech. Rep.
CIRRELT-2003-16, Centre de recherche sur les transports,Université de Montréal.
Katayama, N., H. Kasugai. 1993. A capacitated multi-commodity network design problem a solution method for finding a lower bound using valid inequalities. Journal of Japan
Industrial Management Association 44 164–175.
Magnanti, T. L., P. Mirchandani, R. Vachani. 1993. The convex hull of two core capacitated
network design problems. Mathematical Programming 60 233–250.
10