혼합 정수 선형 계획법(MILP) 알고리즘

혼합 정수 선형 계획법 정의

혼합 정수 선형 계획법(MILP)은 다음 조건을 갖는 문제입니다.

선형 목적 함수 f^Tx. 여기서 f는 상수로 구성된 열 벡터이고 x는 미지수로 구성된 열 벡터입니다.
범위와 선형 제약 조건. 단, 비선형 제약 조건은 포함되지 않음(정의는 제약 조건 작성하기 참조)
x의 일부 성분이 정수 값을 가져야 한다는 제한

수학적 측면에서 벡터 f, lb, ub와 행렬 A, Aeq, 이에 대응하는 벡터 b, beq, 그리고 인덱스 세트 intcon이 주어질 때, 다음 문제의 해가 되는 벡터 x를 구합니다.

$\min_{x} f^{T} x subject to {\begin{array}{l} x (intcon) are integers \\ A \cdot x \leq b \\ A e q \cdot x = b e q \\ l b \leq x \leq u b . \end{array}$

알고리즘 개요

intlinprog는 다음과 같은 기본 전략을 사용하여 혼합 정수 선형 계획법 문제를 풉니다. intlinprog에 의해 어느 단계에서든 문제가 풀릴 수 있습니다. 어느 한 단계에서 문제가 해결되면 intlinprog는 그 이후의 단계를 실행하지 않습니다.

선형 계획 전처리를 사용하여 문제 크기를 줄입니다.
선형 계획법을 사용하여 완화된(정수가 아닌) 초기 문제를 풉니다.
혼합 정수 계획 전처리를 수행하여 혼합 정수 문제에 대한 LP 완화를 강화합니다.
절단 생성을 시도하여 혼합 정수 문제에 대한 LP 완화를 더욱 강화합니다.
발견법(Heuristics)을 사용하여 실현 가능한 정수 해를 구해 봅니다.
분기한정(Branch-and-Bound) 알고리즘을 사용하여 최적해를 체계적으로 구합니다. 이 알고리즘은 정수 변수의 가능한 값에 대한 제한된 범위를 사용하여 LP 완화를 풉니다. 이는 최적의 목적 함수 값에 대한 일련의 업데이트된 범위를 생성하려고 시도합니다.

선형 계획 전처리

혼합 정수 선형 계획법 정의에 따르면 다음과 같이 선형 부등식과 선형 등식 집합을 표현하는 행렬 A와 Aeq, 그리고 대응하는 벡터 b와 beq가 있습니다.

$\begin{matrix} A \cdot x \leq b \\ A e q \cdot x = b e q . \end{matrix}$

이러한 선형 제약 조건은 해 x를 제한합니다.

일반적으로, 문제에 포함되는 변수의 개수(x의 성분 개수)를 줄이고 선형 제약 조건의 개수를 줄일 수 있습니다. 이렇게 줄이는 작업을 수행하느라 솔버에서 시간이 더 걸릴 수 있지만, 일반적으로 해를 구하는 데 소요되는 전체 시간이 감소되므로 더 큰 문제를 풀 수 있게 됩니다. 알고리즘은 해를 수치적으로 더 안정하게 만들 수 있습니다. 또한, 이러한 알고리즘은 경우에 따라 실현불가능 문제를 감지하기도 합니다.

전처리 단계는 중복된 변수와 제약 조건을 제거하고, 모델의 스케일링과 제약 조건 행렬의 희소성을 향상시키고, 변수의 범위를 강화하고, 모델의 원문제 실현불가능성과 쌍대 문제 실현불가능성을 감지하는 것을 목표로 합니다.

자세한 내용은 앤더슨(Andersen)과 앤더슨(Andersen)의 문헌[2] 및 미사로쉬(Mészáros)와 셜(Suhl)의 문헌 [8]을 참조하십시오.

선형 계획법

완화된 초기 문제는 혼합 정수 선형 계획법 정의와 동일한 목적 함수와 제약 조건을 갖지만, 정수 제약 조건은 갖지 않는 선형 계획법 문제입니다. x_LP를 완화된 문제의 해라고 하고 x를 정수 제약 조건이 있는 원래 문제의 해라고 합니다. 간단히 말해 다음이 성립됩니다.

f^Tx_LP ≤ f^Tx,

그 이유는 x_LP가 더 적은 제한 사항으로 동일한 함수를 최소화하기 때문입니다.

분기한정(Branch-and-Bound) 알고리즘이 실행되는 동안 이 완화된 초기 LP(루트 노드 LP)와 생성된 모든 LP 완화는 선형 계획법 풀이 기법을 사용하여 풉니다.

혼합 정수 계획 전처리

혼합 정수 계획의 전처리 과정에서 intlinprog는 정수 제한과 함께 선형 부등식 A*x ≤ b를 분석하여 다음을 결정합니다.

문제가 실현 불가능한지 여부.
일부 범위를 좁힐 수 있는지 여부.
일부 부등식이 중복되어 있어, 무시하거나 제거할 수 있는지 여부.
일부 부등식을 강화할 수 있는지 여부.
일부 정수 변수를 고정할 수 있는지 여부.

IntegerPreprocess 옵션을 사용하면 intlinprog가 여러 스텝을 실행할지, 스텝을 전부 실행할지, 아니면 스텝을 거의 실행하지 않을지를 선택할 수 있습니다. x0 인수를 포함시키는 경우 intlinprog는 전처리에 이 값을 사용합니다.

혼합 정수 계획 전처리의 주 목적은 그다음에 수행하는 분기한정 계산을 단순화하는 것입니다. 전처리에는 분기한정에서 분석하게 될 수 있는 무의미한 하위 문제 후보 일부를 빠르게 미리 검토하여 제거하는 작업이 포함됩니다.

정수 전처리에 대한 자세한 내용은 세이블스버그(Savelsbergh)의 문헌 [10]을 참조하십시오.

절단 생성

절단은 intlinprog가 문제에 추가하는 부가적인 선형 부등식 제약 조건입니다. 이 부등식은 해가 정수에 더 가깝도록 LP 완화의 실현 가능한 영역을 제한하려고 시도합니다. CutGeneration 옵션을 사용하여 intlinprog가 사용하는 절단 유형을 제어할 수 있습니다.

'basic' 절단에는 다음이 포함됩니다.

혼합 정수 반올림 절단
고모리 절단(Gomory cut)
클릭 절단(Clique cut)
커버 절단(Cover cut)
흐름 커버 절단(Flow Cover cut)

또한, 문제가 순수하게 정수이면(모든 변수가 정수 값을 가짐) intlinprog는 다음 절단도 사용합니다.

강한 슈바탈-고모리 절단(Strong Chvatal-Gomory cut)
영-절반 절단(Zero-Half cut)

'intermediate' 절단에는 모든 'basic' 절단과 함께 다음이 포함됩니다.

단순한 올리기 및 투영 절단(Simple Lift-and-Project cut)
단순한 피벗 및 감소 절단(Simple Pivot-and-Reduce cut)
감소 및 분할 절단(Reduce-and-Split cut)

'advanced' 절단에는 감소 및 분할 절단을 제외한 모든 'intermediate' 절단과 함께 다음이 포함됩니다.

강한 슈바탈-고모리 절단(Strong Chvatal-Gomory cut)
영-절반 절단(Zero-Half cut)

순수한 정수 문제의 경우, 'intermediate'가 가장 많은 절단 유형을 사용합니다. intermediate는 감소 및 분할 절단을 사용하지만 'advanced'는 이 절단을 사용하지 않기 때문입니다.

또 다른 옵션인 CutMaxIterations는 intlinprog가 절단을 생성하기 위해 반복하는 횟수에 대한 상한을 지정합니다.

절단 생성 알고리즘(평면 절단 방법이라고도 함)에 대한 자세한 내용은 코르누에졸스(Cornuéjols)의 문헌 [5]를 참조하고, 클릭 절단에 대해서는 아탐튀르크(Atamtürk), 넴하우저(Nemhauser), 사벨스베르그(Savelsbergh)의 문헌 [3]을 참조하십시오.

실현 가능한 해를 구하는 데 활용할 수 있는 발견법

목적 함수에 대한 상한을 구하기 위해 분기한정(Branch-and-Bound) 절차에서는 실현가능점을 구해야 합니다. 분기한정 중에 구하는 LP 완화의 해는 실현 가능한 정수 해일 수 있으며, 이는 원래 MILP에 향상된 상한을 제공할 수 있습니다. 어떤 기법에서는 분기한정 이전 또는 도중에 실현가능점을 더 빠르게 찾아냅니다. intlinprog는 루트 노드에서 분기한정 반복 중에 이런 기법을 사용합니다. 이러한 기법은 발견법입니다. 즉, 성공할 수도 있지만 실패할 수도 있는 알고리즘입니다.

발견법은 솔버가 초기 해 또는 새로운 실현 가능한 정수 해를 구하는 데 유용한 시작 발견법일 수 있습니다. 또는 정수 실현가능점에서 시작하여 더 나은 정수 실현가능점, 즉 더 낮은 목적 함수 값을 갖는 점을 구하려는 개선 발견법일 수도 있습니다. intlinprog 개선 발견법은 'rins', 'rss', 1-opt, 2-opt 및 유도 급강하입니다.

'Heuristics' 옵션을 사용하여 intlinprog 발견법을 설정하십시오. 옵션은 다음과 같습니다.

옵션	설명
`'basic'`(디폴트 값)	솔버가 다양한 파라미터를 사용하여 반올림 발견법과 급강하 발견법을 각각 두 번 실행한 다음, `'rss'`를 실행합니다. 이전 발견법이 충분히 훌륭한 실현 가능한 정수 해를 구하는 경우 솔버는 이후 발견법을 실행하지 않습니다.
`'intermediate'`	솔버가 다양한 파라미터를 사용하여 반올림 발견법과 급강하 발견법을 각각 두 번 실행합니다. 실현 가능한 정수 해가 있는 경우 솔버는 `'rins'`를 실행한 후 `'rss'`를 실행합니다. `'rss'`가 새로운 해를 구할 경우 솔버는 `'rins'`를 다시 실행합니다. 이전 발견법이 충분히 훌륭한 실현 가능한 정수 해를 구하는 경우 솔버는 이후 발견법을 실행하지 않습니다.
`'advanced'`	솔버가 다양한 파라미터를 사용하여 반올림 발견법과 급강하 발견법을 각각 두 번 실행합니다. 실현 가능한 정수 해가 있는 경우 솔버는 `'rins'`를 실행한 후 `'rss'`를 실행합니다. `'rss'`가 새로운 해를 구할 경우 솔버는 `'rins'`를 다시 실행합니다. 이전 발견법이 충분히 훌륭한 실현 가능한 정수 해를 구하는 경우 솔버는 이후 발견법을 실행하지 않습니다.
`'rins'` 또는 이와 동등한 `'rins-diving'`	`intlinprog`는 현재 최적의 실현 가능한 정수 해에 해당하는 점(사용 가능한 경우)의 근방을 탐색하여 새롭고 더 나은 해를 구합니다. 다나(Danna), 로스버그(Rothberg), 르 파프(Le Pape)의 문헌 [6]을 참조하십시오. `'rins'`를 선택하면 솔버가 다양한 파라미터를 사용하여 반올림 발견법과 급강하 발견법을 각각 두 번 실행한 다음, `'rins'`를 실행합니다.
`'rss'` 또는 이와 동등한 `'rss-diving'`	`intlinprog`는 `'rins'`의 아이디어와 국소 분기가 결합된 혼합 절차를 적용하여 실현 가능한 정수 해를 찾습니다. `'rss'`를 선택하면 솔버가 다양한 파라미터를 사용하여 반올림 발견법과 급강하 발견법을 각각 두 번 실행한 다음, `'rss'`를 실행합니다. 이전 발견법이 충분히 훌륭한 실현 가능한 정수 해를 구하는 경우 솔버는 이후 발견법을 실행하지 않습니다. 이러한 설정은 `'basic'`과 동일한 발견법을 수행합니다.
`'round'`	`intlinprog`는 한 노드에서 완화된 문제의 LP 해를 얻고, 실현가능성을 유지하기 위한 시도로서 정수 성분을 반올림합니다. `'round'`를 선택하면 솔버는 루트 노드에서 다양한 파라미터를 사용하여 반올림 발견법과 급강하 발견법을 각각 두 번 실행합니다. 그 후, 솔버는 일부 분기한정 노드에서 반올림 발견법만 실행합니다.
`'round-diving'`	솔버는 `'round'`와 비슷한 방식으로 작동하지만, 루트 노드만이 아니라 일부 분기한정 노드에서도 급강하 발견법을 실행합니다(반올림 발견법도 사용함).
`'diving'`	`intlinprog`는 분기한정 스텝과 유사한 발견법을 사용하되, 다른 분기를 만들지 않고 트리에서 바로 아래에 있는 분기를 따릅니다. 이 단일 분기는 트리 조각 아래로 신속한 “급강하”를 초래하기 때문에 “급강하(Diving)”라는 이름이 붙었습니다. 현재, `intlinprog`는 다음 순서로 6가지 급강하 발견법을 사용합니다. 벡터 길이 급강하 계수 급강하 부분 급강하 의사 비용 급강하 직선 탐색 급강하 유도 급강하(솔버가 이미 최소 하나의 정수 실현가능점을 구한 경우에 적용됨) 급강하 발견법은 일반적으로 정수 값을 가져야 하는 하나의 변수를 선택합니다. 이에 대한 현재 해는 소수입니다. 그런 다음 이 발견법에서는 변수가 정수 값을 갖도록 강제하는 범위를 추가하고 연관된 완화된 LP를 다시 풉니다. 급강하 발견법 간의 주요 차이점은 범위에 대한 변수를 선택하는 방법에 있습니다. 베르톨드(Berthold)의 문헌 [4], 섹션 3.1을 참조하십시오.
`'none'`	`intlinprog`는 실현가능점을 찾지 않습니다. 솔버는 단순히 분기한정 탐색에서 발견되는 실현가능점을 사용합니다.

'intermediate'와 'advanced'의 주요 차이점은 'advanced'는 분기한정 반복 중에 더 자주 발견법을 실행한다는 점입니다.

위 표에 나와 있는 발견법 외에도, Heuristics 옵션이 'basic', 'intermediate' 또는 'advanced'인 경우 다음 발견법이 실행됩니다.

ZI round — 알고리즘이 완화된 LP를 풀 때마다 실행되는 발견법입니다. 이 발견법은 다른 제약 조건에 대한 실현가능성에 영향을 주지 않고 소수인 각 정수 변수를 인접한 정수로 이동시키려고 시도합니다. 자세한 내용은 Hendel [7]을 참조하십시오.
1-opt — 알고리즘이 새로운 실현 가능한 정수 해를 구할 때마다 실행되는 발견법입니다. 이 발견법은 다른 제약 조건에 대한 실현가능성에 영향을 주지 않고 각 정수 변수를 거치면서 해당 변수를 인접한 정수로 이동시켜려고 시도하면서, 목적 함수 값을 낮춥니다.
2-opt — 알고리즘이 새로운 실현 가능한 정수 해를 구할 때마다 실행되는 발견법입니다. 2-opt에서는 동일한 제약 조건에 영향을 주는 정수 변수 쌍을 전부 찾습니다. 이는 곧 A 또는 Aeq 제약 조건 행렬의 같은 행에 0이 아닌 요소가 있다는 뜻입니다. 각 쌍에 대해 2-opt는 실현 가능한 정수 해를 취하고 네 가지의 가능한 모든 이동(위-위, 위-아래, 아래-위, 아래-아래)을 사용하여 변수 쌍의 값을 위나 아래로 이동시켜, 더 나은 목적 함수 값을 가진 실현 가능한 인접 해를 찾습니다. 이 알고리즘에서는 제약 조건을 충족하고 목적 함수 값도 개선하는 쌍에서 각 변수에 대한 이동의 최대 크기(동일한 크기)를 계산하여, 각각의 정수 변수 쌍을 테스트합니다.

발견법 단계의 시작 부분에서 Heuristics이 'none'이 아니거나 사용자가 x0 인수에 초기 정수 실현가능점을 제공하지 않으면 intlinprog는 자명한 발견법을 실행합니다. 자명한 발견법은 다음 점에서 실현가능성을 확인합니다.

모든 영점
상한
하한(0이 아닌 경우)
"lock" 점

"lock" 점은 모든 변수에 유한 상한과 유한 하한을 갖는 문제에 대해서만 정의됩니다. 각 변수의 "lock" 점은 상한 또는 하한이고, 다음과 같이 선택됩니다. 각 변수 j에 대해 선형 제약 조건 행렬 A(:,j)의 대응되는 양수 항목의 개수를 센 다음 대응되는 음수 항목의 개수를 뺍니다. 결과가 양수이면 해당 변수에 하한 lb(j)를 사용하십시오. 그렇지 않으면 해당 변수에 상한 ub(j)를 사용하십시오. "lock" 점은 각 변수에 대해 최대 개수의 선형 부등식 제약 조건을 충족하려고 시도하지만, 반드시 실현 가능하지는 않습니다.

각 발견법이 실현 가능한 해와 함께 완료되고 나면 intlinprog가 출력 함수와 플롯 함수를 호출합니다. intlinprog Output Function and Plot Function Syntax 항목을 참조하십시오.

x0 인수를 포함시킬 경우 intlinprog는 더 나은 정수 실현가능점을 구할 때까지 'rins'와 유도 급강하 발견법에서 그 값을 사용합니다. 따라서 x0을 제공할 경우 'Heuristics' 옵션을 'rins-diving'으로 설정하거나 'rins'를 사용하는 다른 설정을 사용하여 좋은 결과를 얻을 수 있습니다.

분기한정(Branch-and-Bound)

분기한정법은 MILP의 해에 수렴하려고 시도하는 일련의 하위 문제를 생성합니다. 하위 문제는 해 f^Tx에 대한 일련의 상한 및 하한을 제공합니다. 첫 번째 상한은 임의의 실현 가능한 해이고, 첫 번째 하한은 완화된 문제의 해입니다. 상한에 대한 자세한 내용은 실현 가능한 해를 구하는 데 활용할 수 있는 발견법 항목을 참조하십시오.

선형 계획법에 설명된 대로 완화된 선형 계획법 문제의 해는 MILP의 해보다 낮은 목적 함수 값을 가집니다. 또한, 임의의 실현가능점 x_feas는 다음을 충족합니다.

f^Tx_feas ≥ f^Tx,

그 이유는 f^Tx가 모든 실현가능점 중 최솟값이기 때문입니다.

이 컨텍스트에서 노드는 원래 문제와 동일한 목적 함수, 범위, 선형 제약 조건을 갖지만 정수 제약 조건은 갖지 않으며 선형 제약 조건 또는 범위에 대한 특정한 변경 사항이 적용된 LP입니다. 루트 노드는 정수 제약 조건이 없고 선형 제약 조건 또는 범위에 대한 변경 사항이 적용되지 않은 원래 문제입니다. 즉, 루트 노드는 완화된 초기 LP입니다.

시작 범위에서 분기한정법은 루트 노드에서 분기를 생성함으로써 새 하위 문제를 생성합니다. 분기 생성 단계는 여러 규칙 중 하나에 따라 발견법 방식으로 수행됩니다. 각 규칙은 한 변수가 정수 J보다 작거나 같도록 제한하거나 J+1보다 크거나 같도록 제한하여 문제를 분할하는 아이디어를 기반으로 합니다. intcon에 지정된 정수에 대응하는 x_LP의 요소가 정수가 아닌 경우 이 두 하위 문제가 생성됩니다. 여기서, x_LP는 완화된 문제의 해입니다. 변수를 내림(버림)한 값을 J로 취하고 올림(반올림)한 값을 J+1로 취합니다. 결과로 생성되는 두 문제는 f^Tx_LP보다 크거나 같은 해를 가집니다. 그 이유는 제한 사항이 더 많기 때문입니다. 따라서, 이 절차는 잠재적으로 하한을 높일 수 있습니다.

분기한정법의 성능은 분할할 변수를 선택하는 규칙(분기 규칙)에 따라 달라집니다. 알고리즘은 다음과 같은 규칙을 사용하며, 이러한 규칙은 BranchRule 옵션에서 설정할 수 있습니다.

'maxpscost' — 최대 의사 비용을 갖는 소수 변수를 선택합니다.
의사 비용(Pseudocost)
변수 i의 의사 비용은 i가 분기 변수로 선택되었을 때 현재 점 x의 i 성분의 소수부와 결합된 하한의 변화에 대한 경험적 추정값을 기반으로 합니다. 소수부 p는 다음과 같이 두 부분, 즉 아래쪽 부분과 위쪽 부분으로 나뉩니다.
p_i^– = x(i) – ⌊x(i)⌋
p_i⁺ = 1 – p_i^–.
x_i^–를 x(i) ≤ ⌊x(i)⌋를 충족하도록 제한한 선형 계획의 해라고 하고 목적 함수의 변화량을 다음과 같이 나타냅니다.
Δ_i^– = f^Tx_i^– – f^Tx.
마찬가지로, Δ_i⁺는 문제가 x(i) ≥ ⌈x(i)⌉를 충족하도록 제한되었을 때의 목적 함수의 변화량입니다.
변수 x_i의 단위 변화당 목적 함수 이득의 변화량은 다음과 같습니다.
$d_{i}^{-} = \frac{Δ_{i}^{-}}{p_{i}^{-}} or d_{i}^{+} = \frac{Δ_{i}^{+}}{p_{i}^{+}} .$
s_i^– 및 s_i⁺를 이 점까지 분기한정 알고리즘을 실행하는 동안의 d_i^– 및 d_i⁺의 경험적 평균이라고 합시다. 이러한 경험적 값은 관측값이 들어가기 전의 항에 대하여 목적 함수 계수 f(i)의 절댓값으로 초기화됩니다. 그다음에 적용되는 'maxpscost' 규칙은 일부 양의 가중치 w⁺ 및 w^–에 대해 다음 수량을 극대화하는 노드 i에서 분기를 생성하는 것입니다.
w^– * p_i^– * s_i^– + w⁺ * p_i⁺ * s_i⁺.
간단히 말해, 이 규칙은 하한을 최대한 증가시킬 수 있을 법한 계수를 선택합니다.
'strongpscost' — 'maxpscost'와 유사하지만, 각 변수에 대해 의사 비용을 1로 초기화하는 대신 의사 비용이 더 신뢰할 수 있는 추정값을 가진 후에만 솔버가 변수에 대해 분기를 생성하려고 시도합니다. 더 신뢰할 수 있는 추정값을 얻기 위해 솔버는 다음을 수행합니다(아흐터베르그(Achterberg), 코흐(Koch), 마틴(Martin)의 문헌 [1] 참조).
- 현재 의사 비용 기반 점수를 기준으로 모든 잠재적인 분기 변수(현재는 소수이지만 정수여야 하는 변수)의 순서를 지정합니다.
- 가장 높은 점수를 갖는 변수부터 시작해, 현재 분기 변수를 기반으로 하는 두 개의 완화된 선형 계획을 실행합니다(변수가 분기 계산에 아직 사용되지 않은 경우). 솔버는 이 두 해를 사용하여 현재 분기 변수에 대한 의사 비용을 업데이트합니다. 솔버는 분기를 선택하는 데 걸리는 시간을 절약하기 위해 이 과정을 조기에 중단할 수 있습니다.
- 현재 가장 높은 의사 비용 기반 점수가 연속된 k개 변수에 대해 변경되지 않을 때까지 목록의 변수를 계속 선택합니다. 여기서 k는 내부적으로 선택되는 값이며, 일반적으로 5에서 10 사이입니다.
- 가장 높은 의사 비용 기반 점수를 갖는 변수에서 분기를 생성합니다. 솔버가 앞서 의사 비용 추정 절차를 실행하는 동안 이 변수를 기반으로 하는 완화된 선형 계획을 이미 계산했을 수 있습니다.
추가적인 선형 계획 해 때문에 'strongpscost' 분기의 각 반복은 디폴트 'maxpscost'보다 시간이 더 걸립니다. 하지만, 분기한정 반복 횟수가 대개 감소하므로 'strongpscost' 방법이 전체적으로 시간을 절약할 수 있습니다.
'reliability' — 'strongpscost'와 유사하지만, 초기화되지 않은 의사 비용 분기에 대해서만 완화된 선형 계획을 실행하는 대신 'reliability'는 각 변수에 대해 최대 k2회까지 계획을 실행합니다. 여기서 k2는 4 또는 8과 같은 작은 정수입니다. 따라서, 'reliability'에서는 훨씬 더 느리게 분기가 생성되지만, 잠재적으로 'strongpscost'보다 더 적은 횟수의 분기한정 반복을 실행합니다.
'mostfractional' — 1/2에 가장 가까운 소수부를 갖는 변수를 선택합니다.
'maxfun' — 목적 함수 벡터 f에서 대응하는 최대 절댓값을 갖는 변수를 선택합니다.

알고리즘이 분기를 생성하고 나면 탐색할 노드 두 개가 새로 생성됩니다. 알고리즘은 다음 규칙 중 하나를 사용하여, 가능한 모든 노드 중에서 탐색할 노드를 선택합니다.

'minobj' — 가장 낮은 목적 함수 값을 갖는 노드를 선택합니다.
'mininfeas' — 정수 실현불가능성의 합이 가장 작은 노드를 선택합니다. 이는 노드에 있는 모든 정수 실현불가능 성분 x(i)에 대해 p_i^– 및 p_i⁺ 중 더 작은 값을 더한다는 것을 의미합니다. 여기에는 다음이 성립합니다.
p_i^– = x(i) – ⌊x(i)⌋
p_i⁺ = 1 – p_i^–.
'simplebestproj' — 최적의 투영을 갖는 노드를 선택합니다.
최적의 투영
x_B는 지금까지 발견된 최적의 정수 실현가능점을 나타내고, x_R은 루트 노드에서 완화된 LP의 해를 나타내고, x는 검토하는 노드를 나타냅니다. in(x)는 노드 x에서의 정수 실현불가능성의 합을 나타냅니다('mininfeas' 참조). 최적의 투영 규칙은 다음을 최소화하는 것입니다.
$f^{T} x + \frac{f^{T} x_{B} - f^{T} x_{R}}{i n (x_{R})} i n (x) .$
지금까지 발견된 정수 실현가능점이 없으면 f^Tx_B = 0을 설정합니다.

intlinprog는 원래 문제에서의 정보(예: 목적 함수의 최대공약수(GCD))를 고려하여 일부 하위 문제의 분석을 건너뜁니다.

분기한정 절차는 다음 중지 기준 중 하나가 충족될 때까지 분석할 하위 문제를 체계적으로 생성하고 목적 함수의 상한 또는 하한을 향상시키지 않는 하위 문제를 삭제하는 작업을 계속 수행합니다.

알고리즘이 MaxTime 옵션을 초과합니다.
목적 함수의 하한과 상한 사이의 차이가 AbsoluteGapTolerance 허용오차 또는 RelativeGapTolerance 허용오차보다 작습니다.
탐색된 노드 개수가 MaxNodes 옵션을 초과합니다.
정수 실현가능점 개수가 MaxFeasiblePoints 옵션을 초과합니다.

분기한정 절차에 대한 자세한 내용은 Nemhauser와 Wolsey의 문헌 [9] 및 울시의 문헌 [11]을 참조하십시오.

참고 문헌

[1] Achterberg, T., T. Koch and A. Martin. Branching rules revisited. Operations Research Letters 33, 2005, pp. 42–54. Available at https://opus4.kobv.de/opus4-zib/files/788/ZR-04-13.pdf.

[2] Andersen, E. D., and Andersen, K. D. Presolving in linear programming. Mathematical Programming 71, pp. 221–245, 1995.

[3] Atamtürk, A., G. L. Nemhauser, M. W. P. Savelsbergh. Conflict graphs in solving integer programming problems. European Journal of Operational Research 121, 2000, pp. 40–55.

[4] Berthold, T. Primal Heuristics for Mixed Integer Programs. Technischen Universität Berlin, September 2006. Available at https://www.zib.de/groetschel/students/Diplom-Berthold.pdf.

[5] Cornuéjols, G. Valid inequalities for mixed integer linear programs. Mathematical Programming B, Vol. 112, pp. 3–44, 2008.

[6] Danna, E., Rothberg, E., Le Pape, C. Exploring relaxation induced neighborhoods to improve MIP solutions. Mathematical Programming, Vol. 102, issue 1, pp. 71–90, 2005.

[7] Hendel, G. New Rounding and Propagation Heuristics for Mixed Integer Programming. Bachelor's thesis at Technische Universität Berlin, 2011. PDF available at https://opus4.kobv.de/opus4-zib/files/1332/bachelor_thesis_main.pdf.

[8] Mészáros C., and Suhl, U. H. Advanced preprocessing techniques for linear and quadratic programming. OR Spectrum, 25(4), pp. 575–595, 2003.

[9] Nemhauser, G. L. and Wolsey, L. A. Integer and Combinatorial Optimization. Wiley-Interscience, New York, 1999.

[10] Savelsbergh, M. W. P. Preprocessing and Probing Techniques for Mixed Integer Programming Problems. ORSA J. Computing, Vol. 6, No. 4, pp. 445–454, 1994.

[11] Wolsey, L. A. Integer Programming. Wiley-Interscience, New York, 1998.