Learning to optimize (L2O) has recently emerged as a promising approach to
solving optimization problems by exploiting the strong prediction power of
neural networks and offering lower runtime complexity than conventional
solvers. While L2O has been applied to various problems, a crucial yet
challenging class of problems -- robust combinatorial optimization in the form
of minimax optimization -- have largely remained under-explored. In addition to
the exponentially large decision space, a key challenge for robust
combinatorial optimization lies in the inner optimization problem, which is
typically non-convex and entangled with outer optimization. In this paper, we
study robust combinatorial optimization and propose a novel learning-based
optimizer, called LRCO (Learning for Robust Combinatorial Optimization), which
quickly outputs a robust solution in the presence of uncertain context. LRCO
leverages a pair of learning-based optimizers -- one for the minimizer and the
other for the maximizer -- that use their respective objective functions as
losses and can be trained without the need of labels for training problem
instances. To evaluate the performance of LRCO, we perform simulations for the
task offloading problem in vehicular edge computing. Our results highlight that
LRCO can greatly reduce the worst-case cost and improve robustness, while
having a very low runtime complexity.

该论文研究了利用神经网络在 robust combinatorial optimization 中解决 minimax optimization 问题的新方法 Learning for Robust Combinatorial Optimization (LRCO)，并通过在车载边缘计算中解决任务分配问题进行模拟，证明了 LRCO 能够大大减少最坏情况的成本和提高鲁棒性，同时具有非常低的运行时复杂度。