Solutions to most real-world optimization problems involve a trade-off between
multiple conflicting and non-commensurate objectives. Some of the most
challenging ones are area-delay trade-off in VLSI synthesis and design space
exploration, time-space trade-off in computation, and multi-strategy games.
Conventional search techniques are not equipped to handle the partial order
state spaces of multiobjective problems since they inherently assume a single
scalar objective function. Multiobjective heuristic search techniques have been
developed to specifically address multicriteria combinatorial optimization
problems. This text describes the multiobjective search model and develops the
theoretical foundations of the subject, including complexity results. The
fundamental algorithms for three major problem formulation schemes, namely
state-space formulations, problem-reduction formulations, and