Abstract
본 논문에서는 순서 의존적 셋업(sequence-dependent setups)을 갖는 Lot-sizing 및 Scheduling 문제를 대상으로, 단일 기간(substructure) 구조를 분석하여 새로운 유효 부등식(valid inequalities)과 확장 정식화(extended formulations)를 제안한다.
구체적으로, 두 가지 새로운 유효 부등식 계열을 도출하고, 이들이 facet을 정의하기 위한 조건을 규명한다. 또한 이러한 부등식들이 다항 시간 내에 분리(separation) 가능함을 보인다.
기존의 확장 정식화들을 소개한 이후, 시간 흐름(time-flow)을 나타내는 의사결정 변수를 활용한 새로운 확장 정식화를 제시하고, 제안한 방법을 포함한 다양한 정식화 및 유효 부등식들의 이론적 강도를 비교한다.
마지막으로, 제안된 부등식과 정식화의 효과를 검증하기 위해 계산 실험을 수행하였다. 실험 결과, 제안한 유효 부등식과 확장 정식화가 선형계획 완화(linear programming relaxation)의 경계를 더욱 타이트하게 만드는 데 기여함을 확인하였다.
1. Introduction
1.1 문제 설명
- 전통적인 capacitated lot-sizing 문제는 주어진 게획 기간동안 각 기간별로 제품의 생산량을 결정하는 문제
- 목표는 제한된 생산 용량과 셋업 요구사항 등의 제약을 만족하면서, 시간에 따라 변화하는 수요를 최소 비용으로 충족하는 것
- 이 문제는 다양한 현실적 특성을 반영해 여러 변형이 존재 → 그중 중요한 확장 중 하나가 sequence-dependent setup을 고려하는 것 → 이전에 생산한 품목과 이후에 생산할 품목의 조합에 따라 셋업 비용과 시간이 달라짐 의미
- sequence-dependent setup이 존재하면, 단순히 생산량만 결정하는 것이 아니라 생산순서(sequene)까지 함께 결정해야 함. → 생산순서는 총 비용뿐 아니라 사용 가능한 생산 용량에도 영향을 미치기 때문.
- 이러한 특성을 고려한 LSP-SQ(순서 의존적 셋업을 갖는 로트사이징 및 스케줄링 문제)를 다룸.
1.2 Literature Review
- LSP-SQ에 대한 연구는 실제 산업 문제를 다루는 연구와 일반적 문제를 효율적으로 해결하는 알고리즘 연구로 나뉨.
- 그중에서도 polyhedral 연구에 초점을 맞춤.
1) 기존 연구: single-item 중심
- 기존 polyheral 연구는 대부분 단일품목 구조 중심
- 대표적으로
- 단일 품목 무제한 로트사이징 문제(ULSP)의 convex hull을 완전히 기술한 연구
- facility location, shortest path 기반의 확장 정식화
- capacity가 있는 경우의 facet-defining inequality 연구
- 이러한 결과들은 이후 multi-item 또는 capacity variation 문제로 확장됨.
2) 한계: sequence-dependent setup 미반영
- 하지만 기존연구들은 대부분 단일 품목 구조에 집중하거나 / sequence-dependent setup을 고려 x
- 예를 들어
- single-period 연구는 존재하지만 setup이 sequence-independent인 경우만 다룸.
- 일부 연구는 multi-period 확장도 했지만 setup time = 0 가정
- 따라서 LSP-SQ에는 직접 적용 불가
3) 본 논문의 핵심 차별점
- sequence-dependent setup을 포함한 single-period substructure 분석
- 기존: single-item / 단순 구조
- 본 논문: multi-item + suquence 구조
4) Routing 문제(CVRP)와의 연결
- LSP-SQ는 구조적으로 다음과 유사함:
- 생산할 item 선택 ↔ 방문할 고객 선택
- 생산 순서 결정 ↔ 방문 순서 결정
- 그래서 CVRP(차량 경로 문제)의 valid inequality, formulation과 밀접 관련
- 하지만 차이점은
- CVRP: 방문 여부만 결정
- LSP-SQ → 생산량(x)까지 결정해야 함.
- 따라서 CVRP 결과만으로 부족
5) 기존 formulation 연구
- 기존 LSP-SQ formulation 종류
- GSEC 기반 (subtour elimination)
- pattern-based (변수 많음)
- single/multi-commodity flow (실험적으로는 성능 가장 good)
- 하지만 이론적 비교는 부족
6) 최신 연구와 본 논문의 연결
- 최근 연구: time-flow formulation 등장 (시간 흐름 기반 모델)
- 본 논문:
- 새로운 time-flow formulation 제안
- 기존 방법들과 이론+계산적 비교
1.3 Mathematical formulation of LSP-SQ
- 본 절에서는 big bucket 모델 기반의 LSP-SQ를 수학적으로 정의함.
1) Sets, Parameters, Variables
2) Objective Function, Constraints
- (1b) 수요 균형식
- 생산 + 이전 재고 = 수요 + 현재 재고
- (1c) 생산 용량 제한
- 생산시간 + 셋업시간 ≤ 총 용량
- (1d) 생산-셋업 연결
- 산하려면 setup이 있어야 함.
- (1e) 기간 간 연결(carry-over)
- 이전 기간 마지막 → 다음 기간 시작
- (1f) flow conservation
- 들어오는 edge = 나가는 edge = 생산 여부
- (1g) Subtour 제거
- 0번 노드 없이 cycle 금지
3) Big Bucket 모델 핵심 개념
- 한 기간 내에서 여러 제품 생산 가능 / 순서를 하나의 cycle로 표현
- 예시
- t 기간: 1 → 2 → 4
- t+1 기간: 4 → 3 → 2 → 5
- 각각의 cycle형태 그래프로 표현
4) 그래프 표현
- 노드 = 제품
- 간선 = setup (i → j)
- 정의:
- E(S): 내부 간선
- δ+(S): 나가는 간선
- δ−(S): 들어오는 간선
5) Subtour 제거 (GSEC)
- 외부에서 들어오는 간선 없이 생산 불가
2. Single-period substructure
LSP-SQ의 single-period 구조와 그 성질을 다룸.
1) 핵심 아이디어
- 기존 문제는 multi-period 구조(기간 간 연결 존재)
- 여기서는 기간 간 제약을 제거(relax)해서 문제를 각 기간별로 분해
- 즉, 전체 문제 → 여러 개의 single-period 문제로 분해
2) 왜 single-period를 보는지
- polyhedral 분석을 위해 구조 단순화
3) 기존 연구와의 차이
- sequence-independent setup 기준 → sequence-dependent setup 포함한 single-period 분석
4) 새로운 변수 도입
- single-period에서는 기간 index t를 제거하고 대신:
- si−: shortage (부족량)
- si+: surplus (초과량)
- 이유
- 기간 간 연결이 없어지면 수요를 반드시 맞출 필요 x
- 그래서 feasibility 보장용 변수 추가
5) Single-period 문제
- (3a) 목적함수
- min 재고 + 부족 + 생산 + 셋업 비용
- multi-period와 동일 구조지만 기간 index는 없음.
- min 재고 + 부족 + 생산 + 셋업 비용
- (3b) 수요 균형
- (3c) 용량 제한
- (3d) 생산 여부
- (3e) 시작 노드 조건
- 하나의 시작점 존재
- (3f) flow balance
- 들어오는 간선 = 나가는 간선
- (3g) Subtour 제거 (GSEC)
- 0 없이 cycle 생성 방지
- (3h) Solution set 정의
- 이 집합의 convex hull 분석이 핵심 목표
6) 추가 설정
- 생산 상한 ui
- 각 item마다 생산 최대량
- 필요없으면 ui=K
- 두 경우 구분
- 일반: X
- ui = K:X0
- 두 경우 구분
- 중요한 simplification
- ai=1로 변환 가능
- 이유
- 변수 스케일링으로 동일 문제 변환 가능(분석 단순화 목적)
- 추가 가정(현실적 + 분석 용이성)
- 0<stij≤K
- ui≤K
2.1 Basic polyhedral properties
single-period 문제의 convex hull 구조를 분석함.
1) 왜 분석?
- 목표
- 좋은 valide inequality 만들기 위해
- LP relaxation을 강하게 만들기 위해
- 핵심 개념
- facet (facet-defining inequality) → convex hull의 “경계면”
- feasible region의 자유도 (dimension)
- 이후 facet 증명할 때 기준이 됨.
- 이 제약은 facet-defining inequality
- capacity constraint는 단순 제약이 아니라 convex hull의 “가장 중요한 경계” 중 하나
- item i 하나 생산할 때 setup 시간 때문에 실제 최대 생산량이 제한됨.
- 이 조건이 있어야 constraint가 "tight"해짐.
- setup item 고려해서 upper bound를 더 줄임.
- 생산 가능 시간 = 전체 용량 - setup 시간
- 그래서 단순히 Kyi가 아니라 setup 만큼 빼줘야 정확함.
핵심; constraint를 얼마나 "tight"하게 쓰느냐가 모델 성능을 결정
3. New valid inequalities
3.1. S-STAR inequality
X에 대한 새로운 유효 부등식(valid inequalities) 계열을 제안하고, 그 facet 조건을 규명
1) 정의
- 임의의 제품 집합 S⊆I에 대해, 첫 번째 부등식은 다음과 같이 정의:
- 좌변 항들이 SSS를 중심으로 별(star) 형태를 이루기 때문에 S-STAR 부등식이라 불림.
2) 구조 해석
- 좌변(S와 관련된 전체 작업량)
- S에 속한 item들 생산량
- S 내부 + 외부와 연결된 setup 시간
- 우변(S가 외부와 연결된 정도)
- S로 들어오는 edge 수 x capacity K
3) 핵심
- invalid cycle 제거
- 0번 노드 없이 cycle 생기는 경우
- 외부 연결 없음 → RHS = 0
- 하지만 내부 setup 존재 → LHS > 0 (모순 → ineuqality 성립x)
- 0번 노드 없이 cycle 생기는 경우
- 결론: S-STAR inequality 하나로 GSEC 역할 가능
- 주어진 S⊆에 대해, S-STAR 부등식은 X에 대해 유효함.
또한 이 부등식들은 0번 노드를 포함하지 않는 모든 사이클을 제거하기에 충분함. - S-STAR는 valid inequality
- 모든 invalid cycle 제거 가능
- 기존에는 GSEC가 필요했지만 → 이제는 S-STAR로 대체 가능
4) 핵심 구조 그림
- 어두운 노드는 S에 속한 제품들을 나타낸다.
- 집합 E(S)에 속하는 간선은 점선으로, δ(S)에 속하는 간선은 실선으로 표시
- 두 제품 간의 모든 가능한 setup을 표현하기 위해 간선은 양방향으로 표시
5) CVRP와의 관계
- S-STAR 부등식은 CVRP에서의 generalized large multistar (GLM) 부등식과 밀접한 관련이 있음.
- 두 부등식의 관계를 보다 명확히 하기 위해, 다음과 같은 일반화된 형태의 부등식을 고려:
- CVRP에서는:
-
- xi=diyi (이산 값)
- setup time 없음 (stij=0)
-
- 반면, 일반식에서 일부 항(xi,xj) 제거하면 S-STAR 부등식 얻을 수 있음.
- 즉, S-STAR와 GLM은 동일한 구조에서 유도되지만
- GLM: 수요 기반 (CVRP)
- S-STAR: 생산량 기반 (LSP-SQ) 이라는 차이가 있음.
- GLM과 달리, S-STAR inequality는 facet 조건 명확히 제시 가능
- 특히, 각 제품의 상한이 없는 경우(ui=K)
- S-STAR 부등식은 conv(X)의 facet 정의
- 특히, 각 제품의 상한이 없는 경우(ui=K)
S-STAR는 subset S의 생산과 setup을 외부 연결과 연동시키는 강력한 제약이며,
invalid cycle 제거와 facet 특성을 동시에 만족한다.
3.1.1. Separation of S-STAR inequality
- S-STAR 부등식은 모든 부분집합 S⊆IS ⊆ I에 대해 정의되므로, 그 개수는 지수적으로 많음.
- 따라서 초기 모델에 모든 부등식을 포함시키는 것은 비현실적
- 대신, 이 부등식들은 cutting plane 방식으로 사용
- 즉, 현재의 분수 해(fractional solution)가 주어졌을 때
이를 위반하는 부등식을 찾아 동적으로 추가
- 즉, 현재의 분수 해(fractional solution)가 주어졌을 때
1) Separation 문제 정의
- 주어진 분수 해 (xˉ,sˉ+,sˉ−,yˉ,zˉ)에 대해,
다음 조건을 만족하는 부분집합 N⊆I을 찾는 것이 목표:
- 즉, S-STAR inequality 위반하는 집합 N 찾는 문제
2) IP 문제로 변환
- 이 separation 문제를 정수계획으로 표현하기 위해 다음 변수를 정의한다:
- pi=1: item 가 N에 포함됨.
- qij=1: 간선 (i,j)가 δ+(N)에 포함됨.
- 또한 다음 파라미터를 정의:
3) Separation 문제 (SEP-S-STAR)
- 이 문제를 풀면:
- pi=1인 item들의 집합 N을 얻음.
- 만약 최적값 >0 이면, S-STAR 부등식 위반됨. → 해당 부등식 추가
- 최적값 ≤ 0이면 → 위반 x
- 계산복잡도
- cutting plane 과정에서 반복적으로 풀려야 하므로 계산 효율성이 매우 중요함.
- 다항시간(polynomial time)에 해결 가능함.
- 이유
- qij의 목적함수 계수는 음수
- 가능한 한 qij를 작게 만드는 것이 최적
- 그래서 qij = pi - pj로 설정 가능
- 이렇게 하면
- 일부 제약은 자동 만족
- 남는 구조는 totally unimodular 행렬
- 결과
- LP relaxation만 풀어도 정수해 보장하므로
- polynomial time 해결 가능
3.2. U-STAR inequality
- 앞에서 제시한 S-STAR 부등식은 각 item의 생산량 상한이 없는 경우(ui=K)에 facet을 정의함.
- 반면, 각 item별 상한이 존재하는 경우에는 다음과 같은 새로운 부등식이 유용함.
- LHS
- S 내부 생산량
- 내부 setup에 대해 penalty(λ) 차감
- 실제 가능 생산량 더 보수적 계산
- RHS
- 외부에서 들어오는 flow × uj
- 외부 연결을 통해 허용되는 생산량
1) S-STAR: capacity K 기준
2) U-STAR: item별 upper bound ui 기준
즉, “capacity 중심 제약 → item upper bound 중심 제약”
- 다음 조건이 만족되면 U-STAR 부등식은 conv(X)의 facet이 됨.
- 조건1: item 하나 + setup 포함해도 capacity 안 넘음
- 조건2: 두 item이 capacity를 꽉 채우는 상황
- 이 두 조건이 있어야 constraint가 "tight"해짐.
- 만약 ui=K이면
- 조건 깨짐.
- U-STAR 약해짐.
- S-STAR에 의해 지배됨.
| 상황 | 더 좋은 inequality |
| ui = K | S-STAR |
| ui < K | U-STAR |
U-STAR는 item별 생산 한계를 반영해서 더 타이트하게 만든 inequality (각 제품 생산 한도까지 고려)
S-STAR는 전체 공장 capacity 기준
현실 문제에서는 대부분 ui<K
∴ U-STAR가 실제 문제에서 더 중요할 수 있음.
<핵심 비교>
| 구분 | S-STAR | U-STAR |
| 기준 | capacity K | upper bound u |
| 상황 | bound 없음. | bound 존재 |
| 강도 | 일반적 | 특정 상황에서 더 강함. |
3.2.1. Separation of U-STAR inequality
- S-STAR와 마찬가지로, U-STAR 부등식도 모든 부분집합 S⊆I에 대해 정의되므로 그 개수는 지수적으로 많다.
- 따라서 separation 문제를 통해 위반된 부등식을 찾아야 함.
1) 문제 정의
- 주어진 분수 해 (xˉ,sˉ+,sˉ−,yˉ,zˉ)에 대해, 다음 조건을 만족하는 집합 N⊆I을 찾음:
2) IP 변환
- 다음 변수 정의:
- pi=1: item i가 N에 포함됨.
- : 간선 (i,j)가 E(N)에 포함됨.
3) SEP-U-STAR
- 변수 qij의 목적함수 계수는 0 이하(음수 또는 0)
- 또한 (SEP-U-STAR)는 최소화 문제이므로, 최적해에서는 의 값을 가능한 크게 만드는 방향이 됨.
- 그래서:
- 제약 pi+pj−1≤q만 남기고 나머지는 제거 가능
- 남은 행렬 totally unimodular
- 결과
- LP relaxation으로 해결 가능
- 즉, polynomial time
4) Figure3 해석
- 생산 순서를 흐름 감소 과정으로 모델링한 것
4. Extended formulations
생산 순서를 모델링하고 유효한 cycle을 보장하기 위한 확장 정식화(extended formulations)를 소개
- 기존: GSEC 같은 제약으로 cycle 제거
- 이 논문: 새로운 변수 추가해서 구조 자체로 해결
4.1. Single-commodity flow formulations
- single-commodity flow formulation은 원래 Gavish & Graves가 외판원 문제(TSP)를 위해 제안한 방식
- 이후 다양한 routing 문제에 활용
- 핵심 아이디어
- 하나의 “commodity(흐름)”를 정의해서 생산 순서를 표현
- 변수 정의
- fij ( (i,j)∈A0)
- 간선 (i → j)를 따라 흐르는 commodity 양
- 제약식
- (10a) 시작 흐름
- 생산하는 item 수만큼 node0에서 출발
- (10b) flow balance
- i 생산하면 flow 1 감소
- 생산 안하면 변화 x
- (10c) 흐름-간선 연결
- 간선이 선택되어야(flow 가능)
- 선택되지 않으면 flow = 0
- (10a) 시작 흐름
- SCF1 정의
- GSEC 대신 (10) 제약을 넣은 모델
- 구성
- 기존 제약 (3b~3f, 3h, 3i0
- flow 제약(10)
- SCF2 (강화버전)
- 더 강한 formulation
- 기존 (10c) 대신 다음 tighter bound 사용
- SCF1, SCF2 둘 다 0번 노드 없는 cycle 자동 제거
- 성능
- SCF1: 가장 약함.
- SCF2: 개선됨.
- GSEC: 가장 강함.
- why?
- SCF1: loose bound
- SCF2: tighter bound
- GSEC: 모든 subset 직접 제약
- multi-commodity는 각 item별로 ‘아직 남았는지’를 추적하는 흐름 모델
4.2. Multi-commodity flow formulations
- multi-commodity flow formulation은 각 제품(item)을 하나의 commodity(흐름)로 간주하여 생산 순서를 모델링하는 방법
- 변수 정의
- 제약식
- (12a) 시작 조건
- 시작할 때 생산해야 하는 item만 flow 존재
- (12b) flow conservation
- 시작점(0)에서 생성
- item k에서 소멸
- 즉, item k가 k에서 처리됨.
- (12c) 연결 제약
- edge 선택되어야 flow 가능
- (12d) binary
- item k가 아직 생산되지 않았으면 1
- item k에 도달하면 flow 사라짐.
이 모델이 하는 일: 모든 item k에 대해 언제 생산되는지 추적함.
→ 순서 구조 매우 정확하게 표현
이 formulation은 GSEC 없이도 subtour 제거 가능 (∵각 commodity가 반드시 0 → k 경로를 가야 함.)
- z(⋅) 의미: LP relaxation optimal value (하한값)
- MILP 풀기 전 LP로 풀었을 때의 값
- 클수록 더 좋음. (더 tight)
- 오른쪽으로 갈수록 모델이 강해짐.
- 좋은 모델일수록 LP relaxation 값이 커진다 → 탐색 효율 증가
4.3. Time-flow formulations
- 앞서 본:
- SCF (single flow) → 약함.
- MCF (multi flow) → 강하지만 너무 큼.
- Time-flow formulation (시간 기반 흐름 모델) 등장
- single-commodity flow formulation과 유사하지만,
- commodity(물량) 대신 시간의 흐름(flow of time)을 표현
- 변수 정의 wij
- item i → j로 넘어갈 때 남아 있는 용량(remaining capacity)
- 제약 구조
- (17a) Time-flow balance
- 들어온 용량에서 setup 시간과 생산량 빼면 나가는 용량
- (17b) Upper bound
- time-flow 변수는 0 이상이고, 선택된 간선에 대해 최대 capacity K를 넘지 않음.
- (17a) Time-flow balance
- flow가 이동할수록 남은 capacity가 점점 감소
- commodity-flow는 순서 정보만 있지만, time-flow는 순서+생산량까지 동시 반영 가능
- 그래서 LSP-SQ에 매우 적하
- TF1 정의
- 기존 (3g) 제거하고 (17) 넣으면 TF1 모델
- 구성
- (3b)~(3f), (3h), (3i)
- (17)
- TF2 (강화버전)
- (17b) 대신 더 강한 bound 사용
- 시작은 항상 full capacity
- 최소 setup 시간 반영
- TF2를 원래 변수 공간으로 projection하면 S-STAR inequality가 됨.
- TF2는 S-STAR를 “내장”하고 있는 모델
5. Computational experiments
5.1. Experiment settings
- 다양한 formulation과 valid inequality들의 성능을 비교함.
- 특히, LP relaxation bound와 계산 시간 측면에서의 차이를 분석
- 실험에서는 다음과 같은 formulation들이 비교:
- SCF1, SCF2
- MCF
- TF1, TF2
- 기본 모델
- S-STAR 추가
- U-STAR 추가
- 결과 해석 방식
- LP relaxation bound
- 모델이 얼마나 tight한지
- 값이 클수록 good
- optimal 값에 가까울수록 good
- 계산 시간
- 실제 문제 푸는 데 걸리는 시간
- optimality gap
- 제한 시간 내에서 얼마나 optimal에 근접했는지
- LP relaxation bound
5.1.1. Single-period instances
다양한 난이도와 구조를 만들기 위해 파라미터를 조합한 실험 데이터 생성 방식
5.1.2. Multi-period instances
multi-period에서는 시간에 따른 생산·재고·부족 비용 trade-off를 반영한 더 현실적인 실험 설정
1) Single-period vs Multi-period 차이
| 구분 | Single-period | Multi-period |
| 구조 | 한 기간 | 여러 기간 |
| 생산 결정 | 한 번 | 시점별 결정 |
| 핵심 | sequencing | lot-sizing + sequencing |
2) 공통 파라미터
- : 제품 수 → {5, 15, 25, (35)}
- : capacity 압박 → {0.6, 0.8, 1}
- ↓ → 더 빡빡 → 문제 어려움.
- : setup 영향 → {50, 100}
- ↑ → sequencing 중요해짐.
- : upper bound 여부 → {0, 1}
- 0 → S-STAR 중요
- 1 → U-STAR 중요
3) single-period 특징
- 목적: 구조 비교 (formulation, inequality 효과 확인)
- 설정
- 수요: U[40,60]
- 생산비용: -1 (무조건 생산 유도)
- setup time: U[0.05K,0.1K]
- capacity:
- 핵심 특징
- 생산 안할 이유x
- sequence가 핵심
- 데이터 규모
- 4800개 인스턴스
4) Multi-period 특징
- 목적
- 현실적 lot-sizing + timing 문제 ㅏㄴ영
- 설정
- 생산비용: +1
- 재고비용: U[2,10]
- 백로그비용: U[10,50]
- 핵심 특징
- 언제 생산할지 중요
- 재고 vs 부족 trade-off 존재
- 데이터 규모
- 1080개 인스턴스
5.2. Experiment results on single-period instances
본 절에서는 다양한 formulation과 valid inequality의 성능을 비교함.
특히, 각 모델의 LP relaxation bound와 계산 시간을 중심으로 분석함.
실험에서는 다음과 같은 formulation들이 비교됨:
- SCF1, SCF2
- MCF
- TF1, TF2
또한 각 formulation에 대해,
- 기본 모델
- S-STAR 부등식 추가
- U-STAR 부등식 추가
를 포함한 여러 조합을 고려함.
1) 평가 기준
각 모델은 다음 기준에 따라 평가:
- LP relaxation bound: 모델의 이론적 강도 (값이 클수록 좋음)
- 계산 시간: 문제 해결에 소요되는 시간
- optimality gap: 제한 시간 내 최적해와의 차이
2) 전체적인 경향
- S-STAR 부등식
- 대부분의 formulation에서 LP relaxation bound가 유의하게 개선
- 특히, SCF와 같이 상대적으로 약한 formulation에서 효과가 더 크게 나타남.
- U-STAR 부등식
- S-STAR에 비해 추가적 개선을 제공하지만, 그 효과는 모든 경우에 동일하게 나타나지 x
- 특히, 각 제품에 대한 생산 상한이 존재하는 경우()에 더 의미 있는 개선을 보임.
- formulation 간 비교
- 전반적 강도: SCF < TF < MCF
- Time-flow formulation 특징
- SCF보다 더 강한 bound 제공 + MCF에 비해 계산 부담이 훨 작음.
- 따라서, 성능과 계산 효율 사이 좋은 균형을 제공하는 모델임.
- formulation과 inequality의 관계
- S-STAR 부등식을 추가하면 formulation 간 성능 차이가 줄어드는 경향이 관찰됨.
- 상대적으로 약한 formulation이라도 S-STAR를 포함하면 성능이 크게 개선됨.
- 정리
- S-STAR 부등식은 모든 formulation에서 중요한 역할
- U-STAR 부등식은 특정 조건에서 추가적인 개선을 제공
- Time-flow formulation은 성능과 계산 효율 측면에서 균형 잡힌 선택
- Table 2
- LP gap ↓ = 더 좋은 모델 (tight)
- TF가 SCF/MCF보다 훨 좋음. (gap 작아서)
- Valid inequalities: S-STAR 효과 엄청 큼.
- S-STAR ≈ TF2 수준으로 성능 개선
- β=1일 때 U-STAR가 더 좋음.
- U-STAR는 upper bound 있을 때만 의미 o
| β | S-STAR | U-STAR |
| 0 | 29.44 | 33.20 |
| 1 | 13.47 | 12.65 |
- Table 3
- 높을수록 좋음. (optimal에 가까움)
- TF = S-STAR ≈ 거의 최적 수준
- SCF는 거의 못 품.
- Table 4
- 얼마나 자주 좋은 해가 나오는지
- TF / S-STAR가 안정적으로 좋은 성능
1. S-STAR 효과
모든 모델 성능을 크게 개선 (가장 중요)
2. TF 최고 밸런스
MCF만큼 강하면서 훨씬 빠름
3. U-STAR 조건부
β=1일 때만 의미 있음
- Table 5
- 모델이 얼마나 무거운지
- MCF는 매우 크고, TF는 작음.
- variables: 변수 개수, constraints: 제약식 개수 → 많을수록 계산 slow
- 기준 모델(값 1.00)에 비해 MCF는 변수 거의 10배 많고 MCF는 제약도 18~19배 많음.
- SCF/TF: 작음 → 빠름
- MCF: 매우 큼 → 느림
- 강하지만 비현실적..
- Table 6
- 시간 낮을수록 좋은 모델
- SCF < TF < MCF
- SCF가 가장 빠름.
- MCF는 규모 커지면 거의 못 씀.
- TF는 빠르고, MCF는 너무 느림.
- Table 7
- cutting plane에서 몇 개 inequality 추가했냐
- S-STAR > U-STAR > GSEC
- S-STAR: 가장 많이 violation 발생 → 가장 중요한 제약
- 문제 커질수록 S-STAR 중요성 증가
- β=1일 때 U-STAR 더 많이 쓰임.
- Table 8
- 모델이 얼마나 강한지 (LP bound quality)
- single-period보다 전체적으로 훨씬 높음 → multi-period가 더 “tight”
- TF가 가장 좋음.
- multi-period에서도 TF가 가장 좋은 formulation
- Table 9
- 좋은 성능(높은 LP strength)이 얼마나 자주 나오냐
- TF + S-STAR가 압도적으로 좋음.
- Table 10
- 얼마나 무거운 모델인지
- multi-period에서도 MCF는 비효율적
- Table 11
- 시간 ↓ = 좋은 모델
- TF는 빠르고, MCF는 매우 비효율적
- Table 12
- cutting plane에서 몇 개 constraint 추가했냐
- S-STAR + U-STAR가 실제로 많이 쓰이는 핵심 constraint
5.3. Experiment results on multi-period instances
- multi-period에서는 대부분 모델이 강하지만, time-flow와 S-STAR 조합이 가장 안정적으로 최고의 성능을 제공함.
6. Conclusion
본 연구에서는 순서 의존적 셋업(sequence-dependent setups)을 갖는 로트사이징 및 스케줄링 문제(LSP-SQ)와 그 단일 기간 구조를 다룸.
우리는 기존 방법들과 비교하여 LP relaxation bound를 더욱 타이트하게 만드는 새로운 유효 부등식(valid inequalities)과 확장 정식화(extended formulations)를 제안하였다. 또한 제안된 부등식들의 이론적 강도를 분석하고, facet을 정의하기 위한 조건을 규명하였으며, 이들이 다항 시간 내에 분리(separation) 가능함을 보임.
본 연구 결과는 다양한 방식으로 활용: 제안된 유효 부등식은 LSP-SQ를 위한 효율적인 해법 알고리즘을 설계
예를 들어, 기존의 (l, S)-inequality와 함께 활용하여 branch-and-cut 알고리즘을 구성.
특히, 이러한 부등식을 cutting plane으로 사용할 경우,
- 한 번의 반복에서 추가되는 cut의 수
- 탐색 과정에서 cut을 추가하는 빈도
- cut을 추가하는 순서
와 같은 알고리즘적 요소들이 전체 성능에 영향을 미침.
따라서 이러한 요소들을 고려한 추가적인 계산 실험이 향후 연구에서 필요함.
또한, 제안된 time-flow formulation은 실제 산업 문제 해결에도 적용될 수 있음. LSP-SQ는 다양한 산업에서 발생하는 문제로, LP나 MIP 기반의 수리적 접근을 활용한 matheuristic 기법이 널리 사용되고 있음. 이러한 휴리스틱의 성능은 기본이 되는 모델의 tightness에 크게 영향. 동시에, 변수와 제약이 지나치게 많은 모델은 반복적으로 해결해야 하는 과정에서 계산 부담이 커질 수 있음.
따라서 모델의 크기와 강도 사이의 trade-off를 고려할 때, 본 논문에서 제안한 time-flow formulation은 다양한 matheuristic의 성능을 향상시키는 데 유용하게 활용될 수 있음.
*matheuristic: 수학적 프로그래밍(MP) 기법과 메타휴리스틱(Metaheuristics)을 결합한 하이브리드 최적화 알고리즘