(517f) Generalized Disjunctive Programming: A Trip Down Memory Lane from Development, Extensions, and Future Perspectives

In this talk, we will go through the history of Generalized Disjunctive Programming. Linear optimization over linear constraints and disjunct polytopes had already attracted the interest of Prof. Egon Balas at the end of the 1970s [1] in a field that was coined as disjunctive programming (DP). This framework was mainly used to derive valuable linear inequalities (cutting planes) in disjunctions that naturally appear when modeling with binary variables in mixed-integer linear programming (MILP). These cutting planes have been crucial for the noticeable advancement of MILP solvers in the last decades.

In the early 1990s, Prof. Ignacio Grossmann realized the potential of such a framework beyond the derivation of cuts: it could be a tool for modeling discrete choices such as those appearing in process synthesis or stages unit operation design[2,3]. To that end, disjunctive programming required a generalization, which gave birth to generalized disjunctive programming (GDP).

GDP extended DP in various directions, such as the natural inclusion of nonlinear constraints required for modeling physicochemical processes, and logic restrictions, necessary to incorporate higher-level logical implications found in practical applications. More importantly, the understanding of such natural structure in decision-making problems resulted in the development of solution methods informed by what the modeler had in mind when writing a mathematical program representing their problem.

This tool has motivated a series of publications, ranging from the modeling capabilities from and beyond Process Systems Engineering to the algorithmic development to ensure the validity of reformulations in linear[4], convex[5,6], and nonconvex[7] cases. The talk will also include software development solutions [8,9,10] that allow users to communicate the natural formulation of GDP to solvers capable of addressing these problems practically.

This innovation path has continued through various advisees of Prof. Ignacio Grossmann[11], and we will attempt to give a chronological reminiscing of these developments, which are still ongoing. Moreover, we will highlight how many of these developments have been recently rediscovered in other fields [12], given the focus that GDP has had in the Process Systems Engineering academic literature.

For such contributions, we (including the speaker) feel honored to have continued Prof. Grossmann’s vision of aiding decision-making, both on the modeling and solution methods, from the structured approach of generalized disjunctive programming.

References

1. Balas, Disjunctive programming, Annals of discrete mathematics 5 (1979) 3–51
2. Raman, I. E. Grossmann, Modelling and computational techniques for logic-based integer programming, Computers & Chemical Engineering 18 (7) (1994) 563–578
3. T ̈urkay, I. E. Grossmann, Disjunctive programming techniques for the optimization of process systems with discontinuous investment costs-multiple size regions, Industrial & engineering chemistry research 35 (8) (1996) 2611–2623
4. Sawaya, I. Grossmann, A hierarchy of relaxations for linear generalized disjunctive programming, European Journal of Operational Research 216 (1) (2012) 70–82
5. P. Ruiz, I. E. Grossmann, A hierarchy of relaxations for nonlinear convex generalized disjunctive programming, European Journal of Operational Research 218 (1) (2012) 38–47
6. E. Bernal Neira, I. E. Grossmann, Convex mixed-integer nonlinear programs derived from generalized disjunctive programming using cones, Computational Optimization and Applications (2024) 1–62
7. P. Ruiz, I. E. Grossmann, Using convex nonlinear relaxations in the global optimization of nonconvex generalized disjunctive programs, Computers & Chemical Engineering 49 (2013) 70–84
8. Vecchietti, I. E. Grossmann, Modeling issues and implementation of language for disjunctive programming, Computers & Chemical Engineering 24 (9-10) (2000) 2143–2155
9. Chen, E. S. Johnson, D. E. Bernal, R. Valentin, S. Kale, J. Bates, J. D. Siirola, I. E. Grossmann, Pyomo. GDP: an ecosystem for logic-based modeling and optimization development, Optimization and Engineering 23 (1) (2022) 607–642
10. D. Perez, S. Joshi, I. E. Grossmann, DisjunctiveProgramming.jl: Generalized Disjunctive Programming Models and Algorithms for JuMP, arXiv preprint arXiv:2304.10492 (2023)
11. E. Grossmann, F. Trespalacios, Systematic modeling of discrete-continuous optimization models through generalized disjunctive programming, AIChE Journal 59 (9) (2013) 3276–3295
12. Bertsimas, R. Cory-Wright, J. Pauphilet, A unified approach to mixed-integer optimization problems with logical constraints, SIAM Journal on Optimization 31 (3) (2021) 2340–2367