Multiple Kernel Learning-Aided Column-and-Constraint Generation Method

Two-stage robust optimization (two-stage RO), due to its ability to balance robustness and flexibility, has been widely used in various fields for decision-making under uncertainty. This paper proposes a multiple kernel learning (MKL)-aided column-and-constraint generation (CCG) method to address this issue in the context of data-driven decision optimization, and releases a corresponding registered Julia package, MKLTwoStageRO.jl. The proposed method performs efficient multi-process parallel MKL on a large number of directional nullspace projection norm kernels in the uncertainty space, and with the help of one-class support vector machine, constructs a piecewise linear polyhedral intersection uncertainty set enjoying structural sparsity and computational tractability. The significant scenarios identified as boundary support vectors in the MKL phase are used to add valid initial cuts to the subsequent CCG procedure, so that the exact solution of the MKL uncertainty set-induced two-stage RO can be achieved with fewer iterations. Decision-makers are able to adjust the set construction efficiency, model complexity, and risk aversion degree through three hyperparameters in the proposed method. This method implies a connection with two-stage stochastic programming based on the value-at-risk measure, thus providing a quantitative evaluation of the solution quality. Numerical study on the data-driven two-stage robust location-transportation problem demonstrates the effectiveness and practicability of the proposed method and software package. The source code of MKLTwoStageRO.jl is available at https://github.com/hanb16/MKLTwoStageRO.jl.

Article

Download

View PDF