Полная двойная целостность

В математической оптимизации полная двойственная целостность является достаточным условием целостности многогранника . Таким образом, оптимизация линейной цели по целым точкам такого многогранника может быть выполнена с использованием методов линейного программирования .

Линейная система $Ax\leq b$, где $A$ и $b$ рациональны, называется вполне двойственным интегралом (ТДИ), если для любого $c\in \mathbb {Z} ^{n}$ такое, что существует допустимое ограниченное решение линейной программы

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

существует целочисленное оптимальное двойственное решение.

Эдмондс и Джайлз показал, что если многогранник $P$ это набор решений системы TDI $Ax\leq b$, где $b$ имеет все целочисленные записи, то каждая вершина $P$ является целочисленным. Таким образом, если линейная программа, описанная выше, решается с помощью симплексного алгоритма , возвращаемое оптимальное решение будет целочисленным. Далее, Джайлз и Пуллибланк показал, что если $P$ является многогранником, все вершины которого имеют целочисленные значения, тогда $P$ это набор решений некоторой системы TDI $Ax\leq b$, где $b$ имеет целочисленное значение.

Обратите внимание, что TDI является более слабым достаточным условием целостности, чем полная унимодулярность .