Linear Relaxation for Hub Network Design Problems

Presentation on theme: "Linear Relaxation for Hub Network Design Problems"— Presentation transcript:

1 Linear Relaxation for Hub Network Design Problems
東京大学 齋藤廣大 東京大学 松浦史郎 東京大学 松井知己

2 Hub Network

3 線形緩和問題→Hitchcock 型輸送問題 計算実験
Hub Network Problem ここで扱う問題： ハブ空港は与えられている｡ 各非ハブ空港は, 唯一のハブ空港に接続｡ 非ハブ空港間の輸送はハブを経由する｡ 全てのハブ空港対は直接繋がっている｡ 目的関数：総輸送費用の最小化 研究内容： 非凸2次計画としての定式化 線形緩和問題→Hitchcock 型輸送問題 計算実験

4 + ∑ (i,j)∈H×H cij xpi xqj + ∑j∈H cjq xqj )
定式化 H，N：ハブ空港, 非ハブ空港 の集合 cij ：空港 i から j への単位輸送費用 wij ：空港 i から j への需要量 min. ∑(p,q)∈N×N wpq (∑i∈H cpi xpi + ∑ (i,j)∈H×H cij xpi xqj + ∑j∈H cjq xqj ) s. t. ∑i∈H xpi =1 (∀p∈N), ：どこかに接続 xpi∈｛0,1｝（∀(p,i)∈N×H). xpi =1⇔ 非ハブ p はハブ i に接続する

5 + ∑ (i,j)∈H×H cij xpi xqj + ∑j∈H cjq xqj ) + ハブi からハブ j へ
目的関数 ∑(p,q)∈N×N wpq (∑i∈H cpi xpi + ∑ (i,j)∈H×H cij xpi xqj + ∑j∈H cjq xqj ) ∑全ての非ハブペア(p,q) (pからqへの需要) (pから接続するハブi へ + ハブi からハブ j へ + qに接続するハブ j からqへ ) p i j q cij cpi cjq hub

6 fpq(x)=∑ (i,j)∈H×H cij xpi xqj gpq(x)：関数fpq(x)の整数点での関数値の， 下側凸包をとった関数
2次項の線形化 fpq(x)=∑ (i,j)∈H×H cij xpi xqj gpq(x)：関数fpq(x)の整数点での関数値の， 下側凸包をとった関数 fpq 1 x1 x2 gpq x2 1 1 x1

7 + ∑ (i,j)∈H×H cij xpi xqj + ∑j∈H cjq xqj )
線形化と連続緩和 min. ∑(p,q)∈N×N wpq (∑i∈H cpi xpi + ∑ (i,j)∈H×H cij xpi xqj + ∑j∈H cjq xqj ) s. t. ∑i∈H xpi =1 (∀p∈N), xpi∈｛0,1｝（∀(p,i)∈N×H). 線形化＋連続緩和 + gpq(x) + ∑j∈H cjq xqj ) 1≧xpi≧0 （∀(p,i)∈N×H).

8 Primal Approach

9 xq3 =1 xp1 =1 fpq(x)= c13 線形化＝Hitchcock 型輸送問題
fpq(x)=∑ (i,j)∈H×H cij xpi xqj hub 空港 hub 空港 非hub 空港 非hub 空港 1 2 3 4 p q xq3 =1 xp1 =1 fpq(x)= c13

10 xq2 =1 xp3 =1 fpq(x)= c32 線形化＝Hitchcock 型輸送問題
fpq(x)=∑ (i,j)∈H×H cij xpi xqj hub 空港 hub 空港 非hub 空港 非hub 空港 1 2 3 4 p q xq2 =1 xp3 =1 fpq(x)= c32

11 xq2 =1 fpq(x)= c32 線形化＝Hitchcock 型輸送問題 fpq(x)=∑ (i,j)∈H×H cij xpi xqj
hub 空港 hub 空港 0.2 0.7 非hub 空港 非hub 空港 1 2 3 4 p q 0.2 0.2 0.3 0.2 0.3 0.2 0.1 xq2 =1 0.5 0.1 fpq(x)= c32

12 xq2 =1 fpq(x)= c32 線形化＝Hitchcock 型輸送問題 fpq(x)=∑ (i,j)∈H×H cij xpi xqj
hub 空港 hub 空港 0.2 0.7 非hub 空港 非hub 空港 1 2 3 4 p q 0.2 0.3 0.2 0.3 0.2 xq2 =1 0.5 0.2 0.1 fpq(x)= c32 0.1

13 ∑ i∈H yij = xqj (∀j∈H）, fpq(x)=∑ (i,j)∈H×H cij xpi xqj
線形化 fpq(x)=∑ (i,j)∈H×H cij xpi xqj gpq(x)：関数fpq(x)の下側凸包をとった関数 ＝下記のHitchcock型輸送問題の最適値 min. ∑ (i,j)∈H×H cij yij ∑ i∈H yij = xqj (∀j∈H）, ∑ j∈H yij = xpi (∀i∈H）, yij ≧0 (∀(i,j)∈H×H ) .

14 輸送問題の内包 輸送問題の内包 Hub 空港 非hub空港

15 Dual Approach

16 fpq(x)=∑ (i,j)∈H×H cij xpi xqj gpq(x)：関数fpq(x)の整数点での関数値の， 下側凸包をとった関数
線形不等式 fpq(x)=∑ (i,j)∈H×H cij xpi xqj gpq(x)：関数fpq(x)の整数点での関数値の， 下側凸包をとった関数 これらの線形不等式を 直接記述する. 1 x1 x2 fpq gpq

17 fpq(x)=∑ (i,j)∈H×H cij xpi xqj gpq(x)：関数fpq(x)の下側凸包をとった関数
線形不等式 fpq(x)=∑ (i,j)∈H×H cij xpi xqj gpq(x)：関数fpq(x)の下側凸包をとった関数 これらの線形不等式を 直接記述する. 1 x1 x2 gpq 線形不等式 ⇔ Hitchcock型輸送問題の 双対許容端点解 線形不等式の列挙 ⇔ 双対許容端点解の列挙

18 定理 [Balinski] 非退化の仮定のもとでは, n×n Hitchcock 型輸送問題の双対許容端点解は 2n-2Cn-1存在する.
線形不等式の列挙 ⇔ 双対許容端点解の列挙 定理 [Balinski] 非退化の仮定のもとでは, n×n Hitchcock 型輸送問題の双対許容端点解は 2n-2Cn-1存在する.

19 fpq(x)=∑ (i,j)∈H×H cij xpi xqj gpq(x)：関数fpq(x)の下側凸包をとった関数
等式不等式系のサイズ fpq(x)=∑ (i,j)∈H×H cij xpi xqj gpq(x)：関数fpq(x)の下側凸包をとった関数 変数 等式制約 不等式制約 (k : hub の数） Primal k k ー k2 Dual k-2Ck-1 k= ． k= ． k= ．

20 Skorin-Kapov, Skorin-Kapov, O’kelly[1994]
既往の研究との関連 Primal Approach Skorin-Kapov, Skorin-Kapov, O’kelly[1994] ハブが固定されていない問題について，定式化を提案．ハブの変数を固定すると，Primal Approach と同じ定式化になる Dual Approach Sohn and Park [1998] ハブが2個で固定されているとき，線形不等式系で整数解多面体を記述（多項式時間解法）．Dual Approach での不等式系を採用

21 CAB data: O’kelley : アメリカ ２５空港間データ 25空港から3つを選んでHub空港として計算機実験を行った．
すべての計算実験例において，線形緩和問題を解く事で整数最適解が選ばれた. Primal Approach と Dual Approach では， Primal Approach の方が計算機時間は早い． どの問題も5~8分程度で解ける． (lp solve)

22 おわり