Physics-inspired dynamical systems for optimization (Dinamički sustavi za optimizaciju inspirirani fizikom)

master's thesis

• Title (croatian): Dinamički sustavi za optimizaciju inspirirani fizikom
• Author: Luka Jovanović
• Mentor: Ilja Gogić (mentor)
• Committee member: Ilja Gogić (predsjednik povjerenstva)
• Committee member: Nikola Sandrić (član povjerenstva)
• Committee member: Maja Resman (član povjerenstva)
• Committee member: Zvonko Iljazović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2023-12-29, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Physics

Abstract

Ovaj diplomski rad izlaže, analizira te naposljetku predlaže unaprjeđenja dinamičkih sustava inspiriranih fizikom – novu vrstu heurističkih algoritama koji aproksimativno rješavaju NP-teške kombinatorne probleme. Diplomski rad započinje sažetim uvodom u NP-teške kombinatorne probleme, s posebnim naglaskom na problem neograničene binarne optimizacije kvadratnog funkcionala (eng. Quadratic Unconstrained Binary Optimization – QUBO) te MAX-CUT problema. Zatim se izlažu temeljni rezultati teorije dinamičkih sustava i ostalih matematičkih koncepata koji će se koristiti u ostatku rada kako bi se analizirali sustavi koji slijede. Glavni dio ovog rada su dinamički sustavi inspirirani fizikom koji rješavaju kombinatorne probleme. Numeričke simulacije ovih dinamičkih sustava predstavljaju heurističke algoritme za aproksimativno rješavanje NP-teških problema, uključujući QUBO i MAXCUT. Algoritmi koji su obradeni u ovom radu su Coherent Ising Machine (CIM), Simulated Bifurcation (SB), Simulated Coherent Ising Machine (SimCIM) i Ballistic Simulated Bifurcation (bSB). Analiziran je mehanizam ovih algoritama te je provedeno testirananje njihovih performansi na skupu podataka GSet. Na kraju rada predloženo je nekoliko tehnika koje unaprjeduju performanse navedenih algoritama.

Abstract (english)

This thesis presents, analyzes, and finally proposes some improvements to physics-inspired dynamical systems – a novel paradigm of heuristic algorithms used for approximately solving NP-hard combinatorial optimization problems. The thesis begins with a brief introduction to NP-hard combinatorial problems, with a particular emphasis on the quadratic unconstrained binary optimization problem (QUBO) and the MAX-CUT problem. Then, a brief overview is provided for the theory of dynamical systems and other mathematical concepts which are important for analyzing the following systems. At the core of this master’s thesis are physics-inspired dynamical systems for solving combinatorial optimization problems. Numerical simulations of these dynamical systems provide heuristic algorithms for approximately solving some NP-hard problems, including the QUBO and the MAX-CUT problem. The algorithms that are covered in this thesis are namely the Coherent Ising Machine (CIM), Simulated Bifurcation (SB), Simulated Coherent Ising Machine (SimCIM), and Ballistic Simulated Bifurcation (bSB). The mechanism of these heuristic algorithms is analyzed, and they are further benchmarked on the GSet dataset. Finally, a few new techniques are proposed for improving the performance of these algorithms.

• Keywords: heuristički algoritami; NP-teški kombinatorni problemi; kvadratni funkcional; MAX-CUT problem; QUBO
• Keywords (english): heuristic algorithms; NP-hard combinatorial optimization problems; QUBO; MAX-CUT problem
• Language: croatian
• URN:NBN: urn:nbn:hr:217:074762
• Study programme: Title: Theoretical Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: sveučilišni magistar matematike (sveučilišni magistar matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2024-02-13 10:02:02