Randall Britten wrote: >> However, in general, I haven't been able to find an efficient >> (polynomial time) algorithm to compute this break-down (but I also >> haven't yet proved that the problem is NP-complete, so there may be a >> polynomial time solution even if P != NP). >> > Hi Andrew > > If possible, please outline the algorithm that you have found, even though > it is not efficient.

The most trivial algorithm is of course a simple depth first exhaustive search. I believe this is what Justin already started implementing. Firstly, I'll define the exact problem that I'm trying to solve in formal language. ======== There are several ways to formulate the problem, but matrix notation seems the cleanest. Let A be an n*n matrix, where n is the number of equations in the model (which haven't already been used), and is also the number of unknown variables (which must be equal for the problem to be correctly constrained). Let A_ij = 1 if the ith equation involves the jth unknown, and 0 otherwise. The objective is to find the smallest possible non-empty set E such that |E| = |V|, where V = {j where exists i in E such that A_ij = 1 } ======= Algorithm findSmallestSystem(A, n): for setSize from 1 through to n inclusive: result <- findSystemOfSize(A, n, setSize, {}, 1) if result is not failure: return result end end Not reached because there is always a system of size n. end Algorithm findSystemOfSize(A, n, addMembers, existingMembers, lowestConsidered): if (addMembers != 0): result <- findSystemOfSize(A, n, addMembers - 1, existingMembers \ {i}, lowestConsidered + 1) if result is not failure: return result end result <- findSystemOfSize(A, n, addMembers, existingMembers, lowestConsidered + 1) if result is not failure: return result end return failure because this branch is impossible. end V <- {} for j from 1 through to n inclusive: for i from 1 through to n inclusive: if A_ij = 1: V <- V union {j} next iteration of the outer loop end end end if |V| = |existingMembers|: return existingMembers else return failure end end I am measuring the time complexity of this by the number of times we check if A_ij = 1. In the worst case, which is that the only possible system is the system of size n, we fail for systems of size 1 through to n-1, and run to the end of the nth step before failing. This takes n^2 * (choose(n, 1) + choose(n, 2) + ... + choose(n, n)) = n^2 * (2^n - 1) steps. We can optimise certain cases. For example, if we can isolate disjoint sets of variables and equations using a disjoint sets algorithm, we can do better on this case (this won't improve the worst case, because there is no guarantee of this being possible). We can also adapt the above algorithm to be branch-and-bound by noting that even before we get to the end of a branch, if |V| > |E|, then it is never going to shrink as a result of adding more equations so we can close off that branch. Another possibility might be to implement a beam search based on some kind of graph connectivity heuristic. However, it is not clear if this would actually improve real world problems. Also, it is worth noting that the above algorithm builds up the equation set. We can also attack the problem from the other end (i.e. a divisive algorithm) by starting from the set of all equations, which means we know that |V| = |E|, and removing single equations or pairs of equations and so on from |E| to see if this causes |V| to shrink by the corresponding amount. What I suspect will be the best improvement for average world models would combine the disjoint sets separator with alternating between divisive (shrink until we fail) and build-up (grow until we succeed) algorithm attempts. This might work for real world problems if we limit the number of equations we try to add or remove before just returning the best divisive algorithm result even though it may be suboptimal. However, whether this is actually useful is something we would need to try with a number of models to find out; we may find that we still need the metadata as a fallback approach for models where the heuristic is not useful. Best regards, Andrew > > Regards, > Randall > > _______________________________________________ > cellml-discussion mailing list > cellml-discussion@cellml.org > http://www.cellml.org/mailman/listinfo/cellml-discussion _______________________________________________ cellml-discussion mailing list cellml-discussion@cellml.org http://www.cellml.org/mailman/listinfo/cellml-discussion