///|
priv struct Choice {
first : Int32
second : Int32
gain : Int64
}
///|
priv struct Work {
mut candidates : Int32
mut swap_trials : Int32
mut moves : Int32
mut swaps : Int32
}
///|
fn select_move(
g : @model.Hypergraph,
state : State,
capacities : Array[Int64],
locked : Array[Bool],
delta : Array[Int32],
budget : RefinementBudget,
work : Work,
) -> Choice? {
let mut best : Choice? = None
for v in 0..= budget.max_candidates {
break
}
work.candidates += 1
if locked[v] {
continue
}
let from = state.assignment[v]
let to = 1 - from
if state.sizes[from] <= 1 ||
g.vertex_weight(v) > capacities[to] - state.loads[to] {
continue
}
let gain = state.gain(g, v)
let better = match best {
None => true
Some(previous) => gain > previous.gain
}
if better {
best = Some({ first: v, second: -1, gain, })
}
}
if budget.max_moves - work.moves < 2 {
return best
}
for a in 0..= budget.max_swap_trials {
break
}
for b in (a + 1)..= budget.max_swap_trials {
break
}
work.swap_trials += 1
if locked[a] || locked[b] || state.assignment[a] == state.assignment[b] {
continue
}
let from = state.assignment[a]
let to = 1 - from
let wa = g.vertex_weight(a)
let wb = g.vertex_weight(b)
if wb > capacities[from] - (state.loads[from] - wa) ||
wa > capacities[to] - (state.loads[to] - wb) {
continue
}
let gain = state.swap_gain(g, a, b, delta)
let better = match best {
None => true
Some(previous) => gain > previous.gain
}
if better {
best = Some({ first: a, second: b, gain, })
}
}
}
best
}
///|
/// Improve a feasible bipartition using pin-count FM gains and feasible swaps.
/// Every pass locks moved vertices, retains its best prefix and reverts the suffix.
pub fn refine(
g : @model.Hypergraph,
assignment : Array[Int32],
capacities : Array[Int64],
budget~ : RefinementBudget = RefinementBudget::default(),
) -> Result[RefineResult, @initial.SolveError] {
if budget.max_passes < 0 ||
budget.max_passes > 100 ||
budget.max_moves < 0 ||
budget.max_moves > 1000000 ||
budget.max_swap_trials < 0 ||
budget.max_swap_trials > 1000000 ||
budget.max_candidates < 0 ||
budget.max_candidates > 10000000 {
return Err({ kind: "options", message: "invalid refinement work budget", })
}
let initial = match @metrics.verify(g, assignment, capacities) {
Ok(m) => m
Err(error) => return Err({ kind: "validation", message: error.message, })
}
let state = State::new(g, assignment, initial)
let work : Work = { candidates: 0, swap_trials: 0, moves: 0, swaps: 0, }
let delta = Array::make(g.edge_count(), 0)
let mut passes = 0
let mut rolled_back = 0
let mut measured = initial
while passes < budget.max_passes {
if work.moves >= budget.max_moves ||
work.candidates >= budget.max_candidates {
break
}
passes += 1
let locked = Array::make(g.vertex_count(), false)
let history : Array[(Int32, Int32)] = []
let pass_start = state.cut
let mut best_cut = state.cut
let mut best_prefix = 0
while work.moves < budget.max_moves &&
work.candidates < budget.max_candidates {
let choice = match
select_move(g, state, capacities, locked, delta, budget, work) {
Some(choice) => choice
None => break
}
state.apply(g, choice.first)
locked[choice.first] = true
work.moves += 1
if choice.second >= 0 {
state.apply(g, choice.second)
locked[choice.second] = true
work.moves += 1
work.swaps += 1
}
history.push((choice.first, choice.second))
if state.cut < best_cut {
best_cut = state.cut
best_prefix = history.length()
}
}
let mut suffix = history.length()
while suffix > best_prefix {
suffix -= 1
let (first, second) = history[suffix]
if second >= 0 {
state.apply(g, second)
rolled_back += 1
}
state.apply(g, first)
rolled_back += 1
}
measured = match @metrics.verify(g, state.assignment, capacities) {
Ok(m) => m
Err(error) => return Err({ kind: "internal", message: error.message, })
}
if measured.cut_net != state.cut ||
measured.cut_net != best_cut ||
measured.cut_net > pass_start {
return Err({
kind: "internal",
message: "FM counts disagree with independent validation",
})
}
if best_cut == pass_start {
break
}
}
let limited = budget.max_passes > 0 &&
(
work.moves >= budget.max_moves ||
work.candidates >= budget.max_candidates ||
(budget.max_swap_trials > 0 && work.swap_trials >= budget.max_swap_trials) ||
passes == budget.max_passes
)
Ok({
assignment: state.assignment,
metrics: measured,
initial_cut: initial.cut_net,
moves: work.moves,
swaps: work.swaps,
passes,
rolled_back,
budget_limited: limited,
})
}