zbMATH — the first resource for mathematics

Generalized convex disjunctive programming: Nonlinear convex hull relaxation. (English) Zbl 1030.90069
Summary: Generalized Disjunctive Programming (GDP) has been introduced recently as an alternative to mixed-integer programming for representing discrete/continuous optimization problems. The basic idea of GDP consists of representing these problems in terms of sets of disjunctions in the continuous space, and logic propositions in terms of Boolean variables. In this paper we consider GDP problems involving convex nonlinear inequalities in the disjunctions. Based on the work by R. Stubbs and S. Mehrotra [Math. Program. 86A, 515-532 (1999; Zbl 0946.90054)] and S. Ceria and J. Soares [Math. Program 86A, 595-614 (1999; Zbl 0954.90049)], we propose a convex nonlinear relaxation of the nonlinear convex GDP problem that relies on the convex hull of each of the disjunctions that is obtained by variable disaggregation and reformulation of the inequalities. The proposed nonlinear relaxation is used to formulate the GDP problem as a mixed-integer nonlinear programming problem that is shown to be tighter than the conventional “big-M” formulation. A disjunctive branch and bound method is also presented, and numerical results are given for a set of test problems.

90C11 Mixed integer programming
90C25 Convex programming
90C30 Nonlinear programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Full Text: DOI