最小拘束問題の分枝限定法アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
与えられた0-1行列に対し,列を並べ替えることで,各行において1ができるだけ連続して現れるようにする問題を最小拘束問題と呼ぶことにする.最小拘束問題を厳密に解くことは難しく,商用ソフトのように線形計画法をベースにした分枝限定法では,例題ほどのサイズでさえも解くことが困難である.最小拘束問題には動的計画法によるアルゴリズムも知られており,小さな問題では効率良く解けるが,メモリの消費が指数的に増大するため,問題が大きくなるとたちまち限界に達する.しかし,動的計画法の考え方は,行数が小さい場合であれば,下界値を求めるために利用することもできる.本論文では,動的計画法をもとにした下界値を用いて,分枝限定法による厳密解法を開発している.さらに最適解の必要条件に基づいた枝刈りや下界値の強化の工夫も取り入れている.
- 2009-08-15
著者
関連論文
- 1-B-8 割当問題のミニマックス最適化(組合せ最適化(2))
- ナップサック制約付き最大全域木問題の一解法(組合せ(1))
- 最小全域木を全列挙するアルゴリズム(グラフ・ネットワーク(2))
- 1-B-4 最小経路費用木問題の厳密解法(離散最適化(1))
- 多目的ナップサック問題のマックスミン最適化(不確実性の下での意思決定と数理モデル)
- 1-B-7 2目的マックスミンナップサック問題の厳密解法(組合せ最適化(2))
- 2目的ナップサック問題のマックスミン最適化(多目的最適化)
- 一般化ナップサック共有問題の厳密解法
- 排他制約付きナップサック問題の近似解法と厳密解法(組合せ)
- 負コスト枝を含む有向グラフにおける最短単純路問題(グラフ・ネットワーク(3))
- 1-E-8 勝ち抜きトーナメント表の作成(スポーツスケジューリング)
- 最小拘束問題の分枝限定法アルゴリズム
- 最小κ-部分木問題のNP困難性・貪欲的下界値算法・近似解法(グラフ・ネットワーク(2))
- ミニマックス全域森問題のいくつかの拡張(グラフ・ネットワーク(2))
- ミニマックス完全森問題の厳密解法(グラフ・ネットワーク(2))
- 最小k-部分木問題におけるいくつかの妥当不等式とその効果(グラフ・ネットワーク(2))
- ミニマックス完全森問題に対する近似解法(グラフ・ネットワーク(4))
- 最大利得部分木問題に対する近似解法および厳密解法(マルチメディアネットワークシステム)
- 安定結婚の全列挙アルゴリズム(組合せ最適化(2))
- ナップサック共有問題の近似・厳密解法(組合わせ最適化(1))
- スコア・オリエンテ-リング問題に対するいくつかの近似解法とタブ-・サ-チ--中溝高好教授に捧ぐ
- Max-Minナップサック問題の近似解法(組合せ最適化(4))
- 最小通過流問題の諸性質と最適路の明示法(グラフ・ネットワーク(4))
- 多目的線型計画問題における有効端点の全列挙法(意思決定)
- 最小通過流問題の諸性質と最小費用流問題との関係(グラフ・ネットワーク(2))
- 有向グラフにおけるある資源配分問題について(組合せ最適化)
- ジョブショップ・システムにおける費用最小化問題について(グラフ・ネットワーク(2))
- Identifiability of a Simultaneous Equations Model of Economy : A Structural View
- 環状コンピュータ・ネットワークの一最適構成法(グラフ)
- 再帰型端点列挙法 : 理論(数理計画)
- 固定費付き複数ナップサック問題 : 分枝費用法によるアプローチ(組合せ最適化)
- 固定費付き複数ナップサック問題の上界値(整数計画)
- ラグランジュ緩和を用いた最小根付きκ-部分木問題の最適解法(数理計画(3))
- 最小根付きk-部分木問題に対するラグランジュ緩和を用いた貪欲的下界値算法の改善(グラフネットワーク(1))
- 1-D-1 最小経路費用木問題の分枝限定法(離散・組合せ最適化(1))
- 2-D-20 最小経路費用木問題の下界値(離散最適化)
- 2-F-9 Pruferリストに基づく木構造列挙の汎用的アルゴリズム(4) : 最小経路費用木問題への適用(グラフ(1))
- 1-D-10 Pruferリストに基づく木構造列挙の汎用的アルゴリズム(3) : 次数制限付き最小木問題への適用:実験編(離散アルゴリズム(3))
- 2-E-4 Pruferリストに基づく木構造列挙のアルゴリズム(2) : 次数制限付き最小木問題への適用(組合せ最適化と応用(3))
- 2-C-1 Pruferリストに基づく木構造列挙の汎用的アルゴリズム(グラフ・ネットワーク)
- 2-C-5 次数制限付き輸送問題のリスト表現を用いた分枝限定法(グラフ・ネットワーク(1))
- 2-A-2 次数制限付き輸送問題(離散最適化(3))
- 平成16年春季研究発表会ルポ(情報の窓)
- 第51回シンポジウムルポ(情報の窓)
- 0-1複数ナップサック問題に対する列生成法を用いた上界値(組合せ最適化ほか)
- 進行方向片側のみサービス可能な巡回路問題(2) : 基本タイセット行列を用いた表現(グラフ・スケジューリング)
- 進行方向片側のみサービス可能な巡回路問題(グラフ・ネットワーク(2))
- 最小拘束問題の分枝限定法 : これまでの課題の解決策(組合せ最適化(3))
- 最小拘束問題の下界値改善と分枝限定法(組合せ)
- 最小拘束問題の下界値算法(組合せ最適化)
- 最小拘束問題の動的計画法アルゴリズム(組み合わせ最適化(1))
- 最小滞在時間問題(2) : 分枝限定法の適用と3教員緩和(組合せ最適化(2))
- 最小滞在時間問題(1) : 定式化および制約の改善(組合せ最適化(2))
- 最小k部分木問題に対する分枝限定法の適用(グラフ・ネットワーク(1))
- 部分巡回路型の問題に対する有向部分1-木緩和と下界値上昇法(組合せ最適化(4))
- 1つの連結成分を持つ最小有向部分木問題II(グラフ理論)
- 非対称TSPにおける最小有向1-木を用いた下界値上昇法(組合せ)
- 一つの連結成分を持つ最小重み有向部分木問題(数理計画)
- 単一制約付最大集荷問題のアルゴリズム
- 2-I-9 動的計画法による多次元ナップサック問題の近似解法と変数縮小(離散最適化(4))
- 2-A-10 動的計画法による多次元ナップサック問題の近似解法(離散最適化(3))
- 動的計画法を用いた多次元ナップサック問題の変数縮小法 (不確実・不確定環境下における数理的意思決定とその周辺)
- 2-C-8 動的ネットワークフロー問題の分離構造(連続最適化(1))
- 1-B-10 ボトルネック型複数ナップサック割当問題の上下界値の評価(離散最適化(3))
- 1-B-9 複数ナップサック-割当問題の2重分枝価格法(離散最適化(3))
- 2-F-9 列生成法および分枝価格法の退化実態とその対策(最適化(1))