Research map / Learning theory and algorithms / Combinatorial and search optimization
LMask: Learn to Solve Constrained Routing Problems with Lazy Masking
Tianyou Li, Haijun Zou, JIAYUAN WU, Zaiwen Wen
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add backtracking (LazyMask with TSL) instead of lookahead-only masking | LMask · hard TSPTW-100 | solution infeasibility rate: 31.74% (PIP) -> 0.00% (LMask) | Improved |
| increase the backtracking budget R (ablation) | LMask · hard TSPTW-100 | solution infeasibility rate and inference time: about 2 seconds extra inference time per 100 additional budget | Improved |
| backtracking with lightweight lookahead versus deeper lookahead (depth 2 to 3) for PIP (ablation) | PIP and PIP-D · hard TSPTW-100 | solution infeasibility vs inference time: an order of magnitude rise in inference time for marginal gains | No clear effect |
| add refinement intensity embedding (RIE) (ablation) | LMask · medium TSPTW-50 | optimality gap and feasibility | Improved |
| raise entropy coefficient lambda from 0 to 0.01 (ablation) | LMask · easy TSPTW-100 | optimality gap | Improved |
| raise entropy coefficient lambda from 0.01 to 0.05 (ablation) | LMask · easy TSPTW-100 | optimality gap | Hurt |
| use two-step lookahead (TSL) rather than single-step lookahead (SSL) for initialization (ablation) | LMask · hard TSPTW-100 | solution infeasibility vs time: zero infeasibility within 30 seconds with TSL | Improved |
| train with l1 penalty for violations once backtracking budget is reached (small R in training) | LMask · TSPTW and TSPDL | feasibility | Improved |
| add destination-aware feasibility (PIP-D decoder) over PIP | PIP · synthetic TSPTW | feasibility vs optimality gap: TSPTW-50 Medium gap 2.93% -> 3.31% | Mixed |
| increase problem size on TSPTW benchmark | PIP and PIP-D · TSPTW benchmark | infeasibility and gap: PIP-D infeasibility 5.0% (n=20) -> 66.7% (n=80) | Hurt |
Closest papers by meaning
- Learning to Handle Complex Constraints for Vehicle Routing Problems (NeurIPS 2024 · similarity 0.89)
- CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention (ICML 2025 · similarity 0.87)
- Neural Combinatorial Optimization for Robust Routing Problem with Uncertain Travel Times (NeurIPS 2024 · similarity 0.87)
- Destroy and Repair Using Hyper-Graphs for Routing (AAAI 2025 · similarity 0.87)
- GLOP: Learning Global Partition and Local Construction for Solving Large-Scale Routing Problems in Real-Time (AAAI 2024 · similarity 0.87)
- Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
