Problems

There are three problems:

• CSP;
• Max-CSP; and
• WCSP.

The objective for CSP is finding a solution or proving that no solution exists. The objective for Max-CSP is finding an instantiation of variables that violates as few constraints as possible (or, equivalently, that satisfies as many constraints as possible). The objective for WCSP is finding an instantiation of variables that corresponds to the minimal violation cost (a cost or weight is associated with each tuple of each constraint). CSP is a decision problem whereas Max-CSP and WCSP are optimisation ones.