Combining integer linear programming with a state‐of‐the‐art heuristic for the 2‐path network design problem. (29th May 2018)

• Record Type: Journal Article
• Authors: Clímaco, Glaubos; Rosseti, Isabel; Simonetti, Luidi; Guerine, Marcos
• Is Part Of: International transactions in operational research. Volume 26:Number 2(2019)
• Page Start: 615
• Page End: 641
• Publication Date: 2018-05-29
• Subjects: 2‐PNDP -- hybrid heuristic -- ILP -- postoptimization; Operations research -- Periodicals; 003
• DOI: 10.1111/itor.12563
• Languages: English
• ISSNs: 0969-6016

Abstract

Abstract: In communication network design, connections with few edges reduce the probability of delays and increase confidence. The 2‐path network design problem (2‐PNDP) raised in this context and aimed to build up a minimum‐cost network to satisfy a set of pairs of demands using a path with at most two edges. In this work, we propose two strategies that incorporate integer linear programming (ILP) into a state‐of‐the‐art heuristic for solving the 2‐PNDP. Our approaches collect information from specific components of the original heuristic and use it to reduce the solution space explored by the ILP solver, accelerating its resolution and improving the solution quality. Computational experiments conducted on a set of instances from the literature have shown the benefit of these combinations, achieving better solutions in almost all cases.