RGLPKの使い方 - ざっきちょう

線形計画法ライブラリのGLPKをrubyから使えるRglpkなる物があったが, ドキュメントが全然見当たらなかったので, 使い方をメモしておこうかと.
なんか間違ってたら教えてくれると嬉しいです.

インストール

ここのread meに書いてある通り.

いきなりgem install rglpkすると怒られるので, GLPKをDLして, makeして, includeとかにファイルぶち込んだりとかする.
windowsならmsysとかからやればよい.

それが終わったら, gem install rglpkする.

使い方

基本的に, read meに書いてあったように, 適当に変数と制約式を入れていけばよい.
MIPのがread meに無かったので, サンプルとして, 0-1整数計画法でn-queenを書いてみた.
参考:こことここ

require "rglpk"

SIZE = 8

#線形計画問題を作って, 名前を付ける.
lp = Rglpk::Problem.new
lp.name = "%d-queen" % SIZE


#SIZE**2 変数
cols = lp.add_cols(SIZE ** 2)
for i in 0...SIZE
  for j in 0...SIZE
    #変数に名前付ける. 省略可能.
    cols[i * SIZE + j].name = "(%d, %d)" % [i, j]

    #変数の上界と下界を設定する. 今回はバイナリ変数なので, 省略出来る.
    #set_bounds(*, lower, upper)
    #GLP_DB: lower <= x <= upper
    #GLP_FX: lower =  x =  upper
    #GLP_FR: -Inf  <  x <  Inf
    #GLP_LO: lower <= x <  Inf
    #GLP_UP: -Inf  <  x <= upper
    #cols[i * SIZE + j].set_bounds(Rglpk::GLP_DB, 0, 1)

    #変数の種類を設定する. 何もしないとGLP_CV.
    #GLP_CV: 実数
    #GLP_IV: 整数
    #GLP_BV: バイナリ
    #バイナリ以外の時は, set_boundsする事.
    cols[i * SIZE + j].kind = Rglpk::GLP_BV
  end
end

#制約式:
# 縦, 横でSIZE本ずつ.
# 斜めで 2 * (SIZE * 2 - 1) 本
# 後でset_matrixする為に, matも作っておく.
mat = []
rows = lp.add_rows(SIZE * 2 + 2 * (SIZE * 2 - 1))
cnt = 0
#横
for i in 0...SIZE
  #名前付ける(省略可)
  rows[cnt].name = "%dth row" % i

  #変数と同様に上界と下界を設定する.
  #(GLP_FX, 1, 1)でもいいけど, 3-queenでも2個置けるのが出たりするように.
  rows[cnt].set_bounds(Rglpk::GLP_DB, 0, 1)

  #mat作り.
  vec = [0] * (SIZE ** 2)
  for j in 0...SIZE
    vec[i * SIZE + j] = 1
  end
  mat << vec
  cnt += 1
end
#縦
for j in 0...SIZE
  rows[cnt].name = "%dth col" % j
  rows[cnt].set_bounds(Rglpk::GLP_DB, 0, 1)

  vec = [0] * (SIZE ** 2)
  for i in 0...SIZE
    vec[i * SIZE + j] = 1
  end
  mat << vec
  cnt += 1
end

#斜め1
for s in 0...(SIZE * 2 - 1)
  rows[cnt].name = "(i, j) s.t. i+j = %d" % s
  rows[cnt].set_bounds(Rglpk::GLP_DB, 0, 1)

  vec = [0] * (SIZE ** 2)
  for i in 0..s
    vec[i * SIZE + (s - i)] = 1 if (0...SIZE).include?(i) && (0...SIZE).include?(s - i)
  end
  mat << vec
  cnt += 1
end

#斜め2
for s in (-SIZE + 1)..(SIZE - 1)
  rows[cnt].name = "(i, j) s.t. j-i = %d" % s
  rows[cnt].set_bounds(Rglpk::GLP_DB, 0, 1)

  vec = [0] * (SIZE ** 2)
  for i in 0...SIZE
    vec[i * SIZE + (s + i)] = 1 if (0...SIZE).include?(i) && (0...SIZE).include?(s + i)
  end
  mat << vec
  cnt += 1
end

#制約式の係数リストを渡す.
#何故か一次元配列...
lp.set_matrix(mat.flatten)

#目的関数を作る.
#制約満たすのを一つ欲しいだけなら, 省略しても大丈夫っぽい.
#dirは最大化又は最小化に従って, GLP_MAX又はGLP_MIN.
#変数に対する係数のリストの形で与える.
#coefsはcolsの後じゃないとダメっぽい.
lp.obj.name = "number of Queens"
lp.obj.dir = Rglpk::GLP_MAX
lp.obj.coefs = [1] * (SIZE ** 2)

#MIPの時はmip, LPの時はsimplex使う.
#MIPでも, simplexでLP緩和を解けるっぽい.
#MIPの時は{:presolve => Rglpk::GLP_ON}するか, 先にsimplexするかで, LP緩和問題を解いておく.
#lp.simplex
lp.mip({:presolve => Rglpk::GLP_ON})

#結果のチェック.
#OPTIMALだとRglpk::GLP_OPTになるっぽい.
#LPの時はstatus, MIPの時はmip_status.
raise unless lp.mip_status == Rglpk::GLP_OPT

#結果の取り出し.
#LPの時はget_prim, MIPの時はmip_val.
for i in 0...SIZE
  for j in 0...SIZE
    print cols[i * SIZE + j].mip_val.round
  end
  puts
end

解らなかったらrglpk/testの中を漁る.
定数とかはrglpk/ext/glpk_wrapper.cの下の方とかにあったりする.