Modeling the capacitated p-cable trench problem with facility costs

Silvia Schwarze, Eduardo Lalla-Ruiz*, Stefan Voss

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

15 Downloads (Pure)


In this work, two network design concepts which have been proven to be relevant with respect to telecommunication applications, are joined within a unified approach. First, the cable trench problem searches for cost-minimizing network structures that take into account two types of edge costs appearing in the installation of wire-based networks, namely trenching costs and cable costs. Second, the facility location problem considers the placement of shared telecommunication equipment, like switches or concentrators, together with an assignment of entities to demand nodes. Following practical needs, we join these concepts within the new capacitated cable trench problem with facility costs and service capacity in terms of number of customers that can be served by facilities. Within this setting, facility location decisions in wire-based networks can be taken under a more realistic cost scenario. A mixed-integer linear program and valid inequalities are proposed. Experiments indicate a positive impact of the valid inequalities on computational time and integrality gap.
Original languageEnglish
JournalCentral European journal of operations research
Publication statusE-pub ahead of print/First online - 13 Feb 2020


  • UT-Hybrid-D
  • Facility location
  • Valid inequalities
  • Mixed-integer linear program
  • Mathematical modeling
  • Network optimization
  • Optimization
  • Network design and capacity planning
  • Cable-trench problem

Cite this