IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v147y2006i1p87-10710.1007-s10479-006-0063-2.html
   My bibliography  Save this article

A primogenitary linked quad tree data structure and its application to discrete multiple criteria optimization

Author

Listed:
  • Minghe Sun

Abstract

A data structure called the primogenitary linked quad tree is developed. Each node in the data structure has a pointer to its parent, a pointer to its immediate existing younger sibling, a pointer to its eldest existing son, and an integer as its successorship to its parent. To access any other son of a node, the first-born existing son must be accessed first. The siblings of the same parent are managed as a linked list. This data structure is an extension or enhancement of the traditional quad tree data structure. The primogenitary linked quad tree is applied to discrete multiple criteria optimization for the identification, storage, and retrieval of nondominated criterion vectors. Algorithms managing this data structure are developed and implemented. Major advantages of using the primogenitary linked quad tree instead of the traditional quad tree are savings in memory or storage space and savings in execution time. Examples are provided to demonstrate the application. A computational experiment is conducted to test the performances of the data structure and the algorithms. Computational results show that this data structure uses only a small fraction of the CPU time used by the traditional quad tree to perform the same task. Using this data structure, the identification, storage and retrieval of nondominated criterion vectors become an easy task for discrete multiple criteria optimization problems with many criteria and hundreds of thousands criterion vectors. This data structure can also be used for storage and retrieval of data with composite keys in other applications. Copyright Springer Science + Business Media, LLC 2006

Suggested Citation

  • Minghe Sun, 2006. "A primogenitary linked quad tree data structure and its application to discrete multiple criteria optimization," Annals of Operations Research, Springer, vol. 147(1), pages 87-107, October.
    • Handle: RePEc:spr:annopr:v:147:y:2006:i:1:p:87-107:10.1007/s10479-006-0063-2
    DOI: 10.1007/s10479-006-0063-2
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-006-0063-2
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-006-0063-2?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Sun, Minghe, 2005. "Some issues in measuring and reporting solution quality of interactive multiple objective programming procedures," European Journal of Operational Research, Elsevier, vol. 162(2), pages 468-483, April.
    2. Sun, Minghe & Steuer, Ralph E., 1996. "InterQuad: An interactive quad tree based procedure for solving the discrete alternative multiple criteria problem," European Journal of Operational Research, Elsevier, vol. 89(3), pages 462-472, March.
    3. Minghe Sun & Ralph E. Steuer, 1996. "Quad-Trees and Linear Lists for Identifying Nondominated Criterion Vectors," INFORMS Journal on Computing, INFORMS, vol. 8(4), pages 367-375, 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. Nathan Adelgren & Pietro Belotti & Akshay Gupte, 2018. "Efficient Storage of Pareto Points in Biobjective Mixed Integer Programming," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 324-338, May.
    2. 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.
    3. 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.
    4. 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. 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.
    2. Krzysztof S. Targiel & Maciej Nowak & Tadeusz Trzaskalik, 2018. "Scheduling non-critical activities using multicriteria approach," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 26(3), pages 585-598, September.
    3. 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.
    4. Nowak, Maciej, 2007. "Aspiration level approach in stochastic MCDM problems," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1626-1640, March.
    5. Scholz, Michael & Dorner, Verena & Schryen, Guido & Benlian, Alexander, 2017. "A configuration-based recommender system for supporting e-commerce decisions," European Journal of Operational Research, Elsevier, vol. 259(1), pages 205-215.
    6. Zhang Jiangao & Shitao Yang, 2016. "On the Lexicographic Centre of Multiple Objective Optimization," Journal of Optimization Theory and Applications, Springer, vol. 168(2), pages 600-614, February.
    7. Sun, Minghe & Steuer, Ralph E., 1996. "InterQuad: An interactive quad tree based procedure for solving the discrete alternative multiple criteria problem," European Journal of Operational Research, Elsevier, vol. 89(3), pages 462-472, March.
    8. Torabi, S.A. & Mansouri, S.A., 2015. "Integrated business continuity and disaster recovery planning: Towards organizational resilienceAuthor-Name: Sahebjamnia, N," European Journal of Operational Research, Elsevier, vol. 242(1), pages 261-273.
    9. Nathan Adelgren & Pietro Belotti & Akshay Gupte, 2018. "Efficient Storage of Pareto Points in Biobjective Mixed Integer Programming," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 324-338, May.
    10. Nowak, Maciej, 2006. "INSDECM--an interactive procedure for stochastic multicriteria decision problems," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1413-1430, December.
    11. Farhad Hassanzadeh & Hamid Nemati & Minghe Sun, 2013. "Robust Optimization for Interactive Multiobjective Programming with Imprecise Information Applied to R&D Project Portfolio Selection," Working Papers 0194mss, College of Business, University of Texas at San Antonio.
    12. C Gagné & M Gravel & W L Price, 2005. "Using metaheuristic compromise programming for the solution of multiple-objective scheduling problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(6), pages 687-698, June.
    13. Jaszkiewicz, Andrzej, 2004. "On the computational efficiency of multiple objective metaheuristics. The knapsack problem case study," European Journal of Operational Research, Elsevier, vol. 158(2), pages 418-433, October.
    14. Steuer, Ralph E. & Piercy, Craig A., 2005. "A regression study of the number of efficient extreme points in multiple objective linear programming," European Journal of Operational Research, Elsevier, vol. 162(2), pages 484-496, April.
    15. Hassanzadeh, Farhad & Nemati, Hamid & Sun, Minghe, 2014. "Robust optimization for interactive multiobjective programming with imprecise information applied to R&D project portfolio selection," European Journal of Operational Research, Elsevier, vol. 238(1), pages 41-53.

    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:spr:annopr:v:147:y:2006:i:1:p:87-107:10.1007/s10479-006-0063-2. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.