A hierarchy of relaxations for nonlinear convex generalized disjunctive programming

Juan P. Ruiz, Ignacio E. GrossmannEur. J. Oper. Res 2012 · DOI · OpenReview

Abstract

We propose a framework to generate alternative mixed-integer nonlinear programming formulations for disjunctive convex programs that lead to stronger relaxations. We extend the concept of “basic steps” defined for disjunctive linear programs to the nonlinear case. A basic step is an operation that takes a disjunctive set to another with fewer number of conjuncts. We show that the strength of the relaxations increases as the number of conjuncts decreases, leading to a hierarchy of relaxations. We prove that the tightest of these relaxations, allows in theory the solution of the disjunctive convex program as a nonlinear programming problem. We present a methodology to guide the generation of strong relaxations without incurring an exponential increase of the size of the reformulated mixed-integer program. Finally, we apply the theory developed to improve the computational efficiency of solution methods for nonlinear convex generalized disjunctive programs (GDP). This methodology is validated through a set of numerical examples.
BibTeX
@article{ruiz2012hierarchy,
  author = {Juan P. Ruiz and Ignacio E. Grossmann},
  title = {{A hierarchy of relaxations for nonlinear convex generalized disjunctive programming}},
  journal = {Eur. J. Oper. Res.},
  year = {2012},
  doi = {10.1016/j.ejor.2011.10.002},
}

Loading related content...

Figure