A quantitative evaluation 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*, MIDA*, and IDA*_CR. The second type of methods are called available-memory search (AMS) methods, since they attempt to exploit the available memory to reduce node re-expansion. Sample methods in this category are ITS, MA*, RA*, MREC, and SMA*. lit this paper, we survey and compare preview limited-memory search methods. In particular, we present far the first time, a comprehensive performance evaluation of three of the best LMS methods, viz., IDA* ITS, and SMA*, by testing them on random search trees of various characteristics.