Warm-Starting and Sensitivity Analysis

When solving a sequence of related optimization problems, warm-starting from a previous solution can dramatically reduce solve time. The highs package supports warm-starting via both basis and solution information.

Basis Warm-Start

The simplex method maintains a basis — a partition of variables into basic and non-basic sets. Saving and restoring the basis lets the solver skip the initial phase of finding a feasible basis.

Basis status values:

Code	Status	Meaning
0	Lower	Variable at its lower bound
1	Basic	Variable is basic
2	Upper	Variable at its upper bound
3	Zero	Free variable at zero
4	Nonbasic	Non-basic (no bound info)

Example: Basis Round-Trip

library(highs)

model <- highs_model(
  L = c(2, 4, 3),
  lower = 0,
  A = matrix(c(3, 4, 2, 2, 1, 2, 1, 3, 2), nrow = 3, byrow = TRUE),
  rhs = c(60, 40, 80),
  maximum = TRUE
)
solver <- hi_new_solver(model)

# Solve the original problem
hi_solver_run(solver)
#> [1] 0
info1 <- hi_solver_info(solver)
cat("First solve:", info1$simplex_iteration_count, "iterations\n")
#> First solve: 2 iterations

# Save the basis
basis <- hi_solver_get_basis(solver)
cat("Basis valid:", basis$valid, "\n")
#> Basis valid: TRUE
cat("Column statuses:", basis$col_status, "\n")
#> Column statuses: 0 1 1
cat("Row statuses:", basis$row_status, "\n")
#> Row statuses: 2 2 1

Now clear the solver state, restore the basis, and re-solve. The solver should converge in zero iterations:

hi_solver_clear_solver(solver)
#> [1] 0
hi_solver_set_basis(solver, basis$col_status, basis$row_status)
#> [1] 0
hi_solver_run(solver)
#> [1] 0
info2 <- hi_solver_info(solver)
cat("Warm-start solve:", info2$simplex_iteration_count, "iterations\n")
#> Warm-start solve: 0 iterations
cat("Same objective:", info1$objective_function_value == info2$objective_function_value, "\n")
#> Same objective: TRUE

Iterative Solving with Perturbations

A common use case: solve a problem, modify it slightly, and re-solve with the previous basis as a warm-start.

solver <- hi_new_solver(model)
hi_solver_run(solver)
#> [1] 0
obj_original <- hi_solver_info(solver)$objective_function_value
cat("Original objective:", obj_original, "\n")
#> Original objective: 76.66667

# Save basis before modification
basis <- hi_solver_get_basis(solver)

# Tighten a constraint: rhs from 60 to 50
hi_solver_change_constraint_bounds(solver, idx = 0L, lhs = -Inf, rhs = 50)
#> [1] 0

# Warm-start from the saved basis
hi_solver_set_basis(solver, basis$col_status, basis$row_status)
#> [1] 0
hi_solver_run(solver)
#> [1] 0
info <- hi_solver_info(solver)
cat("After perturbation:", info$objective_function_value,
    "(", info$simplex_iteration_count, "iterations)\n")
#> After perturbation: 68.33333 ( 0 iterations)

Solution Warm-Start

For cases where you have a good primal/dual solution but not a basis (e.g., from a different solver), you can supply it as a starting point:

solver <- hi_new_solver(model)
hi_solver_run(solver)
#> [1] 0
sol <- hi_solver_get_solution(solver)

# Clear and warm-start from solution
hi_solver_clear_solver(solver)
#> [1] 0
hi_solver_set_solution(
  solver,
  col_value = sol$col_value,
  row_value = sol$row_value,
  col_dual  = sol$col_dual,
  row_dual  = sol$row_dual
)
#> [1] 0
hi_solver_run(solver)
#> [1] 0
hi_solver_info(solver)$objective_function_value
#> [1] 76.66667

Sparse Solution

When only a few variables have non-zero values, use the sparse interface:

solver <- hi_new_solver(model)

# Set only the non-zero entries (0-based column indices)
hi_solver_set_sparse_solution(solver, index = c(0L, 1L), value = c(5.0, 10.0))
#> [1] 0
hi_solver_run(solver)
#> [1] 0
hi_solver_get_solution(solver)$col_value
#> [1]  0.000000  6.666667 16.666667

Clearing the Basis

Use hi_solver_clear_basis() to invalidate the current basis. This is useful when you want to force presolve to run on the next solve (presolve is skipped when a valid basis is present):

solver <- hi_new_solver(model)
hi_solver_run(solver)
#> [1] 0
cat("Basis valid after solve:", hi_solver_get_basis(solver)$valid, "\n")
#> Basis valid after solve: TRUE

hi_solver_clear_basis(solver)
#> [1] 0
cat("Basis valid after clear:", hi_solver_get_basis(solver)$valid, "\n")
#> Basis valid after clear: FALSE

Using the Closure Interface

The highs_solver() wrapper exposes warm-start methods directly:

hw <- highs_solver(model)
hw$solve()
#> ERROR:   getOptionIndex: Option "pdlp_features_off" is unknown
#> [1] 0
basis <- hw$get_basis()
cat("Basis valid:", basis$valid, "\n")
#> Basis valid: TRUE

# Perturb and warm-start
hw$cbounds(1, -Inf, 50)
#> [1] 0
hw$set_basis(basis$col_status, basis$row_status)
#> [1] 0
hw$solve()
#> ERROR:   getOptionIndex: Option "pdlp_features_off" is unknown
#> [1] 0
hw$info()$simplex_iteration_count
#> [1] 0

Sensitivity Analysis (Ranging)

After solving an LP, ranging analysis shows how much each cost coefficient or bound can change before the basis changes:

solver <- hi_new_solver(model)
hi_solver_run(solver)
#> [1] 0
ranging <- hi_solver_get_ranging(solver)
cat("Ranging valid:", ranging$valid, "\n")
#> Ranging valid: TRUE

Cost Ranging

For each column, col_cost_up and col_cost_dn show how much the objective coefficient can increase or decrease:

cost_up <- ranging$col_cost_up
data.frame(
  variable = seq_along(cost_up$value),
  max_increase = cost_up$value,
  new_objective = cost_up$objective
)
#>   variable max_increase new_objective
#> 1        1     3.833333      76.66667
#> 2        2     6.000000      90.00000
#> 3        3     8.000000     160.00000
#> 4        4     0.000000       0.00000
#> 5        5     0.000000       0.00000
#> 6        6     0.000000       0.00000

Bound Ranging

For each row, row_bound_up and row_bound_dn show how much the constraint bound can change:

bound_up <- ranging$row_bound_up
data.frame(
  constraint = seq_along(bound_up$value),
  max_increase = bound_up$value,
  new_objective = bound_up$objective
)
#>   constraint max_increase new_objective
#> 1          1    100.00000     110.00000
#> 2          2     60.00000      90.00000
#> 3          3     53.33333      76.66667