Maximum weighted matching

[mburq]

Hi,

This is a formulation for maximum weighted matching, works for both bipartite and non-bipartite graphs. In the case of bipartite graphs, the solution of the LP is automatically integral (i.e. no need to enforce integrality constraints). In the case of non-bipartite graphs, it requires an MIP solver (e.g. GLPK) and may therefore be much slower to solve to optimality.

Disclaimer: This is the first time I do a pull request, so I hope I'm not missing an important step.

[codecov-io]

Codecov Report

Merging #23 into master will not change coverage. The diff coverage is 100%.

@@          Coverage Diff          @@
##           master    #23   +/-   ##
=====================================
  Coverage     100%   100%           
=====================================
  Files          13     14    +1     
  Lines         210    234   +24     
=====================================
+ Hits          210    234   +24

Impacted Files	Coverage Δ
src/matching/matching.jl	100% <ø> (ø)	:white_check_mark:
src/matching/maximum_weight_matching.jl	100% <100%> (ø)
src/interdiction/bilevel_adaptive_arc.jl	100% <ø> (ø)	:white_check_mark:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 63b870c...5687734. Read the comment docs.

[CarloLucibello]

"- If the graph is not bipartite, then the computation time may grow exponentially."

I do not see integer programming part in case of fractionary solution, why do you say that?

I see three options here:

• @assert is_bipartite(g)
• accept also bipartite graphs, but caution the user about the possible suboptimality of the solution, possibly returning also a fractional_solution=true flag
• add an Integer programming part in case of fractional solutions

[CarloLucibello]

also, coverage should be increased

[mburq]

Sorry I wasn't clear in my comments, the integer programming is taken care of by the solver (by using the Int keyword in @variable, line 45).
Good idea to use is_bipartite(g) so that it doesn't require a an Integer Programming solver if the graph is bipartite.

[CarloLucibello]

Sorry I wasn't clear in my comments, the integer programming is taken care of by the solver (by using the Int keyword in @variable, line 45). Good idea to use is_bipartite(g) so that it doesn't require a an Integer Programming solver if the graph is bipartite.

Ok, thanks for the clarification, my knowledge of JuMP is very limited. This looks good, i can be merged once the remaining comments are addressed

[CarloLucibello]

this case should be tested

if setdiff(edge_list, keys(w)) != [] # If some edges do not have a key in w.
      error("Some edge weights are missing, check that keys i => j in w satisfy i <= j")
end

with a

@test_throws ErrorException ....

[mburq]

Just a quick follow-up: can this PR be merged? Thanks @CarloLucibello for the help in the review process.