Re: minimize

From: Warwick Harvey <wh_at_icparc.ic.ac.uk>
Date: Fri 02 Aug 2002 03:20:59 PM GMT
Message-ID: <20020802162059.R22613@tempest.icparc.ic.ac.uk>
Hi Marc,

My turn...  :)

On Fri, Aug 02, 2002 at 01:52:37PM +0100, Marc van Dongen wrote:
> Hi there,
> 
> 
> 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.

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

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).

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?

Cheers,
Warwick
Received on Fri Aug 02 16:21:13 2002

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