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

Convex envelope results and strong formulations for a class of mixed‐integer programs

Author

Listed:
  • Meltem Denizel
  • S. Selcuk Erenguc
  • Hanif D. Sherali

Abstract

In this article we present a novel technique for deriving the convex envelope of certain nonconvex fixed‐charge functions of the type that arise in several related applications that have been considered in the literature. One common attribute of these problems is that they involve choosing levels for the undertaking of several activities. Two or more activities share a common resource, and a fixed charge is incurred when any of these activities is undertaken at a positive level. We consider nonconvex programming formulations for these problems in which the fixed charges are expressed in the form of concave functions. With the use of the developed convex envelope results, we show that the convex envelope relaxations of the nonconvex formulations lead to the linear programming relaxations of the strong IP/MIP formulations of these problems. Moreover, our technique for deriving convex envelopes offers a useful construct that could be exploited in other related contexts as well. © 1996 John Wiley & Sons, Inc.

Suggested Citation

  • Meltem Denizel & S. Selcuk Erenguc & Hanif D. Sherali, 1996. "Convex envelope results and strong formulations for a class of mixed‐integer programs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 43(4), pages 503-518, June.
    • Handle: RePEc:wly:navres:v:43:y:1996:i:4:p:503-518
    DOI: 10.1002/(SICI)1520-6750(199606)43:43.0.CO;2-B
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/(SICI)1520-6750(199606)43:43.0.CO;2-B
    Download Restriction: no
    File URL: https://libkey.io/10.1002/(SICI)1520-6750(199606)43:43.0.CO;2-B?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. Kathryn E. Stecke, 1983. "Formulation and Solution of Nonlinear Integer Production Planning Problems for Flexible Manufacturing Systems," Management Science, INFORMS, vol. 29(3), pages 273-288, March.
    2. S. Selcuk Erenguc & Harold P. Benson, 1986. "The interactive fixed charge linear programming problem," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 33(2), pages 157-177, May.
    3. Panagiotis Kouvelis & Hau L. Lee, 1991. "Block Angular Structures and the Loading Problem in Flexible Manufacturing Systems," Operations Research, INFORMS, vol. 39(4), pages 666-676, 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. Saravanan Venkatachalam & Arunachalam Narayanan, 2016. "Efficient formulation and heuristics for multi-item single source ordering problem with transportation cost," International Journal of Production Research, Taylor & Francis Journals, vol. 54(14), pages 4087-4103, July.

    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. Mohamed, Zubair M., 1996. "A flexible approach to (re)configure Flexible Manufacturing Cells," European Journal of Operational Research, Elsevier, vol. 95(3), pages 566-576, December.
    2. Atan, Tankut S. & Pandit, Ram, 1996. "Auxiliary tool allocation in flexible manufacturing systems," European Journal of Operational Research, Elsevier, vol. 89(3), pages 642-659, March.
    3. Mohamed, Zubair M., 1995. "Ramifications of tool magazine size on the makespan and routing flexibility of flexible manufacturing systems," European Journal of Operational Research, Elsevier, vol. 87(2), pages 289-298, December.
    4. Crama, Yves, 1997. "Combinatorial optimization models for production scheduling in automated manufacturing systems," European Journal of Operational Research, Elsevier, vol. 99(1), pages 136-153, May.
    5. Mohamed, Zubair M. & Bernardo, John J., 1997. "Tool planning models for flexible manufacturing systems," European Journal of Operational Research, Elsevier, vol. 103(3), pages 497-514, December.
    6. S. Selcuk Erenguc, 1988. "Multiproduct dynamic lot‐sizing model with coordinated replenishments," Naval Research Logistics (NRL), John Wiley & Sons, vol. 35(1), pages 1-22, February.
    7. Christopher S. Tang, 2017. "OM Forum—Three Simple Approaches for Young Scholars to Identify Relevant and Novel Research Topics in Operations Management," Manufacturing & Service Operations Management, INFORMS, vol. 19(3), pages 338-346, July.
    8. Mohamed, Zubair M. & Kumar, Ashok & Motwani, Jaideep, 1999. "An improved part grouping model for minimizing makespan in FMS," European Journal of Operational Research, Elsevier, vol. 116(1), pages 171-182, July.
    9. Nagraj Balakrishnan & Amiya K. Chakravarty, 2001. "Opportunistic retooling of a flexible machine subject to failure," Naval Research Logistics (NRL), John Wiley & Sons, vol. 48(1), pages 79-97, February.
    10. Mark S. Hillier & Margaret L. Brandeau, 1998. "Optimal Component Assignment and Board Grouping in Printed Circuit Board Manufacturing," Operations Research, INFORMS, vol. 46(5), pages 675-689, October.
    11. Crama Yves & Klundert Joris van de, 1996. "The approximability of tool management problems," Research Memorandum 019, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    12. Bennett, Derek P. & Yano, Candace A., 2004. "A decomposition approach for an equipment selection and multiple product routing problem incorporating environmental factors," European Journal of Operational Research, Elsevier, vol. 156(3), pages 643-664, August.
    13. Reiner Horst, 1990. "Deterministic methods in constrained global optimization: Some recent advances and new fields of application," Naval Research Logistics (NRL), John Wiley & Sons, vol. 37(4), pages 433-471, August.
    14. Matzliach, Barouch & Tzur, Michal, 2000. "Storage management of items in two levels of availability," European Journal of Operational Research, Elsevier, vol. 121(2), pages 363-379, March.
    15. Potts, C. N. & Whitehead, J. D., 2001. "Workload balancing and loop layout in the design of a flexible manufacturing system," European Journal of Operational Research, Elsevier, vol. 129(2), pages 326-336, March.
    16. M. Selim Akturk & Jay B. Ghosh & Evrim D. Gunes, 2003. "Scheduling with tool changes to minimize total completion time: A study of heuristics and their performance," Naval Research Logistics (NRL), John Wiley & Sons, vol. 50(1), pages 15-30, February.
    17. Wilbert E. Wilhelm & Radu Gadidov, 2004. "A Branch-and-Cut Approach for a Generic Multiple-Product, Assembly-System Design Problem," INFORMS Journal on Computing, INFORMS, vol. 16(1), pages 39-55, February.
    18. Das, Sanchoy K. & Nagendra, Prashanth, 1997. "Selection of routes in a flexible manufacturing facility," International Journal of Production Economics, Elsevier, vol. 48(3), pages 237-247, February.
    19. Soares, Leonardo Cabral R. & Carvalho, Marco Antonio M., 2020. "Biased random-key genetic algorithm for scheduling identical parallel machines with tooling constraints," European Journal of Operational Research, Elsevier, vol. 285(3), pages 955-964.
    20. Harold P. Benson & S. Selcuk Erenguc, 1990. "An algorithm for concave integer minimization over a polyhedron," Naval Research Logistics (NRL), John Wiley & Sons, vol. 37(4), pages 515-525, August.

    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:43:y:1996:i:4:p:503-518. 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.