dwavesystems / dwavesystems/dimod

generator maximum_weight_independent_set() has energy multiplied by weight

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

Description

**Description**
BQMs can be offset compared to QUBOs but this seems like a difference in the created QUBOS; for example Q1 has ``('x1', 'x1'): -1.0`` but Q2 has ``('x1', 'x1'): np.float64(-5.0)``, so all the nodes are multiplied by the first weight.

```
import dwave_networkx as dnx
import networkx as nx
import dimod
G = nx.Graph()
G.add_nodes_from(["x1", "x2"], weight=5)
G.add_nodes_from(["x3", "x4"], weight=1)
G.add_edges_from({("x1", "x2"), ("x1", "x3"), ("x1", "x4"),
("x2", "x3"), ("x2", "x4"),
("x3", "x4")})
Q1 = dnx.algorithms.independent_set.maximum_weighted_independent_set_qubo(G, weight="weight")
bqm = dimod.generators.maximum_weight_independent_set(G.edges, G.nodes("weight"))
Q2 = bqm.to_qubo()[0]
print(dimod.ExactSolver().sample_qubo(Q1))
print(dimod.ExactSolver().sample_qubo(Q2))
```

Returns the following:

```
x1 x2 x3 x4 energy num_oc.
1 1 0 0 0 -1.0 1
3 0 1 0 0 -1.0 1
7 0 0 1 0 -0.2 1
15 0 0 0 1 -0.2 1
0 0 0 0 0 0.0 1
2 1 1 0 0 0.0 1
4 0 1 1 0 0.8 1
6 1 0 1 0 0.8 1
12 0 1 0 1 0.8 1
14 1 0 0 1 0.8 1
8 0 0 1 1 1.6 1
5 1 1 1 0 3.8 1
13 1 1 0 1 3.8 1
9 1 0 1 1 4.6 1
11 0 1 1 1 4.6 1
10 1 1 1 1 9.6 1
['BINARY', 16 rows, 16 samples, 4 variables]
x1 x2 x3 x4 energy num_oc.
3 1 0 0 0 -5.0 1
7 0 1 0 0 -5.0 1
1 0 0 0 1 -1.0 1
15 0 0 1 0 -1.0 1
0 0 0 0 0 0.0 1
4 1 1 0 0 0.0 1
2 1 0 0 1 4.0 1
6 0 1 0 1 4.0 1
8 0 1 1 0 4.0 1
12 1 0 1 0 4.0 1
14 0 0 1 1 8.0 1
5 1 1 0 1 19.0 1
11 1 1 1 0 19.0 1
9 0 1 1 1 23.0 1
13 1 0 1 1 23.0 1
10 1 1 1 1 48.0 1
['BINARY', 16 rows, 16 samples, 4 variables]
```
**Environment**
- OS: MAC OS
- Python version: 3.13

Contributor guide

Open the contributing guide

Research direction

Start at maximum_weighted_independent_set_qubo(), using the provided NetworkX and dimod reproduction to compare the generated QUBO with dimod.generators.maximum_weight_independent_set. Trace how node weights are applied and add or update coverage for differing node weights. Done means the generated QUBO preserves each node's weight rather than scaling all node terms by the first weight.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
backend-api-design
Issue type
Bug
Difficulty
2/5
Estimated time
1-3 hours
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
68/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.