Re: [eclipse-clp-users] typical sources of duplicate solutions

Am 21.06.2010 11:31, schrieb Oliver Shycle:
> Dear ECLiPSe community,
>
> I am using ECLiPSe to solve a special kind of scheduling problem. My
> problem is coded as a set of many free vaiables and i have a whole
> bunch of constraints and reified constraints to express how a valid
> solution has to look like. Basically everything works pretty fine and
> as expected :-)
> The only drawback is that i am sometimes experiencing duplicate
> solutions, i.e. instantiations of variables that are absolutely
> identical, when i click the "more" button in the TkEclipse interface.
> I am asking myself where such duplicates might come from. I know that
> this potentially is very problem-specific. But maybe there are some
> "typical sources of duplicates" that I could check? At the moment I
> would have to start with a trial and error approach, because I don't
> have a clue where they might come from.
> Thanks for your help.
>
> Oliver.

Hi Oliver,

such a behaviour can occur when your search routine can freely select
the variables to be labelled. The search tree will then contain branches
where the variables are selected in different orders but, due to the
constraints, will be bound to the same values.

Consider the following program:

:- lib(ic).

test :-
    L = [X,Y],
    L #:: [0..3],
    X #= Y + 1,
    solve(L).

solve([]).
solve(L) :-
    delete(V,L,R),
    get_min(V,V),
    solve(R).


The delete/3 call is non-deterministic. During execution, when L is
[X,Y], V will be first bound to X. On backtracking, V will be bound to
Y. In both cases, the same solution (X == 1, Y == 0) will be returned.

In this simple case, wrapping delete/3 with once/1 will be sufficient to
avoid duplicate solutions. Depending on your problem and search
strategy, more complex steps may be required.

Cheers,
Thorsten