線形計画ソルバー
google code jamの過去問を解いていたら線形計画のソルバーが欲しくなったのでlp_solverを入れてみた.
入れ方は
sudo apt-get install lp-solver
ハイフンに注意
lp_solverを使えば,例えば
のような線形計画問題を解きたいときは
max: 20 x + 30 y;
x + 2 y <= 800;
3 x + 4 y <= 1800;
3 x + y <= 1500;
をhoge.lpに保存して
lp_solve test.lp
とすれば
Value of objective function: 13000
Actual values of the variables:
x 200
y 300
のように解いてくれる.
javaから使う
スクリプトで処理をするよりjavaで書いた方が速い(java以外で何も見ずにかけるような言語がない)ので,apiを入れてみた.
以下,入れるのがかなり大変だったのでその備忘録.OSはUbuntu9.04
まずは,http://sourceforge.net/projects/lpsolve/files/lpsolveに行き最新の
- lp_solve_5.5.0.15_java.zip
- lp_solve_5.5.0.15_source.tar.gz
の二つを落として来て,展開する.
次に,
- lp_solve_5.5/lpsolve55/bin/ux32/liblpsolve55.so
- lp_solve_5.5_java/lib/linux/liblpsolve55j.so
- lp_solve_5.5_java/lib/lpsolve55j.jar
の3つを/usr/local/libにコピーし,chmod 755.
さらに,パスを通すため.zshrcなどに
export CLASSPATH=/usr/local/lib/lpsolve55j.jar:$CLASSPATH
export LD_LIBRARY_PATH=/usr/local/lib:$LD_LIBRARY_PATH
と記述.
c++用のパッケージが足りてない場合があるので,その時は
sudo apt-get install libstdc++5
でOK
あとは,上の問題を解きたいときは
import lpsolve.*; public class LP { public static void main(String[] args) { try { LpSolve solver = LpSolve.makeLp(3, 2);//constraints, variables solver.setOutputfile("debug"); solver.strAddConstraint("1 2", LpSolve.LE, 800); solver.strAddConstraint("3 4", LpSolve.LE, 1800); solver.strAddConstraint("3 1", LpSolve.LE, 1500); solver.setMaxim(); solver.strSetObjFn("20 30"); solver.solve(); System.out.println("Value of objective function: " + solver.getObjective()); solver.deleteLp(); } catch (LpSolveException e) { e.printStackTrace(); } } }
のようなファイルを作って
とすれば
Value of objective function: 13000.0
と出力される.
gcjのルールを見ると
Solving problems using standard and non-standard libraries
You may use standard libraries, such as Boost, and other open source libraries. If you use a publicly available library, you may submit a link to the library's website rather than including the contents of the library in your source code submission.
とあるので,
import lpsolve.*;// http://sourceforge.net/projects/lpsolve/files/lpsolve
と書けば使っても良いはず.