Полная двойная целостность - Total dual integrality

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

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

{ displaystyle { begin {align} && max c ^ { mathrm {T}} x && Ax leq b, end {выравнивается}}}

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

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

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

Рекомендации

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

[gilesPulleyblank-1] а ^б Giles, F.R .; W.R. Pulleyblank (1979). «Полная двойственная целостность и целочисленные многогранники». Линейная алгебра и ее приложения. 25: 191–196. Дои:10.1016/0024-3795(79)90018-1.

[EdmondsGiles-2] а ^б Эдмондс, Дж.; Р. Джайлз (1977). «Отношение min-max для субмодульных функций на графиках». Анналы дискретной математики. 1: 185–204.

[3] Шрайвер А. (1981). «О полной двойной целостности». Линейная алгебра и ее приложения. 38: 27–32. Дои:10.1016/0024-3795(81)90005-7.

[4] Чекури, К. «Лекционные заметки по комбинаторной оптимизации» (PDF).

[1]

[2]

[3]

[4]