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

A Note on Bounding a Class of Linear Programming Problems, Including Cutting Stock Problems

Author

Listed:
  • A. A. Farley

    (Monash University, Melbourne, Victoria, Australia)

Abstract

In LP problems with an extremely large number of possible structural variables, solution to optimality is not always required. A bound can be used to terminate such LPs. Such a bound is presented for a class of problem that includes most cutting stock formulations.

Suggested Citation

  • A. A. Farley, 1990. "A Note on Bounding a Class of Linear Programming Problems, Including Cutting Stock Problems," Operations Research, INFORMS, vol. 38(5), pages 922-923, October.
    • Handle: RePEc:inm:oropre:v:38:y:1990:i:5:p:922-923
    DOI: 10.1287/opre.38.5.922
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.38.5.922
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.38.5.922?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. José M. Valério de Carvalho, 2005. "Using Extra Dual Cuts to Accelerate Column Generation," INFORMS Journal on Computing, INFORMS, vol. 17(2), pages 175-182, May.
    2. David R. Morrison & Jason J. Sauppe & Edward C. Sewell & Sheldon H. Jacobson, 2014. "A Wide Branching Strategy for the Graph Coloring Problem," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 704-717, November.
    3. Ambros Gleixner & Stephen J. Maher & Benjamin Müller & João Pedro Pedroso, 2020. "Price-and-verify: a new algorithm for recursive circle packing using Dantzig–Wolfe decomposition," Annals of Operations Research, Springer, vol. 284(2), pages 527-555, January.
    4. Zeger Degraeve & Marc Peeters, 2003. "Optimal Integer Solutions to Industrial Cutting-Stock Problems: Part 2, Benchmark Results," INFORMS Journal on Computing, INFORMS, vol. 15(1), pages 58-81, February.
    5. François Vanderbeck, 2000. "Exact Algorithm for Minimising the Number of Setups in the One-Dimensional Cutting Stock Problem," Operations Research, INFORMS, vol. 48(6), pages 915-926, December.
    6. Wang, Dujuan & Yin, Yunqiang & Cheng, T.C.E., 2018. "Parallel-machine rescheduling with job unavailability and rejection," Omega, Elsevier, vol. 81(C), pages 246-260.
    7. Alberto Caprara & Giuseppe Lancia & See-Kiong Ng, 2001. "Sorting Permutations by Reversals Through Branch-and-Price," INFORMS Journal on Computing, INFORMS, vol. 13(3), pages 224-244, August.
    8. Suliman, Saad M. A., 2001. "Pattern generating procedure for the cutting stock problem," International Journal of Production Economics, Elsevier, vol. 74(1-3), pages 293-301, December.
    9. Omid Shahvari & Rasaratnam Logendran & Madjid Tavana, 2022. "An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems," Journal of Scheduling, Springer, vol. 25(5), pages 589-621, October.
    10. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    11. Schepler, Xavier & Rossi, André & Gurevsky, Evgeny & Dolgui, Alexandre, 2022. "Solving robust bin-packing problems with a branch-and-price approach," European Journal of Operational Research, Elsevier, vol. 297(3), pages 831-843.
    12. Wang, Zheng & Sheu, Jiuh-Biing, 2019. "Vehicle routing problem with drones," Transportation Research Part B: Methodological, Elsevier, vol. 122(C), pages 350-364.
    13. Marjan van den Akker & Han Hoogeveen & Steef van de Velde, 2002. "Combining Column Generation and Lagrangean Relaxation to Solve a Single-Machine Common Due Date Problem," INFORMS Journal on Computing, INFORMS, vol. 14(1), pages 37-51, February.
    14. C Alves & J M Valério de Carvalho, 2008. "New integer programming formulations and an exact algorithm for the ordered cutting stock problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(11), pages 1520-1531, November.
    15. Ng, T.S. & Lee, L.H. & Chew, E.P., 2006. "Build-pack planning for hard disk drive assembly with approved vendor matrices and stochastic demands," European Journal of Operational Research, Elsevier, vol. 175(2), pages 1117-1140, December.
    16. Mauro Dell’Amico & Giovanni Righini & Matteo Salani, 2006. "A Branch-and-Price Approach to the Vehicle Routing Problem with Simultaneous Distribution and Collection," Transportation Science, INFORMS, vol. 40(2), pages 235-247, May.
    17. Kerem Bülbül & Philip Kaminsky & Candace Yano, 2004. "Flow shop scheduling with earliness, tardiness, and intermediate inventory holding costs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 51(3), pages 407-445, April.
    18. Gislaine Mara Melega & Silvio Alexandre de Araujo & Reinaldo Morabito, 2020. "Mathematical model and solution approaches for integrated lot-sizing, scheduling and cutting stock problems," Annals of Operations Research, Springer, vol. 295(2), pages 695-736, December.
    19. Jing-Quan Li, 2014. "Transit Bus Scheduling with Limited Energy," Transportation Science, INFORMS, vol. 48(4), pages 521-539, November.
    20. Delorme, Maxence & Iori, Manuel & Martello, Silvano, 2016. "Bin packing and cutting stock problems: Mathematical models and exact algorithms," European Journal of Operational Research, Elsevier, vol. 255(1), pages 1-20.
    21. Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, June.
    22. Suliman, S.M.A., 2006. "A sequential heuristic procedure for the two-dimensional cutting-stock problem," International Journal of Production Economics, Elsevier, vol. 99(1-2), pages 177-185, February.
    23. Laszlo Ladanyi & Jon Lee & Robin Lougee-Heimer, 2005. "Rapid Prototyping of Optimization Algorithms Using COIN-OR: A Case Study Involving the Cutting-Stock Problem," Annals of Operations Research, Springer, vol. 139(1), pages 243-265, October.
    24. Zeger Degraeve & Linus Schrage, 1999. "Optimal Integer Solutions to Industrial Cutting Stock Problems," INFORMS Journal on Computing, INFORMS, vol. 11(4), pages 406-419, November.

    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:38:y:1990:i:5:p:922-923. 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.