Re: minimize

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

: The problem here is that I suspect you're unlikely to get a suitable upper
: bound on the cost before starting the branch-and-bound process, at which
: point the bound is only valid in the current branch.  Everything I can think
: of to overcome this really goes against the grain in that it's pretty much
: the opposite of what one would normally do: if your initial COST is a long
: way from optimal and/or N is small these approaches could bite badly.  But
: you probably know all this.

That's why I don't want to abandon minimize because (at least for the
problem that I'm solving at the moment) the first solutions produced
by minimize are very good.
 
: Anyway, your best option (at least as a starting point) probably is to
: write your own labelling predicate which first imposes the constraint
: EXPR >= COST - N + 1 and then calls labeling/1 (or something more
: intelligent) as normal.  If no solution is found, there is no solution.  If

To prove that no solution exists will be difficult. It'll probably
be better to rely on minimize's default semantics.

: a solution is found, the search needs to be re-started with the new value
: for COST.  There are optimisation predicates in the branch_and_bound library
: which (at least when given the relevant options) do restart whenever a
: solution is found; use one of them.
: 
: If that's not enough, you could try digging out an ECLiPSe 5.2 distribution,
: which includes the source code of the branch_and_bound module, and try
: modifying it to do what you want.

I think I'll stick to what's currently available:-) As I already
mentioned the solutions are already pretty good.
 
: Do you have good heuristics for finding an almost-optimal solution, or some
: way of knowing when the solution you have is almost optimal?

Not really. I'm only just starting to understand some of the properties
of the problem. I'll have to look into it.


Regards,


Marc