지점 및 가격

Branch and price

응용수학에서 분기와 가격은 변수가 많은 정수 선형 프로그래밍(ILP)과 혼합정수 선형 프로그래밍(MILP) 문제를 해결하기 위한 조합 최적화의 방법이다.그 방법은 가지와 바운드와 기둥 생성 방법을 혼합한 것이다.

알고리즘 설명

분기 및 가격은 검색 트리의 각 노드에서 열을 선형 프로그래밍 이완(LP 이완)에 추가할 수 있는 분기 및 바운드 방법이다.알고리즘을 시작할 때, 계산 및 메모리 요구 사항을 줄이기 위해 일련의 컬럼을 LP 이완에서 배제한 후 필요에 따라 LP 이완에 다시 칼럼을 추가한다.이 접근방식은 큰 문제의 경우 대부분의 열이 비기본적이며 해당 변수가 최적의 솔루션에서 0과 같을 것이라는 관측에 근거한다.따라서 대부분의 칼럼은 문제 해결과 무관하다.

지점 및 가격 알고리즘의 개요.적응 대상

알고리즘은 일반적으로 단치히-와 같은 리폼을 사용하는 것으로 시작한다.Wolfe 분해, 마스터 문제라고 알려진 것을 형성한다.분해는 원래 제형의 이완을 해결할 때보다 이완을 해결할 때 더 나은 한계를 주는 문제 제형을 얻기 위해 행해진다.그러나 분해에는 보통 많은 변수가 포함되어 있으므로 제한된 마스터 문제라고 불리는 수정된 버전이 열 부분 집합만 고려하는 것으로 해결된다.[2]그런 다음 최적성을 확인하기 위해, 가격문제라는 하위 문제를 해결하여, 그 기초를 입력할 수 있는 열을 찾아 객관적 기능을 축소한다(최소화 문제의 경우).여기에는 비용이 마이너스 절감되는 칼럼을 찾는 것이 포함된다.가격 문제 자체는 해결하기 어려울 수 있지만 가장 부정적인 비용 절감 열은 찾을 필요가 없기 때문에 경험적 접근법과 국지적 검색 방법을 사용할 수 있다.[3]제한된 마스터 문제에 대한 최적의 해결책도 마스터 문제에 대한 최적의 해결책임을 증명하기 위해서는 하위 문제를 완료해야 한다.마이너스 비용 절감 칼럼이 발견될 때마다 '제한된 마스터 문제'에 추가되고 이완이 다시 시간 조정된다.어떤 열도 기초를 입력할 수 없고 이완에 대한 해결책이 정수가 아닌 경우 분기가 발생한다.[1]

대부분의 지점과 가격 알고리즘은 문제가 효과적인 분기 규칙을 수립할 수 있고 가격 문제를 비교적 쉽게 해결할 수 있도록 그러한 방식으로 문제를 공식화해야 하기 때문에 특정적이다.[4]

절삭기를 이용해 지점과 가격 알고리즘 내에서 LP 이완을 조이면, 이 방법을 분기 가격과 인하라고 한다.[5]

지점 및 가격 적용

지점 및 가격 방법을 사용하여 다음과 같은 다양한 적용 영역의 문제를 해결할 수 있다.

  • 그래프 다중 색상.[3]이것은 그래프의 각 노드에 미리 설정된 수의 색상을 할당해야 하며 가장자리를 공유하는 노드는 공통적으로 색상을 가질 수 없는 그래프 컬러링 문제를 일반화한 것이다.그 다음 목표는 유효한 색상을 갖는데 필요한 최소 색상 수를 찾는 것이다.멀티콜링 문제는 업무 스케줄링과 통신 채널 할당을 포함한 다양한 애플리케이션을 모델링하는 데 사용될 수 있다.
  • 차량 라우팅 문제.[2]
  • 일반화 할당 문제.[6]

참고 항목

외부 참조

참조

  1. ^ a b Akella, M.; S. Gupta; A. Sarkar. "Branch and Price: Column Generation for Solving Huge Integer Programs" (PDF). Archived from the original (PDF) on 2010-08-21. Retrieved 2012-12-19.
  2. ^ a b Feillet, Dominique (2010). "A tutorial on column generation and branch-and-price for vehicle routing problems". 4OR. 8 (4): 407–424. doi:10.1007/s10288-010-0130-z.
  3. ^ a b Mehrota, Anuj; M.A. Trick (2007). A Branch-and-price Approach for Graph Multi-Coloring. Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies. Operations Research/Computer Science Interfaces Series. Vol. 37. pp. 15–29. CiteSeerX 10.1.1.163.6870. doi:10.1007/978-0-387-48793-9_2. ISBN 978-0-387-48790-8.
  4. ^ Gamrath, G. "Generic Branch-Cut-and-Price" (PDF).
  5. ^ Desrosiers, J.; M.E. Lubbecke (2010). "Branch-Price-and-Cut Algorithms". Wiley Encyclopedia of Operations Research and Management Science.
  6. ^ Savelsbergh, M. (1997). "A branch-and-price algorithm for the generalized assignment problem". Operations Research. 831-841. 45 (6): 831–841. doi:10.1287/opre.45.6.831.