# Graph Theory problem

I just got sent a problem that I haven't found any model for thus I do not know how to proceed in solving it, if anybody can show me a similar problem so I can use it as a starting point or if they are willing to show how to solve the following problem that I have, it is greatly appreciated!!

Problem: Determine the maximum value coupling for the simple bipartite graph that has the values ​​of the arcs passed in the table below

• "linear assignment problem" May 31, 2022 at 19:42
• The following link includes some insight and codes in different languages to solve the problem. geeksforgeeks.org/maximum-bipartite-matching May 31, 2022 at 19:52
• See also the Wikipedia pages for the assignment problem and the Hungarian method.
– prubin
May 31, 2022 at 20:09
• Oh this is insane, thanks I was so lost since all I learnt was the Bellman and Ford algorithms, I have no idea what Hungarian method was, I just assumed it was a nameless problem part of the Graph Theory chapter we got in our Operation Research course going on May 31, 2022 at 20:15

The problem formulation is as follows:

Here is the Pyomo code

model = AbstractModel()
model.i = RangeSet(Ni)
model.j = RangeSet(Nj)

model.flow = Var(model.i,model.j,bounds=(0,1),initialize=0, within=Reals)

def rule_C1(model,i):
return sum(model.flow[i,j] for j in model.j)<=1
model.C1   = Constraint(model.i,rule=rule_C1)

def rule_C2(model,j):
return sum(model.flow[i,j] for i in model.i)<=1
model.C2   = Constraint(model.j,rule=rule_C2)

def rule_OF(model):
return sum(model.flow[r,c]*dic[r,c] for r in model.i for c in model.j)
model.obj1 = Objective(rule=rule_OF, sense=maximize)