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

An Additive Algorithm for Solving Linear Programs with Zero-One Variables

Author

Listed:
  • Egon Balas

    (Centre of Mathematical Statistics, Rumanian Academy, Bucharest)

Abstract

An algorithm is proposed for solving linear programs with variables constrained to take only one of the values 0 or 1. It starts by setting all the n variables equal to 0, and consists of a systematic procedure of successively assigning to certain variables the value 1, in such a way that after trying a (small) part of all the 2 n possible combinations, one obtains either an optimal solution, or evidence of the fact that no feasible solution exists. The only operations required under the algorithm are additions and subtractions; thus round-off errors are excluded. Problems involving up to 15 variables can be solved with this algorithm by hand in not more than 3–4 hours. An extension of the algorithm to integer linear programming and to nonlinear programming is available, but not dealt with in this article.

Suggested Citation

  • Egon Balas, 1965. "An Additive Algorithm for Solving Linear Programs with Zero-One Variables," Operations Research, INFORMS, vol. 13(4), pages 517-546, August.
    • Handle: RePEc:inm:oropre:v:13:y:1965:i:4:p:517-546
    DOI: 10.1287/opre.13.4.517
    as

    Download full text from publisher

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

    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:oropre:v:13:y:1965:i:4:p:517-546. 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.