A Branch And Cut Method To Solve The P-Cable Trench Problem

Abstract

The p-cable trench is a network design problem consisting in locating p facilities and connecting each client with a facility through a cable. Cables must lie in trenches. The objective minimizes cable length and trench digging costs. WiFi systems and forest exploitation are examples of applications. We present a linear integer model and we use valid cuts based on Mixed Integer Rounding in a Branch and Cut procedure to solve it. We provide preliminary computational experience.