Re: minimize

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
>