Model not finding maximum
Answeredimport gurobipy as gpfrom gurobipy import GRB
def maximum_weighted_matching(vertices, edges):"""Compute the maximal matching of a given multigraphvertices - The number of verticesedges - A list of edges; every edge is a triple of two vertices (from 0 to vertices-1) and weightreturn - A subset of edges forming a maximal matching"""env = gp.Env("")# env.setParam('LogToConsole', 0)model = gp.Model(env=env, name = "Max Weighted Matching")model.modelsense = GRB.MAXIMIZE
edge, weight = gp.multidict({(s,e):w for s,e,w in edges})x = {}for i in range(vertices):for j in range(vertices):if (i, j) in weight.keys():x[i,j] = model.addVar(obj=weight[(i,j)], vtype=GRB.BINARY, name='x'+str(i)+str(j))for k in range(vertices):model.addConstr(gp.quicksum(x[i,k] for i in range(vertices) if (i,k) in x.keys()) + gp.quicksum(x[k,j] for j in range(vertices) if (k,j) in x.keys()) <= 1)
model.update()model.optimize()
values = []for i in range(vertices):for j in range(vertices):if (i,j) in x.keys():if x[i,j].x > 0:values.append((i,j,weight[(i,j)]))
# TODO: Find the maximal matchingreturn values
This is a simple model of maximum weighted matching, so every vertex should be at most covered by one weighted edge.
In my tests it doesn't find the maximum weight.
So the model should be: max sum(W[i,j]*X[i,j]) where W is the weight from edge i to edge j, and X is a binary decision variable that's 1 if edge [i,j] is chosen, and 0 else.
The constraint should be that for all vertices k: sum(X[i,k]+X[k,j] >= 1) where i and j is any given vertice.
I know my running time isn't very good, but I don't understand why my code doesn't find the maximum weighted graph.
Anyone that can give me a hint if it's my constraints or my objective?
1
-
Your code is not directly reproducible but so far I cannot see anything suspicious. Could you explain why you think that your code does not find a maximum weighted matching?
If you know an optimal solution that is not found with your model, you could check what happens if you fix your variables to this solution. If the resulting model is infeasible, something might be wrong with your model formulation, and the article How do I determine why my model is infeasible? – Gurobi Help Center could help.
1 -
I found the fault, the code didn't account for parallel edges, so if there was parallel edges, the dictionary x only took the last value that it read. Otherwise I think the code is okay
0
Please sign in to leave a comment.
Comments
2 comments