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

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

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

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

существует оптимальное целочисленное двойственное решение. ^{[1] [2] [3]}

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

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

Ссылки

1. Giles, FR; WR Pulleyblank (1979). «Полная двойная целочисленность и целочисленные многогранники». Линейная алгебра и ее приложения . 25 : 191–196. doi : 10.1016/0024-3795(79)90018-1 .
2. Эдмондс, Дж .; Р. Джайлс (1977). «Отношение минимума-максимума для субмодулярных функций на графах». Анналы дискретной математики . 1 : 185–204.
3. Schrijver, A. (1981). «О полной дуальной целостности». Линейная алгебра и ее приложения . 38 : 27–32. doi : 10.1016/0024-3795(81)90005-7 .
4. Чекури, К. «Конспекты лекций по комбинаторной оптимизации» (PDF) .