# Re: minimize

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>
```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