An Ising Machine Approach to the Personalized Course Selection Problem

A combinatorial optimization problem is a problem finding an optimal combination of variables that maximizes or minimizes an objective function while satisfying given constraints. Such problems arise in various fields, including transportation and communication. Many combinatorial optimization problems are NP-hard, meaning that the number of possible combinations grows exponentially as the number of variables increases. As a result, it is often difficult to solve large-scale combinatorial optimization problems for conventional classical computers. Recently, Ising machines, including quantum annealers, have gained attention as a promising architecture for efficiently solving combinatorial optimization problems. One real-world example of a combinatorial optimization problem is <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">university course selection</i>. Many students manually choose their courses, but this process is time consuming and labor intensive due to the large number of available options. To address this, in this paper, we formulate course selection as a combinatorial optimization problem, which we define as a Personalized Course Selection Problem (PCSP). To solve it efficiently, we use an Ising machine, a specialized computer designed for combinatorial optimization. We propose a Quadratic Unconstrained Binary Optimization (QUBO) formulation for solving PCSP and solve the problem with an Ising machine. Experimental evaluations demonstrate that, for the largest instance tested, the proposed method solves the problem 20X times faster than the conventional simulated annealing while achieving the same total course cost.