IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v42y1994i4p677-687.html
   My bibliography  Save this article

A Greedy Randomized Adaptive Search Procedure for the Two-Partition Problem

Author

Listed:
  • Manuel Laguna

    (University of Colorado, Boulder, Colorado)

  • Thomas A. Feo

    (University of Texas, Austin, Texas)

  • Hal C. Elrod

    (Princeton Transportation Consulting Group, Inc., Burlington, Massachusetts)

Abstract

We present a greedy randomized adaptive search procedure ( GRASP ) for the network 2-partition problem. The heuristic is empirically compared with the Kernighan-Lin (K&L) method on a wide range of instances. The GRASP approach dominates K&L with respect to solution value on a large percentage of the instances tested. The ability of GRASP to find optimal solutions is assessed by comparing its performance with a general purpose mixed integer programming package.

Suggested Citation

  • Manuel Laguna & Thomas A. Feo & Hal C. Elrod, 1994. "A Greedy Randomized Adaptive Search Procedure for the Two-Partition Problem," Operations Research, INFORMS, vol. 42(4), pages 677-687, August.
    • Handle: RePEc:inm:oropre:v:42:y:1994:i:4:p:677-687
    DOI: 10.1287/opre.42.4.677
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.42.4.677
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.42.4.677?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
    ---><---

    Citations

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


    Cited by:

    1. A J Higgins & L A Laredo, 2006. "Improving harvesting and transport planning within a sugar value chain," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(4), pages 367-376, April.
    2. Yogesh K. Agarwal, 2002. "Design of Capacitated Multicommodity Networks with Multiple Facilities," Operations Research, INFORMS, vol. 50(2), pages 333-344, April.
    3. Drexl, Andreas & Salewski, Frank, 1997. "Distribution requirements and compactness constraints in school timetabling," European Journal of Operational Research, Elsevier, vol. 102(1), pages 193-214, October.
    4. Jan Böttcher & Andreas Drexl & Rainer Kolisch & Frank Salewski, 1999. "Project Scheduling Under Partially Renewable Resource Constraints," Management Science, INFORMS, vol. 45(4), pages 543-559, April.
    5. Sánchez-Oro, J. & López-Sánchez, A.D. & Hernández-Díaz, A.G. & Duarte, A., 2022. "GRASP with strategic oscillation for the α-neighbor p-center problem," European Journal of Operational Research, Elsevier, vol. 303(1), pages 143-158.
    6. Drexl, Andreas & Salewski, Frank, 1996. "Distribution Requirements and Compactness Constraints in School Timetabling. Part II: Methods," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 384, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    7. Andreas Schirmer, 2000. "Case‐based reasoning and improved adaptive search for project scheduling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 47(3), pages 201-222, April.
    8. Dell'Amico, Mauro & Trubian, Marco, 1998. "Solution of large weighted equicut problems," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 500-521, April.
    9. Serigne Gueye & Philippe Michelon, 2005. "“Miniaturized” Linearizations for Quadratic 0/1 Problems," Annals of Operations Research, Springer, vol. 140(1), pages 235-261, November.
    10. Nonobe, Koji & Ibaraki, Toshihide, 1998. "A tabu search approach to the constraint satisfaction problem as a general problem solver," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 599-623, April.
    11. Xu Wang & Guohua Gan & Ling-Yun Wu, 2020. "Framework and algorithms for identifying honest blocks in blockchain," PLOS ONE, Public Library of Science, vol. 15(1), pages 1-14, January.
    12. Böttcher, Jan & Drexl, Andreas & Kolisch, Rainer & Salewski, Frank, 1996. "Project scheduling under partially renewable resource constraints," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 398, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    13. Raúl Martín-Santamaría & Ana D. López-Sánchez & María Luisa Delgado-Jalón & J. Manuel Colmenar, 2021. "An Efficient Algorithm for Crowd Logistics Optimization," Mathematics, MDPI, vol. 9(5), pages 1-19, March.
    14. Schirmer, Andreas & Riesenberg, Sven, 1997. "Parameterized heuristics for project scheduling: Biased random sampling methods," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 456, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    15. Panos M. Pardalos & Tianbing Qian & Mauricio G.C. Resende, 1998. "A Greedy Randomized Adaptive Search Procedure for the Feedback Vertex Set Problem," Journal of Combinatorial Optimization, Springer, vol. 2(4), pages 399-412, December.
    16. El-Ghazali Talbi, 2016. "Combining metaheuristics with mathematical programming, constraint programming and machine learning," Annals of Operations Research, Springer, vol. 240(1), pages 171-215, May.
    17. Sacramento Quintanilla & Francisco Ballestín & Ángeles Pérez, 2020. "Mathematical models to improve the current practice in a Home Healthcare Unit," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(1), pages 43-74, March.
    18. Schirmer, Andreas & Riesenberg, Sven, 1998. "Class-based control schemes for parameterized project scheduling heuristics," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 471, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    19. Alejandra Casado & Sergio Pérez-Peló & Jesús Sánchez-Oro & Abraham Duarte, 2022. "A GRASP algorithm with Tabu Search improvement for solving the maximum intersection of k-subsets problem," Journal of Heuristics, Springer, vol. 28(1), pages 121-146, February.
    20. Corberan, A. & Marti, R. & Sanchis, J. M., 2002. "A GRASP heuristic for the mixed Chinese postman problem," European Journal of Operational Research, Elsevier, vol. 142(1), pages 70-80, October.
    21. A. D. López-Sánchez & J. Sánchez-Oro & M. Laguna, 2021. "A New Scatter Search Design for Multiobjective Combinatorial Optimization with an Application to Facility Location," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 629-642, May.
    22. Charles Fleurent & Fred Glover, 1999. "Improved Constructive Multistart Strategies for the Quadratic Assignment Problem Using Adaptive Memory," INFORMS Journal on Computing, INFORMS, vol. 11(2), pages 198-204, May.
    23. Salewski, Frank & Bartsch, Thomas, 1994. "A comparison of genetic and greedy randomized algorithms for medium-to-short-term audit-staff scheduling," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 356, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    24. Schirmer, Andreas, 1998. "Case-based reasoning and improved adaptive search for project scheduling," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 472, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    25. M. T. Alonso & R. Alvarez-Valdes & F. Parreño, 2020. "A GRASP algorithm for multi container loading problems with practical constraints," 4OR, Springer, vol. 18(1), pages 49-72, March.

    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:inm:oropre:v:42:y:1994:i:4:p:677-687. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.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.