Algoritmo branch and bound para o planejamento da expansão de redes de transmissão usando modelos de programação não linear inteira mista não convexos - Zoppei, Reinaldo Takara [UNESP] (Universidade Estadual Paulista (Unesp), 2023)
O algoritmo branch and bound (BB) é amplamente utilizado para obter a solução global de problemas de programação linear inteira mista (PLIM). Por outro lado, quando esse algoritmo tradicional é usado diretamente para resolver problemas não convexos de programação não linear inteira mista (PNLIM), ele se torna ineficaz, principalmente devido à não linearidade e não convexidade da região factível do problema. Este trabalho apresenta as dificuldades e ineficácia do uso direto do algoritmo BB tradicional para a resolução de problemas PNLIM não convexos e propõe a formulação de um algoritmo BB eficiente para resolver esta categoria de problemas. O algoritmo BB proposto é formulado levando em consideração aspectos particulares de problemas de PNLIM não convexos, incluindo (i) como lidar com os subproblemas de programação não linear (PNL), (ii) como detectar a infactibilidade de um subproblema de PNL, (iii) como tratar a não convexidade do problema, e (iv) como definir as regras de sondagem. O algoritmo BB proposto é usado para resolver o problema de planejamento da expansão de redes de transmissão (PERT), um problema clássico de otimização de sistemas de potência, e seu desempenho é comparado com o desempenho de solucionadores comerciais de otimização para problemas de PNLIM. Os resultados obtidos para sistemas-teste com diferentes graus de complexidade indicam que o algoritmo BB proposto é eficaz para resolver o problema de PERT considerando o modelo CC com e sem considerar perdas e, também, considerando o modelo CA, apresentando desempenho igual ou melhor que os solucionadores comerciais de otimização.

The branch and bound (BB) algorithm is widely used to obtain the global solution of mixed-integer linear programming (MILP) problems. On the other hand, when this traditional algorithm is directly used to solve nonconvex mixed-integer nonlinear programming (MINLP) problems, it becomes ineffective, mainly due to the nonlinearity and nonconvexity of the feasible region of the problem. This article presents the difficulties and ineffectiveness of the direct use of the traditional BB algorithm for solving nonconvex MINLP problems and proposes the formulation of an efficient BB algorithm for solving this category of problems. The proposed BB algorithm is formulated taking into account particular aspects of nonconvex MINLP problems, including (i) how to deal with the nonlinear programming (NLP) subproblems, (ii) how to detect the infeasibility of an NLP subproblem, (iii) how to treat the nonconvexity of the problem, and (iv) how to define the fathoming rules. The proposed BB algorithm is used to solve the transmission network expansion planning (TNEP) problem, a classical problem in power systems optimization, and its performance is compared with the performances of offthe-shelf optimization solvers for MINLP problems. The results obtained for test systems with different degrees of complexity indicate that the proposed BB algorithm is effective for solving the DC TNEP problem with and without considering losses and, also, considering the AC model, showing equal or better performance than off-the-shelf optimization solvers.
Branch and bound algorithm for planning the expansion of transmission networks using non-convex mixed integer non-linear programming models
Keywords: Algoritmo branch and bound; Otimização; Planejamento da expansão de redes de transmissão; Problemas de otimização não convexos; Programação não linear inteira mista; Branch and bound algorithm; Mixed-integer nonlinear programming; Nonconvex optimization problems; Optimization; Transmission network expansion planning