Why Optimization?

• In many cases, it’s easier to search for a counterexample than prove its non-existence.

• Examples:

  • Model checking
  • min-conflicts heuristic for Hubble scheduling
  • WALKSAT for Boolean satisfiability

Previous slide

Next slide

Back to first slide

View graphic version

I now digress and ask again the question others have raised before me: Why optimization? Why is optimization important is the general context of hybrid systems?

First, in many cases, it’s easier to search for a counterexample than prove its non-existence. For example, model checking has made quite an impact. In my experience with Zohar Manna's STeP system, I was surprised at how well the model-checker worked. Should I have been? As another example, Steven Minton et al at NASA admired the performance of a neural network for scheduling astromonical observations for the Hubble Space telescope. The studied the neural network and found that the performance came largely from from the application of a heuristic which they called min-conflicts. Applying this heuristic to constraint satisfaction search, they had the same success with great efficiency. Following their work, Selman, Levesque and Mitchell were impressed with min-conflicts, but didn't think a heuristic, stochastic optimization would work well for really hard 3SAT problems. They proved themselves wrong and the successful result was the GSAT algorithm from which evolved WALKSAT and other algorithms which exploit the power of stochastic heuristic search in that domain.

Now I'm not saying that optimization/search is the best approach for all hybrid system problems. I'm simply sharing a couple lessons whcih I've learned and relearned in a number of different contexts (including this research).

The first lesson is this: Be willing to try different approaches to problem solving (and try the simple ones first!). It's surprising how long it took us in CS to learn how well a stochastic local optimization procedure such as GSAT or WALKSAT works for difficult Boolean satisfiability problems. The second and more important take-home lesson isn't about deduction vs. model-checking, or deduction vs. optimization....It's more like "deduction AND optimization". We should understand and appreciate the benefits of each.

If one's desire to derive declarative knowledge of why something works, should it surprise us if a deductive approach is well-suited? Similarly, if one simply desires to find whether or not something can fail, isn't search for a failure natural and instructive in its own way? How might the two be used together?