Enhanced Branch and Bound Algorithm: Minimizing Subproblem Complexity in Power Dispatch

Abstract

The Branch and Bound (BB) algorithm, while ensuring optimality, often encounters performance bottlenecks, characterized by slow execution and high computational overhead, especially when dealing with intricate or extensive problem instances (NP-Hard). This study introduces an innovative approach by dividing the problem into partial (local) problems in a manner that would not compromise optimality and solving sub-problems of each local problem individually, to shrink the solution space. In the initial phase, this research establishes and validates the mathematical foundation of the proposed algorithm, which involves a pruning approach. Subsequently, enhancements are incorporated into the existing BB to partition the solution space into more manageable sub-spaces and consolidate solutions from these sub-spaces. In the final phase, the Enhanced Branch and Bound (EBB) algorithm is applied to a real-world power dispatching optimization case study. The outcomes of this investigation reveal the following: 1) For smaller problem instances, both the conventional BB and the proposed EBB algorithm yield identical optimal solutions. 2) In contrast, the EBB algorithm demonstrates significantly improved performance in solving NP-hard problems that pose challenges for the BB and BB with pruning. The primary contribution of this research is the introduction of EBB, an enhanced version of BB, specifically designed to effectively tackle NP-hard problems. This approach can be integrated with all pruning, branching, and bounding strategies used in BB, thereby boosting its performance and making it applicable to all problems solved by BB variations.