A hybrid deep-learning-metaheuristic framework for bi-level network design problems

• URL: http://arxiv.org/abs/2303.06024v3
• Date: Thu, 10 Aug 2023 13:03:03 GMT
• Title: A hybrid deep-learning-metaheuristic framework for bi-level network design problems
• Authors: Bahman Madadi and Goncalo Homem de Almeida Correia
• Abstract summary: This study proposes a hybrid deep-learning-metaheuristic framework with a bi-level architecture for road network design problems (NDPs) We train a graph neural network (GNN) to approximate the solution of the user equilibrium (UE) traffic assignment problem. We use inferences made by the trained model to calculate fitness function evaluations of a genetic algorithm (GA) to approximate solutions for NDPs.
• Score: 2.741266294612776
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This study proposes a hybrid deep-learning-metaheuristic framework with a bi-level architecture for road network design problems (NDPs). We train a graph neural network (GNN) to approximate the solution of the user equilibrium (UE) traffic assignment problem and use inferences made by the trained model to calculate fitness function evaluations of a genetic algorithm (GA) to approximate solutions for NDPs. Using three test networks, two NDP variants and an exact solver as benchmark, we show that on average, our proposed framework can provide solutions within 1.5% gap of the best results in less than 0.5% of the time used by the exact solution procedure. Our framework can be utilized within an expert system for infrastructure planning to determine the best infrastructure planning and management decisions under different scenarios. Given the flexibility of the framework, it can easily be adapted to many other decision problems that can be modeled as bi-level problems on graphs. Moreover, we foreseen interesting future research directions, thus we also put forward a brief research agenda for this topic. The key observation from our research that can shape future research is that the fitness function evaluation time using the inferences made by the GNN model was in the order of milliseconds, which points to an opportunity and a need for novel heuristics that 1) can cope well with noisy fitness function values provided by deep learning models, and 2) can use the significantly enlarged efficiency of the evaluation step to explore the search space effectively (rather than efficiently). This opens a new avenue for a modern class of metaheuristics that are crafted for use with AI-powered predictors.

Related papers

• 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)
• A Multi-Head Ensemble Multi-Task Learning Approach for Dynamical Computation Offloading [62.34538208323411]
  We propose a multi-head ensemble multi-task learning (MEMTL) approach with a shared backbone and multiple prediction heads (PHs) MEMTL outperforms benchmark methods in both the inference accuracy and mean square error without requiring additional training data.
  arXiv  Detail & Related papers  (2023-09-02T11:01:16Z)
• Graph Reinforcement Learning for Network Control via Bi-Level Optimization [37.00510744883984]
  We argue that data-driven strategies can automate this process and learn efficient algorithms without compromising optimality. We present network control problems through the lens of reinforcement learning and propose a graph network-based framework to handle a broad class of problems.
  arXiv  Detail & Related papers  (2023-05-16T03:20:22Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems. We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately. Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
  arXiv  Detail & Related papers  (2022-10-31T09:46:26Z)
• Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation [19.582494782591386]
  This work proposes an unsupervised learning framework for optimization (CO) problems. Our key contribution is the observation that if the relaxed objective satisfies entry-wise concavity, a low optimization loss guarantees the quality of the final integral solutions. In particular, this observation can guide the design of objective models in applications where the objectives are not given explicitly while requiring being modeled in prior.
  arXiv  Detail & Related papers  (2022-07-13T06:44:17Z)
• Acceleration techniques for optimization over trained neural network ensembles [1.0323063834827415]
  We study optimization problems where the objective function is modeled through feedforward neural networks with rectified linear unit activation. We present a mixed-integer linear program based on existing popular big-$M$ formulations for optimizing over a single neural network.
  arXiv  Detail & Related papers  (2021-12-13T20:50:54Z)
• Decentralized Personalized Federated Learning for Min-Max Problems [79.61785798152529]
  This paper is the first to study PFL for saddle point problems encompassing a broader range of optimization problems. We propose new algorithms to address this problem and provide a theoretical analysis of the smooth (strongly) convex-(strongly) concave saddle point problems. Numerical experiments for bilinear problems and neural networks with adversarial noise demonstrate the effectiveness of the proposed methods.
  arXiv  Detail & Related papers  (2021-06-14T10:36:25Z)
• TrackMPNN: A Message Passing Graph Neural Architecture for Multi-Object Tracking [8.791710193028903]
  This study follows many previous approaches to multi-object tracking (MOT) that model the problem using graph-based data structures. We create a framework based on dynamic undirected graphs that represent the data association problem over multiple timesteps. We also provide solutions and propositions for the computational problems that need to be addressed to create a memory-efficient, real-time, online algorithm.
  arXiv  Detail & Related papers  (2021-01-11T21:52:25Z)
• On the performance of deep learning for numerical optimization: an application to protein structure prediction [0.0]
  We present a study on the performance of the deep learning models to deal with global optimization problems. The proposed approach adopts the idea of the neural architecture search (NAS) to generate efficient neural networks. Experiments reveal that the generated learning models can achieve competitive results when compared to hand-designed algorithms.
  arXiv  Detail & Related papers  (2020-12-17T17:01:30Z)
• Belief Propagation Reloaded: Learning BP-Layers for Labeling Problems [83.98774574197613]
  We take one of the simplest inference methods, a truncated max-product Belief propagation, and add what is necessary to make it a proper component of a deep learning model. This BP-Layer can be used as the final or an intermediate block in convolutional neural networks (CNNs) The model is applicable to a range of dense prediction problems, is well-trainable and provides parameter-efficient and robust solutions in stereo, optical flow and semantic segmentation.
  arXiv  Detail & Related papers  (2020-03-13T13:11:35Z)
• Optimizing Wireless Systems Using Unsupervised and Reinforced-Unsupervised Deep Learning [96.01176486957226]
  Resource allocation and transceivers in wireless networks are usually designed by solving optimization problems. In this article, we introduce unsupervised and reinforced-unsupervised learning frameworks for solving both variable and functional optimization problems.
  arXiv  Detail & Related papers  (2020-01-03T11:01:52Z)

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.