Naslov
Exact solving scheduling problems accelerated by graph neural networks

Autori
Juros, Jana ; Brcic, Mario ; Koncic, Mihael ; Kovac, Mihael

Vrsta, podvrsta i kategorija rada
Radovi u zbornicima skupova, cjeloviti rad (in extenso), znanstveni

Izvornik
2022 45th Jubilee International Convention on Information, Communication and Electronic Technology (MIPRO) / - : Institute of Electrical and Electronics Engineers (IEEE), 2022, 865-870

Skup
45th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO 2022)

Mjesto i datum
Opatija, Hrvatska, 23.05.2022. - 27.05.2022

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
combinatorial optimization , machine learning , job-shop scheduling problem , delivery scheduling , supply-chain , graph-convolution neural network , branch-and-bound algorithm , mixed-integer linear programming

Sažetak
Scheduling is a family of combinatorial problems where we need to find optimal time arrangements for activities. Scheduling problems in applications are usually notoriously hard to solve exactly. Existing exact solving procedures, based on mathematical programming and constraint programming, usually make manually-tuned heuristic choices. These heuristics can be improved by machine learning. In this paper, we apply the graph convolutional neural network from the literature on speeding up general branch&bound solver by learning its branching decisions. We test the augmented solver on job-shop scheduling problems and specific delivery scheduling problems in the supply chain of a local retailer. We get promising results and point to possible improvements. We discuss the interesting question of how much we can accelerate solving NP-hard problems in the light of the known limits and impossibility results in AI.

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo, Interdisciplinarne tehničke znanosti

POVEZANOST RADA