5. Basic API tutorial


In this chapter the reader will learn how to build a simple application that uses MOSEK.

A number of examples is provided to demonstrate the functionality required for solving linear, quadratic, and conic problems as well as mixed integer problems.

Please note that the section on linear optimization also describes most of the basic functionality that is not specific to linear problems. Hence, it is recommended to read Section 5.2 before reading the rest of this chapter.

5.1. The basics

A typical program using the MOSEK C interface can be described shortly:

  1. Create an environment (MSKenv_t) object.
  2. Set up some environment specific data and initialize the environment object.
  3. Create a task (MSKtask_t) object.
  4. Load a problem into the task object.
  5. Optimize the problem.
  6. Fetch the result.
  7. Delete the environment and task objects.

5.1.1. The environment and the task

The first MOSEK related step in any program that employs MOSEK is to create an environment (MSKenv_t) object. The environment contains environment specific data such as information about the license file, streams for environment messages etc. Before creating any task objects, the environment must be initialized using MSK_initenv. When this is done one or more task (MSKtask_t) objects can be created. Each task is associated with a single environment and defines a complete optimization problem as well as task message streams and optimization parameters.

In C, the creation of an environment and a task could like this:

{
  MSKenv_t    env = NULL;
  MSKtask_t   task = NULL;
  MSKrescodee res;

  /* Create an environment */
  res = MSK_makeenv(&env, NULL,NULL,NULL,NULL);

  /* You may connect streams and other callbacks to env here */

  /* Initialize the environment */
  if (res == MSK_RES_OK)
    res = MSK_initenv(env)
    
  /* Create a task */
  if (res == MSK_RES_OK)
    res = MSK_maketask(env, 0,0, &task);
  ...
  /* input some task data, optimize etc. */
  ...
  MSK_deletetask(&task);
  MSK_deleteenv(&env);
}

Please note that an environment should, if possible, be shared between multiple tasks.

5.1.2. A simple working example

The following simple example shows a working C program which

  • creates an environment and a task,
  • reads a problem from a file,
  • optimizes the problem, and
  • writes the solution to a file.

/* Copyright: Copyright (c) 1998-2011 MOSEK ApS, Denmark. All rights reserved. File: simple.c Purpose: To demonstrate a very simple example using MOSEK by reading a problem file, solving the problem and writing the solution to a file. */ #include "mosek.h" int main (int argc, char * argv[]) { MSKtask_t task = NULL; MSKenv_t env = NULL; MSKrescodee res = MSK_RES_OK; if (argc <= 1) { printf ("Missing argument. The syntax is:\n"); printf (" simple inputfile [ solutionfile ]\n"); } else { /* Create the mosek environment. The `NULL' arguments here, are used to specify customized memory allocators and a memory debug file. These can safely be ignored for now. */ res = MSK_makeenv(&env, NULL, NULL, NULL, NULL); /* Initialize the environment */ if ( res==MSK_RES_OK ) MSK_initenv (env); /* Create a task object linked to the environment env. Initially we create it with 0 variables and 0 columns, since we do not know the size of the problem. */ if ( res==MSK_RES_OK ) res = MSK_maketask (env, 0,0, &task); /* We assume that a problem file was given as the first command line argument (received in `argv'). */ if ( res==MSK_RES_OK ) res = MSK_readdata (task, argv[1]); /* Solve the problem */ if ( res==MSK_RES_OK ) MSK_optimize(task); /* Print a summary of the solution. */ MSK_solutionsummary(task, MSK_STREAM_MSG); /* If an output file was specified, write a solution */ if ( res==MSK_RES_OK && argc>2 ) { /* We define the output format to be OPF, and tell MOSEK to leave out parameters and problem data from the output file. */ MSK_putintparam (task,MSK_IPAR_WRITE_DATA_FORMAT, MSK_DATA_FORMAT_OP); MSK_putintparam (task,MSK_IPAR_OPF_WRITE_SOLUTIONS, MSK_ON); MSK_putintparam (task,MSK_IPAR_OPF_WRITE_HINTS, MSK_OFF); MSK_putintparam (task,MSK_IPAR_OPF_WRITE_PARAMETERS, MSK_OFF); MSK_putintparam (task,MSK_IPAR_OPF_WRITE_PROBLEM, MSK_OFF); MSK_writedata(task,argv[2]); } MSK_deletetask(&task); MSK_deleteenv(&env); } return res; }

5.1.2.1. Writing a problem to a file

It is frequently beneficial to write a problem to a file that can be stored for later use or inspected visually. The MSK_writedata function is used write a problem to a file as follows

MSK_writedata(task,argv[2]);

By default the extension of the filename is the format written. I.e. the filename somename.opf implies the file is written in the OPF format.

Similarly, the function MSK_readdata reads a problem from a file:

res = MSK_readdata (task, argv[1]);

5.1.2.2. Inputting and outputting problem data

An optimization problem consists of several components; objective, objective sense, constraints, variable bounds etc. Therefore, the task (MSKtask_t) provides a number of methods to operate on the task specific data, all of which are listed in Section 15.4.

5.1.2.3. Setting parameters

Apart from the problem data, the task contains a number of parameters defining the behavior of MOSEK. For example the MSK_IPAR_OPTIMIZER parameter defines which optimizer to use. A complete list of all parameters are listed in Chapter 16.

5.1.3. Compiling and running examples

All examples presented in this chapter are distributed with MOSEK and are available in the directory

 mosek/6/tools/examples/ 

in the MOSEK installation. Chapter 4 describes how to compile and run the examples.

It is recommended to copy examples to a different directory before modifying and compiling them.

5.2. Linear optimization

The simplest optimization problem is a purely linear problem. A linear optimization problem is a problem of the following form:

Minimize or maximize the objective function

\begin{math}\nonumber{}\sum _{{j=0}}^{{n-1}}c_{j}x_{j}+c^{f}\end{math} (5.2.1)

subject to the linear constraints

\begin{math}\nonumber{}l_{k}^{c}\leq{}\sum _{{j=0}}^{{n-1}}a_{{kj}}x_{j}\leq{}u_{k}^{c},~k=0,\ldots ,m-1,\end{math} (5.2.2)

and the bounds

\begin{math}\nonumber{}l_{j}^{x}\leq{}x_{j}\leq{}u_{j}^{x},~j=0,\ldots ,n-1,\end{math} (5.2.3)

where we have used the problem elements

m and n, which are the number of constraints and variables respectively,

x, which is the variable vector of length n,

c, which is a coefficient vector of size n

\begin{displaymath}\nonumber{}c=\left[\begin{array}{c}\nonumber{}c_{0}\\\nonumber{}\vdots \\\nonumber{}c_{{n-1}}\end{array}\right],\end{displaymath}

[[MathCmd 10]], which is a constant,

A, which is a [[MathCmd 11]] matrix of coefficients is given by

\begin{displaymath}\nonumber{}A=\left[\begin{array}{ccc}\nonumber{}a_{{0,0}} & \cdots  & a_{{0,(n-1)}}\\\nonumber{}\vdots  & \cdots  & \vdots \\\nonumber{}a_{{(m-1),0}} & \cdots  & a_{{(m-1),(n-1)}}\end{array}\right],\end{displaymath}

[[MathCmd 13]] and [[MathCmd 14]], which specify the lower and upper bounds on constraints respectively, and

[[MathCmd 15]] and [[MathCmd 16]], which specifies the lower and upper bounds on variables respectively.

Please note the unconventional notation using 0 as the first index rather than 1. Hence, [[MathCmd 17]] is the first element in variable vector x. This convention has been adapted from C arrays which are indexed from 0.

5.2.1. Linear optimization example: lo1

The following is an example of a linear optimization problem:

\begin{math}\nonumber{}\begin{array}{lccccccccl}\nonumber{}\mbox{maximize} & 3x_{0} & + & 1x_{1} & + & 5x_{2} & + & 1x_{3} &  & \\\nonumber{}\mbox{subject to} & 3x_{0} & + & 1x_{1} & + & 2x_{2} &  &  & = & 30,\\\nonumber{} & 2x_{0} & + & 1x_{1} & + & 3x_{2} & + & 1x_{3} & \geq{} & 15,\\\nonumber{} &  &  & 2x_{1} &  &  & + & 3x_{3} & \leq{} & 25,\end{array}\end{math} (5.2.4)

having the bounds

\begin{math}\nonumber{}\begin{array}{ccccc}\nonumber{}0 & \leq{} & x_{0} & \leq{} & \infty ,\\\nonumber{}0 & \leq{} & x_{1} & \leq{} & 10,\\\nonumber{}0 & \leq{} & x_{2} & \leq{} & \infty ,\\\nonumber{}0 & \leq{} & x_{3} & \leq{} & \infty .\end{array}\end{math} (5.2.5)

5.2.1.1. Solving the problem

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

  1. Create an environment.
  2. Create an optimization task.
  3. Load a problem into the task object.
  4. Optimization.
  5. Extracting the solution.

Below we explain each of these steps. For the complete source code see section 5.2.1.2. The code can also be found in:

    mosek\6\tools\examples\c\lo1.c
Create an environment.

Before setting up the optimization problem, a MOSEK environment must be created and initialized. This is done in the lines:

r = MSK_makeenv(&env,NULL,NULL,NULL,NULL); /* Directs the env log stream to the 'printstr' function. */ if ( r==MSK_RES_OK ) MSK_linkfunctoenvstream(env,MSK_STREAM_LOG,NULL,printstr); /* Initialize the environment. */ if ( r==MSK_RES_OK ) r = MSK_initenv(env);

We connect a call-back function to the environment log stream. In this case the call-back function simply prints messages to the standard output stream.

Create an optimization task.

Next, an empty task object is created:

/* Create the optimization task. */ r = MSK_maketask(env,NUMCON,NUMVAR,&task); /* Directs the log task stream to the 'printstr' function. */ if ( r==MSK_RES_OK ) MSK_linkfunctotaskstream(task,MSK_STREAM_LOG,NULL,printstr);

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.

Load a problem into the task object.

First an estimate of the size of the input data is set. This is done to increase the speed of inputting data and is optional.

if (r == MSK_RES_OK) r = MSK_putmaxnumvar(task,NUMVAR); if (r == MSK_RES_OK) r = MSK_putmaxnumcon(task,NUMCON); if (r == MSK_RES_OK) r = MSK_putmaxnumanz(task,NUMANZ);

Before any problem data can be set, variables and constraints must be added to the problem via calls to the function MSK_append.

/* Append 'NUMCON' empty constraints. The constraints will initially have no bounds. */ if ( r == MSK_RES_OK ) r = MSK_append(task,MSK_ACC_CON,NUMCON); /* Append 'NUMVAR' variables. The variables will initially be fixed at zero (x=0). */ if ( r == MSK_RES_OK ) r = MSK_append(task,MSK_ACC_VAR,NUMVAR);

New variables can now be referenced from other functions with indexes in [[MathCmd 20]] and new constraints can be referenced with indexes in [[MathCmd 21]]. More variables / constraints can be appended later as needed, these will be assigned indexes from [[MathCmd 22]] / [[MathCmd 23]] and up.

Next step is to set the problem data. We loop over each variable index [[MathCmd 24]] calling functions to set problem data. We first set the objective coefficient [[MathCmd 25]] by calling the function MSK_putcj.

/* Set the linear term c_j in the objective.*/ if(r == MSK_RES_OK) r = MSK_putcj(task,j,c[j]);

The bounds on variables are stored in the arrays

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

and are set with calls to MSK_putbound.

/* Set the bounds on variable j. blx[j] <= x_j <= bux[j] */ if(r == MSK_RES_OK) r = MSK_putbound(task, MSK_ACC_VAR, /* Put bounds on variables.*/ j, /* Index of variable.*/ bkx[j], /* Bound key.*/ blx[j], /* Numerical value of lower bound.*/ bux[j]); /* Numerical value of upper bound.*/

The Bound key stored in bkx specify the type of the bound according to Table 5.1.

Bound key Type of bound Lower bound Upper bound
MSK_BK_FX [[MathCmd 26]] Finite Identical to the lower bound
MSK_BK_FR Free Minus infinity Plus infinity
MSK_BK_LO [[MathCmd 27]] Finite Plus infinity
MSK_BK_RA [[MathCmd 28]] Finite Finite
MSK_BK_UP [[MathCmd 29]] Minus infinity Finite
Table 5.1: Interpretation of the bound keys.

For instance bkx[0]= MSK_BK_LO means that [[MathCmd 30]]. Finally, the numerical values of the bounds on variables are given by

\begin{math}\nonumber{}l_{j}^{x}=\mathtt{blx[j]}\end{math} (5.2.6)

and

\begin{math}\nonumber{}u_{j}^{x}=\mathtt{bux[j]}.\end{math} (5.2.7)

Recall that in our example the A matrix is given by

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

This matrix is stored in sparse format in the arrays:

MSKlidxt aptrb[] = {0, 2, 5, 7}; MSKlidxt aptre[] = {2, 5, 7, 9}; MSKidxt 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 ptrb, ptre, asub, and aval arguments define the constraint matrix A in the column ordered sparse format (for details, see Section 5.8.3.2).

Using the function MSK_putavec we set column j of A

/* Input column j of A */ if(r == MSK_RES_OK) r = MSK_putavec(task, MSK_ACC_VAR, /* Input columns of A.*/ j, /* Variable (column) index.*/ aptre[j]-aptrb[j], /* Number of non-zeros in column j.*/ asub+aptrb[j], /* Pointer to row indexes of column j.*/ aval+aptrb[j]); /* Pointer to Values of column j.*/

Alternatively, the same A matrix can be set one row at a time; please see section 5.2.2 for an example.

Finally, the bounds on each constraint are set by looping over each constraint index [[MathCmd 34]]

/* Set the bounds on constraints. for i=1, ...,NUMCON : blc[i] <= constraint i <= buc[i] */ for(i=0; i<NUMCON && r==MSK_RES_OK; ++i) r = MSK_putbound(task, MSK_ACC_CON, /* Put bounds on constraints.*/ i, /* Index of constraint.*/ bkc[i], /* Bound key.*/ blc[i], /* Numerical value of lower bound.*/ buc[i]); /* Numerical value of upper bound.*/
Optimization:

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

r = MSK_optimizetrm(task,&trmcode);
Extracting the solution.

After optimizing the status of the solution is examined with a call to MSK_getsolutionstatus. If the solution status is reported as MSK_SOL_STA_OPTIMAL or MSK_SOL_STA_NEAR_OPTIMAL the solution is extracted in the lines below:

MSK_getsolutionslice(task, MSK_SOL_BAS, /* Request the basic solution. */ MSK_SOL_ITEM_XX,/* Which part of solution. */ 0, /* Index of first variable. */ NUMVAR, /* Index of last variable+1. */ xx);

The MSK_getsolutionslice function obtains a “slice” of the solution. MOSEK may compute several solutions depending on the optimizer employed. In this example the basic solution is requested by setting the second argument to MSK_SOL_BAS. The third argument MSK_SOL_ITEM_XX specifies that we want the variable values of the solution. The two following arguments 0 and NUMVAR specifies the range of variable values we want.

The range specified is the first index (here “0”) up to but not including the second index (here “NUMVAR).

5.2.1.2. Source code for lo1

/* Copyright: Copyright (c) 1998-2011 MOSEK ApS, Denmark. All rights reserved. File: lo1.c Purpose: To demonstrate how to solve a small linear optimization problem using the MOSEK C API. */ #include <stdio.h> #include "mosek.h" /* This function prints log output from MOSEK to the terminal. */ static void MSKAPI printstr(void *handle, char str[]) { printf("%s",str); } /* printstr */ #define NUMVAR 4 #define NUMCON 3 #define NUMANZ 9 int main(int argc,char *argv[]) { MSKrescodee r; MSKidxt i,j; double c[] = {3.0, 1.0, 5.0, 1.0}; /* Below is the sparse representation of the A matrix stored by column. */ MSKlidxt aptrb[] = {0, 2, 5, 7}; MSKlidxt aptre[] = {2, 5, 7, 9}; MSKidxt 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}; /* Bounds on constraints. */ MSKboundkeye bkc[] = {MSK_BK_FX, MSK_BK_LO, MSK_BK_UP }; double blc[] = {30.0, 15.0, -MSK_INFINITY}; double buc[] = {30.0, +MSK_INFINITY, 25.0 }; /* Bounds on variables. */ MSKboundkeye bkx[] = {MSK_BK_LO, MSK_BK_RA, MSK_BK_LO, MSK_BK_LO }; double blx[] = {0.0, 0.0, 0.0, 0.0 }; double bux[] = {+MSK_INFINITY, 10.0, +MSK_INFINITY, +MSK_INFINITY }; double xx[NUMVAR]; MSKenv_t env = NULL; MSKtask_t task = NULL; /* Create the mosek environment. */ r = MSK_makeenv(&env,NULL,NULL,NULL,NULL); /* Directs the env log stream to the 'printstr' function. */ if ( r==MSK_RES_OK ) MSK_linkfunctoenvstream(env,MSK_STREAM_LOG,NULL,printstr); /* Initialize the environment. */ if ( r==MSK_RES_OK ) r = MSK_initenv(env); if ( r==MSK_RES_OK ) { /* Create the optimization task. */ r = MSK_maketask(env,NUMCON,NUMVAR,&task); /* Directs the log task stream to the 'printstr' function. */ if ( r==MSK_RES_OK ) MSK_linkfunctotaskstream(task,MSK_STREAM_LOG,NULL,printstr); /* Give MOSEK an estimate of the size of the input data. This is done to increase the speed of inputting data. However, it is optional. */ if (r == MSK_RES_OK) r = MSK_putmaxnumvar(task,NUMVAR); if (r == MSK_RES_OK) r = MSK_putmaxnumcon(task,NUMCON); if (r == MSK_RES_OK) r = MSK_putmaxnumanz(task,NUMANZ); /* Append 'NUMCON' empty constraints. The constraints will initially have no bounds. */ if ( r == MSK_RES_OK ) r = MSK_append(task,MSK_ACC_CON,NUMCON); /* Append 'NUMVAR' variables. The variables will initially be fixed at zero (x=0). */ if ( r == MSK_RES_OK ) r = MSK_append(task,MSK_ACC_VAR,NUMVAR); /* Optionally add a constant term to the objective. */ if ( r ==MSK_RES_OK ) r = MSK_putcfix(task,0.0); for(j=0; j<NUMVAR && r == MSK_RES_OK; ++j) { /* Set the linear term c_j in the objective.*/ if(r == MSK_RES_OK) r = MSK_putcj(task,j,c[j]); /* Set the bounds on variable j. blx[j] <= x_j <= bux[j] */ if(r == MSK_RES_OK) r = MSK_putbound(task, MSK_ACC_VAR, /* Put bounds on variables.*/ j, /* Index of variable.*/ bkx[j], /* Bound key.*/ blx[j], /* Numerical value of lower bound.*/ bux[j]); /* Numerical value of upper bound.*/ /* Input column j of A */ if(r == MSK_RES_OK) r = MSK_putavec(task, MSK_ACC_VAR, /* Input columns of A.*/ j, /* Variable (column) index.*/ aptre[j]-aptrb[j], /* Number of non-zeros in column j.*/ asub+aptrb[j], /* Pointer to row indexes of column j.*/ aval+aptrb[j]); /* Pointer to Values of column j.*/ } /* Set the bounds on constraints. for i=1, ...,NUMCON : blc[i] <= constraint i <= buc[i] */ for(i=0; i<NUMCON && r==MSK_RES_OK; ++i) r = MSK_putbound(task, MSK_ACC_CON, /* Put bounds on constraints.*/ i, /* Index of constraint.*/ bkc[i], /* Bound key.*/ blc[i], /* Numerical value of lower bound.*/ buc[i]); /* Numerical value of upper bound.*/ /* Maximize objective function. */ if (r == MSK_RES_OK) r = MSK_putobjsense(task, MSK_OBJECTIVE_SENSE_MAXIMIZE); if ( r==MSK_RES_OK ) { MSKrescodee trmcode; /* Run optimizer */ r = MSK_optimizetrm(task,&trmcode); /* Print a summary containing information about the solution for debugging purposes. */ MSK_solutionsummary (task,MSK_STREAM_LOG); if ( r==MSK_RES_OK ) { MSKsolstae solsta; int j; MSK_getsolutionstatus (task, MSK_SOL_BAS, NULL, &solsta); switch(solsta) { case MSK_SOL_STA_OPTIMAL: case MSK_SOL_STA_NEAR_OPTIMAL: MSK_getsolutionslice(task, MSK_SOL_BAS, /* Request the basic solution. */ MSK_SOL_ITEM_XX,/* Which part of solution. */ 0, /* Index of first variable. */ NUMVAR, /* Index of last variable+1. */ xx); printf("Optimal primal solution\n"); for(j=0; j<NUMVAR; ++j) printf("x[%d]: %e\n",j,xx[j]); break; case MSK_SOL_STA_DUAL_INFEAS_CER: case MSK_SOL_STA_PRIM_INFEAS_CER: case MSK_SOL_STA_NEAR_DUAL_INFEAS_CER: case MSK_SOL_STA_NEAR_PRIM_INFEAS_CER: printf("Primal or dual infeasibility certificate found.\n"); break; case MSK_SOL_STA_UNKNOWN: printf("The status of the solution could not be determined.\n"); break; default: printf("Other solution status."); break; } } else { printf("Error while optimizing.\n"); } } if (r != MSK_RES_OK) { /* In case of an error print error code and description. */ char symname[MSK_MAX_STR_LEN]; char desc[MSK_MAX_STR_LEN]; printf("An error occurred while optimizing.\n"); MSK_getcodedesc (r, symname, desc); printf("Error %s - '%s'\n",symname,desc); } MSK_deletetask(&task); MSK_deleteenv(&env); } return r; }

5.2.2. Row-wise input

In the previous example the A matrix is set one column at a time. Alternatively the same matrix can be set one row at a time or the two methods can be mixed as in the example in section 5.6. The following example show how to set the A matrix by rows.

The source code for this example can be found in:

    mosek\6\tools\examples\c\lo2.c

/* Copyright: Copyright (c) 1998-2011 MOSEK ApS, Denmark. All rights reserved. File: lo2.c Purpose: To demonstrate how to solve a small linear optimization problem using the MOSEK C API. */ #include <stdio.h> #include "mosek.h" /* This function prints log output from MOSEK to the terminal. */ static void MSKAPI printstr(void *handle, char str[]) { printf("%s",str); } /* printstr */ #define NUMVAR 4 #define NUMCON 3 #define NUMANZ 9 int main(int argc,char *argv[]) { MSKrescodee r; MSKidxt i,j; double c[] = {3.0, 1.0, 5.0, 1.0}; /* Below is the sparse representation of the A matrix stored by row. */ MSKlidxt aptrb[] = {0, 3, 7}; MSKlidxt aptre[] = {3, 7, 9}; MSKidxt asub[] = { 0,1,2, 0,1,2,3, 1,3}; double aval[] = { 3.0, 1.0, 2.0, 2.0, 1.0, 3.0, 1.0, 2.0, 3.0}; /* Bounds on constraints. */ MSKboundkeye bkc[] = {MSK_BK_FX, MSK_BK_LO, MSK_BK_UP }; double blc[] = {30.0, 15.0, -MSK_INFINITY}; double buc[] = {30.0, +MSK_INFINITY, 25.0 }; /* Bounds on variables. */ MSKboundkeye bkx[] = {MSK_BK_LO, MSK_BK_RA, MSK_BK_LO, MSK_BK_LO }; double blx[] = {0.0, 0.0, 0.0, 0.0 }; double bux[] = {+MSK_INFINITY, 10.0, +MSK_INFINITY, +MSK_INFINITY }; double xx[NUMVAR]; MSKenv_t env = NULL; MSKtask_t task = NULL; /* Create the mosek environment. */ r = MSK_makeenv(&env,NULL,NULL,NULL,NULL); /* Directs the env log stream to the 'printstr' function. */ if ( r==MSK_RES_OK ) MSK_linkfunctoenvstream(env,MSK_STREAM_LOG,NULL,printstr); /* Initialize the environment. */ if ( r==MSK_RES_OK ) r = MSK_initenv(env); if ( r==MSK_RES_OK ) { /* Create the optimization task. */ r = MSK_maketask(env,NUMCON,NUMVAR,&task); /* Directs the log task stream to the 'printstr' function. */ if ( r==MSK_RES_OK ) MSK_linkfunctotaskstream(task,MSK_STREAM_LOG,NULL,printstr); /* Give MOSEK an estimate of the size of the input data. This is done to increase the speed of inputting data. However, it is optional. */ if (r == MSK_RES_OK) r = MSK_putmaxnumvar(task,NUMVAR); if (r == MSK_RES_OK) r = MSK_putmaxnumcon(task,NUMCON); if (r == MSK_RES_OK) r = MSK_putmaxnumanz(task,NUMANZ); /* Append 'NUMCON' empty constraints. The constraints will initially have no bounds. */ if ( r == MSK_RES_OK ) r = MSK_append(task,MSK_ACC_CON,NUMCON); /* Append 'NUMVAR' variables. The variables will initially be fixed at zero (x=0). */ if ( r == MSK_RES_OK ) r = MSK_append(task,MSK_ACC_VAR,NUMVAR); /* Optionally add a constant term to the objective. */ if ( r ==MSK_RES_OK ) r = MSK_putcfix(task,0.0); for(j=0; j<NUMVAR && r == MSK_RES_OK; ++j) { /* Set the linear term c_j in the objective.*/ if(r == MSK_RES_OK) r = MSK_putcj(task,j,c[j]); /* Set the bounds on variable j. blx[j] <= x_j <= bux[j] */ if(r == MSK_RES_OK) r = MSK_putbound(task, MSK_ACC_VAR, /* Put bounds on variables.*/ j, /* Index of variable.*/ bkx[j], /* Bound key.*/ blx[j], /* Numerical value of lower bound.*/ bux[j]); /* Numerical value of upper bound.*/ } /* Set the bounds on constraints. for i=1, ...,NUMCON : blc[i] <= constraint i <= buc[i] */ for(i=0; i<NUMCON && r==MSK_RES_OK; ++i) { r = MSK_putbound(task, MSK_ACC_CON, /* Put bounds on constraints.*/ i, /* Index of constraint.*/ bkc[i], /* Bound key.*/ blc[i], /* Numerical value of lower bound.*/ buc[i]); /* Numerical value of upper bound.*/ /* Input column j of A */ if(r == MSK_RES_OK) r = MSK_putavec(task, MSK_ACC_CON, /* Input row of A.*/ i, /* Row index.*/ aptre[i]-aptrb[i], /* Number of non-zeros in row i.*/ asub+aptrb[i], /* Pointer to column indexes of row i.*/ aval+aptrb[i]); /* Pointer to Values of row i.*/ } /* Maximize objective function. */ if (r == MSK_RES_OK) r = MSK_putobjsense(task, MSK_OBJECTIVE_SENSE_MAXIMIZE); if ( r==MSK_RES_OK ) { MSKrescodee trmcode; /* Run optimizer */ r = MSK_optimizetrm(task,&trmcode); /* Print a summary containing information about the solution for debugging purposes. */ MSK_solutionsummary (task,MSK_STREAM_LOG); if ( r==MSK_RES_OK ) { MSKsolstae solsta; int j; MSK_getsolutionstatus (task, MSK_SOL_BAS, NULL, &solsta); switch(solsta) { case MSK_SOL_STA_OPTIMAL: case MSK_SOL_STA_NEAR_OPTIMAL: MSK_getsolutionslice(task, MSK_SOL_BAS, /* Request the basic solution. */ MSK_SOL_ITEM_XX,/* Which part of solution. */ 0, /* Index of first variable. */ NUMVAR, /* Index of last variable+1. */ xx); printf("Optimal primal solution\n"); for(j=0; j<NUMVAR; ++j) printf("x[%d]: %e\n",j,xx[j]); break; case MSK_SOL_STA_DUAL_INFEAS_CER: case MSK_SOL_STA_PRIM_INFEAS_CER: case MSK_SOL_STA_NEAR_DUAL_INFEAS_CER: case MSK_SOL_STA_NEAR_PRIM_INFEAS_CER: printf("Primal or dual infeasibility certificate found.\n"); break; case MSK_SOL_STA_UNKNOWN: printf("The status of the solution could not be determined.\n"); break; default: printf("Other solution status."); break; } } else { printf("Error while optimizing.\n"); } } if (r != MSK_RES_OK) { /* In case of an error print error code and description. */ char symname[MSK_MAX_STR_LEN]; char desc[MSK_MAX_STR_LEN]; printf("An error occurred while optimizing.\n"); MSK_getcodedesc (r, symname, desc); printf("Error %s - '%s'\n",symname,desc); } MSK_deletetask(&task); MSK_deleteenv(&env); } return r; }

5.3. Quadratic optimization

MOSEK can solve quadratic and quadratically constrained convex problems. This class of problems can be formulated as follows:

\begin{math}\nonumber{}\begin{array}{lrcccll}\nonumber{}\mbox{minimize} &  &  & \frac{1}{2}x^{T}Q^{o}x+c^{T}x+c^{f} &  &  & \\\nonumber{}\mbox{subject to} & l_{k}^{c} & \leq{} & \frac{1}{2}x^{T}Q^{k}x+\sum \limits _{{j=0}}^{{n-1}}a_{{k,j}}x_{j} & \leq{} & u_{k}^{c}, & k=0,\ldots ,m-1,\\\nonumber{} & l^{x} & \leq{} & x & \leq{} & u^{x}, & j=0,\ldots ,n-1.\end{array}\end{math} (5.3.1)

Without loss of generality it is assumed that [[MathCmd 36]] and [[MathCmd 37]] are all symmetric because

\begin{displaymath}\nonumber{}x^{T}Qx=0.5x^{T}(Q+Q^{T})x.\end{displaymath}

This implies that a non-symmetric Q can be replaced by the symmetric matrix [[MathCmd 39]].

The problem is required to be convex. More precisely, the matrix [[MathCmd 36]] must be positive semi-definite and the kth constraint must be of the form

\begin{math}\nonumber{}l_{k}^{c}\leq{}\frac{1}{2}x^{T}Q^{k}x+\sum \limits _{{j=0}}^{{n-1}}a_{{k,j}}x_{j}\end{math} (5.3.2)

with a negative semi-definite [[MathCmd 37]] or of the form

\begin{math}\nonumber{}\frac{1}{2}x^{T}Q^{k}x+\sum \limits _{{j=0}}^{{n-1}}a_{{k,j}}x_{j}\leq{}u_{k}^{c}.\end{math} (5.3.3)

with a positive semi-definite [[MathCmd 37]]. This implies that quadratic equalities are not allowed. Specifying a non-convex problem will result in an error when the optimizer is called.

5.3.1. Example: Quadratic objective

The following is an example if a quadratic, linearly constrained problem:

\begin{math}\nonumber{}\begin{array}{lcccl}\nonumber{}\mbox{minimize} &  &  & x_{1}^{2}+0.1x_{2}^{2}+x_{3}^{2}-x_{1}x_{3}-x_{2} & \\\nonumber{}\mbox{subject to} & 1 & \leq{} & x_{1}+x_{2}+x_{3} & \\\nonumber{} &  &  & x\geq{}0 &\end{array}\end{math} (5.3.4)

This can be written equivalently as

\begin{math}\nonumber{}\begin{array}{lccl}\nonumber{}\mbox{minimize} & 1/2x^{T}Q^{o}x+c^{T}x &  & \\\nonumber{}\mbox{subject to} & Ax & \geq{} & b\\\nonumber{} & x & \geq{} & 0,\end{array}\end{math} (5.3.5)

where

\begin{math}\nonumber{}Q^{o}=\left[\begin{array}{ccc}\nonumber{}2 & 0 & -1\\\nonumber{}0 & 0.2 & 0\\\nonumber{}-1 & 0 & 2\end{array}\right],\quad{}c=\left[\begin{array}{c}\nonumber{}0\\\nonumber{}-1\\\nonumber{}0\end{array}\right],\quad{}A=\left[\begin{array}{ccc}\nonumber{}1 & 1 & 1\end{array}\right],\mbox{ and }b=1.\end{math} (5.3.6)

Please note that MOSEK always assumes that there is a 1/2 in front of the [[MathCmd 48]] term in the objective. Therefore, the 1 in front of [[MathCmd 49]] becomes 2 in Q, i.e. [[MathCmd 50]].

5.3.1.1. Source code

/* Copyright: Copyright (c) 1998-2011 MOSEK ApS, Denmark. All rights reserved. File: qo1.c Purpose: To demonstrate how to solve a quadratic optimization problem using the MOSEK API. */ #include <stdio.h> #include "mosek.h" /* Include the MOSEK definition file. */ #define NUMCON 1 /* Number of constraints. */ #define NUMVAR 3 /* Number of variables. */ #define NUMANZ 3 /* Number of non-zeros in A. */ #define NUMQNZ 4 /* Number of non-zeros in Q. */ static void MSKAPI printstr(void *handle, char str[]) { printf("%s",str); } /* printstr */ int main(int argc,char *argv[]) { double c[] = {0.0,-1.0,0.0}; MSKboundkeye bkc[] = {MSK_BK_LO}; double blc[] = {1.0}; double buc[] = {+MSK_INFINITY}; 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}; MSKintt aptrb[] = {0, 1, 2 }; MSKintt aptre[] = {1, 2, 3}; MSKidxt asub[] = {0, 0, 0}; double aval[] = {1.0, 1.0, 1.0}; MSKidxt qsubi[NUMQNZ]; MSKidxt qsubj[NUMQNZ]; double qval[NUMQNZ]; MSKidxt i,j; double xx[NUMVAR]; MSKenv_t env; MSKtask_t task; MSKrescodee r; /* Create the mosek environment. */ r = MSK_makeenv(&env,NULL,NULL,NULL,NULL); /* Check whether the return code is ok. */ if ( r==MSK_RES_OK ) { /* Directs the log stream to the 'printstr' function. */ MSK_linkfunctoenvstream(env, MSK_STREAM_LOG, NULL, printstr); } /* Initialize the environment. */ r = MSK_initenv(env); if ( r==MSK_RES_OK ) { /* Create the optimization task. */ r = MSK_maketask(env,NUMCON,NUMVAR,&task); if ( r==MSK_RES_OK ) { r = MSK_linkfunctotaskstream(task,MSK_STREAM_LOG,NULL,printstr); /* Give MOSEK an estimate of the size of the input data. This is done to increase the speed of inputting data. However, it is optional. */ if (r == MSK_RES_OK) r = MSK_putmaxnumvar(task,NUMVAR); if (r == MSK_RES_OK) r = MSK_putmaxnumcon(task,NUMCON); if (r == MSK_RES_OK) r = MSK_putmaxnumanz(task,NUMANZ); /* Append 'NUMCON' empty constraints. The constraints will initially have no bounds. */ if ( r == MSK_RES_OK ) r = MSK_append(task,MSK_ACC_CON,NUMCON); /* Append 'NUMVAR' variables. The variables will initially be fixed at zero (x=0). */ if ( r == MSK_RES_OK ) r = MSK_append(task,MSK_ACC_VAR,NUMVAR); /* Optionally add a constant term to the objective. */ if ( r ==MSK_RES_OK ) r = MSK_putcfix(task,0.0); for(j=0; j<NUMVAR && r == MSK_RES_OK; ++j) { /* Set the linear term c_j in the objective.*/ if(r == MSK_RES_OK) r = MSK_putcj(task,j,c[j]); /* Set the bounds on variable j. blx[j] <= x_j <= bux[j] */ if(r == MSK_RES_OK) r = MSK_putbound(task, MSK_ACC_VAR, /* Put bounds on variables.*/ j, /* Index of variable.*/ bkx[j], /* Bound key.*/ blx[j], /* Numerical value of lower bound.*/ bux[j]); /* Numerical value of upper bound.*/ /* Input column j of A */ if(r == MSK_RES_OK) r = MSK_putavec(task, MSK_ACC_VAR, /* Input columns of A.*/ j, /* Variable (column) index.*/ aptre[j]-aptrb[j], /* Number of non-zeros in column j.*/ asub+aptrb[j], /* Pointer to row indexes of column j.*/ aval+aptrb[j]); /* Pointer to Values of column j.*/ } /* Set the bounds on constraints. for i=1, ...,NUMCON : blc[i] <= constraint i <= buc[i] */ for(i=0; i<NUMCON && r==MSK_RES_OK; ++i) r = MSK_putbound(task, MSK_ACC_CON, /* Put bounds on constraints.*/ i, /* Index of constraint.*/ bkc[i], /* Bound key.*/ blc[i], /* Numerical value of lower bound.*/ buc[i]); /* Numerical value of upper bound.*/ if ( r==MSK_RES_OK ) { /* * The lower triangular part of the Q * matrix in the objective is specified. */ qsubi[0] = 0; qsubj[0] = 0; qval[0] = 2.0; qsubi[1] = 1; qsubj[1] = 1; qval[1] = 0.2; qsubi[2] = 2; qsubj[2] = 0; qval[2] = -1.0; qsubi[3] = 2; qsubj[3] = 2; qval[3] = 2.0; /* Input the Q for the objective. */ r = MSK_putqobj(task,NUMQNZ,qsubi,qsubj,qval); } if ( r==MSK_RES_OK ) { MSKrescodee trmcode; /* Run optimizer */ r = MSK_optimizetrm(task,&trmcode); /* Print a summary containing information about the solution for debugging purposes*/ MSK_solutionsummary (task,MSK_STREAM_LOG); if ( r==MSK_RES_OK ) { MSKsolstae solsta; int j; MSK_getsolutionstatus (task, MSK_SOL_ITR, NULL, &solsta); switch(solsta) { case MSK_SOL_STA_OPTIMAL: case MSK_SOL_STA_NEAR_OPTIMAL: MSK_getsolutionslice(task, MSK_SOL_ITR, /* Request the interior solution. */ MSK_SOL_ITEM_XX,/* Which part of solution. */ 0, /* Index of first variable. */ NUMVAR, /* Index of last variable+1. */ xx); printf("Optimal primal solution\n"); for(j=0; j<NUMVAR; ++j) printf("x[%d]: %e\n",j,xx[j]); break; case MSK_SOL_STA_DUAL_INFEAS_CER: case MSK_SOL_STA_PRIM_INFEAS_CER: case MSK_SOL_STA_NEAR_DUAL_INFEAS_CER: case MSK_SOL_STA_NEAR_PRIM_INFEAS_CER: printf("Primal or dual infeasibility certificate found.\n"); break; case MSK_SOL_STA_UNKNOWN: printf("The status of the solution could not be determined.\n"); break; default: printf("Other solution status."); break; } } else { printf("Error while optimizing.\n"); } } if (r != MSK_RES_OK) { /* In case of an error print error code and description. */ char symname[MSK_MAX_STR_LEN]; char desc[MSK_MAX_STR_LEN]; printf("An error occurred while optimizing.\n"); MSK_getcodedesc (r, symname, desc); printf("Error %s - '%s'\n",symname,desc); } } } MSK_deletetask(&task); MSK_deleteenv(&env); return (r); } /* main */

5.3.1.2. Example code comments

Most of the functionality in this example has already been explained for the linear optimization example in Section 5.2 and it will not be repeated here.

This example introduces one new function, MSK_putqobj, which is used to input the quadratic terms of the objective function.

Since [[MathCmd 36]] is symmetric only the lower triangular part of [[MathCmd 36]] is inputted. The upper part of [[MathCmd 36]] is computed by MOSEK using the relation

\begin{displaymath}\nonumber{}Q^{o}_{{ij}}=Q^{o}_{{ji}}.\end{displaymath}

Entries from the upper part may not appear in the input.

The lower triangular part of the matrix [[MathCmd 36]] is specified using an unordered sparse triplet format (for details, see Section 5.8.3):

qsubi[0] = 0; qsubj[0] = 0; qval[0] = 2.0; qsubi[1] = 1; qsubj[1] = 1; qval[1] = 0.2; qsubi[2] = 2; qsubj[2] = 0; qval[2] = -1.0; qsubi[3] = 2; qsubj[3] = 2; qval[3] = 2.0;

Please note that

  • only non-zero elements are specified (any element not specified is 0 by definition),
  • the order of the non-zero elements is insignificant, and
  • only the lower triangular part should be specified.

Finally, the matrix [[MathCmd 36]] is loaded into the task:

r = MSK_putqobj(task,NUMQNZ,qsubi,qsubj,qval);

5.3.2. Example: Quadratic constraints

In this section describes how to solve a problem with quadratic constraints. Please note that quadratic constraints are subject to the convexity requirement (5.3.2).

Consider the problem:

\begin{math}\nonumber{}\begin{array}{lcccl}\nonumber{}\mbox{minimize} &  &  & x_{1}^{2}+0.1x_{2}^{2}+x_{3}^{2}-x_{1}x_{3}-x_{2} & \\\nonumber{}\mbox{subject to} & 1 & \leq{} & x_{1}+x_{2}+x_{3}-x_{1}^{2}-x_{2}^{2}-0.1x_{3}^{2}+0.2x_{1}x_{3}, & \\\nonumber{} &  &  & x\geq{}0. &\end{array}\end{math} (5.3.7)

This is equivalent to

\begin{math}\nonumber{}\begin{array}{lccl}\nonumber{}\mbox{minimize} & 1/2x^{T}Q^{o}x+c^{T}x &  & \\\nonumber{}\mbox{subject to} & 1/2x^{T}Q^{0}x+Ax & \geq{} & b,\end{array}\end{math} (5.3.8)

where

\begin{math}\nonumber{}Q^{o}=\left[\begin{array}{ccc}\nonumber{}2 & 0 & -1\\\nonumber{}0 & 0.2 & 0\\\nonumber{}-1 & 0 & 2\end{array}\right],\quad{}c=\left[\begin{array}{c}\nonumber{}0\\\nonumber{}-1\\\nonumber{}0\end{array}\right],\quad{}A=\left[\begin{array}{ccc}\nonumber{}1 & 1 & 1\end{array}\right],\quad{}b=1.\end{math} (5.3.9)
\begin{math}\nonumber{}Q^{0}=\left[\begin{array}{ccc}\nonumber{}-2 & 0 & 0.2\\\nonumber{}0 & -2 & 0\\\nonumber{}0.2 & 0 & -0.2\end{array}\right].\end{math} (5.3.10)

5.3.2.1. Source code

/* Copyright: Copyright (c) 1998-2011 MOSEK ApS, Denmark. All rights reserved. File: qcqo1.c Purpose: To demonstrate how to solve a quadratic optimization problem using the MOSEK API. minimize x_1^2 + 0.1 x_2^2 + x_3^2 - x_1 x_3 - x_2 s.t 1 <= x_1 + x_2 + x_3 - x_1^2 - x_2^2 - 0.1 x_3^2 + 0.2 x_1 x_3 x >= 0 */ #include <stdio.h> #include "mosek.h" /* Include the MOSEK definition file. */ #define NUMCON 1 /* Number of constraints. */ #define NUMVAR 3 /* Number of variables. */ #define NUMANZ 3 /* Number of non-zeros in A. */ #define NUMQNZ 4 /* Number of non-zeros in Q. */ static void MSKAPI printstr(void *handle, char str[]) { printf("%s",str); } /* printstr */ int main(int argc,char *argv[]) { MSKrescodee r; double c[] = {0.0,-1.0,0.0}; MSKboundkeye bkc[] = {MSK_BK_LO}; double blc[] = {1.0}; double buc[] = {+MSK_INFINITY}; 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}; MSKlidxt aptrb[] = {0, 1, 2 }; MSKlidxt aptre[] = {1, 2, 3}; MSKidxt asub[] = { 0, 0, 0}; double aval[] = { 1.0, 1.0, 1.0}; MSKidxt qsubi[NUMQNZ]; MSKidxt qsubj[NUMQNZ]; double qval[NUMQNZ]; MSKidxt j,i; double xx[NUMVAR]; MSKenv_t env; MSKtask_t task; /* Create the mosek environment. */ r = MSK_makeenv(&env,NULL,NULL,NULL,NULL); /* Check whether the return code is ok. */ if ( r==MSK_RES_OK ) { /* Directs the log stream to the 'printstr' function. */ MSK_linkfunctoenvstream(env,MSK_STREAM_LOG,NULL,printstr); } /* Initialize the environment. */ r = MSK_initenv(env); if ( r==MSK_RES_OK ) { /* Create the optimization task. */ r = MSK_maketask(env,NUMCON,NUMVAR,&task); if ( r==MSK_RES_OK ) { r = MSK_linkfunctotaskstream(task,MSK_STREAM_LOG,NULL,printstr); /* Give MOSEK an estimate of the size of the input data. This is done to increase the speed of inputting data. However, it is optional. */ if (r == MSK_RES_OK) r = MSK_putmaxnumvar(task,NUMVAR); if (r == MSK_RES_OK) r = MSK_putmaxnumcon(task,NUMCON); if (r == MSK_RES_OK) r = MSK_putmaxnumanz(task,NUMANZ); /* Append 'NUMCON' empty constraints. The constraints will initially have no bounds. */ if ( r == MSK_RES_OK ) r = MSK_append(task,MSK_ACC_CON,NUMCON); /* Append 'NUMVAR' variables. The variables will initially be fixed at zero (x=0). */ if ( r == MSK_RES_OK ) r = MSK_append(task,MSK_ACC_VAR,NUMVAR); /* Optionally add a constant term to the objective. */ if ( r ==MSK_RES_OK ) r = MSK_putcfix(task,0.0); for(j=0; j<NUMVAR && r == MSK_RES_OK; ++j) { /* Set the linear term c_j in the objective.*/ if(r == MSK_RES_OK) r = MSK_putcj(task,j,c[j]); /* Set the bounds on variable j. blx[j] <= x_j <= bux[j] */ if(r == MSK_RES_OK) r = MSK_putbound(task, MSK_ACC_VAR, /* Put bounds on variables.*/ j, /* Index of variable.*/ bkx[j], /* Bound key.*/ blx[j], /* Numerical value of lower bound.*/ bux[j]); /* Numerical value of upper bound.*/ /* Input column j of A */ if(r == MSK_RES_OK) r = MSK_putavec(task, MSK_ACC_VAR, /* Input columns of A.*/ j, /* Variable (column) index.*/ aptre[j]-aptrb[j], /* Number of non-zeros in column j.*/ asub+aptrb[j], /* Pointer to row indexes of column j.*/ aval+aptrb[j]); /* Pointer to Values of column j.*/ } /* Set the bounds on constraints. for i=1, ...,NUMCON : blc[i] <= constraint i <= buc[i] */ for(i=0; i<NUMCON && r==MSK_RES_OK; ++i) r = MSK_putbound(task, MSK_ACC_CON, /* Put bounds on constraints.*/ i, /* Index of constraint.*/ bkc[i], /* Bound key.*/ blc[i], /* Numerical value of lower bound.*/ buc[i]); /* Numerical value of upper bound.*/ if ( r==MSK_RES_OK ) { /* * The lower triangular part of the Q^o * matrix in the objective is specified. */ qsubi[0] = 0; qsubj[0] = 0; qval[0] = 2.0; qsubi[1] = 1; qsubj[1] = 1; qval[1] = 0.2; qsubi[2] = 2; qsubj[2] = 0; qval[2] = -1.0; qsubi[3] = 2; qsubj[3] = 2; qval[3] = 2.0; /* Input the Q^o for the objective. */ r = MSK_putqobj(task,NUMQNZ,qsubi,qsubj,qval); } if ( r==MSK_RES_OK ) { /* * The lower triangular part of the Q^0 * matrix in the first constraint is specified. This corresponds to adding the term - x_1^2 - x_2^2 - 0.1 x_3^2 + 0.2 x_1 x_3 */ qsubi[0] = 0; qsubj[0] = 0; qval[0] = -2.0; qsubi[1] = 1; qsubj[1] = 1; qval[1] = -2.0; qsubi[2] = 2; qsubj[2] = 2; qval[2] = -0.2; qsubi[3] = 2; qsubj[3] = 0; qval[3] = 0.2; /* Put Q^0 in constraint with index 0. */ r = MSK_putqconk(task, 0, 4, qsubi, qsubj, qval); } if ( r==MSK_RES_OK ) r = MSK_putobjsense(task, MSK_OBJECTIVE_SENSE_MINIMIZE); if ( r==MSK_RES_OK ) { MSKrescodee trmcode; /* Run optimizer */ r = MSK_optimizetrm(task,&trmcode); /* Print a summary containing information about the solution for debugging purposes*/ MSK_solutionsummary (task,MSK_STREAM_LOG); if ( r==MSK_RES_OK ) { MSKsolstae solsta; int j; MSK_getsolutionstatus (task, MSK_SOL_ITR, NULL, &solsta); switch(solsta) { case MSK_SOL_STA_OPTIMAL: case MSK_SOL_STA_NEAR_OPTIMAL: MSK_getsolutionslice(task, MSK_SOL_ITR, /* Request the interior solution. */ MSK_SOL_ITEM_XX,/* Which part of solution. */ 0, /* Index of first variable. */ NUMVAR, /* Index of last variable+1. */ xx); printf("Optimal primal solution\n"); for(j=0; j<NUMVAR; ++j) printf("x[%d]: %e\n",j,xx[j]); break; case MSK_SOL_STA_DUAL_INFEAS_CER: case MSK_SOL_STA_PRIM_INFEAS_CER: case MSK_SOL_STA_NEAR_DUAL_INFEAS_CER: case MSK_SOL_STA_NEAR_PRIM_INFEAS_CER: printf("Primal or dual infeasibility certificate found.\n"); break; case MSK_SOL_STA_UNKNOWN: printf("The status of the solution could not be determined.\n"); break; default: printf("Other solution status."); break; } } else { printf("Error while optimizing.\n"); } } if (r != MSK_RES_OK) { /* In case of an error print error code and description. */ char symname[MSK_MAX_STR_LEN]; char desc[MSK_MAX_STR_LEN]; printf("An error occurred while optimizing.\n"); MSK_getcodedesc (r, symname, desc); printf("Error %s - '%s'\n",symname,desc); } } MSK_deletetask(&task); } MSK_deleteenv(&env); return ( r ); } /* main */

The only new function introduced in this example is MSK_putqconk, which is used to add quadratic terms to the constraints. While MSK_putqconk add quadratic terms to a specific constraint, it is also possible to input all quadratic terms in all constraints in one chunk using the MSK_putqcon function.

5.4. Conic optimization

Conic problems are a generalization of linear problems, allowing constraints of the type

\begin{displaymath}\nonumber{}x\in{}\mathcal{C}\end{displaymath}

where [[MathCmd 62]] is a convex cone.

MOSEK can solve conic optimization problems of the following form

\begin{math}\nonumber{}\begin{array}{lccccl}\nonumber{}\mbox{minimize} &  &  & c^{T}x+c^{f} &  & \\\nonumber{}\mbox{subject to} & l^{c} & \leq{} & Ax & \leq{} & u^{c},\\\nonumber{} & l^{x} & \leq{} & x & \leq{} & u^{x},\\\nonumber{} &  &  & x\in{}\mathcal{C} &  &\end{array}\end{math} (5.4.1)

where [[MathCmd 62]] is a cone. [[MathCmd 62]] can be a product of cones, i.e.

\begin{displaymath}\nonumber{}\mathcal{C}=\mathcal{C}_{0}\times \cdots \times \mathcal{C}_{{p-1}}\end{displaymath}

in which case [[MathCmd 67]] means [[MathCmd 68]]. Please note that the set of real numbers [[MathCmd 69]] is itself a cone, so linear variables are still allowed.

MOSEK supports two specific cones apart from the real numbers:

When creating a conic problem in MOSEK, each cone is defined by a cone type (quadratic or rotated quadratic cone) and a list of variable indexes. To summarize:

5.4.1. Example: cqo1

The problem

\begin{math}\nonumber{}\begin{array}{lccccc}\nonumber{}\mbox{minimize} & x_{4}+x_{5} &  & \\\nonumber{}\mbox{subject to} & x_{0}+x_{1}+x_{2}+x_{3} & = & 1,\\\nonumber{} & x_{0},x_{1},x_{2},x_{3} & \geq{} & 0,\\\nonumber{} & x_{4}\geq{}\sqrt{x_{0}^{2} + x_{2}^{2}}, &  & \\\nonumber{} & x_{5}\geq{}\sqrt{x_{1}^{2} + x_{3}^{2}} &  &\end{array}\end{math} (5.4.2)

is an example of a conic quadratic optimization problem. The problem includes a set of linear constraints and two quadratic cones.

5.4.1.1. Source code

/* Copyright: Copyright (c) 1998-2011 MOSEK ApS, Denmark. All rights reserved. File: cqo1.c Purpose: To demonstrate how to solve a small conic quadratic optimization problem using the MOSEK API. */ #include <stdio.h> #include "mosek.h" /* Include the MOSEK definition file. */ #define NUMCON 1 /* Number of constraints. */ #define NUMVAR 6 /* Number of variables. */ #define NUMANZ 4 /* Number of non-zeros in A. */ static void MSKAPI printstr(void *handle, char str[]) { printf("%s",str); } /* printstr */ int main(int argc,char *argv[]) { MSKrescodee r; MSKboundkeye bkc[] = { MSK_BK_FX }; double blc[] = { 1.0 }; double buc[] = { 1.0 }; MSKboundkeye bkx[] = {MSK_BK_LO, MSK_BK_LO, MSK_BK_LO, MSK_BK_LO, MSK_BK_FR, MSK_BK_FR}; double blx[] = {0.0, 0.0, 0.0, 0.0, -MSK_INFINITY, -MSK_INFINITY}; double bux[] = {+MSK_INFINITY, +MSK_INFINITY, +MSK_INFINITY, +MSK_INFINITY, +MSK_INFINITY, +MSK_INFINITY}; double c[] = {0.0, 0.0, 0.0, 0.0, 1.0, 1.0}; MSKintt aptrb[] = {0, 1, 2, 3, 5, 5}; MSKintt aptre[] = {1, 2, 3, 4, 5, 5}; double aval[] = {1.0, 1.0, 1.0, 1.0}; MSKidxt asub[] = {0, 0, 0, 0}; MSKidxt i,j,csub[3]; double xx[NUMVAR]; MSKenv_t env; MSKtask_t task; /* Create the mosek environment. */ r = MSK_makeenv(&env,NULL,NULL,NULL,NULL); /* Check if return code is ok. */ if ( r==MSK_RES_OK ) { /* Directs the log stream to the 'printstr' function. */ MSK_linkfunctoenvstream(env,MSK_STREAM_LOG,NULL,printstr); } /* Initialize the environment. */ if ( r==MSK_RES_OK ) r = MSK_initenv(env); if ( r==MSK_RES_OK ) { /* Create the optimization task. */ r = MSK_maketask(env,NUMCON,NUMVAR,&task); if ( r==MSK_RES_OK ) { MSK_linkfunctotaskstream(task,MSK_STREAM_LOG,NULL,printstr); /* Give MOSEK an estimate of the size of the input data. This is done to increase the speed of inputting data. However, it is optional. */ if (r == MSK_RES_OK) r = MSK_putmaxnumvar(task,NUMVAR); if (r == MSK_RES_OK) r = MSK_putmaxnumcon(task,NUMCON); if (r == MSK_RES_OK) r = MSK_putmaxnumanz(task,NUMANZ); /* Append 'NUMCON' empty constraints. The constraints will initially have no bounds. */ if ( r == MSK_RES_OK ) r = MSK_append(task,MSK_ACC_CON,NUMCON); /* Append 'NUMVAR' variables. The variables will initially be fixed at zero (x=0). */ if ( r == MSK_RES_OK ) r = MSK_append(task,MSK_ACC_VAR,NUMVAR); /* Optionally add a constant term to the objective. */ if ( r ==MSK_RES_OK ) r = MSK_putcfix(task,0.0); for(j=0; j<NUMVAR && r == MSK_RES_OK; ++j) { /* Set the linear term c_j in the objective.*/ if(r == MSK_RES_OK) r = MSK_putcj(task,j,c[j]); /* Set the bounds on variable j. blx[j] <= x_j <= bux[j] */ if(r == MSK_RES_OK) r = MSK_putbound(task, MSK_ACC_VAR, /* Put bounds on variables.*/ j, /* Index of variable.*/ bkx[j], /* Bound key.*/ blx[j], /* Numerical value of lower bound.*/ bux[j]); /* Numerical value of upper bound.*/ /* Input column j of A */ if(r == MSK_RES_OK) r = MSK_putavec(task, MSK_ACC_VAR, /* Input columns of A.*/ j, /* Variable (column) index.*/ aptre[j]-aptrb[j], /* Number of non-zeros in column j.*/ asub+aptrb[j], /* Pointer to row indexes of column j.*/ aval+aptrb[j]); /* Pointer to Values of column j.*/ } /* Set the bounds on constraints. for i=1, ...,NUMCON : blc[i] <= constraint i <= buc[i] */ for(i=0; i<NUMCON && r==MSK_RES_OK; ++i) r = MSK_putbound(task, MSK_ACC_CON, /* Put bounds on constraints.*/ i, /* Index of constraint.*/ bkc[i], /* Bound key.*/ blc[i], /* Numerical value of lower bound.*/ buc[i]); /* Numerical value of upper bound.*/ if ( r==MSK_RES_OK ) { /* Append the first cone. */ csub[0] = 4; csub[1] = 0; csub[2] = 2; r = MSK_appendcone(task, MSK_CT_QUAD, 0.0, /* For future use only, can be set to 0.0 */ 3, csub); } if ( r==MSK_RES_OK ) { /* Append the second cone. */ csub[0] = 5; csub[1] = 1; csub[2] = 3; r = MSK_appendcone(task, MSK_CT_QUAD, 0.0, 3, csub); } if ( r==MSK_RES_OK ) { MSKrescodee trmcode; /* Run optimizer */ r = MSK_optimizetrm(task,&trmcode); /* Print a summary containing information about the solution for debugging purposes*/ MSK_solutionsummary (task,MSK_STREAM_LOG); if ( r==MSK_RES_OK ) { MSKsolstae solsta; MSKidxt j; MSK_getsolutionstatus (task, MSK_SOL_ITR, NULL, &solsta); switch(solsta) { case MSK_SOL_STA_OPTIMAL: case MSK_SOL_STA_NEAR_OPTIMAL: MSK_getsolutionslice(task, MSK_SOL_ITR, /* Request the interior solution. */ MSK_SOL_ITEM_XX,/* Which part of solution. */ 0, /* Index of first variable. */ NUMVAR, /* Index of last variable+1. */ xx); printf("Optimal primal solution\n"); for(j=0; j<NUMVAR; ++j) printf("x[%d]: %e\n",j,xx[j]); break; case MSK_SOL_STA_DUAL_INFEAS_CER: case MSK_SOL_STA_PRIM_INFEAS_CER: case MSK_SOL_STA_NEAR_DUAL_INFEAS_CER: case MSK_SOL_STA_NEAR_PRIM_INFEAS_CER: printf("Primal or dual infeasibility certificate found.\n"); break; case MSK_SOL_STA_UNKNOWN: printf("The status of the solution could not be determined.\n"); break; default: printf("Other solution status."); break; } } else { printf("Error while optimizing.\n"); } } if (r != MSK_RES_OK) { /* In case of an error print error code and description. */ char symname[MSK_MAX_STR_LEN]; char desc[MSK_MAX_STR_LEN]; printf("An error occurred while optimizing.\n"); MSK_getcodedesc (r, symname, desc); printf("Error %s - '%s'\n",symname,desc); } } /* Delete the task and the associated data. */ MSK_deletetask(&task); } /* Delete the environment and the associated data. */ MSK_deleteenv(&env); return ( r ); } /* main */

5.4.1.2. Source code comments

The only new function introduced in the example is MSK_appendcone, which is called here:

r = MSK_appendcone(task, MSK_CT_QUAD, 0.0, /* For future use only, can be set to 0.0 */ 3, csub);

Here MSK_CT_QUAD defines the cone type, in this case it is a quadratic cone. The cone parameter 0.0 is currently not used by MOSEK — simply passing 0.0 will work.

The next argument denotes the number of variables in the cone, in this case 3, and the last argument is a list of indexes of the variables in the cone.

5.5. Integer optimization

An optimization problem where one or more of the variables are constrained to integer values is denoted an integer optimization problem.

5.5.1. Example: milo1

In this section the example

\begin{math}\nonumber{}\begin{array}{lccl}\nonumber{}\mbox{maximize} & x_{0}+0.64x_{1} &  & \\\nonumber{}\mbox{subject to} & 50x_{0}+31x_{1} & \leq{} & 250,\\\nonumber{} & 3x_{0}-2x_{1} & \geq{} & -4,\\\nonumber{} & x_{0},x_{1}\geq{}0 &  & \mbox{and integer}\end{array}\end{math} (5.5.1)

is used to demonstrate how to solve a problem with integer variables.

5.5.1.1. Source code

The example (5.5.1) is almost identical to a linear optimization problem except for some variables being integer constrained. Therefore, only the specification of the integer constraints requires something new compared to the linear optimization problem discussed previously. In MOSEK these constraints are specified using the function MSK_putvartype as shown in the code:

for(j=0; j<NUMVAR && r == MSK_RES_OK; ++j) r = MSK_putvartype(task,j,MSK_VAR_TYPE_INT);

The complete source for the example is listed below.

/* Copyright: Copyright (c) 1998-2011 MOSEK ApS, Denmark. All rights reserved. File: milo1.c Purpose: To demonstrate how to solve a small mixed integer linear optimization problem using the MOSEK API. */ #include <stdio.h> #include "mosek.h" /* Include the MOSEK definition file. */ #define NUMCON 2 /* Number of constraints. */ #define NUMVAR 2 /* Number of variables. */ #define NUMANZ 4 /* Number of non-zeros in A. */ static void MSKAPI printstr(void *handle, char str[]) { printf("%s",str); } /* printstr */ int main(int argc,char *argv[]) { MSKrescodee r; double c[] = { 1.0, 0.64 }; MSKboundkeye bkc[] = { MSK_BK_UP, MSK_BK_LO }; double blc[] = { -MSK_INFINITY,-4.0 }; double buc[] = { 250.0, MSK_INFINITY }; MSKboundkeye bkx[] = { MSK_BK_LO, MSK_BK_LO }; double blx[] = { 0.0, 0.0 }; double bux[] = { MSK_INFINITY, MSK_INFINITY }; MSKintt aptrb[] = { 0, 2 }; MSKintt aptre[] = { 2, 4 }; MSKidxt asub[] = { 0, 1, 0, 1 }; double aval[] = { 50.0, 3.0, 31.0, -2.0 }; MSKidxt i,j; double xx[NUMVAR]; MSKenv_t env; MSKtask_t task; /* Create the mosek environment. */ r = MSK_makeenv(&env,NULL,NULL,NULL,NULL); /* Initialize the environment. */ if ( r==MSK_RES_OK ) r = MSK_initenv(env); /* Check if return code is ok. */ if ( r==MSK_RES_OK ) { /* Directs the log stream to the 'printstr' function. */ MSK_linkfunctoenvstream(env,MSK_STREAM_LOG,NULL,printstr); /* Create the optimization task. */ r = MSK_maketask(env,NUMCON,NUMVAR,&task); if ( r==MSK_RES_OK ) r = MSK_linkfunctotaskstream(task,MSK_STREAM_LOG,NULL,printstr); /* Give MOSEK an estimate of the size of the input data. This is done to increase the speed of inputting data. However, it is optional. */ if (r == MSK_RES_OK) r = MSK_putmaxnumvar(task,NUMVAR); if (r == MSK_RES_OK) r = MSK_putmaxnumcon(task,NUMCON); if (r == MSK_RES_OK) r = MSK_putmaxnumanz(task,NUMANZ); /* Append 'NUMCON' empty constraints. The constraints will initially have no bounds. */ if ( r == MSK_RES_OK ) r = MSK_append(task,MSK_ACC_CON,NUMCON); /* Append 'NUMVAR' variables. The variables will initially be fixed at zero (x=0). */ if ( r == MSK_RES_OK ) r = MSK_append(task,MSK_ACC_VAR,NUMVAR); /* Optionally add a constant term to the objective. */ if ( r ==MSK_RES_OK ) r = MSK_putcfix(task,0.0); for(j=0; j<NUMVAR && r == MSK_RES_OK; ++j) { /* Set the linear term c_j in the objective.*/ if(r == MSK_RES_OK) r = MSK_putcj(task,j,c[j]); /* Set the bounds on variable j. blx[j] <= x_j <= bux[j] */ if(r == MSK_RES_OK) r = MSK_putbound(task, MSK_ACC_VAR, /* Put bounds on variables.*/ j, /* Index of variable.*/ bkx[j], /* Bound key.*/ blx[j], /* Numerical value of lower bound.*/ bux[j]); /* Numerical value of upper bound.*/ /* Input column j of A */ if(r == MSK_RES_OK) r = MSK_putavec(task, MSK_ACC_VAR, /* Input columns of A.*/ j, /* Variable (column) index.*/ aptre[j]-aptrb[j], /* Number of non-zeros in column j.*/ asub+aptrb[j], /* Pointer to row indexes of column j.*/ aval+aptrb[j]); /* Pointer to Values of column j.*/ } /* Set the bounds on constraints. for i=1, ...,NUMCON : blc[i] <= constraint i <= buc[i] */ for(i=0; i<NUMCON && r==MSK_RES_OK; ++i) r = MSK_putbound(task, MSK_ACC_CON, /* Put bounds on constraints.*/ i, /* Index of constraint.*/ bkc[i], /* Bound key.*/ blc[i], /* Numerical value of lower bound.*/ buc[i]); /* Numerical value of upper bound.*/ /* Specify integer variables. */ for(j=0; j<NUMVAR && r == MSK_RES_OK; ++j) r = MSK_putvartype(task,j,MSK_VAR_TYPE_INT); if ( r==MSK_RES_OK ) r = MSK_putobjsense(task, MSK_OBJECTIVE_SENSE_MAXIMIZE); if ( r==MSK_RES_OK ) { MSKrescodee trmcode; /* Run optimizer */ r = MSK_optimizetrm(task,&trmcode); /* Print a summary containing information about the solution for debugging purposes*/ MSK_solutionsummary (task,MSK_STREAM_LOG); if ( r==MSK_RES_OK ) { MSKsolstae solsta; int j; MSK_getsolutionstatus (task, MSK_SOL_ITG, NULL, &solsta); switch(solsta) { case MSK_SOL_STA_INTEGER_OPTIMAL: case MSK_SOL_STA_NEAR_INTEGER_OPTIMAL : MSK_getsolutionslice(task, MSK_SOL_ITG, /* Request the integer */ MSK_SOL_ITEM_XX,/* Which part of solution. */ 0, /* Index of first variable. */ NUMVAR, /* Index of last variable+1. */ xx); printf("Optimal solution.\n"); for(j=0; j<NUMVAR; ++j) printf("x[%d]: %e\n",j,xx[j]); break; case MSK_SOL_STA_PRIM_FEAS: /* A feasible but not necessarily optimal solution was located. */ MSK_getsolutionslice(task, MSK_SOL_ITG, /* Request the integer.*/ MSK_SOL_ITEM_XX,/* Which part of solution. */ 0, /* Index of first variable. */ NUMVAR, /* Index of last variable+1. */ xx); printf("Feasible solution.\n"); for(j=0; j<NUMVAR; ++j) printf("x[%d]: %e\n",j,xx[j]); break; case MSK_SOL_STA_UNKNOWN: printf("The status of the solution could not be determined.\n"); break; default: printf("Other solution status."); break; } } else { printf("Error while optimizing.\n"); } } if (r != MSK_RES_OK) { /* In case of an error print error code and description. */ char symname[MSK_MAX_STR_LEN]; char desc[MSK_MAX_STR_LEN]; printf("An error occurred while optimizing.\n"); MSK_getcodedesc (r, symname, desc); printf("Error %s - '%s'\n",symname,desc); } } MSK_deletetask(&task); MSK_deleteenv(&env); printf("Return code: %d.\n",r); return ( r ); } /* main */

5.5.1.2. Code comments

Please note that when MSK_getsolutionslice is called, the integer solution is requested by using MSK_SOL_ITG. No dual solution is defined for integer optimization problems.

5.5.2. Specifying an initial solution

Integer optimization problems are generally hard to solve, but the solution time can often be reduced by providing an initial solution for the solver. Solution values can be set using MSK_putsolution (for inputting a whole solution) or MSK_putsolutioni (for inputting solution values related to a single variable or constraint).

It is not necessary to specify the whole solution. By setting the MSK_IPAR_MIO_CONSTRUCT_SOL parameter to MSK_ON and inputting values for the integer variables only, will force MOSEK to compute the remaining continuous variable values.

If the specified integer solution is infeasible or incomplete, MOSEK will simply ignore it.

5.5.3. Example: Specifying an integer solution

Consider the problem

\begin{math}\nonumber{}\begin{array}{ll}\nonumber{}\mbox{maximize} & 7x_{0}+10x_{1}+x_{2}+5x_{3}\\\nonumber{}\mbox{subject to} & x_{0}+x_{1}+x_{2}+x_{3}\leq{}2.5\\\nonumber{} & x_{0},x_{1},x_{2}\mathrm{integer},\quad{}x_{0},x_{1},x_{2},x_{3}\geq{}0\end{array}\end{math} (5.5.2)

The following example demonstrates how to optimize the problem using a feasible starting solution generated by selecting the integer values as [[MathCmd 76]].

/* Copyright: Copyright (c) 1998-2011 MOSEK ApS, Denmark. All rights reserved. File: mioinitsol.c Purpose: To demonstrate how to solve a MIP with a start guess. */ #include "mosek.h" #include <stdio.h> static void MSKAPI printstr(void *handle, char str[]) { printf("%s",str); } /* printstr */ #define NUMVAR 4 #define NUMCON 1 #define NUMINTVAR 3 int main(int argc,char *argv[]) { char buffer[512]; MSKrescodee r; MSKenv_t env; MSKtask_t task; double c[] = { 7.0, 10.0, 1.0, 5.0 }; MSKboundkeye bkc[] = {MSK_BK_UP}; double blc[] = {-MSK_INFINITY}; double buc[] = {2.5}; MSKboundkeye bkx[] = {MSK_BK_LO, MSK_BK_LO, MSK_BK_LO,MSK_BK_LO}; double blx[] = {0.0, 0.0, 0.0, 0.0 }; double bux[] = {MSK_INFINITY,MSK_INFINITY,MSK_INFINITY,MSK_INFINITY}; MSKlidxt ptrb[] = {0,1,2,3}; MSKlidxt ptre[] = {1,2,3,4}; double aval[] = {1.0, 1.0, 1.0, 1.0}; MSKidxt asub[] = {0, 0, 0, 0 }; MSKidxt intsub[] = {0,1,2}; MSKidxt j; r = MSK_makeenv(&env,NULL,NULL,NULL,NULL); if ( r==MSK_RES_OK ) { MSK_linkfunctoenvstream(env,MSK_STREAM_LOG,NULL,printstr); } r = MSK_initenv(env); if ( r==MSK_RES_OK ) r = MSK_maketask(env,0,0,&task); if ( r==MSK_RES_OK ) MSK_linkfunctotaskstream(task,MSK_STREAM_LOG,NULL,printstr); if (r == MSK_RES_OK) r = MSK_inputdata(task, NUMCON,NUMVAR, NUMCON,NUMVAR, c, 0.0, ptrb, ptre, asub, aval, bkc, blc, buc, bkx, blx, bux); if (r == MSK_RES_OK) MSK_putobjsense(task,MSK_OBJECTIVE_SENSE_MAXIMIZE); for(j=0; j<NUMINTVAR && r == MSK_RES_OK; ++j) r = MSK_putvartype(task,intsub[j],MSK_VAR_TYPE_INT); /* Construct an initial feasible solution from the values of the integer variables specified */ if (r == MSK_RES_OK) r = MSK_putintparam(task,MSK_IPAR_MIO_CONSTRUCT_SOL,MSK_ON); /* Set status of all variables to unknown */ if (r == MSK_RES_OK) r = MSK_makesolutionstatusunknown(task, MSK_SOL_ITG); /* Assign values 1,1,0 to integer variables */ if (r == MSK_RES_OK) r = MSK_putsolutioni ( task, MSK_ACC_VAR, 0, MSK_SOL_ITG, MSK_SK_SUPBAS, 0.0, 0.0, 0.0, 0.0); if (r == MSK_RES_OK) r = MSK_putsolutioni ( task, MSK_ACC_VAR, 1, MSK_SOL_ITG, MSK_SK_SUPBAS, 2.0, 0.0, 0.0, 0.0); if (r == MSK_RES_OK) r = MSK_putsolutioni ( task, MSK_ACC_VAR, 2, MSK_SOL_ITG, MSK_SK_SUPBAS, 0.0, 0.0, 0.0, 0.0); /* solve */ if (r == MSK_RES_OK) r = MSK_optimize(task); /* Did mosek construct a feasible initial solution ? */ { int isok; if (r == MSK_RES_OK) r = MSK_getintinf(task,MSK_IINF_MIO_CONSTRUCT_SOLUTION,&isok); if ( isok>0 && r == MSK_RES_OK) printf("MOSEK constructed a feasible initial soulution.\n"); } /* Delete the task. */ MSK_deletetask(&task); MSK_deleteenv(&env); printf("Return code: %d\n",r); if ( r!=MSK_RES_OK ) { MSK_getcodedisc(r,buffer,NULL); printf("Description: %s\n",buffer); } return (r); }

5.6. Problem modification and reoptimization

Often one might want to solve not just a single optimization problem, but a sequence of problem, each differing only slightly from the previous one. This section demonstrates how to modify and reoptimize an existing problem. The example we study is a simple production planning model.

5.6.1. A production planning problem

A company manufactures three types of products. Suppose the stages of manufacturing can be split into three parts, namely 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.

Now the question is 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 [[MathCmd 77]] and [[MathCmd 78]], this problem can be formulated as the linear optimization problem:

\begin{math}\nonumber{}\begin{array}{lccccccl}\nonumber{}\mbox{maximize} & 1.5x_{0} & + & 2.5x_{1} & + & 3.0x_{2} &  & \\\nonumber{}\mbox{subject to} & 2x_{0} & + & 4x_{1} & + & 3x_{2} & \leq{} & 100000,\\\nonumber{} & 3x_{0} & + & 2x_{1} & + & 3x_{2} & \leq{} & 50000,\\\nonumber{} & 2x_{0} & + & 3x_{1} & + & 2x_{2} & \leq{} & 60000,\end{array}\end{math} (5.6.1)

and

\begin{math}\nonumber{}x_{0},x_{1},x_{2}\geq{}0.\end{math} (5.6.2)

The following code loads this problem into the optimization task.

MSKrescodee r; MSKidxt i,j; double c[] = {1.5, 2.5, 3.0}; MSKlidxt ptrb[] = {0, 3, 6}; MSKlidxt ptre[] = {3, 6, 9}; MSKidxt 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[NUMVAR]; MSKenv_t env; MSKtask_t task; MSKintt numvar,numcon; /* Create the mosek environment. */ r = MSK_makeenv(&env,NULL,NULL,NULL,NULL); /* Check if return code is ok. */ if ( r==MSK_RES_OK ) { /* Directs the env log stream to the 'printstr' function. */ MSK_linkfunctoenvstream(env,MSK_STREAM_LOG,NULL,printstr); } /* Initialize the environment. */ r = MSK_initenv(env); if ( r==MSK_RES_OK ) { /* Create the optimization task. */ r = MSK_maketask(env,NUMCON,NUMVAR,&task); /* Directs the log task stream to the 'printstr' function. */ MSK_linkfunctotaskstream(task,MSK_STREAM_LOG,NULL,printstr); /* Give MOSEK an estimate of the size of the input data. This is done to increase the efficiency of inputting data, however it is optional.*/ if (r == MSK_RES_OK) r = MSK_putmaxnumvar(task,NUMVAR); if (r == MSK_RES_OK) r = MSK_putmaxnumcon(task,NUMCON); if (r == MSK_RES_OK) r = MSK_putmaxnumanz(task,NUMANZ); /* Append the constraints. */ if (r == MSK_RES_OK) r = MSK_append(task,MSK_ACC_CON,NUMCON); /* Append the variables. */ if (r == MSK_RES_OK) r = MSK_append(task,MSK_ACC_VAR,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_putbound(task,MSK_ACC_CON,i,bkc[i],blc[i],buc[i]); /* Put variable bounds. */ if (r == MSK_RES_OK) for(j=0; j<NUMVAR; ++j) r = MSK_putbound(task,MSK_ACC_VAR,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_putavec(task, MSK_ACC_VAR, 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) MSK_getsolutionslice(task, MSK_SOL_BAS, /* Basic solution. */ MSK_SOL_ITEM_XX, /* Which part of solution. */ 0, /* Index of first variable. */ NUMVAR, /* Index of last variable+1 */ xx);

5.6.2. Changing the A matrix

Suppose we want to change the time required for assembly of product 0 to 3 minutes. This corresponds to setting [[MathCmd 81]], 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:

\begin{math}\nonumber{}\begin{array}{lccccccl}\nonumber{}\mbox{maximize} & 1.5x_{0} & + & 2.5x_{1} & + & 3.0x_{2} &  & \\\nonumber{}\mbox{subject to} & 3x_{0} & + & 4x_{1} & + & 3x_{2} & \leq{} & 100000,\\\nonumber{} & 3x_{0} & + & 2x_{1} & + & 3x_{2} & \leq{} & 50000,\\\nonumber{} & 2x_{0} & + & 3x_{1} & + & 2x_{2} & \leq{} & 60000,\end{array}\end{math} (5.6.3)

and

\begin{math}\nonumber{}x_{0},x_{1},x_{2}\geq{}0.\end{math} (5.6.4)

After changing the A matrix we can find the new optimal solution by calling

MSK_optimize

again

5.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 [[MathCmd 84]], appending a new column to the A matrix and setting a new value in the objective. We do this in the following code.

/* Append a new variable x_3 to the problem */ if (r == MSK_RES_OK) r = MSK_append(task,MSK_ACC_VAR,1); /* Get index of new variable, this should be 3 */ if (r == MSK_RES_OK) r = MSK_getnumvar(task,&numvar); /* Set bounds on new variable */ if (r == MSK_RES_OK) r = MSK_putbound(task, MSK_ACC_VAR, numvar-1, MSK_BK_LO, 0, +MSK_INFINITY); /* Change objective */ if (r == MSK_RES_OK) r = MSK_putcj(task,numvar-1,1.0); /* Put new values in the A matrix */ if (r == MSK_RES_OK) { MSKidxt acolsub[] = {0, 2}; double acolval[] = {4.0, 1.0}; r = MSK_putavec(task, MSK_ACC_VAR, numvar-1, /* column index */ 2, /* num nz in column*/ acolsub, acolval); }

After this operation the problem looks this way:

\begin{math}\nonumber{}\begin{array}{lccccccccl}\nonumber{}\mbox{maximize} & 1.5x_{0} & + & 2.5x_{1} & + & 3.0x_{2} & + & 1.0x_{3} &  & \\\nonumber{}\mbox{subject to} & 3x_{0} & + & 4x_{1} & + & 3x_{2} & + & 4x_{3} & \leq{} & 100000,\\\nonumber{} & 3x_{0} & + & 2x_{1} & + & 3x_{2} &  &  & \leq{} & 50000,\\\nonumber{} & 2x_{0} & + & 3x_{1} & + & 2x_{2} & + & 1x_{3} & \leq{} & 60000,\end{array}\end{math} (5.6.5)

and

\begin{math}\nonumber{}x_{0},x_{1},x_{2},x_{3}\geq{}0.\end{math} (5.6.6)

5.6.4. Reoptimization

When

MSK_optimize

is called MOSEK will store the optimal solution internally. After a task has been modified and

MSK_optimize

is called again the solution will automatically be used to reduce solution time of the new problem, if possible.

In this case an optimal solution to problem (5.6.3) was found and then added a column was added to get (5.6.5). The simplex optimizer is well suited for exploiting an existing primal or dual feasible solution. Hence, the subsequent code instructs MOSEK to choose the simplex optimizer freely when optimizing.

/* Change optimizer to free simplex and reoptimize */ if (r == MSK_RES_OK) r = MSK_putintparam(task,MSK_IPAR_OPTIMIZER,MSK_OPTIMIZER_FREE_SIMPLEX); if (r == MSK_RES_OK) r = MSK_optimizetrm(task,NULL);

5.6.5. Appending constraints

Now suppose we want to add a new stage to the production 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

\begin{math}\nonumber{}x_{0}+2x_{1}+x_{2}+x_{3}\leq{}30000\end{math} (5.6.7)

to the problem which is done in the following code:

/* Append a new constraint */ if (r == MSK_RES_OK) r = MSK_append(task,MSK_ACC_CON,1); /* Get index of new constraint, this should be 4 */ if (r == MSK_RES_OK) r = MSK_getnumcon(task,&numcon); /* Set bounds on new constraint */ if (r == MSK_RES_OK) r = MSK_putbound(task, MSK_ACC_CON, numcon-1, 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_putavec(task, MSK_ACC_CON, numcon-1, /* row index */ 4, /* num nz in row*/ arowsub, arowval); }

5.7. Efficiency considerations

Although MOSEK is implemented to handle memory efficiently, the user may have valuable knowledge about a problem, which could be used to improve the performance of MOSEK. This section discusses some tricks and general advice that hopefully make MOSEK process your problem faster.

Avoid memory fragmentation:

MOSEK stores the optimization problem in internal data structures in the memory. Initially MOSEK will allocate structures of a certain size, and as more items are added to the problem the structures are reallocated. For large problems the same structures may be reallocated many times causing memory fragmentation. One way to avoid this is to give MOSEK an estimated size of your problem using the functions:

None of these functions change the problem, they only give hints to the eventual dimension of the problem. If the problem ends up growing larger than this, the estimates are automatically increased.

Tune the reallocation process:

It is possible to obtain information about how often MOSEK reallocates storage for the A matrix by inspecting MSK_IINF_STO_NUM_A_REALLOC. A large value indicates that maxnumanz has been reestimated many times and that the initial estimate should be increased.

Do not mix put- and get- functions:

For instance, the functions MSK_putavec and MSK_getavec. MOSEK will queue put- commands internally until a get- function is called. If every put- function call is followed by a get- function call, the queue will have to be flushed often, decreasing efficiency.

In general get- commands should not be called often during problem setup.

Use the LIFO principle when removing constraints and variables:

MOSEK can more efficiently remove constraints and variables with a high index than a small index.

An alternative to removing a constraint or a variable is to fix it at 0, and set all relevant coefficients to 0. Generally this will not have any impact on the optimization speed.

Add more constraints and variables than you need (now):

The cost of adding one constraint or one variable is about the same as adding many of them. Therefore, it may be worthwhile to add many variables instead of one. Initially fix the unused variable at zero, and then later unfix them as needed. Similarly, you can add multiple free constraints and then use them as needed.

Use one environment (env) only:

If possible share the environment (env) between several tasks. For most applications you need to create only a single env.

Do not remove basic variables:

When doing reoptimizations, 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 reoptimized and it has left the basis. This makes it easier for MOSEK to restart the simplex optimizer.

5.8. Conventions employed in the API

5.8.1. Naming conventions for arguments

In the definition of the MOSEK C API a consistent naming convention has been used. This implies that whenever for example numcon is an argument in a function definition it indicates the number of constraints.

In Table 5.2 the variable names used to specify the problem parameters are listed.

C name C type Dimension Related problem
  parameter
numcon int m
numvar int n
numcone int t
numqonz int [[MathCmd 88]]
qosubi int[] numqonz [[MathCmd 88]]
qosubj int[] numqonz [[MathCmd 88]]
qoval double* numqonz [[MathCmd 88]]
c double[] numvar [[MathCmd 92]]
cfix double [[MathCmd 10]]
numqcnz int [[MathCmd 94]]
qcsubk int[] qcnz [[MathCmd 94]]
qcsubi int[] qcnz [[MathCmd 94]]
qcsubj int[] qcnz [[MathCmd 94]]
qcval double* qcnz [[MathCmd 94]]
aptrb int[] numvar [[MathCmd 99]]
aptre int[] numvar [[MathCmd 99]]
asub int[] aptre[numvar-1] [[MathCmd 99]]
aval double[] aptre[numvar-1] [[MathCmd 99]]
bkc MSKboundkeye* numcon [[MathCmd 103]] and [[MathCmd 104]]
blc double[] numcon [[MathCmd 103]]
buc double[] numcon [[MathCmd 104]]
bkx MSKboundkeye * numvar [[MathCmd 107]] and [[MathCmd 108]]
blx double[] numvar [[MathCmd 107]]
bux double[] numvar [[MathCmd 108]]
Table 5.2: Naming convention used in MOSEK

The relation between the variable names and the problem parameters is as follows:

  • The quadratic terms in the objective:

    \begin{math}\nonumber{}q_{{\mathtt{qosubi[t]},\mathtt{qosubj[t]}}}^{o}=\mathtt{qoval[t]},~t=0,\ldots ,\mathtt{numqonz}-1.\end{math} (5.8.1)
  • The linear terms in the objective:

    \begin{math}\nonumber{}c_{j}=\mathtt{c[j]},~j=0,\ldots ,\mathtt{numvar}-1\end{math} (5.8.2)
  • The fixed term in the objective:

    \begin{math}\nonumber{}c^{f}=\mathtt{cfix}.\end{math} (5.8.3)
  • The quadratic terms in the constraints:

    \begin{math}\nonumber{}q_{{\mathtt{qcsubi[t]},\mathtt{qcsubj[t]}}}^{\mathtt{qcsubk[t]}}=\mathtt{qcval[t]},~t=0,\ldots ,\mathtt{numqcnz}-1.\end{math} (5.8.4)
  • The linear terms in the constraints:

    \begin{math}\nonumber{}\begin{array}{rl}\nonumber{}a_{{\mathtt{asub[t],j}}}=\mathtt{aval[t]}, & t=\mathtt{ptrb[j]},\ldots ,\mathtt{ptre[j]}-1,\\\nonumber{} & j=0,\ldots ,\mathtt{numvar}-1.\end{array}\end{math} (5.8.5)
  • The bounds on the constraints are specified using the variables bkc, blc, and buc. The components of the integer array bkc specify the bound type according to Table 5.3.

    Symbolic constant Lower bound Upper bound
    MSK_BK_FX finite identical to the lower bound
    MSK_BK_FR minus infinity plus infinity
    MSK_BK_LO finite plus infinity
    MSK_BK_RA finite finite
    MSK_BK_UP minus infinity finite
    Table 5.3: Interpretation of the bound keys.

    For instance bkc[2]=MSK_BK_LO means that [[MathCmd 116]] and [[MathCmd 117]]. Finally, the numerical values of the bounds are given by

    \begin{math}\nonumber{}l_{k}^{c}=\mathtt{blc[k]},~k=0,\ldots ,\mathtt{numcon}-1\end{math} (5.8.6)

    and

    \begin{math}\nonumber{}u_{k}^{c}=\mathtt{buc[k]},~k=0,\ldots ,\mathtt{numcon}-1.\end{math} (5.8.7)
  • The bounds on the variables are specified using the variables bkx, blx, and bux. The components in the integer array bkx specify the bound type according to Table 5.3. The numerical values for the lower bounds on the variables are given by

    \begin{math}\nonumber{}l_{j}^{x}=\mathtt{blx[j]},~j=0,\ldots ,\mathtt{numvar}-1.\end{math} (5.8.8)

    The numerical values for the upper bounds on the variables are given by

    \begin{math}\nonumber{}u_{j}^{x}=\mathtt{bux[j]},~j=0,\ldots ,\mathtt{numvar}-1.\end{math} (5.8.9)

5.8.1.1. Bounds

A bound on a variable or on a constraint in MOSEK consists of a bound key, as defined in Table 5.3, a lower bound value and an upper bound value. Even if a variable or constraint is bounded only from below, e.g. x0, both bounds are inputted or extracted; the value inputted as upper bound for (x0) is ignored.

5.8.2. Vector formats

Three different vector formats are used in the MOSEK API:

Full vector:

This is simply an array where the first element corresponds to the first item, the second element to the second item etc. For example to get the linear coefficients of the objective in task, one would write

MSKrealt * c = MSK_calloctask(task, numvar, sizeof(MSKrealt)); MSK_getc(task,c);

where numvar is the number of variables in the problem.

Vector slice:

A vector slice is a range of values. For example, to get the bounds associated constraint 3 through 10 (both inclusive) one would write

MSKrealt * upper_bound = MSK_calloctask(task,8,sizeof(MSKrealt)); MSKrealt * lower_bound = MSK_calloctask(task,8,sizeof(MSKrealt)); MSKboundkeye * bound_key = MSK_calloctask(task,8,sizeof(MSKboundkeye)); MSK_getboundslice(task,MSK_ACC_CON, 2,10, bound_key,lower_bound,upper_bound);

Please note that items in MOSEK are numbered from 0, so that the index of the first item is 0, and the index of the n'th item is n-1.

Sparse vector:

A sparse vector is given as an array of indexes and an array of values. For example, to input a set of bounds associated with constraints number 1, 6, 3, and 9, one might write

MSKidxt bound_index[] = { 1, 6, 3, 9 }; MSKboundkeye bound_key[] = { MSK_BK_FR, MSK_BK_LO, MSK_BK_UP, MSK_BK_FX }; MSKrealt lower_bound[] = { 0.0, -10.0, 0.0, 5.0 }; MSKrealt upper_bound[] = { 0.0, 0.0, 6.0, 5.0 }; MSK_putboundlist(task,MSK_ACC_CON, 4, bound_index, bound_key,lower_bound,upper_bound);

Note that the list of indexes need not be ordered.

5.8.3. Matrix formats

The coefficient matrices in a problem are inputted and extracted in a sparse format, either as complete or a partial matrices. Basically there are two different formats for this.

5.8.3.1. Unordered triplets

In unordered triplet format each entry is defined as a row index, a column index and a coefficient. For example, to input the A matrix coefficients for [[MathCmd 122]], [[MathCmd 123]], and [[MathCmd 124]], one would write as follows:

MSKidxt subi[] = { 1, 3, 5 }; MSKidxt subj[] = { 2, 3, 4 }; MSKrealt cof[] = { 1.1, 4.3, 0.2 }; MSK_putaijlist(task,3, subi,subj,cof);

Please note that in some cases (like MSK_putaijlist) only the specified indexes remain modified — all other are unchanged. In other cases (such as MSK_putqconk) the triplet format is used to modify all entries — entries that are not specified are set to 0.

5.8.3.2. Row or column ordered sparse matrix

In a sparse matrix format only the non-zero entries of the matrix are stored. MOSEK uses a sparse matrix format ordered either by rows or columns. In the column-wise format the position of the non-zeros are given as a list of row indexes. In the row-wise format the position of the non-zeros are given as a list of column indexes. Values of the non-zero entries are given in column or row order.

A sparse matrix in column ordered format consists of:

asub:

List of row indexes.

aval:

List of non-zero entries of A ordered by columns.

ptrb:

Where ptrb[j] is the position of the first value/index in aval / asub for column j.

ptre:

Where ptre[j] is the position of the last value/index plus one in aval / asub for column j.

The values of a matrix A with numcol columns are assigned so that for

\begin{displaymath}\nonumber{}j=0,\ldots ,\mathtt{numcol}-1.\end{displaymath}

We define

\begin{math}\nonumber{}\begin{array}{rcl}\nonumber{}a_{{\mathtt{asub}[k],j}}=\mathtt{aval}[k],\quad{}k=\mathtt{ptrb}[j],\ldots ,\mathtt{ptre}[j]-1.\end{array}\end{math} (5.8.10)

Figure 5.1: The matrix A (5.8.11) represented in column ordered sparse matrix format.

As an example consider the matrix

\begin{math}\nonumber{}A=\left[\begin{array}{ccccc}\nonumber{}1.1 &  & 1.3 & 1.4 & \\\nonumber{} & 2.2 &  &  & 2.5\\\nonumber{}3.1 &  &  & 3.4 & \\\nonumber{} &  & 4.4 &  &\end{array}\right].\end{math} (5.8.11)

which can be represented in the column ordered sparse matrix format as

\begin{displaymath}\nonumber{}\begin{array}{lcl}\nonumber{}\mathtt{ptrb} & = & [0,2,3,5,7],\\\nonumber{}\mathtt{ptre} & = & [2,3,5,7,8],\\\nonumber{}\mathtt{asub} & = & [0,2,1,0,3,0,2,1],\\\nonumber{}\mathtt{aval} & = & [1.1,3.1,2.2,1.3,4.4,1.4,3.4,2.5].\end{array}\end{displaymath}

Fig. 5.1 illustrates how the matrix A (5.8.11) is represented in column ordered sparse matrix format.

5.8.3.3. Row ordered sparse matrix

The matrix A (5.8.11) can also be represented in the row ordered sparse matrix format as:

\begin{displaymath}\nonumber{}\begin{array}{lcl}\nonumber{}\mathtt{ptrb} & = & [0,3,5,7],\\\nonumber{}\mathtt{ptre} & = & [3,5,7,8],\\\nonumber{}\mathtt{asub} & = & [0,2,3,1,4,0,3,2],\\\nonumber{}\mathtt{aval} & = & [1.1,1.3,1.4,2.2,2.5,3.1,3.4,4.4].\end{array}\end{displaymath}

5.9. The license system

By default a license token is checked out when MSK_optimizetrm is first called and is returned when the MOSEK environment is deleted. Calling MSK_optimizetrm from different threads using the same MOSEK environment only consumes one license token.

To change the license systems behavior to returning the license token after each call to MSK_optimizetrm set the parameter MSK_IPAR_CACHE_LICENSE to MSK_OFF. Please note that there is a small overhead associated with setting this parameter, since checking out a license token from the license server can take a small amount of time.

Additionally license checkout and checkin can be controlled manually with the functions MSK_checkinlicense and MSK_checkoutlicense.

5.9.1. Waiting for a free license

By default an error will be returned if no license token is available. By setting the parameter MSK_IPAR_LICENSE_WAIT MOSEK can be instructed to wait until a license token is available.

Mon Oct 29 07:20:54 2012