(61a) A Theoretical and Computational Comparison between Gdp Cuts, Disjunctive Cuts and Lift-and Project Cuts for Linear Generalized Disjunctive Programming

In this presentation, we report some exciting insights and connections between Disjunctive Programming as originally proposed by Egon Balas, and Generalized Disjunctive Programming, emphasizing fundamental understanding of their corresponding cutting planes, specifically the connections that exist between GDP cuts and disjunctive and lift and project cuts.

Disjunctive Programming was originally developed in the mid-seventies by Egon Balas in his often-cited research report ?Disjunctive Programming: Properties of the convex hull of feasible points? [1], that only recently was published as an invited paper in 1998 [2]. See also [3], [4]. Since establishing the foundations of the field in that seminal work, the methods of disjunctive programming have been successfully applied to mixed-integer linear programming through the generation of strong cutting planes representing facets of the convex hull of disjunction(s), otherwise known as disjunctive cuts in the general case, or lift-and-project cuts in the two-term 0-1 case [5], [6], [7], [8].

Raman and Grossmann [9] extended Balas' disjunctive framework and developed Generalized Disjunctive Programming, which has been proposed as an alternative to the algebraic MILP model for representing discrete/continuous optimization problems. The GDP model allows a combination of algebraic and logical equations through disjunctions and logic propositions, which facilitates the representation of discrete decisions. Grossmann and Lee [10] further extended that work and developed a general method for solving GDP problems for the linear and nonlinear cases that is based on determining the convex hull of each disjunction. While the relaxation of this method will often produce a significantly tighter lower bound when compared with the traditional big-M reformulation, the limitation of this method is that the representation of the convex hull for each disjunction requires the introduction of new disaggregated variables and additional constraints that can greatly increase the size of the problem. In order to circumvent the issue of large problem size, Sawaya and Grossmann [11] proposed a cutting plane method that can be applied to linear GDP problems and that relies on converting the GDP problem into an equivalent big-M reformulation that is successively strengthened by cuts generated from a separation problem whose feasible region corresponds to that of the relaxed formulation given by Lee and Grossmann. They call the resulting cutting planes thus produced through this method ?GDP cuts?.

In this work, we compare, both theoretically and computationally, the intimate connection that exists between GDP cuts and disjunctive cuts developed by Balas for the general case, and their counter-parts in the special two-term 0-1 case (lift-and-project cuts). We present a unified framework for this development through the use of Balas' concept of reverse polar, and present examples that demonstrate the efficiency of both methods for different cases.

[1] Balas E., "Disjunctive Programming: Properties of the convex hull of feasible points", MSRR No.330, Carnegie Mellon University (Pittsburgh PA, 1974).

[2] Balas E., "Disjunctive Programming: Properties of the convex hull of feasible points", Discrete Applied Mathematics 89 (1998) 3-44. [3] Balas E., ?Disjunctive Programming?, Annals of Discrete Mathematics, 5, 1979, 3-51.

[4] Balas E., ?Disjunctive programming and a hierarchy of relaxations for discrete optimization problems?, SIAM Journal on Algebraic and Discrete Methods, 6, 1985, 466-485.

[5] Balas E., Ceria S., Cornuéjols G., ?A lift & project cutting plane algorithm for mixed 0-1 programs?, Mathematical Programming, 58 (1993) 295-324

[6] Balas E., Ceria S., Cornuéjols G., ?Mixed 0-1 programming by lift-and-project in a branch and cut framework?, Management Science, Vol. 42, September 1996.

[7] Balas E., Perregaard M., ?Lift and project for mixed 0-1 programming: recent progress?, Discrete Applied Mathematics, 123 129-154 (2002).

[8] Balas E., Perregaard M., ?A Precise Correspondence Between Lift-and-Project Cuts, Simple Disjunctive Cuts, and Mixed Integer Gomory Cuts for 0-1 Programming?, Mathematical Programming B, 94, 2003, 221-245.

[9] Raman R., Grossmann I.E., ?Modeling and computational techniques for logic based integer programming?, Computers and Chemical Engineering, 18(7), 563-578, 1994.

[10] Grossmann I.E., Lee S., ?Generalized Convex Disjunctive Programming: Nonlinear Convex Hull Relaxation?, Computational Optimization & Applications, 26, 83-100, 2003.

[11] Sawaya N.W., Grossmann I.E., ?A Cutting Plane Method for Solving Linear Generalized Disjunctive Programming Problems?, Computers and Chemical Engineering, 29(2005), 1891-1913.