Linear Programming
CSE 440: Introduction to Artificial Intelligence
Vishnu Boddeti
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).
- Health Goals
- $2000 \leq Calories \leq 2500$
- $Sugar \leq 100g$
- $Calcium \geq 700mg$
| Food |
Cost |
Calories |
Sugar |
Calcium |
| stir-fry (per oz) |
1 |
100 |
3 |
20 |
| Boba (per fl oz) |
0.5 |
50 |
4 |
70 |
- What is the cheapest way to stay "healthy" with this menu?
- How much stir-fry (ounce) and boba (fluid ounces) should we buy?
Can Search Algorithms Help?
- Essence of search algorithms:
- explore all nodes in search tree until you reach the one you want
- use additional information to avoid search all nodes
- Can we adopt a similar strategy here?
Optimization
Problem Description
Optimization Representation
$$\begin{eqnarray}
\min_{\mathbf{x}} && \mathbf{c}^T\mathbf{x} \\
s.t. && \mathbf{A}\mathbf{x} \preceq \mathbf{b}
\end{eqnarray}$$
Graphical Representation
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).
- Health Goals
- $2000 \leq Calories \leq 2500$
- $Sugar \leq 100g$
- $Calcium \geq 700mg$
| Food |
Cost |
Calories |
Sugar |
Calcium |
| stir-fry (per oz) |
1 |
100 |
3 |
20 |
| Boba (per fl oz) |
0.5 |
50 |
4 |
70 |
- What is the cheapest way to stay "healthy" with this menu?
- How much stir-fry (ounce) and boba (fluid ounces) should we buy?
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).
- Health Goals
- $2000 \leq Calories \leq 2500$
- $Sugar \leq 100g$
- $Calcium \geq 700mg$
| Food |
Cost |
Calories |
Sugar |
Calcium |
| stir-fry (per oz) |
1 |
100 |
3 |
20 |
| Boba (per fl oz) |
0.5 |
50 |
4 |
70 |
- What is the cheapest way to stay "healthy" with this menu?
- How much stir-fry (ounce) and boba (fluid ounces) should we buy?
Optimization Formulation
- Health Goals
- $2000 \leq Calories \leq 2500$
- $Sugar \leq 100g$
- $Calcium \geq 700mg$
| Food |
Cost |
Calories |
Sugar |
Calcium |
| stir-fry (per oz) |
1 |
100 |
3 |
20 |
| Boba (per fl oz) |
0.5 |
50 |
4 |
70 |
Diet Problem
$$
\begin{eqnarray}
\min_{\mathbf{x}} && cost(\mathbf{x}) \\
s.t. && \mathbf{x} \mbox{ satisfies constraints }
\end{eqnarray}
$$
Optimization Formulation
- Health Goals
- $2000 \leq Calories \leq 2500$
- $Sugar \leq 100g$
- $Calcium \geq 700mg$
| Food |
Cost |
Calories |
Sugar |
Calcium |
| stir-fry (per oz) |
1 |
100 |
3 |
20 |
| Boba (per fl oz) |
0.5 |
50 |
4 |
70 |
Diet Problem
$$
\begin{eqnarray}
\min_{\mathbf{x}} && cost(\mathbf{x}) \\
s.t. && calories(x) \leq limit \\
&& calories(x) \geq limit \\
&& sugar(\mathbf{x}) \leq limit \\
&& calcium(\mathbf{x}) \geq limit
\end{eqnarray}
$$
Optimization Formulation
- Health Goals
- $2000 \leq Calories \leq 2500$
- $Sugar \leq 100g$
- $Calcium \geq 700mg$
| Food |
Cost |
Calories |
Sugar |
Calcium |
| stir-fry (per oz) |
1 |
100 |
3 |
20 |
| Boba (per fl oz) |
0.5 |
50 |
4 |
70 |
Diet Problem
$$
\begin{eqnarray}
\min_{\mathbf{x}} && 1x_1 + 0.5x_2 \\
s.t. && 100x_1 + 50x_2 \geq 2000 \\
&& 100x_1 + 50x_2 \leq 2500 \\
&& 3x_1 + 4x_2 \leq 100 \\
&& 20x_1 + 70x_2 \geq 700
\end{eqnarray}
$$
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}$$
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
Inequality Form
$$
\begin{eqnarray}
\min_{\mathbf{x}} && \mathbf{c}^T\mathbf{x} \\
s.t. && \mathbf{A}\mathbf{x} \preceq \mathbf{b} \\
&& \mbox{ }
\end{eqnarray}
$$
General Form
$$
\begin{eqnarray}
\min_{\mathbf{x}} && \mathbf{c}^T\mathbf{x} + d \\
s.t. && \mathbf{G}\mathbf{x} \preceq \mathbf{h} \\
&& \mathbf{A}\mathbf{x} = \mathbf{b} \\
\end{eqnarray}
$$
Standard Form
$$
\begin{eqnarray}
\min_{\mathbf{x}} && \mathbf{c}^T\mathbf{x} \\
s.t. && \mathbf{A}\mathbf{x} \preceq \mathbf{b} \\
&& \mathbf{x} \succeq \mathbf{0}
\end{eqnarray}
$$
Optimization
Problem Description
Optimization Representation
$$\begin{eqnarray}
\min_{\mathbf{x}} && \mathbf{c}^T\mathbf{x} \\
s.t. && \mathbf{A}\mathbf{x} \preceq \mathbf{b}
\end{eqnarray}$$
Graphical Representation
Graphics Representation
- What shape does this inequality represent?
$$
a_1x_1 + a_2x_2 \leq b_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
$$
\begin{eqnarray}
\min_{\mathbf{x}} && \mathbf{c}^T\mathbf{x} \\
s.t. && \mathbf{A}\mathbf{x} \preceq \mathbf{b}
\end{eqnarray}
$$
- Start with no constraints
- Add one constraint at a time
Optimization
Problem Description
Optimization Representation
$$\begin{eqnarray}
\min_{\mathbf{x}} && \mathbf{c}^T\mathbf{x} \\
s.t. && \mathbf{A}\mathbf{x} \preceq \mathbf{b}
\end{eqnarray}$$
Graphical Representation
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).
- Health Goals
- $2000 \leq Calories \leq 2500$
- $Sugar \leq 100g$
- $Calcium \geq 700mg$
| Food |
Cost |
Calories |
Sugar |
Calcium |
| stir-fry (per oz) |
1 |
100 |
3 |
20 |
| Boba (per fl oz) |
0.5 |
50 |
4 |
70 |
- What is the cheapest way to stay "healthy" with this menu?
- How much stir-fry (ounce) and boba (fluid ounces) should we buy?
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
- Solutions are at feasible intersections of constraint boundaries!!
