Constraint Satisfaction Problems Questions and Answers

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.

Q: What does an integer programming approach contribute that propagation does not?

Relaxing the integrality requirement gives a linear program whose optimum bounds the true one, and that global bound prunes in a way local propagation cannot. Constraint programming supplies stronger local reasoning about complex combinatorial structures. Both handle discrete variables and can prove infeasibility, and neither is polynomial in general. Two techniques whose strengths are complementary rather than overlapping are natural candidates for combination, which is what hybrid solvers do.

Q: Why are hybrid constraint and integer programming solvers used?

A linear relaxation bounds the objective globally while propagation reasons about combinatorial structures such as sequencing and all different, and each prunes cases the other misses. Both are expressive enough alone, hybrids are considerably more complex, and no polynomial guarantee follows. Combining two pruning mechanisms whose blind spots do not coincide is the same reasoning that makes taking the maximum of two admissible heuristics worthwhile.

101.

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

102.

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

103.

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

104.

What does an integer programming approach contribute that propagation does not?

A.Strong global bounds from a linear relaxation
B.The ability to state constraints over discrete variables
C.A guarantee that the problem will be solved in polynomial time
D.A method for proving that no solution exists at all

Answer: A

Relaxing the integrality requirement gives a linear program whose optimum bounds the true one, and that global bound prunes in a way local propagation cannot. Constraint programming supplies stronger local reasoning about complex combinatorial structures. Both handle discrete variables and can prove infeasibility, and neither is polynomial in general. Two techniques whose strengths are complementary rather than overlapping are natural candidates for combination, which is what hybrid solvers do.

Discuss in Forum

105.

Why are hybrid constraint and integer programming solvers used?

A.The combination guarantees a polynomial time solution
B.Global bounds and local propagation prune in different ways
C.Neither method alone can express the constraints of real problems
D.Hybrid solvers are simpler to implement than either alone

Answer: B

A linear relaxation bounds the objective globally while propagation reasons about combinatorial structures such as sequencing and all different, and each prunes cases the other misses. Both are expressive enough alone, hybrids are considerably more complex, and no polynomial guarantee follows. Combining two pruning mechanisms whose blind spots do not coincide is the same reasoning that makes taking the maximum of two admissible heuristics worthwhile.

Discuss in Forum

Constraint Satisfaction Problems Questions and Answers

Topics

Other Subjects

About Us

Constraint Satisfaction Problems Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications