Re: Multiple optimal solutions

Tallys Hoover Yunes wrote:
> 
>         I am solving an optimization problem with ECLiPSe where
>         there are multiple optimal solutions, i.e. different
>         assignments of values to the variables that lead to the
>         same optimal value of the objective function.
> 
>         I would like to retrieve all these optimal assignments
>         but, as the minimization predicates are not resatisfiable,
>         this cannot be done simply through backtracking (I think...).
>         Is there another way to find all these solutions?


I don't think there is a way to modify the minimization predicates
to achieve this. The dilemma is the following: When you find a
solution during the branch-and-bound process, you want to
- look for one with lower cost (if you don't have the optimum yet)
- look for another one with the same cost (if optimum already reached)
However, at the time you find the solution, you don't know whether
it is the optimum or not, so you can't make this decision...

What you can do is compute the optimal cost first, and then do a new
search with the cost fixed to the optimum. That can give you all solutions:

[eclipse 1]: lib(fd).
...
yes.
[eclipse 2]: [user].
 p(a,8). p(c,3). p(d,5). p(b,2). p(e,7). p(f,2). p(g,7). p(h,2).

yes.
[eclipse 3]: min_max(p(X,C),C).             % gives one optimum only
Found a solution with cost 8
Found a solution with cost 3
Found a solution with cost 2

X = b
C = 2
yes.
[eclipse 4]: min_max(p(X,C),C,C,C).          % find optimum cost only
Found a solution with cost 8
Found a solution with cost 3
Found a solution with cost 2

X = X     <---- not instantiated!
C = 2
yes.
[eclipse 5]: min_max(p(X,C),C,C,C), p(X,C).  % get all optimal solutions
Found a solution with cost 8
Found a solution with cost 3
Found a solution with cost 2

X = b
C = 2     More? (;) 

X = f
C = 2     More? (;) 

X = h
C = 2
yes.



> 
>         By the way, could this same idea be implemented to find
>         all the assignments that lead to the second (and, in general,
>         i-th) best value of the objective function?

No, because in general you don't know the cost of the second
best solution. You know only the optimum and SOME worse solution,
and the second best may lie in between. So I guess you'd have
to call another optimization with these bounds on the cost.


I should mention at this point that in release 5.0 we have a new
library lib(branch_and_bound) which is a generic implementation
of b&b (independent of fd), which works with continuous variables,
supports dichotomic search and provides lower-level building blocks
that you can use to implement your own b&b style search strategies.
With this library, the above example looks as follows:

[eclipse 1]: lib(branch_and_bound).
branch_and_bound.pl compiled traceable 10608 bytes in 0.02 seconds

yes.
[eclipse 3]: bb_min(p(X,C),C,[],_,C,_), p(X,C).
Found a solution with cost 8
Found a solution with cost 3
Found a solution with cost 2
Found no solution with cost -1.0Inf .. 1

X = b
C = 2     More? (;) 

X = f
C = 2     More? (;) 

X = h
C = 2
yes.

-- 
 Joachim Schimpf              /             phone: +44 20 7594 8187
 IC-Parc, Imperial College   /            mailto:J.Schimpf@ic.ac.uk
 London SW7 2AZ, UK         /    http://www.icparc.ic.ac.uk/eclipse