6.10 Problem Modification and Reoptimization¶
Often one might want to solve not just a single optimization problem, but a sequence of problems, each differing only slightly from the previous one. This section demonstrates how to modify and re-optimize an existing problem.
The example we study is a simple production planning model.
Problem modifications regarding variables, cones, objective function and constraints can be grouped in categories:
add/remove,
coefficient modifications,
bounds modifications.
Especially removing variables and constraints can be costly. Special care must be taken with respect to constraints and variable indexes that may be invalidated.
Depending on the type of modification, MOSEK may be able to optimize the modified problem more efficiently exploiting the information and internal state from the previous execution. After optimization, the solution is always stored internally, and is available before next optimization. The former optimal solution may be still feasible, but no longer optimal; or it may remain optimal if the modification of the objective function was small.
In general, MOSEK exploits dual information and availability of an optimal basis from the previous execution. The simplex optimizer is well suited for exploiting an existing primal or dual feasible solution. Restarting capabilities for interior-point methods are still not as reliable and effective as those for the simplex algorithm. More information can be found in Chapter 10 of the book [Chvatal83].
6.10.1 Example: Production Planning¶
A company manufactures three types of products. Suppose the stages of manufacturing can be split into three parts: Assembly, Polishing and Packing. In the table below we show the time required for each stage as well as the profit associated with each product.
Product no. |
Assembly (minutes) |
Polishing (minutes) |
Packing (minutes) |
Profit ($) |
|---|---|---|---|---|
0 |
2 |
3 |
2 |
1.50 |
1 |
4 |
2 |
3 |
2.50 |
2 |
3 |
3 |
2 |
3.00 |
With the current resources available, the company has \(100,000\) minutes of assembly time, \(50,000\) minutes of polishing time and \(60,000\) minutes of packing time available per year. We want to know how many items of each product the company should produce each year in order to maximize profit?
Denoting the number of items of each type by \(x_0,x_1\) and \(x_2\), this problem can be formulated as a linear optimization problem:
and
Code in Listing 6.16 loads and solves this problem.
# Specify the c vector.
prob <- list(sense="max")
prob$c <- c(1.5, 2.5, 3.0)
# Specify a in sparse format.
subi <- c(1, 1, 1, 2, 2, 2, 3, 3, 3)
subj <- c(1, 2, 3, 1, 2, 3, 1, 2, 3)
valij <- c(2, 4, 3, 3, 2, 3, 2, 3, 2)
prob$A <- sparseMatrix(subi,subj,x=valij);
# Specify bounds of the constraints.
prob$bc<- rbind(blc=rep(-Inf, 3),
buc=c(100000, 50000, 60000))
# Specify bounds of the variables.
prob$bx<- rbind(blx=rep(0,3),
bux=rep(Inf,3))
# Perform the optimization.
prob$iparam <- list(OPTIMIZER="OPTIMIZER_DUAL_SIMPLEX")
r <- mosek(prob)
# Show the optimal x solution.
print(r$sol$bas$xx)
6.10.2 Changing the Linear Constraint Matrix¶
Suppose we want to change the time required for assembly of product \(0\) to \(3\) minutes. This corresponds to setting \(a_{0,0} = 3\), which is done by directly modifying the A matrix of the problem, as shown below.
prob$A[1,1] <- 3.0
The problem now has the form:
and
After this operation we can reoptimize the problem.
6.10.3 Appending Variables¶
We now want to add a new product with the following data:
Product no. |
Assembly (minutes) |
Polishing (minutes) |
Packing (minutes) |
Profit ($) |
|---|---|---|---|---|
3 |
4 |
0 |
1 |
1.00 |
This corresponds to creating a new variable \(x_3\), appending a new column to the \(A\) matrix and setting a new term in the objective. We do this in Listing 6.17
prob$c <- c(prob$c, 1.0)
prob$A <- cbind(prob$A, c(4.0, 0.0, 1.0))
prob$bx <- cbind(prob$bx, c(0.0,Inf))
After this operation the new problem is:
and
6.10.4 Appending Constraints¶
Now suppose we want to add a new stage to the production process called Quality control for which \(30000\) minutes are available. The time requirement for this stage is shown below:
Product no. |
Quality control (minutes) |
|---|---|
0 |
1 |
1 |
2 |
2 |
1 |
3 |
1 |
This corresponds to adding the constraint
to the problem. This is done as follows.
prob$A <- rbind(prob$A, c(1.0, 2.0, 1.0, 1.0))
prob$bc <- cbind(prob$bc, c(-Inf, 30000.0))
Again, we can continue with re-optimizing the modified problem.
6.10.5 Changing bounds¶
One typical reoptimization scenario is to change bounds. Suppose for instance that we must operate with limited time resources, and we must change the upper bounds in the problem as follows:
Operation |
Time available (before) |
Time available (new) |
|---|---|---|
Assembly |
100000 |
80000 |
Polishing |
50000 |
40000 |
Packing |
60000 |
50000 |
Quality control |
30000 |
22000 |
That means we would like to solve the problem:
In this case all we need to do is redefine the upper bound vector for the constraints, as shown in the next listing.
prob$bc<- rbind(blc=rep(-Inf, 4),
buc=c(80000, 40000, 50000, 22000))
r <- mosek(prob)
print(r$sol$bas$xx)
Again, we can continue with re-optimizing the modified problem.
6.10.6 Advanced hot-start¶
In order to exploit the possibility of hot-starting the simplex algorithms it is necessary to pass the old basic solution when the modified problem is re-optimized. Without this operation the optimizer will simply start from scratch. Any subset of the basic solution may be provided, but to achieve the best results all fields of res.sol.bas should be present, that is xx,xc,slx,sux,slc,suc,skx,skc.
# Reoptimize with changed coefficient
# Use previous solution to perform very simple hot-start.
# This part can be skipped, but then the optimizer will start
# from scratch on the new problem, i.e. without any hot-start.
prob$sol <- list(bas=r$sol$bas)
r <- mosek(prob)
print(r$sol$bas$xx)
If the dimensions of the problem (number of variables, constraints) have changed, the lengths of all fields have to be adjusted to be compatible with the reformulated problem. For example, here is an adjustment when adding a new variable:
here to download.¶ # Reoptimize with a new variable and hot-start
# All parts of the solution must be extended to the new dimensions.
prob$sol <- list(bas=r$sol$bas)
prob$sol$bas$xx <- c(prob$sol$bas$xx, 0.0)
prob$sol$bas$slx <- c(prob$sol$bas$slx, 0.0)
prob$sol$bas$sux <- c(prob$sol$bas$sux, 0.0)
prob$sol$bas$skx <- c(prob$sol$bas$skx, "UN")
r <- mosek(prob)
print(r$sol$bas$xx)
If the optimizer used the data from the previous run to hot-start the optimizer for reoptimization, this will be indicated in the log:
Optimizer - hotstart : yes
When performing re-optimizations, instead of removing a basic variable it may be more efficient to fix the variable at zero and then remove it when the problem is re-optimized and it has left the basis. This makes it easier for MOSEK to restart the simplex optimizer.
