ANLAnalytics & AIStop 2 of 6
Optimization basics: LP and MILP
Objective, decision variables and constraints in plain words, with a worked linear program and when you need integers.
Read atChange any time
Every optimization model has three parts:
- Decision variables: what you’re choosing, such as how much of each product to make or which warehouse to open.
- Objective: what you’re maximizing or minimizing, such as profit or total cost.
- Constraints: the limits you must respect, such as machine hours, labour, demand and capacity.
Here’s a small linear program (LP). A plant makes products A and B, earning ₹50 and ₹40 per unit. A needs 2 machine hours and 1 labour hour; B needs 1 machine hour and 2 labour hours. There are 100 machine hours and 80 labour hours.
The best plan uses both resources fully: make 40 of A and 20 of B, for a profit of ₹2,800. Making only A would give 50 units and ₹2,500; only B, 40 units and ₹1,600. The optimum sits at a corner where both constraints meet, which is how LP solutions always behave.
It’s called linear because every term is a number times a variable, with no variables multiplied together. That makes LPs fast to solve, even with millions of variables.
Many supply chain decisions are yes-or-no: open this warehouse or not, use this supplier or not, run this line or not. Those need integer (often 0/1) variables, which makes the model a mixed-integer linear program (MILP). MILPs are much harder to solve, so they use specialist solvers such as Gurobi, CPLEX, or open-source ones like HiGHS and CBC. Small models even run in Excel Solver.
Words to use
- Objective function
- The quantity to maximize or minimize, such as profit or cost.
- Binary variable
- A 0/1 decision such as open or closed; it makes a model a MILP.
- Shadow price
- How much the objective improves if one constraint is relaxed by one unit.
Solving the LP by its corners
An LP’s best solution is always at a corner of the feasible region (or along an edge between two equally good corners). For the gist’s problem, the corners are:
| Corner | Product A | Product B | Profit |
|---|---|---|---|
| Make nothing | 0 | 0 | ₹0 |
| Machine hours limit, only A | 50 | 0 | ₹2,500 |
| Both limits binding | 40 | 20 | ₹2,800 |
| Labour hours limit, only B | 0 | 40 | ₹1,600 |
Solvers don’t list corners (there can be billions); the simplex method walks from corner to better corner until no neighbour improves.
Shadow prices: what each resource is worth
At the optimum both resources are fully used. How much would one more hour of each add?
Write for the value of a machine hour and for a labour hour. At the optimum, each product’s profit equals the value of the resources it uses:
- Product A:
- Product B:
Solving gives = ₹20 and = ₹10. One extra machine hour adds ₹20 of profit; one extra labour hour adds ₹10. Check: 100 × ₹20 + 80 × ₹10 = ₹2,800, exactly the optimal profit.
So if overtime on the machine costs less than ₹20 an hour, it pays; labour overtime pays only below ₹10 an hour. Shadow prices hold within a range: beyond some point, another constraint starts to bind and the values change. Solvers report these ranges in a sensitivity report.
Yes-or-no decisions with binary variables
Real supply chain decisions need logic that plain LPs can’t express. Binary variables ( = 0 or 1) handle it:
- Fixed cost: a warehouse with fixed cost and capacity : add to the cost and require flow , so a closed site carries nothing.
- Minimum batch: if a product is made at all, make at least : .
- Either-or: use at most two of five suppliers: .
How MILP solvers work
- Branch and bound: solve the LP version (ignoring integrality). If a binary variable comes out at 0.6, branch into two subproblems, one with it fixed at 0 and one at 1, and keep the best integer solution found as a benchmark to prune branches that can’t beat it.
- Cutting planes: add constraints that cut off fractional solutions without removing any integer ones, tightening the LP bound.
- Heuristics: quickly find good integer solutions to prune more of the tree.
Modern solvers combine all three (branch and cut) and solve problems that were out of reach a few decades ago.
Formulation strength
Two formulations of the same problem can solve at very different speeds. In , choosing far larger than needed lets the LP relaxation set to a tiny fraction, giving weak bounds and huge search trees. Use the smallest valid (a site’s true capacity, or total demand), and prefer formulations whose LP relaxation is close to the integer problem.
The optimality gap
Solvers report the best solution found and a bound on how good the best possible solution could be. The gap between them measures how far from optimal the current answer might be. Stopping at 1% often saves hours, and for decisions based on uncertain forecasts, a 1% gap is usually irrelevant.
Tools
Models are written in modelling languages or libraries (such as Pyomo, PuLP or Google OR-Tools in Python, or AMPL and GAMS), which keep data separate from the model and connect to commercial or open-source solvers. Excel Solver suits small teaching models.
When a model misbehaves
- Infeasible: no solution meets all constraints. Look for conflicting data, such as demand above total capacity, or a constraint written in the wrong direction. Solvers can identify a minimal conflicting set.
- Unbounded: profit can grow forever, usually a missing constraint or a sign error.
- Strange answers: check units, data scaling and whether the objective really reflects the decision.
Beyond linear
Some costs are not linear: safety stock grows with a square root, and quantity discounts jump. Common techniques approximate them piecewise with linear segments, or use specialized nonlinear solvers. Uncertainty can be handled with scenarios (stochastic programming) or by protecting against worst cases within a range (robust optimization).
Interview kit
Practise it out loud
Answer each question yourself before opening the model answer.
An optimization model has decision variables, an objective and constraints. If everything is linear and continuous, it’s an LP, fast to solve even at large scale. If some decisions are yes-or-no, like opening a facility or selecting a supplier, binary variables make it a MILP, which needs solvers like Gurobi, CPLEX or HiGHS. Beyond the answer, I’d read shadow prices to see which constraints are worth relaxing.
Maximize 50x₁ + 40x₂ with 2x₁ + x₂ ≤ 100 and x₁ + 2x₂ ≤ 80. What is the optimum?
Check the corners of the feasible region: (50, 0) gives 2,500, (0, 40) gives 1,600, and where both constraints meet, x₁ = 40 and x₂ = 20, it gives 2,800. So the optimum is 40 of A and 20 of B, profit 2,800.
When do you need a MILP instead of an LP?
When decisions are discrete: open or close a site, choose a supplier, run a line or not, fixed costs that only apply if something is used, or minimum batch sizes. Those need integer or binary variables. Pure quantity decisions with linear costs stay as an LP.
Connected stops
Where this idea feeds in, or gets its inputs from.
Sources and further reading
- Hillier, F. S. & Lieberman, G. J. Introduction to Operations Research. McGraw-Hill.
- Winston, W. L. Operations Research: Applications and Algorithms. Cengage Learning.
- Hillier, F. S., & Lieberman, G. J. (2021). Introduction to Operations Research (11th ed.). McGraw-Hill.
- Wolsey, L. A. (2020). Integer Programming (2nd ed.). Wiley.