This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Realff, M. J. Articles by Stephanopoulos, G. Search for Related Content

On the Application of Explanation-Based Learning to Acquire Control Knowledge for Branch and Bound Algorithms

Laboratory for Intelligent Systems in Process Engineering, Department of Chemical Engineering, Massachusetts Institute of Technology, Cambridge, MA 02139
Laboratory for Intelligent Systems in Process Engineering, Department of Chemical Engineering, Massachusetts Institute of Technology, Cambridge, MA 02139

The goal of this article is to present a methodology for the automatic acquisition of new control knowledge in the form of dominance and equivalence conditions, using an explanation-based learning algorithm from artificial intelligence. The acquisition of new control knowledge proceeds through the following stages: 1) Analysis of the problem-solving activity, generated from the application of a branch and bound algorithm on specific instance(s) of a class of problems. 2) Interpretation of the problem-solving activity and synthesis of new control knowledge, which can lead to more efficient solution of future problems. The generated control knowledge is provably correct within the theory of the given class of problems and the employed branch and bound strategy. Consequently, the number of nodes evaluated by a specific branch and bound algorithm is guaranteed to be reduced, as new control knowledge is continuously acquired from the solution of specific problems. The article presents the theoretical foundations for the handling of the above two tasks. It concludes with an application of the proposed approach to a mixed integer linear programming formulation of a batch scheduling problem.

Key words: Branch and Bound; artificial intelligence; scheduling