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. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. Sodhi, Manbir S. & Lamond, Bernard F. & Gautier, Antoine & Noel, Martin, 2001. "Heuristics for determining economic processing rates in a flexible manufacturing system," European Journal of Operational Research, Elsevier, vol. 129(1), pages 105-115, February.
    13. Liu, Jiyin & MacCarthy, B. L., 1997. "A global MILP model for FMS scheduling," European Journal of Operational Research, Elsevier, vol. 100(3), pages 441-453, August.
    14. Benjaafar, Saifallah, 1996. "Modeling and analysis of machine sharing in manufacturing systems," European Journal of Operational Research, Elsevier, vol. 91(1), pages 56-73, May.
    15. Akturk, M. Selim & Avci, Selcuk, 1996. "Tool allocation and machining conditions optimization for CNC machines," European Journal of Operational Research, Elsevier, vol. 94(2), pages 335-348, October.
    16. Raduly-Baka, Csaba & Nevalainen, Olli S., 2015. "The modular tool switching problem," European Journal of Operational Research, Elsevier, vol. 242(1), pages 100-106.
    17. Renato de Matta & Vernon Ning Hsu & Timothy J. Lowe, 1999. "Capacitated selection problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(1), pages 19-37, February.
    18. S. Selcuk Erenguc & H. Murat Mercan, 1990. "A multifamily dynamic lot‐sizing model with coordinated replenishments," Naval Research Logistics (NRL), John Wiley & Sons, vol. 37(4), pages 539-558, August.
    19. Crama, Y. & van de Klundert, J., 1996. "The approximability of tool management problems," Research Memorandum 034, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    20. Gaalman, G. J. C. & Nawijn, W. M., 1996. "Tool sharing in parallel part production," International Journal of Production Economics, Elsevier, vol. 46(1), pages 521-533, December.

    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.