Say I have a black box implementation of the simplex algorithm given. Even though the worst case complexity is exponential, the implementation is fast for all cases I have tried.
Is there a good/systematic way to create an example of inputs which will require exponential execution time?
I have tried to create examples similar to the Klee-Minty cube, but that didn't scale exponentially based on the number of inputs.
I found this question, which contains a lot of useful pointers: https://cstheory.stackexchange.com/questions/2373/complexity-of-the-simplex-algorithm
I'm not aware of any way to do this, and if it were relatively easy someone would have come up with it a long time ago. Examples like the ones first published by Klee and Minty are constructed for a particular version of the simplex method by careful analysis of the pivoting rule. You've posited a black box version of the simplex analysis that would make such analysis difficult if not impossible.
You say that your algorithm is an exponential time algorithm, but if I have to treat it as a black box there's no way for me to determine an exponential upper bound for the running time, or an exponential lower bound for the running time, or even that the algorithm is correct.