Trouvons un couplage de taille maximum dans le graphe biparti suivant, à l'aide d'un PLNE :
import mip
m = mip.Model()
V = "abcdefgh"
E = [("d", "h"), ("d", "g"), ("d", "f"), ("d", "e"), ("c", "h"), ("c", "g"),
("c", "f"), ("b", "e"), ("a", "f"), ("a", "e")]
x = {e: m.add_var(name=f"x_{e[0]}{e[1]}") for e in E}
m.objective = mip.maximize(mip.xsum(x[e] for e in E))
for v in V:
Ev = [e for e in E if v in e] # liste des arêtes contenant v
m += mip.xsum(x[e] for e in Ev) <= 1
m.optimize(max_seconds=300)
<OptimizationStatus.OPTIMAL: 0>
m.objective_value
4.0
for e in E:
if x[e].x > 0:
print(f"{e[0]} -- {e[1]}")
d -- g c -- h b -- e a -- f
for c in m.constrs: # valeurs des variables duales
print(c)
print(c.pi)
constr(0): +1.0 x_af +1.0 x_ae <= 1.0 1.0 constr(1): +1.0 x_be <= 1.0 1.0 constr(2): +1.0 x_ch +1.0 x_cg +1.0 x_cf <= 1.0 1.0 constr(3): +1.0 x_dh +1.0 x_dg +1.0 x_df +1.0 x_de <= 1.0 1.0 constr(4): +1.0 x_de +1.0 x_be +1.0 x_ae <= 1.0 -0.0 constr(5): +1.0 x_df +1.0 x_cf +1.0 x_af <= 1.0 -0.0 constr(6): +1.0 x_dg +1.0 x_cg <= 1.0 -0.0 constr(7): +1.0 x_dh +1.0 x_ch <= 1.0 -0.0