Combinatorial search problems are ubiquitous in many fields of Computer Science. A common technique for addressing them is the exploitation of lower bounds: optimistic estimates of the cost for transforming a state into a solution. But how to compute such estimates? The proposed BARQ project addresses this question, in a highly inter-disciplinary fashion encompassing Classical Planning, Probabilistic Planning, Scheduling, and Model Checking. To our knowledge, BARQ is the first project addressing all these areas in unison. We use abstraction to obtain the lower bounds, and we use abstraction refinement to incrementally improve these bounds. Combined with upper bounding methods, this yields highly practical anytime algorithms that guarantee bounds on the quality of the current solution. The core technique we focus on is state abstraction, which imposes an equivalence relation over states. We consider a recent scheme, nested state aggregation (NSA), for constructing such abstractions. NSA incorporates a computational trick allowing fine-tuned design of the equivalence relation by selecting individual pairs of states to aggregate into one. It has been shown in Classical Planning that, in theory, this approach dominates most other known abstraction schemes. That power hinges, however, on perfect selection of the states to aggregate. Hardly anything is known about how to make this selection. BARQ fills this gap. To this end, we draw on research traditions from Probabilistic Planning and Model Checking, concerned with state abstraction and abstraction refinement. These traditions have addressed similar questions, but for very different purposes forcing the abstraction to preserve the exact set of solutions. Our research relaxes this restriction to obtain lower bounding methods instead, thus uncovering several new connections between the addressed areas. BARQ is mainly motivated by basic research questions. However, each of the four areas addressed has a tradition of practical applications, which we will leverage for the final evaluation of the developed techniques.