dwavesystems / dwavesystems/dimod

Consider adding a method that measures the "frustration" of a BQM

Open
#1,369 0 comments 0 reactions 0 assignees View on GitHub
enhancement
Dominant language
Python
Stars
143
Forks
91
Avg merge
1h 24m
Merged PRs (30d)
3

Description

"Frustration" is in some sense a measure of problem hardness. That is, what is the energy contribution of the linear and quadratic biases that are violated by a given solution.

Something like
```python
import dimod

def frustration(bqm, sample):
frustration = 0

for v, bias in bqm.linear.items():
frustration += max(0, sample[v] * bias)

for (u, v), bias in bqm.quadratic.items():
frustration += max(0, sample[u] * sample[v] * bias)

return frustration

if __name__ == "__main__":
bqm = dimod.generators.gnp_random_bqm(10, .5, "SPIN")
sampleset = dimod.ExactSolver().sample(bqm)
sample = sampleset.first.sample
print("energy:", sampleset.first.energy)
print("frustration:", frustration(bqm, sample))
```

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.