2. Linear Optimization

The simplest and most scalable class of optimization problems is the one where the objective function and the constraints are formulated using the simplest possible type of functions – linear functions. A linear optimization (LO) is an optimization problem of the form

\[\begin{split} \begin{align*} \min \quad & c^\top x \\ \text{s.t.} \quad & A x \leq b\\ & x \geq 0, \end{align*} \end{split}\]

where the \(n\) (decision) variables are grouped in a vector \(x \in \mathbb{R}^n\), \(c \in \mathbb{R}^n\) are the objective coefficients, and the \(m\) linear constraints are described by the matrix \(A \in \mathbb{R}^{m \times n}\) and the vector \(b \in \mathbb{R}^m\).

Linear problems can (i) be maximization problems, (ii) involve equality constraints and constraints of the form \(\geq\), and (iii) have unbounded or non-positive decision variables \(x_i\)’s. In fact, any LO problem with such features can be easily converted to the “canonical” LO form above by adding/removing variables and/or multiplying specific inequalities by \(-1\).

In this chapter, there is a number of examples with companion AMPL implementation that explore various modeling and implementation aspects of LOs:

• A first LO example, modelling the microchip production problem of company BIM

• Least Absolute Deviation (LAD) Regression

• Mean Absolute Deviation (MAD) portfolio optimization

• Wine quality prediction problem using L1 regression

• A variant of BIM problem: maximizing the lowest possible profit

• Two variants of the BIM problem using fractional objective or additional fixed costs

• The BIM production problem using demand forecasts

• Extra material: Multi-product facility production

Go to the next chapter about mixed-integer linear optimization.