Equity-Transformer: Solving NP-hard Min-Max Routing Problems as Sequential Generation with Equity Context

• URL: http://arxiv.org/abs/2306.02689v3
• Date: Mon, 5 Feb 2024 02:36:54 GMT
• Title: Equity-Transformer: Solving NP-hard Min-Max Routing Problems as Sequential Generation with Equity Context
• Authors: Jiwoo Son, Minsu Kim, Sanghyeok Choi, Hyeonah Kim, Jinkyoo Park
• Abstract summary: Min-max routing problems aim to minimize the maximum tour length among multiple agents by having agents conduct tasks in a cooperative manner. Existing methods are facing challenges, particularly in large-scale problems that require the coordination of numerous agents to cover thousands of cities. This paper proposes Equity-Transformer to solve large-scale min-max routing problems.
• Score: 33.270494123656746
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Min-max routing problems aim to minimize the maximum tour length among multiple agents by having agents conduct tasks in a cooperative manner. These problems include impactful real-world applications but are known as NP-hard. Existing methods are facing challenges, particularly in large-scale problems that require the coordination of numerous agents to cover thousands of cities. This paper proposes Equity-Transformer to solve large-scale min-max routing problems. First, we employ sequential planning approach to address min-max routing problems, allowing us to harness the powerful sequence generators (e.g., Transformer). Second, we propose key inductive biases that ensure equitable workload distribution among agents. The effectiveness of Equity-Transformer is demonstrated through its superior performance in two representative min-max routing tasks: the min-max multi-agent traveling salesman problem (min-max mTSP) and the min-max multi-agent pick-up and delivery problem (min-max mPDP). Notably, our method achieves significant reductions of runtime, approximately 335 times, and cost values of about 53\% compared to a competitive heuristic (LKH3) in the case of 100 vehicles with 1,000 cities of mTSP. We provide reproducible source code: \url{https://github.com/kaist-silab/equity-transformer}.

Related papers

• MultiMax: Sparse and Multi-Modal Attention Learning [60.49318008131978]
  SoftMax is a ubiquitous ingredient of modern machine learning algorithms. We show that sparsity can be achieved by a family of SoftMax variants, but they often require an alternative loss function and do not preserve multi-modality. We propose MultiMax, which adaptively modulates the output distribution according to input entry range.
  arXiv  Detail & Related papers  (2024-06-03T10:51:43Z)
• DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems [26.48767051423456]
  We present a novel attention-based Partition-and-Navigation encoder (P&N) that learns distinct embeddings for partition and navigation. We develop an effective agent-permutation-symmetric (APS) loss function.
  arXiv  Detail & Related papers  (2024-05-27T15:33:16Z)
• iMTSP: Solving Min-Max Multiple Traveling Salesman Problem with Imperative Learning [8.747306544853961]
  The paper considers a Min-Max Multiple Traveling Salesman Problem (MTSP) The goal is to find a set of tours, one for each agent, to collectively visit all the cities while minimizing the length of the longest tour. We introduce a new self-supervised, bilevel, end-to-end learning framework, which we refer to as imperative MTSP (iMTSP)
  arXiv  Detail & Related papers  (2024-05-01T02:26:13Z)
• Robust Multi-Task Learning with Excess Risks [24.695243608197835]
  Multi-task learning (MTL) considers learning a joint model for multiple tasks by optimizing a convex combination of all task losses. Existing methods use an adaptive weight updating scheme, where task weights are dynamically adjusted based on their respective losses to prioritize difficult tasks. We propose Multi-Task Learning with Excess Risks (ExcessMTL), an excess risk-based task balancing method that updates the task weights by their distances to convergence.
  arXiv  Detail & Related papers  (2024-02-03T03:46:14Z)
• Parameter-efficient Tuning of Large-scale Multimodal Foundation Model [68.24510810095802]
  We propose A graceful prompt framework for cross-modal transfer (Aurora) to overcome these challenges. Considering the redundancy in existing architectures, we first utilize the mode approximation to generate 0.1M trainable parameters to implement the multimodal prompt tuning. A thorough evaluation on six cross-modal benchmarks shows that it not only outperforms the state-of-the-art but even outperforms the full fine-tuning approach.
  arXiv  Detail & Related papers  (2023-05-15T06:40:56Z)
• M$^3$ViT: Mixture-of-Experts Vision Transformer for Efficient Multi-task Learning with Model-Accelerator Co-design [95.41238363769892]
  Multi-task learning (MTL) encapsulates multiple learned tasks in a single model and often lets those tasks learn better jointly. Current MTL regimes have to activate nearly the entire model even to just execute a single task. We present a model-accelerator co-design framework to enable efficient on-device MTL.
  arXiv  Detail & Related papers  (2022-10-26T15:40:24Z)
• Pruning Self-attentions into Convolutional Layers in Single Path [89.55361659622305]
  Vision Transformers (ViTs) have achieved impressive performance over various computer vision tasks. We propose Single-Path Vision Transformer pruning (SPViT) to efficiently and automatically compress the pre-trained ViTs. Our SPViT can trim 52.0% FLOPs for DeiT-B and get an impressive 0.6% top-1 accuracy gain simultaneously.
  arXiv  Detail & Related papers  (2021-11-23T11:35:54Z)
• DAN: Decentralized Attention-based Neural Network to Solve the MinMax Multiple Traveling Salesman Problem [5.137147284997655]
  We introduce a decentralized attention-based neural network method to solve the MinMax mTSP, named DAN. In DAN, agents learn fully decentralized policies to collaboratively construct a tour, by predicting the future decisions of other agents. We experimentally demonstrate our model on small- to large-scale mTSP instances, which involve 50 to 1000 cities and 5 to 20 agents, and compare against state-of-the-art baselines.
  arXiv  Detail & Related papers  (2021-09-09T12:26:04Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)

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.