Cutting Plane Algorithm for Convex Generalized Disjunctive Programs

In this work, we propose a cutting plane algorithm to improve optimization models that are originally formulated as convex generalized disjunctive programs. Generalized disjunctive programs are traditionally reformulated as mixed-integer nonlinear programming (MINLP) problems using either the big M (BM) or the hull reformulation (HR). The former yields a smaller MILP/MINLP problem, whereas the latter yields a tighter one. The HR can be further strengthened by using the concept of basic step from disjunctive programming. The proposed algorithm uses the strengthened formulation to derive cuts for the big-M formulation, generating a stronger formulation with small growth in problem size. We test the algorithm with several instances. The results show that the algorithm improves generalized disjunctive programming convex models, in the sense of providing formulations with stronger continuous relaxations than the BM formulation, with few additional constraints. In general, the algorithm also leads to a reduction in the solution time of the problems.