From: Joachim Schimpf <j.schimpf_at_icparc.ic.ac.uk>

Date: Thu 20 Jul 2000 11:33:09 AM GMT

Message-ID: <3976E375.FA054B6F@icparc.ic.ac.uk>

Date: Thu 20 Jul 2000 11:33:09 AM GMT

Message-ID: <3976E375.FA054B6F@icparc.ic.ac.uk>

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/eclipseReceived on Thu Jul 20 12:33:58 2000

*
This archive was generated by hypermail 2.1.8
: Wed 16 Nov 2005 06:07:06 PM GMT GMT
*