Towards a Problem-Solving Service

          Next in thread

I'd like to explore problem-solving systems, especially systems for solving challenging problems, such as NP-complete problems.

I've been thinking about this for about twenty years and would love to see it realized.

I have several posts in mind and will elaborate upon them as time permits.

The topics I'd like to write on include:

• Problem-solving engines for solving a single problem
• The intelligent application of a collection of tools to solve instances of a problem efficiently
• Problem-solving systems - systems based upon graphs in which each node is a problem, edges between nodes are transformations between problems, and associated with some of the nodes are problem-solving engines. The goal of a problem-solving system is to solve a catalog of problems efficiently making good use of the available engines and transformations.
• The Adaptive Market pattern, which is a pattern for a multi-level free-market framework for selecting and applying the best tools for tasks that learns from experience and incorporates the elements of prediction, estimation, bidding, reputation, and adaptation.
• A problem-solving service, which would implement a problem-solving system and make its services available commercially

Let's start by thinking about an engine for solving problem P, which we'll assume is a challenging problem (e.g. boolean satisfiability, k-clique exists).

Our goal is to maximize the throughput of this engine and maximize the percentage of problem instances that we are able to solve.

One characteristic of NP-complete problems is that a good algorithm for solving one may be very efficient for solving nearly all instances of that problem and then blow up on a small minority of instances.

We probably won't be able to solve every instance of P, and one of the tricks we'll have to learn is to learn when to stop efforts to solve a difficult problem instance. Some instances may prove such a challenge to our algorithms that it could take many years to solve one, even though nearly all similar-looking instances can be solved in seconds.

Around twenty years go, as I was working on my dissertation, I realized that I had developed several tools for determining whether a boolean expression is satisfiable, and it wasn't at clear when to apply a tool to a given problem.

This realization, and the fun I had in thinking about it, shaped my dissertation, which I titled Elements of an Expert System for Determining the Satisfiability of General Boolean Expressions. The center of this work involved the constraint calculus, Elegant Normal Form, and the reduction of constraint trees to elegance. I also began to explore how to use the small collection of tools to effectively determine satisfiability.

While I have yet to implement the expert system that I'd envisioned, I've done a lot more thinking about the problem.

The central problem is this: Once we have more that one way of attacking a problem, how do we know which one to use?

Let's assume that we have two algorithms, A and B, for solving problem P. Neither is clearly more efficient than the other in general - each is efficient for some problem instances and inefficient for others.

Rather than speak of efficiency, I'd like to start speaking in terms of 'cost', a metric that could cover many things but that we'll measure in terms of execution time for now. Executing an algorithm to solve a problem has a cost. Attempting to solve a problem but failing to do so has a penalty that can be expressed in terms of cost.

Our goal, then, is to minimize the cost of solving a sequence of problems on an engine.

Which algorithm, A or B, should we pick to solve instance I of problem P?

It really depends upon what we've learned about the behavior of A and B and what a characterization of I suggests in light of what we know about A and B.

We'll work with a problem-instance space - a space of one or more dimensions, each of which is a metric of a problem instance.

Each problem instance corresponds to a point in this space. We'll be lookint into identifying regions of this space that are 'safe' and ones that are 'risky'. - regions in which all instances are easy for algorithm X and regions in whch isnstances that are difficult for X are found.

Consider boolean expressions and the problem of determining whether a boolean expression is satisfiable (can it be made to evalute to True?). There are many obvious metrics of boolean expressions (e.g. the number of literals, variables, negators in the Negative Normal Form), several that are less obvious (e.g. the number of clauses in the CNF and DNF equivalents of the expression) and some that I've made up (e.g. the degree of coincidence).

Which of these descriptive metrics are good at predicting a property that we're interested in?

An example

This example is borrowed from my May 31, 2008 post:

Applet displaying a beautiful rotating plot of four metrics on 2000 Boolean expressions

I found that a metric that I called 'degree of coincidence', based upon an aspect of the structure of the expression, was a great predictor for whether expressions were tautologies or contradictions.

The Java applet (hopefully) running above displays four pieces of information about several hundred randomly generated boolean expressions.

The color of each dot is the expression's logical class: tautologies, contradictions, and expressions that are both satisfiable and falsifiable.

This is a static view of similar data:

In this view, the horizontal axis is the log₁₀ of the number of clauses in the Conjunctive Normal Form (CNF) equivalent of the expression and the vertical axis is the log₁₀ of the number of clauses in the Disjunctive Normal Form (DNF) equivalent of the expression.

Gorgeous.

The third spatial dimension, projecting out from the screen for the static view, is the Degree of Coincidence for the expression. I'll define this metric much later when I start to present some of my work on boolean expressions.

The important thing to note is how well the Degree of Coincidence separates tautologies from contradictions.

For fun: If you click on the left side of the spinning cluster, it will slow down; if you click on the right side of the spinning clust, it will speed up. Repeat.

This instance space has four dimensions, one for each of the four boolean expression metrics. The problem in this case is to determine the logical class of an expression and three other metrics were chosen as being possible predictive metrics of logical class.

I remember when I first created and played with a spinnable point cloud similar to the one shown - I was in love. The shape is beautiful, the approach to working with visualized data is powerful, all three metrics are good predictors, and the degree of coincidence is remarkable good at separating tautologies from contradictions.

A set of metrics doesn't have to be a good predictor in all regions of an instance space to be useful. Other sets of metrics may be better predictors in other regions of the space. Even if some regions of the the space have no good predictors of a property, we'll benefit from the existence of the ones that do.

How do we discover good predictive metrics? By experiment. Theoretical analysis may suggest further investigation of some metrics, but I think experiment - Monte Carlo studies and the accumulation of metrics from real problems - will lead us most efficiently to the most powerful metrics.

We'll want to build up a statistical database of dozens of metrics for each instance of a problem. Include metrics that you think may be of value, but also include metrics that are simply measurable. We're starting out ignorant and will need to accumulate, analyze, and play with a lot of data before useful sets of predictive metrics and the regions in which they are effective can be discovered.

We'll want to track other information as well. For example, suppose that we have several collections of boolean expressions from a company that does chip design. We'll want to record the categories and families of circuit that these expressions are defining or derived from. When we attempt to make predictions regarding the properties of an expression that comes from this company in the future, being able to focus on the metrics for related expressions while having the metrics for all sampled expressions at our disposal may improve our predictions.

I can't overemphasize the importance of playing with the data - some useful patterns may appear, even if over small regions, that would be difficult to discover by more conventional statistical analysis.

So, how do we decide which tool to use?

First, we need to create many metrics, do Monte Carlo studies on a large number of problem instances, collecting metric measurements for each, analyze and play with the resulting data to identify metrics that appear to be good predictors for the properties we're interested in. Time consuming and expensive, but it needs to be done once well and can be augmented with data from the processing of real problem instances and their off-line exploration in the future.

Once we have a sufficient understanding of our metric database, we can devise branching plans of attack for problem instances based upon their characteristics. We'll want to use inexpensive metrics on our instance that will begin to move us down the branches of this plan tree, reserving the more expensive metrics for when they are needed, if at all.

Next, we take a problem instance that we've been asked to solve, we can begin to follow the plan tree, making measurements of metrics and branching as guided by the plan and its underlying statistical database.

We have many of proceeding, even with only two algorithms and no parameters. Some of them are:

• Apply Algorithm A
• Apply Algorithm B
• Apply Algorithm A and B in parallel
• Apply Algorithm A for Y seconds, then apply Algorithm B
• Apply Algorithm B for Z seconds, then apply Algorithm A

Assuming that parallel processing is not available to us, we might, guided by our statistical database, execute a sequence of actions as follows for instance I:

1. Calculate Metric₁₄ and Metric₂₇ for I
2. Based on these values, calculate Metric₃ for I
3. Based on this value, apply Algorithm B to I for 3.4 seconds, retaining its state if unsolved
4. Unsolved, so obtain Metric₈ and Metric₄₂ from the state of Algorithm B
5. Based on these values, calculate Metric₅ for I
6. Based on this value, apply Algorithm A until completion

That's enough for tonight - I've got a good mystery to get back to.

          Next in thread

Copyright and Legal Notices

All Rights Reserved.