Paper Image

Simplifying optimization with ordering constraints

Published on:

11 July 2023

Primary Category:

Optimization and Control

Paper Authors:

Kentaro Ohno,

Nozomu Togawa

Bullets

Key Details

Proposes method to identify ordering constraints between variables that preserve optima

Technique simplifies QUBO problems by reducing quadratic terms

Enables solution of larger problems via minor embedding

Improves solutions from quantum annealer on knapsack problems

AI generated summary

Simplifying optimization with ordering constraints

This paper proposes a technique to simplify optimization problems solved with Ising machines, which are specialized computers for combinatorial optimization. The key idea is to identify and impose ordering constraints between variables that preserve optimal solutions. This reduces quadratic terms in the optimization objective, making the problem easier to solve. The technique is applied to quadratic unconstrained binary optimization (QUBO) problems, improving minor embedding and enabling solution of larger problems on quantum annealers. Experiments on multi-dimensional knapsack problems demonstrate substantially improved solutions from the D-Wave Advantage quantum annealer.

Answers from this paper

Comments

No comments yet, be the first to start the conversation...

Sign up to comment on this paper

Sign Up