벤더 분해

이 글은 일반적인 참고문헌 목록을 포함하고 있지만, 그에 상응하는 인라인 인용구가 충분하지 않다. 좀 더 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오.(2020년 9월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

벤더 분해(또는 벤더의 분해)는 특수한 블록 구조를 가진 매우 큰 선형 프로그래밍 문제의 해답을 가능하게 하는 수학적 프로그래밍의 기법이다.이 블록 구조는 불확실성이 일반적으로 시나리오로 표현되기 때문에 확률적 프로그래밍과 같은 애플리케이션에서 종종 발생한다.이 기술은 자크 F의 이름을 따서 명명되었다. 벤더스.

벤더스 부패의 이면에 있는 전략은 분할과 재무로 요약할 수 있다.즉, Benders 분해에서는 원래 문제의 변수를 두 개의 하위 집합으로 나누어 1단계 마스터 문제가 첫 번째 변수 집합에 걸쳐 해결되며, 두 번째 변수 집합에 대한 값은 주어진 1단계 솔루션에 대한 2단계 하위 문제에서 결정된다.하위 문제가 고정된 1단계 결정이 실제로 실현 불가능한 것으로 판단되면, 이른바 벤더스 컷(Benders cut)이 생성되어 마스터 문제에 추가되며, 컷(cut)이 생성되지 않을 때까지 재솔루션된다.벤더스 분해는 용액을 향해 진행하면서 새로운 제약을 추가하기 때문에, 그 접근법을 "행 발생"이라고 부른다.대조적으로 단치히-울프 분해는 "기둥 생성"을 사용한다.

방법론

두 개 이상의 단계에서 발생하는 문제를 가정하고, 이후 단계에 대한 결정은 이전 단계의 결과에 의존한다.1단계 의사결정에 대한 시도는 이후 단계 결정에 따른 최적성에 대한 사전 지식 없이 이루어질 수 있다.이 1단계 결정은 가장 큰 문제다.이후 추가 단계는 별도의 하위 문제로 분석할 수 있다.이러한 하위 문제로부터 얻은 정보는 다시 마스터 문제로 전달된다.하위 문제에 대한 제약 조건이 위반된 경우 마스터 문제에 다시 추가할 수 있다.그리고 나서 마스터 문제가 다시 해결된다.

마스터 문제는 하위 문제에서 수집된 정보에 의해 추가로 제약되는 초기 볼록 세트를 나타낸다.실현 가능한 공간은 정보가 추가될 때만 축소되기 때문에 마스터 함수의 객관적 값은 전체 문제의 객관적 기능에 대한 하한을 제공한다.

벤더 분해는 블록 대각선 구조의 문제에 적용된다.

수학적 공식

다음 구조의 문제를 가정해 보십시오.

${\displaystyle {\begin{aligned}&{\text{minimize}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} +\mathbf {d} ^{\mathrm {T} }\mathbf {y} \\&{\text{subject to}}&&A\mathbf {x} +B\mathbf {y} \geq \mathbf {b} \\&&&y\in Y\\&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}}$

여기서 ${\displaystyle A}$, B ${\displaystyle A,B}$이$($가) 변수의 두 단계가 공유하는 제약 조건을 나타내고$$, $Y{\displaystyle }$ ${\$에 대해 실현 가능한 $집합$을 나타내는$$ 경우$.$ 모든 $고정{\displaystyle \stackrel{}{\mathbf{}}}$ y${\displaystyle \stackrel{}{\mathbf{}}\in }$ Y ${\displaystyle \mathbf {\\}$에 대해 \$y}$$\in$ Y$},$ 잔류 문제가 있다.

${\displaystyle {\begin{aligned}&{\text{minimize}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} +\mathbf {d} ^{\mathrm {T} }\mathbf {\bar {y}} \\&{\text{subject to}}&&A\mathbf {x} \geq \mathbf {b} -B\mathbf {\bar {y}} \\&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}}$

잔류 문제의 이중성은

${\displaystyle {\begin{aligned}&{\text{maximize}}&&(\mathbf {b} -B\mathbf {\bar {y}} )^{\mathrm {T} }\mathbf {u} +\mathbf {d} ^{\mathrm {T} }\mathbf {\bar {y}} \\&{\text{subject to}}&&A^{\mathbf {T} }\mathbf {u} \leq \mathbf {c} \&&\mathbf {u} \geq \mathbf {0} \ended}}}}}$

잔류 문제의 이중 표현을 사용하여 원래의 문제를 등가 미니맥스 문제로 다시 작성할 수 있다.

${\displaystyle \min _{\mathbf {y} \in Y}\left[\mathbf {d} ^{\mathrm {T} }\mathbf {y} +\max _{\mathbf {u} \geq \mathbf {0} }\left\{(\mathbf {b} -B\mathbf {y} )^{\mathrm {T} }\mathbf {u} \mid A^{\mathrm {T} }\mathbf {u} \leq \mathbf {c} \right\}\right].}$

벤더 분해는 최대화 문제로부터 패스백 메커니즘을 통해 생성된 일련의 컷백 제약조건을 제외하고 내부 문제를 고려하지 않고$$ y ${\$의 연속적인 $값$을 선택하는 반복적 절차에 의존한다.미니맥스 공식은${\displaystyle }$(${\displaystyle u\mathbf{}}$, ${\displaystyle y\mathbf{}}$) ${\displaystyle (\mathbf {u} ,\mathbf {y$의 용어로 작성되지만, $최적$의 y${\$\$mathbf {\bar$${y}}$에 $해당$하는 x ${\$$ma$$\\}$을($으{\displaystyle \stackrel{}{\mathbf{}}}$)로 원래 문제를 해결하면 찾을 수 있다$$$.$$thbf {\bar {y}$ 고정$$.

마스터 문제 공식화

1단계 문제에 대한 결정은 더 작은 최소화 문제로 설명될 수 있다.

${\displaystyle {\begin{ligned}>{\textimize}&#&#{{\text{cuts}\}\&#&#mathbf {y}in Y\\\\\ended}}}}}$

처음에는 컷 세트가 비어 있다.이 마스터 문제를 해결하면 $z{\displaystyle \mathbf{}}$ ${\$의 값이 아래에 바인딩되지$$ 않고 $y{\displaystyle \mathbf{}}$ ${\$이(가) 실행 가능한 값을 갖는$$ 등 전체 문제에 대한 최적의 해결책에서 "첫 번째 추측"을 구성하게 된다.

컷 세트는 미니맥스 제형의 내부 최대화 문제를 해결함으로써 일련의 반복으로 채워질 것이다.두 컷 모두 마스터 문제를 최적의 $y{\displaystyle \mathbf{}}$ ${\$있는 경우)로 안내하고, 전체 문제에 $대해{\displaystyle \mathbf{}}$ y ${\$이(가) 실현 가능한지 확인한다$$.$컷{\displaystyle \mathbf{}}$ 집합은 $y{\displaystyle \mathbf{}}$ ${\$z ${\$ 및$$암시적으로 $x{\displaystyle \mathbf{}}$ ${\$ 사이의 관계를 정의한다$.$

$z{\displaystyle }$ ${\displaystyle z}$의 값은 구속되지 않고$$ 실행 가능한 공간이 축소될 수 있다는 의미인 각 반복에 제약 조건만 추가하므로, 모든 반복에서 마스터 문제의 값은 전체 문제에 대한 해결책에 대한 하한을 제공한다.일부 $"{\$의 경우$$ 마스터 문제의 객관적 값이 내부 문제의 최적 값과 같다면 이중성 이론에 의해 솔루션이 최적이다.

하위 문제 공식화

하위 문제는 제안된 솔루션 $y$의${\$를) 마스터 문제로$$ 간주하고 미니맥스 공식에서 내부 최대화 문제를 해결한다.내부 문제는 이중 표현을 사용하여 공식화된다.

${\displaystyle {\begin{aligned}&{\text{maximize}}&&(\mathbf {b} -B\mathbf {\bar {y}} )^{\mathrm {T} }\mathbf {u} +\mathbf {d} ^{\mathrm {T} }\mathbf {\bar {y}} \\&{\text{subject to}}&&A^{\mathbf {T} }\mathbf {u} \leq \mathbf {c} \&&\mathbf {u} \geq \mathbf {0} \ended}}}}}$

마스터 문제가 문제의 가치에 대한 하한을 제공하는 반면, 하위 문제는 상한선을 얻기 위해 사용된다.주어진 $y$의 ${\$에 대한 하위 문제를 해결한 결과는 극한점 ${\$$bar$${u}}$을(를) 찾을 수 있는$$ 유한 최적값이 될 수 있으며$$, 극한점 $'{\displaystyledatabf$ {$u}$에 대한$$ 무한 솔루션이다$.$세션 콘을 찾을 수도 있고, 또는 그 하위 문제가 실현 불가능하다는 것을 발견할 수도 있다.

절차

높은 수준에서 이 절차는 반복적으로 마스터 문제와 하위 문제를 고려할 것이다.각 반복은 최적의 목표 값에 대한 상한과 하한을 제공한다.하위 문제의 결과는 마스터 문제에 추가하기 위한 새로운 제약조건이나 문제에 대해 유한한 최적 솔루션이 존재하지 않는 인증서를 제공한다.유한 최적 용액이 존재하지 않는다는 것이 입증되거나 상한과 하한 사이의 간격이 충분히 작을 때 절차는 종료된다.이 경우 $x$의 값${\$는) 원시 잔존 문제 해결 ${\$에 따라 결정된다$.$

정식으로$,{\displaystyle }$ 절차는 하한 설정인 ${\displaystyle inf}$ ${\displaystyle -\inf$ $\},$ 상한 설정인 ${\displaystyle inf}$ ${\displaystyle \inf$ $\},$ 컷인 마스터 문제에서 빈 상태로 시작한다.초기 솔루션은 ${\displaystyle y}$의${\displaystyle \stackrel{}{\mathbf{}}\in }$ Y ${\displaystyle \mathbf {\bar {y}$\in $Y}$을(를) 선택하여 생성되며$,$ 이후 반복적인 절차가 시작되어 상한과 하한 사이의 간격이 최대 ${\displaysty \epsilon$}인 경우$$ 또는 유한 최적 솔루션이 존재하지 않는 것으로 나타날 때까지 계속된다.

각 반복의 첫 단계는 가장 최근의 값인 y${\displaystyle \stackrel{}{\mathbf{\text{'}}}}$의 ${\$을(를) 주어진 하위 문제를 해결함으로써 상한을 갱신하는 것으로 시작된다$.$

첫 번째 경우, 하위 문제의 객관적 가치는 위에서 무한하다.이중성 이론에 따르면, 이중 문제가 무한의 목표를 가지고 있을 때 해당 원시적 문제는 실현 불가능하다.This means that the choice of ${\displaystyle \mathbf {\bar {y}} }$ does not satisfy ${\displaystyle A\mathbf {x} +B\mathbf {\bar {y}} \geq \mathbf {b} }$ for any ${\displaystyle \mathbf {x} \geq \mathbf {0} }$. This solution can be removed from the master problem by taking an extreme ray ${\displaystyle \mathbf {\bar {u}} }$ that certifies the subproblem has unbounded objective and adding a constraint to the master asserting that ${\displaystyle (\mathbf {b} -B\mathbf {y} )^{\mathrm {T} }\mathbf {\bar {u}} \leq \mathbf {0} }$.

두 번째 경우에는 부차적인 문제가 실현될 수 없다.문제에 대한 이중의 실현 가능한 공간이 비어 있기 때문에, 원래의 문제는 실현 가능하지 않거나, 원초적 문제에는 객관적 가치를 증명하는 광선이 아래에 한없이 있다.어느 경우든 절차가 종료된다.

세 번째 경우, 하위 문제는 유한한 최적 솔루션을 가진다.$선형$ 프로그램에 대한 이중성 이론에 의해 하위 문제의 최적 값은 $'$의 선택에 제약된 원래 문제의 최적 값과 $동일$하다$.$ 이를 통해 현재 upp보다 우수한 경우 하위 문제의 최적 솔루션 값으로 상한을 업데이트할 수 있다.에르 바운드최적 극한점 $''{\$을$($를) 부여하면, $z{\displaystyle ({}^{}}$ (${\displaystyle {\mathrm{}}^{}}$ -${\displaystyle By\mathbf{}}$ ) ${\displaystyle {T\mathrm{}}^{}}$ ${\displaystyle u^{}\mathbf{}}$ ${\displaystyle u^{}\stackrel{}{\mathbf{}}}$ u u ${\displaystyle {\mathbf{}}^{}}$ u u${\displaystyle }$u u u u u$}\$bf {bf {bf {$bf$ {$y$$}-$mathbf {y$}{$y}{y$}^)$를)를)로 주장함으로써 마스터 문제가 이 특정 솔루션에 따른 객관적 값을 고려해야 하는 새로운$thrm {T} }\mathbf {\bar {u}} +\mathbf {d} ^{\mathrm {T} }\mathbf {y} }$. This will strictly increase the value of ${\displaystyle z}$ at the solution ${\displaystyle \mathbf {\bar {y}} }$ in the master problem if the choice of ${\displaystyle \mathbf {\bar {y}} }$ was suboptimal.

마지막으로, 각 반복의 마지막 부분은 새로운 제약조건으로 마스터 문제를 해결함으로써 마스터 문제에 대한 새로운 해결책을 만드는 것이다.새로운 솔루션$({\displaystyle y}$ "${\displaystyle \stackrel{}{\mathbf{}}}$,${\displaystyle }$z )${\displaystyle(\mathbf {\bar$ {$y},z)$을 사용하여$$ 하한을 업데이트한다.최고 상한과 하한 사이의 간극이${\displaystyle \stackrel{}{\mathbf{}}}$${\displaystyle \epsilon}$보다 작으면 절차가 $종료$되고 x ${{\$$displaystyle \mathbf{\bar$$}}}$의 값은 $원시{\displaystyle \stackrel{}{\mathbf{}}}$ 잔존 문제를 해결하여 결정된다$.$ 그렇지 않으면 절차가 계속된다$.$es 다음 반복으로 넘어가다.

참고 항목

• FortSP 해결사는 확률적 프로그래밍 문제를 해결하기 위해 Benders 분해를 사용한다.

참조

• Benders, J. F. (1962년 9월), "다변수 프로그래밍 문제 해결을 위한 분할 절차", Numische Matheik 4(3): 238–252.
• Lasdon, Leon S. (2002), Optimization Theory for Large Systems (reprint of the 1970 Macmillan ed.), Mineola, New York: Dover Publications, pp. xiii+523, MR 1888251.