IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v24y1977i1p91-104.html
   My bibliography  Save this article

Heuristic 0-1 Linear Programming: An Experimental Comparison of Three Methods

Author

Listed:
  • Stelios H. Zanakis

    (West Virginia College of Graduate Studies)

Abstract

This paper examines the performance of three heuristic methods (Senju-Toyoda, Kochen-berger et al. and Hillier) when applied to the 0-1 linear programming problem with nonnegative coefficients. Their effectiveness, measured in terms of computing time, error and relative error, is evaluated on a set of problems from the literature and randomly generated 0-1 test problems with nonnegative coefficients. Analysis of variance and stepwise regressions are employed to study the effect of the number of variables, number of constraints and degree of constraint slackness. The methods exhibited some similarities bui also marked differences in their behavior. Interestingly enough, the larger the number of variables the belter the accuracy of each method. Error differences among the three methods were significant (1:0.8:0.2) yet small (less than 2% on the average) for many practical situations. Hillier's algorithm was the most accurate but much slower and more core demanding than the other two, which makes it difficult or impossible to use for solving large 0-1 problems. Kochenberger's et al. heuristic was the fastest (most accurate) of the three in tightly (loosely) constrained problems. In general the Senju-Toyoda algorithm was the fastest, but least accurate on small and medium size problems. Suggestions are made for selecting the "best" heuristic based on the problem characteristics.

Suggested Citation

  • Stelios H. Zanakis, 1977. "Heuristic 0-1 Linear Programming: An Experimental Comparison of Three Methods," Management Science, INFORMS, vol. 24(1), pages 91-104, September.
  • Handle: RePEc:inm:ormnsc:v:24:y:1977:i:1:p:91-104
    DOI: 10.1287/mnsc.24.1.91
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.24.1.91
    Download Restriction: no

    File URL: https://libkey.io/10.1287/mnsc.24.1.91?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. Barbucha, Dariusz, 2004. "Three approximation algorithms for solving the generalized segregated storage problem," European Journal of Operational Research, Elsevier, vol. 156(1), pages 54-72, July.
    2. Knolmayer, Gerhard, 1981. "A simulation study of simplification strategies in the development of optimization models," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 96, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    3. Yalçın Akçay & Haijun Li & Susan Xu, 2007. "Greedy algorithm for the general multidimensional knapsack problem," Annals of Operations Research, Springer, vol. 150(1), pages 17-29, March.
    4. Corbett, Charles J. & Debets, Frank J.C. & Van Wassenhove, Luk N., 1995. "Decentralization of responsibility for site decontamination projects: A budget allocation approach," European Journal of Operational Research, Elsevier, vol. 86(1), pages 103-119, October.
    5. Freville, Arnaud, 2004. "The multidimensional 0-1 knapsack problem: An overview," European Journal of Operational Research, Elsevier, vol. 155(1), pages 1-21, May.
    6. Raymond R. Hill & Charles H. Reilly, 2000. "The Effects of Coefficient Correlation Structure in Two-Dimensional Knapsack Problems on Solution Procedure Performance," Management Science, INFORMS, vol. 46(2), pages 302-317, February.
    7. Bahram Alidaee & Vijay P. Ramalingam & Haibo Wang & Bryan Kethley, 2018. "Computational experiment of critical event tabu search for the general integer multidimensional knapsack problem," Annals of Operations Research, Springer, vol. 269(1), pages 3-19, October.

    More about this item

    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:inm:ormnsc:v:24:y:1977:i:1:p:91-104. 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.