Four ways to solve one shipping problem
The same transportation problem, 2,500 suppliers by 10,000 outlets, solved three exact ways and one fast way, to see what each costs in time and in quality.
- Course
- INEG 22203 Computing Methods for Industrial Engineers II, Assignment 5
- Term
- Fall 2026
- Work
- Individual
- Tools
- Java, Google OR-Tools (SCIP, CP-SAT, GLOP)
The problem
Ship goods from 2,500 supply points to 10,000 outlets at the lowest total cost, with whole-number shipping costs from 1 to 20 per unit. Every supplier-to-outlet pair is a variable, so the full model has 25 million of them, although only 15 suppliers and 15 outlets actually had anything to ship (more on that under What I'd use when). I solved the same full instance four ways and timed only the solving, not the data generation.
Four methods
- SCIP treats it as an integer program and uses branch and bound: solve the linear relaxation, then branch on any variable that comes out fractional.
- CP-SAT combines constraint programming, SAT solving and local search, running several strategies in parallel. It needs integer coefficients, which this problem has.
- GLOP solves the linear program, where shipments are allowed to be fractions.
- A greedy heuristic I wrote: sort every route from cheapest to most expensive, then ship as much as possible along each one in turn (the least-cost method).
Results
| Method | Total cost | Above optimal | Time |
|---|---|---|---|
| Greedy heuristic | 669,022 | 1.0% | 19 ms |
| GLOP (linear program) | 662,354 | optimal | 27.3 s |
| CP-SAT | 662,354 | optimal | 33.4 s |
| SCIP (integer program) | 662,354 | optimal | 188.7 s |
All three exact methods found the same optimal cost, 662,354. CP-SAT was about 5.7 times faster than SCIP, and the plain linear program was faster still. The greedy heuristic met every outlet's demand at a cost 1.0% above optimal, in 19 milliseconds instead of minutes.
Why the linear program came out whole
The linear program was allowed to ship fractions, yet every shipment came out a whole number and the cost matched the integer optimum exactly. That isn't luck. A transportation problem's constraint matrix is totally unimodular, so when supplies and demands are whole numbers, the linear program's optimal corner point is whole too.
The assignment tested this by scaling every supply by 0.9999. The linear program then returned 28 fractional shipments and a cost of exactly 0.9999 × 662,354 = 662,287.76. Remove the scaling and the fractions disappear. So for this problem you can skip integer programming entirely: the linear program solved it about 7 times faster than SCIP.
What I'd use when
- Greedy when decisions have to be made over and over in real time, the problem is too big for an exact solver, or being within about 1% is good enough. It also makes a good starting solution for an exact solver.
- A linear program whenever the structure guarantees whole-number answers, as it does here.
- An integer program once you add something that breaks that structure, like a fixed cost to open a route or a minimum shipment size.
- At any scale, drop suppliers and outlets with zero supply or demand before building the model. Only 15 of each were active in this data, which shrinks 25 million variables to 225.
Help I had: Claude helped me write starting code for the integer program and showed me how to switch to continuous variables for the linear program.