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.
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!
The model has two principal parts: * stating the problem instances, which I have done as a matrix using an array of arrays. The
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):
Comment: This problem is really a subset of solving a Sudoku. The ECLiPSe distribution has an example for solving these problems: sudoku.ecl.txt.
Using "plain" lists and the syntactic sugar for multiplying two lists is is quite short:
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.
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:- logical loops, e.g. for, foreach, fromto
- arrays with slices
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 modelBelow 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
iclibrary. I have yet to study (and use) the other libraries,eplex,suspend,propia, andrepairwhich 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
eplexlibrary 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.
- abbots_puzzle.ecl: Abbot's puzzle
- alldifferent_except_0.ecl: Global constraint all different except 0 (decomposition)
- allpartitions.ecl: All partitions
- build_a_house.ecl: Build a house (scheduling)
- bus_schedule.ecl: Bus scheduling (Taha)
- calculs_d_enfer.ecl: Calculs d'enfer
- changes.ecl: Coin changes
- circling_squares.ecl: Circling squares
- coins_grid.ecl: Coins grid, CP version (Hubermann)
- coins_grid_eplex.ecl: Coins grid, MIP version (Huberman)
- contracting_costs.ecl: Contracting costs
- cur_num.ecl: Curious number
- debruijn.ecl: de Bruijn sequences (both "traditional" and "arbitrary"
- devils_word.ecl: Devil's word
- diet.ecl: Diet problem
- dinner.ecl: Dinner problem
- five_brigands.ecl: Five bridands problem
- furniture_moving.ecl: Furniture moving
- general_store.ecl: General store problem
- latin_squares.ecl: Latin squares
- least_diff2.ecl: Least diff problem
- mamas_age.ecl: Mama's age problem
- mankell.ecl: Generating all (mis) spelling of "Henrik Mankell" and "Kjellerstrand". Note: this is not really constraint programming, but it is a nice application of DCG's.
- map.ecl: Map coloring
- monks_and_doors.ecl: Monks and doors
- mortgage.ecl: Mortgage, experiments
- mr_smith.ecl: Mr Smith problem
- music_men.ecl: Music men problem
- pandigital_numbers.ecl: Pandigital numbers
- pythagoras.ecl: Pythagoras number
- quasigroup_completion.ecl: Quasigroup completion
- remainders.ecl: Remainders problem
- safe_cracking.ecl: Safe cracking problem
- schedule1.ecl: Simple sceduling problem
- schedule2.ecl: Simple sceduling problem
- send_more_money_any_base.ecl: SEND + MORE = MONEY (any base)
- send_most_money.ecl: SEND + MOST = MONEY, maximizes MONEY. All solutions.
- seseman.ecl: Seseman problem
- seven1.ecl: Seven eleven problem
- smuggler_knapsack.ecl: Smuggler's knapsack
- survo_puzzle.ecl: Survo puzzle
- timpkin.ecl: Mr Timpkin problem
- tonum.ecl: toNum, converts a number to array (and vice versa)
- torn_numbers.ecl: Torn numbers problem
- twin_letters.ecl: Twin letters problem
- xkcd.ecl: XKCD knapsack problem