절단면법

수학적 최적화에서 절단면 방법은 선형 불평등, 즉 절단을 통해 실현 가능한 세트 또는 객관적 기능을 반복적으로 정제하는 다양한 최적화 방법 중 하나이다.이러한 절차는 일반적으로 혼합 정수 선형 프로그래밍(MILP) 문제에 대한 정수 해결책을 찾는 데 사용되며, 반드시 다를 수 있는 볼록 최적화 문제를 해결할 수 있는 것은 아니다.MILP를 해결하기 위해 절단면을 사용한 것은 랄프 고모리(Ralph E. Gomory)에 의해 소개되었다.

MILP에 대한 절단면 방법은 주어진 정수 프로그램의 선형 완화인 비정수 선형 프로그램을 해결함으로써 작동한다.선형 프로그래밍 이론은 가벼운 가정(선형 프로그램이 최적의 솔루션을 가지고 있고 실현 가능한 영역이 선을 포함하지 않는 경우)에서 항상 최적의 극단점이나 구석점을 찾을 수 있다고 지시한다.얻어진 최적치는 정수용액인지 시험한다.그렇지 않다면 진정한 실현 가능한 세트의 볼록한 선체와 최적기를 분리하는 선형 불평등이 존재한다고 보장한다.그런 불평등을 찾는 것이 분리 문제다, 그런 불평등을 찾는 것은 컷이다.이완된 선형 프로그램에 컷을 추가할 수 있다.그렇다면, 현재의 비임계자 해법은 더 이상 이완에 실현 가능하지 않다.최적의 정수용액을 찾을 때까지 이 과정을 반복한다.

일반적인 볼록 연속 최적화 및 변형을 위한 절단면 방법은 켈리의 방법, 켈리-체니-골드스타인 방법, 번들 방법 등 다양한 이름으로 알려져 있다.그것들은 비차별성 볼록 최소화에 널리 사용되며, 볼록 객관적 기능과 그 하위 등급은 효율적으로 평가될 수 있지만 차별성 최적화를 위한 일반적인 구배 방법은 사용할 수 없다.이러한 상황은 라그랑지안 이중 기능의 오목한 최대화에 가장 전형적이다.또 다른 공통적인 상황은 단치히-의 적용이다.Wolfe 분해는 기하급수적인 수의 변수를 갖는 제형이 얻어지는 구조화된 최적화 문제.지연된 칼럼 생성을 통해 이러한 변수를 온디맨드 방식으로 생성하는 것은 각각의 이중 문제에서 절단면을 수행하는 것과 동일하다.

고모리 컷

절단기는 1950년대 랄프 고모리 감독이 정수 프로그래밍과 혼합정수 프로그래밍 문제를 해결하기 위한 방법으로 제안했다.그러나 고모리 본인을 비롯한 대부분의 전문가들은 해법으로 진척되기 위해서는 여러 차례의 삭감이 필요했기 때문에 수적 불안정성 때문에 비현실적일 뿐만 아니라 비효과적이라고 여겼다.1990년대 중반 제라드 코르누에졸스와 동료들이 그들이 지점과 행선(일명 지점과 컷)과 수적 불안정성을 극복하는 방법들을 결합하여 매우 효과적이라는 것을 보여주었을 때 상황은 반전되었다.요즘은 모든 상용 MILP 해결사들이 고모리 컷을 이런저런 방법으로 사용하고 있다.고모리 컷은 심플렉스 테이블라우에서 매우 효율적으로 생성되는 반면, 다른 많은 유형의 컷은 비용이 많이 들거나 심지어 분리하기가 NP 하드다.MILP에 대한 다른 일반적인 삭감들 중에서 가장 주목할 만한 것은 인양과 프로젝트가 고모리 감소를 지배하고 있다는 것이다.^[1][2]

다음과 같이 정수 프로그래밍 문제를 공식화(정규적 형식)하도록 한다.

${\displaystyle {\begin{aigned}{\text{Maximize }}&c^{T}x\\{\text}{{\text}{{}}}}{}}}}{}&Ax\leq b,\&x\geq 0,\,x_{i}{\text}}}}에 종속됨.\end{정렬}}}$

방법은 먼저 x가_i 정수라는 요구사항을 삭제하고, 기본적인 실현 가능한 해결책을 얻기 위해 관련 선형 프로그래밍 문제를 해결하는 것으로 진행된다.기하학적으로 이 용액은 실현 가능한 모든 점들로 구성된 볼록 폴리토프의 꼭지점이 될 것이다.이 꼭지점이 정수점이 아닌 경우, 한 쪽에는 꼭지점이 있고 다른 쪽에는 모든 가능한 정수점이 있는 하이퍼플레인(hyperplane)을 찾을 수 있다.그런 다음 발견된 정점을 제외하기 위한 추가 선형 제약조건으로 추가되어 수정된 선형 프로그램을 만든다.이후 새로운 프로그램이 해결되고 정수 해법이 나올 때까지 과정이 반복된다.

선형 프로그램을 풀기 위해 심플렉스 방법을 사용하면 형식의 방정식 집합이 생성된다.

${\displaystyle x_{i}+\sum {\bar{a}}_{i,j}x_{j}={\bar}_{i}}}$

여기서 x는_i 기본 변수, x는_j 비기본 변수다.정수 부분이 왼쪽에 있고 분수 부분이 오른쪽에 있도록 이 방정식을 다시 쓰십시오.

${\displaystyle x_{i}+\sum \lfloor {\bar {a}}_{i,j}\rfloor x_{j}-\lfloor {\bar {b}}_{i}\rfloor ={\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor -\sum ({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}.}$

실현 가능한 영역의 정수 점에 대해 이 방정식의 오른쪽은 1 미만이고 왼쪽은 정수이므로 공통 값은 0보다 작거나 같아야 한다.그래서 불평등

${\displaystyle {\b}_{i}-\lfloor {\bloor {b}_{b}_{i}-\llloor {\bar{a}_{i}\loor )x_{j}\leq 0}$

실현 가능한 영역의 정수점을 유지해야 한다.또한, 비기본 변수는 모든 기본 솔루션에서 0s와 같으며, x가_i 기본 솔루션 x에 대한 정수가 아닐 경우,

${\displaystyle {\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor -\sum ({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}={\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor >0.}$

따라서 위의 불평등은 기본적인 실현 가능한 해결책을 배제하고 따라서 원하는 성질을 가진 절단이다.이 불평등에 대해 새로운 느슨한 변수 x를_k 도입하면 선형 프로그램에 새로운 제약조건이 추가된다.

${\displaystyle x_{k}+\sum (\lfloor {\bar {a}}_{i,j}\rfloor -{\bar {a}}_{i,j})x_{j}=\lfloor {\bar {b}}_{i}\rfloor -{\bar {b}}_{i},\,x_{k}\geq 0,\,x_{k}{\mbox{ an integer}}.}$

볼록 최적화

절단면 방법은 비선형 프로그래밍에도 적용된다.기본 원리는 닫힌 반공간의 유한 집합에 의해 비선형(콘벡스) 프로그램의 실현 가능한 영역을 근사하고 근사 선형 프로그램의 순서를 해결하는 것이다.

참고 항목

• 벤더스 분해
• 분기 및 절단
• 분기 및 바운드
• 열생성
• 단치히-울프 분해

참조

• Marchand, Hugues; Martin, Alexander; Weismantel, Robert; Wolsey, Laurence (2002). "Cutting planes in integer and mixed integer programming". Discrete Applied Mathematics. 123 (1–3): 387–446. doi:10.1016/s0166-218x(01)00348-1.
• 아브리엘, 모르드카이(2003)비선형 프로그래밍: 분석 및 방법도버 퍼블리셔스.ISBN 0-486-43227-0
• 코르네홀스, 제라드(2008)혼합 정수 선형 프로그램에 대한 유효한 불평등.수학 프로그래밍 Ser. B, (2008) 112:3–44. [1]
• 코르네홀스, 제라드(2007)1990년대 고모리 컷의 부활.운영 연구 연보, 제149권(2007), 페이지 63–66.[2]

외부 링크

• "Integer Programming" 섹션 9.8 적용 수학 프로그래밍 제9장 정수 프로그래밍(전체 텍스트).브래들리, 헥스, 마그난티(Addison-Wesley, 1977년)