CONVEX ENVELOPE RESULTS AND STRONG FORMULATIONS FOR A CLASS OF MIXED-INTEGER PROGRAMS

In this article we present a novel technique for deriving the convex e nvelope of certain nonconvex fixed-charge functions of the type that a rise in several related applications that have been considered in the literature. One common attribute of these problems is that they involv e choosing levels for the undertaking of several activities. Two or mo re activities share a common resource, and a fixed charge is incurred when any of these activities is undertaken at a positive level. We con sider nonconvex programming formulations for these problems in which t he fixed charges are expressed in the form of concave functions. With the use of the developed convex envelope results, we show that the con vex envelope relaxations of the nonconvex formulations lead to the lin ear programming relaxations of the strong IP/MIP formulations of these problems. Moreover, our technique for deriving convex envelopes offer s a useful construct that could be exploited in other related contexts as well. (C) 1996 John Wiley & Sons, Inc.