電力取り引きにおける約定量決定問題の高速解法

スポンサーリンク

概要

• 論文の詳細を見る

• 2005年4月に施行された改正電気事業法により, 電力会社以外の多くの一般企業が電力を売買することが可能になった.この際の売買によって得られる社会的利潤を最大にするような約定を求める約定量決定問題は, 入札エリアに対応する少数の頂点と, 電力の売買を希望する企業に対応する多数の頂点からなるネットワーク上での最小費用流問題として定式化できる.本稿では約定量決定問題に対し, 最小費用キャンセリングに基づく解法, および中央値発見による解法の2つの高速な解法を与える.入札エリアの数をk, 電力を売買したい企業の数をn, 各企業の希望する売買量の最大値をCとすると, 前者はO(k(n+k^2)(logC+logk)(k^3+logn))の時間で最適解を得ることができ, 後者はnに関して線形であるO(3^kkln)の時間で最適解を得ることができる.実際の電力売買においてはkの値は小さく, nの値は非常に大きいので, これらのアルゴリズムは高速である.なおこの問題は, 2005年4月に開設された卸電力取引市場システムの仕様に基づいている.

• 2005-05-19

著者

• 宇野 毅明

  国立情報学研究所

• 松井 知己

  中央大学理工学部

• 松井 知己

  東京大学

• 松井 知己

  東大・情報理工

• 宇野 毅明

  東京工業大学 システム科学専攻

• 宇野 毅明

  情報学研究所

• 宇野 毅明

  東京工業大学システム科学

• 清見 礼

  北陸先端科学技術大学情報科学研究科

• 清見 礼

  北陸先端科学技術大学院大学

• 清見 礼

  国立情報学研究所

• 宇野 毅明

  国立情報学研

• 宇野 毅明

  国立情報学研究所:総合研究大学院大学

• Tomomi Matsui

  Department of Information and System Engineering, Chuo University

関連論文

• 古典的オーヴァーハングパズルをLPで解く(ORメモランダム)
• 木における消防士問題に対する近似アルゴリズムの改良 (コンピュテーション)
• 弦グラフおよび弦二部グラフのクラスにおけるマッチングの数え上げ
• 木の均一分割問題
• パズル・ゲームに見る悪魔の証明
• 最短路高速検索のための階層メッシュ疎化法
• 2-E-5 最短路高速検索のための階層メッシュ疎化法(組合せ最適化と応用(3))
• Enumeration of Perfect Sequences of Chordal Graph (Acceleration and Visualization of Computation for Enumeration Problems)
• 2-E-17 Enumeration of Perfect Sequences of Chordal Graph
• コーダルグラフの完全列の列挙
• 距離遺伝的グラフの木表現とその応用
• コーダルグラフの独立点集合の数えあげ問題
• スポーツスケジューリング
• 木構造の動的ネットワーク上の施設配置問題に対するO(nlog^2n)時間アルゴリズム
• 負の重みに対応した高速頻出集合発見プログラムの開発(人工知能,データマイニング)
• 木における消防士問題に対する近似アルゴリズムの改良
• 統計的機械翻訳におけるフレーズ対応最適化を利用したN-best翻訳候補のリランキング
• 1-E-4 Web版訪問介護スケジュール作成支援システム(スケジューリング)
• 計算幾何学的な手法を用いた高速相同性計算手法
• グラフクラスと部分グラフ同型性
• フルートの運指のモデル化とその最適化に関する研究
• 計算幾何学的な手法を用いた高速相同性計算手法
• 支配集合数え上げ問題とグラフクラス
• 1-C-8 ハブ空港配置問題の近似解法(離散最適化(1))
• Integer programming for a phrase alignment problem on statistical machine translation (21世紀の数理計画--最適化モデルとアルゴリズム--RIMS研究集会報告集)
• 解けないパズルをLPで解く : ペグソリティアとパゴダ関数と線形計画(ORメモランダム)
• Dependent Rounding Technique(従属丸め技法) : 最小カット問題の整数性(新・ORの図解,学会創立50周年記念号)
• 新入生のための数学ブートキャンプ(後編)
• 新入生のための数学ブートキャンプ(前編)
• A-1-3 自律移動ロボットの最適タスク計算(A-1.回路とシステム,一般セッション)
• フルートの運指最適化と逆最適化を用いたパラメータチューニング
• マルコフ連鎖の完璧シミュレーション(超ロバスト計算原理とモデリング・シミュレーション)
• クラス編成問題--素敵な出会いを演出します
• 多変量離散分布とマルコフ連鎖モンテカルロ法(学生セッション)
• データ結合問題で現れる多次元割当問題の近似解法
• ここまで解ける整数計画(堅く柔らかく…数理計画アプローチ再訪)
• 1-C-12 Approximation Algorithm for Multidimensional Assignment Problem Arising from Data Association Problem
• 1-C-9 フルートの運指のモデル化とその最適化に関する研究(離散最適化(2))
• 1-A-3 対戦日程計画におけるCarry-Over Effect最小化問題(離散最適化(1))
• 電力取り引きにおける約定量決定問題の高速解法
• 電力取り引きにおける約定量決定問題の高速解法(組合せ最適化(5))
• ロジスティクスにおける最適化ツールの開発(交通・輸送(2))
• パターンマイニングの新しい落としどころ : クラスタリングを用いたパターンマイニング(コンピュータビジョンとパターン認識のための機械学習と最適化,一般)
• パターンマイニングの新しい落としどころ : クラスタリングを用いたパターンマイニング(コンピュータビジョンとパターン認識のための機械学習と最適化,一般)
• ディジタルハーフトーニングへの応用に向けての魔方陣の一般化(2)
• ディジタルハーフトーニングへの応用に向けての魔方陣の一般化(1)
• ディジタルハーフトーニングへの応用に向けての魔方陣の一般化(2)
• ディジタルハーフトーニングへの応用に向けての魔方陣の一般化(1)
• 近傍ハッシュ法によるエラー許容頻出パターン列挙(一般セッション3)
• 2.情報爆発時代のための新しい超高速アルゴリズム(パートI:情報爆発時代における新しい基盤技術,情報爆発時代におけるわくわくするITの創出を目指して)
• 極小出現区間を用いたエピソードマイニングの高速化(データベース・アルゴリズム)
• 極小出現区間を用いたエピソードマイニングの高速化(データベース・アルゴリズム)
• データインテンシブコンピューティング : その2 頻出アイテム集合発見アルゴリズム(知能コンピューティングとその周辺〔第2回〕)
• 大規模幾何データからの高速な極大部分グラフ発見 (特集 「ウェブマイニング」および一般)
• ワイルドカードを許した極大モチーフの列挙アルゴリズム
• 大規模データ処理に対するアルゴリズム理論からのアプローチ (第20回 回路とシステム軽井沢ワークショップ論文集) -- (新世代の計算限界)
• 大規模木構造データからの頻出無順序木パターン発見アルゴリズム (計算機科学基礎理論の新展開)
• 大規模木構造データからの頻出部分構造パターン発見アルゴリズム(文字列アルゴリズム)
• 半構造データからの効率よい無順序木パターン発見手法(インターネット環境でのデータ工学とディペンダビィリティ及び一般)
• 半構造データからの効率よい無順序木パターン発見手法(インターネット環境でのデータ工学とディペンダビィリティ及び一般)
• 半構造データからの効率よい無順序木パターン発見手法
• 大規模木構造データからの高速な部分構造発見(「21世紀の知識情報科学に向けて」,及び一般)
• 2部クリークを用いたclosed item setの効率的な列挙(「21世紀の知識情報科学に向けて」,及び一般)
• 双対化を用いた新しい極大頻出アイテム集合の計算(「21世紀の知識情報科学に向けて」,及び一般)
• 中小規模スタッフスケジューリング問題における調整の容易なスケジュール作成に関する研究
• コーダルサンドイッチの列挙, ランダム生成, 数え上げについて (理論計算機科学の深化 : 新たな計算世界観を求めて)
• 2-F-5 多目的最適化への列挙アルゴリズム理論からのアプローチ(数理計画(1))
• UNO は一人でも難しい (計算機科学とアルゴリズムの数理的基礎とその応用)
• DK-2-4 大規模データに対する高速類似性解析手法の構築(DK-2.JSTさきがけセッション:人と社会のための情報処理,ソサイエティ企画)
• DK-2-4 大規模データに対する高速類似性解析手法の構築(DK-2.JSTさきがけセッション:人と社会のための情報処理,ソサイエティ特別企画,ソサイエティ企画)
• 擬似クリークを列挙する多項式時間遅延アルゴリズム
• RF-006 負の重みに対応した高速頻出集合発見プログラムの開発(人工知能・ゲーム,査読付き論文)
• Genome Homology Visualization by Short Similar Substring Enumeration (Acceleration and Visualization of Computation for Enumeration Problems)
• 2-E-18 ハミング距離の短い文字列ペア列挙アルゴリズムと解析ツール(組合せ論)
• 1-A-4 修正を前提としたExcelベースのスタッフスケジューリングツールの開発(つくばOR学生発表(5))
• スタッフスケジューリングにおける修正しやすさを考慮した解の分析 (21世紀の数理計画 : 最適化モデルとアルゴリズム)
• 1-B-8 スタッフスケジューリングにおける修正しやすさを知る為の実験とその考察(スケジューリング(2))
• 1-B-9 部品の取り外しを考慮した仕掛り在庫と受注の高速マッチング(スケジューリング(2))
• 木構造動的ネットワークにおける複数個の施設配置問題(組合せ最適化(5))
• RA-003 修正作業を効果的に支援するExcelベースのスタッフスケジューリングツールの開発(モデル・アルゴリズム・プログラミング,査読付き論文)
• ゲノム情報学における高速データ処理
• 列挙アルゴリズム(新・ORの図解,学会創立50周年記念号)
• 列挙を用いたモデリングの進展(モデリング-さまざまな分野,さまざまな視点から-)
• 近年の列挙技術の進展 : 計画立案と解法(ここまで使える数理計画法)
• DS-1-16 弦グラフおよびその部分クラスの列挙(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
• 頻出パターンの高速列挙
• 飽和系列パターンの多項式時間列挙アルゴリズム
• 飽和系列パターンの多項式時間列挙アルゴリズム
• 木に含まれる限定サイズ部分木の列挙 (コンピュテーション)
• On the base-line location problem for the maximum weight region decomposable into base-monotone shapes (New Trends in Algorithms and Theory of Computation)
• D-1-6 マッチングアルゴリズムを用いた匿名化手法の提案(D-1.コンピュテーション,一般セッション)
• 最適化から見たデータマイニング(活躍する機械学習)
• DS-1-5 ひとりにしてくれ数(DS-1.COMP学生シンポジウム,シンポジウムセッション)
• 最小完全ハッシュ関数を用いたグリッドグラフ上の効率的なパス数え上げ
• 超辺の縮約を許した非巡回部分超グラフの効率よい列挙
• 木に含まれる限定サイズ部分木の列挙
• 運用コストを重視した最適化 : 小規模な事業所で運用可能なシステムを考える(論文・研究レポート)
• 隣の芝は青くない
• 長さ極大な群れパターンを軌跡集合から効率良く発見するアルゴリズム
• 長さ極大な群れパターンを軌跡集合から効率良く発見するアルゴリズム(一般)

もっと見る 閉じる

スポンサーリンク