Treffer: Technique for Transforming Discrete Optimization Problems into QUBO Form.

Practical discrete optimization problems often contain multidimensional arrays of variables interrelated by linear constraints such as equalities and inequalities. Values of each variable depend on its specific meaning and can be binary, integer, or discrete. These conditions make it technically difficult to reduce the original problem statement to QUBO form. We identify and examine three necessary transformations of the original problem statement to reduce it to QUBO form, namely transition from a multidimensional to a one-dimensional array, transition to binary variables in mixed problems, and incorporating linear constraints into the objective function in the form of quadratic penalties. We present and prove computationally convenient formulas to simplify these transformations. In particular, the formulas for the transition from a multidimensional to a one-dimensional array of variables are based on the application of the Kronecker product of matrices. The transformations considered are illustrated by numerous examples and used, as an application, to reduce a number of well-known problems in graph theory and combinatorial optimization to QUBO form. [ABSTRACT FROM AUTHOR]

Copyright of Problems of Information Transmission is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)