6.1 Linear Optimization

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

Minimize or maximize the objective function

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

subject to the linear constraints

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

and the bounds

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

The problem description consists of the following elements:

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

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

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

  \[\begin{split}c = \left[ \begin{array}{c} c_0 \\ \vdots \\ c_{n-1} \end{array} \right],\end{split}\]

• \(c^f\) — fixed term in the objective,

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

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

• \(l^c\) and \(u^c\) — the lower and upper bounds on constraints,

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

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

6.1.1 Example LO1

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

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

under the bounds

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

This is easily programmed in R as shown in Listing 6.1. The first line overwrites any previous definitions of the variable lo1, preparing for the new problem description. The problem is then defined and finally solved on the last line.

Listing 6.1 R implementation of problem (6.1). Click here to download.

lo1 <- function()
{
    prob <- list()

    # Objective sense (maximize or minimize)
    prob$sense <- "max"

    # Objective coefficients
    prob$c <- c(3, 1, 5, 1)

    # Specify matrix 'A' in sparse format.
    asubi  <- c(1, 1, 1, 2, 2, 2, 2, 3, 3)
    asubj  <- c(1, 2, 3, 1, 2, 3, 4, 2, 4)
    aval   <- c(3, 1, 2, 2, 1, 3, 1, 2, 3)

    prob$A <- sparseMatrix(asubi,asubj,x=aval)

    # Bound values for constraints
    prob$bc <- rbind(blc=c(30,  15, -Inf), 
                     buc=c(30, Inf,   25))

    # Bound values for variables
    prob$bx <- rbind(blx=rep(0,4), 
                     bux=c(Inf, 10, Inf, Inf))

    # Solve the problem
    r <- mosek(prob)
    
    # Return the solution
    stopifnot(identical(r$response$code, 0))
    r$sol
}

Notice how the R value Inf is used in both the constraint bounds (blc and buc) and the variable upper bound (bux), to avoid the specification of an actual bound.

From this example the input arguments for the linear program follows easily.

• Objective The string is the objective goal and could be either minimize, min, maximize or max. The dense numeric vector specifies the coefficients in front of the variables in the linear objective function, and the optional constant scalar (reads: c zero) is a constant in the objective corresponding to \(c^f\), that will be assumed zero if not specified.

• Constraint Matrix The sparse matrix is the constraint matrix of the problem with the constraint coefficients written row-wise. Notice that for larger problems it may be more convenient to define an empty sparse matrix and specify the non-zero elements one at a time \(A(i,j) = a_{ij}\), rather than writing out the full matrix as done in the example. E.g. Matrix(0,nrow=30,ncol=50,sparse=TRUE).

• Bounds The constraint bounds with rows blc (constraint lower bound) and buc (constraint upper bound), as well as the variable bounds with rows blx (variable lower bound) and bux (variable upper bound), are both given as dense numeric matrices. These are equivalent to the bounds of problem, namely \(l^c\), \(u^c\), \(l^x\) and \(u^x\).