Solving Constrained Quadratic Models with LeaphHybridCQMSampler class

[pabloT97]

Working with Constrained Quadratic Models, I have tried to implement the example of the bin packing problem which appears on :

https://docs.ocean.dwavesys.com/en/latest/docs_dimod/reference/constrained.html#dimod.ConstrainedQuadraticModel

On this easy problem, clearly the best solution is to use 2 bins.

Applying the same exact code as it appears on the link, I try to solve it calling the sample:

LeapHybridCQMSampler().sample_cqm(cqm)

But it returns each time a different result (most of the time a bad one).

What could this be due to?? The problem can be solved manually, so the solver should arrive almost always to the optimal solution. Moreover, as we are working with Leap's Hybrid, the only parameter of the solver that may be changed is time_limit, which would have no effect.

I reformulated the problem as QUBO (assigning different weights to the constraints) and I got a good result using LeapHybridSampler

[mcfarljm]

Hi Pablo, can you double-check or share the code that you are using to evaluate the optimal solution returned by the CQM solver? I have tried this myself using the below code, and every solution that I have seen is a feasible solution that uses 2 bins.

sampler = LeapHybridCQMSampler()

results = sampler.sample_cqm(cqm)
best = results.filter(lambda s: s.is_feasible).first

print('Solution feasible:', best.is_feasible)
print('Number of bins used:', cqm.objective.energy(best.sample))

for name, value in best.sample.items():
    if value and name.startswith('x'):
        indices = [int(x) for x in name.split('_')[1:]]
        print(f"Item {indices[0]} goes in bin {indices[1]}")

Here is example output:

Solution feasible: True
Number of bins used: 2.0
Item 0 goes in bin 3
Item 1 goes in bin 2
Item 2 goes in bin 2
Item 3 goes in bin 3

[pabloT97]

Thank you very much for your response. I have seen now where the problem was.

When selecting the best solution I did no apply the filter that ensures that the solution is feasible., taking my solution to be just

best=results.first.

I think therefore that I misunderstood how the LeapHybridCQMSampler solver works, as in the BQM formulation, the sample with less energy is going to be the one that satisfies all of the constraints (if the problem is feasible, as in this case).

Could you please give me some references where I can see how CQM problems are solved in terms of formulation?

Thank you very much

[mcfarljm]

No worries, the CQM features are very new. There are some more detailed and complete examples available under the Getting Started guide and the dwave-examples repository:

• https://docs.ocean.dwavesys.com/en/stable/examples/hybrid_cqm_binpacking.html
• https://docs.ocean.dwavesys.com/en/stable/examples/hybrid_cqm_stock_selling.html
• https://github.com/dwave-examples/distributed-computing
• https://github.com/dwave-examples/paint-shop-optimization
• https://github.com/dwave-examples/job-shop-scheduling-cqm
• https://github.com/dwave-examples/knapsack

One thing to note about the difference vs BQM is that the CQM stores the objective and constraints as separate objects. In the BQM formulation, the user must encode the constraints as part of the objective function using a penalty function. Once that is done, unconstrained solvers operate on a BQM and know only about a single objective function that it is to be minimized. On the other hand, the CQM has information about the objective as distinct from the constraints. As such, each solution returned by the CQM solver has separate attributes for the objective function value and the feasibility of each individual constraint. The objective/energy function values returned by the CQM sampler do not have any constraint penalties included, since information about constraint feasibility is available through separate attributes.

[pabloT97]

Thank you very much for your help. I will have a look at those links.

[ACE07-Sev]

I'm having issue with CQM as the constraints don't seem to be taking effect. here is my code : https://github.com/ACE07-Sev/CQM/blob/a9ee5bcf625d597e57a274e86598c95c3ed06444/CQM_.py