The use of lattice structures in design for additive manufacturing has quickly emerged as a popular and efficient design alternative for creating innovative multifunctional lightweight solutions. In particular, the family of triply periodic minimal surfaces (TPMS) studied in detail by Schoen for generating frame-or shell-based lattice structures seems extra promising. In this paper a multi-scale topology optimization approach for optimal macro-layout and local grading of TPMS-based lattice structures is presented. The approach is formulated using two different density fields, one for identifying the macro-layout and another one for setting the local grading of the TPMS-based lattice. The macro density variable is governed by the standard SIMP formulation, but the local one defines the orthotropic elasticity of the element following material interpolation laws derived by numerical homogenization. Such laws are derived for frame- and shell-based Gyroid, G-prime and Schwarz-D lattices using transversely isotropic elasticity for the bulk material. A nice feature of the approach is that the lower and upper additive manufacturing limits on the local density of the TMPS-based lattices are included properly. The performance of the approach is excellent, and this is demonstrated by solving several three-dimensional benchmark problems, e.g., the optimal macro-layout and local grading of Schwarz-D lattice for the established GE-bracket is identified using the presented approach.