01 Intro

Lecture 1

Example Suppose we are selling apples and bananas at a stand. Apples sell for $2 per kilogram, and bananas sell for $1.5 per kilogram. Our stand holds up to 75 kilogram of fruits. Also, there are only 4 square metres of shelf space. Each kilogram of apples / bananas takes up roughly 0.08/ 0.05 square metres of shelf space, respectively. How much of each fruit should we stock to maximize the total sales?

Let $x_1$, $x_2$ be weight of apples, bananas (kg). Define objective function $\max\quad 2x_1 + 1.5x_2$. Add constraints $x_1 + x_2 \leq 75$ for weight, $0.08x_1 + 0.05x_2 \leq 4$ for shelf space, and $x_1, x_2 \geq 0$ for common sense.

Summarize as a linear program: \(\begin{align*}\max\ & 2x_1 + 1.5x_2 \\ \text{subject to}\ & x_1 + x_2 \leq 75 \\ & 0.08x_1 + 0.05x_2 \leq 4 \\ & x_1, x_2 \geq 0 \end{align*}\)

Trial and error:

N.B.: we take domain to be $\R$ since we can take fractional parts of a kilogram of fruit

Plot feasible solutions: bound by convex region defined by axes, $x_1 + x_2 = 23$, and $0.08x_1 + 0.05x_2 = 4$ to give optimal solution at vertex

Course overview

Def [optimization problem]: Given a set of feasible points $A \subseteq \R^n$ and $f : A \to \R$, find some $x \in A$ that minimizes or maximizes the objective value $f(x)$. Composed of decision variables $\vb x \in \R^n$, the objective function $\max f(\vb x)$ or $\min f(\vb x)$, and some constraints of the form $g_i(\vb x) \leq b_i$

Def [affine function]: Function of the form $f(\vb x) = \vb a^T \vb x + b = a_1x_1 + \dotsb + a_nx_n + b$ for constants $\vb a$ and $b$ Def [linear function]: Affine function with $b=0$

Def [linear program]: An optimization problem with affine objective function $f(\vb x)$ and finitely many linear constraint functions $g_i(x) \geq b_i$ (or $\leq b_i$ or $= b_i$) with constant $\vb b$. N.B.: constraints cannot be strict inequalities

Example A company makes 4 types of products, each requiring time on two different machines and two types of labour. The amount of machine time and labour needed to produce one unit of each product along with its sale price are summarized in the following table. Each month, the company can use up to 700 hours on machine 1, and 500 hours on machine 2, with no cost. The company can hire up to 600 hours of skilled labour at $8 per hour, and up to 650 hours of unskilled labour at $6 per hour. How should the company operate to maximize their monthly profit?

Product Machine 1 Machine 2 Skilled labour Unskilled labour Unit sale price
1 11 4 8 7 300
2 7 6 5 8 260
3 6 5 5 7 220
4 5 4 6 4 180

Let $\vb x \in \R^4$ be number of units of products, $y_s$ and $y_u$ be hours of labour hired

Let the objective function be $\max \enspace 300 x_1 + 260 x_2 + 220 x_3 + 180 x_4 - 8y_s - 6y_u$ (unit sale revenue net of labour costs)

Let the constraints be $11x_1 + 7x_2 + 6x_3 + 5x_4 \leq 700$ (machine 1), $4x_1 + 6x_2 + 5x_3 + 4x_4 \leq 500$ (machine 2), $8x_1 + 5x_2 + 5x_3 + 6x_4 = y_s$, $7x_1 + 8x_2 + 7x_3 + 4x_4 = y_u$ (defining $y_s$ and $y_u$), $y_s \leq 600$, $y_u \leq 650$ (labour), and $x_1, x_2, x_3, x_4, y_s, y_u \geq 0$ (non-negativity)

Lecture 2

Example A certain company provides heading oil for the local commnity. They have historical data that helps them predict demand for heating oil in the next four months: 5000, 8000, 9000, 6000 (litres/month) At the beginning of each month, they can purchase oil from the supplier at the current market rate. The projected rates are given: 0.75, 0.72, 0.92, 0.90 ($/litre) There is a storage tank that holds up to 4000 litres of oil, and at the start of month 1, it contains 2000 litres. How should the company buy the required oil to minimize the total money spent?

Let $x_i$ be the amount of oil purchased in the $i$th month, and $y_i$ be the amount of oil in the storage tank at the start of month $i$. Then, we want to minimize $0.75x_1 + 0.72x_2 + 0.92x_3 + 0.9x_4$ . The storage tank constrains us by $y_i \leq 4000$ and the problem gives $y_1 = 2000$. Non-negativity gives $x_i, y_i \geq 0$. For each demand $d_i$, we have $x_i + y_i = d_i + y_{i+1}$. Then, we can write: \(\begin{align*}\min\ & 0.75x_1 + 0.72x_2 + 0.92x_3 + 0.9x_4 \\ \text{s.t.}\ & y_1, y_2, y_3, y_4 \leq 4000 \\ & y_1 = 2000 \\ & x_1 + y_1 = 5000 + y_2 \\ & x_2 + y_2 = 8000 + y_3 \\ & x_3 + y_3 = 9000 + y_4 \\ & x_4 + y_4 = 6000 \\ & x_1,x_2,x_3,x_4,y_1,y_2,y_3,y_4 \geq 0\end{align*}\)

Variation Instead of minimizing the total money spent, suppose we do not have much money to spend each month, and we want to reduce the maximum amount spent in a month.

Let $M = \max {0.75x_1, 0.72x_2, 0.92x_3, 0.9x_4}$. Since $M$ is not linear, we cannot simply put $\min M$ in an LP. Instead, define $m$ with constraints $m \geq 0.75x_1$, $m \geq 0.72x_2$, $m \geq 0.92x_3$, $m \geq 0.9x_4$. Since we are doing $\min m$, we are guaranteed that the optimal solution will give $m = M$ (if $m$ is not $M$, we can make $m$ smaller).

Example Given a set of data points ${(x_i, y_i) : i = 1,\dotsc,n}$ on the plane. Find a line $y = ax + b$ that “best fits” this set of data points.

Define “best fit” as minimizing total vertical distance between points and the line. That is, we must minimize $\sum \abs{ax_i + b - y_i}$, but that is not affine. Define instead the errors $e_i$ associated with the point $i$. We want to constrain $e_i = \abs{ax_i + b - y_i}$, which we can do with $e_i \geq ax_i + b - y_i$ and $e_i \geq y_i - ax_i - b$ since $\abs{x} = \max{x, -x}$. Then, we can use $\min \sum e_i$ as above to get the final LP:

\[\begin{align*}\min \ &\sum e_i \\ \text{s.t.}\ & e_i \geq ax_i + b - y_i \\ & e_i \geq y_i - ax_i - b \end{align*}\]

N.B.: since $e_i$, $e_j$ do not share constraints when $i \neq j$, $\min \sum e_i$ is equivalent to $\min e_1, \dotsc, \min e_n$.

Exercise Modify this to find the best fit parabola. Is this an LP?

Yes, since considering the error function $ax_i^2 + bx_i + c - y_i$ is still linear with respect to the variables for optimization $a$, $b$, and $c$.

Example Consider the job application process where a company has 3 positions available, and there are 4 applicants for these jobs. For each applicant and position, the company assigns a number indicating how well the applicant is suited for the position. The goal is to hire a different applicant for each position to maximize the total suitability.

Lecture 3

Example Consider the job application process where a company has 3 positions available, and there are 4 applicants for these jobs. For each applicant and position, the company assigns a number indicating how well the applicant is suited for the position. The goal is to hire a different applicant for each position to maximize the total suitability.

Positions\Candidates \(M=\mqty(3&5&2&4 \\ 3&1&4&3 \\ 1&4&2&3)\)

Want: For each position, who gets that position Define: Create binary variable $x_{ij}$ for each position $i$ and candidates $j$. Let $x_{ij} = 1$ if position $i$ given to candidate $j$, and $0$ otherwise Objective function: $\max \sum\sum M_{ij}x_{ij}$ Constraints: $\sum_{j} x_{ij} = 1$ for each $i$ (each position filled by exactly one candidate), and $\sum_i x_{ij} \leq 1$ for each $j$ (each candidate takes at most one position), $x_{ij} \geq 0$, $x_{ij} \leq 1$, $x_{ij} \in \Z$ (integrality) \(\begin{align*}\max\ & \sum_{i=0}^3\sum_{j=0}^4 M_{ij}x_{ij} \\ \text{s.t.}\ & \sum_{j=0}^4 x_{ij} = 1 & i = 1,\dotsc,3 \\ &\sum_{i=0}^3 x_{ij} \leq 1 & j = 1,\dotsc,4 \\ & 0 \leq x_{ij} \leq 1, x_{ij} \in \Z\end{align*}\) N.B. We define $x \in {0,1}$ to mean the constraints $0 \leq x \leq 1$ and $x \in \Z$

Example (Knapsack problem) There are 4 types of items that you can put into your backpack. You can take any integer number of units of any item. However, you can only carry a maximum of 40 pounds. Each unit of item you take is also worth a certain amount of money. The goal is to maximize the total value of the items you carry.

Item A B C D
Weight (lbs) 1 7 3 2
Value ($) 10 50 20 15

Let $x_i$, $i = A,B,C,D$ be the number of units of $i$ packed Objective function: $\max 10x_A + 50x_B + 20x_C + 15x_D$ Constraints: $x_A + 7x_B + 3x_C + 2x_D \leq 40$ (weight limit), $x_i \geq 0$, $x_i \in \Z$ (integrality) \(\begin{align*}\max\ && 10x_A + 50x_B + 20x_C + 15x_D \\ \text{s.t.}\ && x_A + 7x_B + 3x_C + 2x_D &\leq 40 \\ && x_A,x_B,x_C,x_D &\geq 0 \\ && x_A,x_B,x_C,x_D &\in \Z\end{align*}\)

Variation Suppose we are allowed to take A only if we take at least one unit of B.

Want: if $x_B = 0$, then we must have $x_A = 0$. If $x_B \geq 1$, no restriction on $A$. Equivalently, add the constraint $x_A \leq x_B \max x_A = 40x_B$. When $x_B = 0$, the RHS goes to $0$ and constrains $x_A = 0$. Otherwise, since $x_B \geq 1$, $40x_B \geq 40$ which is the maximum value of $x_A$, so there are effectively no constraints on $x_A$.

Variation Suppose we want the following conditions to hold:

  1. We carry at least 5 units of items A and/or B; or
  2. We carry at least 7 units of items C and/or D.

Define a binary variable $y$. Want: $y = \begin{cases}1&condition 1 is true\0&condition 2 is true\end{cases}$
If $y = 1$, then $x_A + x_B \geq 5$; if $y = 0$, no restrictions on $x_A$, $x_B$. We can implement this by adding the constraint $x_A + x_B \geq 5y$, since $y = 0$ will send the RHS to $0$

If $y = 0$, then $x_C + x_D \geq 7$; if $y = 1$, no restrictions on $x_C$, $x_D$. Similarly implement with $x_C + x_D \geq 7(1-y)$, since $y=1$ will send the RHS to $0$

Notice that setting $y$ does not force the other condition not to hold, i.e., this implements an inclusive or.

In summary: $x_A + x_B \geq 5y$, $x_C + x_D \geq 7(1-y)$, and $y \in {0,1}$

N.B. When feeding these constraints into an algorithm, ensure that the constraints are truly linear, i.e., move variables to one side. For example, $x_A + x_B - 5y \geq 0$

Exercise Implement an exclusive or of these two conditions

Variation Suppose that the value of item A is $10 for the first 5 units, but any more units beyond that has value $5.

Separate $x_A$ into two variables $x_{A1}$ for first five units and $x_{A2}$ for remainder. Then, we have $x_A=x_{A1}+x_{A2}$ and change the objective function to $10x_{A1} + 5x_{A2} + 50x_B + 20x_C + 15x_C$.

We can create a constraint to force $x_{A2}$ only to go up when $x_{A1}$ is 5 with $x_{A2} \leq (x_{A1} - 4)\max x_{A2}$ which will work in tandem with the non-negativity constraint. This is not actually necessary since the maximum will always fill $x_{A1}$ before $x_{A2}$ because it is worth more (i.e. trading one $x_{A2}$ for $x_{A1}$ will increase the objective function by 5)

In summary: change the objective function and add the constraints $x_A = x_{A1} + x_{A2}$, $x_{A1} \leq 5$, $x_{A1},x_{A2} \geq 0$, $x_{A1}, x_{A2} \in \Z$

Lecture 4

Example (maximum-weight matching) Given graph $G = (V, E)$ and weights $w_e$ for each $e \in E$. Find a matching in $G$ with the maximum edge weight, i.e., maximize $\sum_{e \in M} w_e$.

Define a vector $x \in {0,1}^{\abs{E}}$ by $x_e = 1$ if $e \in M$ and $0$ otherwise. Then, the objective function is $\max w^T x$. To ensure each node appears only once, add constraints $\sum_{e \in \delta(v)} x_e \leq 1$ for each $v \in V$. This is equivalent to taking the incidence matrix $A$ and saying $Ax \leq \mathbb{1}$ This gives us the integer program \(\begin{align*} \max\ & w^T x \\ \text{s.t.}\ & Ax \leq \mathbb{1} \\ & x_e \in \{0,1\} \quad e \in E \end{align*}\)

Lecture 5

Example (shortest path) Given graph $G = (V, E)$, vertices $s$ and $t$, and positive weights $w_e$ for each $e \in E$. Find an $s$,$t$-path $P$ with the minimum edge weight, i.e., minimize $\sum_{e \in P} w_e$.

Define a vector $x \in {0,1}^{\abs{E}}$ by $x_e = 1$ if $e \in P$ and $0$ otherwise. The objective function is $\min w^T x$. Need to constrain $x$ into a path: use cuts.

We get a constraint $\sum_{e \in \delta(W)} x_e \geq 1$ for all $s,t$-cuts $\delta(W)$ (that is, for all $W \subset V$ with $s \in W$ and $t\not\in W$)

Minimizing the edge weights will ensure that the extraneous edges are optimized away and the $s,t$-path remains so long as the edge weights are all positive

This gives us a final IP of \(\begin{align*} \min\ & w^T x \\ \text{s.t.}\ & \sum_{e \in \delta(W)} x_e \geq 1 & \text{$\delta(W)$ an $s,t$-cut} \\ & x_e \geq 0, x_e \in \Z & e \in E \end{align*}\)

Example Among all the points $x$ that satisfy $Ax \leq b$, find one that is closest to the target point $\bar x$

We can take the norm and minimize $\norm{x - \bar x} = \sqrt{\sum(x_i-\bar x_i)^2}$. This gives us the non-linear program $\min \norm{x - \bar x}, \text{s.t.\ } Ax \leq b$.

Lecture 6

02 Solving LPs

Lecture 7

Simplex Preparation

Example Find an equivalent LP in SEF \(\begin{align*} \min & (-1,2,-3)x \\ \text{s.t. } & \mqty(1&5&3\\2&-1&2\\1&2&-1)\mqty(x_1\\x_2\\x_3)\mqty{\leq\\\geq\\=}\mqty(5\\4\\2) \\ &x_1,x_2 \geq 0 \end{align*}\)

Lecture 8

Canonical form

Lecture 9

Simplex Algorithm

Lecture 10

Lecture 11

Geometric simplex

Lecture 12


Lecture 13: Geometry of Simplex (Theory)

Lecture 14

04 Duality

Lecture 15

Lecture 16

Summary of weak duality theorem results

Dual \ Primal Optimal Unbounded Infeasible
Infeasible ✓ (edge case)

Lecture 17

Lecture 18

Lecture 19

Lecture 20

06 Solving IPs

Lecture 21

### Lecture 22

07 Solving NLPs

Lecture 23

Lecture 24