총 이중 통합성

수학적 최적화에서, 총 이중 통합성은 다면체의 통합성을 위한 충분한 조건이다.따라서 이러한 다면체의 적분점에 대한 선형 목표의 최적화는 선형 프로그래밍의 기법을 사용하여 수행할 수 있다.

${\displaystyle {\mathbb{}}^{}}$ 시스템 $A{\displaystyle }$ x ${\displaystyle \le }$ ${\displaystyle b}$ ${\displaystyle A}$ 및$$ b ${\displaystyle b}$이$($가) 합리적인$$ 선형 시스템 A x ${\displaystyle x}$ b${\displaystyle }${\$displaystyle$ A} 및 b {\displaystyle c$\in \mathb {Z} ^{n$}}}에 대해$$ 선형 프로그램에 대한 실현 가능하고 한정된 솔루션이 있는 경우 완전 이중 적분(TDI)이라고 한다.

${\displaystyle {\begin{aigned}&\max c^{\mathrm {T}} }x\&Ax\leq b,\end{aigned}}}}$

정수 최적 이중 용액이 있다.^[1][2][3]

Edmonds와 Giles는^[2] 다면체 $P{\displaystyle }$ ${\displaystyle P}$이(가) TDI 시스템 $A{\displaystyle }$ ${\displaystyle x}$ x${\displaystyle b}$ b ${\displaystyle Ax\leq b$의 솔루션 집합이라면$$, $여기$서 b ${\displaystyle b$$}$이$($가) 모든 정수 값을 갖는다는$$$$ 것을 보여주었다.따라서 위에서와 같은 선형 프로그램을 심플렉스 알고리즘으로 풀면 반환되는 최적 용액은 정수가 된다.또한, Giles와 Pulleblank는^[1] $P{\displaystyle }$ ${\displaystyle P}$이(가) 모든$$ 정수의 값을 갖는 폴리토프라면, $P{\displaystyle }$ ${\displaystyle P}$은 일부 TDI 시스템 A ${\displaystyle x}$ x x${\displaystyle b}$ b ${\displaysty Ax\leq b}$의 솔루션 집합이며$,$ $여기$서 b ${\displaysty b}$은 정수 값이다.

TDI는 전체 단항성보다 통합성을 위한 충분한 조건이라는 점에 유의하십시오.^[4]

참조