最適化問題、とりわけ線形計画問題が気になり始めるお年頃になってきたので、 SCIP というソルバーを使ってみましたよ、というメモ。
インストール
まずは手元にある MBP に、 SCIPをMacにインストール - Qiita の手順を参考にインストールを試してみる。ところが、
src/rational.h:32:10: fatal error: 'gmp.h' file not found
などの gmp.h がない旨のコンパイルエラーが発生してしまう状況に遭遇してインストールできない。
なので、ひとまず make GMP=false としてお茶を濁すことしてみる (GMP を要求するのは ZIMPL らしく、かつその機能を利用することは今のところはないので)。
インタラクティブシェル
ビルド後の scip のバイナリ scip-X.X.X/bin/scip を立ち上げるとインタラクティブシェルが立ち上がる。
read: 問題を記述したファイルを読み込む
ひとまず適当な問題をソルバーで解かせてみようと思い、講義テキストらしきもの (PDF) を参考に、最適化問題を記述した LP ファイル (sample.lp) を作ってみる。
maximize
400 x1 + 300 x2
subject to
60 x1 + 40 x2 <= 3800
20 x1 + 30 x2 <= 2100
20 x1 + 10 x2 <= 1200
end
このファイルを scip のインタラクティブシェル上で読み込んでみる。読み込みには read コマンドを利用する。
SCIP> read /path/to/sample.lp
read problem </path/to/sample.lp>
============
original problem has 2 variables (0 bin, 0 int, 0 impl, 2 cont) and 3 constraints
2 つの変数、3 つの制約条件、と出力がでて、ちゃんと読み込めたようだ。
optimize: 最適化問題を解く
読み込んだ問題を実際に解いてみよう。問題を解くには optimize コマンドを利用する。
SCIP> optimize
feasible solution found by trivial heuristic after 0.0 seconds, objective value 0.000000e+00
presolving:
(round 1, fast) 0 del vars, 0 del conss, 0 add conss, 4 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
presolving (2 rounds: 2 fast, 1 medium, 1 exhaustive):
0 deleted vars, 0 deleted constraints, 0 added constraints, 4 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
0 implications, 0 cliques
presolved problem has 2 variables (0 bin, 0 int, 0 impl, 2 cont) and 3 constraints
3 constraints of type <linear>
Presolving Time: 0.00
transformed 1/1 original solutions to the transformed problem space
time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
* 0.0s| 1 | 0 | 3 | - | 194k| 0 | - | 2 | 3 | 2 | 3 | 0 | 0 | 0 | 2.700000e+04 | 2.700000e+04 | 0.00%
0.0s| 1 | 0 | 3 | - | 194k| 0 | - | 2 | 3 | 2 | 3 | 0 | 0 | 0 | 2.700000e+04 | 2.700000e+04 | 0.00%
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 0.00
Solving Nodes : 1
Primal Bound : +2.70000000000000e+04 (2 solutions)
Dual Bound : +2.70000000000000e+04
Gap : 0.00 %
表示内容が豊富でちょっと面食らってしまうけど、 problem is solved [optimal solution found] がポイント。最適解が求まったぽい。
display: 解を表示する
optimize コマンドで解が求まったら、 display のコマンドでその解を表示してみよう。
SCIP> display solution
objective value: 27000
x1 30 (obj:400)
x2 50 (obj:300)
ちゃんと最適解が求まっているのがわかる。
write: 解をファイルに書き出す
optimize コマンドで求まった解を他の用途で使いたい、ということは結構よくあるはず。ファイルに書き出すことができればスクリプト言語でパースして利用する事もできるだろう。
それでは write コマンドでファイルに書き出してみよう。
SCIP> write solution result.sol
written solution information to file <result.sol>
出力された result.sol を less などで覗いてみれば、display solution でコンソールに表示した内容と同等のものが出力されているのがわかるはず。
問題の記述方法
SCIP のひととおりの使い方がだいたい分かってきたところで、他の問題も SCIP で解けるように、問題の記述方法を勉強してみよう。
ナップサック問題
まずは最適解問題で定番のナップサック問題。具体的な問題は Wikipedia のページ ナップサック問題 の図より拝借。
maximize
4 d4w12 + 2 d2w2 + 2 d2w1 + 1 d1w1 + 10 d10w4
subject to
weight: 12 d4w12 + 2 d2w2 + 1 d2w1 + 1 d1w1 + 4 d10w4 <= 15
binary
d4w12 d2w2 d2w1 d1w1 d10w4
ナップサック問題に入れる・入れないをフラグ的に binary で表現し、目的関数に価値の合計を、制約条件に重さの合計に対する上限値を設定すれば OK だろう。
N クイーン問題
ソルバーで解いて嬉しいかどうか別として、 N クイーン問題 をソルバーで解かせてみよう。
問題の記述が大変だったので、盤面の大きさは 4x4 にしてみる。
maximize
a1 + a2 + a3 + a4 + b1 + b2 + b3 + b4 + c1 + c2 + c3 + c4 + d1 + d2 + d3 + d4
subject to
rowA: a1 + a2 + a3 + a4 = 1
rowB: b1 + b2 + b3 + b4 = 1
rowC: c1 + c2 + c3 + c4 = 1
rowD: d1 + d2 + d3 + d4 = 1
col1: a1 + b1 + c1 + d1 = 1
col2: a2 + b2 + c2 + d2 = 1
col3: a3 + b3 + c3 + d3 = 1
col4: a4 + b4 + c4 + d4 = 1
diagC1D2: c1 + d2 <= 1
diagB1D3: b1 + c2 + d3 <= 1
diagA1D4: a1 + b2 + c3 + d4 <= 1
diagA2C4: a2 + b3 + c4 <= 1
diagA3B4: a3 + b4 <= 1
diagC4D3: c4 + d3 <= 1
diagB4D2: b4 + c3 + d2 <= 1
diagA4D1: a4 + b3 + c2 + d1 <= 1
diagA3C1: a3 + b2 + c1 <= 1
diagA2B1: a2 + c1 <= 1
binary
a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 d1 d2 d3 d4
すごく冗長な表現になってしまっているように思えるが、ちゃんと解くことができる。いいね！
参考文献
0 コメント:
コメントを投稿