Question

1. 4pts: Consider constraint satisfaction and constraint optimization problems.
   1. Compare and contrast these problems?

2. Give an example of each

Answer 1

The constraint satisfaction and optimization problems (CSOPs) are doubly complex to the difficulties related to complete satisfaction of constraints and are thus added to those relating to optimization.

The CSOP is a constraint satisfaction problem (CSP) that seeks complete and consistent instantiations optimizing a cost function. It also presents the different resolution techniques associated with the CSOP.

COMPARE

Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods.

A constraint optimization problem (COPs) is the problem of finding a variable assignment to all variables that satisfies all hard constraints and at the same time optimizes the global cost function. Constrained optimization is the process of optimizing an objective function with respect to some variables in the presence of constraints on those variables.

CONTRAST

COPs	CSPs
uses of exact methods that ensure the completeness of the resolution but require much temporal complexity	uses approximate methods that sacrifice completeness to gain in temporal complexity
In the exact method category, it uses the most traditional method: branch and bound.	The approximate methods are especially used by practitioners that deal with large‐scale optimization problems
The objective function is either a cost function or energy function, which is to be minimized, or a reward function or utility function, which is to be maximized.	CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables.the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families.
Constraints can be either hard constraints, which set conditions for the variables that are required to be satisfied, or soft constraints, which have some variable values that are penalized in the objective function if, and based on the extent that, the conditions on the variables are not satisfied.	The Boolean satisfiability problem (SAT), the satisfiability modulo theories (SMT) and answer set programming (ASP) can be roughly thought of as certain forms of the constraint satisfaction problem.
A cost network is a 4-tuple O = <V, D, Ch, Cs>  where (a) <V,D,Chi> is a constraint network (elements of Ch are called hard constraints), and (b) Cs = {F1,...,Fl} is a set of real-valued functions defined over scopes s1,...,sl (elements of Cs are called soft constraints).	Formally, a constraint satisfaction problem is defined as a $\langle X,D,C\rangle$ , where $X=\{X_{1},\ldots ,X_{n}\}$ is a set of variables, $D=\{D_{1},\ldots ,D_{n}\}$ is a set of the respective domains of values, and $C=\{C_{1},\ldots ,C_{m}\}$ is a set of constraints.
example:: In time-tabling problems, resource constraints such as “a teacher can teach only one class at a time” must be satisfied; a request such as “the schedule of teacher should be concentrated in two days” is simply a preference, but not essential for the solution.	Examples of simple problems that can be modeled as a constraint satisfaction problem include: Eight queens puzzle Map coloring problem Sudoku, Crosswords, Futoshiki, Kakuro (Cross Sums), Numbrix, Hidato and many other logic puzzles