Searching for a constraint solver over finite domains with (in)compatibility tables

[Uwe Lesta]

Hello,

Before reinvented the wheel, i like to ask if someone can advice me for a
constraint solver (prolog or CHR) over finite domains with (in)compatibility tables.

with the possibilities to

- load the Variables ( up to 10 ) with their values as atoms ( up to 1000 )
- load compatibility / incompatibility tables ( up to 1000 entries )
- list the remaining values for each variable
- ( show conflicts if no solution is possible )

thanks in advance

--

Kind regards

Uwe Lesta





------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Markus Triska-2]

Hi,

Uwe Lesta <lesta@...> writes:

> - load the Variables ( up to 10 ) with their values as atoms

If you map these atoms to integers, you can use library(clpfd):

   http://gollem.science.uva.nl/SWI-Prolog/Manual/clpfd.html

> - load compatibility / incompatibility tables ( up to 1000 entries )

Depending on the table, this can be expressed with #=/2 and #\=/2 or
with a tuples_in/2 constraint.

> - list the remaining values for each variable

The residual goals after posting CLP(FD) constraints tell this; domains
are also accessible via the solver's reflection predicates.

> - ( show conflicts if no solution is possible )

Constraint reification can help here. Example:

     http://www.logic.at/prolog/queens/queens.html

Please let me know if you need any further features or constraints.

Thank you and all the best,
Markus

------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Uwe Lesta]

Thank you Markus,

there are some more questions inline:

Markus Triska schrieb:

>>- load the Variables ( up to 10 ) with their values as atoms
>
> If you map these atoms to integers, you can use library(clpfd):
>    http://gollem.science.uva.nl/SWI-Prolog/Manual/clpfd.html

I have also found a CHR implementation 'domain.pl' on
        http://www.cs.kuleuven.be/~dtai/projects/CHR/chr-solver/domain.pl

Does someone known a working versionm for SWI-Prolog ?
I'll try to port it ( set/getval/2 -> nb_setval/2 and some others )
but it seems not work.

Does someone knows which solver performs better ?


So in your library I'll have to map e.g.
        Color::[green, red, blue],
into
        list_to_domain([10, 20, 30], DColor),
        Color in DColor,
Right ?

>>- load compatibility / incompatibility tables ( up to 1000 entries )
>
> Depending on the table, this can be expressed with #=/2 and #\=/2 or
> with a tuples_in/2 constraint.

Can you give me an example if i have

        %% compatibility Color, Shape
        comp_tab(10, 1), % comp_tab(green, square).
        comp_tab(20, 1), % comp_tab(red, square).
        comp_tab(10, 3), % comp_tab(green, circle).
        comp_tab(30, 3), % comp_tab(blue, circle).

        Color::[10, 20, 30], % [green, red, blue],
        Shape::[1,3,5], % [square, circle, triangle],


>>- list the remaining values for each variable
>
> The residual goals after posting CLP(FD) constraints tell this; domains
> are also accessible via the solver's reflection predicates.

is it olso possible with domain_to_list/2 ?


Thanks in advance

--

Kind regards

Uwe Lesta




------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Markus Triska-2]

Uwe Lesta <lesta@...> writes:

> So in your library I'll have to map e.g.
> Color::[green, red, blue],
> into
> list_to_domain([10, 20, 30], DColor),
> Color in DColor,

You can use: ?- Color in 10 \/ 20 \/ 30. This is not necessary though,
as this constraint is implicit in your compatibility table.

> Can you give me an example if i have
>
> %% compatibility Color, Shape
> comp_tab(10, 1), % comp_tab(green, square).
> comp_tab(20, 1), % comp_tab(red, square).
> comp_tab(10, 3), % comp_tab(green, circle).
> comp_tab(30, 3), % comp_tab(blue, circle).

You can enforce this with:

   ?- tuples_in([[Color,Shape]], [[10,1],[20,1],[10,3],[30,3]]).

Answer:

   %@ Shape in 1\/3,
   %@ tuples_in([[Color, Shape]], [[10, 1], [20, 1], [10, 3], [30, 3]]),
   %@ Color in 10\/20\/30.

Shape and Color are automatically constrained as much as possible. If
you now additionally impose (for example) Shape = 1, you get:

   ?- tuples_in([[Color,Shape]], [[10,1],[20,1],[10,3],[30,3]]), Shape = 1.
   %@ Shape = 1,
   %@ Color in 10\/20,
   %@ tuples_in([[Color, 1]], [[10, 1], [20, 1]]).

Here, the domain of Color is automatically reduced to 10\/20. To access
this domain as term, use fd_dom/2:

   ?- tuples_in([[Color,Shape]], [[10,1],[20,1],[10,3],[30,3]]),
      Shape = 1, fd_dom(Color, Dom).
   %@ Shape = 1,
   %@ Dom = 10\/20,
   %@ Color in 10\/20,
   %@ tuples_in([[Color, 1]], [[10, 1], [20, 1]]).


> is it olso possible with domain_to_list/2 ?

Yes, you can easily translate such a finite domain to a list:

   domain_to_list(Domain, List) :- phrase(domain_to_list(Domain), List).

   domain_to_list(I)    --> { integer(I) }, !, [I].
   domain_to_list(A\/B) --> domain_to_list(A), domain_to_list(B).
   domain_to_list(L..U) --> { numlist(L, U, Ns) }, Ns.

Example:

   ?- tuples_in([[Color,Shape]], [[10,1],[20,1],[10,3],[30,3]]),
      Shape = 1, fd_dom(Color, Dom), domain_to_list(Dom, List).
   %@ Shape = 1,
   %@ Dom = 10\/20,
   %@ List = [10, 20],
   %@ Color in 10\/20,
   %@ tuples_in([[Color, 1]], [[10, 1], [20, 1]]).

All the best,
Markus

------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Sanjai Narain]

Hello, I would appreciate knowing about CHR systems that solve Boolean
combinations of simple arithmetic constraints. We are currently using
SAT solvers wrapped by the Kodkod system from MIT, but would be
interested in knowing about alternatives. Thanks. --Sanjai
>


------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Uwe Lesta]

Thanks a lot for your Help Markus

Below is a sample program which do the required tasks.
--
%% see http://gollem.science.uva.nl/SWI-Prolog/Manual/clpfd.html
:- use_module(library(clpfd)).


%% Colors
domain_value(color, green, 10).
domain_value(color, red, 20).
domain_value(color, blue, 30).
domain_value(color, black, 40).
domain_value(color, white, 50).

%% Shapes
domain_value(shape, square, 1).
domain_value(shape, circle, 3).
domain_value(shape, triangle, 7).
domain_value(shape, line, 9).

%% Material
domain_value(material, iron, 100).
domain_value(material, plastic, 101).
domain_value(material, aluminum, 102).



%% compatibility Color, Shape
comp_tab(color_shape, green, square).
comp_tab(color_shape, red, square).
comp_tab(color_shape, green, circle).
comp_tab(color_shape, blue, circle).
comp_tab(color_shape, blue, triangle).

%% incompatibility Material, Shape
incomp_tab(material_shape, aluminum, triangle).
incomp_tab(material_shape, aluminum, circle).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Build a domain variable with possible values
entitiy_number(Name, Var):-
        findall([X], domain_value(Name, _, X), L),
        tuples_in([[Var]], L).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
tab_name(FromName, ToName, Name):-
        concat_atom([FromName, '_', ToName], Name).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

comp_tab_int(NameX, NameY, X, Y):-
        tab_name(NameX, NameY, Name),
        comp_tab(Name, Xname, Yname),
        domain_value(NameX, Xname, X),
        domain_value(NameY, Yname, Y).


%% maps a a comp_tab to tuples_in parameter
% test with % comp_tab_as_tuples('color', 'shape', L).

comp_tab_as_tuples(NameX, NameY, Tuples):-
        findall([X, Y], comp_tab_int(NameX, NameY, X, Y), Tuples).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Build a compatibility table without all tuples from incomp_tab(NameX_NameY, ...
% test with % incomp_tab_as_tuples('material', 'shape', L).

incomp_tab_as_tuples(NameX, NameY, Tuples):-
        tab_name(NameX, NameY, NameTab),
        findall([X, Y], incomp_tab_as_tuple_hlper_(NameTab, NameX, NameY, X, Y), Tuples).

incomp_tab_as_tuple_hlper_(NameTab, NameX, NameY, X, Y):-
        domain_value(NameX, Xn, X),
        domain_value(NameY, Yn, Y),
        not(incomp_tab(NameTab, Xn, Yn)).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

fd_to_listvalues(Name, FD, L):-
        fd_dom(FD, Dom),
        domain_to_list(Dom, Ln),
        maplist(domain_value(Name), L, Ln).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% from clpfd.pl in pl\library\clp\clpfd.pl
        domain_to_list(Domain, List) :- phrase(domain_to_list(Domain), List).

        domain_to_list(I)    --> { integer(I) }, !, [I].
        domain_to_list(A\/B) --> domain_to_list(A), domain_to_list(B).
        domain_to_list(L..U) --> { numlist(L, U, Ns) }, Ns.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

write_out(Name, Var):-
        fd_to_listvalues(Name, Var, Result),
        writef('%t: %t\n', [Name, Result]).


t:-
        statistics,
        entitiy_number(color, Color),
        entitiy_number(shape, Shape),
        entitiy_number(material, Material),
       
        % constrain
        comp_tab_as_tuples(color, shape, Tcs),
        incomp_tab_as_tuples(material, shape, Tms),
        tuples_in([[Color, Shape]], Tcs),
        tuples_in([[Material, Shape]], Tms),

        % set single values
        domain_value(shape, circle, N),
        Shape = N,

        % list result
        write_out(color, Color),
        write_out(shape, Shape),
        write_out(material, Material),
        statistics.

--

Kind regards

Uwe Lesta





------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Uwe Lesta]

Thanks a lot for your Help Markus.

Below is a sample program which do the required tasks.
--
%% see http://gollem.science.uva.nl/SWI-Prolog/Manual/clpfd.html
:- use_module(library(clpfd)).


%% Colors
domain_value(color, green, 10).
domain_value(color, red, 20).
domain_value(color, blue, 30).
domain_value(color, black, 40).
domain_value(color, white, 50).

%% Shapes
domain_value(shape, square, 1).
domain_value(shape, circle, 3).
domain_value(shape, triangle, 7).
domain_value(shape, line, 9).

%% Material
domain_value(material, iron, 100).
domain_value(material, plastic, 101).
domain_value(material, aluminum, 102).



%% compatibility Color, Shape
comp_tab(color_shape, green, square).
comp_tab(color_shape, red, square).
comp_tab(color_shape, green, circle).
comp_tab(color_shape, blue, circle).
comp_tab(color_shape, blue, triangle).

%% incompatibility Material, Shape
incomp_tab(material_shape, aluminum, triangle).
incomp_tab(material_shape, aluminum, circle).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Build a domain variable with possible values
entitiy_number(Name, Var):-
        findall([X], domain_value(Name, _, X), L),
        tuples_in([[Var]], L).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
tab_name(FromName, ToName, Name):-
        concat_atom([FromName, '_', ToName], Name).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

comp_tab_int(NameX, NameY, X, Y):-
        tab_name(NameX, NameY, Name),
        comp_tab(Name, Xname, Yname),
        domain_value(NameX, Xname, X),
        domain_value(NameY, Yname, Y).


%% maps a a comp_tab to tuples_in parameter
% test with % comp_tab_as_tuples('color', 'shape', L).

comp_tab_as_tuples(NameX, NameY, Tuples):-
        findall([X, Y], comp_tab_int(NameX, NameY, X, Y), Tuples).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Build a compatibility table without all tuples from incomp_tab(NameX_NameY, ...
% test with % incomp_tab_as_tuples('material', 'shape', L).

incomp_tab_as_tuples(NameX, NameY, Tuples):-
        tab_name(NameX, NameY, NameTab),
        findall([X, Y], incomp_tab_as_tuple_hlper_(NameTab, NameX, NameY, X, Y), Tuples).

incomp_tab_as_tuple_hlper_(NameTab, NameX, NameY, X, Y):-
        domain_value(NameX, Xn, X),
        domain_value(NameY, Yn, Y),
        not(incomp_tab(NameTab, Xn, Yn)).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

fd_to_listvalues(Name, FD, L):-
        fd_dom(FD, Dom),
        domain_to_list(Dom, Ln),
        maplist(domain_value(Name), L, Ln).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% from clpfd.pl in pl\library\clp\clpfd.pl
        domain_to_list(Domain, List) :- phrase(domain_to_list(Domain), List).

        domain_to_list(I)    --> { integer(I) }, !, [I].
        domain_to_list(A\/B) --> domain_to_list(A), domain_to_list(B).
        domain_to_list(L..U) --> { numlist(L, U, Ns) }, Ns.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

write_out(Name, Var):-
        fd_to_listvalues(Name, Var, Result),
        writef('%t: %t\n', [Name, Result]).


t:-
        statistics,
        entitiy_number(color, Color),
        entitiy_number(shape, Shape),
        entitiy_number(material, Material),
       
        % constrain
        comp_tab_as_tuples(color, shape, Tcs),
        incomp_tab_as_tuples(material, shape, Tms),
        tuples_in([[Color, Shape]], Tcs),
        tuples_in([[Material, Shape]], Tms),

        % set single values
        domain_value(shape, circle, N),
        Shape = N,

        % list result
        write_out(color, Color),
        write_out(shape, Shape),
        write_out(material, Material),
        statistics.

--

Kind regards

Uwe Lesta





------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...