線形計画ソルバー

programming Java

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();
        }
    }

}

のようなファイルを作って

javac LP.java
java LP

とすれば

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

と書けば使っても良いはず．