Lagrangean relaxation of the hull-reformulation of linear generalized disjunctive programs and its use in disjunctive branch and bound

• A Lagrangean relaxation of the hull-reformulation of linear GDPs is presented.
• The proposed Lagrangean relaxation always yields 0–1 values to the binary variables.
• The proposed Lagrangean relaxation can be solved by solving many small LPs in parallel.
• The Lagrangean relaxation is incorporated into a disjunctive branch and bound as primal heuristic.
• Computational results show that the proposed modified disjunctive branch and bound performs better than other alternatives of the algorithm.

In this work, we present a Lagrangean relaxation of the hull-reformulation of discrete-continuous optimization problems formulated as linear generalized disjunctive programs (GDP). The proposed Lagrangean relaxation has three important properties. The first property is that it can be applied to any linear GDP. The second property is that the solution to its continuous relaxation always yields 0–1 values for the binary variables of the hull-reformulation. Finally, it is simpler to solve than the continuous relaxation of the hull-reformulation. The proposed Lagrangean relaxation can be used in different GDP solution methods. In this work, we explore its use as primal heuristic to find feasible solutions in a disjunctive branch and bound algorithm. The modified disjunctive branch and bound is tested with several instances with up to 300 variables. The results show that the proposed disjunctive branch and bound performs faster than other versions of the algorithm that do not include this primal heuristic.