Formulating and solving a radio astronomy antenna connection problem as a generalized cable-trench problem: an empirical study

The low‐frequency array, LOFAR, is the world's largest connected low‐frequency (LF) radio telescope, combining antenna arrays from across Western Europe into a single telescope. A major extension of an existing LOFAR component in Nançay, France, is currently being developed. The prototype design for this extension consists of a network of 96 LF radio telescope antenna arrays distributed across a 400 × 450 m area. A significant portion of the project's cost involves connecting each antenna array directly to a central control facility via a buried coaxial cable. In his 2013 doctoral dissertation, Girard proposed a cabling layout with the goal of minimizing the total cost to dig the trenches and lay the cables, by modeling the problem as a cable‐trench problem (CTP). In this paper, we will discuss Girard's approach and then formulate the problem as a generalized CTP (GCTP) in order to handle physical obstacles more efficiently. To improve upon Girard's solution, we will first apply variations of Prim's algorithm to analyze a number of different GCTPs, based on a variety of cost parameters. Next, we will show that the mixed‐integer linear programming formulation of the GCTP finds even better cable and trench layouts using CPLEX. Finally, we will use a new multicommodity flow formulation of the GCTP to find provably optimal solutions using CPLEX. This work has implications beyond the installation in development in Nançay, as any future component of LOFAR can apply the techniques discussed in this paper to significantly reduce construction costs.