Nonconvex feasible parameter sets are encountered in set membership identification whenever the regressor vector is affected by bounded uncertainty. This occurs for example when considering standard output error models, or when the available measurements are provided by binary or quantized sensors. In this paper, a unifying framework is proposed to deal with several identification problems involving a nonconvex feasible parameter set and a procedure is proposed for approximating the minimum volume orthotope containing the feasible set. The procedure exploits different relaxations for autoregressive and input parameters, based on the solution of a sequence of linear programming problems. The proposed technique is shown to provide tight bounds in some special cases. Moreover, it is extended to cope with bounds not aligned with the parameter coordinates, in order to obtain polytopic approximations of the feasible set. A number of numerical tests on randomly generated models and data sets demonstrates the accuracy of the computed set approximations.