サブロウ丸

主にプログラミングと数学

線形計画問題における、とある条件を持つバイナリ変数の表現方法について

最近、線形計画問題に取り組んでいまして、以下のようなバイナリ変数xを定義する必要が出てきました。
f:id:inarizuuuushi:20170803171451p:plain:w900

バイナリ変数とは0と1の2値のみをとり得る変数のことです。

これがなかなか難しくて、いろいろ調べてみて、
2通りの定式化を行いました。

1つ目は以下のリンクにあるpdfを参考にして、
2つ目は一部を参考にして自分で考えてみました。
http://web.tuat.ac.jp/~miya/fujie_ORSJ.pdf


まず1つ目の表現方法ですが、区分線形関数を用いる定式化です。
xとyがとり得るペアを線形関数により緩和し、それを利用して線形制約化してやります。
f:id:inarizuuuushi:20170803171145p:plain:w700
f:id:inarizuuuushi:20170803172533p:plain:w700
SOS2変数群の表現については、なるほどなぁと感心しますね。
ただ、tとzを合わせて9個の補助変数(しかもtに関しては実変数)を導入しているので、
補助変数をもっと減らせないかと、もう一つの定式化を考えてみました。

2つ目の定式化では、利用する制約選択(or)と凸包による緩和での線形制約化を行なっています。
f:id:inarizuuuushi:20170803171451p:plain:w700
f:id:inarizuuuushi:20170803172412p:plain:w700
Big-Mと呼ばれる十分大きな定数であるMを制約式の右辺に追加することで、バイナリ変数yによって、制約として意味のあるものと意味のないものを切り替える(スイッチする)ということをしています。
f:id:inarizuuuushi:20170803171223p:plain:w700

f:id:inarizuuuushi:20170803171227p:plain:w700
この定式化では補助変数としてバイナリ変数zしか用いていません。
この場合は、バイナリ変数zによってxについての制約をスイッチさせています。
すなわち、「y ≥ α + 1 ⇒ z = 0 ⇒ x ≤ 0 の制約のみ有効化」ということを行なっているのです。
制約式についても単純な制約式でかけていますね。

ただ1つ目の表現と2つ目の表現のどちらが計算機的に良いかは、今後余裕があれば実験を行い、補足したいと思います。

↓その記事です。(2017/08/25)

inarizuuuushi.hatenablog.com