# 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:

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