From: Karen E Petrie <scomkep_at_zeus.hud.ac.uk>

Date: Fri 02 Aug 2002 02:08:30 PM GMT

Message-Id: <200208021408.PAA10455@dvorak.hud.ac.uk>

Date: Fri 02 Aug 2002 02:08:30 PM GMT

Message-Id: <200208021408.PAA10455@dvorak.hud.ac.uk>

Hi all, I know usually most querries are dealt by members of the ECLiPSe team at IC-Parc, but I have come across something simillar to this recently, so I thought I might give a a stab at an answer. I think you want the minimize/5 predicate, which is: minimize(+Goal, ?Template, +Lower +Upper, +Percentage) Where Goal is the term to minimise, C is the cost to minimse in respect to. Lower is the lower bound which any value less than can be considered a solution. Upper is the cost bound which is tightened every time a solution is found (i.e. it is the value which you have to beat everytime you try to find a lower value). Percentage is the amount to chnge by between looking for subsequent solutions. So a simple example (from the documentation) for minimize/2: X::1..3, C #= 3-X, minimize(indomain(X),C). Gives: Found a solution with cost 2 Found a solution with cost 1 Found a solution with cost 0 If we are happy with any solution below 2 i.e. 1 we can use minimze/5 to get: X::1..3, C #= 3-X, minimize(indomain(X),C,2,3,1). Gives: Found a solution with cost 2 Found a solution with cost 1 So all you need to do is write a predicate which trys to see if there is a soloution for COST=COST if there is then you can see if there is a solution between { COST - 1, COST - 2, ..., COST - N } using mimimixe/5. Hope this helps, Karen >Currently, I am working on an optimisation problem >which can be expressed as follows: > > minimize( labeling( LIST ), EXPR ). > >However, the problem that I am solving has the >nice property that if a solution has been found for >cost = COST, and if no solutions exist (for fixed N) >for cost in { COST - 1, COST - 2, ..., COST - N } >then the solution for cost = COST is optimal. > >Needless to say that I would like to make use of >this property. Can this be done with an existing >predicate or do I have to build such predicate >my self? > >Thanks in advance. > >Regards, > > >Marc van Dongen >-- >M.R.C. van Dongen | CS Dept University College Cork | () > dongen@cs.ucc.ie | Cork Constraint Computation Centre | /\ >+353(0)21 4903578 | Western Road | ASCII ribbon > | Cork, Ireland | against html mail >Received on Fri Aug 02 15:19:40 2002

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