Case 09 / Combinatorial optimization
Where should facilities open, and who should they serve?
A GRASP-initialized Tabu Search for the single-source capacitated facility location problem, combining fast feasible construction with neighborhood search and explicit capacity checks.
- GRASP
- Tabu Search
- LP Relaxation
- Mixed-Integer Programming
- PuLP / CBC
- Matplotlib
- 01 / INPUTDemand and capacityCustomers, facilities, fixed and assignment costs
- 02 / BUILDGRASP startsRandomized candidate lists and feasibility repair
- 03 / IMPROVETabu movesReassign customers; open or close facilities
- 04 / CHECKCost and gapFeasibility plus LP lower-bound comparison
- Evaluated instances
- 351, 55, and 63 customers
- Capacity violation
- 0for every reported best solution
- Instance 1 gap
- 4.30%above its LP relaxation bound
One customer, one open facility.
The model must decide which facilities to open and assign every customer to exactly one of them. Opening a facility has a fixed cost; serving a customer from it has an assignment cost. Customer demand consumes limited facility capacity.
The objective is to minimize opening cost plus assignment cost, while keeping every assignment single-source, linked to an open facility, and within capacity. Those interacting decisions make a feasible, low-cost configuration hard to find by simple rules alone.
Construct broadly, then search locally.
GRASP initialization
The construction phase scores facilities using fixed cost per unit of capacity and average assignment cost. A restricted candidate list introduces controlled randomness. Facilities are opened until total capacity can cover demand, then customers are assigned and a repair step resolves capacity conflicts.
Two levels of Tabu Search
One neighborhood moves individual customers between open facilities when capacity permits. The other changes the facility set: opening a new site and moving a useful group of customers, or closing a site and reassigning its customers feasibly.
Tabu tenure discourages immediate reversals. An aspiration rule accepts a tabu move if it improves the global best; a move-frequency penalty helps diversify the search after stagnation. The repository also includes an LP-relaxation lower bound and a binary MIP comparator for instances that can be solved exactly within the configured limit.
Three instances, feasible assignments.
The documented experiment uses seed 103 and five GRASP constructions per instance. Tabu Search refines each feasible construction; the table reports the best result for each sheet.
| Instance | Facilities / customers | Best GRASP | Best after Tabu | LP bound | Gap |
|---|---|---|---|---|---|
| 1 | 51 / 51 | 1,632 | 1,208 | 1,158.2204 | 4.30% |
| 2 | 55 / 55 | 8,655 | 7,678 | 7,220.1838 | 6.34% |
| 3 | 63 / 63 | 11,240 | 10,695 | 9,908.5600 | 7.94% |
The best solutions open 10, 16, and 21 facilities, respectively. All three have zero reported capacity violation. The repository can also generate convergence charts showing improvement across search iterations.
What the gap says.
An LP relaxation is a lower bound, not a feasible integer solution. A 4.30% gap means the heuristic's feasible cost is 4.30% above that bound; it does not prove that the heuristic is 4.30% from the true optimum.