How to convert equality/inequality constraint to a BQM?
Hi,
I need to submit a BQM to DWaveSampler. Since my problem has both objective and constraints, my understanding is that I need to add the latter as bqm to a composite BQM, which is then send to the solver (this can be done via bqm.update(contraint_n), where contraint_n is a dimod.binary.binary_quadratic_model.BinaryQuadraticModel).
My constraints are quite complicated and include many variables, how would you suggest to proceed in order to convert them to BQM?
Another possibility would be to use Pyqubo and use the .compile()_to_bqm method, but I could not find examples with complicated constraints and/or inequality constraints.
Thanks in advance,
Angela
Thank you in advance.
Comments
Hi Angela,
Thank you for reaching out. Can you please elaborate more on what do you mean by complicated constraint?
Best Regards,
Tanjid
Thank you for your reply Tanjid.
By 'complicated' constraint I mean several things: 1. Inequality constraint, which is not clear to me how to convert in BQM (I read some documentation and they suggest to introduce slack variables, but I do not know how to do that and what is the rationale behind this strategy); 2. Many variables (> 90, 000) in the constraint (as in the objective).
Besides this, what makes my problem more 'complicated' is the absolute value in the objective function, which is not handled by BQM. Substituting it with square does not work because of the high number of variables.
Hope I clarified myself!
Thanks a lot,
Angela
Hi Angela,
Thanks for the clarifying our questions and providing more details
1) Many Variables: Is there a specific reason or limitation that's preventing you from using CQM?
2) Inequality constraint: Are you referring to the explanation and example here: Reformulating a Problem? The following section provides a guide with an example for using slack variables to transform the inequalities to equalities.
CQM supports up to 500,000 variables and 100,000 constraints. It would support constraints directly, rather than having to encode them as penalty terms in the objective. Please have a look at this document for more information: Hybrid Solver for Constrained Quadratic Models (Table 1, Page 5).
Please let us know if you have any questions.
With kind regards,
Tanjid
Thank you Tanjid!
The reason I would like to avoid using CQM is that I do not want to use a hybrid solver. I want to run my problem fully on a quantum annealer to compare the classical solution with the quantum one.
The difficulty of converting inequality to equality constraint is best explained in this paper (paragraph following Eq. 3). So I definitely need support from a quantum computing expert to sort this out.
Last but not least, the objective function that I want to minimize includes the absolute value and this is not handled by D-wave for some reasons. Also squaring does not work. I find this a bit frustrating, as the typical instance of an objective function to be minimized is either L1-norm- or the L2-norm-based.
It would be great to have on board of our scientific project someone from the Quantum Computing community that could help us finalizing the problem! Everything is so new and far from our world that a small effort from your side would be a big step for us! :)
Thanks a lot again Tanjid!
Hello,
What was the problem you were facing when squaring? Could you please elaborate a bit on what is not working here?
There are some examples of how to formulate Inequality and Equality Constraints in the docs.
Formulation can be very problem-specific.
On one hand, working more closely with the QPU architecture directly will allow a tighter embedding and implementation, but essentially means optimizing for the problem and architecture, which in itself is a non-trivial task for any system.
On the other hand, working with the available Ocean tools will allow for easier problem formulation and system utilization.
You can formulate your problem as a BQM and use the add_linear_equality_constraint and add_linear_inequality_constraint functions in the docs.
As for the CQM not running directly on the QPU, this is not exactly the case. Both BQMs and CQMs can run using Hybrid samplers. They can also both be run on the QPU directly if properly formulated. This is not recommended though, as the size of the problem that would fit on the QPU would be much smaller and they were not designed with this use-case in mind. To do this an embedding composite would have to be used and the problem would have to be converted to a BQM from a CQM, which there is a helper function for.
solver = EmbeddingComposite(DWaveSampler())
sampleset = solver.sample(dimod.cqm_to_bqm(cqm))
Ideally to run a problem on the QPU, it should be directly formulated on the QPU architecture. This can be extremely labour intensive, which is why the embedding tools were developed to facilitate adaptation of generic QUBOs to the shape of the architecture. For more information please take a look at Minor Embedding Documentation for more details:
We can also look into having one of our associates reach out to discuss options moving forward.
Hello,
I was just rereading through your earlier posts and I was wondering if you had thought to try something like sympy with its function simplify in order to do the squaring operation. I am not sure what the library can handle, but either something like this or a programmatic solution that uses loops and sets might work for formulating the squared polynomial with some development effort.
I hope this idea is helpful. Please let us know if you make any progress.
Thank you David J for your help :)
I will check if this is helpful and let you know. Meanwhile, I am trying to formulate my problem as a CQM only. Most of the effort is to make it efficient. Even setting the binary variable with dimod.Binary() is taking a lot of time given the size of the problem. I hope I will sort it out in a way.
Angela
Solved by substituting the square of the difference with the absolute value:
penalty = dimod.Binary('penalty')
obj = 0
for i in range(rows):
expra = 0
for j in range(..., ...):
if ... :
expra += ...
difference = expra - 2
cqm.add_constraint(difference - penalty <= 0)
cqm.add_constraint(-difference -penalty <= 0 )
obj += penalty
cqm.set_objective(obj)
Please sign in to leave a comment.