A Benders decomposition based framework for solving cable trench problems

Hatice Calik 1 Markus Leitner 2 Martin Luipersbeck 2
1 INOCS - Integrated Optimization with Complex Structure
ULB - Université Libre de Bruxelles [Bruxelles], Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : In this work, we present an algorithmic framework based on Benders decomposition for the Capacitated p-Cable Trench Problem with Covering. We show that our approach can be applied to most variants of the Cable Trench Problem (CTP) that have been considered in the literature. The proposed algorithm is augmented with a stabilization procedure to accelerate the convergence of the cut loop and with a primal heuristic to derive high-quality primal solutions. Three different variants of the CTP are considered in a computational study which compares the Benders approach with two compact integer linear programming formulations that are solved with CPLEX. The obtained results show that the proposed algorithm significantly outperforms the two compact models and that it can be used to tackle significantly larger instances than previously considered algorithms based on Lagrangean relaxation.
Document type :
Journal articles
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-01669247
Contributor : Bernard Fortz <>
Submitted on : Thursday, December 21, 2017 - 2:43:11 PM
Last modification on : Tuesday, June 18, 2019 - 3:10:22 PM

File

paper.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Hatice Calik, Markus Leitner, Martin Luipersbeck. A Benders decomposition based framework for solving cable trench problems. Computers and Operations Research, Elsevier, 2017, 81, pp.128 - 140. ⟨10.1016/j.cor.2016.12.015⟩. ⟨hal-01669247⟩

Share

Metrics

Record views

288

Files downloads

143