優先順位を考慮した大規模な一般化割当問題のためのデータ構造とアルゴリズム(<小特集>LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,制約充足問題の一つである大規模な一般化割当問題を解くためのデータ構造と近似解法を提案している.提案法では,多数の実行可能解のうちで所望の解を求めるために,資源の優先順位を設定し,制約式の実行不可能和を減少させるために整数計画問題を繰り返し解いている.本研究では,オペレーションズリサーチの分野で頻繁に現れる2次元配列の0-1割当変数x_<ij>が,大規模でスパースであるときに,キャッシュメモリのヒット率を向上させるためには,どのようなデータ構造であればよいのかを解析している.提案法では,複数の探索木を構成して,どの資源の割当てを変更すべきかを探索して調べ,探索したときの情報をアークとして保存している.複数の探索木を用いて状態空間探索を行う際に,探索に必要なメモリの断片化をさけるために,2重の「ごみ集め」を行っている.更に,現実の大規模な問題に提案法を適用するために,探索に必要なデータ構造を示している.
- 社団法人電子情報通信学会の論文
- 2002-02-01
著者
関連論文
- 優先順位付き割当問題のための大規模数値求解に関する考察
- 巡回セールスマン問題の定式化に関する一考察(組合せ(2))
- 日本の情報ネットワークおよびソフトウェアセンターに関する提言
- ジョブ・ショップ・スケジューリング問題のための時間帯割当の探索木を用いた近似解法
- 大規模な優先順位付き割当問題のための探索木を用いた近似解法
- 優先順位付き割当問題ための近似解法の数値実験による性能評価(グラフ・ネットワーク(1))
- モデル記述言語による引っ張り型生産指示方式の最適化モデリング
- 大規模な優先順位付き割当問題のための近似解法による数値シミュレーション実験(組合せ最適化(2))
- 探索木のアーク削除数を考慮した優先順位付き割当問題のための近似解法(組合せ最適化(4))
- 優先順位を考慮した割当問題の近似解法(組合せ最適化)
- 大規模非線形混合整数計画となる設備計画問題の近似解法と, その電力設備計画に対する適用
- 逐次線形計画を用いた制約付き潮流計算アルゴリズム
- 制約付き潮流計算に関する考察(理論)
- 制約付き潮流計算に関する考察(数値実験)
- 非線形計画を用いた制約付き潮統計算
- ロジステイクスに関する考察
- 優先順位を考慮した大規模な一般化割当問題のためのデータ構造とアルゴリズム(LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
- 割当問題の制約充足のための探索木のデータ構造
- スプレッドシートのためのまばらなデータの表示法