整数計画法

TODO

概要 †

• NP困難な整数計画法をゴリ押して解く
• 手動で1つのファイルにしようとするのは諦めること！！！
  • 5万行で、しかも同じ名前のクラスをうまく使いまわしていたりして、非常に面倒。4時間かけてできなかったので。
  • リンクするときにプリプロセッサ展開後のファイルを取ってくる方法を使えばいけるかも

ライブラリ †

• GLPK (GNU Linear Programming Kit)
  • ちゃんと全部ソースが公開されている
  • 性能はちょっと低め
• Gurobi
  • ソースが半分くらいしか公開されてない
  • gurobi65.soはライセンスがないと使えない。

GLPK †

インストール †

./configure
make -j8
sudo make install
sudo vi /etc/ld.so.conf.d/glpk.conf  # /usr/local/libを追加
sudo ldconfig

cd examples/tsp
./build.sh
./tspsol sample.tsp

# 普通の線形計画法
cd ../
gcc -o sample sample.c -lglpk -lm

使い方 †

• サンプル
  • MIPの方法、日本語コメント付き

• GLP_DBのようなマクロ
  • DB: Double Bounded, 両側拘束
  • FX: Fixed equation, 等式
  • LO: Lower, 下から抑える
  • UP: Upper, 上から抑える

一応作業記録 †

• /git/sample/glpk-4.60/src$ gcc -o sample glpk-mip-sample-long.c -lm

  • 頑張ってコピペしようね