4

I am new to gecode and constraint programming in general.

So far, I haven't had much trouble picking up gecode, it's great. But 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 solutions 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 explain how to implement this in Gecode, that would be really helpful. Thanks!

CapelliC
  • 59,646
  • 5
  • 47
  • 90
jda
  • 265
  • 2
  • 6
  • It seems that you are trying to perform a kind of multiobjective optimization. I am not sure whether it is supported by GeoCode. Minion says, for instance, explicitly that it supports only one objective function (or none at all). – Alexander Serebrenik Apr 13 '12 at 19:06

1 Answers1

3

You can define any kind of optimization criteria using the constrain member in a space in Gecode. See Section 2.5 in Modeling and Programming with Gecode for an example. In your case, the straight forward way would be to add a constrain member that adds a lexicographic constraint between the previous best solutions answer and the current space.

That being said, in general optimizing based on a lexicographic order can be wasteful (too much searching). It may often be better to first run a search optimizing the first component (X in your case). After that, re-run the search with the first components value fixed (X set to best possible value), and optimize the second value (Y in your case). Iterate as needed for all elements in the cost.

Zayenz
  • 1,914
  • 12
  • 11