A new extended formulation with valid inequalities for the Capacitated Concentrator Location Problem

Massimo Di Francesco, Manlio Gaudioso, Enrico Gorgone and Ishwar Murthy

European Journal of Operational Research, 2021, vol. 289, issue 3, 975-986

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.

Keywords: Integer programming; Concentrator location; Valid inequalities (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719305727
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:289:y:2021:i:3:p:975-986

DOI: 10.1016/j.ejor.2019.07.008

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().