💻 computer science

Solving the Two-dimensional single stock size Cuting Stock Problem with SAT and MaxSAT

이 논문은 2 차원 단일 재단 크기 커팅 스톡 문제 (2D-CSSP) 를 해결하기 위해 SAT 및 MaxSAT 기반 프레임워크를 제안하고, Cui-Zhao 벤치마크에서 기존 상용 솔버보다 더 많은 인스턴스를 최적해로 증명하며 더 낮은 최적성 격차를 달성함을 보여줍니다.

원저자: Tuyen Van Kieu, Chi Linh Hoang, Khanh Van To

게시일 2026-04-03

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Tuyen Van Kieu, Chi Linh Hoang, Khanh Van To

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

이 논문은 **"공장에서 커다란 원단이나 금속판을 잘라내어 필요한 크기의 제품들을 만들 때, 어떻게 하면 가장 적은 수의 원단만 쓰고 낭비를 최소화할 수 있을까?"**라는 문제를 해결하기 위한 새로운 방법을 소개합니다.

이 문제를 쉽게 이해하기 위해 **'거대한 피자 도우를 잘라 여러 개의 피자를 만드는 상황'**으로 비유해 보겠습니다.

1. 문제 상황: 피자 도우와 주문서

상황: 당신은 거대한 피자 도우 (원판) 를 가지고 있습니다.
주문: 고객들이 "작은 정사각형 피자 3 개", "긴 직사각형 피자 2 개" 등을 주문했습니다.
목표: 이 주문들을 모두 채우기 위해 가장 적은 수의 피자 도우를 사용해야 합니다. (남은 도우 조각은 버려야 하므로 낭비를 줄여야 합니다.)
어려움: 같은 종류의 피자가 여러 개 필요할 때 (예: 작은 정사각형 3 개), 이 3 개가 서로 다른 도우에 놓일지, 같은 도우에 놓일지, 어떻게 배치해야 겉보기에 겹치지 않고 들어갈지 계산하는 것이 매우 복잡합니다. 기존 컴퓨터 프로그램들은 이 복잡한 계산 때문에 시간이 너무 오래 걸리거나, "최적의 답"이 맞는지 증명하지 못해 헷갈려 했습니다.

2. 새로운 해결책: "논리 퍼즐"을 푸는 방법 (SAT)

저자들은 이 문제를 수학적인 계산이 아니라, **"논리 퍼즐"**로 접근했습니다. 마치 **"맞춤형 키트"**를 조립하듯이요.

기존 방식의 문제: 모든 조각을 한 번에 다 계산하려다 보니 컴퓨터가 "머리가 터질" 정도로 많은 경우의 수를 다 살펴봤습니다.
이 논문의 방식 (SAT):
1. 조각 나누기: 필요한 피자 조각 (주문) 들을 하나하나 분리해서 각각에게 "너는 1 번 도우에 갈지, 2 번 도우에 갈지?"라고 물어봅니다.
2. 조건부 규칙: "만약 A 조각과 B 조각이 같은 도우에 간다면, 서로 겹치지 않게 배치해야 해!"라는 규칙을 세웁니다. 만약 다른 도우에 간다면 이 규칙은 무시됩니다.
3. 회전 금지/허용: 어떤 조각은 세로로, 어떤 것은 가로로 놓아야 들어갈 수 있습니다. 논리적으로 "이 모양은 도우 크기에 맞지 않으니 회전하지 마"라고 미리 막아주는 지능적인 규칙도 추가했습니다.

이렇게 하면 컴퓨터가 불필요한 경우를 미리 걸러내고, 진짜 해결책만 빠르게 찾아낼 수 있습니다.

3. 세 가지 전략: 어떻게 퍼즐을 푸나?

저자들은 이 논리 퍼즐을 풀기 위해 세 가지 다른 전략을 시도했습니다.

한 번에 다 풀기 (비이분 탐색): "3 개 도우로 가능할까? 아니면 4 개?"라고 숫자를 바꿔가며 매번 처음부터 다시 퍼즐을 풉니다. (조금 비효율적일 수 있음)
이전 기억 활용하기 (증분식 SAT): "3 개 도우로 안 된다면, 그 실패 원인을 기억해 둡니다. 이제 4 개 도우로 시도할 때, 그 실패 원인은 다시 고려하지 않고 바로 다음 단계로 넘어갑니다." 마치 미로 찾기에서 "여기는 막혔다"는 표시를 해두고 다음 시도에 그 표시를 참고하는 것과 같습니다. 이 방법이 회전하지 않는 단순한 문제에서는 가장 강력했습니다.
최적의 답을 한 번에 찾기 (MaxSAT): "최대한 적은 도우를 쓰면서 모든 조건을 만족하는 답"을 한 번에 찾아내려고 노력합니다. 하지만 이 방법은 계산량이 너무 많아서 복잡한 문제에서는 오히려 느려질 수 있었습니다.

4. 실험 결과: 기존 상용 프로그램보다 압도적

저자들은 이 방법을 실제 산업용 소프트웨어 (OR-Tools, CPLEX, Gurobi 등) 와 비교했습니다. 결과는 놀라웠습니다.

성공률: 기존 프로그램들이 "이건 최적이다"라고 확신하며 답을 낸 경우가 1~~7 건이었다면, 이 새로운 방법은 **16~~18 건**이나 확신하며 답을 냈습니다. (약 2~3 배 더 많은 문제를 완벽하게 해결함)
낭비 감소: 해결책을 찾지 못했을 때의 오차 (낭비) 도 기존 프로그램보다 훨씬 적었습니다.
특이점: 회전 (피자를 90 도 돌리는 것) 이 허용된 복잡한 상황에서는, "이전 기억을 활용하는 방법"보다 "매번 새로 시작하는 방법"이 더 잘 작동했습니다. 이는 문제의 복잡도가 변하면 최적의 전략도 달라진다는 것을 보여줍니다.

5. 결론: 왜 이 연구가 중요한가?

이 연구는 **"복잡한 제조 현장의 낭비를 줄이는 데, 논리 퍼즐을 푸는 AI 기술이 기존 거대 소프트웨어보다 더 빠르고 정확할 수 있다"**는 것을 증명했습니다.

간단한 비유: 기존 프로그램은 거대한 도서관에서 모든 책을 다 뒤져 답을 찾으려 했다면, 이 새로운 방법은 **"책의 목차와 색인 (논리 규칙) 을 이용해 필요한 책만精准하게 찾아내는 방법"**입니다.
기대 효과: 이 기술이 실제 공장에 적용되면, 원단이나 금속 판을 더 적게 사면서도 더 많은 제품을 만들 수 있어 비용 절감과 환경 보호에 큰 기여를 할 것입니다.

요약하자면, 이 논문은 **"복잡한 자르기 문제를 논리 퍼즐처럼 변형하여, 기존 슈퍼컴퓨터보다 더 똑똑하고 빠르게 최적의 해답을 찾아냈다"**는 획기적인 연구입니다.

논문 요약: SAT 및 MaxSAT 를 활용한 2 차원 단일 재단 크기 컷팅 스톡 문제 해결

1. 문제 정의 (Problem Definition)

이 논문은 **2 차원 단일 재단 크기 컷팅 스톡 문제 (2D-CSSP, Two-Dimensional Single Stock Size Cutting Stock Problem)**를 다룹니다.

목표: 동일한 크기의 원자재 시트 (Sheet) 에서 여러 개의 직사각형 아이템을 잘라내어 수요를 충족시키면서, 사용하는 시트의 수를 최소화하는 것입니다.
특징: 각 아이템 유형 $t$ 는 수요량 $d_t \ge 1$ 을 가지며, 이는 2 차원 배낭 문제 (2D-BPP) 의 일반화된 형태입니다.
난이도: 수요량이 증가함에 따라 아이템의 복사본 수가 기하급수적으로 늘어나고, 이로 인해 탐색 공간이 폭발적으로 커지는 '조합적 폭발 (Combinatorial Blow-up)'이 발생합니다. 기존 최적화 기법들은 대규모 수요를 처리할 때 확장성 (Scalability) 이 떨어지거나 최적성 증명 (Optimality Certificate) 을 제공하지 못하는 한계가 있습니다.

2. 방법론 (Methodology)

저자들은 2D-CSSP 를 해결하기 위해 **명시적 논리 기반 (Declarative Logic-based)**인 SAT (Boolean Satisfiability) 및 MaxSAT 프레임워크를 제안했습니다.

SAT 인코딩 (SAT Encoding):
- 수요 기반 복사 (Demand Expansion): 각 아이템 유형을 수요량만큼 복사하여 개별 인스턴스로 취급합니다.
- 조건부 비중첩 제약 (Conditional Non-overlap Constraints): 모든 아이템 쌍에 대해 무조건적으로 비중첩을 강제하는 대신, 두 복사본이 동일한 시트에 할당된 경우에만 비중첩 제약이 활성화되도록 설계했습니다. 이는 시트 할당 변수를 사용하여 논리적으로 제어합니다.
- 순서 인코딩 (Order Encoding): 좌표 변수를 부울 변수의 선형 개수로 표현하여 인코딩의 크기를 효율적으로 유지합니다.
대칭성 깨기 (Symmetry Breaking):
- 대형 아이템 제약: 특정 시트에 들어갈 수 없는 조합의 아이템은 배제합니다.
- 동일 크기 아이템 순서: 같은 유형의 아이템 복사본들 간의 순열 대칭성을 깨기 위해 특정 순서를 강제합니다.
- 비실현 가능 방향 제거 (Infeasible-Orientation Elimination): 시트 크기에 맞지 않는 회전 방향은 고정 변수 (Unit Clause) 를 통해 즉시 제거합니다. 이는 정사각형 아이템뿐만 아니라 일반적인 경우에도 적용됩니다.
- 시트 순서: 시트 사용 순서를 인덱스 순으로 고정하여 $k!$ 개의 시트 재레이블링 대칭성을 제거합니다.
해결 전략 (Solving Approaches):
1. 비증분적 SAT (Non-incremental SAT) + 이진 탐색: 각 시트 수 $k$ 에 대해 새로운 SAT 공식을 생성하여 이진 탐색을 수행합니다.
2. 증분적 SAT (Incremental SAT) + 이진 탐색: 한 번에 최대 시트 수에 대한 공식을 생성한 후, 가설 (Assumptions) 을 통해 사용하지 않는 시트를 비활성화합니다. 이전 단계에서 학습된 충돌 절 (Conflict Clauses) 을 재사용하여 탐색 공간을 줄입니다.
3. 가중치 부분 MaxSAT (Weighted Partial MaxSAT): 시트 사용 변수를 소프트 절로 변환하여 한 번의 호출로 최적의 시트 수를 찾습니다.

3. 주요 기여 (Key Contributions)

최초의 2D-CSSP SAT 인코딩: 수요량에 따른 아이템 복제, 시트 할당 변수, 조건부 비중첩 제어를 포함하는 최초의 SAT 기반 프레임워크를 제안했습니다.
일반화된 회전 제거 규칙: 정사각형 아이템에 국한되었던 기존 규칙을 확장하여, 시트 크기에 맞지 않는 회전 방향을 자동으로 고정하는 규칙을 도입했습니다.
대규모 비교 연구: Cui-Zhao 벤치마크 (30 개 인스턴스) 에서 OR-Tools, CPLEX, Gurobi 와 같은 상용 솔버 및 기존 SAT 접근법 (2D-BPP) 과의 비교를 통해, 증분적 SAT 와 비증분적 SAT 의 성능 순위가 회전 (Rotation) 여부에 따라 반전된다는 사실을 발견했습니다.
성능 입증: 제안된 SAT 기반 접근법이 기존 상용 솔버보다 훨씬 많은 인스턴스에서 최적성을 증명하고, 최적성 간격 (Optimality Gap) 을 크게 줄였습니다.

4. 실험 결과 (Results)

Cui-Zhao 벤치마크 (30 개 인스턴스, 7~~21 개 아이템 유형, 수요 1~~45) 에서 1,800 초 시간 제한 하에 실험을 수행했습니다.

회전 금지 (No Rotation) 설정:
- **증분적 SAT (CSP INC SB)**가 가장 우수했습니다. 16 개 인스턴스에서 최적성을 증명 (상용 솔버 대비 2 배 이상) 하고, 평균 간격 9.71% 를 기록했습니다.
- 이유: 동일한 아이템 유형의 복사본들은 기하학적으로 동일한 하위 문제를 생성하므로, 이전 단계에서 학습된 충돌 절이 다음 단계에서도 유효하게 작용하여 증분적 접근이 효율적입니다.
회전 허용 (With Rotation) 설정:
- **비증분적 SAT (CSP R)**가 가장 우수했습니다. 18 개 인스턴스에서 최적성을 증명하고, 평균 간격 3.24% 를 기록했습니다.
- 이유: 회전 허용은 변수 수를 약 26% 증가시키고 절 (Clause) 수를 약 3 배로 증가시켜 증분적 접근의 이점 (절 재사용) 을 상쇄하고 오히려 불필요한 절이 학습 데이터베이스를 오염시킵니다. 따라서 매 단계마다 새로운 상태를 시작하는 비증분적 방식이 더 효과적입니다.
상용 솔버 비교:
- SAT 기반 접근법: 회전 유무에 관계없이 16~18 개의 인스턴스에서 최적성을 증명했습니다.
- 상용 솔버 (OR-Tools, CPLEX, Gurobi): 최적성을 증명한 인스턴스 수는 1~7 개에 불과했습니다. 특히 OR-Tools 는 해를 찾는 능력은 뛰어나지만 (BKS 일치), 최적성을 증명하는 데는 한계가 있었습니다.
- 성능 차이: SAT 기반 방법은 상용 솔버보다 최적성 증명 인스턴스 수를 2~3 배 더 많이 달성했으며, 최적성 간격도 현저히 낮았습니다.

5. 의의 및 결론 (Significance & Conclusion)

새로운 패러다임: 컷팅 스톡 문제 (Cutting Stock) 에 SAT/MaxSAT 기반의 논리 추론을 성공적으로 적용하여, 기존 MIP(혼합 정수 계획법) 나 CP(제약 프로그래밍) 기반 솔버가 도달하지 못했던 최적성 증명 영역을 개척했습니다.
문제 구조에 따른 전략 선택: 문제의 복잡도 (회전 유무) 에 따라 증분적 SAT 와 비증분적 SAT 중 적절한 전략을 선택해야 함을 실증했습니다. 이는 단일 아이템 배낭 문제 (2D-BPP) 와는 다른 2D-CSSP 고유의 특성입니다.
실용성: 제조업 (금속 판재, 유리, 직물 등) 에서 발생하는 대규모 재단 문제의 최적 해를 구하고 그 최적성을 수학적으로 증명할 수 있는 강력한 도구를 제공했습니다.

이 연구는 명제 논리 기반 솔버가 복잡한 기하학적 최적화 문제에서 상용 솔버를 능가할 수 있음을 보여주었으며, 향후 이종 재단 크기 문제 (Heterogeneous Stock Size) 로의 확장 및 컬럼 생성 (Column Generation) 과의 하이브리드화를 위한 기초를 마련했습니다.