Please use this identifier to cite or link to this item: https://repository.iimb.ac.in/handle/2074/21170
DC FieldValueLanguage
dc.contributor.authorMurthy, Ishwar
dc.date.accessioned2022-04-21T12:22:44Z-
dc.date.available2022-04-21T12:22:44Z-
dc.date.issued2022
dc.identifier.otherWP_IIMB_659
dc.identifier.urihttps://repository.iimb.ac.in/handle/2074/21170-
dc.description.abstractIn 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.
dc.publisherIndian Institute of Management Bangalore
dc.relation.ispartofseriesIIMB Working Paper-659
dc.subjectInteger programming
dc.subjectFacility location
dc.subjectValid inequalities
dc.subjectFacets
dc.titleA cardinality induced extended formulation of the single-source un-capacitated facility location problem and its polyhedra
dc.typeWorking Paper
dc.pages45p.
Appears in Collections:2022
Files in This Item:
File SizeFormat 
WP_IIMB_659.pdf1.31 MBAdobe PDFView/Open
Show simple item record

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.