IF-008
Exact Clustering via Integer Programming and Maximum Satisfiability

◎宮内敦史（理研）・薗部知大（NII）・鮏川矩義（東理大）

クラスタリングは，機械学習やデータマイニングで幅広く利用されているデータ解析手法である．クラスタリングをモデル化した最適化問題の一つとして，クリーク分割問題が知られている．この問題では，枝重み（正負あり）付き無向グラフが与えられ，頂点集合を任意の個数のクラスターに分けて，クラスター内の枝重みの総和を最大化する．クリーク分割問題に対しては，Groetschel & Wakabayashi (1989) による整数線形計画問題としての定式化が知られているが，制約式の本数が非常に多く，数百頂点のグラフにしか適用することができない．本研究では，実インスタンスの性質に着目し，制約式の本数を大幅に減らした定式化を提案する．提案定式化は，数千頂点のグラフに対しても適用可能である．