Lankide:Koldosaurio/Konbinaketazko optimizazioa

Konbinaketazko optimizazioa optimizazio matematikoko azpieremu bat da, objektu multzo finitu batetik abiatuta objektu optimo bat aurkitzean datzana, non emaitza egingarrien multzoa diskretua den edo multzo diskretu batera murriztu daitekeen.^[1] Optimizazio konbinatorioko ohiko arazoetako batzuk dira saltzaile ibiltariaren problema ("TSP"), gutxieneko hedadura zuhaitzaren problema ("MST") eta Bizkar-zorroaren buruketa. Arazo horietako askotan, lehen aipatutakoetan adibidez, bilaketa sakona ezinezkoa litzateke, eta, beraz, algoritmo espezializatuetara jotzea beharrezkoa dugu, bilaketa-espazioaren zati handiak baztertuz ala hurbiltze-algoritmoak erabiliz.

Konbinaketazko optimizazioak zerikusia du ikerkuntza eragilearekin, algoritmoen teoriarekin eta konplexutasun konputazionalaren teoriarekin. Hainbat arlotarako aplikazio garrantzitsuak ditu, besteak beste, adimen artifizialean, ikasketa automatikoan, enkanteen teorian, software ingeniaritzan, VLSIn, matematika aplikatuan eta konputazio zientzia teorikoetan.

Erabilerak

Konbinaketazko optimizazioaren oinarrizko aplikazioetako batzuk hauek dira:

Logistika^[2]
Hornidura-kateen optimizazioa^[3]
Irrati eta helmugen arteko sare optimoa garatzea
Tarifak jasotzeko taxi flota bateko ibilgailuen aukeraketa eta ibilbidea egitea
Paketeak entregatzeko modu optimoa zehaztea
Langileei lanpostuen esleipen optimoa egitea
Ur banaketa sareen diseinua
Lurraren zientziaren arazoak (adib. urtegien emariak)^[4]

Metodoak

Denbora polinomialeko algoritmoen inguruko literatura asko dago optimizazio diskretuko mota berezi batzuetarako. Horren atal handi bat programazio linealaren teoriak batzen du. Esparru horrek estaltzen dituen konbinaketazko optimizazio-arazoen adibide batzuk dira bide laburrenak eta ibilbide laburreneko zuhaitzak, fluxu sareak, hedapen zuhaitzak, parekatzea eta arazo matroideoak barne hartzen dituztenak.

denbora polinomialean esku artean dugun arazoaren kasu berezi zehatz eta konpongarriak. (e.g. fixed-parameter tractable problems)
"Ausazko" kasuetan ondo dabiltzan algoritmoak (adib. saltzaile ibiltariaren problemarako)
hurbiltze-algoritmoak, denbora plinomialean exekutatzen direnak eta optimotik hurbil dagoen emaitza bat lortzen dutenak
hurbilketa parametrizatuko algoritmoak, FPT denboran exekutatzen direnak eta optimotik hurbil dagoen emaitza bat lortzen dutenak
Praktikan sortzen diren eta NP-osoko arazoetan portaera okerrenak erakusten ez dituzten mundu errealeko kasuak ebaztea(adib. mundu errealeko TSP instantziak, dozenaka mila nodo dituztenak^[5]).

Optimizazio konbinatorioko problemak elementu diskretu multzo baten elementurik onenaren bilatzailetzat har daitezke; beraz, printzipioz, edozein bilaketa-algoritmo edo algoritmo metaheuristiko erabil daiteke horiek ebazteko.Aplikagarriak diren planteamenduak honako hauek dira: adarkatu eta bornatu (algoritmo zehatza, edozein unetan geldi daitekeena heuristiko gisa erabiltzeko), adarkatu eta moztu (optimizazio lineala erabiltzen du mugak sortzeko), programazio dinamikoa (soluzio errekurtsiboaren eraikuntza, bilaketa-leiho mugatuarekin) eta tabu bilaketa (algoritmo trukatzaile grisa).Hala ere, bilaketa-algoritmo generikoek ez dute bermatzen soluzio optimo bat aurkitzea, ezta ere exekuzio azkar bat izatea (denbora polinomikoan). Optimizazio-problema diskretu batzuk NP-osoak izanik, hala nola saltzaile ibiltariaren problema, hori espero da P=NP frogatzen ez den bitartean.^[6]

Konbinaketazko optimizazio problema bakoitzak erabaki problema bat du lotuta non $m_{0}$ tamainako emaitza bideragarri bat existitzen den. Adibidez, $G$ grafoa eta $u$ eta $v$ erpinak izanik, " $u$ -tik $v$ -rako bide bat topatzea erabilitako ertzak ahalik eta txikienak izanik" optimizazio arazo bat izango litzateke. Demagun problema honen erantzuna 4 dela. Dagokion erabaki problema ondokoa izango litzateke "ba al dago biderik $u$ erpinetik $v$ erpinera doana eta 10 ertz edo gutxiago erabiltzen dituena?". Problema honen emaitza 'bai' ala 'ez' soilik izan daiteke.

Hurbiltze-algoritmoen eremua arazo zailetarako soluzio ia-optimoak lortzen dituzten algoritmoetaz arduratzen da. Ohiko erabaki-bertsioa, orduan, arazoaren definizio desegokia da, irtenbide onargarriak baino ez baititu zehazten. Nahiz eta erabaki-problema egokiak sar ditzakegun, problema optimizazio-problema gisa definitzea litzateke egokiena.^[7]

NP optimizazio-problema

NP optimizazio-problema (NPO) bat konbinaketazko optimizazioko problema bat da, ondorengo baldintza gehigarriak dituena.^[8] Kontuan izan ondoren aipatzen diren polinomioak funtzioen ekarpenen tamainako funtzioak direla, ez sarrerako adibide multzo inplizitu batzuen tamainakoak.

soluzio bideragarri guztien tamaina $y\in f(x)$ emandako $x$ instantziaren tamainari mugatuta dago,
$\{\,x\,\mid \,x\in I\,\}$ eta $\{\,(x,y)\,\mid \,y\in f(x)\,\}$ lengoaiak denbora polinomikoan ezagutu daitezke eta
$m$ denbora polinomikoan konputagarria da

Honen ondorioz problema honi loturiko erabaki problema NP da. Informatikan, optimizazio arazo interesgarriek aurreko propietateak dituzte eta, beraz, NPO arazoak dira. Problema bati, gainera, P-optimizazio (PO) problema deritzo, denbora polinomioan soluzio optimoak aurkitzen dituen algoritmo bat existitzen bada. Erabaki bertsioak NP-osoak diren algoritmoak oso interesgarriak dira NPO arazo bati aurre egiterakoan. Kontuan izan gogortasun-erlazioak beti murrizketaren batekiko direla. Hurbilketa algoritmoen eta optimizazio konputazionaleko arazoen arteko loturaren ondorioz, gai honetarako nahiago dira hurbilketa nolabait mantentzen duten murrizketak Turing eta Karpen ohiko murrizketak baino.Murrizketa horren adibide bat L-ren murrizketa litzateke. Hori dela eta, erabaki bertsioa NP-complete izateak ez du behartzen optimizazio problema NPO-complete izatera.^[9]

Hurbilketaren arabera, NPO honako azpimota hauetan banatu daiteke:^[8]

NPO(I): Equals FPTAS. Contains the Knapsack problem.
NPO(II): Equals PTAS. Contains the Makespan scheduling problem.
NPO(III): The class of NPO problems that have polynomial-time algorithms which computes solutions with a cost at most c times the optimal cost (for minimization problems) or a cost at least $1/c$ of the optimal cost (for maximization problems). In Hromkovič's bookTxantiloi:Which, excluded from this class are all NPO(II)-problems save if P=NP. Without the exclusion, equals APX. Contains MAX-SAT and metric TSP.
NPO(IV): The class of NPO problems with polynomial-time algorithms approximating the optimal solution by a ratio that is polynomial in a logarithm of the size of the input. In Hromkovič's book, all NPO(III)-problems are excluded from this class unless P=NP. Contains the set cover problem.
NPO(V): The class of NPO problems with polynomial-time algorithms approximating the optimal solution by a ratio bounded by some function on n. In Hromkovic's book, all NPO(IV)-problems are excluded from this class unless P=NP. Contains the TSP and clique problem.

An NPO problem is called polynomially bounded (PB) if, for every instance $x$ and for every solution $y\in f(x)$ , the measure $m(x,y)$ is bounded by a polynomial function of the size of $x$ . The class NPOPB is the class of NPO problems that are polynomially-bounded.

Problema espezifikoak

An optimal traveling salesperson tour through Germany’s 15 largest cities. It is the shortest among the 43,589,145,600^[10] possible tours that visit each city exactly once.

Erreferentziak

↑ Schrijver, 2003, or. 1.
↑ Sbihi, Abdelkader; Eglese, Richard W.. (2007). «Combinatorial optimization and Green Logistics» 4OR 5 (2): 99–116. doi:10.1007/s10288-007-0047-3..
↑ Eskandarpour, Majid; Dejax, Pierre; Miemczyk, Joe; Péton, Olivier. (2015). «Sustainable supply chain network design: An optimization-oriented review» 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). «Estimating fluid flow rates through fracture networks using combinatorial optimization» Advances in Water Resources 122: 85–97. doi:10.1016/j.advwatres.2018.10.002. Bibcode: 2018AdWR..122...85H..
↑ Cook, 2016.
↑ Approximation-TSP. .
↑ Ausiello, Giorgio. (2003). Complexity and Approximation. (Corrected. argitaraldia) Springer ISBN 978-3-540-65431-5..
↑ ^a ^b Hromkovic, Juraj. (2002). Algorithmics for Hard Problems. in: Texts in Theoretical Computer Science. (2nd. argitaraldia) Springer ISBN 978-3-540-44134-2..
↑ Kann, Viggo. (1992). On the Approximability of NP-complete Optimization Problems. Royal Institute of Technology, Sweden ISBN 91-7170-082-X..
↑ Take one city, and take all possible orders of the other 14 cities. Then divide by two because it does not matter in which direction in time they come after each other: 14!/2 = 43,589,145,600.

[[Kategoria:Informatika teorikoa]] [[Kategoria:Konbinaziozko optimizazioa]] [[Kategoria:Konputazioaren konplexutasun teoria]]

[1] Schrijver, 2003, or. 1.

[2] Sbihi, Abdelkader; Eglese, Richard W.. (2007). «Combinatorial optimization and Green Logistics» 4OR 5 (2): 99–116. doi:10.1007/s10288-007-0047-3..

[3] Eskandarpour, Majid; Dejax, Pierre; Miemczyk, Joe; Péton, Olivier. (2015). «Sustainable supply chain network design: An optimization-oriented review» Omega 54: 11–32. doi:10.1016/j.omega.2015.01.006..

[4] Hobé, Alex; Vogler, Daniel; Seybold, Martin P.; Ebigbo, Anozie; Settgast, Randolph R.; Saar, Martin O.. (2018). «Estimating fluid flow rates through fracture networks using combinatorial optimization» Advances in Water Resources 122: 85–97. doi:10.1016/j.advwatres.2018.10.002. Bibcode: 2018AdWR..122...85H..

[5] Cook, 2016.

[6] Approximation-TSP. .

[Ausiello03-7] Ausiello, Giorgio. (2003). Complexity and Approximation. (Corrected. argitaraldia) Springer ISBN 978-3-540-65431-5..

[Hromkovic02-8] Hromkovic, Juraj. (2002). Algorithmics for Hard Problems. in: Texts in Theoretical Computer Science. (2nd. argitaraldia) Springer ISBN 978-3-540-44134-2..

[Kann92-9] Kann, Viggo. (1992). On the Approximability of NP-complete Optimization Problems. Royal Institute of Technology, Sweden ISBN 91-7170-082-X..

[10] Take one city, and take all possible orders of the other 14 cities. Then divide by two because it does not matter in which direction in time they come after each other: 14!/2 = 43,589,145,600.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]