RSS

  

RSS

プログラム


SCIPで三択

  • いわいまさか
  • at 2019/7/15 07:11:37

制約ソルバー
整数計画ソルバー
SCIPで
「３択で一番小さい数字を選択」する問題を解く。
こんなことも意外と手がかかる。必死かよ状態。

LPを書くと
Maximize
 value: dummy
Subject To
 c1 + c2 + c3 = 1
 c1 = 1 -> v - v1 = 0
 c2 = 1 -> v - v2 = 0
 c3 = 1 -> v - v3 = 0
 v1 - v >= 0
 v2 - v >= 0
 v3 - v >= 0
Bounds
 dummy = 0
 v1 = 17
 v2 = 3
 v3 = 13
Binary
 c1
 c2
 c3
End

説明
c1 c2 c3 がどの選択を採用するかのbinary値
v1 v2 v3 がその選択をとったきの持ち点
v が最終的な持ち点

v1 v2 v3 が最初から決まっているのなら、LPで式をたてずともすぐに答えが出てしまうけど、v1 v2 v3が他の条件から導きだされる値であることを想定しているのでこんな感じ。

上記のLPをSCIPにかけると
c2 = 1
v = v2 = 3
と答えが出る。


ここで、c1 c2 c3 部分を端折って
 v1 - v >= 0
 v2 - v >= 0
 v3 - v >= 0
だけにすると、vが3でなく、0とか1とかでも答えになってしまう。それは、３択じゃない。


  • コメント (0)
  • トラックバック (0)
トラックバックURL :
http://www.iwai-masaka.jp/tb.cgi/56471

コメントを書く