IEEE International Conference on Quantum Computing and Engineering (QCE)

Personalized Course Selection Optimization Using an Ising Machine

Takeru Ota, Keisuke Fukada, Nozomu Togawa

Published Sep 15, 2024• 4 citations

Abstract

Many students spend a lot of time and effort manually selecting courses, due to the large number of candidate courses offered by universities. We regard course selection as a combinatorial optimization problem and define it as an NP-hard problem. In this paper, we propose a QUBO (Quadratic Unconstrained Binary Optimization) formulation for solving the course selection problem, and solve the problem with an Ising machine. Experimental evaluations demonstrate that for the instance with the largest number of courses, our approach solves a personalized course selection problem 20X times faster than the conventional simulated annealing.

DOI: 10.1109/qce60285.2024.10340

Related papers

An Ising Machine Approach to the Personalized Course Selection Problem

Takeru Ota, Keisuke Fukada, Nozomu Togawa

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 isuniversity course selection. 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.

IEEE AccessJan 1, 20250 citations

Personalized Course Selection Optimization Using QAOA

Takeru Ota, Keisuke Fukada, Tatsuhiko Shirai +1 more

Quantum approximate optimization algorithm (QAOA) is an algorithm for solving combinatorial optimization problems (COP), which can be implemented on gate based quantum computers. However, many practical COPs such as a personalized course selection problem (PCSP) have not been solved by QAOA yet. In this paper, we solve a PCSP using QAOA by transforming the problem into a quadratic unconstrained binary optimization (QUBO), and investigate the solution properties when the weight of the problem's constraint is changed. Experimental evaluations demonstrate that tuning the weight value improves the probability of obtaining optimal solutions and reduces the energy expectation value averaged over the obtained feasible solutions.

International Conference on Consumer ElectronicsJan 11, 20250 citations

Ising Machine Approach to the Lecturer–Student Assignment Problem

Sora Tomita, Tatsuhiko Shirai, Nozomu Togawa

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.

IEEE AccessJan 1, 20242 citations

Visiting-Route Recommendation in Amusement Parks and its Evaluations by an Ising Machine

Yosuke Mukasa, Tomoya Wakaizumi, Shu Tanaka +1 more

In an amusement park, an attraction-visiting route considering the waiting time and traveling time improves visitors' satisfaction and experience. We focus on Ising machines to solve the problem, which are recently expected to solve combinatorial optimization problems at high speed by mapping the problems to Ising models or quadratic unconstrained binary optimization (QUBO) models. We propose a mapping of the visiting-route recommendation problem in amusement parks to a QUBO model for solving it using Ising machines. By using an actual Ising machine, we could obtain feasible solutions 15 times faster with almost the same accuracy as the simulated annealing method for the visiting-route recommendation problem.

International Conference on Consumer ElectronicsJan 10, 20213 citations

An Ising Machine-Based Solver for Visiting-Route Recommendation Problems in Amusement Parks

Yosuke Mukasa, Tomoya Wakaizumi, Shu Tanaka +1 more

In an amusement park, an attraction-visiting route considering the waiting time and traveling time improves visitors' satisfaction and experience. We focus on Ising machines to solve the problem, which are recently expected to solve combinatorial optimization problems at high speed by mapping the problems to Ising models or quadratic unconstrained binary optimization (QUBO) models. We propose a mapping of the visiting-route recommendation problem in amusement parks to a QUBO model for solving it using Ising machines. By using an actual Ising machine, we could obtain feasible solutions one order of magnitude faster with almost the same accuracy as the simulated annealing method for the visiting-route recommendation problem.

IEICE Transactions on Information and SystemsSep 30, 202110 citations

Trip Planning Based on subQUBO Annealing

Tatsuya Noguchi, Keisuke Fukada, Siya Bao +1 more

The trip planning problem (TPP) can be formulated as a combinatorial optimization problem that searches for the best route to visit a series of landmarks and hotels. Meanwhile, Ising machines have attracted attention due to their efficiency in solving combinatorial optimization problems. The Ising machines solve the combinatorial optimization problems by transforming the problems into quadratic unconstrained binary optimization (QUBO) models. However, the possible input QUBO size of current Ising machines is quite limited. Thus, it is hard to directly embed a large-scale TPP onto the current Ising machines. In this paper, we propose a novel subQUBO annealing method based on the combined variable selection method to solve the TPP. The proposed method finds a quasi-optimal solution to a large problem by repeatedly partitioning the original QUBO model into small subQUBOs that can be embedded onto the Ising machine. Specifically, to construct a subQUBO, we select variables from the original QUBO model, which have small deviation values. Further, we select variables randomly from the original QUBO model, so as not to fall into the local optimum. We have conducted an evaluation experiment using Ising machines on TPP and confirmed that the proposed method outperforms the state-of-the-art methods in terms of POI satisfaction and POI cost.

IEEE AccessJan 1, 20239 citations