Model real decisions with linear and integer programming, networks, queues, simulation and decision trees, then present the results so managers act on them.

Optimization & Operations Research

## Why it matters

Many business decisions are not "how much" but "yes or no": open this warehouse or not, fund this project or not, assign this nurse to this shift or not. Fractions make no sense for them. **Integer programming** (IP) adds the rule that some variables must be whole numbers, and **binary variables** (0 or 1) turn logic such as "if A then B" into constraints a solver understands. Most of the high-value OR work in industry, from airline crew scheduling to supply-chain design, is integer programming.

## Integer, binary and mixed models

- **Integer variable**: `x` in {0, 1, 2, ...}, for example the number of trucks.
- **Binary variable**: `y` in {0, 1}, a yes/no decision.
- **Mixed-integer program (MIP)**: some variables are continuous, some integer.

Why not just solve the LP and round? Because rounding can be infeasible or far from optimal. Take `maximize x + y` subject to `-2x + 2y >= 1` and `-8x + 10y <= 13`, with integer `x, y >= 0`. The LP optimum is `x = 4, y = 4.5`. Rounding `y` to 4 breaks the first constraint and rounding up to 5 breaks the second; the true integer optimum is `x = 1, y = 2`. The LP relaxation still helps: its value is an upper bound (for maximization) on the best integer value.

## Modelling logic with binary variables

Let `x_A, x_B, ...` be 1 if a project is chosen and 0 if not.

| rule in words | constraint |
|---|---|
| choose at most k of a group | `x_C + x_D + x_E <= k` |
| C and D exclude each other | `x_C + x_D <= 1` |
| exactly one of C, D | `x_C + x_D = 1` |
| A needs B (if A then B) | `x_A <= x_B` |
| A and B go together | `x_A = x_B` |

**Fixed costs** use a "big-M" link. If a plant produces `q` units only when it is open (`y = 1`) and can make at most `M` units, write `q <= M * y`. Then the cost `F * y + v * q` charges the fixed cost `F` only when the plant is used. Choose `M` as the real capacity, not a huge number: a too-large `M` makes the LP relaxation weak and the solver slow.

## Worked example: capital budgeting

A company has 12 ($M) to invest in five projects:

| project | cost | NPV |
|---|---|---|
| A | 5 | 9 |
| B | 4 | 7 |
| C | 3 | 5 |
| D | 6 | 10 |
| E | 2 | 3 |

A uses software that B builds, so A needs B. C and D compete for the same team, so at most one of them.

```text
maximize   9x_A + 7x_B + 5x_C + 10x_D + 3x_E
subject to 5x_A + 4x_B + 3x_C +  6x_D + 2x_E <= 12   (budget)
           x_A <= x_B                                 (A needs B)
           x_C + x_D <= 1                             (C or D)
           x_A, ..., x_E in {0, 1}
```

With five binary variables there are only `2^5 = 32` portfolios, so you can check them all. The best is {A, B, C}: cost 12, NPV 21. A greedy rule ("pick the best NPV per dollar first") picks A (1.8 per dollar) but then must also take B, and it can easily miss the optimum on other data. With a budget of 15 the answer changes to {A, B, D} with NPV 26.

## How solvers handle integers: branch and bound

Enumeration doubles with every extra binary variable: 50 projects means about 10^15 portfolios. Solvers use **branch and bound** instead:

1. Solve the LP relaxation (allow fractions). If the answer happens to be integer, you are done.
2. Otherwise pick a fractional variable, say `x = 2.4`, and **branch** into two subproblems: one with `x <= 2`, one with `x >= 3`.
3. Keep the best integer solution found so far (the **incumbent**).
4. **Bound**: any subproblem whose LP value cannot beat the incumbent is pruned without exploring it.

Modern solvers add cutting planes, presolve and heuristics on top, and report a **MIP gap**: how far the incumbent might be from the best possible value. A gap of 1% is often good enough for a business decision.

In PuLP, a binary variable is one argument away: `pulp.LpVariable("x_A", cat="Binary")`.

## Common mistakes

- **Rounding an LP answer** and calling it optimal (or even feasible).
- **Reversing an implication.** "A needs B" is `x_A <= x_B`, not `x_B <= x_A`.
- **Huge big-M values.** They cause weak bounds and numerical trouble.
- **Too many integer variables.** Keep continuous whatever can be continuous; solvers handle those cheaply.
- **Waiting for a zero gap** on a large model when a 1% gap answers the business question.

## Quick recap

- Integer variables model counts; binary variables model yes/no choices and logic.
- Rounding LP answers can fail; the LP relaxation gives a bound.
- Common binary patterns: at most k, exclusion, implication, and big-M fixed costs.
- Solvers use branch and bound and report the MIP gap.

## Try it

In the **Do** tab, write the logic constraints for the capital budgeting model and find the best portfolio by enumeration.


Model yes/no decisions and logical rules with binary variables, and see why rounding an LP answer is not enough.

Integer programming

Integer Linear Programming - Binary (0-1) Variables 1, Fixed Cost

Integer Programming: How to Use the Branch and Bound Method

## Why it matters

Goods, people, data and money all move through networks: roads between depots and stores, pipes between plants, links between servers. **Network models** are among the most useful tools in OR because they are easy to draw, easy to explain to managers, and fast to solve, even with millions of arcs. This lesson covers two classics: the **shortest path** problem and the **transportation** problem.

## Networks in one paragraph

A network has **nodes** (locations) and **arcs** (connections), each arc with a cost, distance or time, and sometimes a capacity. Nodes can **supply** flow (plants), **demand** it (stores), or just pass it on (warehouses). At every node, flow in minus flow out equals its demand minus its supply: this **flow conservation** constraint is what all network models share.

## Shortest path with Dijkstra's algorithm

Here are delivery times in minutes on one-way roads:

```text
depot -> a 7,  depot -> b 9,  depot -> f 14
a -> b 10,     a -> c 15
b -> c 11,     b -> f 2
c -> store 6,  f -> store 9
```

**Dijkstra's algorithm** finds the quickest route from one node to all others when every arc cost is non-negative.

1. Set the distance to the start node to 0 and to every other node to infinity.
2. Repeatedly take the unvisited node with the smallest known distance and mark it done (a priority queue, Python's `heapq`, makes this fast).
3. **Relax** each arc leaving it: if going through this node gives a neighbour a shorter distance, record the new distance and remember where it came from.
4. Stop when the target is done, then follow the "came from" links backwards to recover the path.

Tracing it: depot (0) gives a = 7, b = 9, f = 14. Visit a (7): c = 22; b stays 9 because 7 + 10 = 17 is worse. Visit b (9): f improves to 11, c improves to 20. Visit f (11): store = 20. Visit c (20): store via c would be 26, no better. Visit store (20). The route is **depot -> b -> f -> store, 20 minutes**, even though the direct-looking arc depot -> f costs 14 on its own.

With negative arc costs (for example credits or rebates), Dijkstra can fail; use the Bellman-Ford algorithm instead. As an LP, shortest path is a min-cost flow problem that sends one unit from the start to the target.

## The transportation problem

Two plants supply three stores. Plant 0 can ship 30 units and plant 1 can ship 40. The stores need 20, 25 and 25. Unit shipping costs:

| | store 0 | store 1 | store 2 |
|---|---|---|---|
| plant 0 | 8 | 6 | 10 |
| plant 1 | 9 | 12 | 7 |

Let `x_ij` be the units shipped from plant `i` to store `j`.

```text
minimize   sum over i, j of cost_ij * x_ij
subject to sum over j of x_ij  = supply_i    (each plant ships what it has)
           sum over i of x_ij  = demand_j    (each store gets what it needs)
           x_ij >= 0
```

Supply (70) equals demand (70), so the problem is **balanced**. If supply exceeds demand, change the supply rows to `<=`, or add a dummy store with zero cost that absorbs the extra.

The structure gives a good intuition: plant 0 is much cheaper to store 1 (6 versus 12), and plant 1 is cheaper to store 2 (7 versus 10). So plant 0 sends all 25 to store 1, plant 1 sends all 25 to store 2, and the remaining capacity covers store 0: 5 units from plant 0 and 15 from plant 1.

```text
cost = 5*8 + 25*6 + 15*9 + 25*7 = 40 + 150 + 135 + 175 = 500
```

A pleasant fact: when supplies and demands are whole numbers, the transportation LP always has a whole-number optimal solution (its constraint matrix is **totally unimodular**). You get integer shipments without integer programming. Hand methods such as the northwest corner, least cost and Vogel's approximation find good starting plans; a solver then finds the optimum.

## Beyond: flows and routes

- **Maximum flow** pushes as much as possible through capacitated arcs (pipeline throughput, evacuation routes).
- **Minimum-cost flow** generalizes shortest path and transportation with capacities and transshipment nodes.
- **Vehicle routing** (and its simplest form, the travelling salesperson problem) is much harder: it is an integer program, and large instances use heuristics. Do not confuse "shortest path between two points" with "best tour through many points".

In Python, the `networkx` library offers `shortest_path`, `maximum_flow` and `min_cost_flow` for real work.

## Common mistakes

- **Running Dijkstra with negative costs.** Results can be wrong without any warning.
- **Unbalanced transportation models** with `=` constraints: the model becomes infeasible.
- **Mixing directions.** A one-way arc a -> b does not give b -> a.
- **Treating a routing problem as shortest path.** A delivery van visiting 20 stores needs a tour, not 20 separate shortest paths.

## Quick recap

- Networks are nodes, arcs and flow conservation.
- Dijkstra finds shortest paths with non-negative costs, using a priority queue and relaxation.
- The transportation problem balances plant supplies and store demands at minimum cost, and gives integer answers for integer data.
- Max flow, min-cost flow and vehicle routing extend the same ideas.

## Try it

In the **Do** tab, finish Dijkstra's relaxation step and find the cheapest shipping plan for the two plants.


Find shortest paths with Dijkstra's algorithm and solve a transportation problem at minimum shipping cost.

Network flows and routing

Dijkstra's Algorithm - Computerphile

Transportation Problem - LP Formulation

## Why it matters

Labour is the largest cost in hospitals, call centres, airlines, retail and policing. Schedule too few people and service collapses; schedule too many and money is wasted. Staff scheduling is one of the oldest and most profitable uses of integer programming, and the model is short enough to write in an afternoon. This lesson builds the classic **shift scheduling** model step by step.

## The problem

A help desk is open around the clock. The day is split into six 4-hour blocks, and the minimum staff needed in each block comes from forecast call volume:

| block | 00-04 | 04-08 | 08-12 | 12-16 | 16-20 | 20-24 |
|---|---|---|---|---|---|---|
| staff needed | 2 | 4 | 6 | 5 | 3 | 2 |

Each person works one 8-hour shift: two consecutive blocks. A shift starting at 20:00 wraps past midnight into the 00-04 block. How many people should start in each block so that every block is covered, using as few people as possible?

## Step 1: decision variables

`x_s` = number of people whose shift **starts** in block `s` (s = 0, ..., 5). These are integers: you cannot hire 2.5 people.

A common beginner mistake is to define "people working in block t" as the variable. That is an outcome, not a choice: the same person counts in two blocks.

## Step 2: the coverage matrix

People working in block `t` are those who started in block `t` or in block `t - 1`. Write this as a 0/1 **coverage matrix** `A`, where `A[t, s] = 1` if a shift starting in block `s` is on duty in block `t`:

```text
            start: 0  1  2  3  4  5
block 0 (00-04)    1  0  0  0  0  1
block 1 (04-08)    1  1  0  0  0  0
block 2 (08-12)    0  1  1  0  0  0
block 3 (12-16)    0  0  1  1  0  0
block 4 (16-20)    0  0  0  1  1  0
block 5 (20-24)    0  0  0  0  1  1
```

The 1 in the top-right corner is the midnight wrap. Using `%` (modulo) in code handles it: a shift starting in block `s` covers blocks `s` and `(s + 1) % 6`.

## Step 3: objective and constraints

```text
minimize   x_0 + x_1 + x_2 + x_3 + x_4 + x_5
subject to A @ x >= demand          (every block covered)
           x_s >= 0 and integer
```

For example, block 2 gives `x_1 + x_2 >= 6`.

## Step 4: solve and sanity-check

A **lower bound** is easy: each person covers two blocks and the blocks need 2 + 4 + 6 + 5 + 3 + 2 = 22 person-blocks, so at least 11 people are needed. One optimal answer is

```text
x = [0, 4, 2, 3, 0, 2]     (11 people)
coverage A @ x = [2, 4, 6, 5, 3, 2]
```

It meets the bound exactly, so it is optimal, and every block has exactly the staff it needs. Other schedules with 11 people may exist; a solver returns one of them. If shifts were 12 hours (three blocks), the bound becomes 22 / 3, rounded up to 8, and 8 people is achievable.

With PuLP the whole model is a few lines:

```python
import pulp

demand = [2, 4, 6, 5, 3, 2]
n = len(demand)
prob = pulp.LpProblem("help_desk", pulp.LpMinimize)
x = [pulp.LpVariable(f"start_{s}", lowBound=0, cat="Integer") for s in range(n)]
prob += pulp.lpSum(x)
for t in range(n):
    prob += x[t] + x[(t - 1) % n] >= demand[t], f"cover_{t}"
prob.solve(pulp.PULP_CBC_CMD(msg=False))
print([int(v.value()) for v in x])
```

## Making it realistic

The textbook model is the core; real rosters add layers.

- **Weekly patterns.** The classic version uses days: each person works 5 consecutive days and gets 2 off, so `x_d` is the number starting their week on day `d`.
- **Different shift types and costs.** Night or weekend shifts cost more: put a cost per variable in the objective.
- **Labour rules.** Maximum hours, minimum rest between shifts, required breaks and skills (only some agents speak Spanish).
- **Soft constraints.** Preferences and fairness are often modelled with penalty variables in the objective rather than hard rules, so the model stays feasible.
- **Two stages.** First decide how many people start when (this lesson), then assign named people to those shifts (an assignment problem).
- **Forecast first.** Demand comes from a call forecast plus a queueing model (next module) that turns "calls per hour" into "agents needed".

Brute-force search works for six small integer variables (the exercise uses numpy to check every combination), but real rosters with thousands of variables need a MIP solver.

## Common mistakes

- **Defining variables as "people on duty"** instead of "people starting".
- **Forgetting the wrap-around** shift from the last block into the first.
- **Treating fractional LP answers as staffing levels.** Use integer variables, then check the MIP gap.
- **Ignoring legal and union rules** until the end. A schedule that breaks them is not a schedule.
- **Optimizing to the exact forecast.** Forecasts are uncertain; add a buffer or test the schedule in a simulation.

## Quick recap

- Variables are the number of people starting each shift.
- A 0/1 coverage matrix links starts to blocks covered, including wrap-around.
- Minimize total people subject to coverage `A @ x >= demand`, integers.
- Simple bounds (total demand divided by shift length) check the answer.

## Try it

In the **Do** tab, build the coverage matrix with numpy and find the smallest schedule for the help desk.


Build a shift scheduling model with a coverage matrix and find the fewest staff that cover demand.

Scheduling

Personnel Scheduling Problem Solved With Linear Programming

Linear Programming: Employee Scheduling with Excel Solver

Model yes/no decisions with binary variables, solve shortest path and transportation problems, and build a staff schedule.