混合多項式最適化問題のコンパクトなMIP表現

Abstract

混合多項式最適化問題(MIPOP)は多くの応用をもつ広いクラスの問題であるが，一般にはNP困難となる非常に難しい問題である．MIPOPを解くアプローチの一つに，MIPOPを混合整数計画問題(MIP)に等価あるいは近似的に変換して解く手法がある．しかしながら，そのような手法の多くでは，MIPOPのクラスが限定されていたり，近似精度をあげるために数多くの変数を導入する必要があったりしていた．つい最近，Zhuらはx, y ∈ [0, 1]の積z = xyを少ない変数の導入でMIPに表現する方法を提案した．この手法を用いれば，決定変数が[0, 1]区間に入る非凸な2次最適化問題はMIPに定式化して解くことができる．しかしながら，2次の項の数に比例して導入する決定変数が増えるため，大規模な問題や次数が高い問題には適用できなかった．本論文では，まず，Zhuらの手法を拡張することによって，有理関数をMIPとして表現する手法を提案する．さらに，2次形式，3次形式に対して少ない決定変数の導入でMIPに表現する方法を提案する．また，決定変数が整数などの離散変数のみの場合には，等価なMIPに変換できることをみる．