Combined analytical and empirical learning framework for branch and bound algorithms: the knapsack problem

Optimization methods are being applied to engineering problem solving with increasing frequency as computer hardware and software improves. The config uration of an optimization algorithm can make a significant difference to t he efficiency of the solution process. This article examines the use of one such optimization strategy, branch and bound, for the solution of the clas sic knapsack problem. It is shown that the best configuration of the algori thm can be data dependent and hence that an 'intelligent' optimization syst em will need to automatically configure itself with the control knowledge a ppropriate to the problems the user is solving. A two-step approach is take n to configuring the algorithm. First, an analytical learning method, expla nation based learning is used to derive a provably correct dominance condit ion for the knapsack problem. Second, the algorithm is configured with and without the condition, and subjected to rigorous statistical test of perfor mance, on the user's data, to decide which configuration is the best. (C) 1 999 Elsevier Science Ltd. All rights reserved.