CO 250

Formulations

Given a set A \subseteq \mathbb{R}^n and a function f: A \to \mathbb{R}, our goal is to find x \in A that minimizes or maximizes f.

1. Linear Programming (LP). A is given by linear constraints, and f is a linear function.
2. Integer Programming (IP). We want to maximize or minimize over the integer points in A.
3. Nonlinear Programming (NLP). A is given by non-linear constraints, and f is a non-linear function.

Typical Workflow

1. English language description of practical problem.
2. Develop mathematical model.
3. Feed model and data into a solver.

Constrained Optimization

We consider optimization problems of the form \min\{f(x): g_i(x)\le b_i, 1 \le i \le m, x \in \mathbb{R}^n\} where n, m \in \mathbb{N}, b_i \in \mathbb{R}, and f, g_i are functions with form \mathbb{R}^n \to \mathbb{R}.

Problems are very hard to solve in general, so we focus on special cases. We consider affine functions.

Affine Functions

f: \mathbb{R}^n \to \mathbb{R} is affine if f(x) = a^Tx + \beta for a \in \mathbb{R}^n, \beta \in \mathbb{R}. It is linear if \beta = 0.

An optimization problem \min\{f(x): g_i(x) \le b_i, \forall 1 \le i \le m, x \in \mathbb{R}^n\} is called a linear program if f is affine and g_i is finite number of linear functions.

• Cannot have strict inequalities.

Multiperiod Models

In practice, we make a series of decisions that influence each other. An example of this is multiperiod models.

• Time split into periods.
• Make a decision in each period.
• All decisions affect the final outcome.

IP Models

Fractional solutions are often not desirable. We can force solutions to take only integer values by formulating it was an integer program.

• Integer programs are difficult to solve.

In order to express binary decisions, we introduce a new variable y, such that y = 0 implies the first decision, and y = 1 implies the second.

Example: x_1 + x_2 \ge 5 or x_3 + x_4 \ge 5.

1. x_1 + x_2 \ge 5y.
2. x_3 + x_4 \ge 5(1-y).
3. 0 \le y \le 1.
4. y \in \mathbb{Z}.

We can solve similar situations by using a set of binary variables which sum to a specific value.