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 ${ displaystyle A}$ je konečná množina ${ displaystyle G (A)}$ minimálních prvků v sadě

${ displaystyle {x in mathbb {Z} ^ {n}: Ax = 0, x neq 0 } ,}$

v dobře částečné objednávce dne ${ displaystyle mathbb {Z} ^ {n}}$ definován ${ displaystyle x sqsubseteq y}$ když ${ displaystyle x_ {i} y_ {i} geq 0}$ a ${ displaystyle | x_ {i} | leq | y_ {i} |}$ pro všechny i. Například Graverův základ ${ displaystyle A = (1,2,1)}$ 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ě:

${ displaystyle min {f (x) : x v mathbb {Z} ^ {n}, Ax = b, l leq x leq u } .}$

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 ${ displaystyle G (A)}$ z ${ displaystyle A}$, 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í,

${ displaystyle min {wx : x v mathbb {Z} ^ {n}, Ax = b, l leq x leq u } .}$

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 ${ displaystyle G (A)}$ z ${ displaystyle A}$ má následující vlastnost. Za každý proveditelný bod X:

• Buď X je optimální (tj. minimalizuje ${ displaystyle w cdot x}$ vzhledem k omezením);
• Nebo existuje vektor G v ${ displaystyle G (A)}$, takový, že X+G je proveditelné a ${ Displaystyle w cdot (x + g)$ (tj., X lze vylepšit přidáním prvku Graverova základu).

Vzhledem k závažnějšímu základu ${ displaystyle G (A)}$, 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 ${ displaystyle G (A)}$ 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

${ displaystyle min {f (x) : x v mathbb {Z} ^ {n}, Ax = b, l leq x leq u }}$

lze vyřešit pomocí Graverovy báze ${ displaystyle G (A)}$ 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 ${ displaystyle f (x) = součet _ {i = 1} ^ {n} f_ {i} (x_ {i})}$;
• Zejména p-norma ${ displaystyle f (x) = | x | _ {p}}$ 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ů,

${ displaystyle min {wx : x v { mathbb {Z}} _ {+} ^ {l krát m krát n} ,, součet _ {i} x_ {i, j , k} = a_ {j, k} ,, součet _ {j} x_ {i, j, k} = b_ {i, k} ,, součet _ {k} x_ {i, j , k} = c_ {i, j} } ,}$

s ${ displaystyle a_ {j, k}}$, ${ displaystyle b_ {i, k}}$, ${ displaystyle c_ {i, j}}$ nezáporná celá čísla (jejichž maximální hodnota implicitně omezuje všechny proměnné shora). Označit podle ${ displaystyle A}$ (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 ${ displaystyle G (A)}$ 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 ${ displaystyle m_ {1}, tečky, m_ {d}}$, (ne) lineární optimalizace přes ${ displaystyle m_ {1} krát cdots krát m_ {d} krát n}$ 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 ${ displaystyle G (m, n)}$ vážnější základ matice ${ displaystyle A}$ definující univerzální 3 ×m × n výše uvedený problém s tabulkou. Prvky ${ displaystyle G (m, n)}$ 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 ${ displaystyle G (m, n)}$ je nanejvýš G(m). Z toho vyplývá, že základ Graver ${ displaystyle G (m, n)}$ je unie ${ displaystyle {n vyberte g (m)}}$ vhodně vložené kopie základu Graver ${ displaystyle G (m, g (m))}$. 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í ${ displaystyle G (m, n)}$. Na úrovni k této hierarchie, pojďme ${ displaystyle G_ {k} (m, n)}$ být podmnožinou ${ displaystyle G (m, n)}$ skládající se pouze z těch prvků typu k; použijte tuto aproximaci ${ displaystyle G_ {k} (m, n)}$ 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 ${ displaystyle G_ {k} (m, n)}$ Graverova základu má polynomiální mohutnost ${ displaystyle O left (m ^ {g (k)} n ^ {k} right)}$ 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 ${ displaystyle O left (n ^ {g} right)}$ 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 ${ displaystyle G (A)}$ aniž by výslovně konstruoval Graverův základ, v kubickém čase ${ displaystyle O left (n ^ {3} right)}$ 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