Approximate Kernel Learning Uncertainty Set for Robust Combinatorial Optimization
针对支持向量聚类构建的不确定集导致计算复杂的问题，提出一种两阶段近似方法，在近似质量与模型复杂度间取得平衡，实验表明该方法显著降低计算时间且解质量相当。
Support vector clustering (SVC) has been proposed in the literature as a data-driven approach to build uncertainty sets in robust optimization. Unfortunately, the resulting SVC-based uncertainty sets induces a large number of additional variables and constraints in the robust counterpart of mathematical formulations. We propose a two-phase method to approximate the resulting uncertainty sets and overcome these tractability issues. This method is controlled by a parameter defining a trade-off between the quality of the approximation and the complexity of the robust models formulated. We evaluate the approximation method on three distinct, well-known optimization problems. Experimental results show that the approximated uncertainty set leads to solutions that are comparable to those obtained with the classic SVC-based uncertainty set with a significant reduction of the computation time. History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms—Discrete. Funding: This work was supported by the German-French Academy for the Industry of the Future [Data-driven collaboration in Industrial Supply Chains project].