Constraint Satisfaction Problems Questions and Answers

Q: What is the trade between search and inference?

Every propagation step costs time at every node of the search tree, and pays only if it removes more work than it consumes, so the right level depends on how constrained the problem is. Tightly constrained problems reward strong propagation and loosely constrained ones do not. The two are combined in every practical solver, and inference alone rarely suffices. Recognising the trade as a genuine one, rather than assuming more inference is better, is what allows a solver to be tuned to a problem class.

Q: What is a solver's restart strategy?

Backtracking search can commit early to a poor branch and spend an enormous time in it, and restarting with different randomised choices, while keeping the learned no-goods, escapes that. Geometric or Luby schedules govern when to restart. Queue management, reordering and warm starting are different mechanisms. Abandoning work that is going badly, while retaining what was learned from it, converts a heavy tailed runtime distribution into a manageable one.

Q: Why does restarting help when combined with learning?

Without learning a restart would repeat the same work, but with the recorded no-goods the search is genuinely further forward and avoids the region that caused the trouble. Together the two techniques transformed satisfiability solving. Memory rises, the space is not provably smaller, and termination is not guaranteed sooner. Two techniques that are each modest alone and transformative together are worth noticing as a pair rather than individually.

Q: What is a heavy tailed runtime distribution?

Backtracking searches often show a distribution in which most runs finish quickly and a few take orders of magnitude longer, dominated by unlucky early choices. Restarts truncate the tail and dramatically improve the expected time. Uniformity, skew towards short runs and asymptotic growth are different phenomena. A distribution whose mean is dominated by rare extreme cases calls for a quite different response from one that is merely slow on average.

Q: A constraint solver takes seconds on most instances of a problem but occasionally runs for hours. What is the most appropriate response?

That pattern is the signature of a heavy tail caused by unlucky early branching, and restarting with different random choices while keeping the learned no-goods truncates it directly. Stronger propagation helps generally but does not address the tail, model size is fixed by the problem, and local search would lose the ability to prove unsatisfiability. Matching the remedy to the shape of the runtime distribution, rather than to its average, is the diagnostic skill here.

Q: Why can local search not prove that a problem is unsatisfiable?

A local search that fails to find a solution has established only that it did not find one, since it never enumerates the space and may simply have looked in the wrong region. Systematic search with propagation can exhaust the space and prove absence. Constraint evaluation and initialisation are unaffected. That a negative result from an incomplete method carries no information is the same point made about incomplete search algorithms generally, and it decides which family a problem requiring a proof must use.

Q: When must a systematic method be used rather than local search?

Verification, planning and design problems frequently require a proof that no solution exists, and only a complete method can supply one. Size, constraint arity and domain size affect which method is faster rather than which is capable. Asking what must be concluded from a negative result, before choosing a method, is a question that settles the choice immediately and is easily overlooked when only positive results are anticipated.

Q: What does a constraint programming system provide beyond an algorithm?

Such a system supplies a language for stating variables and constraints, propagators for the common global patterns, and search control that the modeller can direct. That combination is what makes industrial modelling practical. No guarantees of speed or structure are possible, and whether a model captures the intent remains the modeller's responsibility. A tool that makes the right things easy to say, rather than one that promises to solve everything, is what a mature framework offers.

Q: What is the most important skill in applying constraint programming?

The same problem can be modelled in ways that differ by orders of magnitude in solving time, chiefly according to whether the constraints chosen propagate strongly, and practitioners consistently report that modelling dominates every other consideration. Algorithm choice, variable count and language are secondary. That the formulation matters more than the solver echoes the lesson from ordinary search that reformulating a problem beats optimising the search over it.

51.

What is the trade between search and inference?

A.Inference and search cannot be combined in one algorithm
B.Inference replaces search entirely in most practical problems
C.More inference prunes more but costs more at every node
D.More inference always reduces the total time taken

Answer: C

Every propagation step costs time at every node of the search tree, and pays only if it removes more work than it consumes, so the right level depends on how constrained the problem is. Tightly constrained problems reward strong propagation and loosely constrained ones do not. The two are combined in every practical solver, and inference alone rarely suffices. Recognising the trade as a genuine one, rather than assuming more inference is better, is what allows a solver to be tuned to a problem class.

Discuss in Forum

52.

What is a solver's restart strategy?

A.Restarting the propagation queue whenever a domain changes
B.Reordering the variables after every failed assignment
C.Beginning the search again from the last solution found
D.Abandoning a search that is going badly and starting again

Answer: D

Backtracking search can commit early to a poor branch and spend an enormous time in it, and restarting with different randomised choices, while keeping the learned no-goods, escapes that. Geometric or Luby schedules govern when to restart. Queue management, reordering and warm starting are different mechanisms. Abandoning work that is going badly, while retaining what was learned from it, converts a heavy tailed runtime distribution into a manageable one.

Discuss in Forum

53.

Why does restarting help when combined with learning?

A.The no-goods learned are kept while the bad branch is abandoned
B.Restarting reduces the memory the search requires
C.Each restart explores a strictly smaller search space
D.Restarts guarantee that the search will terminate sooner

Answer: A

Without learning a restart would repeat the same work, but with the recorded no-goods the search is genuinely further forward and avoids the region that caused the trouble. Together the two techniques transformed satisfiability solving. Memory rises, the space is not provably smaller, and termination is not guaranteed sooner. Two techniques that are each modest alone and transformative together are worth noticing as a pair rather than individually.

Discuss in Forum

54.

What is a heavy tailed runtime distribution?

A.Runtime grows exponentially with the problem size
B.A few runs take enormously longer than the median
C.Every run takes about the same length of time
D.The distribution has more short runs than long ones

Answer: B

Backtracking searches often show a distribution in which most runs finish quickly and a few take orders of magnitude longer, dominated by unlucky early choices. Restarts truncate the tail and dramatically improve the expected time. Uniformity, skew towards short runs and asymptotic growth are different phenomena. A distribution whose mean is dominated by rare extreme cases calls for a quite different response from one that is merely slow on average.

Discuss in Forum

55.

A constraint solver takes seconds on most instances of a problem but occasionally runs for hours.

What is the most appropriate response?

A.Reduce the number of variables in the model
B.Replace the systematic search with local search
C.Introduce randomised restarts with learning
D.Increase the strength of the propagation used

Answer: C

That pattern is the signature of a heavy tail caused by unlucky early branching, and restarting with different random choices while keeping the learned no-goods truncates it directly. Stronger propagation helps generally but does not address the tail, model size is fixed by the problem, and local search would lose the ability to prove unsatisfiability. Matching the remedy to the shape of the runtime distribution, rather than to its average, is the diagnostic skill here.

Discuss in Forum

56.

Why can local search not prove that a problem is unsatisfiable?

A.It cannot evaluate whether a given constraint has been violated
B.It always terminates before the search is complete
C.It requires a solution to exist before it can begin
D.It explores only some assignments and never exhausts the space

Answer: D

A local search that fails to find a solution has established only that it did not find one, since it never enumerates the space and may simply have looked in the wrong region. Systematic search with propagation can exhaust the space and prove absence. Constraint evaluation and initialisation are unaffected. That a negative result from an incomplete method carries no information is the same point made about incomplete search algorithms generally, and it decides which family a problem requiring a proof must use.

Discuss in Forum

57.

When must a systematic method be used rather than local search?

A.When unsatisfiability must be proved rather than merely suspected
B.When the problem contains more than a few hundred of the variables
C.When the constraints are binary rather than global
D.When the domains of the variables are very large

Answer: A

Verification, planning and design problems frequently require a proof that no solution exists, and only a complete method can supply one. Size, constraint arity and domain size affect which method is faster rather than which is capable. Asking what must be concluded from a negative result, before choosing a method, is a question that settles the choice immediately and is easily overlooked when only positive results are anticipated.

Discuss in Forum

58.

What does a constraint programming system provide beyond an algorithm?

A.A proof that the model correctly captures the requirements
B.A modelling language and a library of global constraints
C.A guarantee that every problem will be solved quickly
D.Automatic conversion of any problem into a tree structure

Answer: B

Such a system supplies a language for stating variables and constraints, propagators for the common global patterns, and search control that the modeller can direct. That combination is what makes industrial modelling practical. No guarantees of speed or structure are possible, and whether a model captures the intent remains the modeller's responsibility. A tool that makes the right things easy to say, rather than one that promises to solve everything, is what a mature framework offers.

Discuss in Forum

59.

What is the most important skill in applying constraint programming?

A.Reducing the number of variables to the minimum possible
B.Selecting a programming language with good performance
C.Modelling the problem so that propagation is effective
D.Choosing the fastest available search algorithm

Answer: C

The same problem can be modelled in ways that differ by orders of magnitude in solving time, chiefly according to whether the constraints chosen propagate strongly, and practitioners consistently report that modelling dominates every other consideration. Algorithm choice, variable count and language are secondary. That the formulation matters more than the solver echoes the lesson from ordinary search that reformulating a problem beats optimising the search over it.

Discuss in Forum

60.

A problem has 20 variables each with 5 values. How large is the assignment space?

A.20 to the 5
B.20 times 5
C.5 factorial
D.5 to the 20

Answer: D

Each variable independently takes any of its values, so the count is:

\[ 5^{20} \approx 9.5 \times 10^{13} \]

which is 5 to the 20. That figure is why enumeration is hopeless and why propagation matters so much. Computing the size of the space before choosing a method takes a moment and immediately rules out the naive approaches, which is exactly the estimate that should precede any implementation.

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