Valuation-Based Systems for Discrete Optimization
  This paper describes valuation-based systems for representing and solving
discrete optimization problems. In valuation-based systems, we represent
information in an optimization problem using variables, sample spaces of
variables, a set of values, and functions that map sample spaces of sets of
variables to the set of values. The functions, called valuations, represent the
factors of an objective function. Solving the optimization problem involves
using two operations called combination and marginalization. Combination tells
us how to combine the factors of the joint objective function. Marginalization
is either maximization or minimization. Solving an optimization problem can be
simply described as finding the marginal of the joint objective function for
the empty set. We state some simple axioms that combination and marginalization
need to satisfy to enable us to solve an optimization problem using local
computation. For optimization problems, the solution method of valuation-based
systems reduces to non-serial dynamic programming. Thus our solution method for
VBS can be regarded as an abstract description of dynamic programming. And our
axioms can be viewed as conditions that permit the use of dynamic programming.
