Item type |
Journal(1) |
公開日 |
2016-10-15 |
タイトル |
|
|
タイトル |
連続型・時間/費用トレードオフ最小全域木問題 |
タイトル |
|
|
言語 |
en |
|
タイトル |
Continuous Time/Cost Tradeoff Minimum Spanning Tree Problem |
言語 |
|
|
言語 |
jpn |
キーワード |
|
|
主題Scheme |
Other |
|
主題 |
[一般論文] 時間/費用トレードオフ関係,最小木問題,ラグランジュ緩和,釘付けテスト,分枝限定法 |
資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
著者所属 |
|
|
|
防衛大学校情報工学科 |
著者所属 |
|
|
|
陸上自衛隊 |
著者所属(英) |
|
|
|
en |
|
|
Department of Computer Science, National Defense Academy |
著者所属(英) |
|
|
|
en |
|
|
Japan Grand Self Defense Force |
著者名 |
片岡, 靖詞
村崎, 暢彦
|
著者名(英) |
Seiji, Kataoka
Masahiko, Murasaki
|
論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
最小全域木問題は,グラフの各枝に時間などのデータが与えられているとき,総時間を最小化する全域木を求める問題である.本研究では,各枝に与えられた時間が,資金を投入することにより短縮できる場合を考え,限られた資金の中で総時間を最小にする全域木を求める問題を扱う.各枝における時間の短縮は,資金の投入額に応じて連続的かつ線形的に時間短縮ができる場合を想定しているので,この問題を連続型時間/費用トレードオフ最小全域木問題と呼ぶことにする.このような問題設定は,プロジェクトスケジューリングでは,CPMとして古くから知られている扱いやすい問題設定であるが,最小木問題の場合は,線形的に時間短縮ができる場合でもNP困難である.また,解には特徴的な構造を持つことが知られているが,この性質について先行研究とは別の証明を示す.定式化の構造からラグランジュ緩和は2つの独立した扱いやすい問題に分割でき,効果的に上下界値が導出できる.また,この上下界値を利用して釘付けテストを行い,多くの場合において分枝限定法に入る前に最適解が得られることを示す.釘付けテストは枝数が多くなると,時間的負担も増えてくるものの,疎なグラフ,特に平面的グラフにおいては,先行研究よりも優れた結果を得た. |
論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
Given an undirected graph and a parameter such as time on each edge, the minimum spanning tree problem is a problem of finding a spanning tree that minimizes total time. In this study, we consider the case that the time on each edge can be reduced by throwing resource such as extra fare into the edge, and find the minimum total time spanning tree within a total resource constraint. As for the reduction of time for each edge, we assume that it can be continuously and linearly reduced. Therefore, we call the problem the continuous time/cost tradeoff minimum spanning tree problem. This kind of continuous and linear tradeoff relationship is often seen in the subject of project scheduling problems, which has been studied before as CPM and is easily solvable. But in the case of the minimum spanning tree problem, even though the tradeoff relationship is continuous and linear, the problem is known to be NP-hard. Also we prove that the optimal solution has a characteristic structure. These proofs are different from those seen in the past research. Based on our formulation, we show that the Lagrangian relaxation problem is divided into two independent tractable problems. Hence, we succeed in obtaining upper and lower bounds efficiently. By applying these bounds into the pegging test, we show that in many cases optimal solutions are obtained before going forward to the branch-and-bound algorithm. As the number of edges becomes large, the computational burden increases, but our computational results are superior to the results in the past research, especially when the graph is sparse. |
書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN00116647 |
書誌情報 |
情報処理学会論文誌
巻 57,
号 10,
p. 2260-2271,
発行日 2016-10-15
|
ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
1882-7764 |