Solving the Cubic Knapsack Problem using the Quantum-Inspired Digital Annealer Technology

This study investigates the effectiveness of quantum methods in tackling the cubic knapsack problem (CKP). The CKP is not only NP-hard but also extremely difficult to solve in practice. Benchmark instances of small size (including some with only 60 items) remain unsolved to proven optimality. We solve the CKP using the latest Digital Annealer (DA) prototype, an extended Ising machine available through the Quantum-Inspired Integrated Optimization (QIIO) service on Fujitsu's Kozuchi platform. Specifically, we propose two formulations: a higher-order unconstrained binary optimization (HUBO) and a quadratic unconstrained binary optimization. The latter is derived by reformulating the HUBO model into an equivalent quadratic form. These models are solved using the QIIO solver and compared with three state-of-the-art algorithms, a greedy heuristic, and two mixed integer programs. Additionally, we introduce a postprocessing heuristic to ensure the feasibility of solutions generated by the DA solver, as within short time limits, it does not always produce feasible solutions. Computational experiments are conducted on instances with up to 200 items and varying densities of nonzero objective coefficients. The results indicate that the HUBO formulation is highly competitive with state-of-the-art algorithms, achieving the best new solutions for six large instances.