next up previous contents
Next: MIP Search Up: Constructive Search Previous: Depth-First Search and Backtracking

Guesses - Constraints Imposed During Search

Search is, of course, much more general than just labelling. Certainly, for combinatorial problems, it involves making guesses that may later turn out to have been bad. However a guess need not involve guessing a value for a variable, as is done in labelling. For example if a variable X has range [0..100], instead of guessing a precise value for X, it may be useful to perform a binary chop, first guessing that tex2html_wrap_inline1754 , and then, if the guess turns out to be bad, guessing that X < 50. A guess in the most general sense is the posting of a new (non-redundant) constraint which narrows the search space. However there is no guarantee that such a guess does not rule out solutions to the problem, therefore the system must also explore the remainder of the search space on backtracking. Typically this is done by imposing the negation of the constraint. However the negation of an inequality tex2html_wrap_inline1758 is a strict inequality <, which can't be handled by linear programming. However in case X is an integer variable, and N an integer, the negation of tex2html_wrap_inline1766 is tex2html_wrap_inline1768 which can be handled.

Joachim Schimpf
Wed Sep 3 18:07:19 BST 1997