방법
문제를 푸는 데 쓰이는 알고리즘·휴리스틱·기하 기본 연산입니다.
- phi-함수 (Phi-functions)
두 부품의 상호작용을 해석적으로 부호화하는 비겹침 모델링 기법.
- 감소 우선 적합 (First-Fit Decreasing)
항목을 큰 순으로 정렬해 첫 번째로 맞는 빈에 넣는 휴리스틱.
- 강화학습 (Reinforcement Learning)
보상 신호로부터 배치·순서 정책을 학습.
- 내부 적합 다각형 (Inner-Fit Polygon)
부품을 원자재 경계 안에 담는 유효 배치 영역을 기술하는 기하 기본 연산.
- 동적 계획법 (Dynamic Programming)
겹치는 부분문제를 표로 저장해 푸는 정확 기법.
- 무적합 다각형 (No-Fit Polygon)
두 부품의 모든 비겹침 상대 배치를 기술하는 기하 기본 연산.
- 민코프스키 합 (Minkowski Sum)
무적합 다각형 계산의 토대가 되는 기하 연산.
- 바텀-레프트-필 (Bottom-Left Fill)
각 부품을 가능한 가장 아래·왼쪽 위치에 떨어뜨리는 구성적 배치 휴리스틱.
- 분기 한정 (Branch and Bound)
한계값으로 부분문제를 가지치기하는 정확 트리 탐색.
- 시뮬레이티드 어닐링 (Simulated Annealing)
확률을 점차 낮춰 가며 더 나쁜 이동도 받아들이는 단일 해 메타휴리스틱.
- 열 생성 (Column Generation)
변수(열)를 필요할 때 생성해 거대한 LP를 푸는 기법.
- 유전 알고리즘 (Genetic Algorithm)
부호화된 해 집단을 탐색하는 개체군 기반 메타휴리스틱.
- 정수 선형 계획법 (Integer Linear Programming)
절단·적재 문제를 정수 변수의 선형 모델로 정식화하는 방법.
- 타부 서치 (Tabu Search)
최근 방문 이동을 기억해 순환을 피하는 지역 탐색.
- 하한 (Lower Bounds)
최적값의 하한을 계산해 정확 탐색을 가지치고 해의 품질을 보증하는 기법.