Mind Your Solver! On Adversarial Attack and Defense for Combinatorial Optimization

• URL: http://arxiv.org/abs/2201.00402v1
• Date: Tue, 28 Dec 2021 15:10:15 GMT
• Title: Mind Your Solver! On Adversarial Attack and Defense for Combinatorial Optimization
• Authors: Han Lu, Zenan Li, Runzhong Wang, Qibing Ren, Junchi Yan, Xiaokang Yang
• Abstract summary: We take an initiative on developing the mechanisms for adversarial attack and defense towards optimization solvers. We present a simple yet effective defense strategy to modify the graph structure to increase the robustness of solvers.
• Score: 111.78035414744045
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Combinatorial optimization (CO) is a long-standing challenging task not only in its inherent complexity (e.g. NP-hard) but also the possible sensitivity to input conditions. In this paper, we take an initiative on developing the mechanisms for adversarial attack and defense towards combinatorial optimization solvers, whereby the solver is treated as a black-box function and the original problem's underlying graph structure (which is often available and associated with the problem instance, e.g. DAG, TSP) is attacked under a given budget. In particular, we present a simple yet effective defense strategy to modify the graph structure to increase the robustness of solvers, which shows its universal effectiveness across tasks and solvers.

Related papers

• PARCO: Learning Parallel Autoregressive Policies for Efficient Multi-Agent Combinatorial Optimization [17.392822956504848]
  This paper introduces PARCO, a novel approach that learns fast surrogate solvers for multi-agent problems with reinforcement learning. We propose a model with a Multiple Pointer Mechanism to efficiently decode multiple decisions simultaneously by different agents, enhanced by a Priority-based Conflict Handling scheme.
  arXiv  Detail & Related papers  (2024-09-05T17:49:18Z)
• An Unsupervised Learning Framework Combined with Heuristics for the Maximum Minimal Cut Problem [5.092968949752308]
  This work proposes an unsupervised learning framework combined with Maximums for MMCP. A crucial observation is that each solution corresponds to at least one spanning tree. We conduct extensive experiments to evaluate our framework and give a specific application.
  arXiv  Detail & Related papers  (2024-08-16T02:07:34Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  An emerging strategy to tackle optimization problems involves the adoption of graph neural networks (GNNs) as an alternative to traditional algorithms. Despite the growing popularity of GNNs and traditional algorithm solvers in the realm of CO, there is limited research on their integrated use and the correlation between them within an end-to-end framework. We introduce a decision-focused framework that utilizes GNNs to address CO problems with auxiliary support.
  arXiv  Detail & Related papers  (2024-06-05T22:52:27Z)
• The Complexity of Optimizing Atomic Congestion [14.845310803203724]
  Atomic congestion games are a classic topic in network design, routing, and algorithmic game theory. We show that the problem remains highly intractable even on extremely simple networks. We conclude by extending our analysis towards the (even more challenging) min-max variant of the problem.
  arXiv  Detail & Related papers  (2023-12-15T21:31:30Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. One typical strategy is algorithm unrolling, which relies on automatic differentiation through the operations of an iterative solver. This paper provides theoretical insights into the backward pass of unrolled optimization, leading to a system for generating efficiently solvable analytical models of backpropagation.
  arXiv  Detail & Related papers  (2023-01-28T01:50:42Z)
• Structured Q-learning For Antibody Design [82.78798397798533]
  One of the crucial steps involved in antibody design is to find an arrangement of amino acids in a protein sequence that improves its binding with a pathogen. Combinatorial optimization of antibodies is difficult due to extremely large search spaces and non-linear objectives. Applying traditional Reinforcement Learning to antibody design optimization results in poor performance. We propose Q-learning, an extension of Q-learning that incorporates structural priors for optimization.
  arXiv  Detail & Related papers  (2022-09-10T15:36:55Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  We propose a hybrid approach to combine the best of the two worlds, in which a bi-level framework is developed with an upper-level learning method to optimize the graph. Such a bi-level approach simplifies the learning on the original hard CO and can effectively mitigate the demand for model capacity.
  arXiv  Detail & Related papers  (2021-06-09T09:18:18Z)
• Reversible Action Design for Combinatorial Optimization with Reinforcement Learning [35.50454156611722]
  Reinforcement learning (RL) has recently emerged as a new framework to tackle these problems. We propose a general RL framework that not only exhibits state-of-the-art empirical performance but also generalizes to a variety class of COPs.
  arXiv  Detail & Related papers  (2021-02-14T18:05:42Z)
• MineReduce: an approach based on data mining for problem size reduction [58.720142291102135]
  This paper presents an approach named MineReduce, which uses mined patterns to perform problem size reduction. We present an application of MineReduce to improve a for the heterogeneous fleet vehicle routing problem.
  arXiv  Detail & Related papers  (2020-05-15T08:49:50Z)
• Sparse Optimization for Green Edge AI Inference [28.048770388766716]
  We present a joint inference task selection and downlink beamforming strategy to achieve energy-efficient edge AI inference. By exploiting the inherent connections between the set of task selection and group sparsity transmit beamforming vector, we reformulate the optimization as a group sparse beamforming problem. We establish the global convergence analysis and provide the ergodic worst-case convergence rate for this algorithm.
  arXiv  Detail & Related papers  (2020-02-24T05:21:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.