A column generation approach to capacitated p-median problems
The Capacitated p-median problem (CPMP) seeks to solve the optimal location of p facilities, considering distances and capacities for the service to be given by each median. In this paper we present a column generation approach to CPMP. The identified restricted master problem optimizes the covering of 1-median clusters satisfying the capacity constraints, and new columns are generated considering knapsack subproblems. The Lagrangean/surrogate relaxation has been used recently to accelerate subgradient like methods. In this work the Lagrangean/surrogate relaxation is directly identified from the master problem dual and provides new bounds and new productive columns through a modified knapsack subproblem. The overall column generation process is accelerated, even when multiple pricing is observed. Computational tests are presented using instances taken from real data from So Jos dos Campos city. The location of facilities is a central problem for strategic decisions. Many applications have been explored and the resulting mathematical problems are considered by heuristics and exact methods. We revive in this paper the application of column generation to a capacitated p-median location problem. There has been renewed interest in the column generation approach as it can be faster than nonlinear subgradient methods. However, in many cases a straightforward application of column generation may result in slow convergence. We explore in this paper an alternative to stabilize the column generation when applied to the location problem.
column generation capacitated p-median problems lagrangean/surrogate relaxation location problems