Converting BQM to DQM formulation
Hi,
For some background:
I am having trouble understanding the workings of the dqm.add_linear_equality_constraint() function. I understand how the input tuple needs to be formulated, but a logical discrepancy does not allow me to define the model exactly.
I am working on a factory layout problem, for which I initially used a BQM. I decided to use a DQM to reduce computation time, as it reduced the 2-dimensional matrix into a 1-dimensional list. Essentially, I converted the row labels of the matrix into cases of the column labels. This reduced the required logical qubits from 13*81 to just 81
In the factory layout problem, I have to make sure that the area of facility f is equal to the area provided in the data. I am doing this by taking each variable case of p = m (if facility f is assigned to position p), counting every occurrence of m, and constraining that to be equal to the size defined separately.
My first question: Is this implementation for each m>0 correct - to bias each case by its reciprocal value and then constrain the sum (of ones, essentially) to be = facility size?
And second: what can I do for variable case m = 0? There's really no bias I can give so that the sum of 0*bias will be 14(number of empty spaces), so I make do by keeping the constant as 0 and hoping for the best.
Nfacil = 13
len(positions) = 81
for f in range(Nfacil):
if f == 0:
c1 = [(labels[p],f,1) for p in positions]
dqm.add_linear_equality_constraint(
c1,
constant=0,
lagrange_multiplier=1
)
else:
c1 = [(labels[p],f,1/f) for p in positions]
dqm.add_linear_equality_constraint(
c1,
constant=-1*facility_size[f],
lagrange_multiplier=1
)
If anyone can point out if I'm making a logical error or suggest an alternative way of applying this constraint, i would be really grateful as it would help me move on to the next stage of my thesis.
Comments
Hello,
I am having a little trouble understanding the problem formulation.
It will greatly help if you could simplify and explain each part with examples.
The best approach would probably be to minimize your problem to a toy example to make sure it is behaving as expected. If you can make the problem small enough you can generate truth tables and solution sets to verify the code is doing what is expected, that is ideal.
For instance, using numbers like 2 or 3 rather than 13 and 81 can make things a little more manageable to start. (I think in this case maybe 13 is meant to be 14 based on it being the number of empty spaces?).
It might help to first define all of the parts of the problem in simple terms, and to describe each constraint in terms of what it should do.
Having complete code examples also helps illustrate what the expected values and comparisons are, so a minimal code example is ideal for readability.
At a high level, the problem is selecting between layouts and making sure there is enough room in the layout to fit the facility, am I understanding that correctly? And the cases are the positions within a facility, which will ultimately equate to the size of the facility, right? What does it mean that a facility is assigned to a position? What does the m = 0 case mean? There is no position (i.e. facility of size 0 = facility doesn't exist?)?
Having some concrete examples of what is in the variables will help to illustrate the problem a little better, I think. Hopefully we can clear this up a bit and find a way to verify results.
Please sign in to leave a comment.