|
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
|
dourouc05