Bulk-robust optimization is a recent paradigm for addressing problems in which the structure of a system is affected by uncertainty. It considers the case in which a finite and discrete set of possible failure scenarios is known in advance, and the decision maker aims to activate a subset of available resources of minimum cost so that a certain property is satisfied, regardless of which scenario occurs. Although theoretical properties of this paradigm have been studied and approximation algorithms have been proposed in the literature, we are not aware of any computational approach. Therefore, we devise a unified exact solution method, based on Benders’ decomposition, and apply it to two core problems belonging to this class, the bulk-robust assignment problem and the bulk-robust connectivity problem. In our approach, the master problem determines which resources to activate, while the subproblems verify the feasibility of the master solution in each scenario. We propose combinatorial algorithms for the subproblems that significantly speed up their solution. Our extensive computational results confirm the effectiveness of our approach and the importance of the computational enhancements we propose.