Constraint Satisfaction Problems Questions and Answers

Q: What is a redundant constraint?

A constraint that follows logically from the others adds no solutions and removes none, but may allow a propagator to make deductions the original constraints could not reach locally. Adding such constraints deliberately is a standard modelling technique. Exact duplicates, vacuous constraints and errors are different things. That adding information which is logically redundant can be computationally valuable is counter-intuitive until propagation is recognised as local rather than global reasoning.

Q: Why can adding a logically redundant constraint speed up solving?

Each propagator reasons only within its own constraint, so a consequence following from three constraints together may be invisible to all of them individually until it is stated explicitly. The solution set is unchanged. Constraint counts rise, the tree shrinks as a consequence rather than by definition, and no solutions are removed. Making an implicit consequence explicit, so that local reasoning can use it, is the whole justification for the technique.

Q: What is the practical modelling advice that follows?

Adding implied constraints, using global constraints where they apply and trying alternative encodings, then measuring, is how industrial models are developed. Minimal models propagate poorly, global constraints are the strongest tool available, and variable count is a poor proxy for difficulty. That the advice is to add rather than to minimise runs against most programming instincts, which is why it has to be stated explicitly.

Q: Why is measurement essential when developing a constraint model?

Whether an implied constraint pays for its propagation cost, or an encoding propagates better, depends on the instance in ways no theory reliably predicts, so alternatives are tried and timed. Correctness is established by reasoning and testing rather than by timing. Automatic reporting and regulation are not the argument. A field in which the theory constrains but does not determine the best choice is one where disciplined experiment is part of the methodology.

Q: What does a solver report when a problem has no solution?

A complete solver that has explored the whole space, with propagation pruning the impossible, can assert unsatisfiability as a proved result rather than a failure to find anything. Timeouts, best efforts and explanations are all useful outputs but are different claims. Some systems can also produce a minimal unsatisfiable subset explaining why. Distinguishing a proof of absence from a failure to find is what makes a solver usable for verification rather than only for construction.

Q: What is a minimal unsatisfiable subset?

When a model is found to be unsatisfiable, isolating a small group of constraints that are already contradictory tells the modeller where the error lies far better than a bare failure. Removing any one of them would restore satisfiability. The other options describe different sets. A tool that explains a negative result, rather than merely reporting it, is what makes debugging a large model tractable at all.

Q: Why is explanation valuable when a model proves unsatisfiable?

In practice a model reported as insoluble is far more often mis-stated than the real requirement is impossible, and a small conflicting subset points straight at the mistake. Without it a modeller faces hundreds of constraints and no clue. Publication, speed and provability are not the issue. A diagnostic that localises an error within a large artefact is worth more than any improvement in the speed of detecting that an error exists.

Q: What is a search strategy in a constraint solver?

The strategy combines a variable ordering and a value ordering, and most solvers let the modeller specify it because a problem specific strategy often beats any general one. Propagator scheduling is an internal matter, method choice is made earlier, and depth limits are rarely used. Exposing the search control to the modeller, who knows the problem, is what distinguishes a constraint programming system from a black box solver.

Q: Why do solvers let the modeller specify the search strategy?

A modeller who knows that scheduling the bottleneck machine first, or assigning the largest task first, usually works can express that directly and outperform any general heuristic. Default strategies exist and are often adequate. Documentation and propagation are separate matters. A system that admits domain knowledge where it exists, rather than insisting on generality, is what allows a general tool to compete with a bespoke program.

Q: What is the relationship between constraint programming and operations research?

Integer programming and constraint programming address overlapping territory, one through linear relaxations and cutting planes and the other through propagation and search, and hybrid systems combine them. Neither contains the other, the territories overlap heavily, and operations research covers discrete problems extensively. Two mature traditions attacking the same problems from different directions is a situation where knowing both pays disproportionately.

91.

What is a redundant constraint?

A.One that no assignment can ever violate
B.One that has been added by mistake to the model
C.One implied by the others but improving propagation
D.One that duplicates another constraint exactly

Answer: C

A constraint that follows logically from the others adds no solutions and removes none, but may allow a propagator to make deductions the original constraints could not reach locally. Adding such constraints deliberately is a standard modelling technique. Exact duplicates, vacuous constraints and errors are different things. That adding information which is logically redundant can be computationally valuable is counter-intuitive until propagation is recognised as local rather than global reasoning.

Discuss in Forum

92.

Why can adding a logically redundant constraint speed up solving?

A.The solver checks fewer constraints when more are present
B.Redundant constraints reduce the size of the search tree by definition
C.The redundant constraint removes solutions that were not wanted
D.Propagation is local and may not derive the implied consequence

Answer: D

Each propagator reasons only within its own constraint, so a consequence following from three constraints together may be invisible to all of them individually until it is stated explicitly. The solution set is unchanged. Constraint counts rise, the tree shrinks as a consequence rather than by definition, and no solutions are removed. Making an implicit consequence explicit, so that local reasoning can use it, is the whole justification for the technique.

Discuss in Forum

93.

What is the practical modelling advice that follows?

A.State the strongest constraints you can prove and measure the effect
B.State the minimum set of constraints needed for correctness
C.Avoid global constraints in favour of simple binary ones
D.Choose the encoding with the fewest variables in every case

Answer: A

Adding implied constraints, using global constraints where they apply and trying alternative encodings, then measuring, is how industrial models are developed. Minimal models propagate poorly, global constraints are the strongest tool available, and variable count is a poor proxy for difficulty. That the advice is to add rather than to minimise runs against most programming instincts, which is why it has to be stated explicitly.

Discuss in Forum

94.

Why is measurement essential when developing a constraint model?

A.Measurement is the only way to check the model is correct
B.The effect of a modelling change is hard to predict in advance
C.The solver reports its own efficiency automatically
D.Regulations require solving times to be documented

Answer: B

Whether an implied constraint pays for its propagation cost, or an encoding propagates better, depends on the instance in ways no theory reliably predicts, so alternatives are tried and timed. Correctness is established by reasoning and testing rather than by timing. Automatic reporting and regulation are not the argument. A field in which the theory constrains but does not determine the best choice is one where disciplined experiment is part of the methodology.

Discuss in Forum

95.

What does a solver report when a problem has no solution?

A.The assignment violating the fewest constraints it encountered
B.The constraint responsible for the problem being insoluble
C.That the problem is unsatisfiable, having exhausted the space
D.That it could not find a solution within the time allowed

Answer: C

A complete solver that has explored the whole space, with propagation pruning the impossible, can assert unsatisfiability as a proved result rather than a failure to find anything. Timeouts, best efforts and explanations are all useful outputs but are different claims. Some systems can also produce a minimal unsatisfiable subset explaining why. Distinguishing a proof of absence from a failure to find is what makes a solver usable for verification rather than only for construction.

Discuss in Forum

96.

What is a minimal unsatisfiable subset?

A.The set of constraints violated by the best assignment found
B.The smallest subproblem containing at least one solution
C.The set of variables that could not be assigned any value
D.A smallest set of constraints that together admit no solution

Answer: D

When a model is found to be unsatisfiable, isolating a small group of constraints that are already contradictory tells the modeller where the error lies far better than a bare failure. Removing any one of them would restore satisfiability. The other options describe different sets. A tool that explains a negative result, rather than merely reporting it, is what makes debugging a large model tractable at all.

Discuss in Forum

97.

Why is explanation valuable when a model proves unsatisfiable?

A.The model usually contains an error rather than the requirement
B.Explanations are required before the model may be published
C.The solver runs faster when explanations are requested
D.Unsatisfiability cannot be proved without an explanation

Answer: A

In practice a model reported as insoluble is far more often mis-stated than the real requirement is impossible, and a small conflicting subset points straight at the mistake. Without it a modeller faces hundreds of constraints and no clue. Publication, speed and provability are not the issue. A diagnostic that localises an error within a large artefact is worth more than any improvement in the speed of detecting that an error exists.

Discuss in Forum

98.

What is a search strategy in a constraint solver?

A.The limit placed on the depth of the search tree
B.The rule deciding which variable and value to try next
C.The order in which the propagators are executed
D.The choice between systematic and local search methods

Answer: B

The strategy combines a variable ordering and a value ordering, and most solvers let the modeller specify it because a problem specific strategy often beats any general one. Propagator scheduling is an internal matter, method choice is made earlier, and depth limits are rarely used. Exposing the search control to the modeller, who knows the problem, is what distinguishes a constraint programming system from a black box solver.

Discuss in Forum

99.

Why do solvers let the modeller specify the search strategy?

A.Regulations require the search order to be documented
B.Specifying the order removes the need for propagation
C.Domain knowledge often suggests a much better ordering
D.The solver cannot compute any ordering for itself

Answer: C

A modeller who knows that scheduling the bottleneck machine first, or assigning the largest task first, usually works can express that directly and outperform any general heuristic. Default strategies exist and are often adequate. Documentation and propagation are separate matters. A system that admits domain knowledge where it exists, rather than insisting on generality, is what allows a general tool to compete with a bespoke program.

Discuss in Forum

100.

What is the relationship between constraint programming and operations research?

A.Constraint programming is a branch of operations research
B.The two fields address entirely disjoint classes of problem
C.Operations research applies only to continuous optimisation
D.Both attack combinatorial problems with different primary techniques

Answer: D

Integer programming and constraint programming address overlapping territory, one through linear relaxations and cutting planes and the other through propagation and search, and hybrid systems combine them. Neither contains the other, the territories overlap heavily, and operations research covers discrete problems extensively. Two mature traditions attacking the same problems from different directions is a situation where knowing both pays disproportionately.

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