A cutting plane method for solving linear generalized disjunctive programming problems

Raman and Grossmann [Raman, R., & Grossmann, I.E. (1994). Modeling and computational techniques for logic based integer programming. Computers and Chemical Engineering, 18(7), 563-578] and Lee and Grossmann [Lee, S., & Grossmann, I.E. (2000). New algorithms for nonlinear generalized disjunctive programming. Computers and Chemical Engineering, 24, 2125-2141] have developed a reformulation of Generalized Disjunctive Programming (GDP) problems that is based on determining the convex hull of each disjunction. Although the relaxation of the reformulated problem using this method will often produce a significantly tighter lower bound when compared with the traditional big-M reformulation, the limitation of this method is that the representation of the convex hull of every disjunction requires the introduction of new disaggregated variables and additional constraints that can greatly increase the size of the problem. In order to circumvent this issue, a cutting plane method that can be applied to linear GDP problems is proposed in this paper. The method relies on converting the GDP problem into an equivalent big-M reformulation that is successively strengthened by cuts generated from an LP or QP separation problem. The sequence of problems is repeatedly solved, either until the optimal integer solution is found, or else until there is no improvement within a specified tolerance, in which case one switches to a branch and bound method. The strip-packing, retrofit planning and zero-wait job-shop scheduling problems are presented as examples to illustrate the performance of the proposed cutting plane method. (c) 2005 Elsevier Ltd. All rights reserved.