이 페이지의 최신 내용은 아직 번역되지 않았습니다. 최신 내용은 영문으로 볼 수 있습니다.

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

혼합 정수 선형 계획법 정의

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

  • 선형 목적 함수 fTx. 여기서 f는 상수로 구성된 열 벡터이고 x는 미지수로 구성된 열 벡터입니다.

  • 범위와 선형 제약 조건. 단, 비선형 제약 조건은 포함되지 않음(정의는 제약 조건 작성하기 참조)

  • x의 일부 성분이 정수 값을 가져야 한다는 제한

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

minxfTx subject to {x(intcon) are integersAxbAeqx=beqlbxub.

intlinprog 알고리즘

알고리즘 개요

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

  1. 선형 계획 전처리를 사용하여 문제 크기를 줄입니다.

  2. 선형 계획법을 사용하여 완화된(정수가 아닌) 초기 문제를 풉니다.

  3. 혼합 정수 계획 전처리를 수행하여 혼합 정수 문제에 대한 LP 완화를 강화합니다.

  4. 절단 생성을 시도하여 혼합 정수 문제에 대한 LP 완화를 더욱 강화합니다.

  5. 발견법(Heuristics)을 사용하여 실현 가능한 정수 해를 구해 봅니다.

  6. 분기한정(Branch-and-Bound) 알고리즘을 사용하여 최적해를 체계적으로 구합니다. 이 알고리즘은 정수 변수의 가능한 값에 대한 제한된 범위를 사용하여 LP 완화를 풉니다. 이는 최적의 목적 함수 값에 대한 일련의 업데이트된 범위를 생성하려고 시도합니다.

선형 계획 전처리

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

A·xbAeq·x=beq.

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

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

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

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

선형 계획법

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

fTxLP ≤ fTx,

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

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

혼합 정수 계획 전처리

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

  • 문제가 실현 불가능한지 여부.

  • 일부 범위를 좁힐 수 있는지 여부.

  • 일부 부등식이 중복되어 있어, 무시하거나 제거할 수 있는지 여부.

  • 일부 부등식을 강화할 수 있는지 여부.

  • 일부 정수 변수를 고정할 수 있는지 여부.

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

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

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

절단 생성

절단은 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'는 이 절단을 사용하지 않기 때문입니다.

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

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

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

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

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

  • 'basic'(디폴트 값) — 'round'를 실행한 후 'rss'를 실행합니다. 이전 발견법이 충분히 훌륭한 실현 가능한 정수 해를 구하는 경우 솔버는 이후 발견법을 실행하지 않습니다.

  • 'intermediate' — 먼저 'round'를 실행한 후 'rins''rss'를 차례로 실행합니다. 이전 발견법이 충분히 훌륭한 실현 가능한 정수 해를 구하는 경우 솔버는 이후 발견법을 실행하지 않습니다.

  • 'advanced' — 먼저 'round'를 실행한 후 'diving', 'rins', 'rss'를 차례로 실행합니다. 이전 발견법이 충분히 훌륭한 실현 가능한 정수 해를 구하는 경우 솔버는 이후 발견법을 실행하지 않습니다. 솔버는 'diving'에 대해 부분 급강하(Fractional Diving)와 유도 급강하(Guided Diving) 발견법만 사용합니다.

  • 'rins'intlinprog는 현재 최적의 실현 가능한 정수 해에 해당하는 점(사용 가능한 경우)의 근방을 탐색하여 새 해와 더 나은 해를 구합니다. 다나(Danna), 로스버그(Rothberg), 르 파프(Le Pape)의 문헌 [6]을 참조하십시오.

  • 'rss'intlinprog'rins'의 아이디어와 국소 분기가 결합된 혼합 절차를 적용하여 실현 가능한 정수 해를 찾습니다.

  • 'round'intlinprog는 한 노드에서 완화된 문제의 LP 해를 얻습니다. 이 옵션은 실현가능성을 유지하기 위한 방법으로 정수 성분을 반올림합니다.

  • 'diving'intlinprog는 분기한정 스텝과 유사한 발견법을 사용하되, 다른 분기를 만들지 않고 트리에서 바로 아래에 있는 분기를 따릅니다. 이 단일 분기는 트리 조각 아래로 신속한 “급강하”를 초래하기 때문에 “급강하(Diving)”라는 이름이 붙었습니다. 현재, intlinprog는 상대적인 간격이 5%보다 작은 정수 실현가능점을 얻거나 너무 많은 시간을 소비하기 전까지 다음 여섯 가지 급강하 발견법을 순서대로 사용합니다.

    • 벡터 길이 급강하

    • 계수 급강하

    • 부분 급강하

    • 의사 비용 급강하

    • 직선 탐색 급강하

    • 유도 급강하(intlinprog가 이미 최소 하나의 정수 실현가능점을 구한 경우에 적용됨)

    급강하 발견법은 일반적으로 정수 값을 갖는 것으로 예상되는 하나의 변수를 선택합니다. 이에 대한 현재 해는 소수입니다. 그런 다음 변수가 정수 값을 갖도록 강제하는 범위를 추가하고 연관된 완화된 LP를 다시 풉니다. 급강하 발견법 간의 주요 차이점은 범위에 대한 변수를 선택하는 방법에 있습니다. 베르톨드(Berthold)의 문헌 [4], 섹션 3.1을 참조하십시오.

  • 'rss-diving' 또는 'rins-diving'intlinprog는 먼저 'diving'을 시도한 후 (필요한 경우) 명명된 발견법('rins' 또는 'rss')을 시도합니다.

  • 'round-diving'intlinprog는 먼저 'round'를 시도한 후 (필요한 경우) 'diving'을 시도합니다.

  • 'none'intlinprog는 실현가능점을 찾지 않습니다. 단순히 분기한정 탐색에서 발견되는 실현가능점을 사용합니다.

'intermediate' 설정과 'advanced' 설정은 시간을 절약할 수 있을 법한 순서로 다양한 발견법을 실행합니다. 'round''diving' 모두 상대적으로 빠른 절차이며, 그중 하나가 성공하면 솔버가 발견법 실행 시도를 중지합니다.

각 발견법마다 고유한 중지 기준이 있을 수 있습니다. 예를 들어, HeuristicsMaxNodes 기준은 'rss' 발견법과 'rins' 발견법에만 적용됩니다.

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

x0 인수를 포함시키는 경우 intlinprog는 발견법에 이 값을 사용합니다. 특히, rins 및 유도 급강하와 같은 향상 발견법은 x0에서 시작하여 점을 향상시키려고 시도할 수 있습니다. 따라서 x0을 제공할 때 'Heuristics' 옵션을 'rins-diving'으로 설정하는 것이 효과적일 수 있습니다. 하지만, 간격이 작으면 발견법이 실행되지 않으므로 'rins-diving'을 선택하는 것이 항상 실행 시간을 향상시키는 것은 아닙니다.

분기한정(Branch-and-Bound)

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

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

fTxfeas ≥ fTx,

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

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

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

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

  • 'maxpscost' — 최대 의사 비용을 갖는 소수 변수를 선택합니다.

     의사 비용(Pseudocost)

  • '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)에 대해 pi 및 pi+ 중 더 작은 값을 더한다는 것을 의미합니다. 여기에는 다음이 성립합니다.

    pi = x(i) – ⌊x(i)⌋
    pi+ = 1 – pi.

  • 'simplebestproj'최적의 투영을 갖는 노드를 선택합니다.

     최적의 투영

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

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

  • 알고리즘이 MaxTime 옵션을 초과합니다.

  • 목적 함수의 하한과 상한 사이의 차이가 AbsoluteGapTolerance 허용오차 또는 RelativeGapTolerance 허용오차보다 작습니다.

  • 탐색된 노드 개수가 MaxNodes 옵션을 초과합니다.

  • 정수 실현가능점 개수가 MaxFeasiblePoints 옵션을 초과합니다.

분기한정 절차에 대한 자세한 내용은 넴하우저(Nemhauser)와 울시(Wolsey)의 문헌 [8] 및 울시의 문헌 [10]을 참조하십시오.

참고 문헌

[1] Achterberg, T., T. Koch and A. Martin. Branching rules revisited. Operations Research Letters 33, 2005, pp. 42–54. Available at https://www-m9.ma.tum.de/downloads/felix-klein/20B/AchterbergKochMartin-BranchingRulesRevisited.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] Mészáros C., and Suhl, U. H. Advanced preprocessing techniques for linear and quadratic programming. OR Spectrum, 25(4), pp. 575–595, 2003.

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

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

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