Markus Chimani

Title:
A new cut formulation for fiber-optics networks with redundancy

Abstract:
We consider the problem of enlarging a given fiber-optics network,
trying to minimize the costs for cable laying while maximizing the
profits for newly connected customers. Furthermore, certain potential
customers require 2-connectedness to the existing network.

We formulate this variant of the Generalized Price-Collecting Steiner
Network Problem as an ILP and solve it using Branch-and-Cut
techniques. The main novelty in our directed cut approach is to
formulate 2-connectedness with a purely binary constraint
matrix.