Konbinaketazko optimizazio

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.. 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 edo 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
 Hornidura-kateen optimizazioa
 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)

 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 (adibidez 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.).

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.

Konbinaketazko optimizazio problema bakoitzak erabaki problema bat du lotuta non tamainako emaitza bideragarri bat existitzen den. Adibidez,  grafoa eta  eta  erpinak izanik, " -tik  -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  erpinetik  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.

 NP optimizazio-problema 
NP optimizazio-problema (NPO) bat konbinaketazko optimizazioko problema bat da, ondorengo baldintza gehigarriak dituena. Kontuan izan ondoren aipatzen diren polinomioak funtzioen ekarpenen tamainako funtzioak direla, ez sarrerako adibide multzo inplizitu batzuen tamainakoak.
 soluzio bideragarri guztien tamaina  emandako  instantziaren tamainari mugatuta dago,
  eta lengoaiak denbora polinomikoan ezagutu daitezke eta
  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.

Hurbilketaren arabera, NPO honako azpimota hauetan banatu daiteke:
 NPO(I): FPTAS (guztiz denbora polinomikoko hurbilketa eskema) multzoaren baliokidea da. Bizkar-zorroaren buruketa multzo honen barnean dago.
 NPO(II): PTAS (denbora polinomikoko hurbilketa eskema)  multzoaren baliokidea da. Makespan programazio problema multzo honen barnean dago.
 NPO(III): minimizazio problemetarako gehienez kostu optimoa baino c aldiz kostu handiagoan emaitza lortzen duten eta maximizazio problemetarako gutxienez  kostuan emaitza lortzen duten denbora polinomikoko algoritmoak dituzten NPO problemen azpimultzoa. MAX-SAT eta Saltzaile ibiltariaren problema multzo honen barnean daude.
 NPO(IV): sarreraren tamainaren logaritmoarekiko polinomiala den ratio batean soluzio optimora hurbiltzen den denbora polinomialeko algoritmoak dituzten NPO problemen azpimultzoa. NPO(III)-problemak klase honetatik kanpo daude P=NP egia ez bada. Set estaldura problema multzo honen barnean dago.
 NPO(V):  n inguruko funtzioren batek mugatutako ratio batean soluzio optimora hurbiltzen den denbora polinomialeko algoritmoak dituzten NPO problemen azpimultzoa. NPO(IV)-problemak klase honetatik kanpo daude P=NP egia ez bada. Saltzaile ibiltariaren problema eta clique problema multzo honen barnean daude.

NPO problema bat polinomikoki mugatua izango da baldin eta edozein instantzia  izanik eta edozein soluziorentzat ,  neurketa  tamainako funtzio polinomiko batengatik mugatuta badago. NPOPB klasea polinomikoki mugatuta dauden NPO problemekin osatuta dago.

Problema espezifikoak
 Esleipen problema
 Zakarrontziak paketatzeko arazoa.
 Itxiera problema
 Mugen beteera problema
 Stock mozketa arazoa
 Menderatzen duen setaren arazoa
 Integerren programazioa
 Lan-denden programazioa.
 Bizkarzorroaren buruketa
 Sistema linealeko aldagai garrantzitsu minimoak
 Hedapen zuhaitz minimoaren problema
 Herizainen antolakuntza problema
 Izar eraztun problema
 Set estaldura problema
 Talentu antolakuntza
 Saltzaile ibiltariaren problema
 Ibilgailuen birrantolakuntza problema
 Ibilgailuen ibilbideen antolakuntza problema
 Arma baten helburuen esleipen problema

 Erreferentziak 

 Kanpo estekak 

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