A branch-and-cut algorithm for the discrete (r∣p)-centroid problem

Marcos Costa Roboredo and Artur Alves Pessoa

European Journal of Operational Research, 2013, vol. 224, issue 1, 101-109

Abstract: The environment of the (r∣p)-centroid problem is composed of two noncooperative firms, a leader and a follower, competing to serve the demand of customers from a given market. The demand of each customer is totally served by a facility of the leader or follower according to a customer choice rule. The goal of both the leader and the follower is to maximize its own market share. The (r∣p)-centroid problem consists of deciding where the leader should place p facilities knowing that the follower will react by placing r facilities. The discrete version of the problem is a ∑2p-hard one, where both the applicant facilities and the customers are nodes on a graph. In spite of it, we present an integer programming formulation with polynomially many variables and exponentially many constraints. Moreover, we report several experiments with different number of customers and applicant facilities and different values of p and r. Our results show that our method requires less computational time than the two exact algorithms found in the literature, being able to optimally solve 29 previously open instances with up to 100 customers, 100 applicant facilities and p=r=15.

Keywords: Integer programming; Competitive location; (r∣p)-Centroid problem (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221712005991
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:224:y:2013:i:1:p:101-109

DOI: 10.1016/j.ejor.2012.07.042

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 ().