In this paper, classes of tractable \({\mbox{CSOP}}\) , \({\mbox{WCSP}}\) , and \({\mbox{Max-CSP}}\)  instances are singled out by overviewing and proposing solution approaches
applicable to instances whose hypergraphs have bounded (generalized) hypertree width, or whose incidence graphs have bounded treewidth. The
techniques described in this paper are mainly based on Algorithm ComputeOptimalSolution, which has been designed to optimize costs
expressed as rational numbers and combined via the summation operation. However, it is easily seen that it remains correct if costs are
specified over an arbitrary totally ordered monoid structure, where some binary operation \(\oplus \)  (in place of standard summation) is used in
order to combine costs, provided it is commutative, associative, closed, and that it verifies identity and monotonicity. It follows that all
tractable classes of \({\mbox{CSOP}}\) , \({\mbox{WCSP}}\) , and \({\mbox{Max-CSP}}\)  instances identified in this paper remain tractable in such extended scenarios, which
indeed emerge with valued CSPs (see, e.g., [1]}).
