数理計画問題による最大辺重みクリーク問題の定式化

清水 悟司  山口 一章  増田 澄男  

誌名
電子情報通信学会論文誌 A   Vol.J100-A   No.8   pp.313-315
発行日: 2017/08/01
Online ISSN: 1881-0195
論文種別: レター
専門分野: 
キーワード: 
最大辺重みクリーク問題,  NP困難,  数理計画問題,  定式化,  

本文: PDF(162.2KB)
>>論文を購入


あらまし: 
最大辺重みクリーク問題に対する数理計画問題による定式化を幾つか示し,数理計画ソルバで解く際の計算時間を比較する.混合整数計画問題で定式化する際,頂点番号の付け替えにより時間を短縮する方法を提案する.実験により提案法が他の定式化より計算時間が短く済むことを確認した.