Solving the staircase cost facility location problem with decomposition and piecewise linearization

Facility location problems with staircase costs, i.e. fixed costs that appear at several levels of production, are large structured mixed integer programming problems, which often are quite hard to solve. In this paper solution methods based on convex piecewise linearization and Benders decomposition are investigated. Using convex piecewise linearization, only the integer variables that are needed to improve the approximation are introduced, and computational tests show that on average only a few are needed. Benders decomposition can be used to solve the resulting problems, and we show how to recalculate Benders cuts when new variables are introduced, so they still can be used when the approximation is improved.