IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v140y2005i1p215-23310.1007-s10479-005-3972-6.html
   My bibliography  Save this article

Some Classes of Valid Inequalities and Convex Hull Characterizations for Dynamic Fixed-Charge Problems under Nested Constraints

Author

Listed:
  • Fred Glover
  • Hanif Sherali

Abstract

This paper studies the polyhedral structure of dynamic fixed-charge problems that have nested relationships constraining the flow or activity variables. Constraints of this type might typically arise in hierarchical or multi-period models and capacitated lot-sizing problems, but might also be induced among choices of key variables via an LP-based post-optimality analysis. We characterize several classes of valid inequalities and inductively derive convex hull representations in a higher dimensional space using lifting constructs based on the Reformulation-Linearization Technique. Relationships with certain known classes of valid inequalities for single item capacitated lot-sizing problems are also identified. Copyright Springer Science + Business Media, Inc. 2005

Suggested Citation

  • Fred Glover & Hanif Sherali, 2005. "Some Classes of Valid Inequalities and Convex Hull Characterizations for Dynamic Fixed-Charge Problems under Nested Constraints," Annals of Operations Research, Springer, vol. 140(1), pages 215-233, November.
    • Handle: RePEc:spr:annopr:v:140:y:2005:i:1:p:215-233:10.1007/s10479-005-3972-6
    DOI: 10.1007/s10479-005-3972-6
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-005-3972-6
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-005-3972-6?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Sun, Minghe & Aronson, Jay E. & McKeown, Patrick G. & Drinka, Dennis, 1998. "A tabu search heuristic procedure for the fixed charge transportation problem," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 441-456, April.
    2. CORNUEJOLS, Gérard & FISHER, Marshall L. & NEMHAUSER, George L., 1977. "Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms," LIDAM Reprints CORE 292, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. M. W. Padberg & T. J. Van Roy & L. A. Wolsey, 1985. "Valid Linear Inequalities for Fixed Charge Problems," Operations Research, INFORMS, vol. 33(4), pages 842-861, August.
    4. Padberg, M.W. & Van Roy, T.J. & Wolsey, L.A., 1985. "Valid linear inequalities for fixed charge problems," LIDAM Reprints CORE 656, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. Nozick, Linda K. & Turnquist, Mark A., 1998. "Integrating inventory impacts into a fixed-charge model for locating distribution centers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 34(3), pages 173-186, September.
    6. WOLSEY, Laurence A., 1989. "Submodularity and valid inequalities in capacitated fixed charge networks," LIDAM Reprints CORE 842, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    7. BARANY, Imre & VAN ROY, Tony & WOLSEY, Laurence A., 1984. "Uncapacitated lot-sizing: the convex hull of solutions," LIDAM Reprints CORE 605, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    8. Hanif D. Sherali & Warren P. Adams & Patrick J. Driscoll, 1998. "Exploiting Special Structures in Constructing a Hierarchy of Relaxations for 0-1 Mixed Integer Problems," Operations Research, INFORMS, vol. 46(3), pages 396-405, June.
    9. A. Victor Cabot & S. Selcuk Erenguc, 1984. "Some branch‐and‐bound procedures for fixed‐cost transportation problems," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 31(1), pages 145-154, March.
    10. Nozick, L. K., 2001. "The fixed charge facility location problem with coverage restrictions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 37(4), pages 281-296, 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. Borisovsky, P. & Dolgui, A. & Eremeev, A., 2009. "Genetic algorithms for a supply management problem: MIP-recombination vs greedy decoder," European Journal of Operational Research, Elsevier, vol. 195(3), pages 770-779, June.
    2. Ali, Agha Iqbal & O'Connor, Debra J., 2010. "The impact of distribution system characteristics on computational tractability," European Journal of Operational Research, Elsevier, vol. 200(2), pages 323-333, 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. Alper Atamtürk & Simge Küçükyavuz, 2005. "Lot Sizing with Inventory Bounds and Fixed Costs: Polyhedral Study and Computation," Operations Research, INFORMS, vol. 53(4), pages 711-730, August.
    2. Quentin Louveaux & Laurence Wolsey, 2007. "Lifting, superadditivity, mixed integer rounding and single node flow sets revisited," Annals of Operations Research, Springer, vol. 153(1), pages 47-77, September.
    3. Alper Atamtürk & Martin Savelsbergh, 2005. "Integer-Programming Software Systems," Annals of Operations Research, Springer, vol. 140(1), pages 67-124, November.
    4. Jenn-Rong Lin & Linda Nozick & Mark Turnquist, 2006. "Strategic design of distribution systems with economies of scale in transportation," Annals of Operations Research, Springer, vol. 144(1), pages 161-180, April.
    5. Sherali, Hanif D. & Lee, Youngho & Park, Taehyung, 2000. "New modeling approaches for the design of local access transport area networks," European Journal of Operational Research, Elsevier, vol. 127(1), pages 94-108, November.
    6. Syed Ali, Sharifah Aishah & Doostmohammadi, Mahdi & Akartunalı, Kerem & van der Meer, Robert, 2018. "A theoretical and computational analysis of lot-sizing in remanufacturing with separate setups," International Journal of Production Economics, Elsevier, vol. 203(C), pages 276-285.
    7. Dimitri J. Papageorgiou & Alejandro Toriello & George L. Nemhauser & Martin W. P. Savelsbergh, 2012. "Fixed-Charge Transportation with Product Blending," Transportation Science, INFORMS, vol. 46(2), pages 281-295, May.
    8. Absi, Nabil & Kedad-Sidhoum, Safia, 2008. "The multi-item capacitated lot-sizing problem with setup times and shortage costs," European Journal of Operational Research, Elsevier, vol. 185(3), pages 1351-1374, March.
    9. Hanif D. Sherali & Taehyung Park, 2000. "Discrete equal‐capacity p‐median problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 47(2), pages 166-183, March.
    10. Binyuan Chen & Simge Küçükyavuz & Suvrajeet Sen, 2011. "Finite Disjunctive Programming Characterizations for General Mixed-Integer Linear Programs," Operations Research, INFORMS, vol. 59(1), pages 202-210, February.
    11. Wei-Kun Chen & Liang Chen & Mu-Ming Yang & Yu-Hong Dai, 2018. "Generalized coefficient strengthening cuts for mixed integer programming," Journal of Global Optimization, Springer, vol. 70(1), pages 289-306, January.
    12. Agostinho Agra & Marielle Christiansen & Alexandrino Delgado, 2013. "Mixed Integer Formulations for a Short Sea Fuel Oil Distribution Problem," Transportation Science, INFORMS, vol. 47(1), pages 108-124, February.
    13. Doostmohammadi, Mahdi & Akartunalı, Kerem, 2018. "Valid inequalities for two-period relaxations of big-bucket lot-sizing problems: Zero setup case," European Journal of Operational Research, Elsevier, vol. 267(1), pages 86-95.
    14. Anulark Pinnoi & Wilbert E. Wilhelm, 1998. "Assembly System Design: A Branch and Cut Approach," Management Science, INFORMS, vol. 44(1), pages 103-118, January.
    15. 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.
    16. Pablo Miranda & Rodrigo Garrido, 2006. "A Simultaneous Inventory Control and Facility Location Model with Stochastic Capacity Constraints," Networks and Spatial Economics, Springer, vol. 6(1), pages 39-53, March.
    17. Diego Klabjan & George L. Nemhauser, 2002. "A Polyhedral Study of Integer Variable Upper Bounds," Mathematics of Operations Research, INFORMS, vol. 27(4), pages 711-739, November.
    18. Shi Li, 2020. "Constant Approximation Algorithm for Nonuniform Capacitated Multi-Item Lot Sizing via Strong Covering Inequalities," Mathematics of Operations Research, INFORMS, vol. 45(3), pages 947-965, August.
    19. Sanjay Dominik Jena & Jean-François Cordeau & Bernard Gendron, 2017. "Lagrangian Heuristics for Large-Scale Dynamic Facility Location with Generalized Modular Capacities," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 388-404, August.
    20. Masoud Yaghini & Mohammad Karimi & Mohadeseh Rahbar & Mohammad Hassan Sharifitabar, 2015. "A Cutting-Plane Neighborhood Structure for Fixed-Charge Capacitated Multicommodity Network Design Problem," INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 48-58, February.

    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:spr:annopr:v:140:y:2005:i:1:p:215-233:10.1007/s10479-005-3972-6. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.