분기 절단법

분기 절단법(分岐切斷法, 分岐絶斷法, Branch and cut)은 조합 최적화에서 정수 계획법을 푸는 방법 중 하나이다. 정수 계획법이란 선형 계획법에서 모든 미지수가 정수로 제한된 경우를 말한다. 이 방법은 분기 한정법과 절단평면법을 합친 방법이다.

방법

분기 절단법에서는 우선 정수 제약을 없앤 선형 계획 문제를 일반적인 심플렉스법으로 푼다. 제약이 없어졌으므로 보통 이렇게 구한 최적해에는 실수값도 포함된다. 최적해를 구한 다음 절단평면법을 써서 현재의 실수해가 만족하지는 않지만 모든 유효한 정수점을 만족하는 선형 제약식을 찾아낸다. 그러한 부등식이 발견되면 풀던 선형 계획 문제에 추가한다. 새 문제를 풀면 이전보다 실수값이 줄어드는 바람직한 해가 나올 것이라는 기대를 할 수 있다. 이 과정을 정수해를 찾거나, 절단 평면을 더이상 찾을 수 없을 때까지 반복한다. 정수해를 찾아내는 경우에는 그 해가 최적해임이 알려져 있다. 찾아내지 못했다면 다음 과정으로 넘어간다.

이 시점에서 분기 한정법을 시작한다. 이 문제는 두 가지로 나눌 수 있다. 구해야 할 변수가 중간 결과값보다 큰 정수 중에서 가장 작은 정수값 이상이라는 추가 제약 조건이 있는 경우하고, 중간 결과값보다 작은 정수 중에서 가장 큰 정수값 이하인 경우이다. 여기서 원래의 제약 조건에 따르면 정수가 되어야 하지만 중간 결과에서는 정수값이 아닌 기본 변수의 수에 따라서 새로운 변수들을 도입한다. 이 새로운 선형 계획 문제를 심플렉스법으로 풀고, 이 과정을 해가 모든 정수 제약 조건을 만족할 때까지 반복한다. 분기 한정법을 푸는 도중 또다른 절단 평면으로 나눌 수 있는 경우가 있다. 이 절단 평면은 전역 절단면 즉, 모든 정수해에 유효한 절단면이거나 지역 절단면 즉, 현재 고려하는 분기 한정 부분트리에 적용되는 제약 조건을 만족하는 해에 유효한 절단면이다.

알고리즘

의사코드

C++계열 의사코드의 경우 다음과 같이 작성할 수 있다.

// ILP branch and cut solution pseudocode, assuming objective is to be maximized
ILP_solution branch_and_cut_ILP(IntegerLinearProgram initial_problem) {
    queue active_list; // L, above
    active_list.enqueue(initial_problem); // step 1
    // step 2
    ILP_solution optimal_solution; // this will hold x* above
    double best_objective = -std::numeric_limits<double>::infinity; // will hold v* above
    while (!active_list.empty()) { // step 3 above
        LinearProgram& curr_prob = active_list.dequeue(); // step 3.1
        do { // steps 3.2-3.7
            RelaxedLinearProgram& relaxed_prob = LP_relax(curr_prob); // step 3.2
            LP_solution curr_relaxed_soln = LP_solve(relaxed_prob); // this is x above
            bool cutting_planes_found = false;
            if (!curr_relaxed_soln.is_feasible()) { // step 3.3
                continue; // try another solution; continues at step 3
            }
            double current_objective_value = curr_relaxed_soln.value(); // v above
            if (current_objective_value <= best_objective) { // step 3.4
                continue; // try another solution; continues at step 3
            }
            if (curr_relaxed_soln.is_integer()) { // step 3.5
                best_objective = current_objective_value;
                optimal_solution = cast_as_ILP_solution(curr_relaxed_soln);
                continue; // continues at step 3
            }
            // current relaxed solution isn't integral
            if (hunting_for_cutting_planes) { // step 3.6
                violated_cutting_planes = search_for_violated_cutting_planes(curr_relaxed_soln);
                if (!violated_cutting_planes.empty()) { // step 3.6
                    cutting_planes_found = true; // will continue at step 3.2
                    for (auto&& cutting_plane : violated_cutting_planes) {
                        active_list.enqueue(LP_relax(curr_prob, cutting_plane));
                    }
                    continue; // continues at step 3.2
                }
            }
            // step 3.7: either violated cutting planes not found, or we weren't looking for them
            auto&& branched_problems = branch_partition(curr_prob);
            for (auto&& branch : branched_problems) {
                active_list.enqueue(branch);
            }
            continue; // continues at step 3
        } while (hunting_for_cutting_planes /* parameter of the algorithm; see 3.6 */
               && cutting_planes_found);
        // end step 3.2 do-while loop
    } // end step 3 while loop
    return optimal_solution; // step 4
}