パラメトリック電力需給ネットワーク西関研究室 9527 森下志保 1 電力需給ネットワーク全ての点は供給点又は需要点である供給量,需要量が定数(一定) 定常ネットワーク供給量,需要量が変動し, パラメータ𝜆の関数パラメトリックネットワーク 𝜆:時間,気温,石油価格,風力量等 2 定常ネットワーク需要点 2 8 15 3 2 2 3 15 8 3 必要な需要量供給点 2 1 7 1 供給可能な供給量供給点需要点 3 定常ネットワーク 13 許容分割 8 15 15 3 7 15 2 3 2 2 8 3 2 1 7 1 ・各部分グラフは連結である・各部分グラフは丁度一つの供給点を持つ・供給量は需要量の合計以上である供給点需要点線形時間判定アルゴリズム O(n) [Ito et al. 2005] n : 点数 4 許容分割がない定常ネットワーク 14 7 10 28 8 10 6 15 12 14 12 18 4 2 42 5 許容分割がないときすべての需要量𝑑𝑣 を一様に𝑟倍(0 ≤ 𝑟 < 1)に減少させ,新たに需要量を 𝑑′𝑣 = 𝑟・𝑑𝑣 として, 許容分割があるようにする供給率最大化問題このような𝑟の最大値𝑟 ∗ を求める (𝑟 ∗ :最大供給率) 1 − 𝑟 ∗ : 最小節電率 6 𝑟 = 0.7 𝑑′𝑣 = 0.7・𝑑𝑣 の新しいネットワーク 14 7 10 28 8 10 6 15 12 14 12 18 4 2 42 7 𝑟 = 0.7 𝑑′𝑣 = 0.7・𝑑𝑣 の新しいネットワーク 9.8 4.9 7.0 28 5.6 9.8 + 7.0 + 4.9 + 5.6 ≤ 28 7.0 最大供給率 𝑟 ∗ = 0.7 許容分割がある 4.2 10.5 8.4 14 8.4 12.6 2.8 1.4 42 7.0 + 4.2 + 2.8 = 14 𝑟 ∗ (10 + 6 + 4) = 14 10.5 + 8.4 + 1.4 + 8.4 + 12.6 ≤ 42 8 結果1 • 点数𝑛の定常木ネットワーク𝑇の最大供給率 𝑟 ∗ を𝑂 𝑛𝐿 時間で求める多項式時間アルゴリズムを求めた 𝐿: 𝑇の対数サイズ 9 パラメトリックネットワーク需要量𝑑𝑣 (𝜆)や供給量𝑠𝑣 (𝜆)が変数𝜆とともに変化ビルの需要量 0 8 野球場の需要量 17 λ 24 時間 0 区分的線形 8 17 23 24 λ 時間 10 パラメトリックネットワーク水力発電所の供給量 0 太陽光発電所の供給量 λ 24 0 時間区分的線形 7 10 λ 17 19 24 時間 11 パラメトリック木ネットワークの許容分割問題 𝑠1 (𝜆) 許容分割があるような𝜆 の値全てを求める 𝑑2 (𝜆) 𝑠3 (𝜆) 6 𝑑4 (𝜆) 8 𝑑5 (𝜆) 5 2 𝑑6 (𝜆) 𝑓𝑇 (𝜆) λ 12 パラメトリック木ネットワークの許容分割問題 𝑠1 (𝜆) 許容分割があるような𝜆 の値全てを求める 𝑑2 (𝜆) 6 𝑠3 (𝜆) 𝑑4 (𝜆) 8 𝑑5 (𝜆) 5 2 𝑑6 (𝜆) 𝑓𝑇 (𝜆) λ 区間区間区間 13 結果2 • パラメトリック木ネットワークの許容分割問題を𝑂 𝑛𝑊 2 時間で解く擬多項式時間アルゴリズムを与えた 𝑊:供給量と需要量を表す区分的線形関数の全ての整数係数の絶対値の合計 14 予備スライド質問用 𝜆の値による分割の変化 1 2 余裕量 𝑓𝑇 (𝜆) 𝑑1 𝑑2 8 8 𝑩=𝟑 𝑷=𝟓 区間区間 𝜆の値による分割の変化 2 2 余裕量 𝑓𝑇 (𝜆) 𝑑1 𝑑2 8 8 𝑩=𝟑 𝑷=𝟓 区間区間分割が変わるタイミング 2 余裕量 𝑓𝑇 (𝜆) 𝑑1 𝑑2 𝑑1 𝑑2 8 8 8 8 例えばここ 𝑷=𝟓 区間 2 区間・グラフが折れ曲がるところ・直線で変わることもある対数サイズ𝐿について • 点数𝑛の定常木ネットワーク𝑇の最大供給率 𝑟 ∗ を𝑂 𝑛𝐿 時間で求める多項式時間アルゴリズムを求めた 𝐿: 𝑇の対数サイズ 𝐿= log 𝑠𝑣 + log 𝑑𝑣 ＊logの底は2 ＊(𝑠や𝑑を二進数にしたときの桁数の合計) 供給率最大化問題の理由 (最小節電率ではない理由) 需要量𝑑𝑣 を 𝑑′𝑣 = 𝑟・𝑑𝑣 として, 許容分割があるようにする (最大供給率の場合) 最大供給率で解くほうがわかりやすい式になるから需要量𝑑𝑣 を 𝑑′𝑣 = (1 − 𝑟 ∗ )・𝑑𝑣 として, 許容分割があるようにする (最小節電率の場合) 定常ネットワークの許容分割 13 需要点 8 2 供給点 15 3 15 2 18 2 2 3 3 15 供給可能な供給量 8 供給点需要点 2 1 18 1 5 20 4 2 1 1 5 6 1 2 必要な需要量部分グラフは連結成分であるパラメトリック電力需給ネットワーク線形時間アルゴリズム O(n) [Ito et al. 許容分割がある 2005] 18 23 𝑟 = 0.7 𝑑′𝑣 = 0.7・𝑑𝑣 の新しいネットワーク 14 7 10 28 8 9.8 + 7.0 + 4.9 + 5.6 = 27.3 ≤ 28 10 最大供給率 𝑟 ∗ = 0.7 許容分割がある 6 15 12 14 12 18 4 2 42 7.0 + 4.2 + 2.8 = 14 𝑟 ∗ (10 + 6 + 4) = 14 10.5 + 8.4 + 1.4 + 8.4 + 12.6 = 41.3 ≤ 42 パラメトリック電力需給ネットワーク 24 結果1 • 点数𝑛の定常木ネットワーク𝑇の最大供給率 𝑟 ∗ を𝑂 𝑛𝐿 時間で求める多項式時間アルゴリズムを求めた 𝐿: 𝑇の対数サイズ 𝐿 = log 𝑠𝑣 + log 𝑑𝑣 • アイディア 𝑆 1≤𝑧 ≤𝑆∙𝐷 𝑧 𝑆 = 𝑠𝑣 , 𝐷 = 𝑑𝑣 𝑟∗ ∈ • 𝑟 ∗ は有理数 • 伊藤らの判定アルゴリズムを利用した二分探索パラメトリック電力需給ネットワーク 25 パラメトリック木ネットワーク許容分割問題 𝑠1 (𝜆) 2 𝑠3 (𝜆) 6 すべての𝜆に対して許容分割があるか？ 𝑑4 (𝜆) 8 𝑑5 (𝜆) 5 2 𝑑6 (𝜆) 𝑓𝑇 (𝜆) λ 26 パラメトリック木ネットワークの許容分割問題 𝑠1 (𝜆) 2 6 𝑠3 (𝜆) 許容分割がある𝜆 の値全て？ 𝑑4 (𝜆) 8 𝑑5 (𝜆) 5 2 𝑑6 (𝜆) 𝑓𝑇 (𝜆) λ 区間区間区間 27 結果2 • パラメトリック木ネットワークの許容分割問題を𝑂 𝑛𝑊 2 時間で解く擬多項式時間アルゴリズムを与えた 𝑊:供給量と需要量を表す区分的線形関数の全ての整数係数の絶対値の合計 𝑊 = 𝑣 𝐵𝑖=1 𝑎𝑣𝑖 + 𝑏𝑣𝑖 区間𝑖で 𝑠𝑣 𝜆 , 𝑑𝑣 𝜆 = 𝑎𝑣𝑖 𝜆 + 𝑏𝑣𝑖 • アイディア • 葉から根に向かって, 各部分木𝑇 ′ の根から出せる電力量, 即ち余裕量𝑓 𝑇 ′ (𝜆)を動的計画法で計算するパラメトリック電力需給ネットワーク 28 余裕量𝑓 𝑇′ (𝜆) 部分木𝑇 ′ 𝑇 ′ 不足量𝑔 𝑇′ (𝜆) 𝑇′ 𝑓 𝑇′ 𝜆 :部分木𝑇 ′ 内の全ての需要点を充足させたときに, 𝑇 ′ の根から出せる最大量 𝑔 𝑇′ 𝜆 : 𝑇 ′ 内の全ての需要点を充足させるために, 𝑇 ′ の根から入れないといけない最小量パラメトリック電力需給ネットワーク 29 𝑓 𝑇′ (𝜆) 𝑔 𝑇′ (𝜆) 𝑇 𝑂(𝑃)時間合計𝑂(𝑛𝑃)時間 ′ 𝑇1 𝑇2 𝑇の𝑓𝑇 𝜆 と𝑔𝑇 𝜆 は, 𝑇 ′ の部分木内𝑇1 と𝑇2 のそれらから計算できるパラメトリック電力需給ネットワーク 30 2 余裕量 𝑓𝑇 (𝜆) 𝑑1 𝑑2 8 8 𝑩=𝟑 𝑷=𝟓 区間区間 𝑑𝑣 𝜆 や𝑠𝑣 𝜆 の折れ点 𝑏𝑟𝑒𝑎𝑘𝑝𝑜𝑖𝑛𝑡 𝑓𝑇 (𝜆)の折れ点𝒑の個数 𝑷 ≤ 2𝑊 2 𝑏 𝑊 = 𝑣 𝐵𝑖=1 𝑎𝑣𝑖 + 𝑏𝑣𝑖 , 𝑝 = 𝑎 , 𝑎 , 𝑏 ≤ 𝑊 パラメトリック電力需給ネットワーク区間𝑖で𝑑𝑣 𝜆 = 𝑎𝑣𝑖 𝜆 + 𝑏𝑣𝑖 31 3 8 − 𝑑2 3 − 2 = 3 2 余裕量 𝑓𝑇 (𝜆) 連続折れ点数≤ 𝑊 2 𝑑1 𝑑2 8 8 𝑩=𝟑 𝑷=𝟓 3 区間区間 𝑑𝑣 𝜆 や𝑠𝑣 𝜆 の折れ点 𝑏𝑟𝑒𝑎𝑘𝑝𝑜𝑖𝑛𝑡 𝑓𝑇 (𝜆)の折れ点𝒑の個数 𝑷 ≤ 2𝑊 2 𝑏 𝑊 = 𝑣 𝐵𝑖=1 𝑎𝑣𝑖 + 𝑏𝑣𝑖 , 𝑝 = 𝑎 , 𝑎 , 𝑏 ≤ 𝑊 パラメトリック電力需給ネットワーク区間𝑖で𝑑𝑣 𝜆 = 𝑎𝑣𝑖 𝜆 + 𝑏𝑣𝑖 32 3 8 − 𝑑1 3 − 2 = 3 2 余裕量 𝑓𝑇 (𝜆) 連続折れ点数≤ 𝑊 2 𝑑1 𝑑2 8 8 𝑩=𝟑 𝑷=𝟓 3 区間区間 𝑑𝑣 𝜆 や𝑠𝑣 𝜆 の折れ点 𝑏𝑟𝑒𝑎𝑘𝑝𝑜𝑖𝑛𝑡 𝑓𝑇 (𝜆)の折れ点𝒑の個数 𝑷 ≤ 2𝑊 2 𝑏 𝑊 = 𝑣 𝐵𝑖=1 𝑎𝑣𝑖 + 𝑏𝑣𝑖 , 𝑝 = 𝑎 , 𝑎 , 𝑏 ≤ 𝑊 パラメトリック電力需給ネットワーク区間𝑖で𝑑𝑣 𝜆 = 𝑎𝑣𝑖 𝜆 + 𝑏𝑣𝑖 33 8 − 𝑑2 8 = 0 余裕量 𝑓𝑇 (𝜆) 2 𝑑1 𝑑2 8 8 非連続折れ点数≤ 𝑊 2 𝑩=𝟑 𝑷=𝟓 8 区間区間 𝑑𝑣 𝜆 や𝑠𝑣 𝜆 の折れ点 𝑏𝑟𝑒𝑎𝑘𝑝𝑜𝑖𝑛𝑡 𝑓𝑇 (𝜆)の折れ点𝒑の個数 𝑷 ≤ 2𝑊 2 𝑏 𝑊 = 𝑣 𝐵𝑖=1 𝑎𝑣𝑖 + 𝑏𝑣𝑖 , 𝑝 = 𝑎 , 𝑎 , 𝑏 ≤ 𝑊 パラメトリック電力需給ネットワーク区間𝑖で𝑑𝑣 𝜆 = 𝑎𝑣𝑖 𝜆 + 𝑏𝑣𝑖 34 辺容量があるときも同様 (1) 最大供給率𝑟 ∗ 𝑂(𝑛𝐿)時間 𝑟 ∗ = 0.7 (フロー) パラメトリック電力需給ネットワーク 35 辺容量があるときも同様 (2) パラメトリック木ネットワークの許容分割問題 𝑠1 (𝜆) 𝑐1 (𝜆) 𝑐2 (𝜆) 𝑠3 (𝜆) 𝑓𝑇 (𝜆) 9 2 𝑑4 (𝜆) 𝑑5 (𝜆) 𝑐3 (𝜆) 10 6 8 5 6 𝑂(𝑛𝑊 2 )時間 7 2 2 𝑐4 (𝜆) 𝑑6 (𝜆) λ 区間区間区間パラメトリック電力需給ネットワーク 36 結論 • 定常木ネットワークの最大供給率𝑟 ∗ を求めるアルゴリズム 𝑂(𝑛𝐿) 𝐿: 𝑇の対数サイズ • パラメトリック木ネットワークの許容分割問題を解く擬多項式時間アルゴリズム 𝑂(𝑛𝑊 2 ) 𝑊:整数係数の絶対値の合成パラメトリック電力需給ネットワーク 37 辺容量のある定常ネットワーク辺容量 14 7 10 6 20 28 8 10 7 14 4 8 12 25 12 11 18 40 4 7 供給点 15 20 9 3 10 5 2 3 42 需要点パラメトリック電力需給ネットワーク 38 供給率最大化問題定常ネットワーク・供給量と需要量が正の数多項式時間𝑂 𝑛𝐿 で解くことができることの証明パラメトリック電力需給ネットワーク 39 文字の定義 𝑉：点集合 𝐸：辺集合 𝑉𝑠 ：全ての供給点の集合 𝑉𝑑 ：全ての需要点の集合 𝐺 = 𝑉, 𝐸 𝑉 = 𝑉𝑠 ∪ 𝑉𝑑 , 𝑉𝑠 ∩ 𝑉𝑑 = ∅ 𝑛= 𝑉 𝑛𝑠 = |𝑉𝑠 | ( 点の個数 ) ( 部分グラフの個数 ) パラメトリック電力需給ネットワーク 40 9.8 4.9 7.0 28 5.6 7.0 4.2 10.5 8.4 14 8.4 12.6 2.8 1.4 42 パラメトリック電力需給ネットワーク 41 定常ネットワークと計算時間供給率最大化問題・ NP困難である分割問題・線形時間で解ける (既存の研究より) パラメトリック電力需給ネットワーク 42 削除スライドネットワーク𝐺の分割と分割問題部分グラフ𝐶 全ての部分グラフ𝐶が 𝐶の需要量𝑑𝑣 𝜆 の合計<𝑠𝑣 𝜆 ・連結成分が含まれている・丁度一つの供給点をもつ 2 𝑑𝑣3 8 部分グラフC 𝐺は分割可能である 2 𝑑𝑣4 8 𝑑𝑣3 𝑑𝑣4 𝐺の分割問題 𝜆に対し𝐺は分割をもつかどうかを問う問題 8 8 パラメトリック電力需給ネットワーク 44 分割問題と供給率最大化問題電力配送ネットワークに対する電力供給問題に適用供給量又は需要量時間,気温等パラメータ𝜆に依存するパラメトリック電力需給ネットワーク 45 パラメトリック木ネットワーク 𝑠𝑣 𝜆 :点𝑣の供給量 𝑑𝑣 𝜆 :点𝑣の需要量許容分割がある𝜆 の範囲全て？解 :区間 𝟎 ≤ 𝝀 ≤ 𝟖 と 𝟏𝟎 ≤ 𝝀 2 𝑑1 ●破点 𝑑2 𝑩=𝟑 𝑠𝑣 𝜆 =8 8 8 パラメトリック電力需給ネットワーク 46 今後の課題パラメトリックネットワーク木に辺容量がある場合, もしくはない場合にFPTASがあるか 2 供給可能な供給量 7 𝑑𝑣3 4 必要な需要量 𝑑𝑣4 8 6 8 8 辺容量パラメトリック電力需給ネットワーク 47 今後の課題 • 分割問題の最大化版である最大分割問題をパラメトリック木ネットワークに対し近似的に解くFPTAS? パラメトリック電力需給ネットワーク 48