Accelerated robust spatial Branch-and-Bound algorithm via multi-parametric programming: Application to pooling problems

The aim of this study is to employ a multi-parametric solution approach to address the pooling problem under robust uncertainty. A hybrid algorithm is proposed, integrating principles of multi-parametric programming, global and robust optimization. While in the robust cutting plane algorithm, the lower-level maximization problem is solved within each cutting plane iteration; this work investigates an alternative formulation using multi-parametric programming techniques. The lower-level problem is formulated as a multi-parametric problem with respect to the upper-level problem decision variables. The solution of the multi-parametric problem is precomputed offline via state-of-the-art multi-parametric software. The obtained critical regions are employed to perform function evaluation, replacing time-consuming iterative lower-level solves. A spatial Branch-and-Bound algorithm is presented, augmented by a multi-parametric robust cutting plane search, performing a parallel optimality and robustness search. The performance of the proposed methodology is tested on benchmark pooling problems considering uncertainty in the quality of the inlet feed. Results suggest that adopting a multi-parametric approach for the lower-level maximization problem under linear uncertainty sets offers computational savings compared to standard robust cutting plane approaches and a more efficient uncertainty sampling mechanism.