Model not finding maximum

回答済み

Snorre Åldstedt

2023年03月14日 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

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2026年11月13日 01:47

  This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  Marika Karbstein

  • Gurobi Staff

  2023年03月14日 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

  2023年03月15日 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

投稿コメントは受け付けていません。