2. Linear Optimization

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:

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