In this work, optimal combinations of macro-layouts and local gradings of triply periodic minimal surface (TPMS)-based lattice structures are obtained by using multi-scale topology optimization. A new innovative framework is proposed by using two density variables in each finite element. The first variable is the local relative lattice density and it sets the effective orthotropic elastic properties of the element, which in turn are obtained by using numerical homogenization of representative volume elements of the particular TPMS-based lattice structure of interest. The second variable is a standard topology optimization macro density variable, which defines if the element should be treated as a void or contain the graded lattice structure by letting this variable be governed by the rational approximation of material properties (RAMP) model. By using such density variables for all elements, the compliance is minimized by separately constraining the volume of lattice structure and the volume of macro-layout by using two independent constraints. For benchmarks in 3 D, it is demonstrated that the stiffness is increased significantly by including local grading of the lattice structure compared to using a constant lattice density. It is also demonstrated how ultra-lightweight designs can be generated using the multi-scale formulation, and how the optimal multi-scale solutions easily can be realized to printable stl-files by using implicit based geometry modeling. Finally, the new multi-scale topology optimization framework is utilized to generate an optimal design combination of macro-layout and local grading of frame-based Gyroid structure for the established GE-bracket benchmark.