文献

J-GLOBAL ID：201902218516646984   整理番号：19A2035552

二次最小スパンニング木問題のための半正定値プログラミング下界と分枝限定アルゴリズム【JST・京大機械翻訳】

Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem

著者 (3件)： Guimaraes Dilson Almeida (Universidade Federal de Minas Gerais, Departamento de Ciencia da Computacao, Belo Horizonte, Brazil) ,  da Cunha Alexandre Salles (Universidade Federal de Minas Gerais, Departamento de Ciencia da Computacao, Belo Horizonte, Brazil) ,  Pereira Dilson Lucas (Universidade Federal de Lavras, Departamento de Ciencia da Computacao, Lavras, Brazil)
資料名： European Journal of Operational Research  (European Journal of Operational Research)
巻： 280  号： 1  ページ： 46-58  発行年： 2020年 
JST資料番号： A0547A  ISSN： 0377-2217  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 本論文では,二次最小スパンニング木問題(QMSTP)に対する半有限プログラミング(SDP)下限を検討した。ここでは,二つのSDP低境界法を紹介した。両方とも,問題に対するSDP緩和へのLagrange緩和を適用した。最初のものは,半正定性制約を明示的に二重化し,それに対してLagrange乗算器の正の半正定行列に結合した。第二は,正の半正定行列の円錐に対する半無限再定式化に依存し,円錐を近似する不等式の動的に更新された有限集合を双対化する。これらのより低い境界手順は,2つのQMSTP分枝限定アルゴリズムのコア要素である。計算実験により,ここで計算したSDP限界は非常に強く,文献における最も競争力のある定式化のギャップの少なくとも70%に近いことを示した。結果として,それらの付随する分枝限定アルゴリズムは,文献における最良の以前に利用可能なQMSTPの正確なアルゴリズムと競合する。事実,これらの新しい分枝限定アルゴリズムの一つは,問題に対する新しい最良の厳密解アプローチとして存在する。Copyright 2019 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 厳密解 ,  *分枝限定法 ,  *スパンニング木 ,  *アルゴリズム ,  不等式 ,  緩和現象 ,  定式化 ,  定性分析 ,  円錐 ,  乗算器
準シソーラス用語： Lagrange緩和法 ,  *下界 ,  *半正定値計画法 ,  *最小全域木 , 【Automatic Indexing@JST】

著者キーワード (5件)： 組合せ最適化 ,  スパンニング木 ,  ラグランジュ緩和 ,  半正定値計画法 ,  半無限計画法

分類 (2件)： その他のオペレーションズリサーチの手法  (KA03070E) ,  システム最適化手法  (IA02050Z)

タイトルに関連する用語 (5件)： 最小スパンニング木 ,  問題 ,  半正定値プログラミング ,  下界 ,  分枝限定アルゴリズム