In this paper we consider the optimization of a Petaweb backbone, a core-based composite-star infrastructure capable of accommodating petabit-per-second traffic volumes. The problems of designing both regular and quasi-regular Petaweb structures have recently been discussed in the literature. Our contribution is twofold. First, we propose a new model to optimally plan the regular Petaweb structure: using general purpose optimization software with our formulation allowed us to obtain provably optimal solutions even for large networks. Second, we tackle the problem of directly optimizing the quasi- regular topology: we introduce an Integer Linear Programming (ILP) formulation and devise an ad-hoc heuristic algorithm. We illustrate through experimental results that we can obtain in this way very good configurations for the original architecture.