분기 및 절단

Branch and cut은^[1] 정수 선형 프로그램(ILP), 즉 일부 또는 모든 미지의 값이 정수 값으로 제한되는 선형 프로그래밍(LP)^[2] 문제를 해결하기 위한 조합 최적화의 방법이다. 분기 및 절단에는 분기 및 바운드 알고리즘을 실행하고 절단면을 사용하여 선형 프로그래밍 완화를 조이는 작업이 포함된다. 초기 LP 이완을 조이는 데에만 컷을 사용할 경우, 알고리즘을 컷 앤 분기라고 한다.

알고리즘.

이 설명은 ILP가 최대화 문제라고 가정한다.

이 방법은 정규 심플렉스 알고리즘을 사용하여 정수 제약 없이 선형 프로그램을 해결한다. 최적의 용액을 얻고 이 용액이 정수여야 하는 변수에 대한 비정수 값을 갖는 경우, 절단면 알고리즘을 사용하여 모든 실현 가능한 정수점에 의해 충족되지만 현재 분수 용액에 의해 위반되는 추가적인 선형 제약조건을 찾을 수 있다. 이러한 불평등은 선형 프로그램에 추가될 수 있으며, 선형 프로그램을 해결하면 희망컨대 "덜 작은 부분"인 다른 해결책을 산출하게 될 것이다.

이때 알고리즘의 분기 및 바인딩 부분이 시작된다. 문제는 여러 가지 (보통 두 가지) 버전으로 나뉜다. 그리고 나서 새로운 선형 프로그램은 심플렉스 방법을 사용하여 해결되고 과정이 반복된다. 분기 및 바운드 프로세스에서 LP 이완에 대한 비통합 솔루션은 상한 역할을 하고 일체형 솔루션은 하한 역할을 한다. 상한이 기존 하한보다 낮은 경우 노드를 폐기할 수 있다. 또한, LP 이완을 해결할 때 추가 절단면이 생성될 수 있는데, 이는 모든 실현 가능한 정수 용액에 유효한 전역 절단 또는 국소 절단일 수 있으며, 이는 현재 고려 중인 분기 및 바인딩 하위 트리의 측면 제약을 충족하는 모든 용액에 의해 만족된다는 것을 의미한다.

알고리즘은 아래에 요약되어 있다.

$L$ ${\displaystyle$ L $}$ 에 초기 $ILP$ 추가 $L$ 활성 문제 목록
$x^{*}={\text{null}}$ $x^{*}={\text{null}}$ = $x^{*}={\text{null}}$ ${\$ 및 $v^{*}=-\infty$ $v^{*}=-\infty$ = - $v^{*}=-\infty$ ${\displaystyle$ v $^{*}=-\inflt }$
$L$ $L$ 이 $L$ (가) 비어 있지 않은 동안
1. $L$ $L$ 에서 문제를 선택하여 제거(디큐어 제거)하십시오.
2. 문제의 LP 이완 문제를 해결한다.
3. 솔루션이 불가능한 경우 3(그 동안)으로 돌아가십시오. 그렇지 않으면 $목표$ $값$ v {\ $displaystyle$ v}을(를 $)$ 사용하여 $x$ x ${\$ $displaystyle$ $x}$ 을(를) 사용하여 솔루션을 표시하십시오 $v$
4. $v\leq v^{*}$ $v\leq v^{*}$ $∗{\$ 인 경우 $v\leq v^{*}$ 3으로 돌아가십시오.
5. $x$ ${\displaystyle$ x $}$ 이 $x$ (가) 정수인 경우 $v^{*}\leftarrow v,x^{*}\leftarrow x$ $v^{*}\leftarrow v,x^{*}\leftarrow x$ $v^{*}\leftarrow v,x^{*}\leftarrow x$ $v^{*}\leftarrow v,x^{*}\leftarrow x$ , x $v^{*}\leftarrow v,x^{*}\leftarrow x$ ← x $v^{*}\leftarrow v,x^{*}\leftarrow x$ ← x x x x x x $v^{*}\leftarrow v,x^{*}\leftarrow x$ x x { { { { ${$ { { { ${*}\왼쪽$ 화살표 v $,x^{*}\왼쪽$ 화살표 x}를 $v^{*}\leftarrow v,x^{*}\leftarrow x$ $설정하고$ 3으로 돌아가십시오.
6. 원하는 경우 $x$ $x$ 에 의해 위반된 절단면을 검색하고 $x$ 발견되면 LP 이완에 추가한 후 3.2로 돌아가십시오.
7. 제한된 실현 가능 지역과의 새로운 문제로 문제를 분리하기 위한 분기. 이 문제를 $L$ $L$ 에 추가하고 $L$ 3으로 돌아가십시오.
$∗{\$ x $^{*}}$ 을(를) 반환하십시오.

가성음

C++와 같은 가성 코드에서는 다음과 같이 기록할 수 있다.

// ILP 분기 및 절삭 솔루션 유사 코드, 목표가 최대화되어야 한다고 가정 ILP_솔루션 branch_and_cut_ILP(정수선형 프로그램 initial_properties) {     줄을 서다 active_list; // L, 위     active_list.응수하다(initial_properties); // 1단계     // 단계 2     ILP_솔루션 optimal_properties; // 위의 x*를 유지함     곱절로 하다 best_best = -찌꺼기::numeric_message<곱절로 하다>::무한의; // 위의 v*를 유지함     , 한편 (!active_list.텅 빈()) { // 위 3단계         선형 프로그램& curr_properties = active_list.큐를 제거하다(); // 단계 3.1         하다 { // 단계 3.2-3.7             이완선형 프로그램& 느긋한_부드러운 = LP_relax(curr_properties); // 단계 3.2             LP_솔루션 curr_soln = LP_solve(느긋한_부드러운); // 위의 x             바가지 긁다 cutting_build_found = 거짓의;             만일 (!curr_soln.is_message()) { // 단계 3.3                 계속하다; // 다른 솔루션을 시도해 보십시오. 3단계에서 계속 진행             }             곱절로 하다 current_properties_value = curr_soln.가치를 매기다(); // v 이상             만일 (current_properties_value <= best_best) { // 단계 3.4                 계속하다; // 다른 솔루션을 시도해 보십시오. 3단계에서 계속 진행             }             만일 (curr_soln.is_message()) { // 단계 3.5                 best_best = current_properties_value;                 optimal_properties = cast_as_ILP_솔루션(curr_soln);                 계속하다; // 3단계에서 계속             }             // 현재 완화된 용액은 통합되지 않음             만일 (hunting_for_cuting_beating_beat) { // 단계 3.6                 unrited_cutting_incipals = search_for_for_butting_butt(curr_soln);                 만일 (!unrited_cutting_incipals.텅 빈()) { // 단계 3.6                     cutting_build_found = 진실의; // 3.2 단계에서 계속                     을 위해 (자동차로&& 커팅_플레인 : unrited_cutting_incipals) {                         active_list.응수하다(LP_relax(curr_properties, 커팅_플레인));                     }                     계속하다; // 3.2 단계에서 계속                 }             }             // 단계 3.7: 절단면을 발견하지 못했거나, 우리가 찾지 못했거나, 찾지 못했거나             자동차로&& branched_branched_branched. = 지점_지점(curr_properties);             을 위해 (자동차로&& 가지를 치다 : branched_branched_branched.) {                 active_list.응수하다(가지를 치다);             }             계속하다; // 3단계에서 계속         } , 한편 (hunting_for_cuting_beating_beat /* 알고리즘 매개변수 3.6 */ 참조                && cutting_build_found);         // 3.2단계를 종료하는 동안 루프     } // 루프 중에 3단계 종료     돌아오다 optimal_properties; // 4단계 }

위의 유사 코드에서 함수는 LP_relax, LP_solve 그리고 branch_partition 서브루틴으로 불리는 서브루틴은 문제에 해당되는 경우 제공되어야 한다. 예를 들어, LP_solve 심플렉스 알고리즘을 호출할 수 있어 분기 전략: branch_partition 아래에 설명되어 있다.

분기 전략

분기 및 절단 알고리즘에서 중요한 단계는 분기 단계다. 이 단계에서는 사용할 수 있는 다양한 분기 휴리스틱스가 있다. 아래에서 설명하는 분기 전략은 모두 변수에 대한 분기라고 불리는 것을 포함한다.^[3] Branching on a variable involves choosing a variable, $x_{i}$ , with a fractional value, $x_{i}'$ , in the optimal solution to the current LP relaxation and then adding the constraints $x_{i}\leq \left\lfloor x_{i}'\right\rfloor$ and $x_{i}\geq \left\lceil x_{i}'\right\rceil$ $x_{i}\geq \left\lceil x_{i}'\right\rceil$

가장 실현 불가능한 분기: 이 분기 전략은 0.5에 가장 가까운 분수 부분을 가진 변수를 선택한다.
의사원가분지: 이 전략의 기본 개념은 이 변수를 분기할 변수로 이전에 선택했을 때 목표 함수의 변화를 $x_{i}$ 각 변수 $x_{i}$ $x_{i}$ ${\$ 에 대해 추적하는 것이다. 그런 다음 분기변수로 선택했을 때 과거의 변화에 따라 객관적인 기능에 가장 큰 변화가 예상되는 변수를 전략적으로 선택한다. 사이비 비용 분기는 초기에 검색에 비정보적이라는 점에 유의하십시오. 이는 거의 없기 때문이다.
강한 분기: 강력한 분기에는 실제 분기하기 전에 어떤 후보가 객관적 기능을 가장 잘 개선할 수 있는지를 시험하는 것이 포함된다. 완전한 강력한 분기점은 모든 후보 변수를 테스트하며 계산적으로 비용이 많이 들 수 있다. 후보 변수의 부분집합만 고려하고 각각의 해당 LP 이완을 완료까지 풀지 않으면 계산 비용을 줄일 수 있다.

또한 이러한 분기 전략에는 많은 변화가 있는데, 이는 의사 비용 분기가 비교적 비정보적인 경우 초기에 강한 분기를 사용하고, 의사 비용이 정보를 얻을 수 있을 만큼 분기가 충분한 경우 나중에 의사 비용 분기로 전환하는 것이다.

참조

^ Padberg, Manfred; Rinaldi, Giovanni (1991). "A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems". SIAM Review. 33 (1): 60–100. doi:10.1137/1033004. ISSN 0036-1445.
^ John E., Mitchell (2002). "Branch-and-Cut Algorithms for Combinatorial Optimization Problems" (PDF). Handbook of Applied Optimization: 65–77.
^ Achterberg, Tobias; Koch, Thorsten; Martin, Alexander (2005). "Branching rules revisited". Operations Research Letters. 33 (1): 42–54. doi:10.1016/j.orl.2004.04.002.

외부 링크

혼합 정수 프로그래밍
SCIP: 지점 컷 앤드 프라이스 및 혼합 정수 프로그래밍 솔루션을 위한 프레임워크
ABACUS – 지점 및 CUT 시스템 – 오픈 소스 소프트웨어
CONE-OR Cbc – GitHub의 오픈 소스 소프트웨어

[1] Padberg, Manfred; Rinaldi, Giovanni (1991). "A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems". SIAM Review. 33 (1): 60–100. doi:10.1137/1033004. ISSN 0036-1445.

[2] John E., Mitchell (2002). "Branch-and-Cut Algorithms for Combinatorial Optimization Problems" (PDF). Handbook of Applied Optimization: 65–77.

[3] Achterberg, Tobias; Koch, Thorsten; Martin, Alexander (2005). "Branching rules revisited". Operations Research Letters. 33 (1): 42–54. doi:10.1016/j.orl.2004.04.002.

[1]

[2]

[3]

Search

분기 및 절단

네임스페이스

더

목차

알고리즘.

가성음

분기 전략

참조

외부 링크