분기 절단법

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 방법
3. 알고리즘
- 3.1. 의사 코드 (C++ 스타일)
참조

1. 개요

분기 절단법은 정수 제약이 있는 선형 계획법 문제를 해결하는 데 사용되는 최적화 알고리즘이다. 이 방법은 절단 평면법과 분기 한정법을 결합하여, 정수 제약 조건을 만족하는 최적해를 찾는다. 분기 절단법은 먼저 심플렉스법으로 정수 제약을 완화한 선형 계획 문제를 풀고, 실수해가 나오면 절단 평면법을 적용하여 정수해를 찾거나 분기 한정법을 시작한다. 분기 한정법에서는 문제를 여러 하위 문제로 나누어 각 하위 문제를 심플렉스법으로 풀고, 해가 정수 제약 조건을 만족할 때까지 이 과정을 반복한다. 분기 과정에서 다양한 분기 전략, 예를 들어 가장 비현실적인 분기, 유사 비용 분기, 강력한 분기 등이 사용될 수 있다.

더 읽어볼만한 페이지

조합 최적화 - A* 알고리즘
A* 알고리즘은 가중치 그래프에서 시작 노드부터 목표 노드까지 최소 비용 경로를 찾는 정보 탐색 알고리즘으로, 경로 비용과 목표까지 추정 비용의 합을 최소화하여 경로를 탐색하며 내비게이션, 게임 AI 등에 활용된다.
조합 최적화 - 정수 계획법
정수 계획법은 선형 계획법의 한 분야로, 해가 정수 값을 가져야 하는 제약 조건이 추가된 최적화 문제이며, 다양한 분야에 응용되고 정확한 알고리즘 또는 휴리스틱 방법을 통해 해결할 수 있다.
최적화 알고리즘 - 기댓값 최대화 알고리즘
최적화 알고리즘 - 유전 알고리즘
유전 알고리즘은 생물 진화 과정을 모방하여 최적해를 탐색하는 계산 최적화 기법으로, 해를 유전자로 표현하고 적합도 함수를 통해 평가하며 선택, 교차, 돌연변이 연산을 반복하여 최적해에 근접하는 해를 생성하며, 성능은 매개변수에 영향을 받고 초기 수렴 문제 해결을 위한 다양한 변형 기법과 관련 기법이 존재한다.

분기 절단법
개요
유형	최적화 알고리즘
분야	정수 계획법
상세 정보
특징	선형 계획법 완화 사용 분기 한정법과 절단 평면법 결합
목표	정수 최적화 문제 해결 최적 솔루션 찾기
관련 기법	분기 한정법 절단 평면법 선형 계획법
적용 분야
활용 예시	여행하는 외판원 문제 집합 덮개 문제 최대 절단 문제
참고 문헌

2. 방법

분기 절단법은 정수 계획 문제를 해결하기 위한 방법으로, 크게 두 단계로 나뉜다.

먼저, 절단 평면법을 적용한다. 정수 제약 조건을 없앤 선형 계획 문제를 심플렉스법으로 풀어 실수값을 포함하는 최적해를 구한다. 그 후, 절단 평면법을 사용하여 현재의 실수해는 만족하지 않지만 모든 정수해는 만족하는 선형 제약식을 찾아 원래 문제에 추가한다. 이 과정을 반복하여 정수해를 찾거나 더 이상 절단 평면을 찾을 수 없을 때까지 진행한다.

다음으로, 분기 한정법을 적용한다. 이 단계에서는 원래 문제를 여러 개의 부분 문제로 나누고, 각 부분 문제에 대해 심플렉스법을 적용하여 해를 구한다. 이 과정에서 정수해가 아닌 해는 상한으로, 정수해는 하한으로 작용하며, 상한이 하한보다 낮으면 해당 부분 문제는 더 이상 고려하지 않는다(가지치기). 또한, 분기 한정 과정에서 추가적인 절단 평면(전역 절단 또는 지역 절단)을 찾아 문제에 추가할 수 있다.

분기 과정에서 어떤 변수를 기준으로 문제를 나눌지 결정하는 분기 전략이 중요하다. 변수 분기 전략에는 가장 비현실적인 분기, 유사 비용 분기, 강력한 분기 등이 있다.

2. 1. 절단 평면법의 적용

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

2. 2. 분기 한정법의 적용

이 방법은 정수 제약 조건 없이 일반적인 선형 계획법을 사용하여 심플렉스 알고리즘을 적용한다. 최적해가 나왔을 때, 이 해가 정수여야 하는 변수가 정수가 아닌 값을 가지면, 절단 평면 알고리즘을 사용하여 모든 실현 가능한 정수 점에서는 만족되지만 현재 분수 해에서는 위반되는 추가적인 선형 제약을 찾을 수 있다. 이러한 부등식은 선형 계획법에 추가될 수 있으며, 이를 다시 풀면 "덜 분수적인" 다른 해를 얻을 수 있다.^[1]

이후 알고리즘의 분기 한정 부분이 시작된다. 문제는 여러 (보통 두 개) 버전으로 분할된다. 그 후 새로운 선형 계획법은 심플렉스 방법을 사용하여 풀리고 과정이 반복된다. 분기 한정 과정에서 LP 완화에 대한 비정수 해는 상한으로 작용하고 정수 해는 하한으로 작용한다. 상한이 기존 하한보다 낮으면 노드를 가지치기할 수 있다. 또한 LP 완화를 풀 때 추가적인 절단 평면이 생성될 수 있으며, 이는 모든 실현가능한 정수 해에 유효한 ''전역 절단''이거나, 현재 고려 중인 분기 한정 하위 트리에서 측면 제약을 충족하는 모든 해에 의해 충족되는 ''지역 절단''을 의미한다.^[1]

2. 3. 분기 전략

분기 절단 알고리즘에서 분기 단계는 매우 중요하다. 이 단계에서는 다양한 분기 휴리스틱을 사용할 수 있는데, 모두 '''변수 분기''' 방식을 사용한다.^[3] 변수 분기는 현재 선형 계획법(LP) 완화의 최적 해에서 분수 값을 갖는 변수를 선택하여 제약 조건을 추가하는 방식이다. 대표적인 변수 분기 전략으로는 가장 비현실적인 분기, 유사 비용 분기, 강력한 분기 등이 있다.

2. 3. 1. 변수 분기 전략

분기 절단 알고리즘에서 중요한 단계는 분기 단계이며, 이 단계에서는 다양한 분기 휴리스틱을 사용할 수 있다. 아래에 설명된 분기 전략은 모두 '''변수 분기'''를 포함한다.^[3] 변수 분기는 현재 선형 계획법(LP) 완화의 최적 해에서 분수 값을 갖는 변수

x_i

를 선택하고, 제약 조건

x_i \le \left\lfloor x_i' \right\rfloor

및

x_i \ge \left\lceil x_i' \right\rceil

을 추가하는 것을 포함한다.

'''가장 비현실적인 분기''': 이 분기 전략은 분수 부분이 0.5에 가장 가까운 변수를 선택한다.
'''유사 비용 분기''': 각 변수 $x_i$ 에 대해 이 변수가 이전에 분기할 변수로 선택되었을 때 목적 함수의 변화를 추적한다. 그런 다음, 과거 변화를 기반으로 목적 함수에 가장 큰 변화가 있을 것으로 예측되는 변수를 선택한다. 유사 비용 분기는 초기에는 몇 개의 변수에 대해서만 분기가 수행되었으므로 탐색 과정에서 정보를 제공하지 못한다.
'''강력한 분기''': 실제로 분기하기 전에 후보 변수 중 어느 것이 목적 함수에 가장 큰 개선을 가져다주는지 테스트한다. '''전체 강력한 분기'''는 모든 후보 변수를 테스트하며 계산 비용이 많이 들 수 있다. 계산 비용은 해당 LP 완화를 모두 완료하지 않고 후보 변수의 하위 집합만 고려함으로써 줄일 수 있다.

이러한 분기 전략에는, 유사 비용 분기가 비교적 정보를 제공하지 못하는 초기에 강력한 분기를 사용한 다음, 유사 비용이 정보를 제공할 수 있을 만큼 충분한 분기 이력이 있을 때 나중에 유사 비용 분기로 전환하는 것과 같은 많은 변형이 있다.

3. 알고리즘

분기 절단법은 정수 계획법(ILP) 문제를 해결하기 위한 알고리즘이다. 이 알고리즘은 먼저 정수 제약 조건을 무시하고 선형 계획법 완화 문제를 심플렉스 알고리즘을 사용하여 푼다. 만약 이 해에서 정수여야 하는 변수가 정수 값을 갖지 않는다면, 절단 평면법을 사용하여 현재의 분수 해를 제거하면서도 모든 정수 해는 만족하는 추가적인 선형 제약 조건을 찾는다. 이러한 제약 조건을 추가하여 선형 계획법을 다시 풀면, 더 정수 해에 가까운 새로운 해를 얻을 수 있다.

이후, 분기 한정법 단계가 시작된다. 문제는 여러 개의 하위 문제로 분할되고, 각 하위 문제에 대해 심플렉스 알고리즘을 사용하여 선형 계획법을 푼다. 이 과정에서, 분기 한정법의 비정수 해는 상한, 정수 해는 하한으로 사용되며, 상한이 기존 하한보다 낮으면 해당 노드는 더 이상 탐색하지 않아도 된다. 또한, 선형 계획법 완화를 풀 때 추가적인 절단 평면을 생성할 수 있는데, 이는 모든 정수 해에 유효한 전역 절단이거나, 현재 분기 한정 하위 트리에서 특정 조건을 만족하는 해에 유효한 지역 절단일 수 있다.

알고리즘은 다음과 같이 요약할 수 있다.

# 초기 ILP 문제를 활성 문제 목록( $L$ )에 추가한다.

# $x^* = \text{null}$ (최적해) 및 $v^* = -\infty$ (최적해의 목적 함수 값)로 설정한다.

# $L$ 이 비어 있지 않은 동안 다음을 반복한다.

## $L$ 에서 문제를 선택하여 제거한다.

## 문제의 LP 완화를 푼다.

## 해가 실현 불가능하면 3번 단계로 돌아간다. 그렇지 않으면, 해를 $x$ , 목적 함수 값을 $v$ 로 둔다.

## $v \le v^*$ 이면 3번 단계로 돌아간다.

## $x$ 가 정수이면, $v^* \leftarrow v$ , $x^* \leftarrow x$ 로 설정하고 3번 단계로 돌아간다.

## (선택 사항) $x$ 에 의해 위반되는 절단 평면을 찾는다. 찾은 경우, 이를 LP 완화에 추가하고 3.2번 단계로 돌아간다.

## 문제를 제한된 실현 가능 영역을 가진 새로운 문제들로 분기한다. 이 문제들을 $L$ 에 추가하고 3번 단계로 돌아간다.

# $x^*$ 를 반환한다.

3. 1. 의사 코드 (C++ 스타일)

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::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

}

위 의사 코드에서 하위 루틴으로 호출되는 함수 `LP_relax`, `LP_solve`, `branch_partition`은 문제에 따라 제공되어야 한다. 예를 들어, `LP_solve`는 심플렉스 알고리즘을 호출할 수 있다. `branch_partition`에 대한 분기 전략은 이 문서의 다른 섹션에서 다룬다.

참조

_[1] 논문 A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems 1991
_[2] 논문 Branch-and-Cut Algorithms for Combinatorial Optimization Problems http://eaton.math.rp[...]
_[3] 논문 Branching rules revisited 2005

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com