On the number of iterations of local improvement algorithms

A general model of local improvement algorithms in combinatorial optimization accurately confirms performance characteristics often observed in individual cases. The model predicts exponentially bad worst case and low order polynomial average run times for single optimum problems including some linear complementarity problems and linear programming. For problems with multiple local optima, most notably those that are NP-complete, average speed is linearly bounded but accuracy is poor.     

Low order polynomial bounds on the expected performance of local improvement algorithms

We present a general abstract model of local improvement, applicable to such diverse cases as principal pivoting methods for the linear complementarity problem and hill climbing in artificial intelligence. The model accurately predicts the behavior of the algorithms, and allows for a variety of probabilistic assumptions that permit degeneracy. Simulation indicates an approximately linear average number of iterations under a variety of probability assumptions. We derive theoretical bounds of 2en logn and en ² for different distributions, respectively, as well as polynomial bounds for a broad class of probability distributions. We conclude with a discussion of the applications of the model to LCP and linear programming.The author was supported by the New Faculty Research Development Program of the Georgia Institute of Technology. This work is based on the author's Ph.D. thesis, performed under George Dantzig at Stanford 1978–81, at the Systems Optimization Laboratory. While at Stanford, research was supported in part by Department of Energy Contract AM03-76SF00326, PA #DE-AT03-76ER72018; Office of Naval Research Contract N00014-75-C-0267; National Science Foundation Grants MCS76-81259, MCS-7926009 and ECS-8012974; and Army Research Office Contract DAA29-79-C-0110. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.     

Improving understanding,learning, and performances of novices in dynamic managerial simulation games

Simulations are increasingly used in training and education because of their success and their advantages as a learning method. However, it has also been observed that the dynamic complexity of simulations creates learning difficulties, and that performance tends to plateau quickly at a level well below benchmark performance. To overcome this difficulty, a gradual‐increase‐in‐complexity approach is proposed, which suggests developing simpler versions of a simulation game that can be used as part of the training. Accordingly, the authors developed a series of inventory‐management simulations and conducted an experiment. The results indicate an improvement in the success of the inventory‐management simulation as a training tool. © 2009 Wiley Periodicals, Inc. Complexity, 2010