[gecode-users] MinimizeScript: Beginners Question

Josef Eisl zapster at zapster.cc
Tue Jan 17 15:52:18 CET 2012


On 01/17/2012 02:31 PM, Christian Schulte wrote:
> Hi,
> Please let me take your questions in turn.
> 1. Changing the relation from strict (that is, "<") to a non-strict (that
> is, "<=") will typically not work. It would entail that you do not only find
> all _optimal_ solutions but all solution for each and every cost value! So
> normally that will be way too many solutions! Try it out with Gist on a
> small example and you will see that this will make things break down.

Ups, my bad. Clearly adding a non strict constraint does not make much

> Should I add a tip in MPG that the order must be strict for things to work?

Maybe, but I my eyes it is more confusing that
MinimizeSpace/MinimizeScript return non-optimal solutions, at least for
a new user. Some other things about MPG and optimization that are not
straight forward in my opinion:

1. Information is spread over several chapters:
   - 2.5 Best solution search
   - 3.2 Using a cost function
   - 6.3 Support for cost-based optimization
   - 7.4 Search engines

2. Best Solution Search engine
It is mentioned in 2.5 and 7.4 but not 3.2 and 6.3 and there are no
links to the other sections. Maybe it should be stated more clearly that
BAB or Restart must be used for best solution search.

3. constrain()
In 2.5: "Note that every space defines a default constrain() member
function (to keep the design of models simple). If a model does not
re-define the constrain() member function, the default function will be
called which throws an exception of type SpaceConstrainUndefined (as
this is a modeling error)".
In my eyes the second sentence is not true as OptimizeSpace provides a
valid constrain().

These are rather beginner problems than problems of MPG. Gecode is one
of the best documented free software I've seen. I just want to share my

> 2. To find all optimal solutions, I would first find _one_ optimal solution
> as normal. Then I would find all solutions (starting a new search) where the
> cost value is equal to the optimal const value.

I see. That makes sense.

> 3. You see that printing "all" optimal solutions with respect to 1. and 2.
> does not really make much sense.

Ok using -solutions for optimal solutions does not work. But how about
printing only the last (optimal if -solutions 0) solution with

> I hope that helps

Thank you very much for your quick and detailed answers!


More information about the users mailing list