A Primogenitary Linked Quad Tree Approach for Solution Storage and Retrieval in Heuristic Binary Optimization

A data structure, called the primogenitary linked quad tree (PLQT), is used to store and retrieve solutions in heuristic solution procedures for binary optimization problems. Solutions represented by vectors of binary variables are encoded into vectors of integers in a much lower dimension. The vectors of integers are used as composite keys to store and retrieve solitions in the PLQT. An algorith processing trial solutions for possible insertion into or retrieval from the PLQT is developed. Examples are provided to demonstrate the way the algorithm works. Another Alogorithm traversing the PLQT is also developed. Computational results show that the PLQT approach takes only a very tiny portion of the CPU time taken by the PLQT managing the solutions is negligible as compared to that taken by a heuristic procedure for any reasonably hard to solve binary optimization problems, as shown in a tabu search heuristic procedure for the capacitated facility location problem. Compared to the hashing approach, the PLQT approach takes about the same amount of CPU time but much less memory space while completely eliminating collision.