« My old swedish blog posts about constraint programming translated (via Google) | Main | Some new ECLiPSe models, e.g. Minesweeper »

Constraint programming in ECLiPSe Constraint Programming System

This last few weeks I have programmed in ECLiPSe Constraint Logic Programming system more systematically than before. For example, many of my "learning models" has now been implemented in ECLiPSe. These and other ECLiPSe models is now collected at My ECLiPSe Page.

ECLiPSe

ECLiPSe is very well documented system with a couple of online books for different aspects of the system. For more info see:
  • Documentation
  • Examples
  • The book Constraint Programming using ECLiPSe by Krzysztof R. Apt and Mark Wallace, Cambridge University Press, 2006, ISBN: 9780521866286.
  • Mailing lists


My ECLiPSe page

There is now a My ECLiPSe Page with so far 46 ECLiPSe models (see below). Expect that this number will increase.

Arrays and loops

In these models I have almost exclusively used the following two really great features of ECLiPSe, which are extensions to Prolog proper: For logical loops, also see Logical loops by Joachim Schimpf (2002). A quite recent discussion in comp.lang.prolog, foreach for Prolog discussed this more.

Arrays are very handy to use, especially in combinations with loops, see below for an example. Using loops and arrays means that I have been able to port my models quite easy, often directly from the MiniZinc and/or Comet models. This means that there are very few traditional Prolog recursive predicates in these models. Note that loops don't require arrays, they are as powerful with plain old lists, and ECLiPSe has of course also support for traditional Prolog logic programming.

As I understand it, SICStus Prolog will soon support logical loops (inspired by the ECLiPSe approach). That's great!

Example: Diet problem

For a starter, let's implement a simple diet's problem, where we want to minimize the cost of different food given that the nutrition constraints is met. This problem is in diet.ecl and is shown below.
:- lib(ic).
:- lib(branch_and_bound).

go :-
        % 
        % fetch the data
        % 
        data(Price, Limits, Calories, Chocolate, Sugar, Fat),

        % Xs is the decision variable containing the number
        % of nutrition to buy
        length(Calories, Len), % for setting the length of Xs
        length(Xs, Len),       % set the same length for Xs 
 	Xs :: 0..10,           % domains for Xs
        
        % convert Limits to LimitArray (so we can use LimitArray[i] below)
        length(Limits, LimitLength),
        dim(LimitArray, [LimitLength]),
        collection_to_list(LimitArray, Limits),

        % these constraints calculates: sum(Xs[i]*Y[i]) >= limit 
        Xs * Calories  #>= LimitArray[1], % 500,
        Xs * Chocolate #>= LimitArray[2], %   6,
        Xs * Sugar     #>= LimitArray[3], %  10,
        Xs * Fat       #>= LimitArray[4], %   8,

        %
        % search: minimize the sum of Xs * Price
        % 
        XSum #= Xs * Price, 

        minimize(search(Xs,0,first_fail,indomain,complete,[]),XSum),

        writeln([XSum, Xs]).

%
% data
%
data(
        [ 50, 20, 30, 80], % price in cents for each nutrition
        [500,  6, 10,  8], % limits, requirements for each nutrition
                           % type

        % nutrition for each product
        [400, 200, 150, 500], % calories
        [3,2,0,0],            % chocolate
        [2,2,4,4],            % sugar
        [2,4,1,5]             % fat
).
Note especially the construct Total = List1 * List2 which is a syntactical sugar for following (using MiniZinc/Comet syntax):
Total = sum(i from 1..n) (List1[i]*List2[i])


Using loops and arrays: Quasigroup completion

Quasigroup completion is a problem where starting from a not fully completed Latin square, and the object is to complete this square. quasigroup_completion.ecl is a model for this problem.

The model has two principal parts: * stating the problem instances, which I have done as a matrix using an array of arrays. The [](....) is used for declaring arrays. Here is the first problem:
problem(1, []([](1, _, _, _, 4),  
              [](_, 5, _, _, _),
              [](4, _, _, 2, _),
              [](_, 4, _, _, _),
              [](_, _, 5, _, 1))).
* the model
Below is the code for solving the problem and filling out the squares, as well as keep the Latin square condition (for all rows and all columns there must be unique numbers):
solve(ProblemNum) :-
        problem(ProblemNum, Problem),
        dim(Problem, [N,N]), % get the size of the problem
        Problem[1..N,1..N] :: 1..N,
        (for(I, 1, N), param(Problem, N) do
             ic_global:alldifferent(Problem[I,1..N]),
             ic_global:alldifferent(Problem[1..N,I])
        ),
        search(Problem,0,first_fail,indomain,complete,[backtrack(Backtracks)]),
        nl,
        pretty_print(Problem),
        writeln(backtracks:Backtracks).
Here the loop (for(I,1,N)...) is used for looping through all the rows of the matrix. Note how easy it is to use "slices" of the matrix, e.g. Problem[I,1..N].

Comment: This problem is really a subset of solving a Sudoku. The ECLiPSe distribution has an example for solving these problems: sudoku.ecl.txt.

Another example: XKCD knapsack problem

The xkcd knapsack problem is implemented in xkcd.ecl. The models show some different approaches.

Using "plain" lists and the syntactic sugar for multiplying two lists is is quite short:
go4 :-
        Prices = [215, 275, 335, 355, 420, 580],
        Total = 1505,
        length(Prices, Len),
        length(Xs, Len),
        Xs :: [0..10],
        Total #= Xs * Prices,
        labeling(Xs),
        writeln([Total, Xs]).
The multiplication syntactic sugar don't work with arrays, but we can convert the array (a "collection") to a list with collection_to_list/2. This version also minimize the number of dishes:
go3 :-
        Prices = [](215, 275, 335, 355, 420, 580), % Prices for the dishes
        Total = 1505,       % multiply 15.05 with 100 for integer usage
        dim(Prices, [Len]), % get length of Prices
        dim(Xs, [Len]),     % same length of Xs 
        Xs :: [0..10],      % domain of Xs
        % get all solutions
        knapsack(Prices, Total, Xs),

        collection_to_list(Xs, XsList),
        sum(XsList, NumDishes),
        minimize(search(XsList,0,first_fail,indomain_max,complete,[]),NumDishes),
        writeln([Total, Xs, NumDishes]).
Another approach when using arrays is to use for loops which is shown in the knapsack predicate below. Here for(I,1,Len) is used for incrementing the index counter, and then fromto does the actual summation. Note that fromto is very versatile and can be used for other things. See the documentation for more info.
% 
% Sum the totals: Total = Prices * Xs
%
knapsack(Prices, Total, Xs) :-
        dim(Prices, [Len]), % get the length of the array
        ( for(I, 1, Len), fromto(0, S1, S2, Total), param(Prices, Xs) do
              S2 #= S1+Prices[I]*Xs[I]
        ),
        labeling(Xs).


%
% simple version: Total = 1505
%
% This use the array representation
%
go :-
        Prices = [](215, 275, 335, 355, 420, 580), % Prices for the dishes
        Total = 1505,       % multiply 15.05 with 100 for integer usage
        dim(Prices, [Len]), % get length of Prices
        dim(Xs, [Len]),     % same length of Xs 
        Xs :: [0..10],      % domain of Xs
        findall(Xs, knapsack(Prices, Total, Xs), L),
        length(L, LLen),    % length of solutions
        writeln([total:Total, num_solutions:LLen, solutions:L]).


Some more comments about ECLiPSe

Here are some more comments of ECLiPSe
  • ECLiPSe is based on Prolog, which is a programming language that has fascinated me for a long time.
    struct (records) is another great extension, but I have just used it for a map coloring example map.ecl.
  • There are not very many built in global constraints in ECLiPSe (compared to SICStus Prolog) which is a pity. I have plans to implement decompositions for some global constraints from Global Constraint Catalog.
  • Almost all of the implemented model has used the ic library. I have yet to study (and use) the other libraries, eplex, suspend, propia, and repair which all seem very interesting.
  • there are many useful examples, almost all of them use loops and arrays. A wish: More examples of how to use the eplex library would be nice.
  • MiniZinc/FlatZinc: ECLiPSe has a great support for MiniZinc/FlatZinc, but unfortunately it - as of writing - don't support the recent version of MiniZinc (version 1.0).
  • tkECLiPSe: This is a GUI in TclTk, but I have not used it much (I'm a Emacs guy). There are some visualizations libraries that should be tested more.
  • ECLiPSe is a large system, see the Documentation for the full story.


My ECLiPSe models

I have implemented most of my "learning models" in ECLiPSe. Some are not yet done and will hopefully come later. Also, there are some older experiments in recreational mathematics. See My ECLiPSe Page.

As indicated above, most of these models use arrays and logical loops instead of the traditional Prolog recursion technique. I really like using these extensions since it is much easier to state the constraints, at least of me coming from MiniZinc, Comet and other non-logical programming.

Comments

Nice page, and you have done a greater job, I'm wondering if you have make the model for the knight tour problem, because I'm trying to do this but without successful

Hi Juan,

I have implemented three knight path models:

* MiniZinc: http://www.hakank.org/minizinc/knight_path.mzn
* Comet: http://www.hakank.org/comet/knights_path.co
* ECLiPSe: http://www.hakank.org/eclipse/knights_path.ecl

All are using the same principle of solving the problem.

Hope this helps.

Post a comment

(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)