조합 최적화로 인자의 방을 풀기

Advent Calendar 6 일째 기사 조합 최적화로 타일 페인트 풀기
Advent Calendar 8 일째 기사 조합 최적화로 풀기 풀기

이게 뭐야

요인의 방을 Python으로 조합 최적화 모델을 만들어 풀어 라.
푸는 재미는 모델링을 고안하는 것입니다.

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

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

문제

모든 매스에 1부터 N까지의 숫자의 어느 하나를 하나씩 들어갑니다 (0은 사용하지 않습니다).

세로 열, 가로 열 모두 1에서 N까지의 숫자가 하나씩 들어갑니다.

굵은 선으로 둘러싸인 사각형(방)의 좌상의 매스에 작게 쓰여져 있는 수는, 그 방의 각 매스에 들어가는 수를 모두 곱한 값이 됩니다.

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



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

파이썬

import pandas as pd
from math import log
from pulp import LpProblem, lpSum, lpDot, value
from ortoolpy import addbinvars
data = """\
ABBCD
AEEFD
GGHFD
IJHKK
ILHMM""".splitlines()
nums = {'A':6, 'B':15, 'C':1, 'D':12, 'E':20, 'F':8,
    'G':10, 'H':6, 'I':4, 'J':4, 'K':15, 'L':1, 'M':10}

변수 테이블

아래와 같은 변수 테이블을 작성합니다. 각 행의 변수(Var)는 0 또는 1을 취합니다.
변수의 값이 1이면 해당 행 해당 열의 매스가 해당 수가 됩니다.


행
열
수
글자
Var

0
0
0
1
A
v000001

1
0
0
2
A
v000002

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


파이썬

nn = len(data)
a = pd.DataFrame([(i,j,k,data[i][j]) for i in range(nn)
    for j in range(nn) for k in range(1,nn+1)], columns=list('行列数字'))
a['Var'] = addbinvars(len(a))
a[:2]

수리 모델을 만들어 풀다

변수 테이블이 생겼으므로 요인의 방을 풀 수 있도록 제약 조건을 추가하고 수리 모델을 만들고 풀어 봅시다.

각 매스에 숫자를 1개 넣는다.

for _,v in a.groupby(('行','列')) 에서 하나의 매스 변수가 DataFrame의 v 에 들어가므로 m += lpSum(v.Var) == 1 하면 숫자를 하나 선택하게 됩니다.

각 행에서 같은 숫자는 1개. ('행','수')로 하면 위와 같습니다.

각 열에 같은 숫자는 1개. ('열', '수')로 하면 위와 같습니다.

곱한 숫자가 힌트와 같습니다. 곱셈은 ​​log 를 취하면 덧셈이 됩니다. 계산 오차에 주의해, 등호가 아니고, 어느 폭에 들어가도록(듯이) 제약을 겁니다.

파이썬

m = LpProblem()
for cl in [('行','列'),('行','数'),('列','数')]:
    for _,v in a.groupby(cl):
        m += lpSum(v.Var) == 1
for g,v in a.groupby('字'):
    e = lpDot([log(i) for i in v.数], v.Var) - log(nums[g])
    m += e >= -0.0001
    m += e <=  0.0001
m.solve()

결과 표시

파이썬

a['Val'] = a.Var.apply(value)
print(a[a.Val>0.5].数.values.reshape(nn,nn))
>>>
[[2 3 5 1 4]
 [3 5 4 2 1]
 [5 2 1 4 3]
 [1 4 2 3 5]
 [4 1 3 5 2]]

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

이상