IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v38y1991i1p53-69.html
   My bibliography  Save this article

An exact ceiling point algorithm for general integer linear programming

Author

Listed:
  • Robert M. Saltzman
  • Frederick S. Hillier

Abstract

We present an algorithm called the exact ceiling point algorithm (XCPA) for solving the pure, general integer linear programming problem (P). A recent report by the authors demonstrates that, if the set of feasible integer solutions for (P) is nonempty and bounded, all optimal solutions for (P) are “feasible 1‐ceiling points,” roughly, feasible integer solutions lying on or near the boundary of the feasible region for the LP‐relaxation associated with (P). Consequently, the XCPA solves (P) by implicitly enumerating only feasible 1‐ceiling points, making use of conditional bounds and “double backtracking.” We discuss the results of computational testing on a set of 48 problems taken from the literature.

Suggested Citation

  • Robert M. Saltzman & Frederick S. Hillier, 1991. "An exact ceiling point algorithm for general integer linear programming," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(1), pages 53-69, February.
    • Handle: RePEc:wly:navres:v:38:y:1991:i:1:p:53-69
    DOI: 10.1002/1520-6750(199102)38:13.0.CO;2-D
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/1520-6750(199102)38:13.0.CO;2-D
    Download Restriction: no
    File URL: https://libkey.io/10.1002/1520-6750(199102)38:13.0.CO;2-D?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
    ---><---

    References listed on IDEAS

    as
    1. C. A. Trauth, Jr. & R. E. Woolsey, 1969. "Integer Linear Programming: A Study in Computational Efficiency," Management Science, INFORMS, vol. 15(9), pages 481-493, May.
    2. John Haldi & Leonard M. Isaacson, 1965. "A Computer Code for Integer Solutions to Linear Programs," Operations Research, INFORMS, vol. 13(6), pages 946-959, December.
    3. Larry M. Austin & Parviz Ghandforoush, 1983. "An advanced dual algorithm with constraint relaxation for all‐integer programming," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 30(1), pages 133-143, March.
    4. Frederick S. Hillier, 1969. "Efficient Heuristic Procedures for Integer Linear Programming with an Interior," Operations Research, INFORMS, vol. 17(4), pages 600-637, August.
    5. Egon Balas, 1965. "An Additive Algorithm for Solving Linear Programs with Zero-One Variables," Operations Research, INFORMS, vol. 13(4), pages 517-546, August.
    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. Joseph, Anito & Gass, Saul I. & Bryson, Noel, 1998. "An objective hyperplane search procedure for solving the general all-integer linear programming (ILP) problem," European Journal of Operational Research, Elsevier, vol. 104(3), pages 601-614, February.
    2. Joseph, A. & Gass, S. I., 2002. "A framework for constructing general integer problems with well-determined duality gaps," European Journal of Operational Research, Elsevier, vol. 136(1), pages 81-94, January.

    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. Manfred Padberg, 2005. "Classical Cuts for Mixed-Integer Programming and Branch-and-Cut," Annals of Operations Research, Springer, vol. 139(1), pages 321-352, October.
    2. Mazzola, Joseph B. & Neebe, Alan W., 1999. "Lagrangian-relaxation-based solution procedures for a multiproduct capacitated facility location problem with choice of facility type," European Journal of Operational Research, Elsevier, vol. 115(2), pages 285-299, June.
    3. Abumoslem Mohammadi & Javad Tayyebi, 2019. "Maximum Capacity Path Interdiction Problem with Fixed Costs," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 36(04), pages 1-21, August.
    4. Joseph B. Mazzola & Robert H. Schantz, 1997. "Multiple‐facility loading under capacity‐based economies of scope," Naval Research Logistics (NRL), John Wiley & Sons, vol. 44(3), pages 229-256, April.
    5. Ghosh, Diptesh & Sumanta Basu, 2011. "Diversified Local Search for the Traveling Salesman Problem," IIMA Working Papers WP2011-01-03, Indian Institute of Management Ahmedabad, Research and Publication Department.
    6. Jain, A. S. & Meeran, S., 1999. "Deterministic job-shop scheduling: Past, present and future," European Journal of Operational Research, Elsevier, vol. 113(2), pages 390-434, March.
    7. Lijun Wei & Zhixing Luo, & Roberto Baldacci & Andrew Lim, 2020. "A New Branch-and-Price-and-Cut Algorithm for One-Dimensional Bin-Packing Problems," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 428-443, April.
    8. Christoph Neumann & Oliver Stein & Nathan Sudermann-Merx, 2019. "A feasible rounding approach for mixed-integer optimization problems," Computational Optimization and Applications, Springer, vol. 72(2), pages 309-337, March.
    9. Robert G. Dyson & Frances A. O’Brien & Devan B. Shah, 2021. "Soft OR and Practice: The Contribution of the Founders of Operations Research," Operations Research, INFORMS, vol. 69(3), pages 727-738, May.
    10. Joseph, A. & Gass, S. I., 2002. "A framework for constructing general integer problems with well-determined duality gaps," European Journal of Operational Research, Elsevier, vol. 136(1), pages 81-94, January.
    11. Freville, Arnaud, 2004. "The multidimensional 0-1 knapsack problem: An overview," European Journal of Operational Research, Elsevier, vol. 155(1), pages 1-21, May.
    12. Michael Brusco & Patrick Doreian, 2015. "An Exact Algorithm for the Two-Mode KL-Means Partitioning Problem," Journal of Classification, Springer;The Classification Society, vol. 32(3), pages 481-515, October.
    13. Thomas L. Magnanti, 2021. "Optimization: From Its Inception," Management Science, INFORMS, vol. 67(9), pages 5349-5363, September.
    14. Avinoam Perry, 1974. "A Strengthened Modified Dantzig Cut for All Integer Program," Discussion Papers 95, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    15. Sabah Bushaj & İ. Esra Büyüktahtakın, 2024. "A K-means Supported Reinforcement Learning Framework to Multi-dimensional Knapsack," Journal of Global Optimization, Springer, vol. 89(3), pages 655-685, July.
    16. Hasan Pirkul, 1987. "A heuristic solution procedure for the multiconstraint zero‐one knapsack problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 34(2), pages 161-172, April.
    17. Joseph, Anito & Gass, Saul I. & Bryson, Noel, 1998. "An objective hyperplane search procedure for solving the general all-integer linear programming (ILP) problem," European Journal of Operational Research, Elsevier, vol. 104(3), pages 601-614, February.
    18. Bala Shetty, 1990. "A relaxation/decomposition algorithm for the fixed charged network problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 37(2), pages 327-340, April.
    19. J. Glover & V. Quan & S. Zolfaghari, 2021. "Some new perspectives for solving 0–1 integer programming problems using Balas method," Computational Management Science, Springer, vol. 18(2), pages 177-193, June.
    20. S Das & D Ghosh, 2003. "Binary knapsack problems with random budgets," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(9), pages 970-983, September.

    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:wly:navres:v:38:y:1991:i:1:p:53-69. 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: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    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.