ImpossibleBQM raised for possible BQM

[mcfarljm]

Description The following:

import dwavebinarycsp

csp = dwavebinarycsp.ConstraintSatisfactionProblem(dwavebinarycsp.BINARY)
def sum_to_one(*args):
    return sum(args) == 1
nvar = 7
ngroup = 4
for igroup in range(ngroup):
    vars = [igroup*nvar + i for i in range(nvar)]
    csp.add_constraint(sum_to_one, vars)
bqm = dwavebinarycsp.stitch(csp)

produces:

ImpossibleBQM: No penalty model can be build for constraint Constraint.from_configurations(frozenset({(0, 0, 1, 0, 0, 0, 0), 
(0, 0, 0, 0, 0, 1, 0), (0, 1, 0, 0, 0, 0, 0), (0, 0, 0, 0, 0, 0, 1), (0, 0, 0, 0, 1, 0, 0), (1, 0, 0, 0, 0, 0, 0), (0, 0, 0, 
1, 0, 0, 0)}), (0, 1, 2, 3, 4, 5, 6), Vartype.BINARY, name='Constraint')  

This is misleading because the BQM should be possible.

Note that adding max_graph_size=9 to stitch() resolves the error.

Steps To Reproduce See above.

Expected Behavior Error message indicating that the problem is related to graph size as opposed to the BQM being impossible.

Environment

• dwavebinarycsp version 0.1.2
• python 3.7

[mcfarljm]

Some other observations:

• The original example can be simplified by setting ngroup=1 and the problem remains
• Keeping with the simplification ngroup=1, it's not clear why some combinations of nvar and max_graph_size work and others don't. The following are some results for cases where max_graph_size >= nvar:

nvar	max_graph_size	Outcome
3	3	Runs
4	4	Runs
5	5	No penalty model can be built
6	6	No penalty model can be built
7	7 or 8	No penalty model can be built
8	8 or 9	No penalty model can be built

From further inspection, the issue may be stemming from how auxiliary variables are being created. For example, with nvar=4, print(list(bqm)) produces the following:

[0, 1, 2, 3]

whereas, with nvar=5 we get:

[0, 1, 2, 3, 4, 'aux0']

So it's unclear why an auxiliary variable is needed when constructing the one-hot constraint with 5 variables, but it is not needed when doing so with 4 variables.

[arcondello]

Ah, I understand what the problem is. So the important thing to know about this library is it constructs constraints with a minimum gap subject to the Ising energy range.

So the "normal" 1-in-N constraint (\sum_i x_i - 1)^2 will not be generated since, when constrained to a specific energy range, will have smaller and smaller gap as N increases. One way to help this problem is to create auxiliary variables. So penaltymodel does that for a little while and then runs out of variables.

I am pretty sure if you do bqm = dwavebinarycsp.stitch(csp, min_classical_gap=.00001) it will construct them without aux variables.

[mcfarljm]

Ah, yes setting min_classical_gap does allow the BQM to be constructed in those cases. Not sure if there is any good way to address this via the error messages, but it certainly threw me for a loop.