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

\[\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.2.1 Example LO1

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

(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}\]

Example: Linear optimization using msklpopt

A linear optimization problem such as (1) can be solved using the msklpopt function. The first step in solving the example (1) is to setup the data for problem (1) i.e. the \(c\), \(A\), etc. Afterwards the problem is solved using an appropriate call to msklpopt.

Listing 4 Script implementing problem (1). Click here to download.
function lo1()

c     = [3 1 5 1]';
a     = [[3 1 2 0];[2 1 3 1];[0 2 0 3]];
blc   = [30 15  -inf]';
buc   = [30 inf 25 ]';
blx   = zeros(4,1);
bux   = [inf 10 inf inf]';

[res] = msklpopt(c,a,blc,buc,blx,bux,[],'maximize');
sol   = res.sol;

% Interior-point solution.

sol.itr.xx'      % x solution.
sol.itr.sux'     % Dual variables corresponding to buc.
sol.itr.slx'     % Dual variables corresponding to blx.

% Basic solution.

sol.bas.xx'      % x solution in basic solution.

Please note that

  • Infinite bounds are specified using -inf and inf. Moreover, the bux = [] means that all upper bounds \(u^x\) are plus infinite.
  • The lines after the msklpopt call can be omitted, but the purpose of those lines is to display different parts of the solutions. The res.sol field contains one or more solutions. In this case both the interior-point solution (sol.itr) and the basic solution (sol.bas) are defined.

Example: Linear optimization using mosekopt

The msklpopt function is in fact just a wrapper around the real optimization routine mosekopt. Therefore, an alternative to using the msklpopt is to call mosekopt directly. In general, the syntax for a mosekopt call is

[rcode,res] = mosekpt(cmd,prob,param)

The arguments prob and param are optional. The purpose of the arguments are as follows:

  • cmd string telling mosekopt what to do, e.g. ’minimize info’ tells mosekopt that the objective should be minimized and information about the optimization should be returned.
  • prob : MATLAB structure specifying the problem that should be optimized.
  • param : MATLAB structure specifying parameters controlling the behavior of the MOSEK optimizer. However, in general it should not be necessary to change the parameters.

The following MATLAB commands demonstrate how to set up the prob structure for the example (1) and solve the problem using mosekopt.

Listing 5 Script implementing problem (1) using mosekopt. Click here to download.
function lo2()
clear prob;

% Specify the c vector.
prob.c  = [3 1 5 1]';

% Specify a in sparse format.
subi   = [1 1 1 2 2 2 2 3 3];
subj   = [1 2 3 1 2 3 4 2 4];
valij  = [3 1 2 2 1 3 1 2 3];

prob.a = sparse(subi,subj,valij);

% Specify lower bounds of the constraints.
prob.blc = [30 15  -inf]';

% Specify  upper bounds of the constraints.
prob.buc = [30 inf 25 ]';

% Specify lower bounds of the variables.
prob.blx = zeros(4,1);

% Specify upper bounds of the variables.
prob.bux = [inf 10 inf inf]';

% Perform the optimization.
[r,res] = mosekopt('maximize',prob); 

% Show the optimal x solution.
res.sol.bas.xx

Please note that

  • A MATLAB structure named prob containing all the relevant problem data is defined.
  • All fields of this structure are optional except prob.a which is required to be a sparse matrix.
  • Different parts of the solution can be viewed by inspecting the solution field res.sol.

Example: Linear optimization using linprog

MOSEK also provides a linprog function, which is compatible with the function provided by the MATLAB toolbox, using the syntax

[x,fval,exitflag,output,lambda] = linprog(f,A,b,B,c,l,u,x0,options)

Several control parameters can be set using the options structure, for example,

options.Write = 'test.opf';
linprog(f,A,b,B,c,l,u,x0,options);

creates a human readable opf file of the problem, and

options.Write = 'test.task';
linprog(f,A,b,B,c,l,u,x0,options);

creates a binary task file which can be send to MOSEK for debugging assistance or reporting errors.

Consult Sec. 5.1 (The MOSEK integration with MATLAB) for details on using linprog and other compatibility functions.

Internally, the linprog function is just a wrapper for the mosekopt function, and is mainly intended for compatibility reasons; advanced features are mainly available through the mosekopt function.