We present a novel approach aimed at enhancing the efficacy of solving both regular and distributionally robust chance constrained programs using an empirical reference distribution. In general, these programs can be reformulated as mixed-integer programs (MIPs) by introducing binary variables for each scenario, indicating whether a scenario should be satisfied. While existing methods have predominantly focused on either inner or outer approximations, this paper bridges this gap by studying a scheme that effectively combines these approximations via variable fixing. Through probing the restricted outer approximations and comparing them with the inner approximations, we derive optimality cuts that can notably reduce the number of binary variables by effectively setting them to either one or zero. We conduct a theoretical analysis of variable fixing techniques, deriving an asymptotic closed-form expression. This expression quantifies the proportion of binary variables that should be optimally fixed to zero. Our empirical results showcase the advantages of our approach, both in terms of computational efficiency and solution quality. Notably, we solve all the tested instances from literature to optimality, signifying the robustness and effectiveness of our proposed approach.
Citation
Jiang, N., Xie, W. (2023) The Terminator: An Integration of Inner and Outer Approximations for Solving Regular and Distributionally Robust Chance Constrained Programs via Variable Fixing. Available at Optimization Online.