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

24 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
Pages (from-to)713-735
Number of pages23
JournalCentral European journal of operations research
Issue number2
Early online date13 Feb 2020
Publication statusPublished - 1 Jun 2021


  • 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