Kombinatorial optimallaşdırma — riyaziyyatın və əməliyyatlar tədqiqinin bir sahəsi olub, diskret obyektlər üzərində optimal həllərin tapılması ilə məşğul olur.[1] Bu sahədə əsas məqsəd sonlu və ya sayılabilən çoxluq daxilində mümkün variantlardan ən yaxşısını (maksimum və ya minimum dəyərlini) seçməkdir.[2]
Kombinatorial optimallaşdırma həm nəzəri, həm də praktik baxımdan mühüm əhəmiyyətə malikdir. O, müxtəlif sahələrdə — kompüter elmləri, nəqliyyat, telekommunikasiya, robot texnikası, sənaye mühəndisliyi və bioinformatika kimi istiqamətlərdə tətbiq olunur.[3]
Kombinatorial optimallaşdırmada aşağıdakı əsas anlayışlar istifadə olunur[4]:
- Axtarış sahəsi — mümkün həllərin təşkil etdiyi çoxluq.
- Məqsəd funksiyası — hər bir mümkün həllə uyğun qiymət verən funksiya; bu funksiya maksimumlaşdırılır və ya minimumlaşdırılır.
- Məhdudiyyətlər — həll variantlarının müəyyən şərtlərə cavab verməsini təmin edən qaydalar.
Kombinatorial optimallaşdırma anlayışı riyaziyyatın və əməliyyatlar tədqiqinin inkişafı ilə paralel olaraq XX əsrin birinci yarısında formalaşmağa başlamışdır. [5]Onun elmi əsasları Leonhard Eulerin 1736-cı ildə Königsberq körpüləri problemi ilə başlatdığı qraf nəzəriyyəsində qoyulmuşdur. Bu problem müasir qraf nəzəriyyəsinin və dolayısı ilə kombinatorial optimallaşdırmanın ilkin nümunəsi hesab olunur.[6]
XX əsrin əvvəllərində Corc Dantziq tərəfindən 1947-ci ildə təklif olunmuş simpleks metodu və xətti proqramlaşdırma sahəsində aparılan tədqiqatlar kombinatorial məsələlərin dəqiq və səmərəli həlli yollarını açdı. [7]1950-ci illərdə Harold Kuhn tərəfindən hazırlanmış Macar alqoritmi və Karoy Eqervarinin nəzəri nəticələri assignment problem kimi konkret məsələlərin optimal həllində dönüş nöqtəsi oldu.[8]
1960–1970-ci illərdə Edmonds alqoritmi, Dinamik proqramlaşdırma (R. Bellman tərəfindən), Axtarış ağacları və müxtəlif təxmini alqoritmlər təklif edildi. Bu dövr həm də NP-tamlıq və hesablama mürəkkəbliyi nəzəriyyəsi kimi anlayışların riyaziyyat və kompüter elmlərinə daxil olması ilə əlamətdardır. Kombinatorial optimallaşdırma məsələlərinin çoxunun NP-çətin olduğu sübut ediləndən sonra daha səmərəli və praktik həll yollarının axtarışına başlanıldı.[9]
1980-ci illərdən etibarən metaalqoritmlərə maraq artmağa başladı. Genetik alqoritmlər, simulated annealing, tabu search və digər metodlar real vaxt və böyük həcmli məsələlərin yaxın optimallaşdırılmış həllini tapmaq üçün istifadə olunmağa başlandı.
XXI əsrdə kombinatorial optimallaşdırma süni intellekt, maşın öyrənməsi, nəqliyyat sistemləri, şəbəkə dizaynı, robot texnikası və bioinformatika sahələrində mühüm alətə çevrilmişdir. Bu sahə həm nəzəri tədqiqatların, həm də praktiki tətbiqlərin mərkəzində dayanaraq daim inkişaf edir.[10]
Kombinatorial optimallaşdırmanın ən məşhur məsələləri aşağıdakılardır[11]:
- Tapşırıqların təyini problemi (ing. assignment problem)
- Səyahət edən satıcı problemi (ing. Travelling Salesman Problem, TSP)
- Qrafda maksimum uyğunluq
- Minimum örtük problemi
- Rəngləmə problemi
- Çoxbucaqlının örtülməsi problemi
Kombinatorial optimallaşdırma məsələlərinin həlli üçün müxtəlif alqoritmlər mövcuddur:
- ↑ Cook, William. "Optimal TSP Tours". University of Waterloo. 2016. (Information on the largest TSP instances solved to date.)
- ↑ Beasley, J. E. "Integer programming" (lecture notes).
- ↑ Cook, William J.; Cunningham, William H.; Pulleyblank, William R.; Schrijver, Alexander. Combinatorial Optimization. Wiley. 1997. ISBN 0-471-55894-X.
- ↑ Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (redaktorlar ). "A Compendium of NP Optimization Problems". (This is a continuously updated catalog of approximability results for NP optimization problems.)
- ↑ Das, Arnab; Chakrabarti, Bikas K, redaktorlar Quantum Annealing and Related Optimization Methods. Lecture Notes in Physics. 679. Springer. 2005. Bibcode:2005qnro.book.....D. ISBN 978-3-540-27987-7.
- ↑ Das, Arnab; Chakrabarti, Bikas K. "Colloquium: Quantum annealing and analog quantum computation". Rev. Mod. Phys. 80 (3). 2008: 1061. arXiv:0801.2193. Bibcode:2008RvMP...80.1061D. CiteSeerX 10.1.1.563.9990. doi:10.1103/RevModPhys.80.1061.
- ↑ Lee, Jon. A First Course in Combinatorial Optimization. Cambridge University Press. 2004. ISBN 0-521-01012-8.
- ↑ Lawler, Eugene. Combinatorial Optimization: Networks and Matroids. Dover. 2001. ISBN 0-486-41453-1.
- ↑ Schrijver, Alexander. On the history of combinatorial optimization (till 1960) (PDF) // Aardal, K.; Nemhauser, G.L.; Weismantel, R. (redaktorlar ). Handbook of Discrete Optimization. Elsevier. 2005. 1–68.
- ↑ Papadimitriou, Christos H.; Steiglitz, Kenneth. Combinatorial Optimization : Algorithms and Complexity. Dover. July 1998. ISBN 0-486-40258-4.
- ↑ Schrijver, Alexander. Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics. 24. Springer. 2003. ISBN 9783540443896.
- Schrijver, Alexander. A Course in Combinatorial Optimization (PDF). February 1, 2006.
- Sierksma, Gerard; Ghosh, Diptesh. Networks in Action; Text and Computer Exercises in Network Optimization. Springer. 2010. ISBN 978-1-4419-5512-8.
- Gerard Sierksma; Yori Zwols. Linear and Integer Optimization: Theory and Practice. CRC Press. 2015. ISBN 978-1-498-71016-9.
- Pintea, C-M. Advances in Bio-inspired Computing for Combinatorial Optimization Problem. Intelligent Systems Reference Library. Springer. 2014. ISBN 978-3-642-40178-7.
