Penalty Coefficient Adjustment Technique for Extended Ising Machines

Abstract

We have developed an extended Ising machine that extends the energy function, which is restricted to a binary-quadratic form in conventional Ising machines, to include a variety of penalty functions representing inequality constraints and higher-order energy terms. Such an extension opens up the possibility of dealing with problems featuring many (e.g., thousands or more) constraints. However, for problems with so many constraints, it is often necessary to adjust the value of the penalty coefficient, which represents the ratio of the penalty function to the total cost function, in order to find a solution. In this paper, we propose a penalty coefficient adjustment technique that can be combined with the parallel trial-based Exchange Monte Carlo method, a search algorithm for the extended Ising machine. The proposed algorithm enables us to solve the inequality constraint problem, which previously had the difficulty of manually determining penalty coefficients by trial and error. It also improves the solution quality. In two of the five QPLIB instances we tested, the extended Ising machine with fixed penalty coefficients obtained either a previous or a new best-known solution depending on the random seed, while the proposed coefficient adjustment method obtained a new best-known solution with all ten random seeds used.

Keywords

• Penalty coefficient adjustment
• Ising machine
• combinatorial optimization
• MCMC
• parallel tempering
• QUBO