On the existence of optimal solutions to integer and mixed-integer programming problems

link.springer.com

線形計画問題は

1. Unbounded
2. Infeasible
3. has an optimal solution

の3通りしかないけど整数計画問題はそうとは限らなく、

いくらでもいい結果が存在する

というパターンがある。

たとえば、

maximize

subject to , is positive integer

など。

この論文では、最適解が存在する十分条件を提示している。それは整数計画問題の場合、変数の非負性や整数性を除いた条件が、等式であることで、混合整数計画の場合、制約の係数が有理数であること、である。

ところで、整数計画の実行可能解の存在判定はNP-Completeである。証明はいくつかあり、一つはSATを整数計画として表せることによる方法で、もう一つは、制約を二分探索すれば整数計画の最適解が求まってしまうことによる方法である。