Improved Big-M reformulation for generalized disjunctive programs

摘要

In this work, we present a new Big-M reformulation for Generalized Disjunctive Programs. Unlike the traditional Big-M reformulation that uses one M-parameter for each constraint, the new approach uses multiple M-parameters for each constraint. Each of these M-parameters is associated with each alternative in the disjunction to which the constraint belongs. In this way, the proposed MINLP reformulation is at least as tight as the traditional Big-M, and it does not require additional variables or constraints. We present the new Big-M, and analyze the strength in its continuous relaxation compared to that of the traditional Big-M. The new formulation is tested by solving several instances with an NLP-based branch and bound method. The results show that, in most cases, the new reformulation requires fewer nodes and less time to find the optimal solution.