数理最適化で全国小中学生プログラミング大会グランプリ作品を解く

これなに

「Pythonとグラフ理論で全国小中学生プログラミング大会グランプリ作品を解く - Qiita」を数理最適化で解いてみました。

数理最適化については、「組合せ最適化を使おう」を参照ください。

Pythonのコード

各頂点の次数を入力とします。
各辺が存在するかどうかを変数とすれば、次数が一致する制約条件を作ればOKです。

import pandas as pd
from pulp import LpProblem, lpSum
from ortoolpy import addbinvars, addvals

# 次数のデータ
data = [[int(c) for c in s] for s in """\
12232
23333
33333
24442
13331""".splitlines()]

nr, nc = len(data), len(data[0])
# 変数表（df）の作成（Horionは水平かどうか）
df = pd.DataFrame([(False, i, j) for i in range(nr - 1) for j in range(nc)] +
                  [(True, i, j) for i in range(nr) for j in range(nc - 1)],
                  columns=['Horion', 'Row', 'Col'])
addbinvars(df)  # 変数追加
m = LpProblem()  # 数理モデル（目的関数なし）
for i in range(nr):
    for j in range(nc):
        # (i, j)の次数を一致させる制約条件
        m += lpSum(df[(df.Horion & (df.Row == i) & (df.Col.isin((j - 1, j)))) |
                      (~df.Horion & (df.Row.isin((i - 1, i))) & (df.Col == j))].Var) == data[i][j]
m.solve()  # 解を求める
addvals(df)  # 結果追加
# 得られた辺の集合
st = set(df[df.Val > 0.5].set_index(['Horion', 'Row', 'Col']).index)
# 結果の表示
for i in range(nr):
    for j in range(nc - 1):
        print(' --' if (True, i, j) in st else '   ', end='')
    print()
    if i < nr - 1:
        for j in range(nc):
            print('|' if (False, i, j) in st else ' ', end='  ')
        print()

出力結果

 --    -- --
   |  |  |  |  
 --    -- --
|  |  |     |  
 --    -- --
|  |  |  |  |  
 -- -- -- --
   |  |  |     
 -- -- -- --

元の結果と異なりますが、次数が一致しているのが確認できます。

以上