整数制約付き線形計画問題は、線形計画問題に定式化できる

いわゆる Mixed Integer Programming Problem、より正確には整数制約付きの線形計画問題は、線形計画問題に定式化できる。
したがって、指数オーダーで増加するの計算時間と計算メモリに耐えられれば、理論上はシンプレックス法で解くことができる。

定式化するには、
(1) copositive programming により定式化する
(2) copositive programming を sum of squares により定式化する
(3) sum of squares を非常に巨大な LP により定式化する
とすればよい。