dwavesystems / dwavesystems/dimod

Consider addings a method to get a graph showing the relationship between constraints

Open
#1,318 2 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

Example for a QAP
```python
import itertools

import dimod
import networkx as nx

# set up a basic QAP
cqm = dimod.ConstrainedQuadraticModel()
cqm.add_variables("BINARY", itertools.product(range(10), range(5)))

for row in range(10):
cqm.add_constraint((((row, col), 1) for col in range(5)), '==', 1, label=f"row={row}")
for col in range(5):
cqm.add_constraint((((row, col), 1) for row in range(10)), '==', 1, label=f"col={col}")

# get the dual constraint graph
G = nx.Graph()
G.add_nodes_from(cqm.constraints)
for (c0, comp0), (c1, comp1) in itertools.combinations(cqm.constraints.items(), 2):
if comp0.lhs.variables & comp1.lhs.variables:
G.add_edge(c0, c1)
```
*Additional Considerations*
* Should this method/function always return a NetworkX graph and raise an error if NetworkX isn't installed, or should it always return a list-of-lists, or toggle the behavior with a parameter.
* What should we call it? I have seen this graph called the "constraint dual graph", but only in the context of CSP. In the context of MIP, I believe "dual" has a very different meaning.

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.