整数解を導出するための単体法とゴモリーカットの合成について

摘要

与えられた有理数上の線形制約を充足する割り当てを求める手法として単体法がある．また，有理数解を求める手法と，ゴモリーカットをはじめとする切除平面法を組み合わせることで整数解を求められることが知られている．しかし，単体法を適用した後，必ずしもゴモリーカットが適用可能であるとは限らない．本稿では，ゴモリーカットの合成に必要な単体法における不変条件を示し，単体法とゴモリーカットを合成した手続きを示す．また，ゴモリーカットで追加する制約について，より単純な実装を行うための制約の形式を述べる．これらに基づいて，上記2つの手法を合成したソルバを実装し，評価する．