COMPARISON AND ANALYSIS OF LIMITED-MEMORY BRANCH-AND-BOUND ALGORITHMS

摘要

Branch-and-bound (B&B) best-first search (BFS) is a widely applicable method that requires the least number of node expansions to obtain optimal solutions to combinatorial optimization problems (COPs). However, for many problems of interest, its memory requirements are enormous and can far exceed the available memory capacity on most systems. To circumvent this problem, two types of limited-memory search (LMS) methods have been proposed. Methods belonging to the first type are based purely on depth-first search (DFS) and require very little memory compared to that available on current systems, but they may perform significant node re-expansions, and hence generally require appreciable amounts of time; these are called minimal-memory search (MMS) methods. Examples of such methods are DFBB, IDA, DFS, IDA_CR, MIDA, RIDA, IE, RBFS, and IES. The second type of methods are called available-memory search (AMS) methods, since they attempt to exploit the available memory to reduce node re-expansions. Sample methods in this category are ITS, MA, RA, SMA, MREC, SNC, and MRBFS. In this paper, we survey and compare previous limited-memory search methods and present a performance evaluation of three important LMS methods: IDA, IE, and SMA.