This paper was published through Galoá and has a deposited DOI. To cite this paper, use one of the standards below:
In case you are one of the co-authors and want to register this paper in your Lattes, use the following code: doi > 10.59254/sbpo-2026-232236
If you've NEVER registered a DOI in your Lattes, check our tutorial!We investigate the Budget-Constrained Minimum Bottleneck Spanning Tree problem with Node Upgrades (BC-MBST-NU), a network design challenge that optimizes infrastructure investment to improve worst-case performance. By upgrading nodes to reduce the weights of adjacent edges, we seek a spanning tree that minimizes the maximum edge weight under a strict budget. We propose the first exact approach for this NP-hard problem, presenting a novel mixed-integer linear programming formulation. Our solution strategy is enhanced by a tailored primal heuristic for warm-starting the solver and a structural variable-fixing procedure that leverages the bottleneck objective to prune the search space effectively. Computational results on various instance scales show that the proposed methodology is robust, providing optimal solutions for small and medium instances and good-quality feasible solutions for large-scale networks within practical time limits.
With nearly 200,000 papers published, Galoá empowers scholars to share and discover cutting-edge research through our streamlined and accessible academic publishing platform.
Learn more about our products:
This proceedings is identified by a DOI , for use in citations or bibliographic references. Attention: this is not a DOI for the paper and as such cannot be used in Lattes to identify a particular work.
Check the link "How to cite" in the paper's page, to see how to properly cite the paper