Decision diagrams (DDs) are well-known tools for modeling and verifying properties of digital systems, including electronic circuits and abstract protocols. In recent years, it was discovered that DDs are also powerful tools for discrete optimization. So far, DDs have been primarily used in conjunction with constraint programming and mathematical programming approaches, but clearly utilizing them in or together with metaheuristics also is highly promising. An exact DD closely corresponds to the state-graph of a dynamic programming formulation to a problem at hand and represents all feasible solutions by corresponding paths from a root node to a target node. A shortest (or longest) path then represents an optimal solution. For hard problems such an exact DD usually is of only limited value due to its exponential size. More interesting from a practical point of view are compact restricted and relaxed DDs. A restricted DD represents only part of the whole solution space and therefore an approximation to the original problem. A relaxed DD, on the other hand, represents a discrete relaxation and thus a super-set of the original problem's solution space. It is obtained by superimposing nodes of an exact DD and yields dual bounds but usually not directly a feasible solution. In this talk we will consider different methods for constructing restricted and relaxed DDs and exploiting them in combinatorial optimization. This includes a novel approach based on A* search.