Now that we can solve arbitrary LPs, let's see what other problems we can solve with it.

The first real LP is the "Stigler Diet" (1945)

Question: What is the cheapest diet (out of 77 foods) that provides enough calories and a minimum of 8 different nutrients?

The model is very similar to our Muffin Problem

• For each food item $i$, we take a variable $x_i \geq 0$ indicating how many grams of it are included in the diet.
• The cost $c_i$ per gram of food item $i$ is in the objective function.
• We want to minimize the objective function.
• For each nutrient $j$, $b_j$ represents the required daily intake in grams.
• If $a_{ji}$ is the amount of nutrient $j$ in food item $i$, we obtain the constraints:

\[ \sum_i a_{ji} x_i \geq b_j \qquad \forall j \]

Jupyter Example

• Stigler could only solve the problem approximately at the time (the Simplex algorithm was invented 2 years later).
  ($39.93 per year)
• In 1947, a team of 9 people calculated the optimal solution with the Simplex algorithm in 120 person-days
  ($39.69 per year)
• Today, the solution can be calculated using Google Sheets
• The optimal Stigler diet consists of flour, liver, cabbage, spinach, and beans. (Linear Optimization Stigler Style)

Next example: We have 3 Muffin factories with different production capacities in

• Bingen (3000 pieces)
• Gera (1000 pieces)
• Soltau (2000 pieces)

We want to transport the muffins from the factories to the sales markets in a way that minimizes the number of muffin kilometers and meets the demand everywhere.

We assume that the distance between factory $i$ and market $j$ is given as $\text{distance}_{ij}$.

Which variables do we need?

For each factory $i$ and market $j$, we need a variable $x_{ij} \geq 0$ that represents how many muffins should be transported from $i$ to $j$.

Objective function:

From a factory $i$, no more products can be delivered than can be produced there:

At a market $j$, at least as much goods must be transported as there is demand:

The whole model:

New Example:

• We have 23 students and 5 exercise groups with a maximum of 5 people each
• Each person provides a preference between 1 and 10 for each exercise group.
• We want to assign the groups in a way that maximizes the sum of preferences.

Which variables do we need?

For each person $i$ and group $j$, a variable $x_{ij} \geq 0$ is needed, representing whether person $i$ is in group $j$.

Let $p_{ij}$ be the preference of $i$ for group $j$

Objective function:

Every person is only allowed to join one group:

Each group may only be booked by a maximum of 5 people.

Modification: We now want to ensure that the smallest preference is maximized.

We introduce a new variable $x_\text{minpref}$ for the minimum preference.

The new variable must not exceed any of the preferences:

• The new variable $x_\text{minpref}$ is not forced by the constraints to take the smallest preference value.
• However, the objective function pushes it exactly there.

General Modeling Trick:

We can determine the minimum of multiple variables using an auxiliary variable that is maximized in the objective function.

Analogously, the maximum of multiple variables can be determined using minimization in the objective function.

Similar: We have a variable $x$ that can potentially take negative values. We want to minimize its absolute value $|x|$:

The trick here is that for the auxiliary variable, one condition always applies and the other one is irrelevant. The direction of the objective function always determines the correct condition.

Next Example: We are looking for the shortest path from A to D through a network of nodes.

Of course, we can solve this problem differently (e.g. using Dijkstra's algorithm).

As a starting point for more complex models, we still want to model it as an LP.

Most important question: What are the variables?

For an edge $ij$ from node $i$ to $j$, we take a variable $x_{ij} \geq 0$ that indicates whether we traverse the edge.

We want to minimize the sum of the edge weights:

We need to make sure that we leave node A:

\[ x_{AB} + x_{AC} = 1 \]

When entering node B, we also have to leave it again:

\[ x_{AB} + x_{CB} = x_{BC} + x_{BD} \]

Analog: When entering node C, we must also leave it:

\[ x_{AC} + x_{BC} = x_{CB} + x_{CD} \]

Optional: We want to re-enter node D as well.

\[ x_{BD} + x_{CD} = 1 \]

Why "Optional"?

Now we can search for shortest paths in any graph.

Next step: What if we want to send more than one resource through the network?

Now we have not only the costs per edge, but also capacities:

Two different objectives possible:

• Maximize the flow from A to D (ignoring costs).
• Minimize costs for a fixed amount of flow from A to B.

First: Maximize flow from A to D (Max Flow)

As before, we take a variable $x_{ij} \geq 0$ for each edge $ij$, in which we represent the flow from $i$ to $j$.

The constraints work the same way as in the shortest paths: what enters a node must also leave it:

Generally speaking, for a node $i$:

"Flow conservation"

For each individual edge, we need to ensure that the capacity is not exceeded:

As an objective function, we want to maximize the flow leaving node A:

Alternatively, we could also demand that the maximum flow arrives at D.

Now let's consider the costs
(Min-Cost Flow)

Minimize the costs for a flow of 3 units from A to D.

We start from the current model and modify the objective function:

Analogous to the shortest path.

We don't need to touch the constraints for flow conservation and edge capacity.

We need a new condition for A or B (or both):

Generalized flow conservation:

$d_i$ is the difference between the inflow and outflow of the node: Positive for a source and negative for a sink.

In this formulation, we can generally easily incorporate multiple sources and sinks.