US 2025/0165807 A1 · METHODS AND SYSTEMS FOR OPTIMIZATION PROBLEM TRANSFORMATION FOR FACILITATED RESOLUTION

Abstract

Methods and system for transformation of an optimization problems to facilitate its resolution are provided. According to at least one aspect of the present embodiments, a method includes casting the optimization problem into a quadratic unconstrained binary model and transforming the optimization problem into an optimization problem in the same model but with reduced connectivity. Transforming the optimization problem into the optimization problem with reduced connectivity includes partitioning decision variables in the quadratic unconstrained binary model into two or more groups, each of the two or more groups comprising at least one decision variable node and introducing a register variable node between adjacent pairs of the at least one decision variable node in the two or more groups to hold partial values of a sum in a linear constraint to form the optimization problem with reduced connectivity.

Claims30

Dependent claims

A computer-implemented method for transformation of an optimization problem to facilitate its resolution, the method comprising:

casting the optimization problem into a quadratic unconstrained binary model;
and
transforming the optimization problem into an optimization problem having the quadratic unconstrained binary model with reduced connectivity, wherein transforming the optimization problem comprises:
partitioning decision variables in the quadratic unconstrained binary model into two or more groups, each of the two or more groups comprising at least one decision variable node;
and
introducing a register variable node between adjacent pairs of the at least one decision variable node in the two or more groups to hold partial values of a sum in a linear constraint to form the optimization problem with reduced connectivity.

3 more elements

A system for transformation of an optimization problem to facilitate resolution of the optimization problem, the system comprising:

one or more processors;
and
storage means connected to the one or more processors, the storage means comprising instructions for controlling the one or more processors to:
cast the optimization problem into a quadratic unconstrained binary model;
and
transform the optimization problem into an optimization problem having the quadratic unconstrained binary model with reduced connectivity, wherein transforming the optimization problem comprises instructions to control the processor to:
partition decision variables in the quadratic unconstrained binary model into two or more groups, each of the two or more groups comprising at least one decision variable node;
and
introduce a register variable node between adjacent pairs of the at least one decision variable node in the two or more groups to hold partial values of a sum in a linear constraint to form the optimization problem with reduced connectivity.

6 more elements

Dependencies are inferred from the claim text.

Methods and systems for optimization problem transformation for facilitated resolution

Life of this patent

Methods and systems for optimization problem transformation for facilitated resolution

Life of this patent

Abstract

Claims30