Analyzing valid bounds for a facility location bilevel problem with capacities

Abstract

In this paper, valid bounds for a facility location bilevel problem with capacities are proposed. This problem arises from the situation when a company aims to locate some facilities such that the location and distribution costs are minimized. Nevertheless, the customers are free to choose the facility they prefer for satisfying their demand. Under this assumption, this problem can be modeled as a bilevel program, in which, the upper level is associated with the company’s decision and the lower level corresponds to the allocation of the customers based on their preferences. The resulting lower level problem is NP-hard, which complicates the resolution of the bilevel problem due to the difficulty of obtaining –in general- bilevel feasible solutions. Hence, we explore other approaches for handling this issue. By considering traditional bounds for the lower level problem, we are able to propose valid bounds for the bilevel one. However, the impossibility of classify them as upper or lower bounds is shown through computational experimentation.