We consider the problem of interlink optimization in multilayer interdependent networks under cost constraints, with the objective of maximizing the robustness of the network against component (node) failures. Diverting from the popular approaches of branching process based analysis of the failure cascades or using a supra-adjacency matrix representation of the multilayer network and employing classical metrics, in this work, we present a surrogate metric based framework for constructing interlinks to maximize the network robustness. In particular, we focus on three representative mechanisms of failure propagation, namely, connected component based cascading failure, load distribution in interdependent networks, and connectivity in demand-supply networks, and propose metrics to track the network robustness for each of these mechanisms. Owing to their mathematical tractability, these metrics allow us to optimize the interlink structure to enhance robustness. Furthermore, we are able to introduce the cost of construction into the interlink design problem, a practical feature largely ignored in relevant literature. We simulate the failure cascades on real world networks to compare the performance of our interlinking strategies with the state of the art heuristics and demonstrate their effectiveness.