For a large class of bounded-error estimation problems, the posterior feasible set S for the parameters can be defined by nonlinear inequalities. The set inversion approach combines classical interval analysis with branch-and-bound algorithms to characterize S. Unfortunately, as bisections have to be done in all directions of the parameter space, this approach is limited to problems involving a small number of parameters. Techniques based on interval constraint propagation make it possible to drastically reduce the number of bisections. In this paper, these techniques are combined with set inversion to bracket S between inner and outer subpavings (union of nonoverlapping boxes). When only interested in the feasible intervals for the parameters, the set inversion approach becomes inefficient, and a new algorithm able to compute these intervals is given. This algorithm uses a new interval-based local research to compute the smallest box that contains S. It is then compared with existing methods on an example taken from the literature.