quadratic constraint with 9 variables cannot be stitched
i am trying to code a tiny job shop scheduling problem with 2 jobs à 2 operations on 2 machines, 10 time slots are available; 40 binary variables x_i_t indicate if operation i starts at time t or not; major constraints are precedence constraints between operations, one of these constraints is coded as follows:
myCsp.add_constraint(csp.Constraint.from_configurations([(1, 0, 0, 0, 0, 0, 0, 0, 0), (0, 0, 0, 0, 0, 0, 0, 0, 0), (0, 1, 0, 0, 0, 0, 0, 0, 0), (0, 0, 1, 0, 0, 0, 0, 0, 0), (0, 0, 0, 1, 0, 0, 0, 0, 0), (0, 0, 0, 0, 1, 0, 0, 0, 0), (0, 0, 0, 0, 0, 1, 0, 0, 0), (0, 0, 0, 0, 0, 0, 1, 0, 0),
(0, 0, 0, 0, 0, 0, 0, 1, 0), (0, 0, 0, 0, 0, 0, 0, 0, 1)],['x_1_7', 'x_2_1', 'x_2_2', 'x_2_3', 'x_2_4', 'x_2_5', 'x_2_6', 'x_2_7', 'x_2_8'],
csp.BINARY, name = 'c_prec'))
the corresponding penalty model is:
variables = ['i_3', 'k_1', 'k_2', 'k_3', 'k_4', 'k_5', 'k_6', 'k_7', 'k_8']
feasible_configs = {(1, 0, 0, 0, 0, 0, 0, 0, 0), (0, 0, 0, 0, 0, 0, 0, 0, 0), (0, 1, 0, 0, 0, 0, 0, 0, 0), (0, 0, 1, 0, 0, 0, 0, 0, 0),
(0, 0, 0, 1, 0, 0, 0, 0, 0), (0, 0, 0, 0, 1, 0, 0, 0, 0), (0, 0, 0, 0, 0, 1, 0, 0, 0), (0, 0, 0, 0, 0, 0, 1, 0, 0),
(0, 0, 0, 0, 0, 0, 0, 1, 0), (0, 0, 0, 0, 0, 0, 0, 0, 1)}
graph = nx.Graph()
graph.add_edges_from([('i_3', 'k_1'), ('i_3', 'k_2'), ('i_3', 'k_3'), ('i_3', 'k_4'), ('i_3', 'k_5'), ('i_3', 'k_6'), ('i_3', 'k_7'), ('i_3', 'k_8')])
spec = pm.Specification(graph, variables, feasible_configs, dimod.BINARY)
qubo = dimod.BinaryQuadraticModel({'i_3':0., 'k_1':0., 'k_2':0., 'k_3':0., 'k_4':0., 'k_5':0., 'k_6':0., 'k_7':0., 'k_8':0.},
{('i_3', 'k_1'):1., ('i_3', 'k_2'):1., ('i_3', 'k_3'):1., ('i_3', 'k_4'):1., ('i_3', 'k_5'):1., ('i_3', 'k_6'):1.,
('i_3', 'k_7'):1., ('i_3', 'k_8'):1.}, 0.0,
dimod.BINARY)
i add only the above constraint to the csp and call
bqm = csp.stitch(myCsp, 2, 11)
which never returns, i.e. it is not possible to create a bqm from the above very simple csp... what am i doing wrong?
Comments
Hello,
I would like to try to reproduce the behaviour you are seeing.
Unfortunately it looks like I have different versions of the libraries installed.
Would you be so kind as to do a pip freeze so I can reproduce your environment?
This will list out all of the libraries you have installed for your ocean virtualenv.
I am mostly concerned with the versions of the installed libraries for penaltymodel (also including penaltymodel-lp, penaltymodel-mip, penaltymodel-core, penaltymodel-cache, and penaltymodel-maxgap if installed), dwavenbinarycsp, and dwave-ocean-sdk.
It sounds like the reason it's hanging is similar to another issue one of our users ran into.
This community post discusses a similarly big problem and the issues that user ran into:
https://support.dwavesys.com/hc/en-us/community/posts/360020801573
For 5 variables the model formulation has already begun to be nontrivial, and a noticeable pause occurs.
In the case of your problem, the stitch function is trying to create a model in which all 10 of those states passed in will be ground states with an energy of 0.
This is a really hard problem to formulate, and the stitch function is likely adding lots of auxiliary values to try to attain this ideal model.
It's possible that the process is "hanging", or not finishing in a timely manner.
With the library I am using there is an error thrown:
Unfortunately this is masking a more important message:
I'm looking into correcting the error message so that it shows the correct message.
I am curious which libraries you are using that don't run into this error message.
I hope this was helpful.
Looking forward to your response!
david, thanks for your response. these are the libraries installed in my system:
certifi==2019.3.9
chardet==3.0.4
Click==7.0
cycler==0.10.0
decorator==4.4.0
dimod==0.8.12
dwave-cloud-client==0.5.4
dwave-networkx==0.7.1
dwave-system==0.7.3
dwavebinarycsp==0.0.11
homebase==1.0.1
idna==2.8
jsonschema==2.6.0
kiwisolver==1.1.0
matplotlib==3.0.3
minorminer==0.1.8
networkx==2.3
numpy==1.15.4
penaltymodel==0.16.2
penaltymodel-cache==0.4.0
penaltymodel-lp==0.1.0
penaltymodel-maxgap==0.5.1
plucky==0.4.3
pyparsing==2.4.0
PySMT==0.7.0
PySocks==1.6.8
python-dateutil==2.8.0
requests==2.21.0
scipy==1.2.1
six==1.12.0
urllib3==1.24.3
Hello,
One strange thing I noticed with this pip freeze is that I don't see dwave-ocean-sdk.
What happens if you do a pip install dwave-ocean-sdk?
Does it sow up in the pip freeze?
if i run "pip install dwave-ocean-sdk" the following error message shows up
Collecting ortools<7.0.0,>=6.6.4659 (from penaltymodel-mip<0.3.0,>=0.2.0; extra == "mip"->dwavebinarycsp[mip]<0.1.0,>=0.0.9; (platform_machine == "x86_64" or platform_machine == "amd64" or platform_machine == "AMD64") and python_version != "3.4"->dwave-ocean-sdk)
ERROR: Could not find a version that satisfies the requirement ortools<7.0.0,>=6.6.4659 (from penaltymodel-mip<0.3.0,>=0.2.0; extra == "mip"->dwavebinarycsp[mip]<0.1.0,>=0.0.9; (platform_machine == "x86_64" or platform_machine == "amd64" or platform_machine == "AMD64") and python_version != "3.4"->dwave-ocean-sdk) (from versions: none)
ERROR: No matching distribution found for ortools<7.0.0,>=6.6.4659 (from penaltymodel-mip<0.3.0,>=0.2.0; extra == "mip"->dwavebinarycsp[mip]<0.1.0,>=0.0.9; (platform_machine == "x86_64" or platform_machine == "amd64" or platform_machine == "AMD64") and python_version != "3.4"->dwave-ocean-sdk)
with "pip freeze" dwave-ocean-sdk does not show up
Hi Alexander,
Your installation error above is very similar to the one in this community post:
https://support.dwavesys.com/hc/en-us/community/posts/360029291214
In this case, 32-bit Python was installed on a 64-bit machine. Could you check which version of Python (and your OS) you have installed? For example, in Python:
thanks for your comment, luca; with 64 bit python on a 64 bit machine the installation error is resolved.
No problem, Alexander. Glad you were able to get the SDK working properly.
Please sign in to leave a comment.