A kind of status bar to see where the Search is in csp

[Robert Van Dam]

Sounds a lot like an approximation to "computing in the limit":

http://portal.acm.org/citation.cfm?id=1096001&coll=ACM&dl=ACM&CFID=56757886&CFTOKEN=99364084&ret=1#Fulltext

Rob

On 6/9/06, Tim Heath <wgheath at saber.net> wrote:
> Is it an insane idea to have a type of heuristic for finding a solution
> that says something like:
>
> Find at least 1 solution
>
> Spend an hour or some amount of time looking for a better solution.  If
> in an hour no superior solution has been found take the first solution.
>
> The reason I like this idea is as the speed of computers go up the
> heuristic will improve automatically.
>
> Luis Quesada wrote:
> > Dear Torsten,
> >> I really like this approximation you propose. Of course, the
> >> 'progress  bar' may quick go to, say, 90% and then stay there forever
> >> and  eventually fall back again. Still, that's at least some feedback..
> >
> > Indeed the progress reported does not evolve monotonically. It is also
> > true that you may get stuck at 90%. However, this might suggest that
> > it is time to abort your search and have a look at the remaining 10%.
> > Maybe the reason why it is so hard to determine them is a bug in the
> > input data...
> >
> > In fact, I have found this approximation useful when dealing with
> > tough CSP where finding one solution may take hours.
> >
> > Cheers,
> > Luis
> >>
> >> On 08.06.2006, at 22:47, Luis Quesada wrote:
> >>
> >>> Well, you could consider the following approximation: to associate
> >>> the  status of your search with the number of variables determined
> >>> so far.
> >>> For this you got two options.
> >>> 1. (naive) have a thread per variable that sends a message to a
> >>> port  when the variable has been determined:
> >>> thread {Wait X} {Send P incCountOfVarsDetermined)} end
> >>> The thread reading the messages will print the status when
> >>> receiving  the incCountOfVarsDetermined messages.
> >>> 2. To keep a cell and update the contents of that cell at each
> >>> distribution step with the number of variables that have been
> >>> filtered  out. For this you will need to write your own distributor.
> >>> Have a look  at
> >>> http://www.mozart-oz.org/documentation/fdt/node40.html#chapter.user-
> >>> defined
> >>>
> >>> Luis
> >>>
> >>> Torsten Anders wrote:
> >>>
> >>>> The short answer is: this is not possible unfortunately.
> >>>> To realise this you would need to know the shape of your search
> >>>> tree   and where the solutions are in this search tree. But if you
> >>>> already   know that, then there is no search required anyway -- you
> >>>> would just   directly go to that solution.
> >>>> I'm no guru, though ;-)
> >>>> Best,
> >>>> Torsten
> >>>> On 08.06.2006, at 21:45, Tim Heath wrote:
> >>>>
> >>>>> Hi Oz Gurus,
> >>>>>
> >>>>> I want to make a kind of status bar showing how the search is
> >>>>> going   for csp application.  Any ideas how to do that?  I know if
> >>>>> I look at   the explorer it shows the tree as it is being
> >>>>> populated.  What I am   not clear on is if there is a way to know
> >>>>> if it is like 50% done or   75% done at any period of time
> >>>>> programatically.
> >>>>>
> >>>>> Oz rocks!
> >>>>>
> >>>>> _____________________________________________________________________
> >>>>> __ __________
> >>>>> mozart-users mailing list
> >>>>> mozart-users at ps.uni-sb.de
> >>>>> http://www.mozart-oz.org/mailman/listinfo/mozart-users
> >>>>>
> >>>>>
> >>>> --
> >>>> Torsten Anders
> >>>> Sonic Arts Research Centre • Queen's University Belfast
> >>>> Frankstr. 49 • D-50996 Köln
> >>>> Tel: +49-221-3980750
> >>>> www.torsten-anders.de
> >>>> strasheela.sourceforge.net
> >>>
> >>>
> >>> _______________________________________________________________________
> >>> __________
> >>> mozart-users mailing list
> >>> mozart-users at ps.uni-sb.de
> >>> http://www.mozart-oz.org/mailman/listinfo/mozart-users
> >>>
> >>>
> >> --
> >> Torsten Anders
> >> Sonic Arts Research Centre • Queen's University Belfast
> >> Frankstr. 49 • D-50996 Köln
> >> Tel: +49-221-3980750
> >> www.torsten-anders.de
> >> strasheela.sourceforge.net
> >>
> >>
> >
> > _________________________________________________________________________________
> >
> > mozart-users mailing list
> > mozart-users at ps.uni-sb.de
> > http://www.mozart-oz.org/mailman/listinfo/mozart-users
> >
>
>
>
> _________________________________________________________________________________
> mozart-users mailing list                               mozart-users at ps.uni-sb.de
> http://www.mozart-oz.org/mailman/listinfo/mozart-users
>