다목적 최적화 문제에서 하나의 목적함수만 최적화하고 나머지 목적함수들은 허용 한계값(ε) 이하로 제한하여 해를 구하는 방법
단일 최적해가 아닌 Pareto optimal solution들을 생성하는 대표적인 방법
다목적 최적화를 단일 목적 최적화 문제로 변환하는 기법
⭐ ε-constraint의 특징
✅ 1. 하나의 목적함수만 직접 최적화
-
여러 목적함수 중 하나를 주 목적함수로 선택
-
나머지 목적함수들은 제약조건(constraint) 으로 처리
예:
비용 최소화 (목적함수)
이동 거리 ≤ ε
불균형 ≤ ε₂
✅ 2. ε(엡실론)는 허용 한계값
-
ε는 각 목적함수에 대해 “이 정도까지는 허용” 이라는 기준
-
ε 값을 바꾸면 다른 Pareto 해가 생성됨
-
ε 조절 = 목적 간 trade-off 조절
✅ 3. Pareto front를 간접적으로 생성
-
ε 값을 단계적으로 변화시키며 문제를 반복 해결
-
각 실행 결과가 하나의 Pareto optimal solution
-
결과적으로 Pareto optimal set / Pareto front 구성
📌 ε-constraint의 절차
✅ 1. 목적함수 정의
- 가장 중요하다고 판단되는 목적함수 하나 선택
예:
f₁(x): 총 비용 최소화
✅ 2. ε 값 설정
- 나머지 목적함수에 대해 허용 가능한 상한 설정
예:
f₂(x) ≤ ε (이동 거리)
f₃(x) ≤ ε₂ (불균형)
✅ 3. 단일 목적 최적화 수행
-
일반적인 최적화 기법 그대로 사용
-
LP / MILP / MIP / 휴리스틱 등 적용 가능
✅ 4. ε 값 변경
-
ε 값을 바꿔가며 반복 실행
-
서로 다른 Pareto 해 획득
❗ ε-constraint의 구현 방식
✅ 1. 반복 실행 방식
-
ε 값을 일정 간격으로 변화
-
각 실행 결과 = 하나의 Pareto solution
-
계산 비용이 큼 (ε 개수 × 최적화 비용)
✅ 2. 적응적 ε 설정
-
이전 해를 기준으로 ε 범위 조정
-
불필요한 영역 탐색 감소
✅ 3. 정수 최적화 문제와 궁합이 좋음
-
MIP / MILP와 자연스럽게 결합 가능
-
물류, 네트워크, 스케줄링 문제에 자주 사용
⚠️ ε-constraint의 장단점
✅ 장점
-
모든 Pareto optimal solution 생성 가능
-
비볼록 Pareto front도 탐색 가능
-
가중치 설정 불필요 (해석 직관적)
-
기존 단일 목적 솔버 재사용 가능
❌ 단점
-
ε 값 설정이 어려움
-
반복 실행으로 계산 비용 큼
-
ε 간격에 따라 Pareto front 품질 달라짐
📝 예제
