1
$\begingroup$

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

.

$\endgroup$
4
  • 1
    $\begingroup$ "linear assignment problem" $\endgroup$
    – RobPratt
    May 31, 2022 at 19:42
  • 1
    $\begingroup$ The following link includes some insight and codes in different languages to solve the problem. geeksforgeeks.org/maximum-bipartite-matching $\endgroup$ May 31, 2022 at 19:52
  • $\begingroup$ See also the Wikipedia pages for the assignment problem and the Hungarian method. $\endgroup$
    – prubin
    May 31, 2022 at 20:09
  • $\begingroup$ 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 $\endgroup$ May 31, 2022 at 20:15

1 Answer 1

3
$\begingroup$

The problem formulation is as follows:

enter image description here 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)

enter image description here

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.