Please use this identifier to cite or link to this item: https://repository.iimb.ac.in/handle/2074/11022
Title: A new extended formulation with valid inequalities for the capacitated concentrator location problem
Authors: Di Francesco, Massimo 
Gaudioso, Manlio 
Gorgone, Enrico 
Murthy, Ishwar 
Keywords: Concentrator Location;Integer Programming;Valid Inequalities
Issue Date: 2021
Publisher: Elsevier
Abstract: We present a new disaggregated formulation of the Capacitated Concentrator Location Problem (CCLP) using the notion of cardinality of terminals assigned to a concentrator. This formulation consists of O(mnn) variables and constraints, where m denotes the number of concentrators and n the number of terminals, respectively. We prove that this extended formulation is stronger than the traditional one. We also present two classes of inequalities exploiting the cardinality effect of the extended formulation. The first class is a generalization of the well-known Cover and (1, k)-Configuration inequalities, which collectively are stronger than the original Cover and (1, k)-Configuration inequalities. The second class, called the 2-Facility Cardinality Matching Inequality, holds for the uncapacitated version of the Concentrator Location Problem and can be lifted to become a strong inequality for CCLP. We solve the LP relaxation of the extended formulation and use separation heuristics to identify and sequentially add the previous valid inequalities to improve the lower bound. This approach is embedded in a branch-and-bound and results in a branch-and-cut approach. We test our solution approach on a large set of benchmark problems. The experimentation shows that we can identify the optimal solution at the root node in most of the problem instances with up to 50 concentrators and 50 terminals. For larger sized test problems with up to 100 concentrators and 1000 terminals, the branch-and-cut procedure using the disaggregated formulation outperforms the branch-and-cut procedure applied to the traditional formulation both in terms of CPU and the required number of branch-and-bound nodes.
URI: https://repository.iimb.ac.in/handle/2074/11022
ISSN: 2157-3611
DOI: 10.1016/J.EJOR.2019.07.008
Appears in Collections:2020-2029 C

Show full item record

Google ScholarTM

Check

Altmetric


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