Generalized disjunctive programming: Solution strategies

Abstract

Generalized disjunctive programming (GDP) is an extension of the disjunctive programming paradigm developed by Balas. The GDP formulation involves Boolean and continuous variables that are specified in algebraic constraints, disjunctions and logic propositions, which is an alternative representation to the traditional algebraic mixed-integer programming formulation. GDP has proven to be very useful in representing a wide variety of problems successfully. Even though a wealth of powerful algorithms exist to solve these problems, GDP suffers a lack of mature solver technology. The main goal of this paper is to review the basic concepts and algorithms related to GDP problems and describe how solver technology is being developed. With this in mind after providing a brief review of MINLP optimization, we present an overview of GDP for the case of convex functions emphasizing the quality of continuous relaxations of alternative reformulations that include the big-M and the hull relaxation. We then review disjunctive branch and bound as well as logic-based decomposition methods that circumvent some of the limitations in traditional MINLP optimization. The first implemented GDP solver LogMIP successfully demonstrated that formulating and solving such problems can be done in an algebraic modeling system like GAMS. Recently, LogMIP has been introduced into GAMS’ Extended Mathematical Programming (EMP) framework integrating it much closer into the GAMS system and language and at the same time offering much more flexibility to the user. Since the model is separated from the reformulation chosen and from the solver used to solve the automatically generated model, this setup allows to easily switch methods at no costs and to benefit from advancing solver technology.