# 6.1 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

subject to the linear constraints

and the bounds

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:

under the bounds

Solving the problem

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

- Create an environment.
- Create an optimization task.
- Load a problem into the task object.
- Optimization.
- Extracting the solution.

Below we explain each of these steps.

Create an environment.

Before setting up the optimization problem, a **MOSEK** environment must be created. All tasks in the program should share the same environment.

```
# Make mosek environment
with mosek.Env() as env:
```

Create an optimization task.

Next, an empty task object is created:

```
# Create a task object
with env.Task(0, 0) as task:
# Attach a log stream printer to the task
task.set_Stream(mosek.streamtype.log, streamprinter)
```

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.

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 \(0, \ldots, \mathtt{numvar}-1\) and new constraints can be referenced with indexes in \(0, \ldots , \mathtt{numcon}-1\). More variables and/or constraints can be appended later as needed, these will be assigned indexes from \(\mathtt{numvar}\)/\(\mathtt{numcon}\) and up.

Next step is to set the problem data. We loop over each variable index \(j=0, \ldots, \mathtt{numvar}-1\) calling functions to set problem data. We first set the objective coefficient \(c_j = \mathtt{c[j]}\) by calling the function `Task.putcj`

.

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

Setting bounds on variables

The bounds on variables are stored in the arrays

```
# Bound keys for variables
bkx = [mosek.boundkey.lo,
mosek.boundkey.ra,
mosek.boundkey.lo,
mosek.boundkey.lo]
# Bound values for variables
blx = [0.0, 0.0, 0.0, 0.0]
bux = [+inf, 10.0, +inf, +inf]
```

and are set with calls to `Task.putvarbound`

.

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

The *Bound key* stored in `bkx`

specifies the type of the bound according to Table 2.

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

and

Defining the linear constraint matrix.

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

This matrix is stored in sparse format in the arrays:

```
asub = [[0, 1],
[0, 1, 2],
[0, 1],
[1, 2]]
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 index of these non-zeros.

Using the function `Task.putacol`

we set 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.
```

There are many alternative formats for entering the \(A\) matrix. See functions such as `Task.putarow`

, `Task.putarowlist`

, `Task.putaijlist`

and similar.

Finally, the bounds on each constraint are set by looping over each constraint index \(i= 0, \ldots,\mathtt{numcon}-1\)

```
# Set the bounds on constraints.
# blc[i] <= constraint_i <= buc[i]
for i in range(numcon):
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`

. If the solution status is reported as `solsta.optimal`

or `solsta.near_optimal`

the solution is extracted in the lines below:

```
xx = [0.] * numvar
task.getxx(mosek.soltype.bas, # Request the basic solution.
xx)
```

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`

.

Catching exceptions

We cache any exceptions thrown by **MOSEK** in the lines:

```
except mosek.Error as e:
print("ERROR: %s" % str(e.errno))
if e.msg is not None:
print("\t%s" % e.msg)
sys.exit(1)
```

The types of exceptions that **MOSEK** can throw can be seen in Sec. 16.8 (Response codes).

Source code

The complete source code `lo1.py`

of this example appears below. See also `lo2.py`

for a version where the \(A\) matrix is entered row-wise.

```
import sys
import mosek
# Since the value of infinity is ignored, we define it solely
# for symbolic purposes
inf = 0.0
# Define a stream printer to grab output from MOSEK
def streamprinter(text):
sys.stdout.write(text)
sys.stdout.flush()
def main():
# Make mosek environment
with mosek.Env() as env:
# Create a task object
with env.Task(0, 0) as task:
# Attach a log stream printer to the task
task.set_Stream(mosek.streamtype.log, streamprinter)
# Bound keys for constraints
bkc = [mosek.boundkey.fx,
mosek.boundkey.lo,
mosek.boundkey.up]
# Bound values for constraints
blc = [30.0, 15.0, -inf]
buc = [30.0, +inf, 25.0]
# Bound keys for variables
bkx = [mosek.boundkey.lo,
mosek.boundkey.ra,
mosek.boundkey.lo,
mosek.boundkey.lo]
# Bound values for variables
blx = [0.0, 0.0, 0.0, 0.0]
bux = [+inf, 10.0, +inf, +inf]
# Objective coefficients
c = [3.0, 1.0, 5.0, 1.0]
# Below is the sparse representation of the A
# matrix stored by column.
asub = [[0, 1],
[0, 1, 2],
[0, 1],
[1, 2]]
aval = [[3.0, 2.0],
[1.0, 1.0, 2.0],
[2.0, 3.0],
[1.0, 3.0]]
numvar = len(bkx)
numcon = len(bkc)
# 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 j in range(numvar):
# 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 i in range(numcon):
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
solsta = task.getsolsta(mosek.soltype.bas)
if (solsta == mosek.solsta.optimal or
solsta == mosek.solsta.near_optimal):
xx = [0.] * numvar
task.getxx(mosek.soltype.bas, # Request the basic solution.
xx)
print("Optimal solution: ")
for i in range(numvar):
print("x[" + str(i) + "]=" + str(xx[i]))
elif (solsta == mosek.solsta.dual_infeas_cer or
solsta == mosek.solsta.prim_infeas_cer or
solsta == mosek.solsta.near_dual_infeas_cer or
solsta == mosek.solsta.near_prim_infeas_cer):
print("Primal or dual infeasibility certificate found.\n")
elif solsta == mosek.solsta.unknown:
print("Unknown solution status")
else:
print("Other solution status")
# call the main function
try:
main()
except mosek.Error as e:
print("ERROR: %s" % str(e.errno))
if e.msg is not None:
print("\t%s" % e.msg)
sys.exit(1)
except:
import traceback
traceback.print_exc()
sys.exit(1)
```