7.8 The linear/simplex warm-start tutorial¶
In this tutorial we demonstrate how to warm-start the simplex optimizer using the linear/simplex optimization part of API for MATLAB. See Sec. 7.7 (The linear/simplex interface tutorial) for a general introduction to specifying linear problems using this tool.
The simplex optimizers can be warm-started to speed up the solution process by providing a good initial point and thereby reducing the number of simplex iterations required to reach the optimal basic solution. The efficiency of warm-start depends on the quality and amount of information provided, typically this will be any of the following:
a primal feasible point,
status keys indicating if the variables are basic or on their bounds,
full primal-dual solution,
an optimal solution from a previous solve which remains primal or dual feasible after problem modification and can be used to warm-start a subsequent solve.
We demonstrate warm-starting on two examples
providing the initial information with the problem data,
reusing a solution from a previous solve after modifying the problem.
In both cases we work with the same sample problem as in Sec. 7.7 (The linear/simplex interface tutorial):
with variable bounds
7.8.1 Inputting warm-start information¶
If the initial warm-start information is available it can be entered together with the full specification of the problem in the constructor of moseklinmodel. Alternatively, the function moseklinmodel.setsolution can also be used for that purpose.
% We set up the linear model
% together with:
% - approximate primal solution
% - status keys
model = moseklinmodel(...
name = "lo1", ...
numvar = 6, ...
objsense = "maximize", ...
objective = [ 3 1 5 1 0 0 ]', ...
A = [ 3 1 2 0 0 0 ; ...
2 1 3 1 -1 0 ; ...
0 2 0 3 0 -1 ], ...
b = [ 30 15 25 ]', ...
blx = [ 0.0 0.0 0.0 0.0 0.0 -inf ]', ...
bux = [ inf 10.0 inf inf inf 0.0 ]', ...
varnames = ["x1" "x2" "x3" "x4" "y1" "y2"]',...
conname = ["c1" "c2" "c3"]', ...
solution_x = [0 0 15 8.3 0 0]', ...
solution_skx = ["LOW" "LOW" "BAS" "BAS" "BAS" "UPR"]', ...
solution_skc = ["FIX" "FIX", "FIX"]);
In this example we input a primal solution (approximate) and status keys as defined in stakey. Additional data that can be entered at this point is the dual solution: solution_y, solution_slx and solution_sux.
The simplex optimizer (primal, dual or free) is then invoked and solution retrieved as in Sec. 7.7 (The linear/simplex interface tutorial).
We can check solver statistics to validate that the initial solution was taken into account and whether it reduced the number of simplex iterations:
% Solver statistics
fprintf("Optimizer time %.3f\n", model.info.MSK_DINF_OPTIMIZER_TIME);
fprintf("#iterations %ld\n", model.info.MSK_LIINF_SIMPLEX_ITER);
7.8.2 Warm-starting after modification¶
In this scenario we solve a sequence of linear problems obtained by modifying the data in a single moseklinmodel object. In this case the solution from a previous solve remains in the object and will be used to initialize a subsequent solve without any extra action form the user.
Suppose first we solve some initial problem:
% We set up and initially solve a sample linear model
model = moseklinmodel(...
numvar = 6, ...
objsense = "maximize", ...
objective = [ 3 1 5 1 0 0 ]', ...
A = [ 3 1 2 0 0 0 ; ...
2 1 3 1 -1 0 ; ...
0 2 0 3 0 -1 ], ...
b = [ 30 15 25 ]', ...
blx = [ 0.0 0.0 0.0 0.0 0.0 -inf ]', ...
bux = [ inf 10.0 inf inf inf 0.0 ]');
model.solve(param = [ "MSK_IPAR_OPTIMIZER", "MSK_OPTIMIZER_FREE_SIMPLEX" ], quiet = true);
Later, we may want to change an upper bound (make it more strict) using moseklinmodel.setb. This operation preserves dual feasibility of the previous solution stored in the model, so it makes sense to solve the new problem with the dual simplex. The previous solution will be fed as an initial warm start to the solver automatically:
% Introduce a stricter upper bound for the 3-rd constraint
model.setb([30, 15, 22]');
% Solve, using dual simplex
model.solve(param = [ "MSK_IPAR_OPTIMIZER", "MSK_OPTIMIZER_DUAL_SIMPLEX" ]);
Similarly, we may now want to change the objective vector using moseklinmodel.setc. This operation preserves primal feasibility of the previous solution stored in the model, so it makes sense to solve the new problem with the primal simplex. The previous solution will be fed as an initial warm start to the solver automatically:
% Change an objective coefficient
model.setc([3 2 0 2]');
% Solve, using primal simplex
model.solve(param = [ "MSK_IPAR_OPTIMIZER", "MSK_OPTIMIZER_PRIMAL_SIMPLEX" ]);
The solution from a previous solve is propagated to the next solve of the same moseklinmodel, unless the user inputs any new element of the initial solution using moseklinmodel.setsolution, at which point that solution is used to warm-start the immediately following solve. This pattern continues.
