やりたいこと

下図のようなエリアがあります。

この三角形の中央にセンサーを設置して、データ収集をします。
総取得データ量を最大化することが目的です。
1つの三角形に1つまでしかセンサーは置けません。
1つのセンサーを置くと、データ量 3 を取得できます。
予め、センサーを設置しなければいけない箇所と、センサーを設置してはいけない箇所が決まっています。
下表のように、隣りに別のセンサーがあると、干渉を起こして、取得データ量が各々 1 減ります。(合計 2 減少)
- 従って、周りに2以上のセンサーがある場合は、設置しない方がよいことになります。

周りのセンサー数	取得データ量	干渉データ量	全体として増えるデータ量
0	3	0	3
1	3	2	1
2	3	4	-1
3	3	6	-3

混合整数最適化問題による最適化(数理問題によるアプローチ)

混合整数最適化問題(Mixed Integer optimization Problem: MIP)としてモデル化してみましょう。
定式化や考え方については、組合せ最適化を使おうを参考にしてください。

定式化

最大化	$取得データ量 \\ = 3 \times 設置するかどうか - 2 \times 干渉するかどうか$
変数	$(センサーを)設置するかどうか \in\{0，1\} \forall 設置箇所$
変数	$干渉するかどうか \ge 0 \forall 隣接箇所$
制約条件	$設置するかどうか_1 + 設置するかどうか_2 - 干渉するかどうか \le 1$

最小カット問題による最適化(典型問題によるアプローチ)

グラフ理論で最小カット問題というものがあります。

以下のようなs-tグラフを考えます。この有向グラフのs-t最小カットを求めると、元のセンサー設置問題の最適解を得ることができます。
元の問題は最大化問題ですが、"3 －取得データ量"をコストと考えることにより、最小化問題としてとらえます。
詳しくは、後述の参考サイトをご覧ください。

s-tグラフ

(0,0),(0,1),(1,0)の3つの例を上図に示します。
始端ノード"s"から、各箇所(三角形)に辺を引きます。また、各箇所から終端ノード"t"にも辺を引きます。
上三角の箇所(上図では(0,0)と(1,0))では、sからの辺は"設置"を表し、tへの辺は"非設置"を表します。
下三角の箇所(上図では(0,1))では、sからの辺は"非設置"を表し、tへの辺は"設置"を表します。
設置の辺の重みは0とし、非設置の辺の重みは3とします。(重みは、"3 －取得データ量"です。)
全ての隣接箇所に対して、下三角から上三角に、重み2の辺を引きます。
"設置"で固定する場合、"設置"の辺は削除(カット済み)とし、"非設置"の辺の重みを十分大きくします。
"非設置"で固定する場合、"非設置"の辺は削除(カット済み)とし、"設置"の辺の重みを十分大きくします。

s-tグラフの意味

s-tカットするためには、各々の箇所において、設置または非設置の辺のどちらかをカットすることになります。カットされた方を選んだものとみなします。
s-tカットが成り立つためには、隣接箇所共に設置した場合、干渉の辺もカットする必要があり、干渉量を表現できます。(上三角と下三角で分けたことで上手くいきます。)

最小カット問題について

最小カット問題は、多項式時間で解ける解きやすい問題です。後述のプログラムでは、Pythonのnetworkxを用いて解きます。
ちなみに、最小カット問題の双対問題は、最大流問題です。

pythonによる実行例

準備をします。

python3

import numpy as np, networkx as nx
from pulp import *
def addvar(lowBound=0, var_count=[0], *args, **kwargs):
    """変数作成用ユーティリティ"""
    var_count[0] += 1
    return LpVariable('v%d' % var_count[0], lowBound=lowBound, *args, **kwargs)
def calc(a, r):
    """rを設置箇所として取得データ量を計算"""
    b = a.copy()
    b[b > 1] = 0
    for x, y in r:
        b[y, x] = 1
    s = b.sum() * 3
    for y in range(0, b.shape[0], 2):
        for x in range(b.shape[1]):
            s -= 2 * b[y, x] * b[y+1,x]
            if x:
                s -= 2 * b[y, x] * b[y+1,x-1]
            if y:
                s -= 2 * b[y, x] * b[y-1,x]
    return s

solve_by_mipは、MIPによる解法です。設置箇所を返します。

python3

def solve_by_mip(a):
    """MIPで問題を解き、設置箇所を返す"""
    nm, nn = a.shape
    b = a.astype(object)
    vv1 = [addvar(cat=LpBinary) for _ in range((b > 1).sum())]
    b[b > 1] = vv1
    vv2 = []
    m = LpProblem(sense=LpMaximize)
    for y in range(0, nm, 2):
        for x in range(nn):
            chk(m, vv2, b[y,x] + b[y+1,x])
            if x: chk(m, vv2, b[y,x] + b[y+1,x-1])
            if y: chk(m, vv2, b[y,x] + b[y-1,x])
    m += 3 * lpSum(vv1) - 2 * lpSum(vv2)
    m.solve()
    return [(x, y) for x in range(nn) for y in range(nm)
            if isinstance(b[y,x], LpVariable) and value(b[y, x]) > 0.5]
def chk(m, vv2, e):
    """eが変数を含むならば、共に1であれば目的関数を2減らす制約を追加"""
    if isinstance(e, LpAffineExpression):
        v = addvar()
        vv2.append(v)
        m += e - v <= 1

solve_by_graphは、最小カットによる解法です。同じく設置箇所を返します。

python3

def solve_by_graph(a):
    """最小カット問題で問題を解き、設置箇所を返す"""
    nm, nn = a.shape
    g = nx.DiGraph()
    for y in range(0, nm, 2):
        for x in range(nn):
            if a[y, x] == 0: # off
                g.add_edge('s', (x,y), capacity=7)
            elif a[y, x] == 1: # on
                g.add_edge((x,y), 't', capacity=7)
            else:
                g.add_edge('s', (x,y), capacity=0)
                g.add_edge((x,y), 't', capacity=3)
            if a[y+1, x] == 0: # off
                g.add_edge((x,y+1), 't', capacity=7)
            elif a[y+1, x] == 1: # on
                g.add_edge('s', (x,y+1), capacity=7)
            else:
                g.add_edge('s', (x,y+1), capacity=3)
                g.add_edge((x,y+1), 't', capacity=0)
            g.add_edge((x,y+1), (x,y), capacity=2)
            if x:
                g.add_edge((x-1,y+1), (x,y), capacity=2)
            if y:
                g.add_edge((x,y-1), (x,y), capacity=2)
    r = []
    for s in nx.minimum_cut(g, 's', 't')[1]:
        b = 's' in s
        for t in s:
            if isinstance(t, str): continue
            x, y = t
            if a[y, x] > 1 and b == (y%2 != 0):
                r.append((x, y))
    return sorted(r)

40×80のサイズで、固定箇所をランダムに設置して、結果を比較してみましょう。

python3

nn, nm = 40, 80 # 横、縦
np.random.seed(1)
a = np.random.randint(0, 6, (nm, nn)) # 0; fix off, 1: fix on, ow:select

%time rmip = calc(a, solve_by_mip(a))
%time rgrp = calc(a, solve_by_graph(a))
print(rmip == rgrp)
>>>
Wall time: 455 ms
Wall time: 185 ms

True

どちらの手法も同じ取得データ量になっている(rmip == rgrp)のが確認できます。
MIPの方が2倍強、遅いです。
- 一般に、汎用ソルバーより専用ソルバーの方が計算が速いです。
- 別途確認したところ、MIPソルバー単体の計算時間は、最小カットによる計算時間を少し上回るくらいでした。
また、理屈はわかっていないですが、MIPを線形緩和しても取得データ量は変わらず、計算時間は若干早くなります。

参考サイト

Problem E. The Year of Code Jam: 参考にした問題
最小カットを使って「燃やす埋める問題」を解く: 参考にした解法

以上