Linear Programming

CSE 440: Introduction to Artificial Intelligence

Vishnu Boddeti

October 01, 2020

Content Credits: CMU AI, http://ai.berkeley.edu

What to eat?

• We are trying healthy by finding the optimal amount of food to purchase.
• We can choose the amount of stir-fry (ounce) and boba (fluid ounces).

Optimization

What to eat?: Constraints

• We are trying healthy by finding the optimal amount of food to purchase.
• We can choose the amount of stir-fry (ounce) and boba (fluid ounces).

Constraint Satisfaction Problems

Map Coloring $$ \begin{eqnarray} Any && \mathbf{x} \\ s.t. && \mathbf{x} \mbox{ satisfies constraints } \end{eqnarray} $$

What to eat?: Costs

• We are trying healthy by finding the optimal amount of food to purchase.
• We can choose the amount of stir-fry (ounce) and boba (fluid ounces).

Optimization Formulation

Optimization Formulation

Optimization Formulation

Optimization Formulation

Diet Problem $$ \begin{eqnarray} \min_{\mathbf{x}} && c_1x_1 + c_2x_2 \\ s.t. && a_{1,1}x_1 + a_{1,2}x_2 \geq b_1 \\ && a_{2,1}x_1 + a_{2,2}x_2 \leq b_2 \\ && a_{3,1}x_1 + a_{3,2}x_2 \leq b_3 \\ && a_{4,1}x_1 + a_{4,2}x_2 \geq b_4 \end{eqnarray} $$

$$A=\begin{bmatrix}100 & 50 \\ 100 & 50 \\ 3 & 4 \\ 20 & 70\end{bmatrix} \mbox{ } b=\begin{bmatrix}2000 \\ 2500 \\ 100 \\ 700\end{bmatrix} \mbox{ and } c=\begin{bmatrix}1 \\ 0.5\end{bmatrix}$$

Optimization Formulation

Diet Problem $$ \begin{eqnarray} \min_{\mathbf{x}} && \mathbf{c}^T\mathbf{x} \\ s.t. && a_{1,1}x_1 + a_{1,2}x_2 \geq b_1 \\ && a_{2,1}x_1 + a_{2,2}x_2 \leq b_2 \\ && a_{3,1}x_1 + a_{3,2}x_2 \leq b_3 \\ && a_{4,1}x_1 + a_{4,2}x_2 \geq b_4 \end{eqnarray} $$

$$A=\begin{bmatrix}100 & 50 \\ 100 & 50 \\ 3 & 4 \\ 20 & 70\end{bmatrix} \mbox{ } b=\begin{bmatrix}2000 \\ 2500 \\ 100 \\ 700\end{bmatrix} \mbox{ and } c=\begin{bmatrix}1 \\ 0.5\end{bmatrix}$$

Optimization Formulation

Diet Problem $$ \begin{eqnarray} \min_{\mathbf{x}} && \mathbf{c}^T\mathbf{x} \\ s.t. && -a_{1,1}x_1 - a_{1,2}x_2 \leq -b_1 \\ && a_{2,1}x_1 + a_{2,2}x_2 \leq b_2 \\ && a_{3,1}x_1 + a_{3,2}x_2 \leq b_3 \\ && -a_{4,1}x_1 - a_{4,2}x_2 \leq -b_4 \end{eqnarray} $$

$$A=\begin{bmatrix}100 & 50 \\ 100 & 50 \\ 3 & 4 \\ 20 & 70\end{bmatrix} \mbox{ } b=\begin{bmatrix}2000 \\ 2500 \\ 100 \\ 700\end{bmatrix} \mbox{ and } c=\begin{bmatrix}1 \\ 0.5\end{bmatrix}$$

Optimization Formulation

Diet Problem $$ \begin{eqnarray} \min_{\mathbf{x}} && \mathbf{c}^T\mathbf{x} \\ s.t. && a_{1,1}x_1 + a_{1,2}x_2 \leq b_1 \\ && a_{2,1}x_1 + a_{2,2}x_2 \leq b_2 \\ && a_{3,1}x_1 + a_{3,2}x_2 \leq b_3 \\ && a_{4,1}x_1 + a_{4,2}x_2 \leq b_4 \end{eqnarray} $$

$$A=\begin{bmatrix}-100 & -50 \\ 100 & 50 \\ 3 & 4 \\ -20 & -70\end{bmatrix} \mbox{ } b=\begin{bmatrix}-2000 \\ 2500 \\ 100 \\ -700\end{bmatrix} \mbox{ and } c=\begin{bmatrix}1 \\ 0.5\end{bmatrix}$$

Optimization Formulation

Diet Problem $$ \begin{eqnarray} \min_{\mathbf{x}} && \mathbf{c}^T\mathbf{x} \\ s.t. && \mathbf{A}\mathbf{x} \preceq \mathbf{b} \end{eqnarray} $$

$$A=\begin{bmatrix}-100 & -50 \\ 100 & 50 \\ 3 & 4 \\ -20 & -70\end{bmatrix} \mbox{ } b=\begin{bmatrix}-2000 \\ 2500 \\ 100 \\ -700\end{bmatrix} \mbox{ and } c=\begin{bmatrix}1 \\ 0.5\end{bmatrix}$$

Quiz 1

• What has to increase to add more nutrition constraints?

Quiz 2

• What has to increase to add more menu items?

Quiz 3

• If $\mathbf{A}\in\mathbb{R}^{M\times N}$, which of the following also equals $N$?

• Select all that apply
• length $\mathbf{x}$
• length $\mathbf{c}$
• length $\mathbf{b}$

Linear Programming

• Linear objective with linear constraints

$$ \begin{eqnarray} \min_{\mathbf{x}} && \mathbf{c}^T\mathbf{x} \\ s.t. && \mathbf{A}\mathbf{x} \preceq \mathbf{b} \end{eqnarray} $$

• As opposed to general optimization

$$ \begin{eqnarray} \min_{\mathbf{x}} && f_0(\mathbf{x}) \\ s.t. && f_i(\mathbf{x}) \leq \mathbf{0}, i=1,\dots,M \\ && \mathbf{a}_i^T\mathbf{x} = \mathbf{b}_i, i=1,\dots,P \end{eqnarray} $$

Linear Programming

• Different formulations

Optimization

Graphics Representation

• What shape does this inequality represent?

Quiz 4

• What is the relationship between the half plane: $a_1x_1 + a_2x_2 \leq b_1$ and the vector: $[a_1,a_2]^T$

Quiz 5

• Given the cost vector $[c_1,c_2]^T$ and initial point $x^{(0)}$, which unit vector step $\Delta\mathbf{x}$ will cause $x^{(1)}=x^{(0)}+\Delta\mathbf{x}$ to have the lowest cost $\mathbf{c}^T\mathbf{x}^{(1)}$?

Cost Contours

• Given the cost vector $[c_1,c_2]^T$ where will,
• $\mathbf{c}^T\mathbf{x}=0$
• $\mathbf{c}^T\mathbf{x}=1$
• $\mathbf{c}^T\mathbf{x}=2$
• $\mathbf{c}^T\mathbf{x}=-1$
• $\mathbf{c}^T\mathbf{x}=-2$

LP Graphical Representation

• Inequality Form

• Start with no constraints
• Add one constraint at a time

Quiz 6

• True or False: Minimizing an LP with exactly one constraint, will always have a minimum objective at $-\infty$.

Optimization

What to eat?

• We are trying healthy by finding the optimal amount of food to purchase.
• We can choose the amount of stir-fry (ounce) and boba (fluid ounces).

Optimization Formulation

Diet Problem $$ \begin{eqnarray} \min_{\mathbf{x}} && \mathbf{c}^T\mathbf{x} \\ s.t. && \mathbf{A}\mathbf{x} \preceq \mathbf{b} \end{eqnarray} $$

$$A=\begin{bmatrix}-100 & -50 \\ 100 & 50 \\ 3 & 4 \\ -20 & -70\end{bmatrix} \mbox{ } b=\begin{bmatrix}-2000 \\ 2500 \\ 100 \\ -700\end{bmatrix} \mbox{ and } c=\begin{bmatrix}1 \\ 0.5\end{bmatrix}$$

Solving an LP