Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Access

Ising Machine Approach to the Lecturer–Student Assignment Problem

Sora Tomita, Tatsuhiko Shirai, Nozomu Togawa

Published Jan 1, 2024• 2 citations
Publisher

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.

DOI
10.1109/access.2024.3384980

Related papers

Ising-Machine-Based Solver for Constrained Graph Coloring Problems

Soma Kawakami, Yosuke Mukasa, Siya Bao +5 more

Ising machines can find optimum or quasi-optimum solutions of combinatorial optimization problems efficiently and effectively. The graph coloring problem, which is one of the difficult combinatorial optimization problems, is to assign a color to each vertex of a graph such that no two vertices connected by an edge have the same color. Although methods to map the graph coloring problem onto the Ising model or quadratic unconstrained binary optimization (QUBO) model are proposed, none of them considers minimizing the number of colors. In addition, there is no Ising-machine-based method considering additional constraints in order to apply to practical problems. In this paper, we propose a mapping method of the graph coloring problem including minimizing the number of colors and additional constraints to the QUBO model. As well as the constraint terms for the graph coloring problem, we firstly propose an objective function term that can minimize the number of colors so that the number of used spins cannot increase exponentially. Secondly, we propose two additional constraint terms: One is that specific vertices have to be colored with specified colors; The other is that specific colors cannot be used more than the number of times given in advance. We theoretically prove that, if the energy of the proposed QUBO mapping is minimized, all the constraints are satisfied and the objective function is minimized. The result of the experiment using an Ising machine showed that the proposed method reduces the number of used colors by up to 75.1% on average compared to the existing baseline method when additional constraints are not considered. Considering the additional constraints, the proposed method can effectively find feasible solutions satisfying all the constraints.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Sep 11, 2023•3 citations

Variable Reduction Method for Quadratic Three-Dimensional Assignment Problem with FMQA

Sora Tomita, Tatsuhiko Shirai, Nozomu Togawa

Ising machines including quantum annealers have attracted attention as efficient solvers for combinatorial optimization problems (COPs). To use Ising machines, the objective function and constraints of a COP must be expressed in a QUBO (quadratic unconstrained binary optimization) form. However, their application range is practically limited since some COPs are difficult to formulate in a QUBO form, or require a large number of binary variables. Quadratic three-dimensional assignment problem (Q3AP) is a challenging problem for Ising machines to solve since the number of required binary variables rapidly increases with the problem size N. In this paper, to overcome the difficulty, we propose a method to reduce the number of necessary variables from$N^{3}$to$2N^{2}$by using a factorization machine with quantum annealing (FMQA) to estimate QUBO through machine learning. Experimental results with a real Ising machine demonstrate that the proposed method can obtain the best-known solution in a short time.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•0 citations

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 Access•Jan 1, 2025•0 citations

Spin-Variable Reduction Method for Handling Linear Equality Constraints in Ising Machines

Tatsuhiko Shirai, Nozomu Togawa

We propose a spin-variable reduction method for Ising machines to handle linear equality constraints in a combinatorial optimization problem. Ising machines including quantum-annealing machines can effectively solve combinatorial optimization problems. They are designed to find the lowest-energy solution of a quadratic unconstrained binary optimization (QUBO), which is mapped from the combinatorial optimization problem. The proposed method reduces the number of binary variables to formulate the QUBO compared to the conventional penalty method. We demonstrate a sufficient condition to obtain the optimum of the combinatorial optimization problem in the spin-variable reduction method and its general applicability. We apply it to typical combinatorial optimization problems, such as the graph κ-partitioning problem and the quadratic assignment problem. Experiments using simulated-annealing and quantum-annealing based Ising machines demonstrate that the spin-variable reduction method outperforms the penalty method. The proposed method extends the application of Ising machines to larger-size combinatorial optimization problems with linear equality constraints.

IEEE Transactions on Computers•Jan 24, 2023•11 citations

A Constrained Graph Coloring Solver Based on Ising Machines

Soma Kawakami, Yosuke Mukasa, Siya Bao +5 more

Optimum or quasi-optimum solutions of combinatorial optimization problems can be efficiently found by using Ising machines. The graph coloring problem (GCP) is known as a difficult combinatorial problem. Given a graph, each vertex should be assigned a color and any two vertices connected by an edge must not be colored the same. Although methods to map the GCP onto the Ising model are proposed, none of them considers minimizing the number of colors. In this paper, we propose a mapping method of the GCP including minimizing the number of colors and additional constraints to the QUBO (Quadratic Unconstrained Binary Optimization) model. As well as the constraint terms for the GCP, we firstly propose an objective function term that can minimize the number of colors so that the number of used spins cannot increase exponentially. Secondly, we propose two more additional terms so that our proposed method can be applicable to practical consumer applications. The experimental evaluations on an Ising machine showed that the proposed method reduces the number of used colors by up to 75.1% on average compared with the existing baseline method. Considering the additional constraints, the proposed method can effectively find feasible solutions satisfying all the constraints.

International Conference on Consumer Electronics•Jan 6, 2023•2 citations

Personalized Course Selection Optimization Using an Ising Machine

Takeru Ota, Keisuke Fukada, Nozomu Togawa

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.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•4 citations
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.
Ising machines can find optimum or quasi-optimum solutions of combinatorial optimization problems efficiently and effectively. The graph coloring problem, which is one of the difficult combinatorial optimization problems, is to assign a color to each vertex of a graph such that no two vertices connected by an edge have the same color. Although methods to map the graph coloring problem onto the Ising model or quadratic unconstrained binary optimization (QUBO) model are proposed, none of them considers minimizing the number of colors. In addition, there is no Ising-machine-based method considering additional constraints in order to apply to practical problems. In this paper, we propose a mapping method of the graph coloring problem including minimizing the number of colors and additional constraints to the QUBO model. As well as the constraint terms for the graph coloring problem, we firstly propose an objective function term that can minimize the number of colors so that the number of used spins cannot increase exponentially. Secondly, we propose two additional constraint terms: One is that specific vertices have to be colored with specified colors; The other is that specific colors cannot be used more than the number of times given in advance. We theoretically prove that, if the energy of the proposed QUBO mapping is minimized, all the constraints are satisfied and the objective function is minimized. The result of the experiment using an Ising machine showed that the proposed method reduces the number of used colors by up to 75.1% on average compared to the existing baseline method when additional constraints are not considered. Considering the additional constraints, the proposed method can effectively find feasible solutions satisfying all the constraints.
Ising machines including quantum annealers have attracted attention as efficient solvers for combinatorial optimization problems (COPs). To use Ising machines, the objective function and constraints of a COP must be expressed in a QUBO (quadratic unconstrained binary optimization) form. However, their application range is practically limited since some COPs are difficult to formulate in a QUBO form, or require a large number of binary variables. Quadratic three-dimensional assignment problem (Q3AP) is a challenging problem for Ising machines to solve since the number of required binary variables rapidly increases with the problem size N. In this paper, to overcome the difficulty, we propose a method to reduce the number of necessary variables fromN3N^{3}N3to2N22N^{2}2N2by using a factorization machine with quantum annealing (FMQA) to estimate QUBO through machine learning. Experimental results with a real Ising machine demonstrate that the proposed method can obtain the best-known solution in a short time.
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.
We propose a spin-variable reduction method for Ising machines to handle linear equality constraints in a combinatorial optimization problem. Ising machines including quantum-annealing machines can effectively solve combinatorial optimization problems. They are designed to find the lowest-energy solution of a quadratic unconstrained binary optimization (QUBO), which is mapped from the combinatorial optimization problem. The proposed method reduces the number of binary variables to formulate the QUBO compared to the conventional penalty method. We demonstrate a sufficient condition to obtain the optimum of the combinatorial optimization problem in the spin-variable reduction method and its general applicability. We apply it to typical combinatorial optimization problems, such as the graph κ-partitioning problem and the quadratic assignment problem. Experiments using simulated-annealing and quantum-annealing based Ising machines demonstrate that the spin-variable reduction method outperforms the penalty method. The proposed method extends the application of Ising machines to larger-size combinatorial optimization problems with linear equality constraints.
Optimum or quasi-optimum solutions of combinatorial optimization problems can be efficiently found by using Ising machines. The graph coloring problem (GCP) is known as a difficult combinatorial problem. Given a graph, each vertex should be assigned a color and any two vertices connected by an edge must not be colored the same. Although methods to map the GCP onto the Ising model are proposed, none of them considers minimizing the number of colors. In this paper, we propose a mapping method of the GCP including minimizing the number of colors and additional constraints to the QUBO (Quadratic Unconstrained Binary Optimization) model. As well as the constraint terms for the GCP, we firstly propose an objective function term that can minimize the number of colors so that the number of used spins cannot increase exponentially. Secondly, we propose two more additional terms so that our proposed method can be applicable to practical consumer applications. The experimental evaluations on an Ising machine showed that the proposed method reduces the number of used colors by up to 75.1% on average compared with the existing baseline method. Considering the additional constraints, the proposed method can effectively find feasible solutions satisfying all the constraints.
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.