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 , 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 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 is which can be handled.

Wed Sep 3 18:07:19 BST 1997