Why does "is_satisfied" seem to report incorrect information regarding if a constraint is satisfied?

In the example below, I solve a simple model, in which I add constraints to a model, and then check to see which constraints are violated by the solution by calling `is_satisfied`. on the first sample. However, what you'll see from the example below is that it reports that some of the constraints are satisfied (as indicated by "True"), when in fact this clearly is not the case. 

 

cqm_model = dimod.ConstrainedQuadraticModel()
# create binary variables
var_strings=['x_0_0_1_1', 'x_0_0_1_2', 'x_0_0_1_3', 'x_0_0_1_4', 'x_2_0_1_1', 'x_2_0_1_2', 'x_2_0_1_3', 'x_2_0_1_4', 'x_0_0_2_2', 'x_0_0_2_4', 'x_1_0_2_2', 'x_1_0_2_4', 'x_1_1_2_2', 'x_1_1_2_4', 'x_3_0_2_2', 'x_3_0_2_4', 'x_3_1_2_2', 'x_3_1_2_4', 'x_0_0_3_2', 'x_0_0_3_3', 'x_0_0_3_4', 'x_1_0_3_2', 'x_1_0_3_3', 'x_1_0_3_4', 'x_1_1_3_2', 'x_1_1_3_4', 'x_2_0_3_2', 'x_2_0_3_3', 'x_2_0_3_4', 'x_2_1_3_2', 'x_2_1_3_3', 'x_2_1_3_4']
for i,var_name_string in enumerate(var_strings):
    exec_string = 'cqm_model.' + var_name_string + '=dimod.Binary(\''+var_name_string+'\')'
    exec(exec_string)

# add constraints
cqm_model.add_constraint(cqm_model.x_0_0_1_1 + cqm_model.x_0_0_1_2 + cqm_model.x_0_0_1_3 + cqm_model.x_0_0_1_4 + cqm_model.x_2_0_1_1 + cqm_model.x_2_0_1_2 + cqm_model.x_2_0_1_3 + cqm_model.x_2_0_1_4 == 1.0, label='constr_1') 
cqm_model.add_constraint(cqm_model.x_0_0_2_2 + cqm_model.x_0_0_2_4 + cqm_model.x_1_0_2_2 + cqm_model.x_1_0_2_4 + cqm_model.x_1_1_2_2 + cqm_model.x_1_1_2_4 + cqm_model.x_3_0_2_2 + cqm_model.x_3_0_2_4 + cqm_model.x_3_1_2_2 + cqm_model.x_3_1_2_4 == 1.0, label='constr_2')
cqm_model.add_constraint(cqm_model.x_0_0_3_2 + cqm_model.x_0_0_3_3 + cqm_model.x_0_0_3_4 + cqm_model.x_1_0_3_2 + cqm_model.x_1_0_3_3 + cqm_model.x_1_0_3_4 + cqm_model.x_1_1_3_2 + cqm_model.x_1_1_3_4 + cqm_model.x_2_0_3_2 + cqm_model.x_2_0_3_3 + cqm_model.x_2_0_3_4 + cqm_model.x_2_1_3_2 + cqm_model.x_2_1_3_3 + cqm_model.x_2_1_3_4 == 1.0, label='constr_3')

# type 2 constraints
cqm_model.add_constraint(cqm_model.x_0_0_3_2 + cqm_model.x_1_0_3_2 + cqm_model.x_1_1_3_2 + cqm_model.x_2_0_3_2 + cqm_model.x_2_1_3_2 == 0.0, label='constr_4')
cqm_model.add_constraint(cqm_model.x_0_0_3_3 + cqm_model.x_1_0_3_3 + cqm_model.x_2_0_3_3 + cqm_model.x_2_1_3_3 == 0.0, label='constr_5')
cqm_model.add_constraint(cqm_model.x_0_0_3_4 + cqm_model.x_1_0_3_4 + cqm_model.x_1_1_3_4 + cqm_model.x_2_0_3_4 + cqm_model.x_2_1_3_4 == 0.0, label='constr_6')

# objective
cqm_model.set_objective(cqm_model.x_0_0_1_1 + cqm_model.x_0_0_1_2 + cqm_model.x_0_0_1_3 + cqm_model.x_0_0_1_4 + cqm_model.x_0_0_2_2 + cqm_model.x_0_0_2_4 + cqm_model.x_0_0_3_2 + cqm_model.x_0_0_3_3 + cqm_model.x_0_0_3_4)

sampler = LeapHybridCQMSampler()
result = sampler.sample_cqm(cqm_model)

for var in cqm_model.variables:
    if result.first.sample[var]==1.0:
        print(var)
# prints the following:
# >>> x_2_0_1_2
# >>> x_3_1_2_4

result.first.is_satisfied
# prints the following:
# >>>> array([False,  True,  True,  True,  True,  True])
cqm_model.constraint_labels
# prints the following:
# >>>> Variables(['constr_1', 'constr_2', 'constr_3', 'constr_4', 'constr_5', 'constr_6'])

Since the output is obviously non-deterministic, you may need to run the example several times before observing the behavior I described.  Clearly constraint 'constr_1' is satisfied, whereas 'constr_3' is violated.  So, I would have expected the output of 'result.first.is_satisfied' to return 

`array([True,  True,  False,  True,  True,  True])`

Is the method "is_satisfied" reporting incorrect information? Or how am I supposed to interpret this?

0

Comments

4 comments
  • As it turns out "cqm_model.iter_violations(result.first.sample)" seems like it DOES report correctly if a constraint is satisfied or not.  Can someone tell me why it has different behavior from "result.first.is_satisfied"?

     

    0
    Comment actions Permalink
  • Hello,

    The order of the constraints in is_satisfied is not guaranteed to be maintained, but is given in the info variable returned by the solver:

    result.info["constraint_labels"]

    This one is for the input labels in the CQM model:

    cqm_model.constrant_labels

    It's a little confusing, but hopefully this helps clear things up. Please let us know how this goes.

    Thanks again for reaching out, and please don't hesitate to ask any more questions.

    0
    Comment actions Permalink
  • Thanks. I do find some of the fields a little confusing. I assume this documentation is up-to-date: https://docs.ocean.dwavesys.com/en/latest/docs_dimod/reference/generated/dimod.SampleSet.lowest.html ? 

    I understand `sampleset.lowest()` will tell me the samples with the lowest energy. And, I see there is a field inside it called `is_feasible`, but I'm not able to find a way to access that field. Is there an easy way to check if th `sampleset.lowest()` is feasible? 

    0
    Comment actions Permalink
  • That's right, the documentation you linked to is the most recent.

    In the documentation for sampleset.lowest you'll see that it returns a sampleset.

    Returns:
    A new sample set containing the lowest energy samples as delimited by configured tolerances from the lowest energy sample in the current sample set.

    The object returned is a set of samples that are in a given range (provided as function parameters).

    The first sample would still need to be selected in order to check is_feasible.

    result.lowest(rtol, atol).first.is_feasible

    Samples are compared relative to the lowest energy as follows (also in the docs):

    absolute(a - b) <= (atol + rtol * absolute(b))
    0
    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post