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

[Julien Fischer]

Hi Ondrej,

On Fri, 19 Sep 2014, Ondrej Bojar wrote:

> it's been a while since I've been using Mercury. (Don't worry, I still
> haven't found any substitute programming language, it just happened that all
> I've done in the meantime was so ugly that Perl fitted just right.)
>
> Now I'd like to write a solver for an 'optimal riffle shuffle' problem.
>
> I am given two linear sequences (a, b, c, d, .. and A, B, C, D, ..) and I
> want to merge them into one linearly sorted sequence (e.g. a, A, b, c, B, d,
> C, D, ...) subject to:
> - a number of (hard or soft) ordering constraints between the two sequences
> (b<B, C>d, ...)
> - minimal cost which is some function (linear might be sufficient) of the
> node positions (e.g. b-c to make b and c as close possible)
>
> I've tried glpsol on an early formulation of the problem as linear
> optimization. Satisfying the (hard) ordering constraints is easy, as is the
> minimization of the cost, but I don't think there is way to require the
> global linear order. One way to express this would be to say that each
> variable a, b, .., A, B, has to receive a distinct integer value.
>
> I haven't really written any CS code, but I know Mercury is the basis of HAL
> and there used to be the G12 group. Are there any code examples that would
> illustrate the bits and pieces I might need?

There's a small example of how to use Mercury's support for constraint logic
programming in samples/solver_types.  The program in that directory implements a
simple solver that supports equality and disequality constraints between
integer valued variables.  It uses this to solve Sudoku puzzles.  The principle
pieces used for this approach to constraint solving in Mercury are:

    - solver types
    - dynamic modes (i.e. the "any" inst)
    - trailing

You also require a constraint solver that operates over the constraint domain
in which you're interested.  In early days of the G12 project we used this
approach to implement, or interface to, finite-domain, interval, linear and
Boolean satisfiability solvers.  The current version of the G12 platform has
moved away from the solver type based approach and uses an approach that
involves normal types and various kinds of unique or mostly-unique threaded
state.

There are further details of the solver types approach in the paper "Adding
constraint solving to Mercury", which is on the papers page.  (That paper is
out of date in a few important respects, notably auto-initialisation of solver
variables is no longer supported.)  I don't think that there's anything
publicly available about the approach now used in G12.

Cheers,
Julien.