整数計画法 のバックアップ(No.2)

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• 整数計画法 へ行く。
  • 1 (2016-08-19 (金) 08:11:17)
  • 2 (2016-08-19 (金) 08:36:55)
  • 3 (2016-08-19 (金) 12:26:26)

TODO

概要 †

• NP困難な整数計画法をゴリ押して解く

ライブラリ †

• 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

使い方 †

• サンプル
  • https://en.wikibooks.org/wiki/GLPK/Using_the_GLPK_callable_library
  • https://gist.github.com/msakai/2450935

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