Kombinatorická optimalizace - Combinatorial optimization - Wikipedia

A minimální kostra váženého rovinný graf. Nalezení minimálního kostry je běžným problémem zahrnujícím kombinatorickou optimalizaci.

Kombinatorická optimalizace je podpole z matematická optimalizace to souvisí s operační výzkum, teorie algoritmů, a teorie výpočetní složitosti. Má důležité aplikace v několika oblastech, včetně umělá inteligence, strojové učení, teorie dražby, softwarové inženýrství, aplikovaná matematika a teoretická informatika.

Kombinatorická optimalizace je téma, které spočívá v nalezení optimálního objektu z a konečná množina předmětů.^[1] V mnoha takových problémech vyčerpávající vyhledávání není přitažlivý. Funguje na doméně těch optimalizačních problémů, ve kterých je sada proveditelná řešení je oddělený nebo je lze zredukovat na diskrétní a cílem je najít nejlepší řešení. Typickými problémy jsou problém obchodního cestujícího (Dále jen „TSP“) minimální problém s kostrou ("MST") a batoh problém.

Nějaká výzkumná literatura^[2] zvažuje diskrétní optimalizace skládat se z celočíselné programování společně s kombinatorickou optimalizací (která se zase skládá z optimalizační problémy jednat s struktury grafů ) i když všechna tato témata úzce propojují výzkumnou literaturu. Často to zahrnuje určení způsobu, jak efektivně alokovat zdroje používané k hledání řešení matematických problémů.

Aplikace

Mezi aplikace pro kombinatorickou optimalizaci patří mimo jiné:

Logistika^[3]
Optimalizace dodavatelského řetězce^[4]
Rozvoj nejlepší letecké sítě paprsků a destinací
Rozhodování, které taxíky ve flotile se vydají, aby vyzvedly jízdné
Určení optimálního způsobu doručování balíků
Vypracování nejlepšího alokace pracovních míst lidem
Projektování vodovodních sítí
Věda o Zemi problémy (např. nádrž průtoky)^[5]

Metody

Existuje velké množství literatury o algoritmy polynomiálního času pro určité speciální třídy diskrétní optimalizace je její značné množství sjednoceno teorií lineární programování. Některé příklady kombinatorických optimalizačních problémů, které spadají do tohoto rámce, jsou nejkratší cesty a stromy s nejkratší cestou, toky a oběhy, klenout se nad stromy, vhodný, a matroid problémy.

Pro NP-kompletní problémy diskrétní optimalizace, aktuální výzkumná literatura obsahuje následující témata:

polynomiálně přesně řešitelné speciální případy daného problému (viz např fixovatelný parametr )
algoritmy, které fungují dobře v "náhodných" případech (např TSP )
aproximační algoritmy které běží v polynomiálním čase a najdou řešení, které je „blízké“ optimálnímu
řešení skutečných instancí, které vznikají v praxi a nemusí nutně vykazovat nejhorší chování spojené s NP-úplnými problémy (např. instance TSP s desítkami tisíc uzlů^[6]).

Problémy kombinatorické optimalizace lze chápat jako hledání nejlepšího prvku některé sady samostatných položek; tedy v zásadě jakýkoli druh vyhledávací algoritmus nebo metaheuristické lze je použít k jejich vyřešení. Snad nejuniverzálnější přístupy jsou rozvětvené a vázané (přesný algoritmus, který lze kdykoli zastavit, aby sloužil jako heuristika), větev a řez (používá lineární optimalizaci ke generování hranic) dynamické programování (rekurzivní konstrukce řešení s omezeným vyhledávacím oknem) a tabu vyhledávání (chamtivý swapový algoritmus). Není však zaručeno, že obecné vyhledávací algoritmy najdou nejprve optimální řešení, ani že nebudou fungovat rychle (v polynomiálním čase). Protože některé problémy s diskrétní optimalizací jsou NP-kompletní, například problém obchodního cestujícího^{[Citace je zapotřebí ]}, to se očekává, pokud P = NP.

Formální definice

Formálně problém kombinatorické optimalizace ${ displaystyle A}$ je čtyřnásobek^{[Citace je zapotřebí ]} ${ displaystyle (I, f, m, g)}$ , kde

${ displaystyle I}$ je soubor případů;
daný případ ${ displaystyle x v I}$ , ${ displaystyle f (x)}$ je konečný soubor proveditelných řešení;
daný případ ${ displaystyle x}$ a proveditelné řešení ${ displaystyle y}$ z ${ displaystyle x}$ , ${ displaystyle m (x, y)}$ označuje opatření z ${ displaystyle y}$ , což je obvykle a pozitivní nemovitý.
${ displaystyle g}$ je branková funkce a je ${ displaystyle min}$ nebo ${ displaystyle max}$ .

Cílem je pak pro nějaký případ najít ${ displaystyle x}$ an optimální řešení, tj. proveditelné řešení ${ displaystyle y}$ s

{ displaystyle m (x, y) = g {m (x, y ') střední y' ve f (x) }.}

Pro každý problém kombinatorické optimalizace existuje odpovídající rozhodovací problém to se ptá, zda existuje proveditelné řešení pro určité konkrétní opatření ${ displaystyle m_ {0}}$ . Například pokud existuje graf ${ displaystyle G}$ který obsahuje vrcholy ${ displaystyle u}$ a ${ displaystyle v}$ , optimalizačním problémem může být „najít cestu z ${ displaystyle u}$ na ${ displaystyle v}$ který používá nejmenší počet hran ". Tento problém může mít odpověď, řekněme, 4. Odpovídající rozhodovací problém by byl" existuje cesta z ${ displaystyle u}$ na ${ displaystyle v}$ který používá 10 nebo méně hran? “Na tento problém lze odpovědět jednoduchým„ ano “nebo„ ne “.

V oblasti aproximační algoritmy, jsou algoritmy navrženy tak, aby nacházely téměř optimální řešení těžkých problémů. Obvyklá rozhodovací verze je pak neadekvátní definicí problému, protože specifikuje pouze přijatelná řešení. I když bychom mohli zavést vhodné rozhodovací problémy, problém je přirozenější charakterizován jako optimalizační problém.^[7]

Problém optimalizace NP

An Problém optimalizace NP (NPO) je kombinatorický optimalizační problém s následujícími dalšími podmínkami.^[8] Všimněte si, že níže uvedené polynomy jsou funkce velikosti vstupů příslušných funkcí, nikoli velikost nějaké implicitní sady vstupních instancí.

velikost každého proveditelného řešení ${ Displaystyle y in f (x)}$ je polynomiálně ohraničený ve velikosti dané instance ${ displaystyle x}$ ,
jazyky ${ displaystyle {, x , střední , x v I , }}$ a ${ displaystyle {, (x, y) , střední , y ve f (x) , }}$ může být uznáno v polynomiální čas, a
${ displaystyle m}$ je vypočítatelný v polynomiálním čase.

To znamená, že příslušný rozhodovací problém je v NP. Ve výpočetní technice mají zajímavé optimalizační problémy obvykle výše uvedené vlastnosti, a jsou tedy problémy NPO. Problém se dále nazývá problém P-optimalizace (PO), pokud existuje algoritmus, který najde optimální řešení v polynomiálním čase. Při jednání s třídou NPO se často zajímají optimalizační problémy, pro které jsou rozhodovací verze NP-kompletní. Pamatujte, že vztahy tvrdosti jsou vždy s ohledem na určité snížení. Vzhledem k propojení mezi aproximačními algoritmy a problémy s výpočetní optimalizací jsou pro tento předmět upřednostňovány redukce, které v určitém ohledu zachovávají aproximaci, než je obvyklé Turing a Karp redukce. Příkladem takového snížení by byl L-redukce. Z tohoto důvodu se problémy s optimalizací u rozhodovacích verzí NP-Complete nemusí nutně nazývat NPO-Complete.^[9]

NPO je rozdělena do následujících podtříd podle jejich přibližnosti:^[8]

NPO (I): Rovná se FPTAS. Obsahuje Problém s batohem.
NPO (II): Rovná se PTAS. Obsahuje Makespan problém s plánováním.
NPO (III):: Třída problémů NPO, které mají algoritmy polynomiálního času, které počítají řešení s maximální cenou C krát optimální náklady (pro minimalizaci problémů) nebo alespoň náklady ${ displaystyle 1 / c}$ optimálních nákladů (pro problémy s maximalizací). v Hromkovič Kniha vyloučená z této třídy zahrnuje všechny problémy NPO (II), pokud P = NP. Bez vyloučení se rovná APX. Obsahuje MAX-SAT a metrické TSP.
NPO (IV):: Třída problémů NPO s polynomiálně-časovými algoritmy přibližujícími optimální řešení poměrem, který je polynomický v logaritmu velikosti vstupu. V Hromkovicově knize jsou z této třídy vyloučeny všechny problémy NPO (III), pokud P = NP. Obsahuje nastavit kryt problém.
NPO (V):: Třída problémů NPO s polynomiálně-časovými algoritmy aproximujícími optimální řešení poměrem ohraničeným nějakou funkcí na n. V Hromkovicově knize jsou z této třídy vyloučeny všechny problémy NPO (IV), pokud P = NP. Obsahuje TSP a Max Clique problémy.

Problém NPO se nazývá polynomiálně ohraničené (PB) if, for every instance ${ displaystyle x}$ a pro každé řešení ${ Displaystyle y in f (x)}$ , Měření ${ displaystyle m (x, y)}$ je ohraničen polynomiální funkcí velikosti ${ displaystyle x}$ . Třída NPOPB je třída problémů NPO, které jsou polynomiálně ohraničené.

Specifické problémy

Prohlídka optimálního obchodního cestujícího Německo Je 15 největších měst. Je to nejkratší z 43 589 145 600^[10] možné prohlídky navštěvující každé město přesně jednou

Viz také

Omezený složený graf

Poznámky

^ Schrijver 2003, str. 1.
^ Diskrétní optimalizace. Elsevier. Citováno 2009-06-08.
^ Sbihi, Abdelkader; Eglese, Richard W. (2007). „Kombinatorická optimalizace a zelená logistika“ (PDF). 4OR. 5 (2): 99–116. doi:10.1007 / s10288-007-0047-3. S2CID 207070217.
^ Eskandarpour, Majid; Dejax, Pierre; Miemczyk, Joe; Péton, Olivier (2015). „Udržitelný design sítě dodavatelského řetězce: revize zaměřená na optimalizaci“ (PDF). Omega. 54: 11–32. doi:10.1016 / j.omega.2015.01.006.
^ Hobé, Alex; Vogler, Daniel; Seybold, Martin P .; Ebigbo, Anozie; Settgast, Randolph R .; Saar, Martin O. (2018). „Odhad rychlosti proudění tekutin zlomovými sítěmi pomocí kombinatorické optimalizace“. Pokroky ve vodních zdrojích. doi:10.1016 / j.advwatres.2018.10.002.
^ Cook 2016.
^ Ausiello, Giorgio; et al. (2003), Složitost a aproximace (Opraveno) Springer, ISBN 978-3-540-65431-5
^ ^A ^b Hromkovic, Juraj (2002), Algoritmy pro řešení těžkých problémů, Texty v teoretické informatice (2. vyd.), Springer, ISBN 978-3-540-44134-2
^ Kann, Viggo (1992), O přibližnosti NP-úplných optimalizačních problémů, Královský technologický institut, Švédsko, ISBN 91-7170-082-X
^ Vezměte jedno město a vezměte všechny možné objednávky dalších 14 měst. Pak vydělte dvěma, protože nezáleží na tom, kterým směrem v čase přijdou za sebou: 14! / 2 = 43 589 145 600.

Reference

Beasley, J. E. „Programování celého čísla“ (poznámky z přednášky).CS1 maint: ref = harv (odkaz)

Cook, William J.; Cunningham, William H .; Pulleyblank, William R.; Schrijver, Alexander (1997). Kombinatorická optimalizace. Wiley. ISBN 0-471-55894-X.CS1 maint: ref = harv (odkaz)

Cook, William (2016). „Optimální prohlídky TSP“. University of Waterloo.CS1 maint: ref = harv (odkaz) (Informace o největších dosud vyřešených instancích TSP.)

Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (eds.). „Kompendium problémů s optimalizací NP“.CS1 maint: ref = harv (odkaz) (Toto je průběžně aktualizovaný katalog výsledků přibližnosti pro problémy s optimalizací NP.)

Das, Arnab; Chakrabarti, Bikas K., eds. (2005). Kvantové žíhání a související optimalizační metody. Přednášky z fyziky. 679. Springer. Bibcode:2005qnro.book ..... D.CS1 maint: ref = harv (odkaz)

Das, Arnab; Chakrabarti, Bikas K (2008). „Kolokvium: Kvantové žíhání a analogový kvantový výpočet“. Rev. Mod. Phys. 80 (3): 1061. arXiv:0801.2193. Bibcode:2008RvMP ... 80.1061D. CiteSeerX 10.1.1.563.9990. doi:10.1103 / RevModPhys.80.1061. S2CID 14255125.CS1 maint: ref = harv (odkaz)

Lawler, Eugene (2001). Kombinatorická optimalizace: Sítě a matroidy. Doveru. ISBN 0-486-41453-1.CS1 maint: ref = harv (odkaz)

Lee, Jon (2004). První kurz kombinatorické optimalizace. Cambridge University Press. ISBN 0-521-01012-8.CS1 maint: ref = harv (odkaz)

Papadimitriou, Christos H .; Steiglitz, Kenneth (Červenec 1998). Kombinatorická optimalizace: Algoritmy a složitost. Doveru. ISBN 0-486-40258-4.CS1 maint: ref = harv (odkaz)

Schrijver, Alexander (2003). Kombinatorická optimalizace: mnohostěn a účinnost. Algoritmy a kombinatorika. 24. Springer. ISBN 9783540443896.CS1 maint: ref = harv (odkaz)

Schrijver, Alexander (2005). „K historii kombinatorické optimalizace (do roku 1960)“ (PDF). v Aardal, K.; Nemhauser, G.L .; Weismantel, R. (eds.). Příručka diskrétní optimalizace. Elsevier. s. 1–68.CS1 maint: ref = harv (odkaz)

Schrijver, Alexander (1. února 2006). Kurz kombinatorické optimalizace (PDF).CS1 maint: ref = harv (odkaz)

Sierksma, Gerard; Ghosh, Diptesh (2010). Sítě v akci; Textová a počítačová cvičení v optimalizaci sítě. Springer. ISBN 978-1-4419-5512-8.CS1 maint: ref = harv (odkaz)

Gerard Sierksma; Yori Zwols (2015). Lineární a celočíselná optimalizace: teorie a praxe. CRC Press. ISBN 978-1-498-71016-9.

Pintea, CM. (2014). Pokroky v biologicky inspirovaných výpočtech pro problém kombinatorické optimalizace. Referenční knihovna inteligentních systémů. Springer. ISBN 978-3-642-40178-7.CS1 maint: ref = harv (odkaz)

externí odkazy

[1] Schrijver 2003, str. 1.

[2] Diskrétní optimalizace. Elsevier. Citováno 2009-06-08.

[3] Sbihi, Abdelkader; Eglese, Richard W. (2007). „Kombinatorická optimalizace a zelená logistika“ (PDF). 4OR. 5 (2): 99–116. doi:10.1007 / s10288-007-0047-3. S2CID 207070217.

[4] Eskandarpour, Majid; Dejax, Pierre; Miemczyk, Joe; Péton, Olivier (2015). „Udržitelný design sítě dodavatelského řetězce: revize zaměřená na optimalizaci“ (PDF). Omega. 54: 11–32. doi:10.1016 / j.omega.2015.01.006.

[5] Hobé, Alex; Vogler, Daniel; Seybold, Martin P .; Ebigbo, Anozie; Settgast, Randolph R .; Saar, Martin O. (2018). „Odhad rychlosti proudění tekutin zlomovými sítěmi pomocí kombinatorické optimalizace“. Pokroky ve vodních zdrojích. doi:10.1016 / j.advwatres.2018.10.002.

[6] Cook 2016.

[Ausiello03-7] Ausiello, Giorgio; et al. (2003), Složitost a aproximace (Opraveno) Springer, ISBN 978-3-540-65431-5

[Hromkovic02-8] A ^b Hromkovic, Juraj (2002), Algoritmy pro řešení těžkých problémů, Texty v teoretické informatice (2. vyd.), Springer, ISBN 978-3-540-44134-2

[Kann92-9] Kann, Viggo (1992), O přibližnosti NP-úplných optimalizačních problémů, Královský technologický institut, Švédsko, ISBN 91-7170-082-X

[10] Vezměte jedno město a vezměte všechny možné objednávky dalších 14 měst. Pak vydělte dvěma, protože nezáleží na tom, kterým směrem v čase přijdou za sebou: 14! / 2 = 43 589 145 600.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]