[gecode-users] nested cost functions

[revo revo]

Hi Mikael,

I see, thanks for the clarification. That makes sense (although it will
probably take me a while to figure out how to get it to work).

One additional question - for some reason when I use DFS, I am able to
return all solutions, but when I use BAB, I seem to only get one solution,
using the exact same Script class (with no other differences to how it's
called). Any reason for this?

~r

On Wed, Sep 14, 2011 at 2:49 AM, Mikael Zayenz Lagerkvist
<zayenz at gmail.com>wrote:

> 2011/9/14 revo revo <4evo.11.ove4 at gmail.com>
>
>> I am new to gecode (and constraint programming in general). So far, gecode
>> has been a joy to work with, even for a novice like me.
>>
>> I was wondering what is the best way to perform a "nested" cost function.
>> Specifically, I am looking to minimize X, but within the space of solutioins
>> for which X is equal, prefer solutions which minimize Y? I could probably
>> hack it by defining a cost function that looks like X*large_number+Y, but
>> I'd prefer to do this properly if there's a good solution.
>>
>> If anyone can point me to both the introductory literature (I see the
>> min-max algorithm, but being relatively new to the literature, I'm not sure
>> if the game-theoretic descriptions match what I am trying to do here) as
>> well as how to implement this in Gecode, that would be really helpful.
>>
>
>
> Hi,
>
> The cost function is a convenience function for the simple cases where what
> we want to optimize over is just a single variable. The general mechanism in
> Gecode  for optimizing using branch and bound search is the constrain
> function (see Section 2.5 in MPG for an explanation).
>
> In your case, the simple solution is to use a lexical ordering constraint
> over the array of variables. See MPG for details on lexical ordering
> constraints. This is the approach you should try first.
>
> In some cases, depending on the particular problem that you have and if it
> is hard to solve, it might be better to first optimize on the first
> variable. When the optimal solution to that is found, fix that value as a
> part of a new instance of your problem, and optimize on the second variable.
> Repeat for as many variables as you have. Running a search this way is a bit
> more involved (one needs to do a bit more in setting up the search), but can
> avoid potential long plateaus where the last variable is re-optimized for
> every new better value of the second to-last variable.
>
> Hope this helps,
> Mikael
>
> --
> Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20110914/66a5d9ed/attachment.htm>