An Exact Algorithm for Linear Optimization over the Efficient Set of a Multi-Objective Stochastic Set-Covering Problem

Abstract

This paper presents an exact solution framework for optimizing a linear function over the set of efficient solutions of a stochastic multi-objective set-covering problem. Using a chance-constrained programming approach, the stochastic model is first transformed into an exact deterministic equivalent under the assumption of normally distributed random parameters. To address the computational challenges associated with the resulting nonlinear convex constraints, a robust conic reformulation is developed, yielding a Mixed-Integer Second-Order Cone Programming (MISOCP) model. An exact decomposition-based algorithm is then proposed, integrating a specialized efficiency test with dominance-based cuts to efficiently prune the search space without requiring complete enumeration of the Pareto frontier. Extensive computational experiments on benchmark instances demonstrate the effectiveness, robustness, and scalability of the proposed framework. The results show that the method consistently computes exact optimal solutions within competitive computational times, highlighting its practical applicability to large-scale stochastic set-covering problems.