Performance of the Extended Ising Machine for the Quadratic Knapsack Problem

Abstract

The extended Ising machine (EIM) enhances conventional Ising models, which handle only binary quadratic forms by allowing constraints through real-valued dependent variables. We address the quadratic knapsack problem (QKP), hard to solve using Ising machines when formulated as a quadratic unconstrained binary optimization (QUBO). We demonstrated the EIM's superiority by comparing it with the conventional Ising model-based approach, a commercial exact solver, and a state-of-the-art heuristic solver for QKP.

6 pages

References in corpus (6)

• Exchange Monte Carlo Method and Application to Spin Glass Simulations
• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• Domain-Wall Free-Energy of Spin Glass Models:Numerical Method and Boundary Conditions
• Jump Markov Chains and Rejection-Free Metropolis Algorithms
• Toward Practical Benchmarks of Ising Machines: A Case Study on the Quadratic Knapsack Problem
• A Fast and Effective Breakpoints Heuristic Algorithm for the Quadratic Knapsack Problem