7.10 Problem Modification and Reoptimization

This tutorial demonstrates how to modify a model by adding new elements and changing existing ones. If instead you want to create one model of fixed structure and reoptimize it for changing input data, see Sec. 7.9 (Model Parametrization and Reoptimization).

The example we study is a simple production planning model.

Problem modifications regarding variables, cones, objective function and constraints can be grouped in categories:

  • adding constraints and variables,

  • modifying existing constraints.

Adding new variables and constraints is very easy. Modifications to existing constraints are more cumbersome, and the user should consider whether it is not worth rebuilding the model from scratch in such case. The amount of work required by Fusion to update the optimizer task may outweigh the potential gains.

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

Parameter settings (see Sec. 8.4 (Setting solver parameters)) can also be changed between optimizations.

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

(7.25)\[\begin{split}\begin{array}{lcccccll} \mbox{maximize} & 1.5 x_0 & + & 2.5 x_1 & + & 3.0 x_2 & & \\ \mbox{subject to} & 2 x_0 & + & 4 x_1 & + & 3 x_2 & \leq & 100000, \\ & 3 x_0 & + & 2 x_1 & + & 3 x_2 & \leq & 50000, \\ & 2 x_0 & + & 3 x_1 & + & 2 x_2 & \leq & 60000, \end{array}\end{split}\]

and

\[x_0,x_1,x_2 \geq 0.\]

Code in Listing 7.22 loads and solves this problem.

Listing 7.22 Setting up and solving problem (7.25) Click here to download.
        double[]   c = new double[] { 1.5, 2.5, 3.0 };
        double[,]  A = new double[,] { {2, 4, 3},
                                       {3, 2, 3},
                                       {2, 3, 2} };
        double[]   b = new double[] { 100000.0, 50000.0, 60000.0 };
        int   numvar = c.Length;
        int   numcon = b.Length;

        // Create a model and input data
        Variable x = M.Variable(numvar, Domain.GreaterThan(0.0));
        Constraint con = M.Constraint(Expr.Mul(A, x), Domain.LessThan(b));
        M.Objective(ObjectiveSense.Maximize, Expr.Dot(c, x));
        // Solve the problem
        M.Solve();

7.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\). Now the Constraint provides the method Constraint.Update, which can replace the columns corresponding to a variable with new values (or to replace the whole constraint). In our case the update we need is replacing \(1\cdot x_0\) with \(3\cdot x_0\) in the constraint with index \(0\).

        con.Index(0).Update(Expr.Mul(3.0, x.Index(0)), x.Index(0));

The problem now has the form:

(7.26)\[\begin{split}\begin{array} {lccccccl} \mbox{maximize} & 1.5 x_0 & + & 2.5 x_1 & + & 3.0 x_2 & & \\ \mbox{subject to} & 3 x_0 & + & 4 x_1 & + & 3 x_2 & \leq & 100000, \\ & 3 x_0 & + & 2 x_1 & + & 3 x_2 & \leq & 50000, \\ & 2 x_0 & + & 3 x_1 & + & 2 x_2 & \leq & 60000, \\ \end{array}\end{split}\]

and

\[x_0,x_1,x_2 \geq 0.\]

After this operation we can reoptimize the problem.

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

Listing 7.23 How to add a new variable (column) Click here to download.
        /*************** Add a new variable ******************************/
        // Create a variable and a compound view of all variables
        Variable x3 = M.Variable(Domain.GreaterThan(0.0));
        Variable xNew = Var.Vstack(x, x3);
        // Add to the exising constraint
        con.Update(Expr.Mul(x3, new double[]{4, 0, 1}), x3);
        // Change the objective to include x3
        M.Objective(ObjectiveSense.Maximize, Expr.Dot(new double[]{1.5,2.5,3.0,1.0}, xNew));

After this operation the new problem is:

(7.27)\[\begin{split}\begin{array}{lccccccccl} \mbox{maximize} & 1.5 x_0 & + & 2.5 x_1 & + & 3.0 x_2 & + & 1.0 x_3 & & \\ \mbox{subject to} & 3 x_0 & + & 4 x_1 & + & 3 x_2 & + & 4 x_3 & \leq & 100000, \\ & 3 x_0 & + & 2 x_1 & + & 3 x_2 & & & \leq & 50000, \\ & 2 x_0 & + & 3 x_1 & + & 2 x_2 & + & 1 x_3 & \leq & 60000, \end{array}\end{split}\]

and

\[x_0,x_1,x_2,x_3 \geq 0.\]

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

\[x_0 + 2 x_1 + x_2 + x_3 \leq 30000\]

to the problem. This is done as follows.

Listing 7.24 Adding a new constraint. Click here to download.
        /**************** Add a new constraint *****************************/
        Constraint con2 = M.Constraint(Expr.Dot(xNew, new double[]{1, 2, 1, 1}), Domain.LessThan(30000.0));

Again, we can continue with re-optimizing the modified problem.

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

(7.28)\[\begin{split}\begin{array}{lccccccccl} \mbox{maximize} & 1.5 x_0 & + & 2.5 x_1 & + & 3.0 x_2 & + & 1.0 x_3 & & \\ \mbox{subject to} & 3 x_0 & + & 4 x_1 & + & 3 x_2 & + & 4 x_3 & \leq & 80000, \\ & 3 x_0 & + & 2 x_1 & + & 3 x_2 & & & \leq & 40000, \\ & 2 x_0 & + & 3 x_1 & + & 2 x_2 & + & 1 x_3 & \leq & 50000, \\ & x_0 & + & 2 x_1 & + & x_2 & + & x_3 & \leq & 22000. \end{array}\end{split}\]

Since Domain objects are immutable, we cannot change the constraints by simply updating the value inside domains. To circumvent this, we add the differences between new and old bounds as fixed terms to the constraint expression. That means, we effectively construct an equivalent problem:

(7.29)\[\begin{split}\begin{array}{lccccccccccl} \mbox{maximize} & 1.5 x_0 & + & 2.5 x_1 & + & 3.0 x_2 & + & 1.0 x_3 & & & & \\ \mbox{subject to} & 3 x_0 & + & 4 x_1 & + & 3 x_2 & + & 4 x_3 & + & 20000 & \leq & 100000, \\ & 3 x_0 & + & 2 x_1 & + & 3 x_2 & & & + & 10000 & \leq & 50000, \\ & 2 x_0 & + & 3 x_1 & + & 2 x_2 & + & 1 x_3 & + & 10000 & \leq & 60000, \\ & x_0 & + & 2 x_1 & + & x_2 & + & x_3 & + & 8000 & \leq & 30000. \end{array}\end{split}\]

The next listing shows how to do it.

Listing 7.25 Change constraint bounds. Click here to download.
        /**************** Change constraint bounds *****************************/
        // Assemble all constraints we previously defined into one
        Constraint cAll = Constraint.Vstack(con, con2);
        // Change bounds by effectively updating fixed terms with the difference
        cAll.Update(new double[]{20000, 10000, 10000, 8000});

Again, we can continue with re-optimizing the modified problem.

7.10.6 Advanced hot-start

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.