Lagrangean relaxation heuristics for the p-cable-trench problem

Vladimir Marianov, Gabriel Gutiérrez-Jarpa, Carlos Obreque, Oscar Cornejo

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


We address the p-cable-trench problem. In this problem, p facilities are located, a trench network is dug and cables are laid in the trenches, so that every customer-or demand-in the region is connected to a facility through a cable. The digging cost of the trenches, as well as the sum of the cable lengths between the customers and their assigned facilities, are minimized. We formulate an integer programming model of the problem using multicommodity flows that allows finding the solution for instances of up to 200 nodes. We also propose two Lagrangean Relaxation-based heuristics to solve larger instances of the problem. Computational experience is provided for instances of up to 300 nodes.

Original languageEnglish
Pages (from-to)620-628
Number of pages9
JournalComputers and Operations Research
Issue number3
StatePublished - Mar 2012


  • Lagrangean relaxation heuristics
  • Location
  • Network design


Dive into the research topics of 'Lagrangean relaxation heuristics for the p-cable-trench problem'. Together they form a unique fingerprint.

Cite this