Facility location with economies and diseconomies of scale: models and column generation heuristics

Most of the literature on facility location assumes a fixed setup and a linear variable cost. It is known, however, that as volume increases cost savings are achieved through economies of scale, but when the volume exceeds a certain level, diseconomies of scale occur and marginal costs start to increase. This is best captured by an inverse S-shaped cost function that is initially concave and then turns convex. This article studies such a class of location problems and solution methods are proposed that are based on Lagrangian relaxation, column generation, and branch-and-bound methods. A nonlinear mixed-integer programming formulation is introduced that is decomposable by environment type; i.e., economies or diseconomies of scale. The resulting concave and convex subproblems are then solved efficiently as piecewise convex and concave bounded knapsack problems, respectively. A heuristic solution is found based on dual information from the column generation master problems and the solution of the subproblems. Armed with the Lagrangian lower bound and the heuristic solution, the procedure is embedded in a branch-and-price-type algorithm. Unfortunately, due to the nonlinearity of the problem, global optimality is not guaranteed, but high-quality solutions are achieved depending on the amount of branching performed. The methodology is tested on three function types and four cost settings. Solutions with an average gap of 1.1% are found within an average of 20 minutes.