Combinatorial optimisation and delta evaluation

Orderings as a design space

Not every decision variable is a real number. Scheduling, routing, and assignment problems search over orderings, and space_permutation(n) declares exactly that. It is a general-purpose permutation engine, not a specialist: on large instances of a structured problem such as the travelling salesman, a dedicated solver with problem-specific moves will beat it.

A worked example

A synthetic assignment problem: twenty items of different weights must be placed into twenty positions of increasing cost, paying the item’s weight times the position’s cost. The best ordering puts the heaviest items in the cheapest positions:

n <- 20L
set.seed(101)
w <- as.numeric(sample.int(100L, n))
pos_cost <- as.numeric(seq_len(n))
placement_cost <- function(perm) {
  sum(w[perm] * pos_cost)
}

The delta hook

Simulated annealing proposes thousands of swaps, and re-evaluating the whole objective after each one is wasteful when a swap only touches a sliver of the sum. The contract’s delta_fn hook makes that saving first-class. Its signature is delta_fn(perm, i, j), and it must return the change in the objective when the entries at positions i and j of perm are swapped. For the placement objective the change involves only the two moved items:

placement_delta <- function(perm, i, j) {
  (w[perm[i]] - w[perm[j]]) * (pos_cost[j] - pos_cost[i])
}

A wrong delta would corrupt the anneal silently, so optimix does not take the hook on trust. At startup the claimed delta of one random swap is verified against a full re-evaluation and a disagreement stops with an error. During the anneal the accumulated value is re-synchronised periodically with a fresh full evaluation, and the value reported in the result is always a fresh full evaluation at the best permutation found – never the accumulated shortcut.

Same trajectory, fewer evaluations

The two problems below are identical except for the hook, and they share a seed. To see not just how many true evaluations each run spends but where they land, placement_cost is wrapped in a small counter that logs every call it actually receives, without changing what it returns:

track_calls <- function(fn) {
  log_env <- new.env(parent = emptyenv())
  log_env$vals <- numeric(0)
  wrapped <- function(x) {
    v <- fn(x)
    log_env$vals[length(log_env$vals) + 1L] <- v
    v
  }
  list(fn = wrapped, log = log_env)
}

The engine draws its random numbers in the same order whether or not a delta_fn is present, and the delta here is exact, so both runs walk the same trajectory and return the same permutation:

tr_plain <- track_calls(placement_cost)
prob_plain <- optim_problem(
  fn = tr_plain$fn,
  space = space_permutation(n),
  max_evals = 4000,
  seed = 7
)
tr_delta <- track_calls(placement_cost)
prob_delta <- optim_problem(
  fn = tr_delta$fn,
  space = space_permutation(n),
  max_evals = 4000,
  seed = 7,
  delta_fn = placement_delta
)
plain <- optimix(prob_plain)
fast <- optimix(prob_delta)
identical(plain$par, fast$par)
#> [1] TRUE
c(plain = plain$value, fast = fast$value)
#> plain  fast 
#>  8458  8458

In this seeded run the anneal lands on the exact optimum, which for this objective can be computed directly:

exact_optimum <- sum(sort(w, decreasing = TRUE) * pos_cost)
exact_optimum
#> [1] 8458

Counting true evaluations

counts[["function"]] counts true objective evaluations only. Calls to the delta_fn never touch the objective, so they are tallied separately in the diagnostics field delta_evals rather than folded into the count:

c(plain = plain$counts[["function"]], fast = fast$counts[["function"]])
#> plain  fast 
#>  4001     5
c(plain = plain$diagnostics$delta_evals, fast = fast$diagnostics$delta_evals)
#> plain  fast 
#>     0  4000

A figure: the sparse footprint of true evaluations

The counts above say how many true evaluations each run spent; they do not show what those evaluations achieved along the way. The tracker attached above recorded every value placement_cost actually returned, in call order, for both runs – 4001 calls for the plain run and 5 for the delta-hook run. Plotting the running best (the cumulative minimum) against call order shows the shape of the search each spent its evaluations on:

trace_df <- rbind(
  data.frame(
    run = "plain (no delta_fn)", call_index = seq_along(tr_plain$log$vals),
    best_so_far = cummin(tr_plain$log$vals)
  ),
  data.frame(
    run = "delta_fn attached", call_index = seq_along(tr_delta$log$vals),
    best_so_far = cummin(tr_delta$log$vals)
  )
)
trace_df$run <- factor(
  trace_df$run, levels = c("plain (no delta_fn)", "delta_fn attached")
)
ggplot2::ggplot(
  trace_df, ggplot2::aes(x = call_index, y = best_so_far, colour = run)
) +
  ggplot2::geom_step() +
  ggplot2::geom_point(size = 1.6) +
  ggplot2::facet_wrap(~run, scales = "free_x") +
  ggplot2::scale_colour_viridis_d(name = "run", guide = "none") +
  ggplot2::labs(
    x = "true objective evaluations, in call order",
    y = "best placement cost found so far (synthetic units)",
    title = "The delta hook reaches the same floor from a handful of calls"
  ) +
  ggplot2::theme_minimal()

Best placement cost found so far, in call order, for the plain run against the delta_fn run. The plain run’s true evaluations trace a dense staircase over four thousand calls; the delta_fn run reaches the same floor from a handful of calls, because most of its moves are scored from the delta alone and never touch the objective. Each panel keeps its own x-axis, since the two runs spend true evaluations at entirely different rates.

The plain run pays one full evaluation per scored move. With the hook, the objective is touched only for the initial score, the startup contract check, the periodic re-syncs, and the final fresh evaluation of the returned value – a few true evaluations in place of four thousand, for the same answer. For objectives where a full evaluation is genuinely expensive (a delta over a large assignment or schedule), this is the difference between an anneal that explores and one that stalls.