2. Linear Optimization

The simplest and most scalable type of optimization problem is the one where the objective function and constraints are formulated using the simplest possible type of functions – linear functions. We refer to this class of problems as linear optimization (LO) problems.

In this collection of notebooks, we adhere to the standard convention of representing LO problems with an objective of minimization, all constraints being of the type \(\geq\), and all variables being nonnegative. In other words, we work with the following general formulation for LO problems:

\[\begin{split} \begin{align*} \min \quad & c^\top x \\ \text{s.t.} \quad & A x \geq 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\).

This chapter includes several with companion Pyomo implementation that explore various modeling and implementation aspects of LOs:

• Microchip production problem of company BIM

• Least Absolute Deviation (LAD) Regression

• Mean Absolute Deviation (MAD) portfolio optimization

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

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

• The dual problem of the microchip production problem

• The BIM production problem using demand forecasts

• Extra material: Wine quality prediction problem using \(L_1\) regression

• Extra material: Multi-product facility production

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