Re: [eclipse-users] Finding all optimal solutions

From: Joachim Schimpf (Independent Contractor) <jschimpf_at_cisco.com>
Date: Mon, 03 Dec 2007 09:18:42 +1100
Peter Nilsson wrote:
> Is there any way of finding ALL optimal (integer) solutions by e.g. 
> branch and bound (bb_min)?

What you can do is compute the optimal cost first, and then do a new
search with the cost fixed to that optimum.  E.g. given the program

:- lib(ic).
:- lib(branch_and_bound).

p(a,8). p(c,3). p(d,5). p(b,2). p(e,7). p(f,2). p(g,7). p(h,2).


Then the following query gives you all solutions. Note that p/2 is
called twice, once inside bb_min/6 (which does not instantiate the
decision variables), and then outside (with Cost instantiated to 2):

?- bb_min(p(X, Cost), Cost, [], _, Cost, _),  p(X, Cost).
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
Cost = 2
Yes (0.00s cpu, solution 1, maybe more)
X = f
Cost = 2
Yes (0.00s cpu, solution 2, maybe more)
X = h
Cost = 2
Yes (0.00s cpu, solution 3)


A more detailed discussion is in
http://www.eclipse-clp.org/archive/eclipse-users/0074.html


-- Joachim
Received on Sun Dec 02 2007 - 22:19:00 CET

This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET