Vážnější základ - Graver basis - Wikipedia
v aplikovaná matematika, Vážnější základny umožnit iterační řešení lineárních a různých nelineárních celočíselné programování problémy v polynomiální čas. Byli představeni Jack E. Graver.[1] Jejich souvislost s teorií Gröbnerovy základny byl projednán uživatelem Bernd Sturmfels.[2] Algoritmickou teorii Graverových bází a její aplikaci na celočíselné programování popisuje Shmuel Onn.[3][4]
Formální definice
The Vážnější základ z m × n celočíselná matice je konečná množina minimálních prvků v sadě
v dobře částečné objednávce dne definován když a pro všechny i. Například Graverův základ skládá se z vektorů (2, −1,0), (0, −1,2), (1,0, −1), (1, −1,1) a jejich negací.
Řešení celočíselného programování pomocí Graverových bází
Programování celého čísla je problém optimalizace lineární nebo nelineární objektivní funkce přes množinu celočíselných bodů splňujících systém lineárních nerovností. Formálně jej lze napsat ve standardní formě následovně:
Jedná se o jeden z nejzásadnějších problémů diskrétní optimalizace a má velmi širokou modelovací sílu a četné aplikace v různých oblastech, ale obvykle je výpočetně velmi tvrdý, jak je uvedeno níže. Vzhledem k základu Graver z , problém s lineárními a různými nelineárními objektivními funkcemi lze vyřešit v polynomiálním čase, jak je vysvětleno dále.
Lineární celočíselné programování
Nejvíce studovaný případ, důkladně ošetřený,[5] je to z lineární celočíselné programování,
Lze předpokládat, že všechny proměnné jsou omezeny zdola i shora: takové hranice se buď přirozeně objevují v dané aplikaci, nebo je lze vynutit bez ztráty optimálních řešení. Ale i při lineárních objektivních funkcích je problém NP-tvrdý, a proto ho pravděpodobně nelze vyřešit v polynomiálním čase.
Základ Graver z má následující vlastnost. Za každý proveditelný bod X:
- Buď X je optimální (tj. minimalizuje vzhledem k omezením);
- Nebo existuje vektor G v , takový, že X+G je proveditelné a (tj., X lze vylepšit přidáním prvku Graverova základu).
Vzhledem k závažnějšímu základu , ILP umět být vyřešen v polynomiálním čase pomocí následujícího jednoduchého iteračního algoritmu.[3][6] Předpokládejme nejprve, že nějaký počáteční proveditelný bod X je dáno. I když je to možné, opakujte následující iteraci: najít kladné celé číslo q a prvek G v takhle X + qg neporušuje hranice a poskytuje nejlepší možné zlepšení; Aktualizace X := X + qg a přejděte k další iteraci. Poslední bod X je optimální a počet iterací je polynomický.
K nalezení počátečního proveditelného bodu lze podobným způsobem nastavit a vyřešit vhodný pomocný program.
Nelineární celočíselné programování
Pokud jde o případ obecných objektivních funkcí F, pokud jsou proměnné neomezené, může být problém ve skutečnosti nepočítatelný: vyplývá to z řešení Hilbertův 10. problém (vidět [7]), že neexistuje žádný algoritmus, který by vzhledem k celočíselnému polynomu F stupně 8 v 58 proměnných, rozhodne, zda je minimální hodnota f na všech 58-rozměrných celočíselných vektorech 0. Když jsou však proměnné ohraničené, problém
lze vyřešit pomocí Graverovy báze v polynomiálním čase pro několik nelineárních objektivních funkcí včetně[Citace je zapotřebí ]:
- Oddělitelné-konvexní funkce formuláře ;
- Zejména p-norma pro každé kladné celé číslo p;
- Kompozitní-konkávní funkce F(X) = G(Šx), kde Ž je d × n celočíselná matice s d pevné a kde G je d-měnit konkávní funkci;
- Určitý (in) -definite kvadratický a polynom vyššího stupně funkce.
Některé aplikace
Vícedimenzionální tabulky
Zvažte následující problém s optimalizací na trojrozměrných tabulkách s předepsanými součty řádků,
s , , nezáporná celá čísla (jejichž maximální hodnota implicitně omezuje všechny proměnné shora). Označit podle (lm + ln + mn) × (lmn) definující matici tohoto systému. Všimněte si, že tato matice je obecně ne naprosto unimodulární. Nicméně, to bylo uvedeno v [8] to pro každou pevnou l a m, jeho vážnější základ lze vypočítat v čase, ve kterém je polynomn. Výsledky uvedené výše umožňují tento problém vyřešit v polynomiálním čase pro fixní l a m a variabilní n. Všimněte si, že pokud jen jedna strana l tabulky je pevná (i s l = 3) zatímco oba m a n jsou variabilní, pak je problém NP těžký, jak je uvedeno v.[9] Obecněji platí, že podobné pozitivní výsledky platí pro problémy s vícerozměrnými tabulkami (zavedené v [10]): pro každou pevnou d a , (ne) lineární optimalizace přes tabulky s proměnnou n a předepsanými okraji lze provádět v polynomiálním čase. To má další aplikace pro zadávání bezpečnostních problémů a soukromí ve statistických databázích.
Multikomoditní toky
Zvažte celé číslo problém multikomoditního toku směrování k typy celých komodit z m dodavatelé n spotřebitelé podléhající omezením nabídky, spotřeby a kapacity, aby se minimalizoval součet konvexních nákladů lineárních nebo kongesčních v závislosti na přetížení na obloucích. Pak pro každou pevnou k a mlze vypočítat Graverův základ definujícího systému a výslednou separovatelně konvexní objektivní funkci minimalizovat v čase, který je polynomem v proměnném počtu n spotřebitelů a ve zbytku údajů.
Další aplikace
Mnoho aplikací algoritmické teorie Graverových bází také zahrnuje:
- stochastické celočíselné programování,[6]
- N-násobné celočíselné programování,
- N- skládací 4-blokové rozložitelné celočíselné programování,[11]
- shlukování,
- kontrola zveřejňování ve statistických databázích,
- a spravedlivé rozdělení nedělitelných předmětů.[12]
V některých z těchto aplikací je použit závažnější základ nemůže být vypočítán v polynomiálním čase, ale lze k nim přistupovat nepřímo, což umožňuje jeho použití v polynomiálním čase.
Univerzálnost a parametrizace
Bylo ukázáno v [13] že každý (ohraničený) celočíselný programovací problém je přesně ekvivalentní 3 ×m × n u některých problém diskutovaný výše m a n a některé řádkové částky. Tedy takový 3 ×m × n problémy s tabulkou jsou univerzální pro celočíselné programování. Navíc pro každou pevnou m, výslednou třídu celočíselných programů lze vyřešit v polynomiálním čase iterativní metodou Graverovy báze popsanou výše. Takže šířka stolu m poskytuje a parametrizace všech problémů s celočíselným programováním.
Hierarchie aproximací pro celočíselné programování
Označit podle vážnější základ matice definující univerzální 3 ×m × n výše uvedený problém s tabulkou. Prvky jsou 3 ×m × n tabulky se všemi řádkovými součty rovnými 0. typ takové tabulky je počet nenulových 3 ×m vrstvy. Ukazuje se, že existuje konečná Funkce vážnější složitosti G(m) tak, že pro všechny n, typ libovolného prvku základu Graver je nanejvýš G(m). Z toho vyplývá, že základ Graver je unie vhodně vložené kopie základu Graver . Chcete-li v praxi přibližně vyřešit problém libovolného celočíselného programování, postupujte následovně. Nejprve jej vložte do vhodného 3 ×m × n problém tabulky umožněný výše uvedenou univerzálností. Nyní použijte následující hierarchii aproximací . Na úrovni k této hierarchie, pojďme být podmnožinou skládající se pouze z těch prvků typu k; použijte tuto aproximaci v iteračním algoritmu co nejdéle k získání co nejlepšího možného bodu pro problém celočíselného programování vloženého do 3 ×m × n stolní problém; je-li objektivní hodnota funkce tohoto bodu uspokojivá (řekněme ve srovnání s hodnotou relaxace lineárního programování ), pak použijte tento bod; jinak přírůstek k a přejděte na další úroveň hierarchie. Může se to ukázat [3] že pro jakoukoli pevnou úroveň k, aproximace Graverova základu má polynomiální mohutnost a lze je vypočítat za tolik času.
Opravitelná vlastnost parametru: od polynomiální po kubickou časovou složitost
Časová složitost řešení některých výše diskutovaných aplikací, jako jsou problémy s vícerozměrnými tabulkami, problémy s tokem více akomodit a N-problémy s celočíselným programováním, dominuje mohutnost příslušného Graverova základu, což je polynom s typicky velkým stupněm G což je vhodná Graverova složitost systému. v [14] je představen mnohem rychlejší algoritmus, který při každé iteraci najde nejlepší vylepšení X + qg s q kladné celé číslo a G prvek v aniž by výslovně konstruoval Graverův základ, v kubickém čase bez ohledu na systém. V terminologii parametrizovaná složitost, to znamená, že všechny tyto problémy jsou vhodně parametrizovány, a to zejména l × m × n problémy s tabulkou parametrizované pomocí l a m, jsou fixní parametr.
Viz také
- Gordanovo lemma - další nástroj související s nulovými množinami celočíselných matic.
Reference
- ^ Jack E. Graver: Na základech lineárního a lineárního celočíselného programování, Mathematical Programming 9: 207–226, 1975
- ^ Bernd Sturmfels, Gröbnerovy základny a konvexní polytopy, Americká matematická společnost, xii + 162 stran, 1996
- ^ A b C Shmuel onn: Nelineární diskrétní optimalizace, Evropská matematická společnost, x + 137 stran, 2010
- ^ Shmuel Onn: Lineární a nelineární optimalizace celého čísla Série přednášek o videu online, Výzkumný ústav matematických věd, Berkeley, 2010
- ^ Alexander Schrijver: Teorie lineárního a celočíselného programování, Wiley, xii + 471 stran, 1986
- ^ A b Raymond Hemmecke, Shmuel Onn, Robert Weismantel: Polynomiální věštecko-časový algoritmus pro minimalizaci konvexních celých čísel, Matematické programování 126: 97–117, 2011
- ^ Jurij V. Matijasevič: Hilbertův desátý problém, MIT Press, xxiv + 264 stran, 1993
- ^ Jesús A. De Loera Raymond Hemmecke, Shmuel Onn, Robert Weismantel: N-násobné celočíselné programování, DiscreteOptimization, 5: 231–241, 2008
- ^ Jesús A. De Loera „Shmuel Onn: Složitost třícestných statistických tabulek, SIAM Journal on Computing, 33: 819–836, 2004
- ^ Theodore S. Motzkin: Problém s víceindexovou přepravou, Bulletin of the American Mathematical Society 58: 494, 1952
- ^ Raymond Hemmecke, Matthias Köppe, Robert Weismantel: Algoritmus polynomiálního času pro optimalizaci N- skládací 4-blokové rozložitelné celočíselné programy, IPCO 14, 2010
- ^ Bredereck, Robert; Kaczmarczyk, Andrzej; Knop, Dušan; Niedermeier, Rolf (2019-06-17). „Fair-Allocation High-Multiplicity Fair: Lenstra Empowered by N-fold Integer Programming“. Sborník konferencí ACM o ekonomii a výpočtu z roku 2019. ES19. Phoenix, AZ, USA: Sdružení pro výpočetní techniku: 505–523. doi:10.1145/3328526.3329649. ISBN 978-1-4503-6792-9.
- ^ Jesus A. De Loera, Shmuel Onn: Alllinear and integer programs are slim 3-way transport programs, SIAM Journal on Optimization, 17: 806–821, 2006
- ^ Raymond Hemmecke, Shmuel Onn, Lyubov Romanchuk: N-násobné celočíselné programování v kubickém čase, Mathematical Programming, 137: 325–341, 2013