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

Lecture notes in networks and systems

QUBO Model Formulation Based on Petri Net Behavioral Description for Combinatorial Optimization Problems

Keisuke Tokuhira, Morikazu Nakamura, Mitsunaga Kinjo, Katsuhiko Shimabukuro

Published Oct 20, 2022• 0 citations
Publisher
DOI
10.1007/978-3-031-19958-5_77

Related papers

QUBO Model Formulation for Flow-shop Scheduling Problems with Changeover based on Timed Colored Petri Nets

Takuya Shinjo, Morikazu Nakamura, Norihiko Itani

Quadratic unconstrained binary optimization (QUBO) and Ising models are standard formats for the problem instance formulation of quantum annealing and quantum approximate optimization algorithm. This paper proposes a formulation method of QUBO models for flexible flow-shop scheduling problems with resource changeover based on timed colored Petri nets. The proposed method generates QUBO models for such practical flow-shop scheduling problems from Petri net firing rules, problem-specific constraints, and optimization criteria. The proposed method requires us to use only the domain knowledge of the target optimization problem and simple rules of Petri nets. Our method provides a low-cost formulation and reduces the hurdle to increasing the usability of quantum annealing and QAOAs.

International Symposium on Computing and Networking Workshops (CANDARW)•Nov 1, 2022•4 citations

QUBO solver for combinatorial optimization problems with constraints

Fumiyo Takano, Motoi Suzuki, Y. Kobayashi +1 more

IEICE Technical Report; IEICE Tech. Rep.•Nov 21, 2019•7 citations

Quadratic Unconstrained Binary Optimization (QUBO) Modeling

WORLD SCIENTIFIC eBooks•Mar 20, 2023•2 citations

Petri Net Modeling for Ising Model Formulation in Quantum Annealing

Morikazu Nakamura, Kohei Kaneshima, Takeo Yoshida

Quantum annealing is an emerging new platform for combinatorial optimization, requiring an Ising model formulation for optimization problems. The formulation can be an essential obstacle to the permeation of this innovation into broad areas of everyday life. Our research is aimed at the proposal of a Petri net modeling approach for an Ising model formulation. Although the proposed method requires users to model their optimization problems with Petri nets, this process can be carried out in a relatively straightforward manner if we know the target problem and the simple Petri net modeling rules. With our method, the constraints and objective functions in the target optimization problems are represented as fundamental characteristics of Petri net models, extracted systematically from Petri net models, and then converted into binary quadratic nets, equivalent to Ising models. The proposed method can drastically reduce the difficulty of the Ising model formulation.

arXiv:2107.04304•Applied Sciences•Aug 18, 2021•7 citations

AutoQUBO v2: Towards Efficient and Effective QUBO Formulations for Ising Machines

Justin Pauckert, Mayowa Ayodele, Marcos Diez García +2 more

The QUBO framework provides a way to model, in principle, any combinatorial optimization problem and enables the use of Ising machines to solve it. Ising machines are devices designed to quickly find good solutions to QUBO problems. In previous work, Auto-QUBO was designed to automatically generate QUBO formulations from a high-level problem description. We address two shortcomings of this method. It only works on a per-instance basis, making repeated formulations for similar problems inefficient, and relies on the user to specify penalty weights. This work introduces symbolic sampling, which provides QUBO formulations for entire problem classes. We demonstrate the speedup that can be achieved with this approach using instances of the maximum clique problem. Additionally, we use proven methods to compute valid penalty weights automatically to simplify the translation process. By providing a user-friendly way to generate QUBO formulations in an efficient manner, both in terms of time and problem difficulty, we enable more people to use Ising machines for combinatorial optimization.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 15, 2023•14 citations

Penalty and partitioning techniques to improve performance of QUBO solvers

Amit Verma, Mark W. Lewis

Discrete Optimization•Jun 29, 2020•77 citations
Quadratic unconstrained binary optimization (QUBO) and Ising models are standard formats for the problem instance formulation of quantum annealing and quantum approximate optimization algorithm. This paper proposes a formulation method of QUBO models for flexible flow-shop scheduling problems with resource changeover based on timed colored Petri nets. The proposed method generates QUBO models for such practical flow-shop scheduling problems from Petri net firing rules, problem-specific constraints, and optimization criteria. The proposed method requires us to use only the domain knowledge of the target optimization problem and simple rules of Petri nets. Our method provides a low-cost formulation and reduces the hurdle to increasing the usability of quantum annealing and QAOAs.
Quantum annealing is an emerging new platform for combinatorial optimization, requiring an Ising model formulation for optimization problems. The formulation can be an essential obstacle to the permeation of this innovation into broad areas of everyday life. Our research is aimed at the proposal of a Petri net modeling approach for an Ising model formulation. Although the proposed method requires users to model their optimization problems with Petri nets, this process can be carried out in a relatively straightforward manner if we know the target problem and the simple Petri net modeling rules. With our method, the constraints and objective functions in the target optimization problems are represented as fundamental characteristics of Petri net models, extracted systematically from Petri net models, and then converted into binary quadratic nets, equivalent to Ising models. The proposed method can drastically reduce the difficulty of the Ising model formulation.
The QUBO framework provides a way to model, in principle, any combinatorial optimization problem and enables the use of Ising machines to solve it. Ising machines are devices designed to quickly find good solutions to QUBO problems. In previous work, Auto-QUBO was designed to automatically generate QUBO formulations from a high-level problem description. We address two shortcomings of this method. It only works on a per-instance basis, making repeated formulations for similar problems inefficient, and relies on the user to specify penalty weights. This work introduces symbolic sampling, which provides QUBO formulations for entire problem classes. We demonstrate the speedup that can be achieved with this approach using instances of the maximum clique problem. Additionally, we use proven methods to compute valid penalty weights automatically to simplify the translation process. By providing a user-friendly way to generate QUBO formulations in an efficient manner, both in terms of time and problem difficulty, we enable more people to use Ising machines for combinatorial optimization.