Datum / čas
Date(s) - 12.04.
15:00 - 17:00
Kategorie ne Kategorie
Wojciech Božejko (Wrocław University of Science and Technology)
Optimal solving of scheduling problems on D-Wave quantum machines
April 12, 2023 at 15 CET
Join online or offline on our Youtube channel:
https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A
The abstract:
The main disadvantage of calculations on real quantum computers is their non-determinism. For optimization problems, it is possible to get surprisingly good results using Quantum Annealing approach, but without a guarantee of the optimality of the result. Simply put, the quantum machine has not found anything better. In the presentation an approach that provides such a guarantee of optimality is proposed. A solution that is optimal in the strict mathematical sense is generated, without probabilistic considerations. For this purpose, a D-Wave quantum machine is used working as a sampler implementing quantum annealing — an approach considered as a hardware metaheuristic — to obtain upper and lower bounds on the value of the objective function of the problem under consideration. Then the mechanism of a Branch and Bound scheme is used and controlled by quantum annealing, which allows us to obtain very quickly — in constant time for considered instances — the boundaries of the considered subproblems. The whole idea is an alternately combination of calculations realized on QPU and CPU, allowing us to generate optimal solutions to the NP-hard problems of task scheduling on a single machine with a total weighted tardiness as well as with total number of tardy jobs criteria. The main result is the formulation of the lower bound in a „language“ (i.e. mathematical model) understandable by a quantum machine.
Wojciech Božejko is a Professor at Wrocław University of Science and Technology. He obtained M.Sc. in University of Wroclaw, Institute of Computer Science in 1999, Ph.D. in Wrocław University of Technology, Institute of Engineering Cybernetics in 2003, D.Sc. (habilitation) in Wrocław University of Technology, Faculty of Electronics, in 2011 and Full Professor title in 2020. From 2019 he is the Head of the Department of Control Systems in Wrocław University of Science and Technology.
The seminar is organized by Zdeněk Hanzálek (CIIRC CTU in Prague), Michael Pinedo (New York University) and Guohua Wan (Shanghai Jiao Tong).
Find full info and program at https://schedulingseminar.com/.