Hybrid seminar at GERAD and on Zoom.

Combinatorial Bayesian Optimization (CBO) has emerged as a powerful framework for optimizing expensive black-box functions over combinatorial search spaces. However, current approaches fail to scale to tackle the difficult, and often large-scale, instances that appear in classical OR problems. We focus on key OR problems and consider a setting where the objective function is nonlinear, stochastic and costly to compute. We assume that we have access to a cheap to compute approximation derived from a classical OR formulation (e.g., a MIP formulation), which we call the auxiliary function. We discuss various approaches to use information from the auxiliary function to enable existing CBO techniques to tackle OR problems with greater sample efficiency and higher scale. We further discuss a multi-fidelity kernel framework that fuses information from both sources within a Gaussian process surrogate. Beyond improving the surrogate fit, we further show that the auxiliary function can be leveraged to guide the optimization of the acquisition function over the combinatorial space, which is itself a challenging combinatorial problem.