Model not finding maximum

Answered

Snorre Åldstedt

• March 14, 2023 10:52

import gurobipy as gp

from gurobipy import GRB

def maximum_weighted_matching(vertices, edges):

    """

    Compute the maximal matching of a given multigraph

    vertices - The number of vertices

    edges - A list of edges; every edge is a triple of two vertices (from 0 to vertices-1) and weight

    return - 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 matching

    return 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

• 

  Marika Karbstein

  Gurobi Staff

  • March 14, 2023 12:38

  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
• 

  Snorre Åldstedt

  • March 15, 2023 18:38

  

  

  

  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.