선형 프로그래밍 이완

A(일반) 정수 프로그램 및 해당 LP-완화

수학에서 (혼합) 정수 선형 프로그램의 이완은 각 변수의 통합성 제약조건을 제거함으로써 발생하는 문제다.

예를 들어, 0–1 정수 프로그램에서 모든 제약조건은 형식이다.

x_{i}\in \{0,1\}

x_{i}\in \{0,1\}

x_{i}\in \{0,1\}

x_{i}\in \{0,1\}

{\displaystyle x_{i}\in

\{

0,1

원래 정수 프로그램의 이완은 대신 선형 제약 조건의 집합을 사용한다.

0\leq x_{i}\leq 1.

그 결과로 생기는 이완은 선형적인 프로그램이다, 그래서 이름이 그렇다.이 이완 기법은 NP-하드 최적화 문제(integer programming)를 다항 시간(선형 프로그래밍)에서 해결할 수 있는 관련 문제로 변환한다. 이완된 선형 프로그램에 대한 솔루션은 원래의 정수 프로그램에 대한 해법에 대한 정보를 얻기 위해 사용될 수 있다.

예

로바스(1975)가 처음 고려한 선형 프로그래밍 완화의 세트 커버 문제를 고려한다.이 문제에서 하나는 F = {S₀, S, ...의₁ 집합의 입력으로 주어진다.}; 과제는 F와 동일한 조합을 가진 가능한 적은 수의 세트로 이루어진 하위 패밀리를 찾는 것이다.

이것을 0–1 정수 프로그램으로 공식화하려면, S가_i 선택된 서브 패밀리에 속할 때는 1을, 그렇지 않을 때는 0을 취하는 각 세트 S에_i 대해 표시 변수 x를_i 형성한다.그런 다음 제약을 만족하는 지표 변수에 값을 할당하여 유효한 표지를 설명할 수 있다.

\textstyle x_{i}\in \{0,1\}

(즉, 지정된 지표 변수 값만 허용) 및 F의 조합의 각 요소 e에_j 대해,

\textstyle \sum _{\{i\mid e_{j}\in S_{i}\}x_{i}\geq 1

(즉, 각 원소는 커버된다.)최소 세트 커버는 이러한 제약 조건을 만족하고 선형 목표 함수를 최소화하는 지표 변수 할당에 해당한다.

\textstyle \min \sum _{i}x_{i}.

세트 커버 문제의 선형 프로그래밍 완화는 각 요소를 포함하는 세트의 총 중량이 적어도 하나 이상이고 모든 세트의 총 중량이 최소화되도록 입력 세트에 가중치가 할당되는 부분 커버를 설명한다.

설정된 커버 문제의 특정 예로서 인스턴스 F = {{a, b}, {b, c}, {a, c}}을(를) 고려하십시오.최적 세트 커버는 3개가 있으며, 각각 주어진 세트 3개 중 2개를 포함한다.따라서 해당 0–1 정수 프로그램의 목표함수의 최적값은 최적 커버의 세트 수인 2이다.단, 각 세트에 무게 1/2이 할당되고, 목표함수의 총 값이 3/2인 분수 솔루션이 있다.따라서 이 예에서 선형 프로그래밍 이완은 0–1 정수 프로그램의 그것과 다른 값을 가진다.

느긋하고 독창적인 프로그램의 솔루션 품질

정수 프로그램의 선형 프로그래밍 완화는 표준 선형 프로그래밍 기법을 사용하여 해결할 수 있다.선형 프로그램에 대한 최적 솔루션이 모든 변수를 0 또는 1로 가질 경우, 원래 정수 프로그램에 대한 최적 솔루션이 될 것이다.그러나 일부 특수 사례(예: 완전히 비모형 행렬 사양의 문제)를 제외하고는 일반적으로 사실이 아니다.

그러나 모든 경우에 있어서, 어떤 정수 프로그램 솔루션도 유효한 선형 프로그램 솔루션이 될 것이기 때문에, 선형 프로그램의 솔루션 품질은 적어도 정수 프로그램의 그것만큼 좋다.즉, 최대화 문제에서 완화 프로그램은 원래 프로그램의 값보다 크거나 같은 값을 갖는 반면, 설정 커버 문제와 같은 최소화 문제에서는 완화 프로그램이 원래 프로그램의 값보다 작거나 같은 값을 갖는 것이다.따라서, 그 이완은 정수 프로그램의 해법에 대해 낙관적인 한계를 제공한다.

이완이 3/2의 최적 솔루션 값을 갖는 위에서 설명한 세트 커버 문제의 예에서, 우리는 이완되지 않은 정수 프로그램의 최적 솔루션 값이 적어도 그 만큼 크다고 추론할 수 있다.세트 커버 문제는 정수인 솔루션 값(하위 패밀리에서 선택한 세트 수)을 가지므로 최적 솔루션 품질은 최소한 다음 정수인 2만큼 커야 한다.따라서 이 경우, 완화되지 않은 문제와 다른 가치를 가지고 있음에도 불구하고 선형 프로그래밍 완화는 원래 문제의 솔루션 품질에 대한 엄격한 하한을 제공한다.

근사치 및 통합성 격차

선형 프로그래밍 이완은 하드 최적화 문제에 대한 근사 알고리즘을 설계하기 위한 표준 기법이다.이 애플리케이션에서 중요한 개념은 정수 프로그램의 솔루션 품질과 그 이완 사이의 최대 비율인 통합성 격차다.최소화 문제의 경우, 실제 최소(정수 문제의 최소치)가 M $M_{int}$ t $M_{int}$ {\ $displaystyle M_{int$ 이고, 완화된 최소치(선형 프로그래밍 이완의 $M_{frac}$ )가 M $M_{frac}$ r $M_{frac}$ a c {\ $displaystyle M_{frac}$ 인 경우 $M_{frac}$ 해당 인스턴스의 $IG={\frac {M_{int}}{M_{frac}}}$ 는 I $IG={\frac {M_{int}}{M_{frac}}}$ = $IG={\frac {M_{int}}{M_{frac}}}$ i $IG={\frac {M_{int}}{M_{frac}}}$ $IG={\frac {M_{int}}{M_{frac}}}$ f $IG={\frac {M_{int}}{M_{frac}}}$ 이다. $IG={\frac {M_{int}}{M_{frac}}}$ ${\$ 최대화 문제에서는 분율이 역전된다.통합성 격차는 항상 최소 1이다.위의 예에서 인스턴스 F = {{a, b}, {b, c}, {a, c}}은(는) 4/3의 통합성 차이를 나타낸다.

일반적으로 통합성 간격은 근사 알고리즘의 근사비로 해석된다.근사 알고리즘은 크기 $M_{frac}$ f $M_{frac}$ $M_{frac}$ c $M_{frac}$ {\ $displaystyle M_{frac}$ 의 모든 완화된 용액에 대해 $RR\cdot M_{frac}$ R $RR\cdot M_{frac}$ $RR\cdot M_{frac}$ $RR\cdot M_{frac}$ f $RR\cdot M_{frac}$ a $RR\cdot M_{frac}$ {\ $displaystyle RR\cdot M_{frac}}}($ RRR이 반올림 비율인 경우)의 정수 $M_{frac}$ 용액을 찾아내는 어떤 반올림 전략에 의존하기 때문이다.통합성 갭 IG가 있는 인스턴스가 있는 경우, 모든 라운딩 전략은 최소 $M_{int}=IG\cdot M_{frac}$ $M_{int}=IG\cdot M_{frac}$ = I $M_{int}=IG\cdot M_{frac}$ $M_{int}=IG\cdot M_{frac}$ $M_{int}=IG\cdot M_{frac}$ $M_{int}=IG\cdot M_{frac}$ a $M_{int}=IG\cdot M_{frac}$ ${\$ 크기의 둥근 솔루션을 반환한다. $IG\cdot M_{frac$ 따라서 반드시 $RR\geq IG$ $RR\geq IG$ $RR\geq IG$ $RR\geq IG$ G ${\displaystyle RR\geq IG$ 반올림비 RR는 근사비에 대한 상한에 불과하므로 이론상으로는 실제 근사비가 IG보다 낮을 수 있으나 이는 입증하기 어려울 수 있다.실제로, 큰 IG는 일반적으로 선형 프로그래밍 완화의 근사 비율이 나쁠 수 있으며, 그 문제에 대한 다른 근사 체계를 찾는 것이 더 나을 수 있다.

세트 커버 문제에 대해, 로바스즈는 n번째 원소를 가진 한 인스턴스의 통합성 간격이 n번째 고조파 수인 H라는_n 것을 증명했다.무작위 반올림(Ragavan & Tompson 1987년) 하브 오차: 목표 없음: CITREFRAGhavanTompson1987(도움말)을 통해 이 문제에 대한 선형 프로그래밍 완화를 원래의 미완축 세트 커버 인스턴스의 대략적인 해결책으로 바꿀 수 있다.각 세트 S에_i w중량이_i 있는 부분 표지가 주어진 경우, 각 0–1 지시 변수 x의_i 값을 확률 w_i ×(ln n +1)와 0으로 랜덤하게 선택한다.그러면 어떤 요소 e는_j 덮이지 않은 나머지 1/(e×n) 미만의 확률을 가지므로 일정한 확률로 모든 요소를 덮는다.이 기법에 의해 생성된 커버는 (1+o(1))(ln n)W, 여기서 W는 분수 용액의 총중량이다.따라서 이 기법은 최적 로그 계수 내에서 세트 커버를 찾는 랜덤화된 근사 알고리즘으로 이어진다.영(1995)이 보여주었듯이, 이 알고리즘의 무작위 부분과 선형 프로그래밍 완화에 대한 명시적 해결책의 구성 필요성 모두 조건 확률의 방법을 사용하여 제거할 수 있으며, 이는 이미 Lovász에 알려진 세트 커버에 대한 결정론적 탐욕 알고리즘으로 이어지며, 대형을 커버하는 세트를 반복적으로 선택한다.남은 덮개 없는 원소의 가능한 수이 탐욕스러운 알고리즘은 세트 커버에 대한 통합성 갭으로 Lovász가 입증한 동일한 H 인자_n 내에서 세트 커버에 근사치를 가진다.어떤 다항 시간 근사 알고리즘도 유의하게 더 나은 근사 비율을 달성할 수 없다고 믿는 데는 강한 복잡성-이론적 이유가 있다(Feige 1998).

Raghavan, Tompson 및 Young이 설명한 것처럼, 유사한 무작위 반올림 기법 및 감산된 근사 알고리즘을 선형 프로그래밍 이완과 함께 사용하여 다른 많은 문제에 대한 근사 알고리즘을 개발할 수 있다.

정확한 솔루션을 위한 분기 및 바인딩

선형 프로그래밍은 근사치뿐만 아니라 분기와 결합 알고리즘에서 하드 최적화 문제에 대한 진정한 최적 솔루션을 계산하는 중요한 역할을 한다.

최적 솔루션의 일부 변수가 부분 값을 갖는 경우, 일부 부분 변수가 0 또는 1에 고정된 하위 문제를 재귀적으로 해결하는 분기 및 바운드 유형 프로세스를 시작할 수 있다.이러한 유형의 알고리즘의 각 단계에서, 우리는 원래 0–1 정수 프로그램의 하위 문제를 고려한다. 일부 변수에는 0 또는 1의 값이 할당되어 있고, 나머지 변수는 여전히 두 값 중 하나를 자유롭게 수행할 수 있다.하위 문제 i에서 V가_i 나머지 변수 집합을 나타내도록 한다.프로세스는 변수 값이 할당되지 않았고 V가₀ 원래 문제의 전체 변수 집합인 하위 문제를 고려하는 것으로 시작한다.그런 다음, 각 하위 문제 i에 대해 다음과 같은 단계를 수행한다.

현재 하위 문제의 선형 프로그래밍 완화에 대한 최적의 솔루션을 계산한다.즉, V의_i 각 변수 x에_j 대해 x가_j 0 또는 1인 제약조건을 구간 [0,1]에 있는 완화된 제약조건으로 대체하지만, 이미 값이 할당된 변수는 완화되지 않는다.
현재의 하위 문제의 완화 솔루션이 지금까지 발견된 최상의 정수 솔루션보다 더 나쁘다면, 재귀 검색의 이 분기에서 역추적하십시오.
완화된 용액이 모든 변수를 0 또는 1로 설정한 경우, 지금까지 발견된 최고의 정수 용액에 대해 테스트하고 두 용액 중 가장 적합한 것을 유지하십시오.
그렇지 않은 경우, x는_j 완화된 용액에서 분수 값으로 설정된 변수가 되도록 한다.두 개의 하위 문제를 형성하십시오. 하나는 x가_j 0으로 설정되고 다른 하나는 x가_j 1로 설정되며, 두 하위 문제 모두 일부 변수에 대한 값의 기존 할당이 여전히 사용되므로 나머지 변수 집합은 V_i \ {x_j}이(가) 된다.두 하위 문제를 모두 재귀적으로 검색하십시오.

이러한 유형의 알고리즘 성능에 대한 이론적 한계를 입증하기는 어렵지만, 실제로 매우 효과적일 수 있다.

절삭면법

0–1 정수 프로그램 두 개가 동일한 목적 함수와 동일한 일련의 실현 가능한 솔루션을 가지고 있다는 점에서, 상당히 다른 선형 프로그래밍 완화를 가질 수 있다. 선형 프로그래밍 완화는 모든 실현 가능한 솔루션을 포함하고 다른 0–1 벡터를 제외한 볼록 폴리토프로서 기하학적으로 볼 수 있다.여러 가지 다른 폴리에스테르들이 이 속성을 가지고 있다.이상적으로는 실현 가능한 해결책의 볼록한 선체를 이완시키는 것으로 사용하기를 원한다; 이 폴리토프의 선형 프로그래밍은 원래의 정수 프로그램에 정확한 해결책을 자동으로 산출할 것이다.그러나, 일반적으로 이 폴리토프는 기하급수적으로 많은 면을 가지고 있을 것이고, 구성하기가 어려울 것이다.앞에서 논의한 세트 커버 문제의 이완과 같은 전형적인 이완은 볼록한 선체를 엄격히 포함하는 폴리토프를 형성하며, 풀리지 않는 문제를 해결하는 0–1 벡터 이외의 정점을 가지고 있다.

0–1 정수 계획, 먼저 단치그, Fulkerson &amp에 의해 외판원 문제에 대한 소개를 해결하기 위한cutting-plane 메서드 존슨(1954년)과 다른 정수 프로그램에 Gomory(1958년)에 의해 일반화, 가능한 일종의 소일거리 이 다양성의를 더 꽉 soluti에 제약을 가하는 일종의 소일거리 시퀀스를 찾아내 이용한 것이다.s에결국 정수 용액을 얻을 때까지 속도를 높인다.이 방법은 주어진 프로그램의 어떤 이완으로부터 시작하여, 선형 프로그래밍 해결기를 사용하여 최적의 솔루션을 찾는다.솔루션이 모든 변수에 정수 값을 할당하는 경우, 이는 완화되지 않은 문제에 대한 최적의 해결책이기도 하다.그렇지 않으면, 추가적인 선형 제약(절단면 또는 절단면)이 발견되어 결과적인 분수 용액이 정수 용액의 볼록한 선체와 분리되며, 이 방법은 더 엄격하게 제약된 새로운 문제에 반복된다.

이 방법에서 사용하는 절단을 찾으려면 문제별 방법이 필요하다.특히 정수용액의 볼록한 선체의 면을 형성하는 절단면을 찾는 것이 바람직하다. 이러한 평면들은 용액 공간을 가장 엄격하게 구속하는 평면이기 때문이다. 이러한 유형의 절단면은 정수용액과 어떤 분수용액도 분리하는 것이 항상 존재한다.다면 결합 최적화(Aardal & Weismantel 1997)의 프레임워크 아래에서 다양한 유형의 결합 최적화 문제에 대해 이러한 측면을 찾는 방법에 대해 많은 연구가 수행되었다.

관련 분기 및 절단 방법은 절단면과 분기 및 바운드 방법을 결합한다.하위 문제에서는 절삭면을 더 이상 찾을 수 없을 때까지 절삭면 방법을 실행한 다음, 나머지 부분 변수 중 하나에 분기한다.

참고 항목

그래프 색상의 선형 프로그래밍 완화인 분수 색상.
무작위 반올림. 해결책에서 이완에 이르는 원래 문제에 대한 해결책을 얻기 위한 것이다.

참조

Aardal, Karen; Weismantel, Robert (1997), "Polyhedral combinatorics: An annotated bibliography", Annotated Bibliographies in Combinatorial Optimization (PDF), Wiley.
Agmon, Shmuel (1954), "The relaxation method for linear inequalities", Canadian Journal of Mathematics, 6: 382–392, doi:10.4153/CJM-1954-037-2.
Dantzig, George; Fulkerson, D. R.; Johnson, Selmer (1954), "Solution of a large-scale traveling-salesman problem", Journal of the Operations Research Society of America, 2 (4): 393–410, doi:10.1287/opre.2.4.393.
Feige, Uriel (1998), "A threshold of ln n for approximating set cover", Journal of the ACM, 45 (4): 634–652, CiteSeerX 10.1.1.70.5014, doi:10.1145/285055.285059.
Gomory, Ralph E. (1958), "Outline of an algorithm for integer solutions to linear programs", Bulletin of the American Mathematical Society, 64 (5): 275–279, doi:10.1090/S0002-9904-1958-10224-4.
Lovász, László (1975), "On the ratio of optimal integral and fractional covers", Discrete Mathematics, 13 (4): 383–390, doi:10.1016/0012-365X(75)90058-8.
Motzkin, T. S.; Schoenberg, I. J. (1954), "The relaxation method for linear inequalities", Canadian Journal of Mathematics, 6: 393–404, doi:10.4153/CJM-1954-038-x.
Raghavan, Prabhakar; Thompson, Clark D. (1987), "Randomized rounding: A technique for provably good algorithms and algorithmic proofs", Combinatorica, 7 (4): 365–374, doi:10.1007/BF02579324.
Young, Neal E. (1995), "Randomized rounding without solving the linear program", Proc. 6th ACM-SIAM Symp. Discrete Algorithms (SODA), Soda '95, pp. 170–178, ISBN 9780898713497.

Search