Constraint Satisfaction Problems Questions and Answers

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.