Constraint satisfaction optimization problems naturally arise in various application contexts. As an example they have recently been used in
the context of combinatorial auctions [1]}, in order to model and solve the winner determination problem of determining the
allocation of the items among the bidders that maximizes the sum of the accepted bid prices. In particular, in [1]}, it has been
observed that CSOPs and, in particular, the winner determination problem, can be solved in polynomial time on
some classes of acyclic instances via a dynamic programming algorithm founded on the ideas of [3]}. This algorithm, named ComputeOptimalSolution, is reported in Figure REF  and will be briefly illustrated in the following.
