The hardware and bandwidth for this mirror is donated by dogado GmbH, the Webhosting and Full Service-Cloud Provider. Check out our Wordpress Tutorial.
If you wish to report a bug, or if you are interested in having us mirror your free-software or open-source project, please feel free to contact us at mirror[@]dogado.de.
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.
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) |
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 1Now 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: TRUEA 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)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.66667When 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.666667Use 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: FALSEThe 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] 0After 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: TRUEFor 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.00000For 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.66667Run presolve independently of solving:
solver <- hi_new_solver(model)
hi_solver_presolve(solver)
#> LP has 3 rows; 3 cols; 9 nonzeros
#>
#> Presolving model
#>
#> 3 rows, 3 cols, 9 nonzeros 0s
#>
#> 3 rows, 3 cols, 9 nonzeros 0s
#>
#> Presolve reductions: rows 3(-0); columns 3(-0); nonzeros 9(-0) - Not reduced
#>
#> Presolve status: Not reduced
#> [1] 0These binaries (installable software) and packages are in development.
They may not be fully stable and should be used with caution. We make no claims about them.
Health stats visible at Monitor.