Branch-and-Bound and Approximate Solutions to the Capacitated Plant-Location Problem

In the capacitated plant-location problem, a planner is given a set of projects for production expansion and a linear transportation-cost matrix, and is asked to choose the subset of projects that meets demand at several markets, at the least production-distribution cost. The projects are defined a priori by size, location, and cost function, the latter being concave. An exact branch-and-bound treatment for the problem is explained, together with an approximate routine for solving the problem. The approximate routine borrows from the “add” approach of Kuehn-Hamburger and the “drop” approach of Feldman-Lehrer-Ray. Some of its mathematical properties are described, and sufficient conditions for the optimality of the solution obtained are shown. Empirical evidence is provided suggesting that the branch-and-bound method may be useful in problems of around 25 integer variables, perhaps more, depending on how tightly row-constrained the problem at hand is. Evidence is also provided suggesting that the approximate routine is fast and produces good, frequently optimal, results.