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

[arcondello]

Example for a QAP

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.

[ACE07-Sev]

What would be the purpose of the graph besides visualization? I believe if it serves any logical purpose (by logical meaning we would use it elsewhere and try to interpret/infer something from it) then it should be a Iterable[Iterable[c0 dtype]] and we could then have a method that would access this Iterable of Iterables and construct the graph.

As for the name, if the literature doesn't have a standard meaning for it, why not name it as is, i.e. "Constraint Relationship Graph". I'd like to have a crack at this if possible, may I ask if there are any specific format you would prefer this, and in any specific file for a PR?

[arcondello]

What would be the purpose of the graph besides visualization?

It can serve a logical purpose in some instances.

I believe if it serves any logical purpose (by logical meaning we would use it elsewhere and try to interpret/infer something from it) then it should be a Iterable[Iterable[c0 dtype]] and we could then have a method that would access this Iterable of Iterables and construct the graph.

I agree that a more general format is probably preferable. Upon further consideration I think {c0: [c1, ...], c1: [c0, ...], ...} is probably the best return type. This would allow automatic construction of a NetworkX graph, e.g.

G = nx.Graph(cqm.constraint_dual_graph())

We could also allow a bit more future proofing by using a triple-nested-dict structure {c0: {c1: {}, ...}, ...} which would allow the addition of edge data (for instance maybe the list of shared variables?) in the future. If we go with the former, I do think we should document that users should only expect that the "inner" iterable is an iterable, rather than a list specifically. So

class ConstraintedQuadraticModel:
    ...
    def constraint_dual_graph(self) -> typing.Dict[typing.Hashable, typing.Iterable[typing.Hashable]]:
        ...

that way we can go from dict-of-lists to dict-of-dict-of-dict later if we like.

As for the name, if the literature doesn't have a standard meaning for it, why not name it as is, i.e. "Constraint Relationship Graph".

On further review, I think constraint dual graph is the literature name for it. So I like constraint_dual_graph() as a name for the method.

I'd like to have a crack at this if possible, may I ask if there are any specific format you would prefer this, and in any specific file for a PR?

Contributions are very welcome! See above for opinions on the formatting. As for the file, I think as a method of the ConstrainedQuadraticModel in this file.