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

Minghe Sun
Additional contact information
Minghe Sun: University of Texas at San Antonio

No 9, Working Papers from College of Business, University of Texas at San Antonio

Abstract: 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.

Keywords: Primogenitary Quad Tree; Data Structure; Heuristic Procedures; Binary Optimization; Combinatorial Optimization (search for similar items in EconPapers)
JEL-codes: C61 (search for similar items in EconPapers)
Pages: 25 pages
Date: 2007-02-15
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://interim.business.utsa.edu/wps/MSS/0010MSS-061-2007.pdf Full text (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:tsa:wpaper:0037mss

Access Statistics for this paper

More papers in Working Papers from College of Business, University of Texas at San Antonio Contact information at EDIRC.
Bibliographic data for series maintained by Wendy Frost ().