6.1 Linear Optimization

The simplest optimization problem is a purely linear problem. A linear optimization problem (see also Sec. 12.1 (Linear Optimization)) is a problem of the following form:

Minimize or maximize the objective function

\[\sum_{j=0}^{n-1} c_j x_j + c^f\]

subject to the linear constraints

\[l_k^c \leq \sum_{j=0}^{n-1} a_{kj} x_j \leq u_k^c,\quad k=0,\ldots ,m-1,\]

and the bounds

\[l_j^x \leq x_j \leq u_j^x, \quad j=0,\ldots ,n-1.\]

The problem description consists of the following elements:

  • \(m\) and \(n\) — the number of constraints and variables, respectively,

  • \(x\) — the variable vector of length \(n\),

  • \(c\) — the coefficient vector of length \(n\)

    \[\begin{split}c = \left[ \begin{array}{c} c_0 \\ \vdots \\ c_{n-1} \end{array} \right],\end{split}\]
  • \(c^f\) — fixed term in the objective,

  • \(A\) — an \(m\times n\) matrix of coefficients

    \[\begin{split}A = \left[ \begin{array}{ccc} a_{0,0} & \cdots & a_{0,(n-1)} \\ \vdots & \cdots & \vdots \\ a_{(m-1),0} & \cdots & a_{(m-1),(n-1)} \end{array} \right],\end{split}\]
  • \(l^c\) and \(u^c\) — the lower and upper bounds on constraints,

  • \(l^x\) and \(u^x\) — the lower and upper bounds on variables.

Please note that we are using \(0\) as the first index: \(x_0\) is the first element in variable vector \(x\).

6.1.1 Example LO1

The following is an example of a small linear optimization problem:

(6.1)\[\begin{split}\begin{array} {lccccccccl} \mbox{maximize} & 3 x_0 & + & 1 x_1 & + & 5 x_2 & + & 1 x_3 & & \\ \mbox{subject to} & 3 x_0 & + & 1 x_1 & + & 2 x_2 & & & = & 30, \\ & 2 x_0 & + & 1 x_1 & + & 3 x_2 & + & 1 x_3 & \geq & 15, \\ & & & 2 x_1 & & & + & 3 x_3 & \leq & 25, \end{array}\end{split}\]

under the bounds

\[\begin{split}\begin{array}{ccccc} 0 & \leq & x_0 & \leq & \infty , \\ 0 & \leq & x_1 & \leq & 10, \\ 0 & \leq & x_2 & \leq & \infty ,\\ 0 & \leq & x_3 & \leq & \infty . \end{array}\end{split}\]

Solving the problem

To solve the problem above we go through the following steps:

  1. (Optionally) Creating an environment.

  2. Creating an optimization task.

  3. Loading a problem into the task object.

  4. Optimization.

  5. Extracting the solution.

Below we explain each of these steps.

Creating an environment.

The user can start by creating a MOSEK environment, but it is not necessary if the user does not need access to other functionalities, license management, additional routines, etc. Therefore in this tutorial we don’t create an explicit environment.

Creating an optimization task.

We create an empty task object. A task object represents all the data (inputs, outputs, parameters, information items etc.) associated with one optimization problem.

    try (mosek.Task task = new Task()) {
      // Directs the log task stream to the user specified
      // method task_msg_obj.stream
      task.set_Stream(
        mosek.streamtype.log,
        new mosek.Stream()
      { public void stream(String msg) { System.out.print(msg); }});

We also connect a call-back function to the task log stream. Messages related to the task are passed to the call-back function. In this case the stream call-back function writes its messages to the standard output stream. See Sec. 7.4 (Input/Output).

Loading a problem into the task object.

Before any problem data can be set, variables and constraints must be added to the problem via calls to the functions Task.appendcons and Task.appendvars.

      // Append 'numcon' empty constraints.
      // The constraints will initially have no bounds.
      task.appendcons(numcon);

      // Append 'numvar' variables.
      // The variables will initially be fixed at zero (x=0).
      task.appendvars(numvar);

New variables can now be referenced from other functions with indexes in \(\idxbeg, \ldots, \idxend{\mathtt{numvar}}\) and new constraints can be referenced with indexes in \(\idxbeg, \ldots , \idxend{\mathtt{numcon}}\). More variables and/or constraints can be appended later as needed, these will be assigned indexes from \(\mathtt{numvar}\)/\(\mathtt{numcon}\) and up. Optionally one can add names.

Setting the objective.

Next step is to set the problem data. We first set the objective coefficients \(c_j = \mathtt{c[j]}\). This can be done with functions such as Task.putcj or Task.putclist.

        task.putcj(j, c[j]);

Setting bounds on variables

For every variable we need to specify a bound key and two bounds according to Table 6.1.

Table 6.1 Bound keys as defined in the enum boundkey.

Bound key

Type of bound

Lower bound

Upper bound

boundkey.fx

\(u_j = l_j\)

Finite

Identical to the lower bound

boundkey.fr

Free

\(-\infty\)

\(+\infty\)

boundkey.lo

\(l_j \leq \cdots\)

Finite

\(+\infty\)

boundkey.ra

\(l_j \leq \cdots \leq u_j\)

Finite

Finite

boundkey.up

\(\cdots \leq u_j\)

\(-\infty\)

Finite

For instance bkx[0]= boundkey.lo means that \(x_0 \geq l_0^x\). Finally, the numerical values of the bounds on variables are given by

\[l_j^x = \mathtt{blx[j]}\]

and

\[u_j^x = \mathtt{bux[j]}.\]

Let us assume we have the bounds on variables stored in the arrays

    mosek.boundkey
    bkx[]  = {mosek.boundkey.lo,
              mosek.boundkey.ra,
              mosek.boundkey.lo,
              mosek.boundkey.lo
             };
    double  blx[]  = {0.0,
                      0.0,
                      0.0,
                      0.0
                     };
    double  bux[]  = { +infinity,
                       10.0,
                       +infinity,
                       +infinity
                     };

Then we can set them using various functions such Task.putvarbound, Task.putvarboundslice, Task.putvarboundlist, depending on what is most convenient in the given context. For instance:

        // Set the bounds on variable j.
        // blx[j] <= x_j <= bux[j]
        task.putvarbound(j, bkx[j], blx[j], bux[j]);

Defining the linear constraint matrix.

Recall that in our example the \(A\) matrix is given by

\[\begin{split}A = \left[ \begin{array}{cccc} 3 & 1 & 2 & 0 \\ 2 & 1 & 3 & 1 \\ 0 & 2 & 0 & 3 \end{array} \right].\end{split}\]

This matrix is stored in sparse format:

    int    asub[][] = { 
      {0, 1},
      {0, 1, 2},
      {0, 1},
      {1, 2}
    };
    double aval[][] = { 
      {3.0, 2.0},
      {1.0, 1.0, 2.0},
      {2.0, 3.0},
      {1.0, 3.0}
    };

The array aval[j] contains the non-zero values of column \(j\) and asub[j] contains the row indices of these non-zeros.

We now input the linear constraint matrix into the task. This can be done in many alternative ways, row-wise, column-wise or element by element in various orders. See functions such as Task.putarow, Task.putarowlist, Task.putaijlist, Task.putacol and similar.

        task.putacol(j,                     /* Variable (column) index.*/
                     asub[j],               /* Row index of non-zeros in column j.*/
                     aval[j]);              /* Non-zero Values of column j. */

Setting bounds on constraints

Finally, the bounds on each constraint are set similarly to the variable bounds, using the bound keys as in Table 6.1. This can be done with one of the many functions Task.putconbound, Task.putconboundslice, Task.putconboundlist, depending on the situation.

      // Set the bounds on constraints.
      // blc[i] <= constraint_i <= buc[i]
      for (int i = 0; i < numcon; ++i)
        task.putconbound(i, bkc[i], blc[i], buc[i]);

Optimization

After the problem is set-up the task can be optimized by calling the function Task.optimize.

      task.optimize();

Extracting the solution.

After optimizing the status of the solution is examined with a call to Task.getsolsta.

      mosek.solsta solsta[] = new mosek.solsta[1];
      task.getsolsta(mosek.soltype.bas, solsta);

If the solution status is reported as solsta.optimal the solution is extracted:

          double[] xx = task.getxx(mosek.soltype.bas); // Request the basic solution.

The Task.getxx function obtains the solution. MOSEK may compute several solutions depending on the optimizer employed. In this example the basic solution is requested by setting the first argument to soltype.bas. For details about fetching solutions see Sec. 7.2 (Accessing the solution).

Catching exceptions

We catch any exceptions thrown by MOSEK in the lines:

    catch (mosek.Exception e) {
      System.out.println ("An error/warning was encountered");
      System.out.println (e.toString());
      throw e;
    }

The types of exceptions that MOSEK can throw can be seen in Sec. 15.5 (Exceptions). See also Sec. 7.3 (Errors and exceptions).

Source code

The complete source code lo1.java of this example appears below. See also lo2.java for a version where the \(A\) matrix is entered row-wise.

Listing 6.1 Linear optimization example. Click here to download.
package com.mosek.example;
import mosek.*;

public class lo1 {
  static final int numcon = 3;
  static final int numvar = 4;

  public static void main (String[] args) {
    // Since the value of infinity is ignored, we define it solely
    // for symbolic purposes
    double infinity = 0;

    double c[]    = {3.0, 1.0, 5.0, 1.0};
    int    asub[][] = { 
      {0, 1},
      {0, 1, 2},
      {0, 1},
      {1, 2}
    };
    double aval[][] = { 
      {3.0, 2.0},
      {1.0, 1.0, 2.0},
      {2.0, 3.0},
      {1.0, 3.0}
    };
    mosek.boundkey[]
    bkc    = {mosek.boundkey.fx,
              mosek.boundkey.lo,
              mosek.boundkey.up
             };
    double  blc[]  = {30.0,
                      15.0,
                      -infinity
                     };
    double  buc[]  = {30.0,
                      +infinity,
                      25.0
                     };
    mosek.boundkey
    bkx[]  = {mosek.boundkey.lo,
              mosek.boundkey.ra,
              mosek.boundkey.lo,
              mosek.boundkey.lo
             };
    double  blx[]  = {0.0,
                      0.0,
                      0.0,
                      0.0
                     };
    double  bux[]  = { +infinity,
                       10.0,
                       +infinity,
                       +infinity
                     };

    try (mosek.Task task = new Task()) {
      // Directs the log task stream to the user specified
      // method task_msg_obj.stream
      task.set_Stream(
        mosek.streamtype.log,
        new mosek.Stream()
      { public void stream(String msg) { System.out.print(msg); }});

      // Append 'numcon' empty constraints.
      // The constraints will initially have no bounds.
      task.appendcons(numcon);

      // Append 'numvar' variables.
      // The variables will initially be fixed at zero (x=0).
      task.appendvars(numvar);

      for (int j = 0; j < numvar; ++j) {
        // Set the linear term c_j in the objective.
        task.putcj(j, c[j]);

        // Set the bounds on variable j.
        // blx[j] <= x_j <= bux[j]
        task.putvarbound(j, bkx[j], blx[j], bux[j]);

        // Input column j of A
        task.putacol(j,                     /* Variable (column) index.*/
                     asub[j],               /* Row index of non-zeros in column j.*/
                     aval[j]);              /* Non-zero Values of column j. */
      }

      // Set the bounds on constraints.
      // blc[i] <= constraint_i <= buc[i]
      for (int i = 0; i < numcon; ++i)
        task.putconbound(i, bkc[i], blc[i], buc[i]);

      // Input the objective sense (minimize/maximize)
      task.putobjsense(mosek.objsense.maximize);

      // Solve the problem
      task.optimize();

      // Print a summary containing information
      // about the solution for debugging purposes
      task.solutionsummary(mosek.streamtype.msg);

      // Get status information about the solution
      mosek.solsta solsta[] = new mosek.solsta[1];
      task.getsolsta(mosek.soltype.bas, solsta);

      switch (solsta[0]) {
        case optimal:
          double[] xx = task.getxx(mosek.soltype.bas); // Request the basic solution.

          System.out.println("Optimal primal solution\n");
          for (int j = 0; j < numvar; ++j)
            System.out.println ("x[" + j + "]:" + xx[j]);
          break;
        case dual_infeas_cer:
        case prim_infeas_cer:
          System.out.println("Primal or dual infeasibility certificate found.\n");
          break;
        case unknown:
          System.out.println("Unknown solution status.\n");
          break;
        default:
          System.out.println("Other solution status");
          break;
      }
    }
    catch (mosek.Exception e) {
      System.out.println ("An error/warning was encountered");
      System.out.println (e.toString());
      throw e;
    }
  }
}