TY - JOUR
T1 - A branch-and-price algorithm for facility location with general facility cost functions
AU - Ni, Wenjun
AU - Shu, Jia
AU - Song, Miao
AU - Xu, Dachuan
AU - Zhang, Kaike
N1 - Funding Information:
History: Accepted by Andrea Lodi, Area Editor, Design & Analysis of Algorithms—Discrete. Funding: This research was supported by the National Natural Science Foundation of China [Grants 71525001, 71831004, 71922901, and 11531014], the Jiangsu Provincial Six Talent Peaks Project [Grant TD-RJFW-001], the Jiangsu Province “333” Project [Grant BRA2018068], and Hong Kong Research Grants Council General Research Fund [Grants PolyU 17207415E and PolyU 15212617E]. Supplemental Material: Data and the online supplement are available at https://doi.org/10.1287/ ijoc.2019.0921.
Publisher Copyright:
© 2020 INFORMS.
PY - 2021/12
Y1 - 2021/12
N2 - 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-andprice 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.
AB - 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-andprice 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.
KW - Branch-and-price
KW - Combinatorial optimization
KW - Facility location
KW - Integrated supply chain
UR - http://www.scopus.com/inward/record.url?scp=85101189871&partnerID=8YFLogxK
U2 - 10.1287/ijoc.2019.0921
DO - 10.1287/ijoc.2019.0921
M3 - Journal article
AN - SCOPUS:85101189871
SN - 1091-9856
VL - 33
SP - 86
EP - 104
JO - INFORMS Journal on Computing
JF - INFORMS Journal on Computing
IS - 1
ER -