We are delighted to announce the talk given by Wojciech Bozejko (Poli
Wroclawska).
The title is "Optimal solving of scheduling problems on D-Wave quantum
machines".
The seminar will take place on Zoom on Wednesday, April 12 at 13:00 UTC.
Join Zoom Meeting
https://cesnet.zoom.us/j/95332759663?pwd=YVNNT3JrWFhzbmQxcFpUczBGM0d4QT09
Meeting ID: 953 3275 9663
Passcode: 208021
You can follow the seminar online or offline on our Youtube channel as well:
https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A
The abstract follows.
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.
The next talk in our series will be:
Rainer Kolisch (TU Munich) | April 26 | The Resource-Constrained Project
Scheduling Problem with Flexible Resource Profiles: Models, Methods, and
Applications.
For more details, please visit https://schedulingseminar.com/
With kind regards
Zdenek, Mike and Guohua
--
Zdenek Hanzalek
Industrial Informatics Department,
Czech Institute of Informatics, Robotics and Cybernetics,
Czech Technical University in Prague,
Jugoslavskych partyzanu 1580/3, 160 00 Prague 6, Czech Republic
https://rtime.ciirc.cvut.cz/~hanzalek/
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
