MIXED-INTEGER BILINEAR-PROGRAMMING PROBLEMS

This paper addresses a class of problems called mixed-integer bilinear programming problems. These problems are identical to the well known bilinear programming problems with the exception that one set of varia bles is restricted to be binary valued, and they arise in various prod uction, location-allocation, and distribution application contexts. We first identify some special cases of this problem which are relativel y more readily solvable, even though their continuous relaxations are still nonconvex. For the more general case, we employ a linearization technique and design a composite Lagrangian relaxation-implicit enumer ation-cutting plane algorithm. Extensive computational experience is p rovided to test the efficacy of various algorithmic strategies and the effects of problem data on the computational effort of the proposed a lgorithm.