Executing a program with a temporary directory and measuring the running time
Well, firstly, don't be afraid of empty lines. This code is quite hard to read.

Secondly, functions is good invention. ;) That code as it is now is a bare piece of code, with no indication of where most of the parameters come from, and it seems that the acceptable solutions is a global, as you have capitalized it? That doesn't make much sense to me.

Just as you have a function called run() to run the program, it would make sense to have a function to run it multiple times, with the tests for that you have.

I'm also not sure why you trap KeyboardInterrupt, without seeming to actually do anything with it, except setting the status, and then testing the status. You could just do exit directly from that exception handler, that would be clearer.

Otherwise it seems fine. Feedback on correctness is impossible when your code isn't a running example. But then again, tests generally work better than code reviews there, although they are not exclusive.