Ising Machine Approach to the Lecturer–Student Assignment Problem

Abstract

Ising machines are efficient solvers for combinatorial optimization problems (COPs). After mapping COPs to Quadratic Unconstrained Binary Optimization (QUBO) problems, Ising machines search for the lowest energy solution of the QUBO corresponding to the optimal solution of the COP. Herein we propose an efficient method to formulate a lecturer–student assignment problem as a QUBO problem. In this problem, the sets of subjects, lecturers, students, lecturers’ teachable subjects, and students’ required subjects are given. To minimize lecture costs, the number of lecturers in charge of students must be minimized. The number of combinations drastically increases as the number of lecturers or students increases. Using these results, we theoretically prove the optimality, i.e., the formulated QUBO takes the lowest energy if and only if the students are optimally assigned to the lecturers. Additionally, we demonstrate that an Ising machine outperforms simulated annealing in terms of solution quality and execution time.

Keywords

• Combinatorial optimization problem
• Ising machine
• quantum annealing
• QUBO
• simulated annealing