Adding incompatibilities to the Simple Plant Location Problem: Formulation, facets and computational experience. (April 2019)

• Record Type: Journal Article
• Authors: Marín, A.; Pelegrín, M.
• Is Part Of: Computers & operations research. Volume 104(2019)
• Page Start: 174
• Page End: 190
• Publication Date: 2019-04
• Subjects: Discrete Location -- Set packing -- Facets -- Separation algorithm; 90C10 -- 90B80 -- 90C90; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2018.12.018
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: A new model, SPLPI, is introduced to tackle the Uncapacitated Facility Location Problem when there are incompatibilities between clients. New facets for the proposed integer programming formulation are derived. Original lifting procedures are used to obtain those facets. The facets are sequentially added to the formulation in an ad hoc procedure, which performs better than a standard solver when applied to a varied set of instances of the problem. Abstract: We propose and study a new variant of the Simple Plant Location Problem (SPLP). The problem we tackle, which we call Simple Plant Location Problem with Incompatibilities (SPLPI), differs from the classic version in the fact that possible incompatibilities between clients are considered. This variant not only adds flexibility to the SPLP, but also gathers together other previously studied location models. Two clients are said to be incompatible if they cannot be served by the same plant. This circumstance adds a new family of set-packing constraints to the classic set-packing formulation of the SPLP. We study the integer polytope of this restricted formulation, P, which is a tighter version of the polytope of the classic formulation of the problem. All the clique facets of P are identified. Different facets originated by holes of the corresponding conflict graph are described. Separation algorithms for each kind of facet are designed and a computational study to test their performance is presented.