I’ve just finished one version of the algorithm, which can bring the correct convergent result.
Actually is my very first realistic asynchronous program. Many thanks to @sgaure (e.g. post #8).
Well, I do find it tricky to implement a decent & concise & problem-itself-based termination criterion! Therefore I adopt a pragmatic one temporarily.
function subproblemˈs_duty(j, snap, inbox) # the hasty version
mj = inn[j]
reset_mj_obj!(mj, snap.β, snap.μ, snap.ν)
JuMP.optimize!(mj); JuMP.assert_is_solved_and_feasible(mj; allow_local = false)
Δ = snap.θ[j] - JuMP.objective_value(mj)
if (is_cut_off = Δ > COT)
con = build_con(j, mj) # on the currently solved status of `mj`
@lock model_lock JuMP.add_constraint(model, con) # add it in haste
end
lens = function(new_snap) # this is dumb here but make provision for the fussy version
j, is_cut_off
end
@lock inbox_lock push!(inbox, lens)
end
function masterˈs_algorithm(Δt)
function shot!()
JuMP.optimize!(model); JuMP.assert_is_solved_and_feasible(model; allow_local = false, dual = true)
println("▶ modelˈs ObjBound = $(JuMP.objective_bound(model))")
local snap = (t = timestamp += 1, θ = ı.(θ), β = ı.(β), μ = ı.(μ), ν = ı(ν))
end
function masterˈs_loop()
while true
if isempty(inbox)
yield()
continue
end
js2reply, is_global_cut_off = Set{Int}(), false
while !isempty(inbox)
lens = @lock inbox_lock pop!(inbox)
local j, is_cut_off = lens(snap)
println("t = $(snap.t), j = $j, is_cut_off = $is_cut_off")
push!(js2reply, j)
is_global_cut_off |= is_cut_off
end
if is_global_cut_off
@lock model_lock snap = shot!()
t0 = time()
elseif time() - t0 > Δt
println("▶▶▶ Long time no improvements, quit!")
return
end
for j = js2reply Threads.@spawn subproblemˈs_duty(j, snap, inbox) end
end
end
t0 = time()
timestamp, inbox = -1, Function[]
snap = shot!()
masterˈs_task = Threads.@spawn masterˈs_loop()
for j = 1:J Threads.@spawn subproblemˈs_duty(j, snap, inbox) end
wait(masterˈs_task)
end
masterˈs_algorithm(5)
This follows a hasty fashion—adding cut to model upon it is proved to be capable of cutting off the very trial point who generates cut. This follows the convention about how we would add cuts in a serial program.
Since we are currently writing asynchronous programs. It is natural to have an updated trial point in master’s loop, motivating a fussy fashion—adding cut to model upon it is proved to be capable of cutting off the updated trial point, instead of the potentially older one who generates cut.
To this end, we need to prepare a judging function can_cut_off inside subproblemˈs_duty:
function subproblemˈs_duty(j, snap, inbox) # the fussy version
mj = inn[j]
reset_mj_obj!(mj, snap.β, snap.μ, snap.ν)
JuMP.optimize!(mj); JuMP.assert_is_solved_and_feasible(mj; allow_local = false)
con = build_con(j, mj) # on the currently solved status of `mj`
can_cut_off = function(new_snap) # the body has some details that you can skip
Θ, Β, Μ, Ν = new_snap.θ, new_snap.β, new_snap.μ, new_snap.ν
pair = haskey(mj, :bLent)
pBus, q = ı.(mj[:pBus]), ı.(mj[:q])
term_beta = pair ? sum((pBus[t,1] + pBus[t,2])Β[t] for t=1:T) : Β ⋅ pBus
term_mu = pair ? sum((q[t,1] + q[t,2])Μ[t] for t=1:T) : Μ ⋅ q
term_nu = sum(q)Ν
cut_term = +(ı(mj[:prim_obj]), term_beta, term_mu, term_nu)
local is_cut_off = Θ[j] > cut_term + COT # return a Bool
end
lens = function(new_snap) # this is dumb here but make provision for other versions
j, can_cut_off(new_snap), con
end
@lock inbox_lock push!(inbox, lens)
end
The related part in masterˈs_loop is revised accordingly as
local j, is_cut_off, con = lens(snap)
is_cut_off && @lock model_lock JuMP.add_constraint(model, con)