In practice it frequently occurs that when an optimization problem has been solved, then the same problem slightly modified should be reoptimized. Moreover, if it is just a small the modification, it can be expected that the optimal solution to the original problem is a good approximation to the modified problem. Therefore, it should be efficient to start the optimization of the modified problem from the previous optimal solution.

Currently, the interior-point optimizer in MOSEK cannot take advantage of a previous optimal solution, however, the simplex optimizer can exploit any basic solution.

We work with the simple linear problem:

$\begin{split}\begin{array}{rl} \mbox{minimize} & x_{1} + 2 x_{2} \\ \mbox{subject to} & 4 \leq x_{1} + x_{3} \leq 6, \\ & 1 \leq x_{1} + x_{2}, \\ & 0 \leq x_{1},x_{2},x_{3}. \end{array}\end{split}$

9.1.1 Initial hot-start¶

A quick inspection of the problem indicates that $$(x_{1},x_{3}) =(1,3)$$ is an optimal solution. Hence, it seems to be a good idea to let the initial basis consist of $$x_{1}$$ and $$x_{3}$$ and all the other variables be at their lower bounds. This idea is used in the example code:

Listing 9.1 Passing the full basic solution. Click here to download.
% Specify an initial basic solution.
bas.skc      = ['LL';'LL'];
bas.skx      = ['BS';'LL';'BS'];
bas.xc       = [4 1]';
bas.xx       = [1 3 0]';

prob.sol.bas = bas;

% Specify the problem data.
prob.c       = [ 1 2 0]';
subi         = [1 2 2 1];
subj         = [1 1 2 3];
valij        = [1.0 1.0 1.0 1.0];
prob.a       = sparse(subi,subj,valij);
prob.blc     = [4.0 1.0]';
prob.buc     = [6.0 inf]';
prob.blx     = sparse(3,1);
prob.bux     = [];

% Use the primal simplex optimizer.
param.MSK_IPAR_OPTIMIZER = 'MSK_OPTIMIZER_PRIMAL_SIMPLEX';
[r,res] = mosekopt('minimize',prob,param)


• In the example the dual solution is not defined. This is acceptable because the primal simplex optimizer is used for the reoptimization and it does not exploit a dual solution. Otherwise it will be important that a good dual solution is specified.

• The status keys bas.skc and bas.skx must contain only the entries BS, EQ, LL, UL, SB. Moreover, e.g. EQ must be specified only for a fixed constraint or variable. LL and UL can be used only for a variable that has a finite lower or upper bound respectively. For an explanation of status keys see stakey.

• The number of constraints and variables defined to be basic must correspond exactly to the number of constraints.

Next, assume we modify the problem by adding a new variable:

$\begin{split}\begin{array}{rl} \mbox{minimize} & x_{1} + 2 x_{2} - x_{4} \\ \mbox{subject to} & 4 \leq x_{1} + x_{3} + x_{4} \leq 6, \\ & 1 \leq x_{1} + x_{2}, \\ & 0 \leq x_{1},x_{2},x_{3},x_{4}. \end{array}\end{split}$

In continuation of the previous example this problem can be solved as follows, using the full previous basic solution in hot-start:

Listing 9.2 Hot-start when adding a new variable. Click here to download.
prob.c       = [prob.c;-1.0];
prob.a       = [prob.a,sparse([1.0 0.0]')];
prob.blx     = sparse(4,1);

% Reuse the old optimal basic solution.
bas          = res.sol.bas;

% Add to the status key.
bas.skx      = [res.sol.bas.skx;'LL'];

% The new variable is at it lower bound.
bas.xx       = [res.sol.bas.xx;0.0];
bas.slx      = [res.sol.bas.slx;0.0];
bas.sux      = [res.sol.bas.sux;0.0];

prob.sol.bas = bas;

[rcode,res]  = mosekopt('minimize',prob,param);

% The new primal optimal solution
res.sol.bas.xx'


9.1.3 Fixing a variable¶

In e.g. branch-and-bound methods for integer programming problems it is necessary to reoptimize the problem after a variable has been fixed to a value. This can easily be achieved as follows:

Listing 9.3 Hot-start with a fixed variable. Click here to download.
prob.blx(4)  = 1;
prob.bux     = [inf inf inf 1]';

% Reuse the basis.
prob.sol.bas = res.sol.bas;

[rcode,res]  = mosekopt('minimize',prob,param);

% Display the optimal solution.
res.sol.bas.xx'


Now assume that the constraint

$x_{1} + x_{2} \geq 2$

should be added to the problem and the problem should be reoptimized. The following example demonstrates how to do this.

Listing 9.4 Hot-start when adding a new constraint. Click here to download.
% Modify the problem.
prob.a       = [prob.a;sparse([1.0 1.0 0.0 0.0])];
prob.blc     = [prob.blc;2.0];
prob.buc     = [prob.buc;inf];

% Obtain the previous optimal basis.
bas          = res.sol.bas;

% Set the solution to the modified problem.
bas.skc      = [bas.skc;'BS'];
bas.xc       = [bas.xc;bas.xx(1)+bas.xx(2)];
bas.y        = [bas.y;0.0];
bas.slc      = [bas.slc;0.0];
bas.suc      = [bas.suc;0.0];

% Reuse the basis.
prob.sol.bas = bas;

% Reoptimize.
[rcode,res]  = mosekopt('minimize',prob,param);

res.sol.bas.xx'


Please note that the slack variable corresponding to the new constraint is declared basic. This implies that the new basis is nonsingular and can be reused.

9.1.5 Removing a constraint¶

We can remove a constraint in two ways:

• Set the bounds for the constraint to $$\pm \infty$$ as appropriate.

• Remove the corresponding row from prob.a and other parts of the data and update the basis.

In the following example we use the latter approach to again remove the constraint $$x_{1} + x_{2} \geq 2$$.

Listing 9.5 Hot-start when removing a constraint. Click here to download.
% Modify the problem.
prob.a       = prob.a(1:end-1,:);
prob.blc     = prob.blc(1:end-1);
prob.buc     = prob.buc(1:end-1);

% Obtain the previous optimal basis.
bas          = res.sol.bas;

% Set the solution to the modified problem.
bas.skc      = bas.skc(1:end-1,:);
bas.xc       = bas.xc(1:end-1);
bas.y        = bas.y(1:end-1);
bas.slc      = bas.slc(1:end-1);
bas.suc      = bas.suc(1:end-1);

% Reuse the basis.
prob.sol.bas = bas;

% Reoptimize.
[rcode,res]  = mosekopt('minimize',prob,param);

res.sol.bas.xx'


9.1.6 Removing a variable¶

Similarly we can remove a variable in two ways:

• Fix the variable to zero.

• Remove the corresponding column from prob.a and other parts of the data and update the basis.

The following example uses the latter approach to remove $$x_4$$.

Listing 9.6 Hot-start when removing a constraint. Click here to download.
% Modify the problem.
prob.c       = prob.c(1:end-1);
prob.a       = prob.a(:,1:end-1);
prob.blx     = prob.blx(1:end-1);
prob.bux     = prob.bux(1:end-1);

% Obtain the previous optimal basis.
bas          = res.sol.bas;

% Set the solution to the modified problem.
bas.xx       = bas.xx(1:end-1);
bas.skx      = bas.skx(1:end-1,:);
bas.slx      = bas.slx(1:end-1);
bas.sux      = bas.sux(1:end-1);

% Reuse the basis.
prob.sol.bas = bas;

% Reoptimize.
[rcode,res]  = mosekopt('minimize',prob,param);

res.sol.bas.xx'