Cheatsheet

280. Cheatsheet

281. Linear Programming

Function Type	Method	Example
Maximization to Minimization	$\begin{aligned} max & 𝑓 (𝑥) & ⟺ \\ min & - & 𝑓 (𝑥) \end{aligned}$	$\begin{aligned} max & 3 𝑥 + & 2 𝑦 ⟺ \\ min - & 3 𝑥 - & 2 𝑦 \end{aligned}$
$\geq$ Constraint to $\leq$	$\begin{aligned} 𝑔_{𝑖} (𝑥) & \geq & 𝑏_{𝑖} & ⟺ \\ - & 𝑔_{𝑖} (𝑥) & \leq & - & 𝑏_{𝑖} \end{aligned}$	$\begin{aligned} 𝑥 + & 𝑦 & \geq & 5 & ⟺ \\ - & 𝑥 - & 𝑦 & \leq & - & 5 \end{aligned}$
Equality Constraint	$\begin{aligned} 𝑔_{𝑖} (𝑥) & = 𝑏_{𝑖} ⟺ \\ 𝑔_{𝑖} (𝑥) & \geq 𝑏_{𝑖} \land \\ 𝑔_{𝑖} (𝑥) & \leq 𝑏_{𝑖} \end{aligned}$	$\begin{aligned} 𝑥 + 𝑦 & = 4 ⟺ \\ 𝑥 + 𝑦 & \geq 4 \land \\ 𝑥 + 𝑦 & \leq 4 \end{aligned}$
Slack Variable		$𝑥 + 𝑦 \leq 6$ Add slack variable $𝑠 \geq 0$ : $𝑥 + 𝑦 + 𝑠 = 6$ $𝑠$ is how much less is being used than the maximum limit of 6
Surplus Variable		$𝑥 + 𝑦 \geq 6$ Add slack variable $𝑠 \geq 0$ : $𝑥 + 𝑦 - 𝑠 = 6$ $𝑠$ is the amount above the minimum required level 6

282. Integer Programming

Function Type	Method	Example
At least $𝑘$ of the items in $𝑆$	$\sum_{𝑖 \in 𝑆} 𝑥_{𝑖} \geq 𝑘$	Produce at least 3 products: $\sum_{𝑖 \in 𝑆} 𝑥_{𝑖} \geq 3$
At most $𝑘$ of the items in $𝑆$	$\sum_{𝑖 \in 𝑆} 𝑥_{𝑖} \leq 𝑘$	Open at most 2 facilities: $\sum_{𝑖 \in 𝑆} 𝑥_{𝑖} \leq 2$
Exactly $𝑘$ of the items in $𝑆$	$\sum_{𝑖 \in 𝑆} 𝑥_{𝑖} = 𝑘$	Choose exactly one location: $\sum_{𝑖 \in 𝑆} 𝑥_{𝑖} = 1$
If $𝑥_{𝑎} = 1$ , then $𝑥_{𝑏} = 1$	$𝑥_{𝑎} \leq 𝑥_{𝑏}$	If project A is done, project B must also be done
If $𝑥_{𝑎} = 1$ , then $𝑥_{𝑏} = 0$	$𝑥_{𝑎} + 𝑥_{𝑏} \leq 1$	Projects A and B are mutually exclusive
If $𝑥_{𝑎} = 1$ , then $𝑥_{𝑏} + 𝑥_{𝑐} \leq 0$	$𝑥_{𝑏} + 𝑥_{𝑐} \leq 𝑀 (1 - 𝑥_{𝑎})$	If project A is selected, neither project B nor C can be selected
If $𝑥_{𝑗} = 0$ , then at least $𝑘$ items in $𝑆$ must be selected	$\sum_{𝑖 \in 𝑆} 𝑥_{𝑖} \geq 𝑘 (1 - 𝑥_{𝑗})$	You have a main server represented by $𝑥_{𝑗}$ . If it is down or not used ( $𝑥_{𝑗} = 0$ ), then at least $𝑘$ backup servers (in set $𝑆$ ) must be activated
At least $𝑘$ of $𝑚$ constraints satisfied	$\begin{matrix} 𝑧_{𝑖} = {\begin{cases} 1 if 𝑔_{𝑖} (𝑥) \leq 𝑏_{𝑖} enforced \\ 0 if 𝑔_{𝑖} (𝑥) \leq 𝑏_{𝑖} relaxed \end{cases} \\ for 𝑖 = 1, \dots, 𝑚 \\ 𝑔_{𝑖} (𝑥) - 𝑏_{𝑖} \leq 𝑀_{𝑖} (1 - 𝑧_{𝑖}) \forall 𝑖 = 1, \dots, 𝑚 \\ \sum_{𝑖 = 1}^{𝑚} 𝑧_{𝑖} \geq 𝑘 \\ 𝑀_{𝑖} \geq max_{𝑥} (𝑔_{𝑖} (𝑥) - 𝑏_{𝑖}) \end{matrix}$	Enforce any $𝑘$ of the $𝑚$ constraints by relaxing up to $𝑚 - 𝑘$ of them
Fixed (Setup) Costs	$𝑦 = {\begin{cases} 1 if is used \\ 0 if not used \end{cases}$ $\begin{aligned} 𝑥 & \geq 0 \\ 𝑥 & \leq 𝑀 \cdot 𝑦 \end{aligned}$	If facility is used ( $𝑦 = 1$ ), then allow production up to $𝑀$ ; else $𝑥 = 0$
Balanced Flow	$\begin{matrix} \sum_{\begin{matrix} 𝑖 \in 𝑉 \\ 𝑖 \neq 𝑘 \end{matrix}} 𝑥_{𝑖 𝑘} = 𝑑_{𝑘} \\ \sum_{\begin{matrix} 𝑖 \in 𝑉 \\ 𝑖 \neq 𝑘 \end{matrix}} 𝑥_{𝑗 𝑘} = 𝑑_{𝑘} \end{matrix}$	Each node $𝑘$ receives and sends exactly $𝑑_{𝑘}$ units of flow. If $𝑑_{𝑘} = 1$ , this is a TSP or assignment
Unbalanced Flow	$\sum_{\begin{matrix} 𝑖 \in 𝑉 \\ 𝑖 \neq 𝑘 \end{matrix}} 𝑥_{𝑖 𝑘} - \sum_{\begin{matrix} 𝑖 \in 𝑉 \\ 𝑖 \neq 𝑘 \end{matrix}} 𝑥_{𝑗 𝑘} = 𝑏_{𝑘}$	Each node $𝑘$ has net inflow minus outflow equal to $𝑏_{𝑘}$ : $𝑏_{𝑘} > 0$ : demand $𝑏_{𝑘} < 0$ : supply $𝑏_{𝑘} = 0$ : transshipment
Subtours (MTZ)	$\begin{matrix} 1 \leq 𝑢_{𝑖} \leq 𝑛 - 1 \forall 𝑖 = 2, \dots, 𝑛 \\ 𝑢_{𝑖} - 𝑢_{𝑗} + (𝑛 - 1) 𝑥_{𝑖 𝑗} \leq 𝑛 - 2 \\ \forall 𝑖 \neq 𝑗, 𝑖, 𝑗 \in {2, \dots, 𝑛} \end{matrix}$
Subtours (SEC)	$\sum_{\begin{matrix} 𝑖 \in 𝑆, 𝑗 \in 𝑆 \\ 𝑗 \neq 𝑗 \end{matrix}} 𝑥_{𝑖 𝑗} \leq \| 𝑆 \| - 1 \forall 𝑆 \subseteq 𝑉, \| 𝑆 \| \geq 2$	For every subset $𝑆$ of the nodes $𝑉$ that has at least 2 nodes, the total number of arcs (or paths) within that subset — from node $𝑖$ to node $𝑗$ , where $𝑖 \neq 𝑗$ must be less than or equal to $\| 𝑆 \| - 1$

283. Non-Linear Programming

Function Type	Example	Linearization Method	Example
Binary $\times$ Binary Constraint	$\begin{matrix} 𝑧 = 𝑥 \cdot 𝑦 \\ 𝑥, 𝑦 \in {0, 1} \end{matrix}$	$\begin{aligned} 𝑧 & \leq 𝑥 \\ 𝑧 & \leq 𝑦 \\ 𝑧 & \geq 𝑥 + 𝑦 - 1 \\ 𝑥 & \in {0, 1} \end{aligned}$	$\begin{matrix} 𝑧 = 1 ⟺ \\ 𝑥 = 𝑦 = 1 \end{matrix}$
Binary $\times$ Continuous Constraint	$\begin{aligned} 𝑧 & = 𝑥 \cdot 𝑦 \\ 𝑥 & \in {0, 1} \\ 𝑦 & \in [𝐿, 𝑈] \end{aligned}$	$\begin{aligned} 𝑧 & \leq 𝑈 𝑥 \\ 𝑧 & \geq 𝐿 𝑥 \\ 𝑧 & \leq 𝑦 - 𝐿 (1 - 𝑥) \\ 𝑧 & \geq 𝑦 - 𝑈 (1 - 𝑥) \end{aligned}$
Continuous $\times$ Continuous Constraint	$\begin{matrix} 𝑧 = 𝑥 \cdot 𝑦 \\ 𝑥 \in [𝐿_{𝑥}, 𝑈_{𝑥}] \\ 𝑦 \in [𝐿_{𝑦}, 𝑈_{𝑦}] \end{matrix}$	$\begin{matrix} 𝑧 \geq 𝐿_{𝑥} 𝑦 + 𝐿_{𝑦} 𝑥 - 𝐿_{𝑥} 𝐿_{𝑦} \\ 𝑧 \geq 𝑈_{𝑥} 𝑦 + 𝑈_{𝑦} 𝑥 - 𝑈_{𝑥} 𝑈_{𝑦} \\ 𝑧 \geq 𝐿_{𝑥} 𝑦 + 𝑈_{𝑦} 𝑥 - 𝐿_{𝑥} 𝑈_{𝑦} \\ 𝑧 \geq 𝑈_{𝑥} 𝑦 + 𝐿_{𝑦} 𝑥 - 𝑈_{𝑥} 𝐿_{𝑦} \end{matrix}$
Absolute Value	$𝑧 = \| 𝑥 \|$	$\begin{matrix} 𝑧 \geq 𝑥 \\ 𝑧 \geq - 𝑥 \end{matrix}$	$\begin{matrix} 𝑧 = \| 𝑥_{1} - 𝑥_{2} \| \\ ⟺ \\ 𝑧 \geq 𝑥_{1} - 𝑥_{2} \\ 𝑧 \geq 𝑥_{2} - 𝑥_{1} \end{matrix}$
Max Constraint	$𝑦 \geq max (𝑥_{1}, \dots, 𝑥_{𝑛})$	$𝑦 \geq 𝑥_{1} \forall 𝑖 = 1, \dots, 𝑛$	$\begin{matrix} 𝑦 + 𝑥_{1} + 3 \geq max (𝑥_{1} - 𝑥_{3}, 2 𝑥_{2} + 4) \\ ⟺ \\ {\begin{cases} 𝑦 + 𝑥_{1} + 3 \geq 𝑥_{1} - 𝑥_{3} \\ 𝑦 + 𝑥_{1} + 3 \geq 2 𝑥_{2} + 4 \end{cases} \end{matrix}$
Min Constraint	$𝑦 \leq min (𝑥_{1}, \dots, 𝑥_{𝑛})$	$𝑦 \leq 𝑥_{1} \forall 𝑖 = 1, \dots, 𝑛$	$\begin{matrix} 𝑦 + 𝑥_{1} \leq min (𝑥_{1} - 𝑥_{3}, 2 𝑥_{2} + 4, 0) \\ ⟺ \\ {\begin{cases} 𝑦 + 𝑥_{1} \leq 𝑥_{1} - 𝑥_{3} \\ 𝑦 + 𝑥_{1} \leq 2 𝑥_{2} + 4 \\ 𝑦 + 𝑥_{1} \leq 0 \end{cases} \end{matrix}$
Max Min Objective	$max min (𝑥_{1}, \dots, 𝑥_{𝑛})$	$\begin{aligned} 𝑦 & = min (𝑥_{1}, \dots, 𝑥_{𝑛}) \\ 𝑦 & \leq 𝑥_{𝑖} \forall 𝑖 = 1, \dots, 𝑛 \end{aligned}$
Min Max Objective	$min max (𝑥_{1}, \dots, 𝑥_{𝑛})$	$\begin{aligned} 𝑦 & = max (𝑥_{1}, \dots, 𝑥_{𝑛}) \\ 𝑦 & \geq 𝑥_{𝑖} \forall 𝑖 = 1, \dots, 𝑛 \end{aligned}$
Min Min Objective	$min min (𝑥_{1}, \dots, 𝑥_{𝑛})$
Max Max Objective	$max max (𝑥_{1}, \dots, 𝑥_{𝑛})$

284. Algorithms

Algorithm	Update Rule
Gradient Descent	$𝑥_{𝑘 + 1} = 𝑥_{𝑘} - 𝛼 \nabla 𝑓 (𝑥_{𝑘})$
Newton’s Method	$𝑥_{𝑘 + 1} = 𝑥_{𝑘} - {[\nabla^{2} 𝑓 (𝑘)]}^{- 1} \nabla 𝑓 (𝑥_{𝑘})$

Newton’s Method

Approximation	Taylor Expansion	Newton Update
Linear (1D)	$𝑓^{'} (𝑥_{𝑘 + 1}) \approx 𝑓^{'} (𝑥_{𝑘}) + 𝑓^{″} (𝑥_{𝑘}) (𝑥_{𝑘 + 1} - 𝑥_{𝑘})$	$𝑥_{𝑘 + 1} = 𝑥_{𝑘} - \frac{𝑓^{'} (𝑥_{𝑘})}{𝑓^{″} (𝑥_{𝑘})}$
Linear (nD)	$\nabla 𝑓 (𝐱_{𝑘 + 1}) \approx \nabla 𝑓 (𝐱_{𝑘}) + 𝐻_{𝑘} (𝐱_{𝑘 + 1} - 𝐱_{𝑘})$	$𝐱_{𝐤 + 1} = 𝐱_{𝑘} - 𝐻_{𝑘}^{- 1} \nabla 𝑓 (𝐱_{𝑘})$
Quadratic (1D)	$\begin{matrix} 𝑓_{𝑄} (𝑥) = \\ 𝑓 (𝑥_{𝑘}) + 𝑓^{'} (𝑥_{𝑘}) (𝑥 - 𝑥_{𝑘}) + \frac{1}{2} 𝑓^{″} (𝑥_{𝑘}) {(𝑥 - 𝑥_{𝑘})}^{2} \end{matrix}$	$𝑥_{𝑘 + 1} = 𝑥_{𝑘} - \frac{𝑓^{'} (𝑥_{𝑘})}{𝑓^{″} (𝑥_{𝑘})}$
Quadratic (nD)	$\begin{matrix} 𝑚_{𝑘} (𝐩) = 𝑓 (𝐱_{𝑘}) + \nabla {𝑓 (𝐱_{𝑘})}^{𝑇} 𝐩 + \frac{1}{2} 𝐩^{𝑇} 𝐻_{𝑘} 𝐩 \\ 𝐩 = 𝐱 - 𝐱_{𝑘} \end{matrix}$	$𝐱_{𝐤 + 1} = 𝐱_{𝑘} - 𝐻_{𝑘}^{- 1} \nabla 𝑓 (𝐱_{𝑘})$