9.1 Advanced hot-start

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)

Comments:

  • 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.

9.1.2 Adding a new variable

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'

9.1.4 Adding a new constraint

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'