반응형
- 컷팅 플레인 (
Cutting Plane
) 방법은 혼합 정수 계획법 (Mixed Integer Programming
,MIP
) 에서 최적해를 찾기 위해 사용되는 대표적인 기법 중 하나입니다.
- 주로 다음과 같은 특징을 가집니다.
- 정수 프로그램 문제에서 단순히 선형 계획법 (
Linear Programming
,LP
)으로는 정수 제약을 만족하는 최적해를 찾기 어렵기 때문에 사용됩니다. - 단순한
LP
해가 실수 영역에 놓일 때, 이를 정수로 제한하기 위해 추가적인 제약식을 도입하여 해를 점진적으로 개선하는 방법입니다.
- (1) 초기
LP
문제 해결- 정수 제약을 무시하고 연속 변수로 설정한
LP
문제를 먼저 해결합니다.
- 정수 제약을 무시하고 연속 변수로 설정한
- (2) 컷 생성
- 최적해가 정수 제약을 만족하지 않으면, 이를 배제하기 위한 컷 (
Cut
) 을 추가합니다.
- 최적해가 정수 제약을 만족하지 않으면, 이를 배제하기 위한 컷 (
- (3) 문제 재해결
- 새로운 컷이 포함된 수정된 문제를 다시 해결합니다.
- (4) 반복
- 정수 해가 나올 때까지 컷 생성을 반복합니다.
- (5) 정수 해 도달
- 최적의 정수 해가 도출되면 알고리즘을 종료합니다.
Gomory Cut
- 가장 기본적인 컷 중 하나로, 단순한 분수 형태의 해를 정수화하기 위한 방식입니다.
Chvátal-Gomory Cut
- 모든 정수 계획 문제에 적용할 수 있는 일반적인 컷입니다.
Lift-and-Project Cut
- 더 강력한 형태의 컷으로, 보다 날카로운 절단면을 제공합니다.
Mixed Integer Rounding(MIR) Cut
- 혼합 정수 문제에 특화된 컷입니다.
- 장점
- 단순하면서도 효율적으로 정수 해를 찾는 데 유용합니다.
- 다양한 문제에 적용 가능하고, 구현이 비교적 간단합니다.
- 단점
- 잘못된 컷 추가 시 수렴 속도가 매우 느려질 수 있습니다.
- 특정 문제에서는 비효율적이거나 불안정한 결과를 초래할 수 있습니다.
- 생산 계획 최적화
- 물류 경로 최적화
- 네트워크 설계
- 자원 할당 문제
- 도움이 되셨으면 하단의 ❤️ 공감 버튼 부탁 드립니다. 감사합니다! 😄
- 일부 모바일 환경에서는 ❤️ 버튼이 보이지 않습니다.
728x90
반응형
'Algorithm' 카테고리의 다른 글
엔-퀸(N-Queen) 문제와 백트래킹 알고리즘 (0) | 2025.05.24 |
---|---|
분지 한정법(Branch and Bound) 알고리즘 (0) | 2025.05.17 |
정렬 알고리즘과 검색 알고리즘 조합 빅오(Big O) 분석 (2) (0) | 2025.03.17 |
정렬 알고리즘과 검색 알고리즘의 Big-O 복합 분석 (0) | 2025.03.16 |
웰시-파월 알고리즘 (Welsh-Powell Algorithm) (0) | 2025.03.13 |