[gecode-users] nested cost functions

[Mikael Zayenz Lagerkvist]

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/40d510dc/attachment.htm>