Constraint Satisfaction Problems Questions and Answers

Q: What is the practical consequence of confluence in a solver?

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.

Q: What is a variable in a constraint problem?

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.

Q: What is a solution to a constraint problem?

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.

Q: What does it mean for a constraint problem to be over constrained?

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.

Q: What is a maximum satisfiability formulation used for?

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.

Q: Why are real problems often posed as optimisation rather than satisfaction?

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.

Q: What is a soft constraint?

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.

Q: How are hard and soft constraints handled differently by a solver?

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.

Q: What is branch and bound in a constraint optimisation problem?

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.

Q: What must the bound in branch and bound satisfy?

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.

71.

What is the practical consequence of confluence in a solver?

A.The result of the search is independent of the variable ordering
B.Every problem has exactly one propagation fixed point per solution
C.Propagators can be scheduled in whatever order is fastest
D.The solver need only apply each propagator once

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.

Discuss in Forum

72.

What is a variable in a constraint problem?

A.A parameter of the algorithm that the user may adjust
B.A constraint that changes as the search proceeds
C.A value that has not yet been assigned to anything
D.A quantity whose value the solution must determine

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.

Discuss in Forum

73.

What is a solution to a constraint problem?

A.A complete assignment satisfying every constraint
B.A partial assignment that violates no constraint so far
C.The sequence of assignments made during the search
D.The set of values remaining after propagation

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.

Discuss in Forum

74.

What does it mean for a constraint problem to be over constrained?

A.The domains have been reduced to a single value each
B.No assignment satisfies all the constraints
C.Every variable appears in more than one constraint
D.The constraints are more numerous than the variables

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.

Discuss in Forum

75.

What is a maximum satisfiability formulation used for?

A.Proving that a constraint problem has no solution at all
B.Determining the maximum size of a satisfiable subproblem
C.Finding an assignment violating as few constraints as possible
D.Finding the assignment satisfying the largest number of variables

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.

Discuss in Forum

76.

Why are real problems often posed as optimisation rather than satisfaction?

A.Optimisation problems are easier to solve computationally
B.Satisfaction problems cannot express numerical preferences
C.Optimisation requires no constraints to be specified
D.All the requirements can rarely be met simultaneously

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.

Discuss in Forum

77.

What is a soft constraint?

A.One that may be violated at a stated cost
B.One that applies only to some of the variables
C.One whose truth is uncertain rather than known
D.One that is checked only after a solution is found

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.

Discuss in Forum

78.

How are hard and soft constraints handled differently by a solver?

A.Hard constraints apply to variables and soft ones to values
B.Hard constraints prune while soft ones contribute to an objective
C.Hard constraints are checked first and soft ones afterwards
D.Soft constraints are removed before the search begins

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.

Discuss in Forum

79.

What is branch and bound in a constraint optimisation problem?

A.Bounding the number of branches explored at each node
B.Searching only within a bounded region of the assignment space
C.Pruning branches whose best possible cost exceeds the best found
D.Splitting the problem into bounded independent subproblems

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.

Discuss in Forum

80.

What must the bound in branch and bound satisfy?

A.It must be computed exactly rather than estimated
B.It must equal the cost of the best solution found so far
C.It must be recomputed from scratch at every node
D.It must never be worse than the true best cost in the branch

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.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Constraint Satisfaction Problems Questions and Answers || Constraint Satisfaction Problems MCQ Questions and Answers || Constraint Satisfaction Problems GK Questions and Answers || Constraint Satisfaction Problems GK MCQ Questions || Constraint Satisfaction Problems Multiple Choice Questions and Answers || Constraint Satisfaction Problems GK || GK on Constraint Satisfaction Problems || Artificial Intelligence Questions and Answers || Artificial Intelligence MCQ Questions and Answers || Artificial Intelligence GK Questions and Answers || GK on Artificial Intelligence

Constraint Satisfaction Problems Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications