A cardinality induced extended formulation of the single-source un-capacitated facility location problem and its polyhedra

Abstract

In this paper, an new extended formulation of the Single-Source Un-capacitated Facility Location Problem (SSUFLP) is presented that incorporates the cardinality of the customer set assigned to facilities (or agents) into its formulation. Given a set of M potential facilities and N customers (or jobs), the traditional integer programming formulation consists of O(mn) variables and constraints, where |M| = m and |N| = n. In our extended formulation, potential facility location variables as well as variables describing assignment of customers to agents are disaggregated into n possible cardinalities. Consequently, our formulation consists of O(mn2 ) variables and constraints. Given this, we first show that all non-trivial facets of the polytope associated with this disaggregated formulation can be described by 0-1 coefficients for variables representing assignment of customers to agents and non-negative, integer coefficients of variables representing facility location. We next present in detail, all possible structures of these non-trivial facet inequalities, which we refer to as p-Agent Cardinality Matching inequalities. These inequalities are constructed around N’?N jobs assigned to Wp?M agents in which |Wp| = p. This is motivated by identifying a fractional solution to the LP relaxation of the extended formulation, in which all the fractional variables are associated with N’ and Wp. The basic idea behind these inequalities is to ‘match’ n’ = |N’| jobs to a set of 2 ? p ? m agents with specific cardinalities. The structure varies depending on the relative sizes of p and n’, as well as the cardinalities associated each agent in Wp. All the structures of the p-Agent Cardinality Matching inequalities presented in this paper are shown to be facets of the polytope defined by the convex hull of feasible solutions to our extended formulation. For each such structure, we identify fractional solutions to the LP relaxation of our formulation that violate it. These structures cover all possible combinations of N’ and Wp. Therefore, the p-Agent Cardinality Matching inequalities along with the trivial inequalities completely describe the polytope of the LP relaxation of the extended formulation.