ECE Seminar: Wojciech Bozejko
Tuesday, October 11, 2022
2:00 p.m.
Wojciech Bożejko
Professor and Department Head of Control Systems and Mechatronics
Wrocław University of Science and Technology, Poland
"Exact Optimization by Using Quantum Annealing Metahuristics"
ECE 530 | Zoom link
Abstract
The main disadvantage of calculations on real quantum computers is their non-determinism. For optimization problems, of course, it is possible to get surprisingly good results, but without a guarantee of the actual optimality of the result - that is, an assurance that there is no better solution. Simply put, the quantum machine has not found anything better. Bożejko proposes to use an approach that provides such a guarantee of optimality. We generate a solution that is optimal in the strict mathematical sense, without probabilistic considerations. For this purpose, he uses a D-Wave quantum machine working as a sampler implementing quantum annealing - an approach considered a hardware metaheuristic - to obtain upper and lower bounds on the value of the objective function of the problem under consideration. Then Bożejko uses the mechanism of a Branch and Bound scheme controlled by quantum annealing, which allows him to obtain very quickly - because in constant time - the boundaries of the considered subproblems. The whole thing is a combination of calculations realized on a quantum machine controlled by procedures implemented on a classical computer (we can say "hybrid quantum computing", CPU+QPU), allowing him to generate optimal solutions to the NP-hard problem of task scheduling on a single machine with goal function of: total weighted tardiness and total weighted number of late jobs (both NP-hard, the second is a generalization of knapsack problem).
Bio
Wojciech Bożejko is a professor at Wrocław University of Technology. He obtained an M.Sc. at the University of Wrocław, Institute of Computer Science in 1999, a Ph.D. in Wrocław University of Technology, Institute of Engineering Cybernetics in 2003, a D.Sc. (habilitation) in Wrocław University of Technology, Faculty of Electronics, in 2011 and full professor title in 2020. From 2019 Bożejko is the head of the Department of Control Systems in Wrocław University of Science and Technology. He is an author of over 240 papers published in peer-reviewed journals and conference proceedings from the field of parallel processing, scheduling, and optimization. Bożejko is also a reviewer of journals in this field: European Journal of Operational Research, Journal of Intelligent Manufacturing, Journal of Parallel and Distributed Computing, Computers & Industrial Engineering, IEEE Transactions on Automation Science and Engineering, International Journal of Advanced Manufacturing Technology, Journal of Civil Engineering and Management. He is interested in parallel algorithms, GPU computing, scheduling, and discrete optimization.
Bożejko is also a musician with a MS degree, 1998 from the Academy of Music in Wroclaw in the specialization of piano.