Neural Sequence Generation with Constraints via Beam Search with Cuts: A Case Study on VRP

Pouya Shati, Eldan Cohen, Sheila A. McIlraith

Introduction

Neural sequence models, such as Transformers, have shown significant promise in solving combinatorial optimization problems like the Vehicle Routing Problem (VRP) and the Traveling Salesperson Problem (TSP). These models typically generate solutions sequentially, guided by decoding algorithms like beam search. However, real-world applications often involve strict, non-negotiable constraints—such as vehicle capacity limits or specific visit sequences—that standard beam search struggle to enforce. Because beam search is inherently myopic, it often pursues high-probability tokens that lead to dead-ends where no valid completion of the sequence exists.

Methodology: Beam Search with Cuts (BSC)

To address these limitations, this paper introduces Beam Search with Cuts (BSC). This neuro-symbolic approach integrates a classical Constraint Satisfaction Problem (CSP) solver directly into the neural decoding process.

At each expansion step, the algorithm performs a "cut" by translating the current partial sequence and the problem's hard constraints into a formal CSP. An off-the-shelf solver (such as Gurobi for Integer Programming or PySAT for Boolean Satisfiability) then checks if the partial sequence can mathematically be extended into a valid full solution. If the solver proves feasibility is impossible, that branch is immediately pruned from the beam. To maintain efficiency, the system utilizes incremental solving—carrying logical clauses forward between steps—and enforces strict timeouts to prevent the solver from stalling the search process.

Experimental Evaluation

The authors evaluated BSC on standard Capacitated Vehicle Routing Problem (CVRP) benchmarks and synthetic datasets involving temporal and demand-based constraints. The primary goal was to determine if BSC could find feasible solutions in highly constrained environments where standard beam search fails.

Table 1: Comparison of standard Beam Search and Beam Search with Cuts across CVRP instances. BSC consistently finds solutions with the required number of vehicles (m) where standard search fails.

As shown in Table 1, BSC demonstrates a clear advantage in feasibility. In nine highly constrained CVRP instances, a standard beam search with a massive width of 8,096 failed to find any valid solutions (often requiring more vehicles than the constraint allowed). In contrast, BSC, using a minimal beam width of just 4, successfully identified valid solutions for all instances. Furthermore, the solution quality remained high; in several cases, pruning the search space actually allowed the model to find shorter total distances than the unconstrained baseline.

Pushing the Limits of Feasibility

A key insight of this work is that scaling beam width is an ineffective strategy for handling hard constraints. While standard search requires exponentially larger widths as constraints tighten, BSC maintains its effectiveness by focusing only on the feasible search space.

Figure 1: Evolution of solution distance as vehicle capacity constraints are tightened. BSC successfully finds solutions right up to the mathematical limit of infeasibility.

When testing the limits by incrementally tightening vehicle capacity, BSC continued to find valid routes until the problem became mathematically infeasible. As illustrated in Figure 1, while the total distance naturally increases as constraints become more restrictive, the BSC framework ensures that the generated sequences remain valid throughout the process.

Conclusion

Beam Search with Cuts provides a robust framework for enforcing hard constraints in neural sequence generation. By combining the predictive power of deep learning with the rigorous logic of CSP solvers, the method guarantees feasibility without sacrificing solution quality. Future work will explore caching feasibility results to further reduce computational overhead and extending the framework to domains like program synthesis and automated planning.

Summary updated

Abstract

In recent years, neural sequence models have been applied successfully to solve combinatorial optimization problems. Solutions, encoded as sequences, are typically generated from trained models via beam search, a search algorithm that generates sequences token-by-token while keeping a fixed number of promising partial solutions at each step. In this paper, we explore the problem of augmenting beam search generation with the enforcement of requirements---hard constraints that any generated solution must adhere to. We propose a hybrid approach, by encoding the requirements in the form of a constraint satisfaction problem (CSP) and iteratively solving the CSP to cut any partial solution within the beam search that is incapable of satisfying the requirements. We study this problem in the context of vehicle routing problems (VRP) further augmented with capacity-related or temporal requirements. We experimentally show that cuts often allow us to satisfy the requirements with negligible impact on solution quality. Without the use of cuts, beam search is shown to be exponentially less likely to satisfy the requirements as the length of the solution increases and/or the requirements are strengthened.
BibTeX
@inproceedings{shati2024neural,
  author = {Pouya Shati and Eldan Cohen and Sheila A. McIlraith},
  title = {{Neural Sequence Generation with Constraints via Beam Search with Cuts: A Case Study on VRP}},
  booktitle = {SOCS},
  year = {2024},
  doi = {10.1609/socs.v17i1.31549},
}
Figure