1 ```# Non-bipartite: https://theory.stanford.edu/~jvondrak/CS369P/lec5.pdf ``` 2 3 ```mutable struct PerfectBipartiteMatchingLPSolver <: PerfectBipartiteMatchingSolver ``` 4 ``` solver ``` 5 6 ``` # Optimisation model (reused by solve_linear). ``` 7 ``` model # ::Model ``` 8 ``` x # ::Matrix{Variable} ``` 9 10 ``` function PerfectBipartiteMatchingLPSolver(solver) ``` 11 0 ``` return new(solver, nothing, nothing) ``` 12 ``` end ``` 13 ```end ``` 14 15 ```function build!(solver::PerfectBipartiteMatchingLPSolver, n_arms::Int) ``` 16 ``` # Build the optimisation model behind solve_linear. ``` 17 0 ``` solver.model = Model(solver.solver) ``` 18 0 ``` indices = collect((i, j) for i in 1:n_arms, j in 1:n_arms) ``` 19 0 ``` solver.x = @variable(solver.model, [indices], binary=true) ``` 20 21 0 ``` for i in 1:n_arms # Left nodes. ``` 22 0 ``` @constraint(solver.model, sum(solver.x[(i, j)] for j in 1:n_arms) <= 1) ``` 23 ``` end ``` 24 0 ``` for j in 1:n_arms # Right nodes. ``` 25 0 ``` @constraint(solver.model, sum(solver.x[(i, j)] for i in 1:n_arms) <= 1) ``` 26 ``` end ``` 27 ```end ``` 28 29 0 ```has_lp_formulation(::PerfectBipartiteMatchingLPSolver) = true ``` 30 31 ```function get_lp_formulation(solver::PerfectBipartiteMatchingLPSolver, rewards::Dict{Tuple{Int, Int}, Float64}) ``` 32 0 ``` return solver.model, ``` 33 ``` sum(rewards[(i, j)] * solver.x[(i, j)] for (i, j) in keys(rewards)), ``` 34 ``` Dict{Tuple{Int, Int}, JuMP.VariableRef}((i, j) => solver.x[(i, j)] for (i, j) in keys(rewards)) ``` 35 ```end ``` 36 37 ```function solve_linear(solver::PerfectBipartiteMatchingLPSolver, rewards::Dict{Tuple{Int, Int}, Float64}) ``` 38 0 ``` m, obj, vars = get_lp_formulation(solver, rewards) ``` 39 0 ``` @objective(m, Max, obj) ``` 40 41 0 ``` set_silent(m) ``` 42 0 ``` optimize!(m) ``` 43 44 0 ``` if termination_status(m) != MOI.OPTIMAL ``` 45 0 ``` return Tuple{Int, Int}[] ``` 46 ``` end ``` 47 0 ``` return Tuple{Int, Int}[(i, j) for (i, j) in keys(rewards) if value(vars[(i, j)]) > 0.5] ``` 48 ```end ```

Read our documentation on viewing source code .