How do discrete optimization models (MST, Steiner Tree, Max-Flow/Min-Cut, MILP) scale in cost, coverage, and runtime for rural electrification networks of different sizes?

This study evaluates four discrete optimization models—Minimum Spanning Tree (MST), Steiner Tree, Max-Flow/Min-Cut (MFMC), and Mixed-Integer Linear Programming (MILP)—for planning rural electrification networks in African contexts. By simulating small (50-node) and large (1,000-node) village networks, the research analyzes each model’s scalability in terms of runtime, total cost, coverage, and computational resource requirements. MST provides fast, full-coverage baseline solutions, Steiner Tree reduces total wiring cost through auxiliary nodes, MFMC emphasizes flow capacity and bottleneck identification, and MILP balances cost and coverage under multi-objective constraints. The study highlights the trade-offs between efficiency, coverage, and computational feasibility, offering practical guidance for selecting appropriate optimization strategies in low-resource and large-scale rural electrification projects. This study investigates the performance, scalability, and practicality of four network design models—Minimum Spanning Tree (MST), Steiner Tree, Max-Flow/Min-Cut (MFMC), and Mixed-Integer Linear Programming (MILP)—for rural electrification planning in an African context. Using simulated village networks of varying sizes, the work evaluates each model based on computational efficiency, total connection cost, coverage, and robustness. Results show that MST consistently delivers low-cost, fully connected solutions at exceptional speeds, making it suitable for large-scale deployments. The Steiner Tree model achieves marginally lower costs but at the expense of significant computational overhead and instability for large networks. MFMC performs well for flow-related constraints but struggles to provide complete network structures. MILP offers globally optimal solutions on large instances but becomes computationally intractable as network size decreases. Overall, the findings highlight the trade-offs between optimality and scalability, providing a framework to guide infrastructure planners in selecting appropriate algorithms for electrification projects across developing regions.