2
$\begingroup$

using this paper, I want to implement a solution for the Job Shop Problem on a D-Wave machine. One of the constraints mentioned in the paper, is $$ h_3(\bar{x}) = \sum_i \left(\sum_t x_{i,t}-1 \right)^2, $$ and I'm curious, how to implement a general BQM for it. I need to create a Qubo matrix, based on the solution of this sum. For that I have rewritten it to $$ \sum_i \left(\sum_t x_{i,t}-1 \right)^2 = \sum_i\left(2\sum_t\sum_{u>t}x_{it}x_{iu} - \sum_tx_{it} +1\right) $$ and tried to fill the generall matrix with these loops

for i in range (num_operations):
    for u in range(upper_time_limit):
        for t in range(u):
            # What to do with 2* x_{it}x_{iu} ?
    for t in range(upper_time_limit):
        Q[i][t] -= 1

Here I am unsure about how to handle the first part, with situations like $x_{2, 3}x_{2,4}$, and I'm not sure what to do with the $+1$ in the end.

I appreciate any help!

$\endgroup$
1
$\begingroup$

From what I understand, $x_{i,t}$ are the binary variables. So your QUBO matrix should not be indexed as Q[i][t]. If you do this way, this means you have a binary variable $x_i$ and a binary variable $x_t$ and they have a real coefficient, so representing a term $Q[i][j] *x_i x_j$.

In this case, if you really want a QUBO matrix with a correct indexing, you should reindex or relabel. Or even simpler, think of a simple matrix reindexing from 2D to 1D, by applying the function: $$ R: (i,u) \rightarrow i*U + u $$ U being your $upper\_time\_limit$ or number of columns; and then you can simply call $Q[R(i,t)][R(i,u)]$.

The $+1$ at the end will just end up in a constant factor that you do not submit to the QPU. So you can store your constants in an offset variable if you really want but adding it to the evaluations you get after running the QPU with your problem.

|improve this answer|||||
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.