Transforming optimization problems into a QUBO form: A tutorial

Practically relevant problems of quadratic optimization often contain multidimensional arrays of variables interconnected by linear constraints, such as equalities and inequalities. The values of each variable depend on its specific meaning and can be binary, integer, discrete, and continuous. These...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-10
Main Authors: Semenov, Alexander M, Usmanov, Sergey R, Fedorov, Aleksey K
Format: Article
Language:English
Subjects:
Arrays
Constraints
Optimization
Variables
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Practically relevant problems of quadratic optimization often contain multidimensional arrays of variables interconnected by linear constraints, such as equalities and inequalities. The values of each variable depend on its specific meaning and can be binary, integer, discrete, and continuous. These circumstances make it technically difficult to reduce the original problem statement to the QUBO form. The paper identifies and considers three main transformations of the original problem statement, namely, the transition from a multidimensional to a one-dimensional array of variables, the transition in mixed problems to binary variables, and the inclusion of linear constraints in the objective function in the form of quadratic penalties. Convenient formulas for calculations are presented and proven, simplifying the implementation of these transformations. In particular, the formulas for the transition in the problem statement from a multidimensional to a one-dimensional array of variables are based on the use of the Kronecker product of matrices. The considered transformations are illustrated by numerous examples.
ISSN:2331-8422