file.pdf (743.94 kB)

Cutting planes algorithm for convex Generalized Disjunctive Programs

Download (743.94 kB)
journal contribution
posted on 01.01.2014, 00:00 by Francisco Trespalacios, Ignacio E. Grossmann

In this work, we propose a cutting plane algorithm to improve optimization models that are originally formulated as convex Generalized Disjunctive Programs (GDP). GDPs are traditionally reformulated as MINLPs using either the Big-M (BM) or the hull-reformulation (HR). The former yields a smaller MILP/MINLP while the later a tighter one. The (HR) reformulation 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 GDP convex models, in the sense of providing formulations with stronger continuous relaxations than the (BM) with few additional constraints. In general, the algorithm also leads to a reduction in the solution time of the problems.