Binary Quadratic Models (BQMs) are a powerful and versatile class of mathematical optimization problems. They are used to represent a wide range of combinatorial optimization challenges across various fields. A Binary Quadratic Model involves optimizing an objective function that is quadratic in binary variables (variables that can only take the values 0 or 1, or sometimes -1 and 1).
Here is an example implementation of solving a Quadratic Unconstrained Binary Optimization (QUBO) problem using Python and the dimod library, which is part of the D-Wave Ocean SDK.
https://gist.github.com/viadean/f69e767c9090b2ed608ed3a832b5f06b
Q is defined as a dictionary where the keys are tuple indices (i, j) representing the interaction between binary variables (x_i) and (x_j), and the values are the coefficients for those interactions.dimod.BinaryQuadraticModel.from_qubo(Q) function converts the QUBO matrix into a Binary Quadratic Model, which is the input format required by solvers.ExactSolver is a classical solver that exhaustively evaluates all possible binary variable combinations to find the optimal solution. For larger problems, you can use SimulatedAnnealingSampler or a quantum solver such as D-Wave's sampler.results.data(["sample", "energy"]) method iterates over the solutions, where sample is a dictionary of variable assignments, and energy is the objective function value.For the given QUBO matrix , the output may look like this:
https://gist.github.com/viadean/ba92f91af3f510be583e0c6560b4ab39
Here’s a demonstration of solving a QUBO problem using different solvers. I will provide implementations for Simulated Annealing, Gurobi, and D-Wave's Quantum Solver.
Simulated Annealing is a heuristic method that works well for optimization problems like QUBO.
https://gist.github.com/viadean/0d4eba6ed5d3920b2e51efcd47de41c5
Gurobi is a powerful mathematical programming solver that can handle QUBO problems.
https://gist.github.com/viadean/aa0877200f03368ae6a8e6a06b5807f6