Linear Programming in Supply Chain Management: Five Problems and the Code to Solve Them

The three-part recipe every supply chain optimisation reduces to, and five problems solved with it in Python: network design, supply planning, workforce, budget and raw materials.

Need Help?
Subscribed! Error
Linear Programming in Supply Chain Management: Five Problems and the Code to Solve Them

Linear programming is the mathematical technique that finds the best decision when you have an objective to minimise or maximise, a set of variables you control, and constraints you cannot break.

In a supply chain those three parts are always the same shape: minimise cost or maximise profit, decide how much goes where, and respect the capacities, the demand and the rules.

That is why most supply chain optimisation problems, from where to build a factory to how many operators to schedule on Saturday, reduce to the same recipe with different numbers in it.

I have used that recipe on a dozen operational problems over ten years.

In this article, I will explain it once, then walk through five problems I solved with it in Python, with the objective, the constraints and the code for each.

Supply chain network design as an optimisation problem: factories, capacities, markets and the flows between them.
Where to produce, at what capacity, for which market: one objective, a few hundred variables, a handful of constraints - (Image by Samir Saci)

The scenario: a manufacturer choosing where to produce

Take a company selling to five markets, the United States, Brazil, Germany, India and Japan, and able to open a low-capacity or a high-capacity plant in each.

Each plant carries a fixed cost and a variable cost per unit, and every lane from a plant to a market carries a freight cost.

A container holds 1,000 units, and a high-capacity plant in Brazil can produce 1,500,000 units a month.

The question is which plants to open and how much each one ships to each market, and the answer is not the cheapest lane per market, because capacity binds and every market's best choice depends on every other market's.

That is a linear programme, and supply chain optimisation with Python solves it in a few dozen lines with the PuLP library.

The recipe, in three parts

Every linear programme is written the same way, and the detailed recipe is worth learning once because it is replicated on every problem after.

The three parts of every linear programme: decision variables, objective function, and constraints.
Write the three parts down in plain language first, and the code follows - (Image by Samir Saci)

The decision variables are the quantities you control: units shipped on each lane, workers on each shift, euros allocated to each project.

The objective function is the one number you want to minimise or maximise, written as a linear combination of those variables: total cost, total profit, total workers.

The constraints are the linear conditions the variables must satisfy: demand is met, capacity is not exceeded, the budget is not overspent, each worker rests two days in seven.

The decision variables of a linear programme, the quantities the solver is allowed to change.
The variables are what the model decides, and everything else is either data or a rule - (Image by Samir Saci)
If you can write the objective and the constraints as sums of the variables, the solver does the rest, and it does it in seconds.

The solver is free, PuLP or OR-Tools in Python, and the hard part is never the solver, it is writing down the constraints the operation actually has rather than the ones the textbook lists.

Five problems, and the code

1. Network design: which plants, at what capacity

The problem above, and the one with the largest money attached, because a plant is a decision that lasts years.

The objective is total cost, fixed plus variable plus freight, and the variables are the open or closed status of each plant and the units on each lane.

The constraints are that each market's demand is met and no plant exceeds its capacity.

The result is a footprint, and the Monte Carlo extension runs it across fifty demand scenarios, because the cheapest footprint sits at its capacity ceiling by construction and the one that keeps coming back is the robust one.

2. Supply planning: which plant and which warehouse serve which store

Given the plants and the warehouses, decide the flows so that every store receives what it ordered at the lowest inbound plus outbound cost.

In the supply planning case study the model routes more than 90% of the outbound traffic through one distribution centre to minimise outbound cost, which is what the arithmetic says and not what the planning team had been doing.

3. Workforce planning: how many operators, on which shifts

An e-commerce distribution centre needs a different number of workers every day of the week, and the operators work five consecutive days then rest two.

The objective is to minimise the number hired, and the variables are the workers assigned to each of the seven possible shift starts.

The constraints are that each day's demand is covered and every worker gets the rest the regulation requires.

Inbound resource needs forecast by day, the demand side of the workforce planning problem.
Thirty-one workers on Monday, fewer on Sunday, and every worker on a five-days-on two-days-off cycle - (Image by Samir Saci)

The workforce planning model came out at 53 staff, with nobody starting on the Thursday or Saturday shifts, which is an answer a manager would not have found by hand.

4. Budget planning: which projects to fund

A company has 58 candidate projects, a budget of 4.5 million euros, and a management guideline that each of three strategic pillars gets at least one million.

The objective is to maximise the return on investment, the variables are which projects are accepted, and the constraints are the total budget and the minimum per pillar.

The budget allocation model accepts 36 of the 58 projects, allocates 4.07 of the 4.5 million, and returns 1,050,976 euros, and the interesting output is how the answer changes when the strategic constraints are removed.

I later put an AI agent in front of that model, so that a manager can ask for a scenario in a sentence and the linear programme runs behind the conversation.

5. Raw materials: the cheapest recipe that meets the specification

A food manufacturer has to produce a product that meets nutritional constraints, minimum protein and fibre and maximum fat and sugar, from raw materials with different costs.

The objective is the cost of the mix, the variables are the quantity of each ingredient, and the constraints are the nutrition facts.

The raw materials model finds the feasible minimum in a form a procurement team can act on.

The same structure covers procurement across suppliers and, with a different objective, production planning over a fixed horizon.

The five problems with the objective and the constraints of each: network design, supply planning, workforce, budget, raw materials.
Five different operations, and the same three-part recipe under every one of them - (Image by Samir Saci)

When linear programming is not the tool

Two conditions break it.

If the relationship is not linear, a cost that falls with volume in steps or a setup that only happens when a batch runs, you need integer variables.

The problem becomes a mixed integer programme, which the same solvers handle at a higher computational price.

If the problem is a sequence, which job runs first on which machine, it is scheduling rather than allocation, and the value added services case study uses OR-Tools' constraint solver for exactly that.

Linear programming answers how much goes where. Scheduling answers in what order. Do not force one into the other.
Linear programming for allocation questions beside scheduling for sequence questions.
The question decides the solver, and forcing a sequence into an allocation model is the commonest mistake - (Image by Samir Saci)

Conclusion

Linear programming is one recipe, decision variables, an objective and constraints, and five of the most expensive decisions in a supply chain are that recipe with different data in it.

What we covered in this article

The three-part recipe, network design across five markets, supply planning through the warehouses, workforce planning on a seven-day cycle, budget allocation across 58 projects, and the cheapest recipe under nutritional constraints, each with its case study and code.

Where to go next

Every case study above links to the GitHub repository with the notebook, and the fastest way in is to run the supply chain optimisation example with your own capacities and freight rates.

If the prescriptive type is new to you, what supply chain analytics is puts it beside the other three, and the Supply Science App has a quiz on supply chain optimisation.

The videos behind this article, already on the channel:

The ones coming next, with the date each goes public:

About Me

Let's connect on LinkedIn and Twitter. I am a Supply Chain Engineer who is using data analytics to improve logistics operations and reduce costs.

Need Help?