GitHub

Primal and dual warm-starts

This tutorial was generated using Literate.jl. Download the source as a .jl file.

This tutorial demonstrates how to write a helper function that sets primal and dual warm-starts from the current optimal solution of a conic model, which can improve solver performance when repeatedly solving related problems.

Learning intentions:

  • Cache all solution values before modifying the model, because JuMP forbids interleaving solution queries with model modifications
  • Set primal and dual warm-starts using set_start_value and set_dual_start_value to reduce iterations on repeated solves
  • Handle solvers that do not support warm-starts gracefully using a try-catch around each constraint type

Required packages

This tutorial uses the following packages:

using JuMP
import SCS

A basic function

The main component of this tutorial is the following function. The most important observation is that we cache all of the solution values first, and then we modify the model second. (Alternating between querying a value and modifying the model is not allowed in JuMP.)

function set_optimal_start_values(model::Model)
    # Store a mapping of the variable primal solution
    variable_primal = Dict(x => value(x) for x in all_variables(model))
    # In the following, we loop through every constraint and store a mapping
    # from the constraint index to a tuple containing the primal and dual
    # solutions.
    constraint_solution = Dict()
    for (F, S) in list_of_constraint_types(model)
        # We add a try-catch here because some constraint types might not
        # support getting the primal or dual solution.
        try
            for ci in all_constraints(model, F, S)
                constraint_solution[ci] = (value(ci), dual(ci))
            end
        catch
            @info("Something went wrong getting $F-in-$S. Skipping")
        end
    end
    # Now we can loop through our cached solutions and set the starting values.
    for (x, primal_start) in variable_primal
        set_start_value(x, primal_start)
    end
    for (ci, (primal_start, dual_start)) in constraint_solution
        set_start_value(ci, primal_start)
        set_dual_start_value(ci, dual_start)
    end
    return
end
set_optimal_start_values (generic function with 1 method)

Testing the function

To test our function, we use the following linear program:

model = Model(SCS.Optimizer)
@variable(model, x[1:3] >= 0)
@constraint(model, sum(x) <= 1)
@objective(model, Max, sum(i * x[i] for i in 1:3))
optimize!(model)
assert_is_solved_and_feasible(model)
------------------------------------------------------------------
	       SCS v3.2.11 - Splitting Conic Solver
	(c) Brendan O'Donoghue, Stanford University, 2012
------------------------------------------------------------------
problem:  variables n: 3, constraints m: 4
cones: 	  l: linear vars: 4
settings: eps_abs: 1.0e-04, eps_rel: 1.0e-04, eps_infeas: 1.0e-07
	  alpha: 1.50, scale: 1.00e-01, adaptive_scale: 1
	  max_iters: 100000, normalize: 1, rho_x: 1.00e-06
	  acceleration_lookback: 10, acceleration_interval: 10
	  compiled with openmp parallelization enabled
lin-sys:  sparse-direct-amd-qdldl
	  nnz(A): 6, nnz(P): 0
------------------------------------------------------------------
 iter | pri res | dua res |   gap   |   obj   |  scale  | time (s)
------------------------------------------------------------------
     0| 4.42e+01  1.00e+00  1.28e+02 -6.64e+01  1.00e-01  1.18e-04
    75| 5.30e-07  2.63e-06  3.15e-07 -3.00e+00  1.00e-01  1.68e-04
------------------------------------------------------------------
status:  solved
timings: total: 1.69e-04s = setup: 4.61e-05s + solve: 1.23e-04s
	 lin-sys: 1.56e-05s, cones: 7.05e-06s, accel: 3.62e-06s
------------------------------------------------------------------
objective = -2.999998
------------------------------------------------------------------

By looking at the log, we can see that SCS took 75 iterations to find the optimal solution. Now we set the optimal solution as our starting point:

set_optimal_start_values(model)

and we re-optimize:

optimize!(model)
------------------------------------------------------------------
	       SCS v3.2.11 - Splitting Conic Solver
	(c) Brendan O'Donoghue, Stanford University, 2012
------------------------------------------------------------------
problem:  variables n: 3, constraints m: 4
cones: 	  l: linear vars: 4
settings: eps_abs: 1.0e-04, eps_rel: 1.0e-04, eps_infeas: 1.0e-07
	  alpha: 1.50, scale: 1.00e-01, adaptive_scale: 1
	  max_iters: 100000, normalize: 1, rho_x: 1.00e-06
	  acceleration_lookback: 10, acceleration_interval: 10
	  compiled with openmp parallelization enabled
lin-sys:  sparse-direct-amd-qdldl
	  nnz(A): 6, nnz(P): 0
------------------------------------------------------------------
 iter | pri res | dua res |   gap   |   obj   |  scale  | time (s)
------------------------------------------------------------------
     0| 1.90e-05  1.56e-06  9.14e-05 -3.00e+00  1.00e-01  1.16e-04
------------------------------------------------------------------
status:  solved
timings: total: 1.17e-04s = setup: 4.34e-05s + solve: 7.37e-05s
	 lin-sys: 1.35e-06s, cones: 1.73e-06s, accel: 3.00e-08s
------------------------------------------------------------------
objective = -3.000044
------------------------------------------------------------------

Now the optimization terminates after 0 iterations because our starting point is already optimal.

Caveats

Some solvers do not support setting some parts of the starting solution, for example, they may support only set_start_value for variables.

If you encounter an UnsupportedSupported attribute error for MOI.VariablePrimalStart, MOI.ConstraintPrimalStart, or MOI.ConstraintDualStart, comment out the corresponding part of the set_optimal_start_values function.