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 <[email protected]>wrote: > 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
