[gecode-users] MinimizeScript: Beginners Question

[Christian Schulte]

Hi Josef,

Thanks for your observations as far as MPG is concerned. I'll think them
through and look how to improve. The information being spread out can't
really be helped much as each location takes a different angle and different
depth. But I promise I'll think...

Then printing each solution is actually what you want (I guess): normally,
finding a best solution takes so long that you will have to settle for the
solution that has been found last after the time is up. But maybe there
could be an additional switch which would only make sense in a best solution
search scenario: -print-last where only the last solution found is printed,
and if a time out is encountered then also the last and not necessarily best
solution is printed. Would that make you happy?

Christian

--
Christian Schulte, www.ict.kth.se/~cschulte/


-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Josef Eisl
Sent: Tuesday, January 17, 2012 3:52 PM
To: cschulte at kth.se
Cc: users at gecode.org
Subject: Re: [gecode-users] MinimizeScript: Beginners Question

Hello!

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
sense.

> 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
experience.

> 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
MinimizeScript?

> I hope that helps

Thank you very much for your quick and detailed answers!

Josef

_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users