Constraint Satisfaction Problems Questions and Answers

Answer: C

Knowing the answer does not depend on the schedule frees the implementation to use priority queues, cheap propagators first and event driven wake up without affecting correctness. Propagators are called repeatedly, search order does affect which solution is found first, and fixed points are properties of states. A theoretical property that licenses an engineering freedom is exactly the kind worth establishing before optimising.

Answer: D

The variables are the unknowns of the problem, and a solution assigns a value from its domain to each of them consistently. Algorithm parameters, dynamic constraints and unassigned values are different notions. Deciding what the variables should be is the first modelling choice and it determines the whole structure of the constraint graph, so it repays more thought than it usually receives.

Answer: A

A solution gives every variable a value and violates nothing, whereas a consistent partial assignment is merely a node in the search that may or may not extend. The order of assignment is not part of the answer, and propagated domains are an intermediate state. Being precise about what constitutes an answer determines when the algorithm may stop, which is not always obvious in problems where partial progress looks like success.

Answer: B

An over constrained problem has no solution, and the practical response is usually to relax some constraints or to seek an assignment violating as few as possible, which turns it into an optimisation. Constraint counts and domain sizes are not the criterion, and multiple membership is normal. Recognising that a real problem stated as insoluble usually needs its requirements reconsidered, rather than a better solver, is the practically important response.

Answer: C

When a problem is over constrained, minimising the number of violated constraints, possibly weighted by importance, gives the best available compromise. Timetabling and staff rostering are typically posed this way from the start. Variable counts, unsatisfiability proofs and subproblem sizing are different questions. Converting an infeasible satisfaction problem into a feasible optimisation is how most real requirements are actually met.

Answer: D

Every stakeholder's preferences cannot usually be satisfied at once, so the requirement becomes the best available compromise with soft constraints weighted against one another. Optimisation is generally harder rather than easier, satisfaction can express preferences by encoding them as constraints, and constraints remain central. That a hard formulation must be softened before it matches what is actually wanted is a lesson learned repeatedly when a solver reports that no solution exists.

Answer: A

Soft constraints carry a penalty rather than a prohibition, so the solver minimises the total penalty while satisfying the hard constraints absolutely. That distinction between what must hold and what is merely preferred is essential in any real specification. Partial application, uncertainty and post hoc checking are different notions. Requiring a specification to state which of its requirements are negotiable is often the most useful question an analyst can ask.

Answer: B

A hard constraint removes values from domains, while a soft one adds to a cost that the search minimises, so the two enter the algorithm through entirely different mechanisms. Branch and bound over the cost is the usual arrangement. Ordering, removal and scope are not the distinction. Knowing that the two kinds of requirement are handled by different machinery explains why a specification must classify them before a model can be written.

Answer: C

Keeping the cost of the best solution so far and abandoning any branch whose optimistic cost estimate already exceeds it prunes enormously while preserving optimality. It is the constraint optimisation counterpart of alpha beta pruning. Decomposition, branch limits and region restriction are different techniques. A bound that is provably optimistic, used to discard work that cannot help, is the same idea as an admissible heuristic seen from another direction.

Answer: D

The bound must be optimistic, never claiming a branch is worse than it truly is, or a branch containing the optimum could be pruned. That is exactly the admissibility condition in another guise. Exact computation is unnecessary and usually impossible, the incumbent cost is what the bound is compared against, and incremental computation is normal. The same one sided condition guaranteeing optimality appears in search, in games and here, which is worth noticing as a unifying pattern.