Strengthening the integrality gap for the capacitated facility location problem with LP-based rounding algorithms

Abstract

This thesis studies the capacitated facility location problem, in which all clients have unit demand and all facilities have integral capacity. A linear relaxation is researched, with corresponding integrality gap bounded by a constant. Recently, such a linear relaxation has been found and proven using an LP-bounding algorithm. The formulation of the relaxation and the proof were very complex and intuitively hard to understand, however. Therefore, this thesis provides a simpler, more formulation and proof. This thesis has two main contributions. First, a structured overview of all the theory prior to the construction of the relaxation is provided. To do so, the minimum knapsack problem is treated, which is a simplied version of the capacitated facility location problem. An LP-based rounding algorithm is presented to illustrate general ow-network techniques for facility location problems. Second, the rounding algorithm for the capacitated facility location problem is illustrated and explained more accessible to readers less familiar with LP-based rounding algorithms. The existing rounding algorithm for the capacitated facility location problem is treated, illustrated and extended with Matlab code. The rounding algorithm proves an integral solution for the capacitated facility location can be constructed from the linear optimal solution, with cost no more than 288 times the cost of the fractional optimal solution. This proves that the integrality gap of the proposed relaxation is bounded by 288.