2011/9/14 revo revo <[email protected]> > 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/
_______________________________________________ Gecode users mailing list [email protected] https://www.gecode.org/mailman/listinfo/gecode-users
