#3-1 OrTools로 bin packing 문제 해결(CP-SAT)

2D bin packing(상자 채우기) 문제는 2차원 평면에 사각형의 객체를 적절히 채우는 문제입니다. 이 문제를 푸는 방법은 상당히 여러가지가 있는 것 같습니다. 여기말고 '티바이트' 라는 분의  블로그에 상당히 자세한 알고리즘 풀이가 있으니, 궁금하신 분들은 참고하시면 좋을 것 같습니다.

이 글에서는 OrTools의 CP-SAT 솔버를 통해 문제를 해결하는 방법을 보여드립니다. 아래 소스의 대부분은 "Yet Another Math Programming Consultant"라는 분의 블로그의 글을 참고했습니다.

우선 결과부터 보여드리면 아래와 같습니다.

2D Bin Packing

너비 68, 높이 60 영역에 50개에 서로 크기가 같거나 다른 상자를 채운 모습입니다.

소스는 크게 4부분으로 나누어 집니다.

1. 데이터 정의
2. 제약 조건 추가
3. 목적함수 정의 및 최적화 실행
4. 최적화 결과 표시

우선 <1.데이터 정의> 하는 부분의 소스입니다.

import matplotlib.pyplot as plt
import matplotlib.font_manager as fm
from ortools.sat.python import cp_model
import pandas

# data 정의
# bin 은 채울 공간의 너비와 높이
# catN은 쌓을 객체의 너비와 높이와 수량
data = {'bin':{'h':60,'w':34},
        'cat1':{'w': 7,'h':12,'items':10},
        'cat2':{'w': 9,'h': 3,'items':10},
        'cat3':{'w': 5,'h':14,'items':10},
        'cat4':{'w':13,'h': 9,'items':10},
        'cat5':{'w': 6,'h': 8,'items': 5},
        'cat6':{'w':20,'h': 5,'items': 5}}      

# bin의 width와 height 추출
H = data['bin']['h']
W = data['bin']['w']

# 각 아이템의 높이, 너비, 카테고리이름 배열 추출
h = [data[cat]['h'] for cat in data if cat!='bin' for i in range(data[cat]['items'])]
w = [data[cat]['w'] for cat in data if cat!='bin' for i in range(data[cat]['items'])]
cat = [cat for cat in data if cat!='bin' for i in range(data[cat]['items'])]
n = len(h)  # 총 아이템 개수
m = 10  # 최대 bin 개수

# OR-Tools 모델
model = cp_model.CpModel()

# x와 y
x = [model.NewIntVar(0,W-w[i],f'x{i}') for i in range(n)]
xb1 = [model.NewIntVar(0,m*W-w[i],f'xb1.{i}') for i in range(n)]
xb2 = [model.NewIntVar(w[i],m*W,f'xb2.{i}') for i in range(n)]
y1 = [model.NewIntVar(0,H-h[i],f'y1.{i}') for i in range(n)]
y2 = [model.NewIntVar(h[i],H,f'y2.{i}') for i in range(n)]

# interval variables
xival = [model.NewIntervalVar(xb1[i],w[i],xb2[i],f'xival{i}') for i in range(n)]
yival = [model.NewIntervalVar(y1[i],h[i],y2[i],f'yival{i}') for i in range(n)]

# 아이템 빈의 개수
b = [model.NewIntVar(0,m-1,f'b{i}') for i in range(n)]

# 목적 대상 변수 지정
z = model.NewIntVar(0,m-1,'z')

x, y는 사각형의 왼쪽 아래쪽 모서리고, xb1, xb2, y1, y2는 너비와 높이를 더한 위치라고 볼 수 있다. 이렇게 최적화 가능한 변수의 범위를 정의합니다. 다음 글에서는 제약조건 설정과 최적화 된 결과를 보는 부분에 대한 설명을 이어나가겠습니다.