(568a) Lagrangean Disjunctive Branch and Bound for Linear Generalized Disjunctive Programs

Authors: 
Trespalacios, F. - Presenter, Carnegie Mellon University
Grossmann, I. E. - Presenter, Carnegie Mellon University

Many optimization problems are represented with algebraic equations, using continuous and discrete variables, giving rise to Mixed-Integer (Linear or Nonlinear) Programs (MILP/ MINLP). An alternative way to represent this type of problems is Generalized Disjunctive Programming (GDP) proposed by Raman and Grossmann [1]  that involves not only algebraic equations, but also disjunctions and logic propositions. This higher level representation, which is of special importance in engineering, allows us to exploit the logic structure of the problem to obtain better formulations and improved solution methods.

GDP problems are normally reformulated as MILP/MINLP models to exploit the developments of these types of solvers. Big M (BM) and Hull Reformulation (HR) are the two traditional GDP to MILP/MINLP reformulations. The BM provides a formulation that is usually weaker than the HR (i.e. the continuous relaxation of the HR is at least as tight as that of the BM, and typically tighter). However, the BM reformulation yields an MILP/MINLP that is smaller in size than the HR. Alternatively to reformulation, specialized methods have been developed to solve generalized disjunctive programs: disjunctive branch and bound [2], and logic-based outer approximation [3].

The traditional disjunctive branch and bound requires the solution of the continuous relaxation of the MILP/MINLP reformulation of the GDP at every node, using either the BM or HR. The BM disjunctive branch and bound typically requires the evaluation of more nodes than the HR disjunctive branch and bound. However, the time required to evaluate each node is smaller in the BM disjunctive branch and bound. An important property of the disjunctive branch and bound is that the time required to evaluate each node decreases as the search tree progresses.

In this work we first present a novel Lagrangean relaxation scheme for the continuous relaxation of the HR. Normally, the Lagrangean relaxation technique requires the user to identify the “complicated constraints” in each problem. In the proposed Lagrangean decomposition, the complicating constraints are the same for any linear GDP. These complicating constraints are related to the (HR) reformulation.Therefore, the proposed decomposition is general and applicable to any linear GDP (i.e. also applicable to any MILP, since any MILP can be represented as a linear GDP). This Lagrangean relaxation has two important properties. The first one is that it is simpler to solve than the HR, as it is usually expected from the Lagrangean relaxation of a problem. The second one, and perhaps the most relevant, is that its solution (a continuous LP) always assigns 0-1 values to the binary variables. It is important to note that a solution to the Lagrangean relaxation does not necessarily satisfy all of the constraints of the HR.

We present a solution method that exploits the proposed Lagrangean relaxation of the HR (which is general to any linear GDP, is “easy to solve”, and its solution always provides 0-1 values to binary variables). This solution method is a disjunctive branch and bound for linear GDPs that makes use of the Lagrangean relaxation.

The proposed method solves three LPs at each node: the continuous relaxation of the BM, the proposed Lagrangean relaxation of the HR, and an LP in which all of the discrete variables are fixed. The continuous relaxation of the BM serves the same purpose as in the traditional disjunctive branch and bound: if it is infeasible or integer feasible the node is pruned; if the relaxation is worse than a known feasible solution then it is pruned; otherwise, one branches on that node. The proposed Lagrangean relaxation has two purposes. The first one is to provide a stronger lower bound than the BM relaxation, which will occur in some nodes. The second one is to provide a value for the binary variables. The discrete decisions are then fixed at this value, and a corresponding LP is evaluated (e.g. the third LP evaluation at each node). Note that the Lagrangean relaxation requires the use of Lagrangean multipliers. These are calculated at the root node by solving the continuous relaxation of the HR, and can be updated later in the search tree. From a general point of view, the Lagrangean relaxation is used as a heuristic to find feasible solutions at every node. Considering that it only requires the solution of two “simple” LPs, and that the Lagrangean relaxation is a good approximation of the linear GDP, the method is very efficient.

We illustrate the application of this algorithm with several linear GDP problems, including strip packing problems and randomly generated instances. The results show that the proposed method performs much better than the traditional disjunctive branch and bound (either BM or HR). The method requires fewer nodes to find feasible solutions and the optimal solution. Furthermore, in most cases the search tree requires the evaluation of considerably fewer nodes. Compared to the HR disjunctive branch and bound, the method also requires less time per node.

 

References:

[1] Raman, Ramesh, and Ignacio E. Grossmann. "Modelling and computational techniques for logic based integer programming", Computers & Chemical Engineering. 1994; 18(7), 563-578.

[2] Beaumont, Nicholas. "An algorithm for disjunctive programs", European Journal of Operational Research.1990; 48(3), 362-371.

[3] Türkay, Metin, and Ignacio E. Grossmann. "Logic-based MINLP algorithms for the optimal synthesis of process networks", Computers & Chemical Engineering. 1996; 20(8), 959-978.