6.6 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. This special case is discussed in Sec. 15.3 (Sensitivity Analysis).

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

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

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

(1)\[\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 11 loads and solves this problem.

Listing 11 Setting up and solving problem (1) Click here to download.
  MSKint32t       numvar = 3,
                  numcon = 3;
  MSKint32t       i, j;
  double          c[]    = {1.5, 2.5, 3.0};
  MSKint32t       ptrb[] = {0, 3, 6},
                  ptre[] = {3, 6, 9},
                  asub[] = { 0, 1, 2,
                             0, 1, 2,
                             0, 1, 2
                           };

  double          aval[] = { 2.0, 3.0, 2.0,
                             4.0, 2.0, 3.0,
                             3.0, 3.0, 2.0
                           };

  MSKboundkeye    bkc[]  = {MSK_BK_UP, MSK_BK_UP, MSK_BK_UP    };
  double          blc[]  = { -MSK_INFINITY, -MSK_INFINITY, -MSK_INFINITY};
  double          buc[]  = {100000, 50000, 60000};

  MSKboundkeye    bkx[]  = {MSK_BK_LO,     MSK_BK_LO,    MSK_BK_LO};
  double          blx[]  = {0.0,           0.0,          0.0,};
  double          bux[]  = { +MSK_INFINITY, +MSK_INFINITY, +MSK_INFINITY};

  double          *xx = NULL;
  MSKenv_t        env;
  MSKtask_t       task;
  MSKint32t       varidx, conidx;
  MSKrescodee     r;

  /* Create the mosek environment. */
  r = MSK_makeenv(&env, NULL);

  if ( r == MSK_RES_OK )
  {
    /* Create the optimization task. */
    r = MSK_maketask(env, numcon, numvar, &task);

    /* Append the constraints. */
    if (r == MSK_RES_OK)
      r = MSK_appendcons(task, numcon);

    /* Append the variables. */
    if (r == MSK_RES_OK)
      r = MSK_appendvars(task, numvar);

    /* Put C. */
    if (r == MSK_RES_OK)
      r = MSK_putcfix(task, 0.0);

    if (r == MSK_RES_OK)
      for (j = 0; j < numvar; ++j)
        r = MSK_putcj(task, j, c[j]);

    /* Put constraint bounds. */
    if (r == MSK_RES_OK)
      for (i = 0; i < numcon; ++i)
        r = MSK_putconbound(task, i, bkc[i], blc[i], buc[i]);

    /* Put variable bounds. */
    if (r == MSK_RES_OK)
      for (j = 0; j < numvar; ++j)
        r = MSK_putvarbound(task, j, bkx[j], blx[j], bux[j]);

    /* Put A. */
    if (r == MSK_RES_OK)
      if ( numcon > 0 )
        for (j = 0; j < numvar; ++j)
          r = MSK_putacol(task,
                          j,
                          ptre[j] - ptrb[j],
                          asub + ptrb[j],
                          aval + ptrb[j]);

    if (r == MSK_RES_OK)
      r = MSK_putobjsense(task,
                          MSK_OBJECTIVE_SENSE_MAXIMIZE);

    if (r == MSK_RES_OK)
      r = MSK_optimizetrm(task, NULL);

    if (r == MSK_RES_OK)
    {
      xx = calloc(numvar, sizeof(double));
      if ( !xx )
        r = MSK_RES_ERR_SPACE;
    }

    if (r == MSK_RES_OK)
      r = MSK_getxx(task,
                    MSK_SOL_BAS,       /* Basic solution.       */
                    xx);

6.6.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 calling the function MSK_putaij as shown below.

    if (r == MSK_RES_OK)
      r = MSK_putaij(task, 0, 0, 3.0);

The problem now has the form:

(2)\[\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.

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

Listing 12 How to add a new variable (column) Click here to download.
    /*********************** Add a new variable ******************/    
    /* Get index of new variable, this should be 3 */
    if (r == MSK_RES_OK)
      r = MSK_getnumvar(task, &varidx);
    /* Append a new variable x_3 to the problem */
    if (r == MSK_RES_OK)
    {
      r = MSK_appendvars(task, 1);
      numvar++;
    }
    /* Set bounds on new variable */
    if (r == MSK_RES_OK)
      r = MSK_putvarbound(task,
                          varidx,
                          MSK_BK_LO,
                          0,
                          +MSK_INFINITY);

    /* Change objective */
    if (r == MSK_RES_OK)
      r = MSK_putcj(task, varidx, 1.0);

    /* Put new values in the A matrix */
    if (r == MSK_RES_OK)
    {
      MSKint32t acolsub[] = {0,   2};
      double    acolval[] =  {4.0, 1.0};

      r = MSK_putacol(task,
                      varidx, /* column index */
                      2, /* num nz in column*/
                      acolsub,
                      acolval);
    }

After this operation the new problem is:

(3)\[\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.\]

6.6.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 13 Adding a new constraint. Click here to download.
    /* **************** Add a new constraint ******************* */
    /* Get index of new constraint*/
    if (r == MSK_RES_OK)
      r = MSK_getnumcon(task, &conidx);

    /* Append a new constraint */
    if (r == MSK_RES_OK) 
    {
      r = MSK_appendcons(task, 1);
      numcon++;
    }

    /* Set bounds on new constraint */
    if (r == MSK_RES_OK)
      r = MSK_putconbound(task,
                          conidx,
                          MSK_BK_UP,
                          -MSK_INFINITY,
                          30000);

    /* Put new values in the A matrix */
    if (r == MSK_RES_OK)
    {
      MSKidxt arowsub[] = {0,   1,   2,   3  };
      double arowval[] =  {1.0, 2.0, 1.0, 1.0};

      r = MSK_putarow(task,
                      conidx, /* row index */
                      4,      /* num nz in row*/
                      arowsub,
                      arowval);
    }

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