Abstract
Robust cover inequality는 robust knapsack problem(RKP)에 대해 잘 알려진 유효 부등식이다. 이를 강화하기 위해, 우리는 lifting을 사용하는데, 이는 lifting problem—RKP의 특수한 경우—을 푸는 과정을 포함한다. 우리는 lifting problem에 대한 upper bound를 활용하는 새로운 lifting 방법을 제안한다. 먼저, 해집합의 분해 성질을 기반으로 RKP에 대해 강하고, 효율적으로 계산 가능하며, 품질이 보장된 upper bound를 제시한다. 이후, 제안한 upper bound를 lifting problem에 적용하여 효율적인 lifting 방법을 구성한다.
1. Introduction
1) 문제 배경
- Binary Knapsack Problem, BKP(이진 배낭 문제)
- MIP에서 자주 등장하는 핵심 구조
- cover inequality 등 다양한 valid inequality 연구
- 현실 문제 → 불확실성 존재
- 데이터가 변동되면 하나의 feasibility/품질 문제 발생 → Robust Optimization 필요
- RKP (Robust Knapsack Problem)
- 각 weight가 구간 내에서 변동
- 동시에 최대 Γ개만 deviation 허용 (Bertsimas-Sim 모델)
2) 기존 연구 흐름
- RKP feasible set은 n+1개의 BKP로 decomposition 가능
- Valid Inequality
- BKP → cover inequality
- RKP → Robust Cover Inequality (RCI)
3) Lifting의 역할
- RCI는 약함 → 강화 필요
- 방법: lifting
- 핵심
- 각 는 lifting problem 풀어서 구함.
- lifting problem = RKP의 특수한 형태
4) 기존 방법의 한계
- Park(2008)
- Polynomial-time lifting
- Joung & Park(2018)
- DP로 속도 개선
- 그래도 문제:
- 계산 복잡도 큼.
- 대규모 RKP에서는 여전히 느림.
lifting problem을 “정확히 풀지 말고” upper bound로 근사하자!
- 새로운 upper bound 제안
- RKP 해집합의 decomposition property 활용
- 특징
- strong (tight)
- efficiently computable
- quality guarantee 있음.
- 특징
- RKP 해집합의 decomposition property 활용
- Lifting heuristic
- 기존: lifting problem exact solve
- 제안: upper bound로 β 계산
- 결과
- 정확하진 않지만(heuristic) 훨씬 빠름.
5) 논문의 기여
- 이론적 기여
- 제안한 upper bound → 기존 LP relaxation보다 더 강함. / optimal의 2배 이내 보장
- 알고리즘 기여
- lifting complexity: O(n^2Γ|C|) → O(n^2|C|)
- 실험 결과
- exact lifting vs heuristic
- cut quality(성능): 거의 동일
- 속도: 훨 빠름.
- exact lifting vs heuristic
robust cover inequality를 강화하는 lifting을, exact solve 대신 strong upper bound로 빠르게 근사하는 방법
2. Decomposition-based upper bound for the RKP
lifting heuristic은 lifting coefficient를 결정하기 위해 lifting problem의 upper bound를 활용한다.
이 upper bound의 강도는 생성되는 LRCI의 품질에 큰 영향을 미치며, 이는 Section 3에서 자세히 설명한다.
이 절에서는 RKP를 위한 decomposition 기반 upper bound를 소개한다. 이 upper bound는 lifting problem이 RKP의 특수한 경우로 표현될 수 있기 때문에, 우리의 lifting heuristic에서 lifting problem의 upper bound로 사용할 수 있다.
또한, 기존 RKP에 대한 MIP 모델들의 LP relaxation bound 및 RKP의 최적 목적함수값과 비교하여,
제안한 upper bound의 강도를 분석한다.
2.1. Decomposition-based upper bound for the RKP
- 먼저, decomposition property 소개
- 각 j∈N, k∈[n+1]에 대해 다음과 같이 정의:
- 각 k∈[n+1]에 대해 Xk의 연속 완화(continuous relaxation)를 Pk라 하자.
- 이때, 각 k∈[n+1]에 대해 다음과 같은 LP 문제를 고려:
- 이 LP 문제는 fractional knapsack problem의 LP relaxation 형태임을 알 수 있음.
- 이제 RKP의 decomposition-based upper bound를 다음과 같이 정의:
- 이는 다음과 같은 이유로 RKP의 유효한 upper bound임.
- 각 zk는 fractional knapsack 문제이므로 Dantzig의 greedy algorithm을 사용하면 O(nlogn) 시간에 계산 가능
- 따라서 모든 zk를 계산하는 데 O(n^2logn)이 필요하고,
그 중 최대값을 찾는 데는 O(n)이 추가되므로 전체 복잡도는 O(n^2logn)
RKP를 n+1개의 fractional knapsack으로 분해하고, 그 중 최대값을 upper bound로 사용
2.2. Analysis for the strength of the decomposition-based upper bound for the RKP
- 분해 기반 upper bound z^DEC의 강도 분석
- RKP는 다음과 같이 집합 표기법으로 표현:
- 함수 f(S)의 submodularity를 기반으로, Joung et al.은 다음과 같은 MIP 모델(MOD 모델)로 재구성:
- 이때, z^MOD를 MOD 모델의 LP relaxation bound라 함.
- 즉, z^DEC는 MOD 모델의 LP relaxation bound보다 더 타이트하거나 동일한 upper bound
- 비교를 통해 z^DEC는 Bertsimass-Sim, Atamtürk의 모델을 포함한 기존 RKP 모델들의 LP relaxation bound보다도 적어도 동일하거나 더 강한 bound임을 알 수 있음.
- 다음으로 z^DEC를 RKP의 최적값 z^OPT와 비교해 그 품질을 분석함.
- 즉, 분해 기반 upper vound는 항상 최적값의 2배 이내로 제한됨.
- 이는 z^DEC가 품질 보장된 upper bound임을 의미함.
- 반면, 기존 MOD 모델의 LP relaxation bound는 최적값과의 차이가 크게 벌어질 수 있음.
- 즉, 기존 LP relaxation bound는 문제 크기 n이 커질수록 임의로 크게 나빠질 수 있음. (큰 intergrality gap)
3. Lifting heuristic using decomposition-based upper bounds of the lifting problems
- exacting lifting 방법은 식 (1)의 lifting coefficient βj들을 순차적으로 계산하며, 이를 위해 lifting problem을 풂.
- 주어진 robust cover C와 N\C의 변수 순서 (σ1,…,σn-|C|) 대해,
각 i∈[n−|C|]에 대해 다음과 같이 정의:
- 각 i에 대해 lifting coefficient βσi는 다음과 같이 결정:
- 여기서
- 위 최적화 문제는 주어진 RCI에 대한 i번째 lifting problem
- 이는 pj ≤ |C|-1을 만족하는 RKP의 특수한 경우
- 또한 일부 변수 값이 고정된 형태이므로, 기존 RKP 모델을 그대로 적용할 수 있음.
Heuristic 접근
- 각 lifting problem을 정확히 푸는 대신, lifting heuristic은 각 문제에 대한 upper bound를 이용해 lifting coefficient를 계산함.
- 즉, 계산 시 zi 대신 해당 문제의 upper bound를 사용함.
- 이후 얻어지는 LRCI는 다음과 같은 특징을 가짐:
- convex hull의 facet을 정의하지 않을 수도 있음. (exact lifting과 달리)
- upper bound가 약하면 coefficient가 작아져 inequality가 약해질 수 있음.
제안 방법
- 본 논문의 lifting heuristic은 decomposition-based upper bound 활용함.
- 해당 upper bound는 품질 보장이 있음.
- 기존 MIP 기반 LP relaxation보다 더 타이트함.
- 따라서, exact lifting 없이도 유사한 품질의 coefficient를 얻을 수 있음.
Heuristic으로 생성된 LRCI
- 주어진 robust cover C에 대해, lifting heuristic으로 얻은 LRCI는 다음과 같음:
- 여기서 lifting coefficient는 다음과 같이 정의:
- 여기서 zi^DEC는 해당 lifting problem의 decomposition-based upper bound
- 이는 다음과 같이 표현:
floor 사용하는 이유
- ⌊zi^DEC⌋ 역시 유효한 upper bound
- 정수 계수 유지
- 더 타이트한 inequality 생성 가능
계산 복잡도
- Proposition 1에 의해 zi^DEC는 O(n^2logn)에 계산 가능함.
- 따라서 전체 LRCI 생성은 O(n^2logn)이 됨.
추가 최적화
- 계산을 더 줄이기 위해 다음을 활용:
- fractional knapsack 구조 활용
- 각 inner problem은 greedy로 해결
- 탐색 개수 제한
- 최대 |C|-1개의 아이템만 확인하면 충분
- 이유
- 그 이상이면 zi^DEC → β^σi=0
- 정렬 리스트 업데이트
- 이전 단계 결과 재사용
- 새 변수만 삽입하고 마지막 제거
- 업데이트 비용: O(|C|)
- fractional knapsack 구조 활용
최종 결과
- 기존보다 더 빠름.
BKP에 대한 적용
- BKP에도 동일 heuristic 적용 가능
- 하지만, BKP에서는
- exact lifting에도 이미 빠름.
- facet 보장됨.
RKP에서의 의미
- RKP에서는
- exact lifting: 매우 느림.
- heuristic: 훨씬 빠름 + 성능 유지
lifting problem을 exact로 풀지 않고 decomposition-based upper bound로 대체
→ 결과: 계산 시간 크게 감소 + inequality 품질 유지
decomposition-based upper bound를 활용하여 lifting problem을 근사적으로 해결함으로써,
계산 효율을 크게 향상시키면서도 기존과 유사한 품질의 lifted inequality를 생성하는 heuristic을 제안한다.
4. Computational results
이 절에서는 제안한 lifting heuristic의 계산 효율성과, 이를 통해 생성된 LRCI의 효과성에 대한 계산 실험 결과를 제시한다.
모든 알고리즘은 C++로 구현되었으며, MIP solver로는 Gurobi 10.0.0을 사용하였다.
계산 실험은 Intel Core i7 3.10GHz CPU와 16GB RAM을 갖춘 환경에서 수행되었다.
별도의 언급이 없는 한, 시간 제한은 1800초로 설정하였다.
4.1. Test instance: the robust bandwidth packing problem
- 주어진 통신 네트워크와 call 집합에 대해, robust bandwidth packing problem(RBPP)은 일부 호출을 네트워크에 할당하면서 총 이익을 최대화하는 문제
- 구체적으로, G = (V,A)를 네트워크라 하자. 여기서 V는 노드 집합, A는 간선 집합을 의미함. 각 간선 i∈A는 대역폭 용량 bi>0를 가짐.
- 또한, 네트워크에 할당할 호출들의 집합: J에 대해, 각 호출 j∈J는 출발 노드 sj에서 도착 노드 tj까지 이동하며, 해당 경로의 모든 아크에서 불확실한 대역폭 요구량 a~j 필요로 함.
- RBPP에서는 각 a~j의 불확실성 집합이 구간 [a - dj, aj + dj]로 주어지며, 여기서 aj>0 은 nominal 값, dj>0은 편차를 의미함.
- 또한, 각 간선마다 파라미터 Γ가 주어지며, 해당 아크에 할당된 호출들 중 최대 Γ개의 호출만 nominal 값에서 벗어난 대역폭을 가질 수 있음.
- RBPP의 목적; 네트워크에 할당된 호출들의 이익 pj의 총합을 최대화하는 것
- 이 문제는 다음과 같이 수식화할 수 있음:
- 제약식
- 유량 보존, 용량 제약, 불확실성 제약 등 포함
- xij: 호출 j가 간선 i를 사용하는지 여부
- yj: 호출 j가 네트워크에 할당되는지 여부
- 특히, 각 간선 i∈A에 대한 제약식은 RKP의 feasible solutoin set과 동일한 구조를 가짐.
- 따라서, 각 간선에 대해 생성된 LRCI(Lifted Robusted Cover Inequalities)를 활용해 RBPP 해결 가능
- 실험에 사용된 RBPP 인스턴스는 Fig. 1에 제시된 네트워크 기반으로 생성됨.
- 호출 집합 J = {1, ..., n}
- 각 호출의 출발 - 도착 노드 쌍은 무작위로 선택
- 파라미터는 다음과 같이 생성:
- dj∈[0,310−aj]
- pj∈[aj+10, aj+20]
- 간선 용량은 다음과 같이 설정:
RBPP는 각 아크마다 RKP 구조를 가지는 네트워크 최적화 문제이며,
제안한 LRCI를 실제 문제에 적용하기 위한 실험용 테스트베드로 사용됨.
4.2. Performance of the proposed lifting heuristic
- 제안한 lifting heuristic의 성능을, Joung and Park에서 제안한 exact lifting 방법과 비교
- 또한 lifting 효과 자체를 확인하고자, lifting을 적용하지 않은 RCI만 사용하는 경우도 함께 비교함.
실험 설정
- Branch-and-Cut 알고리즘에 LRCI를 적용
- LRCI는 branch-and-bound tree의 root node에서만 생성
- cutting-plane 방식으로 반복 수행
알고리즘 절차
(Step 1) 문제의 LP relaxation을 풀고 최적해 x^\hat{x}를 구한다.
(Step 2) 만약 x^가 정수해라면 종료한다. 그렇지 않으면 Step 3으로 간다.
(Step 3) 문제에 포함된 각 RKP에 대해, x에 의해 위배되는 RCI를 찾고 해당 RCI에 lifting 방법을 적용한다. 이후 생성된 LRCI를 원래 문제에 추가하고 Step 1로 돌아간다. 만약 더 이상 위배되는 RCI가 없다면 종료한다.
중요한 설정
- RBPP는 여러 개의 RKP 구조 포함함. → 한 iteration에서 최대 |A|개의 cut 생성 가능
- RCI 탐색: Joung & Park heuristic 사용
- lifting 순서: 기존 연구 기준 사용
성능 평가 지표
- lifting time (s)
- lifting에 걸린 총 시간
- Gap (%)
- 최적해와의 차이
- rgap closed (%)
- cut이 LP bound를 얼마나 개선했는지
실험 결과 요약
- LRCI는 확실히 효과 있음.
- RCI보다 LP bound를 훨씬 더 개선
- lifting 자체는 매우 중요
- Exact vs Heuristic 비교
- cut 품질
- 거의 동일
- 생성된 cut 개수
- 비슷
- 속도 차이
- heuristic이 훨씬 빠름.
- exact는 Γ 커질수록 폭발적으로 느려짐.
- branch-and-cut 전체 성능
- 작은 문제: exact가 node를 덜 탐색 (약간 더 유리)
- 큰 문제: exact는 너무 느림. heuristic이 훨 좋은 결과
- cut 품질
핵심 관찰
- heuristic
- cut 품질 유지
- 생성 속도 빠름
- 전체 성능 개선
lifting heuristic은 exact lifting보다 훨씬 빠르면서도, 거의 동일한 품질의 LRCI를 생성함.
- branch-and-cut 성능 비교
- 비교 대상
- GUROBI: 기본 solver
- EXT: exact lifting
- HEU: proposed heuristic
- cut을 쓰면 확실히 빨라짐. (GUROBI보다)
- heuristic이 압도적으로 빠르고, 충분히 좋은 cut 생성, 큰 문제에서 훨씬 안정적
- 비교 대상
- Fig. 2: rgap closed (%)
- LP relaxation이 얼마나 개선됐는지
- 값이 클수록 cut 성능 좋음.
- heuristic은 exact와 거의 같은 cut 품질을 만듦.
- Fig. 3: Lifting time (s)
- lifting 계산 시간
- heuristic은 훨씬 빠름. (압도적 차이)
5. Concluding remarks
본 연구에서는 RKP를 위한 robust cover inequality에 대해 대안적인 lifting 방법을 제안함.
먼저, feasible solution set의 분해 성질을 기반으로 품질이 보장된 upper bound를 제안하였으며, 이것이 기존 RKP MIP 모델들의 LP relaxation bound보다 더 타이트함을 보임.
이후, 제안한 upper bound를 이용하여 lifted robust cover inequality의 계수를 결정하는 lifting heuristic을 설계하였으며, 이는 기존 exact lifting 방법보다 낮은 계산 복잡도를 가짐.
또한, 다양한 계산 실험을 통해 제안한 방법이 기존 lifting 방법에 비해 훨씬 짧은 시간 내에 LRCI를 생성하면서도, 생성된 부등식의 성능은 유사한 수준임을 확인하였음.
비록 제안한 lifting heuristic이 기존 exact lifting보다 계산 복잡도를 줄였지만, 대규모 robust optimization 문제를 해결하기 위해서는 여전히 더 효율적인 lifting 방법이 필요할 수 있음.
하나의 향후 연구 방향으로는, 분해 기반 upper bound를 계산하는 과정에서 Xk들 간의 계수 관계를 활용하여 계산 비용을 줄이는 방법이 있음. 또 다른 확장 방향으로는, 제안한 heuristic을 수정하여 robust cover inequality에 대한 효율적인 down-lifting 방법을 개발하는 것이 있음.