A multi-layer network planning system can determine a set of regenerator sites (“RSs”) that have been found to cover all paths among a set of nodes of an optical layer of a multi-layer network and can determine a set of candidate RSs in the optical layer for use by the links between a set of nodes of an upper layer, wherein each RS can be selected as a candidate RS for the links. The system can determine a binary path matrix for the links between the set of nodes of the upper layer. The system can determine a min-cost matrix that includes a plurality of min-cost paths. The system can determine a best RS from the set of candidate RSs and can move the best RS from the set of candidate RSs into the set of RSs for the links. The system can then update the binary path matrix.