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 .

Loading