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

[Ondrej Bojar]

Dear all,

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?

Looking forward to your response and feeling very homesick for Australia and Melbourne in particular.

Cheers, Ondrej.

-- 
Ondrej Bojar (mailto:obo at cuni.cz / bojar at ufal.mff.cuni.cz)
http://www.cuni.cz/~obo