LMask: Learn to Solve Constrained Routing Problems with Lazy Masking

• URL: http://arxiv.org/abs/2505.17938v1
• Date: Fri, 23 May 2025 14:15:26 GMT
• Title: LMask: Learn to Solve Constrained Routing Problems with Lazy Masking
• Authors: Tianyou Li, Haijun Zou, Jiayuan Wu, Zaiwen Wen,
• Abstract summary: We propose LMask, a novel learning framework that utilizes dynamic masking to generate high-quality feasible solutions for constrained routing problems.<n>LMask achieves state-of-the-art feasibility rates and solution quality, outperforming existing neural methods.
• Score: 4.693576188349811
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Routing problems are canonical combinatorial optimization tasks with wide-ranging applications in logistics, transportation, and supply chain management. However, solving these problems becomes significantly more challenging when complex constraints are involved. In this paper, we propose LMask, a novel learning framework that utilizes dynamic masking to generate high-quality feasible solutions for constrained routing problems. LMask introduces the LazyMask decoding method, which lazily refines feasibility masks with the backtracking mechanism. In addition, it employs the refinement intensity embedding to encode the search trace into the model, mitigating representation ambiguities induced by backtracking. To further reduce sampling cost, LMask sets a backtracking budget during decoding, while constraint violations are penalized in the loss function during training to counteract infeasibility caused by this budget. We provide theoretical guarantees for the validity and probabilistic optimality of our approach. Extensive experiments on the traveling salesman problem with time windows (TSPTW) and TSP with draft limits (TSPDL) demonstrate that LMask achieves state-of-the-art feasibility rates and solution quality, outperforming existing neural methods.

Related papers

• Cutting Slack: Quantum Optimization with Slack-Free Methods for Combinatorial Benchmarks [4.266376725904727]
  Constraint handling remains a key bottleneck in quantum optimization.<n>We investigate a suite of Lagrangian-based optimization techniques for solving constrained problems on quantum simulators and hardware.<n>Our results highlight the flexibility of Lagrangian formulations as a scalable alternative to QUBO penalization.
  arXiv  Detail & Related papers  (2025-07-16T11:39:47Z)
• Learning for Cross-Layer Resource Allocation in MEC-Aided Cell-Free Networks [71.30914500714262]
  Cross-layer resource allocation over mobile edge computing (MEC)-aided cell-free networks can sufficiently exploit the transmitting and computing resources to promote the data rate.<n>Joint subcarrier allocation and beamforming optimization are investigated for the MEC-aided cell-free network from the perspective of deep learning.
  arXiv  Detail & Related papers  (2024-12-21T10:18:55Z)
• Learning to Handle Complex Constraints for Vehicle Routing Problems [26.354311541533754]
  Vehicle Routing Problems (VRPs) can model many real-world scenarios and often involve complex constraints. Recent neural methods excel in constructing solutions based on feasibility masking, but struggle with handling complex constraints. We propose a novel Proactive Infeasibility Prevention framework to advance the capabilities of neural methods towards more complex VRPs.
  arXiv  Detail & Related papers  (2024-10-28T14:26:54Z)
• Robust Stochastically-Descending Unrolled Networks [85.6993263983062]
  Deep unrolling is an emerging learning-to-optimize method that unrolls a truncated iterative algorithm in the layers of a trainable neural network.<n>We show that convergence guarantees and generalizability of the unrolled networks are still open theoretical problems.<n>We numerically assess unrolled architectures trained under the proposed constraints in two different applications.
  arXiv  Detail & Related papers  (2023-12-25T18:51:23Z)
• Amortizing intractable inference in large language models [56.92471123778389]
  We use amortized Bayesian inference to sample from intractable posterior distributions. We empirically demonstrate that this distribution-matching paradigm of LLM fine-tuning can serve as an effective alternative to maximum-likelihood training. As an important application, we interpret chain-of-thought reasoning as a latent variable modeling problem.
  arXiv  Detail & Related papers  (2023-10-06T16:36:08Z)
• Faith and Fate: Limits of Transformers on Compositionality [109.79516190693415]
  We investigate the limits of transformer large language models across three representative compositional tasks. These tasks require breaking problems down into sub-steps and synthesizing these steps into a precise answer. Our empirical findings suggest that transformer LLMs solve compositional tasks by reducing multi-step compositional reasoning into linearized subgraph matching.
  arXiv  Detail & Related papers  (2023-05-29T23:24:14Z)
• Reimagining Demand-Side Management with Mean Field Learning [0.0]
  We propose a new method for DSM, in particular the problem of controlling a large population of electrical devices to follow a desired consumption signal. We develop a new algorithm, MD-MFC, which provides theoretical guarantees for convex and Lipschitz objective functions.
  arXiv  Detail & Related papers  (2023-02-16T10:15:08Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Learning to Solve Soft-Constrained Vehicle Routing Problems with Lagrangian Relaxation [0.4014524824655105]
  Vehicle Routing Problems (VRPs) in real-world applications often come with various constraints. We propose a Reinforcement Learning based method to solve soft-constrained VRPs. We apply the method on three common types of VRPs, the Travelling Salesman Problem with Time Windows (TSPTW), the Capacitated VRP (CVRP) and the Capacitated VRP with Time Windows (CVRPTW)
  arXiv  Detail & Related papers  (2022-07-20T12:51:06Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)

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.