In the previous module we learned to analyze: express costs, compute them, and lean on the right data structures. From here on, Rutalia changes the question. It no longer wants to know how much an operation costs, but what the best possible decision is: how many van hours and how many e-bike hours should I hire tomorrow to deliver the maximum number of packages without blowing the budget? Linear programming (LP) is the oldest, most studied, and most widely used tool in industry for answering this kind of question, and it is the natural gateway to the entire optimization module: it forces us to think in terms of decision variables, objective function, and constraints — a vocabulary we will reuse in every lesson to come.

1. From analyzing to deciding: what an optimization problem is
2. Formulating a linear program
3. The feasible region: geometric intuition with an example solvable by hand
4. The simplex method, from a bird's-eye view
5. Solving in practice with scipy.optimize.linprog
6. Integer linear programming: when variables can't be split

Every optimization problem, linear or not, is built from three pieces:

• Decision variables: the numbers we control. At Rutalia: how many van hours to hire, how many packages to assign to each courier, which route to follow.
• Objective function: a formula that, given some decision variables, returns a number we want to maximize (packages delivered, revenue) or minimize (kilometers, cost, emissions).
• Constraints: the conditions a solution must satisfy to be valid: maximum budget, staff hours available, load capacity.

An assignment of values to the variables that satisfies every constraint is called a feasible solution. The best feasible solution according to the objective function is the optimal solution. Optimizing is, quite literally, searching for the best point inside the set of feasible solutions.

A problem is a linear programming problem when the objective function and all the constraints are linear: sums of variables multiplied by constants, with no products between variables, no squares, no exotic functions. 3x + 5y is linear; x·y or x² are not. This restriction, which sounds severe, turns out to be enormously productive: linear problems can be solved exactly and blazingly fast even with millions of variables — something we will see does not happen with the combinatorial problems of the coming lessons.

Getting the formulation right is 80% of the job. Let's look at Rutalia's concrete problem for the morning shift:

• One hour of van delivers on average 30 packages and costs €25 (fuel + driver).
• One hour of electric bike delivers on average 15 packages and costs €10.
• The shift budget is €400.
• Across all available couriers, at most 25 hours of work can be covered.
• There are only enough vans to cover at most 12 hours of van time.

Step-by-step translation:

1. Variables: x = van hours, y = bike hours. (For now we accept fractional values: 10.5 hours is a valid assignment.)
2. Objective: maximize Z = 30x + 15y (packages delivered).
3. Constraints:
   • Budget: 25x + 10y ≤ 400
   • Staff: x + y ≤ 25
   • Fleet: x ≤ 12
   • Non-negativity: x ≥ 0, y ≥ 0 (negative hours don't exist; it sounds obvious, but it must be declared).

The complete linear program looks like this:

Notice that every line is a linear inequality. If the problem statement asked for something like "the van's throughput drops 2% for every accumulated hour", the relationship would no longer be linear and we would need other techniques.

With two variables we can draw the problem. Each constraint is a line that splits the plane into two halves; the feasible region is the intersection of all the valid halves: a convex polygon.

For our problem, the vertices of the feasible polygon are:

Why is it enough to look at the vertices? The objective function 30x + 15y = Z defines, for each value of Z, a line. As Z grows, that line shifts in parallel. The largest achievable Z is the last instant at which the line still touches the feasible region, and that last contact always happens at a vertex (or, in case of a tie, along an entire edge). This is the fundamental theorem of linear programming: if a finite optimum exists, there is an optimal vertex.

Let's verify the winning vertex by hand. Intersection of budget and staff:

Optimal decision: 10 van hours and 15 bike hours → 525 packages, spending exactly the €400 and the 25 staff hours. Notice a detail with economic substance: the fleet constraint (x ≤ 12) is not binding — buying more vans would improve nothing; hiring more staff or raising the budget would. This kind of reading ("which constraint is holding me back?") is one of the reasons LP is so valuable for decision-making.

With 2 variables we draw; with 200,000 we don't. The simplex method (Dantzig, 1947) automates exactly the intuition above:

1. Start at any feasible vertex (for example, the origin).
2. Look at the edges leaving that vertex and pick one along which the objective function improves.
3. Move along that edge to the next vertex.
4. Repeat until no neighbor improves: that vertex is the optimum.

In our example, one possible path would be (0,0) → (12,0) → (12,10) → (10,15), improving Z at every hop (0 → 360 → 510 → 525). Because the region is convex, a vertex with no better neighbors is a global optimum, not merely a local one — there are no "valleys" to get trapped in, unlike what we will see with metaheuristics in 02-04.

Two complexity notes, connecting back to module 1:

• In the theoretical worst case, simplex can visit an exponential number of vertices (pathological instances exist, built on purpose).
• In practice it is almost always extremely fast, and interior-point algorithms with polynomial guarantees exist besides. For the engineer, the message is: an LP with thousands or millions of continuous variables is a solved problem — hand it to a solver and move on.

We will not implement simplex: it is a delicate algorithm to program well (degeneracy, numerical stability) and existing solvers carry decades of engineering. Our job is to formulate; the solver's job is to solve.

scipy includes an industrial-grade LP solver (HiGHS). Its convention: it always minimizes and inequalities are of type ≤. Since we want to maximize Z, we minimize −Z (the same problem with the sign flipped).

Let's unpack what can trip you up the first time:

• c holds the objective coefficients with the sign flipped, because linprog minimizes. At the end we recover the real value with -res.fun.
• Each row of A_ub is one ≤ constraint, and b_ub stores its right-hand side in the same order. The constraint x ≤ 12 is written as the row [1, 0] (coefficient 1 for x, 0 for y).
• bounds covers non-negativity; we could have folded it into A_ub, but declaring it as a bound is clearer (and more efficient for the solver).
• Always check res.status: 0 means optimal; 2 means infeasible (the constraints contradict each other: for example, demanding 30 hours with only 25 available); 3 means unbounded (you forgot a constraint and the objective can grow without limit — almost always a formulation error, not a money-printing machine).

If tomorrow Rutalia adds motorbikes (20 packages/h, €15/h), nothing needs rethinking: one more variable, one more column in A_ub, and the same code solves the problem in milliseconds. That painless scalability is the great gift of linearity.

Our "hours" allowed fractions. But many of Rutalia's decisions are indivisible: you can't rent 2.5 vans or open 0.75 micro-warehouses. If we require the variables to be integers, the problem becomes integer linear programming (ILP), and its nature changes completely.

The obvious temptation — "solve the continuous LP and round" — fails, and it's worth seeing a counterexample with numbers. Suppose Rutalia is studying how many monthly contracts to sign for large vans (x, each contributing 13 capacity points) and small ones (y, contributing 8), with two limited resources:

• Optimum of the continuous LP (ignoring integrality): x = 2.5, y = 3.75, with value 62.5.
• Rounding to the nearest integer, (3, 4): infeasible (violates x + 2y ≤ 10: it gives 11).
• Rounding down, (2, 3): feasible, value 50.
• The true integer optimum: (2, 4), value 58 — which is not obtained by rounding the continuous optimum in any direction.

With 2 variables the error looks small; with hundreds, rounding can violate constraints in a cascade or leave a lot of value on the table. Geometrically, the explanation is that the integer feasible set is no longer a continuous polygon but a cloud of isolated points, and the optimal-vertex theorem no longer applies.

scipy also solves ILPs (the integrality parameter, available with the HiGHS method):

And why do we say ILP "is harder"? Because requiring integrality turns a problem solvable in polynomial time into an NP-hard one: in the worst case, no algorithm is known (and probably none exists) that is essentially better than exploring an exponential number of combinations. In fact, many famous combinatorial problems — the knapsack, the traveling salesman — can be written as ILPs. Modern solvers attack them with a technique called branch and bound, which we will study in depth in lesson 02-03; and when even that falls short, the metaheuristics of 02-04 and 02-05 step in. That is exactly the route we are going to travel in this module.

• Forgetting non-negativity. Without x, y ≥ 0 the solver can return "negative hours" (or an unbounded problem!). Always declare each variable's natural bounds.
• Confusing the direction of optimization. linprog minimizes. If you're maximizing, negate the coefficients of c and remember to negate res.fun when reading the result. It's the number-one slip-up.
• Mixing units. If the budget is in euros and a row of A_ub mixes euros with hours, the model is silent garbage: it will "correctly" solve a problem that isn't yours. Write the units of each constraint in a comment.
• Not checking res.status. An infeasible or unbounded model also "finishes"; if you use res.x without checking the status, you'll propagate None or meaningless values.
• Rounding a continuous LP to get integers. As we just saw, it can be infeasible or suboptimal. If the variables are indivisible, use integrality (or model with ILP directly).
• Forcing linearity where there is none. If the hourly cost changes with volume (tiered discounts), sometimes you can linearize piecewise with extra variables; sometimes you can't. Be honest with the model: an elegant LP of the wrong problem decides nothing useful.
• Tip: before coding, write the model on paper in the maximize / subject to format. If you can't write it that way, you don't understand the problem yet — and scipy won't understand it for you either.

1. Evening shift. In the evening, traffic gets worse: the van drops to 24 packages/hour (same cost, €25/h) and the bike keeps 15 packages/hour at €10/h. Budget: €300; staff hours: 20; van maximum: 8 hours. Formulate the LP and solve it graphically (enumerate the vertices and evaluate the objective at each one).

2. Three transport modes. Add motorbikes to the lesson's original model: 22 packages/h and €15/h, with a maximum of 10 motorbike hours. The budget rises to €500 and staff to 30 hours (van: maximum 12 h, as before). Write the complete linprog code and obtain the optimal assignment. Is any constraint left slack?

3. Why not round? Consider the ILP maximize 5x + 4y subject to 6x + 4y ≤ 24, x + 2y ≤ 6, x, y ≥ 0 integer. (a) Solve the continuous LP by hand (two constraints, two variables). (b) Round the result and check feasibility. (c) Find the integer optimum by enumeration (there are few feasible points) and compare.

Exercise 1.

Vertices and values: (0,0)→0; (8,0)→192; (8,10) (fleet ∩ budget: 25·8+10y=300 → y=10) → 342; budget ∩ staff: 25x+10(20−x)=300 → 15x=100 → x=20/3≈6.67, y≈13.33 → 24·6.67+15·13.33 ≈ 360; (0,20)→300. Optimum: x = 20/3 ≈ 6.67 van hours and y = 40/3 ≈ 13.33 bike hours, with 360 packages. Note: the result is fractional and that's fine, because hours really are divisible. Compare with the morning shift: as the van's throughput worsens, the optimum shifts load toward the bikes and the fleet constraint is no longer binding.

Exercise 2.

Optimum: 10 h of van, 10 h of bike, and 10 h of motorbike → 670 packages. Verify the constraints against the returned solution (a two-line assert prevents decisions based on a misread): budget 25·10 + 10·10 + 15·10 = 500 ✔ binding; staff 10+10+10 = 30 ✔ binding; motorbikes z = 10 ✔ binding. The only slack constraint is the van fleet (x = 10 < 12): with these prices and throughputs, buying more vans would contribute nothing; the bottleneck is the budget and the staff. Notice that the solver does not fill the van up to its cap even though it's the mode that delivers the most packages per hour: per euro spent, the bike (1.5 pkg/€) and the motorbike (≈1.47 pkg/€) outperform the van (1.2 pkg/€), and the budget is scarce.

Exercise 3. (a) Continuous: intersection of 6x+4y=24 and x+2y=6 → x = 3, y = 1.5, value Z = 21. (b) Roundings: (3,2) violates 6x+4y ≤ 24 (26 > 24); (3,1) is feasible with Z = 19. (c) Enumerating the feasible integers, the optimum is (4,0) with Z = 20 (check: 24 ≤ 24, 4 ≤ 6). Neither (3,1) nor any rounding of the continuous optimum finds it: you have to search among the integers, which is exactly what branch and bound will do in 02-03.

We have made the leap from analyzing to deciding. Linear programming has taught us the vocabulary of the whole module — decision variables, objective function, constraints, feasible region, optimum — and has left us two practical results: when the problem is linear and continuous, a solver like linprog solves it exactly and almost instantly (formulating is our job; solving is its job); and when the variables must be integers, the problem becomes NP-hard and rounding is not a valid shortcut. That is exactly where the next lesson begins: most of Rutalia's real decisions — which packages I load into this van, in what order I visit these addresses — are intrinsically discrete. Welcome to combinatorial optimization, where the solution space is not a smooth polygon but an explosion of combinations, and where choosing the right algorithm makes the difference between seconds and centuries.