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

이전 글에 이어서 제약조건을 설정하고 최적화를 실행하는 부분을 설명하겠습니다.

# 제약조건
for i in range(n):
  model.Add(xb1[i] == x[i] + b[i]*W)
  model.Add(xb2[i] == xb1[i] + w[i])

model.AddNoOverlap2D(xival,yival)
model.AddMaxEquality(z,[b[i] for i in range(n)])

# 목적함수
model.Minimize(z)

# 모델 최적화
solver = cp_model.CpSolver()
# 로그 남기기
solver.parameters.log_search_progress = True
# search worker 개수 지정 - 멀티스레드
#solver.parameters.num_search_workers = 4
rc = solver.Solve(model)
print(f"return code:{rc}")
print(f"status:{solver.StatusName()}")

제약조건 부분을 보면 model.Add, model.AddNoOverlap2D, model.AddMaxEquality 가 있습니다.

model.Add에서 박스의 시작과 끝 영역이 박스의 너비와 일치해야한다는 제약조건을 추가했고, model.AddNoOverlap2D에서는 박스의 너비에 해당하는 x interval 변수들과 박스의 높이에 해당하는 y interval 변수들이 서로 중첩되서는 안된다는 제약 조건을 추가하고, AddMaxEquality에서는 각 bin({h:60, w:34})에 최대한 많은 아이템을 각 bin에 배치하도록 제약합니다.

목적함수 부분에는 bin의 개수는 최소화 하는 걸 목적으로 합니다(각 bin에는 최대의 아이템할당, bin의 개수를 최소화).

해당 모델을 풀기위한 최적화 모델을 생성하고 솔루션 풀이를 시도하고 그 결과를 화면에 출력합니다.

소스에서 18번째 줄을 부면 결과값을 rc 변수에 저장하는데, rc에 올수 있는 값은 아래와 같습니다.

cp_model.UNKNOWN : 알수 없음
cp_model.MODEL_INVALID : 모델이 유효하지 않음
cp_model.FEASIBLE : 실행 가능
cp_model.INFEASIBLE : 실행 불가능
cp_model.OPTIMAL : 최적의 풀이

 

다음 글에서는 최적화 결과를 챠트 형태로 확인하는 방법에 대해 설명하겠습니다.