Stochastic Greedy Algorithms: A Learning-Based Approach to Combinatorial Optimization

Abstract

Research in combinatorial optimization initially focused on finding optimal solutions to various problems. Researchers realized the importance of alternative approaches when faced with large practical problems that took too long to solve optimally and this led to approaches like simulated annealing and genetic algorithms which could not guarantee optimality, but yielded good solutions within a reasonable amount of computing time. In this paper we report on our experiments with stochastic greedy algorithms (SGA) � perturbed versions of standard greedy algorithms. SGA incorporates the novel idea of learning from optimal solutions, inspired by data-mining and other learning approaches. SGA learns some characteristics of optimal solutions and then applies them while generating its solutions. We report results based on applying this approach to three different problems � knapsack, combinatorial auctions and single-machine job sequencing. Overall, the method consistently produces solutions significantly closer to optimal than standard greedy approaches. SGA can be seen in the space of approximate algorithms as falling between the very quick greedy approaches and the relatively slower soft computing approaches like genetic algorithms and simulated annealing. SGA is easy to understand and implement -- once a greedy solution approach is known for a problem, it becomes possible to very quickly rig up a SGA for the problem. SGA has explored only one aspect of learning from optimal solutions. We believe that there is a lot of scope for variations on the theme, and the broad idea of learning from optimal solutions opens up possibilities for new streams of research.