On two new formulations for the fixed charge network design problem with shortest path constraints. (August 2019)

• Record Type: Journal Article
• Authors: Bouras, Ikram; Figueiredo, Rosa; Poss, Michael; Zhou, Fen
• Is Part Of: Computers & operations research. Volume 108(2019)
• Page Start: 226
• Page End: 237
• Publication Date: 2019-08
• Subjects: Network design -- Bi-level programming -- Cutting plane -- Branch-and-cut; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2019.04.007
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: Two new BILP formulations are proposed for the FCNDP-SPC problem. Valid inequalities are added to improve the formulations. Cutting plane and Branch-and-cut algorithms are implemented to solve the FCNDP-SPC using the proposed formulations. A new set of benchmark instances are generated according to their difficult. Abstract: We study the fixed charge network design problem with shortest path constraints which is modeled as a bi-level program. We first review three one-level formulations obtained by applying the complementarity slackness theorem, Bellman's optimality conditions and cycle elimination constraints. We propose two new binary integer programming (BILP) formulations inspired by path and cycle inequalities. The two formulations have exponential numbers of constraints. We incorporate the path and the cycle based formulations in a branch-and-cut algorithm and in another cutting-plane based method. Numerical experiments are performed on real instances, and random data sets generated with different criteria to examine the difficulty of the instances. The results show that the proposed cutting plane algorithms can solve up to 19% more instances than the classic branch-and-bound algorithms.