IDEAS home Printed from https://ideas.repec.org/p/tsa/wpaper/0037mss.html
   My bibliography  Save this paper

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

Author

Listed:
  • Minghe Sun

    (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.

Suggested Citation

  • Minghe Sun, 2007. "A Primogenitary Linked Quad Tree Approach for Solution Storage and Retrieval in Heuristic Binary Optimization," Working Papers 0009, College of Business, University of Texas at San Antonio.
    • Handle: RePEc:tsa:wpaper:0037mss
    as

    Download full text from publisher

    File URL: http://interim.business.utsa.edu/wps/MSS/0010MSS-061-2007.pdf
    File Function: Full text
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Carlton, William B. & Barnes, J. Wesley, 1996. "A note on hashing functions and tabu search algorithms," European Journal of Operational Research, Elsevier, vol. 95(1), pages 237-239, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Minghe Sun & Zhen-Yu Chen & Zhi-Ping Fan, 2014. "A Multi-task Multi-kernel Transfer Learning Method for Customer Response Modeling in Social Media," Working Papers 0161mss, College of Business, University of Texas at San Antonio.
    2. Fathali Firoozi, 2008. "Boundary Distributions in Testing Inequality Hypotheses," Working Papers 0046, College of Business, University of Texas at San Antonio.
    3. Minghe Sun, 2008. "A Tabu Search Heuristic Procedure for the Capacitated Facility Location Problem," Working Papers 0050, College of Business, University of Texas at San Antonio.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Minghe Sun, 2007. "A Primogenitary Linked Quad Tree Approach for Solution Storage and Retrieval in Heuristic Binary Optimization," Working Papers 0009, College of Business, University of Texas at San Antonio.
    2. Sun, Minghe, 2011. "A primogenitary linked quad tree approach for solution storage and retrieval in heuristic binary optimization," European Journal of Operational Research, Elsevier, vol. 209(3), pages 228-240, March.
    3. Fathali Firoozi, 2008. "Boundary Distributions in Testing Inequality Hypotheses," Working Papers 0046, College of Business, University of Texas at San Antonio.
    4. Lai, Xiangjing & Hao, Jin-Kao & Yue, Dong, 2019. "Two-stage solution-based tabu search for the multidemand multidimensional knapsack problem," European Journal of Operational Research, Elsevier, vol. 274(1), pages 35-48.
    5. Qinghua Wu & Yang Wang & Fred Glover, 2020. "Advanced Tabu Search Algorithms for Bipartite Boolean Quadratic Programs Guided by Strategic Oscillation and Path Relinking," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 74-89, January.
    6. Wang, Yang & Wu, Qinghua & Glover, Fred, 2017. "Effective metaheuristic algorithms for the minimum differential dispersion problem," European Journal of Operational Research, Elsevier, vol. 258(3), pages 829-843.
    7. Minghe Sun & Zhen-Yu Chen & Zhi-Ping Fan, 2014. "A Multi-task Multi-kernel Transfer Learning Method for Customer Response Modeling in Social Media," Working Papers 0161mss, College of Business, University of Texas at San Antonio.
    8. R. Christopher L. Riley & Cesar Rego, 2019. "Intensification, diversification, and learning via relaxation adaptive memory programming: a case study on resource constrained project scheduling," Journal of Heuristics, Springer, vol. 25(4), pages 793-807, October.
    9. Minghe Sun, 2008. "A Tabu Search Heuristic Procedure for the Capacitated Facility Location Problem," Working Papers 0050, College of Business, University of Texas at San Antonio.

    More about this item

    Keywords

    Primogenitary Quad Tree; Data Structure; Heuristic Procedures; Binary Optimization; Combinatorial Optimization;
    All these keywords.

    JEL classification:

    • C61 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Optimization Techniques; Programming Models; Dynamic Analysis

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:tsa:wpaper:0037mss. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Wendy Frost (email available below). General contact details of provider: https://edirc.repec.org/data/cbutsus.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.