SMIPS

The Smallest MIP Solver by C++

概要

　超ざっくり書いたMIPソルバーです。 　シンプレックス法と分枝限定法しか使ってません。

使い方

　まず、問題ファイルを次のような書式のテキストファイルで用意します。

2 3
5 4
1.5 3 < 13.5
3 1 < 10
1 2 > 7
1 1

　数字及び記号は半角スペースで区切ること。
　ここで目的関数は「最大化」のみ、制約式における「＝」は「=」と書くこと。
　また、各変数(ここではx1,x2)はどちらも負でないものとします。
　各行の意味は次の通りです。

行のテキスト	意味
2 3	2変数・3制約式
5 4	目的関数：5x1 + 4x2
1.5 3 < 13.5	制約式：1.5x1 + 3x2 ≦ 13.5
3 1 < 10	制約式：3x1 + 1x2 ≦ 10
1 2 > 7	制約式：1x1 + 2x2 ≧ 7
1 1	x1もx2も、整数制約があることを示す(実数でもいいなら0)

　そうして書いたファイルを仮にquery.txtとすると、そのまま「SMIPS.exe query.txt」で計算できます。

maximize
  + 5 x1 + 4 x2
subject to
  + 1.5 x1 + 3 x2 <= 13.5
  + 3 x1 + 1 x2 <= 10
  + 1 x1 + 2 x2 >= 7
general
  x1 x2
緩和問題(1)の解：
z: 24.6
  x1: 2.2 x2: 3.4
緩和問題(2)の解：
z: 24
  x1: 2 x2: 3.5
緩和問題(3)の解：
z: 22
  x1: 2 x2: 3
緩和問題(3)の解：
z: 21
  x1: 1 x2: 4
緩和問題(3)の解：
z: -1.79769e+308

z: 22
  x1: 2 x2: 3

　なお、最後に出て来る結果(ここでは「x1: 2 x2: 3」)において、変数の値が0なら、その変数名は表示されません。

注意

• 線形計画問題(問題ファイルの最終行が「0 0 ... 0」と0しかないもの)はともかく、整数計画問題等は計算が遅いです
• シンプルに作っただけあって計算が遅いのは仕方がありません。計算だけなら普通のソルバーを使いましょう
• sampleフォルダの「sample.gps」は、GRAPES用のグラフデータです

参考サイト

• 『システムの最適化 １．線形計画法（ LP : Linear Programming ）』
• 『３．シンプレックス表（シンプレックスタブロー）を利用して解く 』
• 『Simplex method theory - PHPSimplex』

　ここで上2つは、大学のWebページに載っている内容にも関わらず、解法に一部誤りがあります。
　具体的には、『2x+3y≦12、y≧4、x,y≧0の際に4x+5yが最大となるx,yを求めよ』と出題した際、
なぜか(x,y)＝(0,4)ではなく(6,0)を出力してしまいます。制約式を無視するんじゃねえよ！
　恐らく、2段階法の1段階目では実行可能解を出力できているものの、2段階目でミスるようです。
　これだと使い物になりませんので、マトモな情報を探すのに苦労しました。