minimum vertex cover problem

Sara S

May 08, 2023 08:06

I am trying to implement the minimum vertex cover problem

So here is my objective:
//minimize the number of vertices/variables
//minimize(Σ x_i , i ∈ V) (the sum is over all nodes in the graph)
cqm.set_objective(-1.5*quicksum(all_vars.values()))

And here is my constraint:
//x_i + x_j ≥ 1 for all (i, j) ∈ E
for i in range(len(pair_list)):
cqm.add_constraint((all_vars[pair_list[i][0]] + all_vars[pair_list[i][1]]) >= 1)

the constraints and objectives are from this link: hvidberrrg/d-wave: Experiments with D-Wave quantum annealing (github.com)

But it does not seem to work.

I did not want to write the constraint the way i wrote it above but it is the only way Dwave accepted it.
I wanted to write it like this:
cqm.add_constraint((all_vars[pair_list[i][0]] + all_vars[pair_list[i][1]]) >= 1 for i in range(len(pair_list)))

I appreciate your help!
I am stuck in this part.

minimum vertex cover problem

Comments

Didn't find what you were looking for?