조합 최적화로 빌딩 해결

이게 뭐야

문제

입력 파라미터

import numpy as np
from pulp import LpProblem, lpSum, lpDot, value
from ortoolpy import addvar, addvars, addbinvars
data = """\
   33  
 ..... 
 .....5
2.....1
3.....3
 .....2
  5 13 """.splitlines()
n = len(data)-2

파이썬으로 풀기

변수

제약

m = LpProblem()
v = np.array(addbinvars(n, n, n)) # (1)
r = np.array(addvars(n, n)) # (2)
def add(m, c, p, q, y, x):
    if not c.isdigit():
        return
    k = int(c)
    u = addvars(n-1) # (3)
    m += lpSum(u) == k - 1 # (7)
    vmx = r[p,q]
    for i in range(1,n):
        vnx = r[p + y*i][q + x*i]
        m += vmx + n * u[i-1] >= vnx + 1 # (7)
        m += vmx + 1 <= vnx + n - n * u[i-1] # (7)
        vtm = addvar()
        m += vmx <= vtm # (7)
        m += vnx <= vtm # (7)
        vmx = vtm
    m += vmx <= n # (7)
for i in range(n):
    for j in range(n):
        m += lpSum(v[i,j,:]) == 1 # (4)
        m += lpDot(range(n), v[i,j]) + 1 == r[i,j] # (5)
        m += lpSum(v[i,:,j]) == 1 # (6)
        m += lpSum(v[:,i,j]) == 1 # (6)
    add(m, data[i+1][  0],   i,   0,  0,  1)
    add(m, data[i+1][n+1],   i, n-1,  0, -1)
    add(m, data[  0][i+1],   0,   i,  1,  0)
    add(m, data[n+1][i+1], n-1,   i, -1,  0)
m.solve()

결과 표시

print(np.vectorize(value)(r).astype(int))
>>>
[[2 5 1 3 4]
 [5 4 3 2 1]
 [4 3 2 1 5]
 [1 2 5 4 3]
 [3 1 4 5 2]]