分数切除平面法(ゴモリーカット)の頂点彩色問題への適用明治大学理工学部情報科学科 計算理論研究室 中田 寛基 概要 巡回セールスマン問題(TSP)などの難しい問題を解く手法の一つに、数理計画法というものがある。その手法を、定式化した彩色問題に応用できないかを考える。 研究背景、目的 CPLEX(Iloｇ社)などの数理計画問題ソルバーが強力になってきている。 巡回セールスマン問題(TSP)などにおいて、数理計画法(と分枝限定などの組み合わせ)が良い成績を残している。 その数理計画法を学び他の問題に応用できないかを考える。 彩色問題が整数計画法に定式化できるので、より高速に解を求めたい。 彩色問題以外にも、整数計画法に定式化できる問題に対するアプローチの開発にもつながるはずである。 内容 数理計画法について 分数切除平面法(ゴモリーカット)について 頂点彩色問題の定式化 実験結果 参考資料 「オペレーションズ・リサーチ」 森雅夫、松井知己 経営シ
