ナップサックとlp_solve 5.5.0.15 とビンパッキング
この 記事 を読んで、ナップサックってそんな感じなんだぁって思った。で、全然関係ないけど、MacPorts で lp_solve をアップグレードしようとしたら失敗した。
sudo port selfupgrade sudo port upgrade lp_solve
ここで、エラーが出た。ビルドはできてるっぽいので、コメント診て対応。未だに Leopard 使ってんなよ的な弊害なのか。
sudo cd /opt/local/var/macports/build/_opt_local_var_macports_sources_rsync.macports.org_release_ports_math_lp_solve/work/lp_solve_5.5/lpsolve55/bin; ln -s /opt/local/var/macports/build/_opt_local_var_macports_sources_rsync.macports.org_release_ports_math_lp_solve/work/lp_solve_5.5/lpsolve55/bin osx32
それで、もう一度 port upgrade したらインストールできた。ははん。
で、むかしのコードで確認。lp_solve のいくつかのシンタックスが変わっていたりしたところを修正した。ビンパッキングの超制限されたインスタンスに対するアルゴリズム。大学の頃にお手伝いで lp_solve を使ったコードを書いてあげたときの。たしか、Approximation Algorithms for Np-Hard Problems か 計算とアルゴリズム (新コンピュータサイエンス講座) 記載のアルゴリズムだったと思う。
下に載っけたコードを実行したら、つぎのような結果が出力される。ビンの大きさは1。荷物のサイズはどれも分子が1で分母が正整数の分数。サイズが1/5 の荷物が14個。1/4が7個で1/3が3個。で、全部突っ込むには6個ビンがいりますよっつって。んでパタンが下の６個のベクトル。1行目の500 は、ビン1には1/5が五個だけ。計算とアルゴリズム (新コンピュータサイエンス講座) に書いてあるPTASで、各荷物のサイズを丸めてこの形にして近似的に問題を解くときに使われる。近似率を良くするように働きかけると、分母の種類が増える。
instance: (1 / 5) x 14 (1 / 4) x 7 (1 / 3) x 3 Value of objective function: 6.00000000 5 0 0 4 0 0 3 0 1 2 1 1 0 4 0 0 2 1
なんか、整数計画でやってる。PTASではもちろんLPで置き換えられてる。だので、main関数の一個目のforループは全消し。IP に対して lp_solve を利用する C のコードの例としては、まぁ、分かりやすい例題だと思う。不自然だけど。
#include <lpsolve/lpkit.h> #include <iostream> #define ERROR() { std::cerr << "Error" << std::endl; exit(1); } typedef struct { double num; long numerator; long denominator; } package; /*** globals ***/ int n; // the number of packages. int m; // the number of types of packages int k; // the denominator of a lower bound of weight with 1/k. int N; // the number of patterns. double pattern[1000][1000]; // to be used for storing the pattern vectors. double obj_coeff[1000]; package packs[3]; void init() { n = 24; m = 3; k = 5; packs[0].num = 14; packs[0].numerator = 1; packs[0].denominator = 5; packs[1].num = 7; packs[1].numerator = 1; packs[1].denominator = 4; packs[2].num = 3; packs[2].numerator = 1; packs[2].denominator = 3; for (int i = 0; i < 1000; i++) obj_coeff[i] = 1; }; double get_r(package x) { return (double) x.numerator / x.denominator; } void gen_patt() { N = 1; for (long i = packs[0].denominator; i >= 0; i--) { for (long j = packs[1].denominator; j >= 0; j--) { for (long l=packs[2].denominator; l >= 0; l--) { if (get_r(packs[0]) * i + get_r(packs[1]) * j + get_r(packs[2]) * l <= 1) { pattern[0][N] = i; pattern[1][N] = j; pattern[2][N] = l; N++; } } } } N--; // minus the case (0, 0, ..., 0). std::cout << "instance:" << std::endl; for (int i = 0; i < m; i++) { std::cout << "(" << packs[i].numerator << " / " << packs[i].denominator << ") x " << packs[i].num << std::endl; } } int main() { init(); gen_patt(); lprec *lp = make_lp(0, N); set_verbose(lp, SEVERE); for (int i = 1; i <= N; i++) { set_binary(lp, i, TRUE); } for (int i = 0; i < m; i++) { if (!add_constraint(lp, pattern[i], GE, packs[i].num)) ERROR(); } if (!(set_obj_fn(lp, obj_coeff))) ERROR(); if (solve(lp)) ERROR(); print_objective(lp); get_variables(lp, obj_coeff); for (int i = 0; i < N; i++) { if (obj_coeff[i] > 0) { for (int j = 0; j < 3; j++) { std::cout << pattern[j][i + 1] << " "; } std::cout << std::endl; } } delete_lp(lp); return 0; }
#! /bin/sh suffix=`date "+-%y%m%d"` out=macports${suffix} sudo port selfupdate > $out port outdated >> $out sudo port upgrade outdated >> $out exit 0
- おまけ: lp_solve と環境変数
setenv DYLD_FALLBACK_LIBRARY_PATH /opt/local/lib
CGAL とかもそうだけど、この変数を設定しておかないと実行時に dylib がきちんとリンクできない。
*1:とりとめも無い文章はいつものことですが、まったくまとまっていない文章で、だらだらしてしまってます。また、なんか敬語使っていませんが、お気を悪くさせてしまったら申し訳ありません。例に漏れず、いつも通り、今日も書き手の自己満足な記事です。ごめん下さい
