John
07-24-2003, 06:00 AM
"Cagdas Ozgenc" <co19@removeme.cornell.edu> wrote in message
news:bfoge9$a6a$1@news01.cit.cornell.edu...
Some of my collegues are extensively developing applications that deal
with NP-complete problems. Approaches mostly involve attacking the search space in a random fashion backed up by heuristics. So far we can only assume
that the apps are working as designed and do not have any idea how to test
these kind of apps at any level (unit, system, etc). Random behavior makes it
very hard for us to write test cases. Constraints that guarantee to hold only expose themselves at the very macro level.
At the end we feel as if we had built a very complicated random number generator. Things happen, the app comes up with an output. We run it on various input data and then speculate on its effectiveness.
The only kind of debugging we can do is to make sure that the apps don't crash. Nothing in terms of functionality. There are lots of heuristic functions, probability calculations. Who knows whether they are producing the desired output.
Any suggestions?
1. comp.software.testing
That is the place for all things testing (cross-posted accordingly) .
Someone there will probably be able to assist on general schemes for testing
components that solve NP-type problems.
2. Devise a means of reasonably measuring (rather than "speculating" on)
effectiveness.
You could hold historical output data (raw or processed) for a given set of
inputs. From this, a measure of "effectiveness" is computed. The next time
changes to your impl results in a 'better' output for a known input, that
output
becomes the benchmark for subsequent tests of said inputs.
Regards,
Steven Perryman
news:bfoge9$a6a$1@news01.cit.cornell.edu...
Some of my collegues are extensively developing applications that deal
with NP-complete problems. Approaches mostly involve attacking the search space in a random fashion backed up by heuristics. So far we can only assume
that the apps are working as designed and do not have any idea how to test
these kind of apps at any level (unit, system, etc). Random behavior makes it
very hard for us to write test cases. Constraints that guarantee to hold only expose themselves at the very macro level.
At the end we feel as if we had built a very complicated random number generator. Things happen, the app comes up with an output. We run it on various input data and then speculate on its effectiveness.
The only kind of debugging we can do is to make sure that the apps don't crash. Nothing in terms of functionality. There are lots of heuristic functions, probability calculations. Who knows whether they are producing the desired output.
Any suggestions?
1. comp.software.testing
That is the place for all things testing (cross-posted accordingly) .
Someone there will probably be able to assist on general schemes for testing
components that solve NP-type problems.
2. Devise a means of reasonably measuring (rather than "speculating" on)
effectiveness.
You could hold historical output data (raw or processed) for a given set of
inputs. From this, a measure of "effectiveness" is computed. The next time
changes to your impl results in a 'better' output for a known input, that
output
becomes the benchmark for subsequent tests of said inputs.
Regards,
Steven Perryman