Re: minimize

Sorry about the delay in replying. We've had a power cut
over the weekend and mail is comming in slowly.

Warwick Harvey (wh@icparc.ic.ac.uk) wrote:

: What is it about minimize's behaviour that you would like to change, in
: order to try to exploit this?

If minimize( labeling( VARS ), EXPR ) results in a valid
labeling and cost COST, then it will post the constraint
EXPR < COST and will search for new solutions to
labeling( VARS ). If constraint propagation forces the domain
of EXPR to be such that COST - 1, COST -2, ..., COST - N + 1
are no longer in it, then I would like to stop. Especially if
EXPR has many values in its domain, this may save a lot.

: Note that if a solution has been found with cost COST, then minimize
: proceeds to search for a solution with *any* cost less than COST.  If it
: proceeded to try cost = COST-1, etc., then yes, one could stop when COST-N
: had no solution, but that's not the way it works (because in general that's
: not a particularly smart way to do it).

I know it's not the way it works. That's why I asked if it's
possible to do it differently:-)
 
: Is there some way of determining that COST-1 through COST-N have no solution
: that would be significantly cheaper than just looking for anything less than
: COST-1?

I believe that near an almost optimal solution it is
far more cheaper to find a solution with cost between
COST-1 and COST-N or to prove that such solution does not
exist. That's why I'm so interested  in it.

Regards,


Marc