Optimization Modeling with Applications - Optimization for Decision Science

Recommended Reading¶

Please review the following book chapters (in order):

Chapter 1 of Biegler (2010) introduces classes of optimization problems motivated by applications.
Chapters 1 and 2 in Bynum et al. (2021) provide an overview of Pyomo and optimization modeling.
Chapters 3 and 4 in Bynum et al. (2021) describe core Pyomo features through examples.
Chapter 7 in Bynum et al. (2021) describes special considerations for nonlinear programs.
Chapter 8 in Bynum et al. (2021) describes structured modeling with blocks.
Chapter 11 in Bynum et al. (2021) describes generalized disjunctive programming (logical decisions).
Chapter 12 in Bynum et al. (2021) describes optimization with differential algebraic equations (DAEs).
Chapter 10 in Biegler (2010) provides mathematical background for DAE-constrained optimization.

For stochastic programming, read Birge and Louveaux instead of the Pyomo book. The third edition dropped the PySP chapter, and PySP is no longer shipped with Pyomo; the capability now lives in the separate mpi-sppy package.

Reference: Bynum, M. L., Hackebeil, G. A., Hart, W. E., Laird, C. D., Nicholson, B. L., Siirola, J. D., Watson, J.-P., and Woodruff, D. L. Pyomo — Optimization Modeling in Python, Third Edition. Springer Optimization and Its Applications, Vol. 67, 2021.

Taxonomy of Optimization Problems¶

Reference: Chapter 1 in Biegler (2010).

The following chart organizes optimization problems based on key characteristics including variable type (continuous versus discrete) and whether the objective and constraints are differentiable. These factors impact which algorithms are best suited for different problems.

Linear Programs (LP) / Linear Optimization Problems¶

\begin{align*} \min_{x} \quad & f^T x & \text{(linear objective)} \\ \text{s.t.} \quad & A \cdot x = b & \text{(linear constraints)} \\ & x^L \leq x \leq x^U & \text{(bounds)} \end{align*}

(1)

Recall, “s.t.” means “subject to”.

How to enforce $x_1 + x_2 \leq c$ in the above formulation? Convert it to an equality constraint:

x_1 + x_2 = s_1

(2)

where $s_1$ is a slack variable.

Quadratic Program (QP)¶

\begin{align*} \min_{x} \quad & \frac{1}{2} x^T H x + f^T x & \text{(quadratic objective)} \\ \text{s.t.} \quad & A \cdot x = b & \text{(linear constraints)} \\ & x^L \leq x \leq x^U & \text{(bounds)} \end{align*}

(3)

Parameters: $H$ , $f$ , $A$ , $b$ , $x^L$ , $x^U$

There are specialized solvers for LP, QP, and other convex optimization problems. We will not focus on these in this class, but instead consider algorithms for general nonlinear programs.

Nonlinear Program (NLP)¶

\begin{align*} \min_{x} \quad & f(x) & \text{(nonlinear objective)} \\ \text{s.t.} \quad & g(x) = 0 & \text{(equality constraints)} \\ & h(x) \leq 0 & \text{(inequality constraints)} \end{align*}

(4)

where $f(x), g(x), h(x)$ are all nonlinear functions. Bounds can be modeled as inequality constraints.

Mixed Integer Nonlinear Programs (MINLP)¶

The most general form is:

\begin{align*} \min_{x,y} \quad & f(x,y) & \text{(nonlinear objective)} \\ \text{s.t.} \quad & g(x,y) = 0 & \text{(equality constraints)} \\ & h(x,y) \leq 0 & \text{(inequality constraints)} \\ & x \in \mathbb{R}^{n}, ~ y \in \{0,1\}^m \end{align*}

(5)

It is much easier to design algorithms to solve MINLPs with the following structure:

\begin{align*} \min_{x,y} \quad & f(x) + g^T y & \text{(nonlinear objective)} \\ \text{s.t.} \quad & A \cdot x + B \cdot y = c & \text{(linear equality constraints)} \\ & g(x) = 0 & \text{(nonlinear equality constraints)} \\ & h(x) \leq 0 & \text{(nonlinear inequality constraints)} \\ & x \in \mathbb{R}^{n}, ~ y \in \{0,1\}^m \end{align*}

(6)

where x are continuous and y are discrete (binary) variables. Notice y only enters linearly into the objective and equality constraint.

Here are common (chemical) engineering optimization problems organized by problem type: optimization_examples