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

Meltem Denizel, S. Selcuk Erenguc and Hanif D. Sherali

Naval Research Logistics (NRL), 1996, vol. 43, issue 4, 503-518

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.

Date: 1996
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1002/(SICI)1520-6750(199606)43:43.0.CO;2-B

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:43:y:1996:i:4:p:503-518

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().