Same machine problem in JSP demo

Marek S

July 31, 2019 18:06

Hi, i tried to learn how to implement a JSP problem solver, but i wanted to tweak the https://github.com/dwavesystems/demos/tree/master/job-shop-scheduling solution to solve a JSP problem for one machine with multiple cores, which means that every operation can be done by every "machine". I decided to use the same machine for each operation and change the "share machine constraint" so that it allows multiple operations at once. I stumbled upon a problem, that when i changed the original example input to use the same machine and made the max_time value higher, some weird aux0 and aux1 values started to appear and bugged the code. Furthermore, when i increased max_time even more, the output suggested that the solution was impossible, which seems absurd to me.

What am i doing wrong? I'll be grateful for every bit of help.

Marek Subocz

for max_time = 6:

for max_time = 7 or more:

Comments

4 comments

David J (Report)
August 13, 2019 00:04 (Edited August 13, 2019 00:08)
Hello,

My apologies for the delay in reply.

So what happens when you increase the max time parameter is that the schedule is made to have more time slots in it.

At first glance, increasing the time variable doesn't look like it should change anything, but what it is actually doing is adding time slots to the schedule.

A longer schedule with more time slots is a more complex schedule with more possible combinations.

When a problem increases in complexity, sometimes this requires the introduction of auxiliary variables.

Let's look at a simple example and then discuss how this could become more complex.

The logical expression "a OR b" can be expressed on the QPU using only three qubits.

Here is a truth table to understand the states that the three values can take and the energies needed to cause them to be valid:
```
 a   b   aORb   Energy

-1  -1  -1      Low

-1  -1   1      High

-1   1  -1      High

-1   1   1      Low

 1  -1  -1      High

 1  -1   1      Low

 1   1  -1      High

 1   1   1      Low
```
Remember that "Low" energy means that this state is more likely to appear in the results, since it is a more efficient energy state.

Looking at the valid, Low energy output states, we see that the state where "a" and "b" are false (-1), "a or b" is also false (-1).

Then we see the cases in which either or both "a" or "b" are true (1), "a or b" is also true (1).

All other combinations of bits are invalid, so ideally they will be made to have "High" energy states, in order to exclude them from the results.

A simple code example could look like this:
```
import dwavebinarycsp as dbc

csp = dbc.ConstraintSatisfactionProblem(dbc.SPIN)

csp.add_constraint({(-1, 1, 1),(1, -1, 1),(1, 1, 1),(-1, -1, -1)},('a', 'b', 'aORb'))

bqm = dbc.stitch(csp) 

print(bqm)
```
And it would result in a BQM (BinaryQuadraticModel) like this:
```
BinaryQuadraticModel({'a': 0.5, 'b': 0.5, 'aORb': -1.0}, {('a', 'b'): 0.5, ('a', 'aORb'): -1.0, ('b', 'aORb'): -1.0}, 1.5, Vartype.SPIN)
```
We could use the following code to print up a truth table with the actual energy values for the above table:
```
def calculate_or(): 

     for a, b, aORb in itertools.product({-1,1}, repeat=3): 

         energy = 0.5*a -aORb +0.5*b +0.5*a*b -a*aORb -b*aORb + 1.5 

         print(a, b, aORb, energy)  
```
The output would look like this:
```
-1  -1  -1      0.0

-1  -1   1      2.0

-1   1  -1      2.0

-1   1   1      0.0

 1  -1  -1      2.0

 1  -1   1      0.0

 1   1  -1      6.0

 1   1   1      0.0
```
Moving forward, if we think about a slightly more complex issue, such as "a XOR b", we can't represent this using just three variables.
```
import dwavebinarycsp as dbc

csp = dbc.ConstraintSatisfactionProblem(dbc.SPIN)

csp.add_constraint({(-1, -1, -1),(-1, 1, 1),(1, -1, 1),(1, 1, -1)},('a', 'b', 'aXORb'))

bqm = dbc.stitch(csp) 

print(bqm)
```
Produces:
```
BinaryQuadraticModel({'a': 0.0, 'b': -1.0, 'aXORb': 0.0, 'aux0': -1.0, 'aux1': -1.0}, {('a', 'b'): 0.0, ('a', 'aXORb'): -1.0, ('a', 'aux0'): -1.0, ('a', 'aux1'): 1.0, ('b', 'aXORb'): 0.0, ('b', 'aux0'): 1.0, ('b', 'aux1'): 1.0, ('aXORb', 'aux0'): 1.0, ('aXORb', 'aux1'): -1.0, ('aux0', 'aux1'): 0.0}, 4.0, Vartype.SPIN)
```
```
def calculate_xor(): 

     for a, b, aXORb, aux0, aux1 in itertools.product({-1,1}, repeat=5): 

         energy = -b -aux0 -aux1 -a*aXORb -a*aux0 +a*aux1 +b*aux0 +b*aux1 +aXORb*aux0 -aXORb*aux1 +4.0

         print(a, b, aXORb, aux0, aux1, energy)  
```
Output would be:
```
1 1 1 1 1 2.0

1 1 1 1 -1 2.0

1 1 1 -1 1 2.0

1 1 1 -1 -1 2.0

1 1 -1 1 1 4.0

1 1 -1 1 -1 0.0

1 1 -1 -1 1 8.0

1 1 -1 -1 -1 4.0

1 -1 1 1 1 0.0

1 -1 1 1 -1 4.0

1 -1 1 -1 1 4.0

1 -1 1 -1 -1 8.0

1 -1 -1 1 1 2.0

1 -1 -1 1 -1 2.0

1 -1 -1 -1 1 10.0

1 -1 -1 -1 -1 10.0

-1 1 1 1 1 4.0

-1 1 1 1 -1 8.0

-1 1 1 -1 1 0.0

-1 1 1 -1 -1 4.0

-1 1 -1 1 1 2.0

-1 1 -1 1 -1 2.0

-1 1 -1 -1 1 2.0

-1 1 -1 -1 -1 2.0

-1 -1 1 1 1 2.0

-1 -1 1 1 -1 10.0

-1 -1 1 -1 1 2.0

-1 -1 1 -1 -1 10.0

-1 -1 -1 1 1 0.0

-1 -1 -1 1 -1 4.0

-1 -1 -1 -1 1 4.0

-1 -1 -1 -1 -1 8.0
```
Looking closely at the 0.0 energy lines:
```
a,  b, aXORb, aux0, aux1, energy

 1  1  -1      1    -1    0.0

 1 -1   1      1     1    0.0

-1  1   1     -1     1    0.0

-1 -1  -1      1     1    0.0
```
In this snippet we can see that the valid outputs are the targets of "a XOR b".

In order to get these energies, we needed to add the aux0, and aux1 variables.

This is really similar to the scheduling issue, in adding more time slots, we are increasing the complexity of the problem in a similar way as XOR builds on OR.

In the example with max_time=7, there are several requirements for creation of a penaltymodel (one of the smaller BQMs that gets combined into the full BQM for the problem):

-The values of all valid result states must be low, as we saw above.

-The biases chosen must fall within a given range.

-The gap between the ground state and the first excited state must be above some chosen minimum classical gap.

We choose a minimum classical gap value that will provide enough energy to differentiate the ground state from other states, since the ground state is what we want, and this makes it easier to obtain the ground state on the QPU.

The default minimum gap value is 2.0.

We can reduce this value to try to squeeze more problem information onto the QPU, but it will also reduce the accuracy of the problem.

The ground state and first excited state will be closer together, so it's possible that the excited state might be confused for the ground state.

This can also lead to some strange issues with invalid schedules.

In the end, we can always check to see that the schedule makes sense and is valid.

You could try reducing the minimum gap to 1.0 by using the following line:
```
bqm = get_jss_bqm(jobs, max_time, stitch_kwargs={'min_classical_gap':1})
```
I hope this was helpful and answered your questions.

Please feel free to ask any follow up questions, or for clarification on any of the information provided.
0

Comment actions Permalink
Marek S (Report)
August 13, 2019 17:06

I already wrote this on the mirror topic at General Discussion section, but maybe writing it here too will help You find out about my problem:

I think I understood all of what you wrote and I have a little question. Do you see a way to make the algorithm work for bigger instances, without necessary compromising the quality of the result? And also, is it possible that the lower-noise version of D-wave quantum computers can help me achieve better results? I understand it might be a really complicated problem, so i'll appreciate every example, even based on some simple problems.

Marek Subocz

0

Comment actions Permalink
David J (Report)
August 13, 2019 18:03

I have closed the mirror issue, as this is the best place to discuss this issue.

1

Comment actions Permalink
David J (Report)
August 13, 2019 18:12

This JSP example is just a simple demo, and requires further development.

Coming up with a better or bigger solution will take some ingenuity.

The lower-noise version of the QPU should generally give better results.

This is an excellent opportunity for the community to get involved and help come up with ideas to improve on the simple JSP example.

If you have questions about using the existing Ocean libraries, or if you run into problems, please let us know, so we can help get you back on track!

0

Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post