Alloy Community

User login

Progress Bar/Indicator for the Solver

 
Posted on: Wed, 12/31/2008 - 01:08
Joined: 2008-10-16
Points: 26
User is offline
Progress Bar/Indicator for the Solver
I am suggesting that a feature be added to the Analyzer so that as the command "Execute" is being... executed, the user is updated on the progress of the solver. This could be done with a simple progress bar, or even printouts to the output area every x number of states. This would be nice because it's often impossible to tell how long the solver will take; thus it's impossible to know whether it's worth waiting for or whether it would be better to just scrap the execution, reduce the scope, and start again.

I know from my experience with progress bars that come with operating systems that progress bars are not always very accurate time estimators, and are often way off the mark. However, from a psychological point of view, any indication of progress, albeit inaccurate, is welcomed as it makes the wait seem shorter. It puts thoughts like "The program is frozen" and "This will take forever" out of our heads and replaces them with ones like "The program is running very slowly" and "this will take a few minutes, I'll get a cup of tea and come back to it".
 
Posted on: Sun, 01/04/2009 - 09:10    #1
dnj
dnj's picture
Joined: 2008-06-06
Points: 39
User is offline
Yes, we know it would be nice to have. And in fact an earlier version of the Alloy Analyzer had a progress bar. But unfortunately SAT solvers don't offer feedback on progress, so to implement it, we had to modify the code of the SAT solvers themselves. We're very reluctant to repeat this because (a) it risks damaging performance or breaking correctness, and (b) it would mean that we could no longer immediately take advantage of improved solvers. How about trying to persuade the SAT solver community to take this on, with a standard interface?

We tend to find, btw, that for most models the solver comes back almost immediately if there is a counterexample or instance, so if it does nothing for a minute, that's often evidence that the formula is not satisfiable.

Also, we have implemented an experimental feature that allows you to instruct the solver to perform a series of analyses with incrementally growing scopes.

--Daniel
 
Posted on: Sun, 01/04/2009 - 10:52    #2
leberre's picture
Joined: 2008-04-23
Points: 115
User is offline
Daniel,

The problem is that there is no progress indicator that really estimates correctly the time needed to solve a problem.

I am aware of the work of your group on the subject (2000) :
http://sdg.csail.mit.edu/satsolvers/progressbar.html

and also the work of aloul et al (2002)
http://www.eecs.umich.edu/~faloul/Tools/satometer/

Minisat displays some statistics regarding the explored search space since release 1.0, but that information is far from accurate: you usually solve the problem after exploring only a few percents of the search space (we could not solve them in reasonable time if we had to explore the whole search space anyway :))

The current use of rapid restarts strategy does not help in predicting the progress of the SAT solver either.

I would love to provide an easy way to report progress in SAT4J. I have just no clue how to do it 1) accurately and 2) efficiently.

BTW, you can easily get information about the search performed by SAT4J using a SearchListener:
http://www.sat4j.org/maven2/org.sat4j.core/xref/org/sat4j/minisat/core/S...

--Another Daniel
 
Posted on: Sun, 01/04/2009 - 15:03    #3
Joined: 2008-07-16
Points: 7
User is offline
Hi,

> Also, we have implemented an experimental feature that allows you to instruct the solver to perform a series of analyses with incrementally growing scopes. --Daniel<

I'd like this experimental feature of Alloy would have a time limit (as Prover9/Mace4). Thus Alloy could search an answer with incrementally growing scopes until the time limit is reached (given a report of the maximum scope analized).

--Miguel Carrillo
 
Posted on: Mon, 01/05/2009 - 10:56    #4
nicolas.rouquette's picture
Joined: 2008-06-06
Points: 41
User is offline
Hum... it seems to me that the SAT4J SearchListener API could be useful for a domain-specific progress bar indicator. For example, if we had knowledge about the characteristics of the A4 => KK => SAT4J encoding, we could perhaps derive some kind of domain-specific progress metric in terms of the elements that the SearchListener API reports on, i.e., decision variables, units, ...

Isn't this related to the idea of specializing an unsat core algorithm for a particular domain?

Nicolas Rouquette
Flight Software Engineering & Architecture Group
Jet Propulsion Laboratory, Caltech, Pasadena, CA, USA

Syndicate content  

The development of this site is supported by the National Science Foundation under Computing Research Infrastructure Grant No. 0707612.

Theme originally designed by Chris Herberte