A Branch-and-Price Algorithm for Facility Location with General Facility Cost Functions

Wenjun Ni (), Jia Shu (), Miao Song (), Dachuan Xu () and Kaike Zhang ()
Additional contact information
Wenjun Ni: Department of Management Science and Engineering, School of Economics and Management, Southeast University, 210096 Nanjing, Jiangsu, People’s Republic of China;
Jia Shu: Department of Management Science and Engineering, School of Economics and Management, Southeast University, 210096 Nanjing, Jiangsu, People's Republic of China;
Miao Song: Department of Logistics and Maritime Studies, Faculty of Business, Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, People's Republic of China
Dachuan Xu: Department of Applied Mathematics, Beijing University of Technology, 100124 Beijing, People’s Republic of China
Kaike Zhang: Department of Management Science and Engineering, School of Economics and Management, Southeast University, 210096 Nanjing, Jiangsu, People’s Republic of China;

INFORMS Journal on Computing, 2021, vol. 33, issue 1, 86-104

Abstract: Most existing facility location models assume that the facility cost is either a fixed setup cost or made up of a fixed setup and a problem-specific concave or submodular cost term. This structural property plays a critical role in developing fast branch-and-price, Lagrangian relaxation, constant ratio approximation, and conic integer programming reformulation approaches for these NP-hard problems. Many practical considerations and complicating factors, however, can make the facility cost no longer concave or submodular. By removing this restrictive assumption, we study a new location model that considers general nonlinear costs to operate facilities in the facility location framework. The general model does not even admit any approximation algorithms unless P = NP because it takes the unsplittable hard-capacitated metric facility location problem as a special case. We first reformulate this general model as a set-partitioning model and then propose a branch-and-price approach. Although the corresponding pricing problem is NP-hard, we effectively analyze its structural properties and design an algorithm to solve it efficiently. The numerical results obtained from two implementation examples of the general model demonstrate the effectiveness of the solution approach, reveal the managerial implications, and validate the importance to study the general framework.

Keywords: branch-and-price; combinatorial optimization; facility location; integrated supply chain (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2019.0921 (application/pdf)

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:inm:orijoc:v:33:y:2021:i:1:p:86-104

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().