6.1 Linear Optimization¶
The simplest optimization problem is a purely linear problem. A linear optimization problem (see also Sec. 12.1 (Linear Optimization)) is a problem of the following form:
Minimize or maximize the objective function
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:
(Optionally) Creating an environment.
Creating an optimization task.
Loading a problem into the task object.
Optimization.
Extracting the solution.
Below we explain each of these steps.
Creating an environment.
The user can start by creating a MOSEK environment, but it is not necessary if the user does not need access to other functionalities, license management, additional routines, etc. Therefore in this tutorial we don’t create an explicit environment.
Creating an optimization task.
We create an empty task object. A task object represents all the data (inputs, outputs, parameters, information items etc.) associated with one optimization problem.
maketask() do task
# Use remote server: putoptserverhost(task,"http://solve.mosek.com:30080")
putstreamfunc(task,MSK_STREAM_LOG,msg -> print(msg))
We also connect a call-back function to the task log stream. Messages related to the task are passed to the call-back function. In this case the stream call-back function writes its messages to the standard output stream. See Sec. 7.4 (Input/Output).
Loading a problem into the task object.
Before any problem data can be set, variables and constraints must be added to the problem via calls to the functions appendcons and appendvars.
# Append 'numcon' empty constraints.
# The constraints will initially have no bounds.
appendcons(task,numcon)
for i=1:numcon
putconname(task,i,@sprintf("c%02d",i))
end
# Append 'numvar' variables.
# The variables will initially be fixed at zero (x=0).
appendvars(task,numvar)
for j=1:numvar
putvarname(task,j,@sprintf("x%02d",j))
end
New variables can now be referenced from other functions with indexes in \(\idxbeg, \ldots, \idxend{\mathtt{numvar}}\) and new constraints can be referenced with indexes in \(\idxbeg, \ldots , \idxend{\mathtt{numcon}}\). More variables and/or constraints can be appended later as needed, these will be assigned indexes from \(\mathtt{numvar}\)/\(\mathtt{numcon}\) and up. Optionally one can add names.
Setting the objective.
Next step is to set the problem data. We first set the objective coefficients \(c_j = \mathtt{c[j]}\). This can be done with functions such as putcj or putclist.
putclist(task,[1,2,3,4], c)
Setting bounds on variables
For every variable we need to specify a bound key and two bounds according to Table 6.1.
Bound key |
Type of bound |
Lower bound |
Upper bound |
|---|---|---|---|
\(u_j = l_j\) |
Finite |
Identical to the lower bound |
|
Free |
\(-\infty\) |
\(+\infty\) |
|
\(l_j \leq \cdots\) |
Finite |
\(+\infty\) |
|
\(l_j \leq \cdots \leq u_j\) |
Finite |
Finite |
|
\(\cdots \leq u_j\) |
\(-\infty\) |
Finite |
For instance bkx[0]= MSK_BK_LO means that \(x_0 \geq l_0^x\). Finally, the numerical values of the bounds on variables are given by
and
Let us assume we have the bounds on variables stored in the arrays
# Bound keys for variables
bkx = [ MSK_BK_LO
MSK_BK_RA
MSK_BK_LO
MSK_BK_LO ]
# Bound values for variables
blx = [ 0.0, 0.0, 0.0, 0.0]
bux = [+Inf, 10.0, +Inf, +Inf]
Then we can set them using various functions such putvarbound, putvarboundslice, putvarboundlist, depending on what is most convenient in the given context. For instance:
putvarboundslice(task, 1, numvar+1, bkx,blx,bux)
Defining the linear constraint matrix.
Recall that in our example the \(A\) matrix is given by
This matrix is stored in sparse format:
# Below is the sparse representation of the A
# matrix stored by column.
A = sparse([1, 2, 1, 2, 3, 1, 2, 2, 3],
[1, 1, 2, 2, 2, 3, 3, 4, 4],
[3.0, 2.0, 1.0, 1.0, 2.0, 2.0, 3.0, 1.0, 3.0 ],
numcon,numvar)
The matrix is stored as a standard sparse matrix in Julia, but other representations are also possible.
We now input the linear constraint matrix into the task. This can be done in many alternative ways, row-wise, column-wise or element by element in various orders. See functions such as putarow, putarowlist, putaijlist, putacol and similar.
putacolslice(task,1,numvar+1,A)
Setting bounds on constraints
Finally, the bounds on each constraint are set similarly to the variable bounds, using the bound keys as in Table 6.1. This can be done with one of the many functions putconbound, putconboundslice, putconboundlist, depending on the situation.
# Set the bounds on constraints.
# blc[i] <= constraint_i <= buc[i]
putconboundslice(task,1,numcon+1,bkc,blc,buc)
Optimization
After the problem is set-up the task can be optimized by calling the function optimize.
optimize(task)
Extracting the solution.
After optimizing the status of the solution is examined with a call to getsolsta.
solsta = getsolsta(task,MSK_SOL_BAS)
If the solution status is reported as MSK_SOL_STA_OPTIMAL the solution is extracted:
xx = getxx(task,MSK_SOL_BAS)
The 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 MSK_SOL_BAS. For details about fetching solutions see Sec. 7.2 (Accessing the solution).
Source code
The complete source code lo1.jl of this example appears below. See also lo2.jl for a version where the \(A\) matrix is entered row-wise.
using Mosek
using Printf, SparseArrays
############################
## Define problem data
bkc = [MSK_BK_FX
MSK_BK_LO
MSK_BK_UP]
# Bound values for constraints
blc = [30.0, 15.0, -Inf]
buc = [30.0, +Inf, 25.0]
# Bound keys for variables
bkx = [ MSK_BK_LO
MSK_BK_RA
MSK_BK_LO
MSK_BK_LO ]
# Bound values for variables
blx = [ 0.0, 0.0, 0.0, 0.0]
bux = [+Inf, 10.0, +Inf, +Inf]
numvar = length(bkx)
numcon = length(bkc)
# Objective coefficients
c = [ 3.0, 1.0, 5.0, 1.0 ]
# Below is the sparse representation of the A
# matrix stored by column.
A = sparse([1, 2, 1, 2, 3, 1, 2, 2, 3],
[1, 1, 2, 2, 2, 3, 3, 4, 4],
[3.0, 2.0, 1.0, 1.0, 2.0, 2.0, 3.0, 1.0, 3.0 ],
numcon,numvar)
############################
maketask() do task
# Use remote server: putoptserverhost(task,"http://solve.mosek.com:30080")
putstreamfunc(task,MSK_STREAM_LOG,msg -> print(msg))
putobjname(task,"lo1")
# Append 'numcon' empty constraints.
# The constraints will initially have no bounds.
appendcons(task,numcon)
for i=1:numcon
putconname(task,i,@sprintf("c%02d",i))
end
# Append 'numvar' variables.
# The variables will initially be fixed at zero (x=0).
appendvars(task,numvar)
for j=1:numvar
putvarname(task,j,@sprintf("x%02d",j))
end
putclist(task,[1,2,3,4], c)
putacolslice(task,1,numvar+1,A)
putvarboundslice(task, 1, numvar+1, bkx,blx,bux)
# Set the bounds on constraints.
# blc[i] <= constraint_i <= buc[i]
putconboundslice(task,1,numcon+1,bkc,blc,buc)
# Input the objective sense (minimize/maximize)
putobjsense(task,MSK_OBJECTIVE_SENSE_MAXIMIZE)
# Solve the problem
optimize(task)
# Print a summary containing information
# about the solution for debugging purposes
solutionsummary(task,MSK_STREAM_MSG)
# Get status information about the solution
solsta = getsolsta(task,MSK_SOL_BAS)
if solsta == MSK_SOL_STA_OPTIMAL
xx = getxx(task,MSK_SOL_BAS)
print("Optimal solution:")
println(xx)
elseif solsta in [ MSK_SOL_STA_DUAL_INFEAS_CER,
MSK_SOL_STA_PRIM_INFEAS_CER ]
println("Primal or dual infeasibility certificate found.\n")
elseif solsta == MSK_SOL_STA_UNKNOWN
println("Unknown solution status")
else
@printf("Other solution status (%d)\n",solsta)
end
end
