最適化系の問題を解いてみる。完結編

6年前に書いた記事があった。

sasau.hatenablog.com

ここでは僕の好きなhttps://checkio.org/のある問題を通して、最適化系の問題を解いていた。
それで、まあ、プログラミングの問題としては一応解けたわけだけど、最適化についてなんか、こういう方法に落とし込めば解ける、のようなものがあるのではないかという課題感を残したままだった。
そこから時は流れ...世の中には線形計画法というすごい手法があることを知った。
それを使って、この問題を解いてみた。
pulpは線形計画法のライブラリ→ https://coin-or.github.io/pulp/

import pulp
from typing import Tuple, Set
from functools import reduce


def break_rings(input_value: Tuple[Set[int]]):
    # # 問題定義
    # つながっているリング
    p: pulp.LpProblem = pulp.LpProblem("BreakRings", sense=pulp.LpMaximize)

    # 存在するリングを列挙
    # {1, 2, 3, 4, 5, 6}
    all_rings = reduce(lambda cur, pair: cur | pair, input_value)

    # 変数を定義する。それぞれのリングを残す場合を1, 壊す場合を0とする。
    # {1: x1, 2: x2, 3: x3, 4: x4, 5: x5, 6: x6}
    ring_variables = {
        num: pulp.LpVariable(f"x{num}", 0, 1, cat=pulp.LpInteger) for num in all_rings
    }

    # リング、x1~x6までの合計を目的関数にして、これを最大化する。
    p += sum(ring_variables.values()), "目的関数"

    # リングの繋がりの制約. リングのペアは全て壊れているか、1つだけ残っているかのいずれか。
    # つまりリングのペアの合計は1以下
    for ring_pair in input_value:
        ring1, ring2 = ring_pair
        p += ring_variables[ring1] + ring_variables[ring2] <= 1

    # # 解析
    result = p.solve()
    pulp.LpSenses[result]
    v = pulp.value(p.objective)

    # 求めるのは壊す回数なので残ったリングの数を最初のリングの数から引く
    print(len(all_rings) - v)
    for v in p.variables():
        print(f"{v} = {pulp.value(v)}")


if __name__ == "__main__":
    # 簡単な問題
    break_rings(({1, 2}, {2, 3}, {3, 4}, {4, 5}, {4, 6}, {6, 5}))
    # 少し複雑な問題
    break_rings(
        (
            {3, 4},
            {5, 6},
            {2, 7},
            {1, 5},
            {2, 6},
            {8, 4},
            {1, 7},
            {4, 5},
            {9, 5},
            {2, 3},
            {8, 2},
            {2, 4},
            {9, 6},
            {5, 7},
            {3, 6},
            {1, 3},
        )
    )

実行結果は

(...中略)

3.0
x1 = 1.0
x2 = 0.0
x3 = 1.0
x4 = 0.0
x5 = 1.0
x6 = 0.0

(...中略)

5.0
x1 = 0.0
x2 = 0.0
x3 = 1.0
x4 = 0.0
x5 = 0.0
x6 = 0.0
x7 = 1.0
x8 = 1.0
x9 = 1.0

となる。
これらの結果は正しい。

まとめ

前回までで

ペアのどちらかに該当する数字で、全てのペアを網羅するリングの数字を列挙すれば良いのでは？

というように問題を観察して、モデル化するところまでは済んでいたのでその通りに数式に落とすことで解くことができた。
とはいえ、前回までは

やる前は、知ってるか知らないかで終わるような解答があるのではみたいな甘えた考えがあったが、まあ、ないよな...。

というように、なにかこういう問題について明瞭な解き方のようなものがあるのではないかという疑問が残った形で終わったが、以下のように回答を得ることができた。

• モデル化を行い数式に落とし込むことで機械の力を借りて解くことができる
• 線形計画法は便利

知っている人にはひどく当たり前のような話なんだろうけど、学んだことが過去自分が取り組んだ問題に繋がると成長を実感できる。