PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Active Search for Combinatorial Optimization Problems

André Hottung, Yeong-Dae Kwon, Kevin Tierney

arXiv:2106.05126v3cs.LGcs.AImath.OC

TL;DR

ML construction methods lack strong adaptive search guidance, while full active search is too costly because it updates all model weights for each test instance. The paper introduces three efficient active-search strategies that update only parameter subsets. These methods improve search performance, outperform ML baselines, surpass LKH3 on CVRP, and generalize to instances much larger than those seen in training.

  • Problem

    Construction methods combine readily with sampling and beam search but offer limited search guidance, while full active search is too time- and memory-intensive because it updates all model weights per test instance.

    Source: §1 · pp. 1–2

  • Method

    The paper evaluates three efficient active-search strategies that fine-tune only a subset of model parameters during instance-specific search.

    Source: §1 · p. 2

  • Results

    EAS significantly improves performance over sampling, outperforms state-of-the-art ML methods on CVRP and JSSP, surpasses LKH3 on CVRP, and improves generalization to larger instances.

    Source: §4.2 · p. 7, §4.3 · p. 8

  • Takeaways & Limitations

    Efficient active search provides a simple way to add extensive, instance-adaptive search to existing ML construction methods across difficult combinatorial optimization problems.

    Source: §1 · p. 2, §5 · p. 9

    The tabular EAS method requires problem-specific design of its state-action mapping, and the evaluated TSP assumes a distance matrix obeying the triangle inequality.

    Source: §3.3 · p. 5, §4.1 · p. 6

Abstract

from arXiv · show

Recently numerous machine learning based methods for combinatorial optimization problems have been proposed that learn to construct solutions in a sequential decision process via reinforcement learning. While these methods can be easily combined with search strategies like sampling and beam search, it is not straightforward to integrate them into a high-level search procedure offering strong search guidance. Bello et al. (2016) propose active search, which adjusts the weights of a (trained) model with respect to a single instance at test time using reinforcement learning. While active search is simple to implement, it is not competitive with state-of-the-art methods because adjusting all model weights for each test instance is very time and memory intensive. Instead of updating all model weights, we propose and evaluate three efficient active search strategies that only update a subset of parameters during the search. The proposed methods offer a simple way to significantly improve the search performance of a given model and outperform state-of-the-art machine learning based methods on combinatorial problems, even surpassing the well-known heuristic solver LKH3 on the capacitated vehicle routing problem. Finally, we show that (efficient) active search enables learned models to effectively solve instances that are much larger than those seen during training.

1 INTRODUCTION

ML construction methods are easy to combine with sampling and beam search but provide limited adaptive search guidance. The paper introduces efficient active search, which updates only subsets of parameters and improves performance across combinatorial optimization tasks.

Background

  • Construction methods sequentially build incomplete solutions and support greedy decoding, sampling, and beam search without problem-specific components.However, these search strategies provide limited guidance and do not change their sampling distribution based on solutions already found.Source: §1 · p. 1
  • Active search adapts model parameters during single-instance search to increase the likelihood of generating high-quality solutions, but updating all parameters is resource intensive.This resource cost has limited adoption despite improvements over random sampling from an already trained model.Source: §1 · p. 2

Contributions

  • Efficient active search updates only a subset of model parameters per test instance, reducing runtime while preserving solution quality.The approach retains the active-search idea of adapting a trained model during instance-specific search without updating the full network.Source: §1 · p. 2

Evaluation

  • Three EAS implementations significantly improve performance over pure sampling across TSP, CVRP, and JSSP.For CVRP and JSSP, the approaches outperform state-of-the-art ML methods, surpass LKH3 on CVRP, and improve performance on instances much larger than those used for training.Source: §1 · p. 2

2 LITERATURE REVIEW

Prior work applies neural construction and improvement methods across routing, scheduling, and other combinatorial optimization problems. These approaches differ in whether they construct solutions directly, guide post-hoc search, or iteratively improve existing solutions.

Construction methods

  • Neural construction methods have been applied to TSP using pointer networks, actor-critic reinforcement learning, graph embeddings, and graph attention networks.These studies target sequential or graph-based solution construction for instances including TSP sizes up to 50 or 100 cities.Source: §2 · p. 2
  • CVRP research includes attention-based recurrent and transformer-like models, embedding updates during search, and parallel tour construction with time windows.Updating node embeddings improves performance but increases runtime.Source: §2 · p. 2
  • Beyond routing, neural construction methods address minimum vertex cover, maximum cut, job shop scheduling, maximal independent set, and maximal clique.The literature also includes guided tree search and broader reviews of ML methods for combinatorial optimization.Source: §2 · p. 2

Post-hoc search

  • Some methods predict edge heat-maps and use beam search, Monte Carlo tree search, or dynamic programming to construct routing solutions afterward.These approaches separate learned edge preferences from the subsequent solution-search procedure.Source: §2 · p. 3

Improvement methods

  • Improvement methods iteratively modify complete solutions using learned region or rule selection, learned repair after handcrafted destruction, local-neighborhood selection, or continuous optimization.They generally spend more time solving instances and often find better solutions than construction-based methods, while commonly relying on problem-specific components.Source: §2 · p. 3

3 SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS WITH EAS

Efficient active search updates only instance-specific parameters while keeping most of a trained construction model fixed, enabling guided search with lower runtime and memory costs. The section presents embedding, added-layer, and tabular update strategies for sequential solution construction.

3 SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS WITH EAS

  • EAS adjusts a small parameter subset for each instance, reducing runtime while preserving or sometimes improving solution quality and supporting parallel batch generation.Most network parameters remain fixed, so gradients and unchanged operations can be shared across instances.Source: §3 · p. 3, §3.1 · p. 4
  • Sequential construction models encode an instance into static embeddings and autoregressively select actions until a complete feasible solution and its objective value are obtained.Static embeddings can be computed once per instance, allowing rapid sampling of multiple solutions.Source: §3 · p. 3

3.1 EMBEDDING UPDATES

  • EAS-Emb updates encoder-generated instance embeddings using reinforcement-learning and imitation-learning losses to favor low-cost solutions and the best solution found so far.A tunable imitation term can emphasize reproducing the incumbent, accelerating convergence when search iterations are limited.Source: §3.1 · p. 4

3.2 ADDED-LAYER UPDATES

  • EAS-Lay inserts an instance-specific residual layer whose weights are updated during search while the original model layers remain fixed.The added layer is initialized so it does not affect the model output during the first search iteration; its placement trades performance against memory requirements.Source: §3.2 · pp. 4–5

3.3 TABULAR UPDATES

  • EAS-Tab modifies action probabilities with a lookup table, leaving network parameters unchanged and avoiding backpropagation for fast, memory-efficient generation.The table is updated from the incumbent solution, while α controls exploration and σ controls exploitation of incumbent actions.Source: §3.3 · p. 5
  • EAS-Tab requires problem-specific design of the state-action mapping g, and for TSP it increases probabilities for directed edges appearing in the incumbent solution.This mapping ignores previous visits in the state when selecting the next move and makes the approach similar to ant colony optimization.Source: §3.3 · p. 5

4 EXPERIMENTS

Experiments evaluate efficient active search across TSP, CVRP, and JSSP, comparing its solution quality, runtime, generalization, search trajectories, and imitation-learning sensitivity.

4 EXPERIMENTS

  • EAS outperforms sampling across TSP, CVRP, and JSSP, surpassing machine-learning baselines and LKH3 on CVRP while improving generalization to larger instances.The evaluation uses existing POMO and L2D construction methods, with exact and heuristic solvers included where applicable.Source: §4 · p. 5, §4.1 · p. 7, §4.2 · p. 7

4.1 TSP

  • On TSP, EAS substantially reduces active search runtime while retaining a nearly comparable optimality gap, and reduces the sampling gap by up to 3.6x on larger instances.Original active search achieves the best POMO-based gap but requires 5 days; EAS is faster, while DPDP remains the strongest ML-based comparison through problem-specific beam search.Source: §4.1 · pp. 6–7

4.2 CVRP

  • On CVRP, EAS-Lay performs best on test instances and beats LKH3 in gap, while all EAS variants outperform LKH3 there and remain faster than active search on n = 125 and n = 150.For n = 200, active search reaches a 0.22% gap to LKH3, whereas tuning α improves EAS-Tab from 11.8% to at least 3.54%.Source: §4.2 · p. 7, Table 2 · p. 7

4.3 JSSP

  • On JSSP, EAS-Emb performs best across all three instance sets and reduces the 10×10 sampling gap by 50%, while reducing the 20 × 15 gap from 20.8% to 16.8%.EAS-Tab performs similarly to active search on test instances but generalizes poorly to larger instances; CPU-bound L2D limits batching and runtime.Source: §4.3 · p. 8, Table 3 · p. 8

4.4 SEARCH TRAJECTORY ANALYSIS

  • Across 200 search iterations, sampling quality remains unchanged, whereas every active-search variant progressively improves sampled-solution quality for TSP, CVRP, and JSSP.This trajectory indicates that the variants modify parameters to increase the likelihood of generating high-quality solutions during search.Source: §4.4 · p. 8, Figure 2 · p. 9

4.5 ABLATION STUDY: IMITATION LEARNING LOSS

  • Imitation learning improves EAS-Emb and EAS-Lay on TSP and CVRP, has little effect on JSSP, and can hurt performance when λ is too low or too high.The study evaluates different λ values on reduced TSP and CVRP subsets and all JSSP test instances.Source: §4.5 · p. 9, Figure 3 · p. 9

5 CONCLUSION

The paper presents efficient active search, which fine-tunes a small subset of model parameters per test instance to extend ML construction heuristics with extensive search. Across three difficult combinatorial problems, the three EAS implementations improve performance and generalization, while search-time cost and complex industrial side constraints remain limitations.

  • EAS fine-tunes a small subset of model parameters for each test instance, extending ML construction heuristics with extensive search.The approach is evaluated through three example implementations.Source: §5 · p. 9
  • EAS significantly improves model performance in testing and generalization experiments across three difficult combinatorial optimization problems.Source: §5 · p. 9
  • Search requires time, so greedy construction remains preferable when solutions must be extremely fast or practically instantaneous.Source: §5 · p. 9
  • Additional work may be needed for complex side constraints common in industrial optimization problems.Source: §5 · p. 9

A EXPERIMENTS FOR MORE REALISTIC CVRP INSTANCES

On more realistic CVRP instance sets, EAS methods are compared with NLNS, LKH3, and unified hybrid genetic search, including a cross-distribution EAS-Lay model trained on uniform instances.

Setup

Results

  • EAS-Emb and EAS-Lay find better solutions than NLNS and LKH3 on 8 of 9 realistic CVRP instance sets.EAS-Tab outperforms NLNS and LKH3 on all but two instance sets.Source: A EXPERIMENTS FOR MORE REALISTIC CVRP… · p. 12
  • EAS-Lay trained on uniform n = 100 instances generalizes with gaps of 0.26% to 4.08% relative to unified hybrid genetic search.These cross-distribution results are marked with a star in the table.Source: A EXPERIMENTS FOR MORE REALISTIC CVRP… · p. 12
  • Table 4 reports each method’s gap to unified hybrid genetic search and average runtime per instance.Source: Table 4 · p. 12

B ABLATION STUDY: ACTIVE SEARCH LOSS

The active-search loss ablation examines whether imitation learning improves original active search, comparing versions with and without the imitation learning loss component.

C PARAMETER SWEEP: EAS-TAB INTENSIFICATION

The parameter sweep studies σ in EAS-Tab, where σ controls the degree of search exploitation and the influence of lookup-table updates.

Loading 2106.05126v3…