조합 최적화로 풀기 풀기

Advent Calendar 7 일째 기사 조합 최적화로 인자의 방을 풀기
Advent Calendar 9 일째 기사 조합 최적화로 초코나 풀기

이게 뭐야

풀을 파이썬으로 조합 최적화 모델을 만들어 풀어 라.
푸는 재미는 모델링을 고안하는 것입니다.

자신도 시도하고 싶은 사람은 아래를 참조하십시오.

스도쿠를 통해 조합 최적화를 배우자.

문제

반면의 일부 송어를 검은색으로 칠합니다.

블랙 매스는 반드시 세로나 가로에 딱 2개만 색칠합니다.

굵은 선으로 단락지어진 각 부분에는, 흑 매스가 2개씩 들어갑니다.

왼쪽이 문제이고 오른쪽이 대답입니다.



파이썬에서는 data (룸 그룹)을 사용하기로 결정합니다.

파이썬

import pandas as pd, matplotlib.pyplot as plt
from pulp import LpProblem, lpSum, value
from ortoolpy import addbinvars
data = """\
ABBBC
ADDBC
EDBBB
EEEEE
EEEEE""".splitlines()

변수 테이블

아래와 같은 변수 테이블을 작성합니다. 각 행의 변수는 0 또는 1을 취합니다.
변수의 값이 1이면 해당 행 해당 열의 질량이 검정색입니다.


행
열
글자
Var

0
0
0
A
v000001

1
0
1
B
v000002

...
...
...
...
...


파이썬

ni, nj = len(data), len(data[0])
a = pd.DataFrame([(i,j,data[i][j]) for i in range(ni)
    for j in range(nj)], columns=list('行列字'))
a['Var'] = addbinvars(len(a))
a[:2]

수리 모델을 만들어 풀다

변수 테이블이 생겼으므로 풀기의 해가되도록 제약 조건을 추가하고 수리 모델을 작성하고 풀어 봅시다.

어떤 매스가 블랙이면, 그 상하 좌우의 블랙의 수는 정확히 1이 된다. 이것은 다음 두 가지 식으로 표현할 수 있습니다 (M은 충분히 큰 수).

상하좌우의 검은 수 >= 해당 매스의 검은 수

상하좌우의 검은 수 <= 1 + M*(1-해당 매스의 검정의 수)

각 그룹 내의 검정의 수는 다만 2.

파이썬

m = LpProblem()
for _,r in a.iterrows():
    e = lpSum(a.query(f'abs(行-{r.行})+abs(列-{r.列})==1').Var)
    m += e >= r.Var
    m += e <= 1+(len(e)-1)*(1-r.Var)
for g,v in a.groupby('字'):
    m += lpSum(v.Var) == 2
m.solve()

결과 표시

파이썬

a['Val'] = a.Var.apply(value)
plt.imshow((a.Val<0.5).values.reshape(ni,nj), cmap='gray', interpolation='none')
plt.show()

풀리고 있는지 확인할 수 있습니다.

이상