Accurate simulations of multiscale problems, e.g., architected materials and structures, require a full discretization of the fine-scale geometry for applications with insufficient scale separation. This leads to numerical models with many unknowns and increased computational cost. Moreover, in the con- text of the optimization of architected materials, many model evaluations are required, making a direct numerical solution impractical. In this contribution, a methodology for the shape optimization of lattice structures is presented. The chal- lenges pertaining to the accurate simulation of architected materials mentioned above are addressed as follows. Projection-based model order reduction and domain decomposition are combined to reduce the number of unknowns. The decomposition allows for the localization of the subspace construction. Here, an algorithm based on random sampling is developed that allows the construction of local approximation spaces (with nearly exponential decay of the error) for parametric problems and, hence, constitutes an extension of the work [1] to the parametric case. The method described in [2] is used to treat parameter- ized geometries and is combined with the matrix version of the discrete empirical interpolation method (see [3]) to deal with non-affine parameter dependence. This combination allows the geometrical param- eterization of the lattice unit cell to be altered without modifying the rest of the computational procedure. The accuracy and efficiency of the proposed methodology are discussed based on its application to the shape optimization of a graded concrete structure as a special case of a lattice structure.