Accelerating Generalized Benders Decomposition for Wireless Resource Allocation

• URL: http://arxiv.org/abs/2003.01294v2
• Date: Thu, 15 Oct 2020 01:11:11 GMT
• Title: Accelerating Generalized Benders Decomposition for Wireless Resource Allocation
• Authors: Mengyuan Lee, Ning Ma, Guanding Yu, and Huaiyu Dai
• Abstract summary: Generalized Benders decomposition (GBD) is a globally optimal algorithm for mixed integer nonlinear programming (MINLP) problems. We propose to leverage machine learning (ML) techniques to accelerate GBD aiming at decreasing the complexity of the master problem.
• Score: 40.75748765274763
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Generalized Benders decomposition (GBD) is a globally optimal algorithm for mixed integer nonlinear programming (MINLP) problems, which are NP-hard and can be widely found in the area of wireless resource allocation. The main idea of GBD is decomposing an MINLP problem into a primal problem and a master problem, which are iteratively solved until their solutions converge. However, a direct implementation of GBD is time- and memory-consuming. The main bottleneck is the high complexity of the master problem, which increases over the iterations. Therefore, we propose to leverage machine learning (ML) techniques to accelerate GBD aiming at decreasing the complexity of the master problem. Specifically, we utilize two different ML techniques, classification and regression, to deal with this acceleration task. In this way, a cut classifier and a cut regressor are learned, respectively, to distinguish between useful and useless cuts. Only useful cuts are added to the master problem and thus the complexity of the master problem is reduced. By using a resource allocation problem in device-to-device communication networks as an example, we validate that the proposed method can reduce the computational complexity of GBD without loss of optimality and has strong generalization ability. The proposed method is applicable for solving various MINLP problems in wireless networks since the designs are invariant for different problems.

Related papers

• Towards An Unsupervised Learning Scheme for Efficiently Solving Parameterized Mixed-Integer Programs [6.1860817947800655]
  We train an autoencoder for binary variables in an unsupervised learning fashion. We present a strategy to construct a class of cutting plane constraints from the decoder parameters of an offline-trained AE. Their integration into the primal MIP problem leads to a tightened MIP with the reduced feasible region.
  arXiv  Detail & Related papers  (2024-12-23T14:48:32Z)
• DiffSG: A Generative Solver for Network Optimization with Diffusion Model [75.27274046562806]
  Generative diffusion models are popular in various cross-domain applications. These models hold promise in tackling complex network optimization problems. We propose a new framework for generative diffusion models called Diffusion Model-based Solution Generation.
  arXiv  Detail & Related papers  (2024-08-13T07:56:21Z)
• Symmetry-preserving graph attention network to solve routing problems at multiple resolutions [1.9304772860080408]
  We introduce the first-ever completely equivariant model and training to solve problems. It is essential to capture the multiscale structure of the input graph. We propose a Multiresolution scheme in combination with Equi Graph Attention network (mEGAT) architecture.
  arXiv  Detail & Related papers  (2023-10-24T06:22:20Z)
• Hybrid Quantum-Classical General Benders Decomposition Algorithm for Unit Commitment with Multiple Networked Microgrids [5.6035987109587895]
  Unit commitment with multiple networked microgrids (UCMNM) is a typical mixed-integer nonlinear programming problem. We introduce quantum computing in Generalized Benders decomposition algorithm (GBDA) framework. For privacy-preserving and independent decision-making, HQC-GBDA decomposes the UCMNM problem into a master problem and a series of sub-problems.
  arXiv  Detail & Related papers  (2022-10-13T02:26:27Z)
• Large-scale matrix optimization based multi microgrid topology design with a constrained differential evolution algorithm [30.792124441010447]
  A binary-matrix-based differential evolution algorithm is proposed to solve nonlinear problems. To deal with the constraints, we propose an improved feasibility rule based environmental selection strategy.
  arXiv  Detail & Related papers  (2022-07-18T00:35:29Z)
• Graph Signal Restoration Using Nested Deep Algorithm Unrolling [85.53158261016331]
  Graph signal processing is a ubiquitous task in many applications such as sensor, social transportation brain networks, point cloud processing, and graph networks. We propose two restoration methods based on convexindependent deep ADMM (ADMM) parameters in the proposed restoration methods are trainable in an end-to-end manner.
  arXiv  Detail & Related papers  (2021-06-30T08:57:01Z)
• Deep Unsupervised Learning for Generalized Assignment Problems: A Case-Study of User-Association in Wireless Networks [11.42707683459227]
  We propose a novel deep unsupervised learning (DUL) approach to solve the generalized assignment problems (GAP) in a time-efficient manner. In particular, we propose a new approach that facilitates to train a deep neural network (DNN) using a customized loss function. Numerical results demonstrate that the proposed DUL approach provides near-optimal results with significantly lower time-complexity.
  arXiv  Detail & Related papers  (2021-03-26T16:07:02Z)
• A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free! [72.31332210635524]
  Decentralized optimization methods enable on-device training of machine learning models without a central coordinator. We propose a new randomized first-order method which tackles the communication bottleneck by applying randomized compression operators. We prove that our method can solve the problems without any increase in the number of communications compared to the baseline.
  arXiv  Detail & Related papers  (2020-11-03T13:35:53Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  We introduce new generalized data reduction and transformation rules for the maximum weight independent set problem. Surprisingly, these so-called increasing transformations can simplify the problem and also open up the reduction space to yield even smaller irreducible graphs later in the algorithm. Our algorithm computes significantly smaller irreducible graphs on all except one instance, solves more instances to optimality than previously possible, is up to two orders of magnitude faster than the best state-of-the-art solver, and finds higher-quality solutions than solvers DynWVC and HILS.
  arXiv  Detail & Related papers  (2020-08-12T08:52:50Z)
• Graph Neural Networks for Scalable Radio Resource Management: Architecture Design and Theoretical Analysis [31.372548374969387]
  We propose to apply graph neural networks (GNNs) to solve large-scale radio resource management problems. The proposed method is highly scalable and can solve the beamforming problem in an interference channel with $1000$ transceiver pairs within $6$ milliseconds on a single GPU.
  arXiv  Detail & Related papers  (2020-07-15T11:43:32Z)
• 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)
• Detached Error Feedback for Distributed SGD with Random Sparsification [98.98236187442258]
  Communication bottleneck has been a critical problem in large-scale deep learning. We propose a new distributed error feedback (DEF) algorithm, which shows better convergence than error feedback for non-efficient distributed problems. We also propose DEFA to accelerate the generalization of DEF, which shows better bounds than DEF.
  arXiv  Detail & Related papers  (2020-04-11T03:50:59Z)

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.