Edited at

競プロerのための整数計画ソルバー入門

この記事は Competitive Programming (2) Advent Calendar 2018 の 3 日目の記事です.

2 日目の記事は rian_tkb さんの 2018 ICPC Asia Hanoi Regional Contest です.

4 日目はこの記事を書いている時点では埋まっておらず,

直近の埋まっている日は 6 日目で Mister さんの「超自己流 解説記事の書き方」です.

(状況が変わったら反映します.)


はじめに

すべてはこの問題から始まった…….

KUPC2018 C 問題


9×9 のマス目があり、最初マス目は全て白で塗られています。

あなたはできるだけ少ないマスを黒で塗りつぶし、白いマスが縦、横、斜めのいずれにも 7 マス連続して並ばないようにしたいです。

そのような塗りつぶし方の中から 1 つを出力してください。


この問題に対する解法は主に以下の 2 通りでしょう.


  1. 地頭

  2. 枝刈り全探索

筆者はコンテスト本番でこの問題に取り組んだのですが,

1 は筆者には難しく,2 もその場でコードを書くとバグらせそうだと感じました.

そこで筆者は思いついたのです,禁忌の手段 †整数計画ソルバー† に頼ることを…….


この記事では,競プロer向けに整数計画ソルバーの使い方を説明します.

整数計画ソルバーとは,整数計画問題のソルバーです.

整数計画問題とは,「何らかの制約1のもとで,ある目的関数を最大化 or 最小化せよ」という形で書ける問題で,変数が整数値を取るものです.

整数計画問題として定式化できる問題は多く,定式化さえできてしまえば,あとは整数計画ソルバーに投げるとよしなに問題を解いてくれます.

整数計画ソルバーを用いる利点としては,


  • 様々な問題を統一的な枠組みで解ける

  • 定式化さえ与えれば,問題を解くプログラムを自分で実装する必要はない→時間短縮,バグ軽減につながる

といった点があります.一方で,整数計画ソルバーを用いる欠点としては,


  • オンラインジャッジ上では使えないことが多い

  • 定式化の仕方になれないとちょっと大変

  • グレー2

といった点があります.オンラインジャッジ上では使えないので,基本的にはローカルでの運用(いわゆる「実験」や「埋め込み」用)になります.

定式化の仕方については,この記事で上記の問題を例にとって説明します.

整数計画ソルバーとして,この記事では無料ですぐ使える PuLP3 を用います.

PuLP は Python で使える整数計画ソルバーのパッケージです.

PuLP のインストール方法については以下をご覧ください4

PuLP による線型計画問題の解き方ことはじめ

この記事では整数計画問題とは何か?や定式化の仕方から説明します.

ソルバーの使い方が知りたいという人は最後の方からどうぞ.


整数計画問題とは?

整数計画問題とは,「何らかの制約のもとで,ある目的関数を最大化 or 最小化せよ」という形で書ける問題で,変数が整数値を取るものです.

例えば,次のナップザック問題を考えます.


$N$ 個のアイテムがあり,$i$ 番目のアイテムは大きさ $w_i$ と価値 $v_i$ をもつ.

大きさの和が $C$ を超えないようにアイテムをいくつか選ぶとき,価値の和の最大値を求めよ.


この問題は次のように定式化できます.

\begin{align}

&\mbox{maximize} && \sum_{i=1}^{N} v_i x_i && \\
&\mbox{subject to} && \sum_{i=1}^{N} w_i x_i \leq C && \\
&&& x_i \in \{0, 1\} && 1 \leq i \leq N
\end{align}

変数 $x_i$ は $x_i = 1$ のとき $i$ 番目のアイテムを選ぶことを,$x_i = 0$ のとき $i$ 番目のアイテムを選ばないことを意味します.

この変数を用いると,選んだアイテムたちの価値の和は $\sum_{i=1}^{N} v_i x_i$, 大きさの和は $\sum_{i=1}^{N} w_i x_i$ と書くことができ,上のように簡潔に問題を記述できます.

整数計画問題で最大化(or 最小化)する対象を目的関数といい,その最大値(or 最小値)を最適値,最適値を与える $x$ を最適解といいます.

整数計画問題として定式化できる問題は多く,例えばナップザック問題,巡回セールスマン問題,頂点被覆問題など多岐に渡ります.

また,8-クイーン問題のような組合せ的な問題を定式化するのにも適しています.


整数計画ソルバーとは?

整数計画ソルバーとは,整数計画問題のソルバーです.

整数計画問題の定式化を与えると,最適値と最適解を出力してくれます.

整数計画問題は一般に NP 困難なので,計算量を理解している競プロerなら {0,1}-変数が 30 個程度で限界ではと思うかもしれません.

しかし整数計画ソルバーには様々な高速化のテクニックが実装されており,実用上は変数が数百個程度なら数秒で解けてしまうようです.

有名な整数計画ソルバーとしては CPLEX, Gurobi, PuLP などがあります.

この記事では誰でも無料で使える PuLP を使うことにします.


PuLP とは?

PuLP は Python で使える整数計画ソルバーのパッケージです.

Python 上で整数計画問題の定式化を記述することができます.

定式化さえ与えれば後は勝手に解いてくれるのが魅力で,汎用的なソルバーとして活用することができます.


PuLP で競プロの問題を解く

この記事では冒頭に挙げた KUPC2018 C 問題を整数計画ソルバーで解いてみたいと思います.

問題文を再掲します.


9×9 のマス目があり、最初マス目は全て白で塗られています。

あなたはできるだけ少ないマスを黒で塗りつぶし、白いマスが 縦、横、斜めのいずれにも 7 マス連続して並ばないようにしたいです。

そのような塗りつぶし方の中から 1 つを出力してください。


ここから問題の解き方を次の 2 つのステップに分けて説明します.


  1. 整数計画問題としての定式化

  2. PuLP によるコーディング

定式化はわかるという人はコーディングの方から読んでもらえば OK です.


整数計画問題としての定式化

整数計画ソルバーで問題を解くためには,まずは問題を整数計画問題として定式化する必要があります.

整数計画問題として定式化する手順はいろいろあると思いますが,筆者は以下のように考えるのがわかりやすいと思います5


  1. 何を変数にすればよいか?

  2. 目的関数は何か?

  3. 制約は何か?

この手順に沿って,実際に問題を定式化してみましょう.


変数

まずは何を変数にすればよいかを考えます.

何を変数にするかは,「この問題で何を決めたいか」を考えるとわかりやすいです.

今回の問題では,9x9 の各マスに対して,各マスを「黒で塗るか」「白のままにするか」を決めたいわけです.

そこで,各マスに対応する変数を定義しましょう.

$1$ 以上 $9$ 以下の整数 $i, j$ に対して $i$ 行 $j$ 列目のマスを $(i,j)$ と書くことにします.

そして,変数 $x_{(i,j)}$ を $(i,j)$ を黒で塗るとき $1$, 白のままにするとき $0$ と定義します.


目的関数

次に,目的関数を定義します.

問題を読むと「できるだけ少ないマスを黒で塗りつぶし」とありますが,

これは「黒で塗りつぶすマスの個数を最小化したい」と言い換えることができます.

先程定義した変数を使うと,黒で塗りつぶすマスの個数は以下の式で書けます.

\sum_{i=1}^{9} \sum_{j=1}^{9} x_{(i,j)}


制約

最後に制約を考えます.

問題を読むと「白いマスが縦,横,斜めのいずれにも 7 マス連続して並ばないようにしたい」(☆)とあります.

これを式で表現してみましょう.

(☆)は次のように言い換えられます:「縦,横,斜めに連続するどの 7 マスに対しても,少なくとも 1 つ黒で塗りつぶす」

例として縦に連続する 7 マス $(1,1)$ から $(7,1)$ を考えると,これら 7 マスのうち少なくとも 1 つを黒で塗りつぶすという条件は以下のように書けます.

x_{(1,1)} + x_{(2,1)} + x_{(3,1)} + x_{(4,1)} + x_{(5,1)} + x_{(6,1)} + x_{(7,1)} \geq 1

左辺が $(1,1)$ から $(7,1)$ までの 7 マス中の黒で塗りつぶすマスの個数を表しており,これが $1$ 以上であることが少なくとも 1 つを黒で塗りつぶすことに対応しています.

上の式は,総和記号を用いると次のように短く書けます.

\sum_{k=0}^{6} x_{(1+k,\,1)} \geq 1

同様に他の 7 マスたちについても考えると,以下のように制約が書けます.

それぞれの不等式たちは,上から順に縦,横,斜め(左上→右下),斜め(右上→左下)に対応しています.

\begin{align}

& \sum_{k=0}^{6} x_{(i+k,\, j)} \geq 1 && 1 \leq i \leq 3,\ 1 \leq j \leq 9 \\
& \sum_{k=0}^{6} x_{(i,\, j+k)} \geq 1 && 1 \leq i \leq 9,\ 1 \leq j \leq 3 \\
& \sum_{k=0}^{6} x_{(i+k,\, j+k)} \geq 1 && 1 \leq i \leq 3,\ 1 \leq j \leq 3 \\
& \sum_{k=0}^{6} x_{(i+k,\, j-k)} \geq 1 && 1 \leq i \leq 3,\ 7 \leq j \leq 9 \\
\end{align}

これまでの結果をまとめると,以下のように問題を定式化できました.

\begin{align}

&\mbox{minimize} && \sum_{i=1}^{9} \sum_{j=1}^{9} x_{(i,\,j)} && \\
&\mbox{subject to} && \sum_{k=0}^{6} x_{(i+k,\, j)} \geq 1 && 1 \leq i \leq 3,\ 1 \leq j \leq 9 \\
&&& \sum_{k=0}^{6} x_{(i,\, j+k)} \geq 1 && 1 \leq i \leq 9,\ 1 \leq j \leq 3 \\
&&& \sum_{k=0}^{6} x_{(i+k,\, j+k)} \geq 1 && 1 \leq i \leq 3,\ 1 \leq j \leq 3 \\
&&& \sum_{k=0}^{6} x_{(i+k,\, j-k)} \geq 1 && 1 \leq i \leq 3,\ 7 \leq j \leq 9 \\
&&& x_{(i,j)} \in \{0, 1\} && 1 \leq i \leq 9,\ 1 \leq j \leq 9
\end{align}

最後の式は $x_{(i,\, j)}$ が $0$ または $1$ の変数であることを表しています.一応これも含めて定式化です.


PuLP によるコーディング

PuLP では,問題を表すオブジェクトに目的関数や制約式を追加していくという形で問題を定式化します.

次のコードを見るとなんとなく雰囲気がわかると思います.

import pulp

# 問題オブジェクトを初期化(最小化なので pulp.LpMinimize)
problem = pulp.LpProblem('KUPC2018_C', pulp.LpMinimize)

# 変数とその定義域の定義
x = pulp.LpVariable.dicts('x', (range(9), range(9)), 0, 1, pulp.LpInteger)

# 目的関数の定義
problem += pulp.lpSum(x[i][j] for i in range(9) for j in range(9))

# 制約式の定義
for i in range(3):
for j in range(9):
problem += (pulp.lpSum(x[i+k][j] for k in range(7)) >= 1)

for i in range(9):
for j in range(3):
problem += (pulp.lpSum(x[i][j+k] for k in range(7)) >= 1)

for i in range(3):
for j in range(3):
problem += (pulp.lpSum(x[i+k][j+k] for k in range(7)) >= 1)

for i in range(3):
for j in range(6, 9):
problem += (pulp.lpSum(x[i+k][j-k] for k in range(7)) >= 1)

# # 問題を出力
# print(problem)

# 問題を解く(結果を status に格納)
status = problem.solve()

# 結果を見る
print("Status", pulp.LpStatus[status])
print("Min", pulp.value(problem.objective))

# KUPC2018_Cの出力形式に合わせて最適解を出力
s = [['.' for i in range(9)] for j in range(9)]
for i in range(9):
for j in range(9):
if x[i][j].value() == 1:
s[i][j] = '#'
print("".join(s[i]))

問題を表すオブジェクト problem+= で変数や制約を追加できるのがすごいところです.

このように,PuLP では直感的に整数計画問題の定式化を記述することができます.

また,Python(というかプログラミング言語)なので,似た制約をループで書く等の処理も簡単にできます.

上のコードを実行すると,筆者の環境では 1 秒足らずで以下の出力が得られました.

(下記の「出力結果」をクリックすると折り畳まれている文章が表示されます(ネタバレ防止))

出力結果

Status Optimal

Min 11.0
......#..
..#......
#......#.
.....#...
....#....
...#.....
.#......#
......#..
..#......

最適解が求まっていて,最適値は 11 であることがわかります.

結構きれいな配置が得られて気持ちいいですね.

あとはこれを Text (cat) で提出すれば AC です!6



まとめ

この記事では競プロer向けに整数計画ソルバーの使い方について説明しました.

整数計画ソルバーは,整数計画問題としての定式化さえ与えれば後は勝手に問題を解いてくれるので,「実験」や「埋め込み」をするときの汎用的なソルバーとして役に立つと思います.

困った時は整数計画ソルバーのことを思い出してみてもいいかもしれません.

ただし,整数計画ソルバーを使わなくて済むならその方がいいと思います7


参考文献

PuLPによる線型計画問題の解き方ことはじめ

Python+PuLPによるタダで仕事に使える数理最適化

整数計画ソルバー入門





  1. 制約式は基本的に線形である必要があります.線形でなくとも線形に変換できることもあります(ここ参照) 



  2. コンテストによっては使用が制限されていたりするかもしれないので,ルールをよく確認してください(実際にそういうコンテストがあるのかは知りませんが).このような記事を書いておいてなんですが,本記事は競プロにおける整数計画ソルバーの使用を特別奨励するものではありません.あくまで「困ったときの最終手段」くらいの認識でお願いします. 



  3. 正確には PuLP はソルバーではなくモデラー(問題の式をコーディングするためのライブラリ)です.内部ではデフォルトで COIN というソルバーが呼ばれています.COIN は PuLP に同梱されているので,PuLP をインストールすれば使えるようになります. 



  4. 筆者は正直 PuLP をインストールしたのが昔すぎてやり方を忘れました.PuLP の前に Python をインストールする必要があるかもしれません. 



  5. 個人的には,整数計画問題の定式化を考える手順は,動的計画法のそれと似ている気がします.動的計画法だと「状態を定義して,状態間の遷移を考える」のが,整数計画問題だと「変数を定義して,変数間の制約を考える」という感じです. 



  6. コンテストによっては歓迎されないこともあると思うので,自己責任で……. 



  7. この記事の存在意義とは…….