Learning for Robust Combinatorial Optimization: Algorithm and Application
This addresses robust optimization for uncertain contexts in domains like vehicular edge computing, but it is incremental as it applies learning-based methods to a specific, under-explored problem class.
The paper tackles robust combinatorial optimization, a challenging minimax problem, by proposing LRCO, a learning-based optimizer that uses neural networks for both minimizer and maximizer, and demonstrates in simulations for vehicular edge computing that it greatly reduces worst-case cost and improves robustness with low runtime complexity.
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.