[m-users.] Examples of constraint solving tasks?

[Mark Brown]

Hi,

On Mon, Sep 22, 2014 at 9:53 PM, Paul Bone <paul at bone.id.au> wrote:
> Constraint Logic Programming and Constraint Programming are the domains of
> research that deal with optimising such things, by pruning away parts of the
> search tree that are known to not contain any solutions.  However in order
> to use these techniques with Mercury you must not use Mercury's backtracking
> and instead write your own code for what to test next.  (Unless you use
> impurity or something else that breaks normal logical semantics.)

That's a little misleading. So called second-order predicates like
solutions/2 and optimization can't be expressed in "normal" logic, but
this is true whether or not constraint programming techniques are
used.

The key idea from constraint programming is to test the constraints as
high up in the search tree as possible (so, the opposite of what is
done in the earlier example, which only tests them at the bottom). To
illustrate, I've attached a translation of the example Julien
mentioned into a style that just uses plain old ground terms.
Constraints are added to the constraint store first, then choice
points are created. (Not the other way around.) It is able to prune
the search tree because it can be readily inferred from the constraint
store when a choice is bad and ought to fail.

> This is
> more difficult and not really something that can be explained in an e-mail,
> besides there are online resources that do this better, search for "Branch
> and bound".

Another technique worth searching for is Dynamic Programming. E.g., if
you have already found the optimal solution for sequences starting
with A, a, and these variables aren't in the cost function, then you
don't need to perform the search for sequences starting with a, A
because the remaining sub-problem is exactly the same as before.

Cheers,
Mark.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: eqneq.m
Type: application/octet-stream
Size: 9247 bytes
Desc: not available
URL: <http://lists.mercurylang.org/archives/users/attachments/20140929/15c8b452/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: sudoku.m
Type: application/octet-stream
Size: 7253 bytes
Desc: not available
URL: <http://lists.mercurylang.org/archives/users/attachments/20140929/15c8b452/attachment-0001.obj>