ASAP: Exploiting the Satisficing Generalization Edge in Neural Combinatorial Optimization

Deep Reinforcement Learning (DRL) has emerged as a promising approach for solving Combinatorial Optimization (CO) problems, such as the 3D Bin Packing Problem (3D-BPP), Traveling Salesman Problem (TSP), or Vehicle Routing Problem (VRP), but these neural solvers often exhibit brittleness when facing distribution shifts. To address this issue, we uncover the Satisficing Generalization Edge, which we validate both theoretically and experimentally: identifying a set of promising actions is inherently more generalizable than selecting the single optimal action. To exploit this property, we propose Adaptive Selection After Proposal (ASAP), a generic framework that decomposes the decision-making process into two distinct phases: a proposal policy that acts as a robust filter, and a selection policy as an adaptable decision maker. This architecture enables a highly effective online adaptation strategy where the selection policy can be rapidly fine-tuned on a new distribution. Concretely, we introduce a two-phase training framework enhanced by Model-Agnostic Meta-Learning (MAML) to prime the model for fast adaptation. Extensive experiments on 3D-BPP, TSP, and CVRP demonstrate that ASAP improves the generalization capability of state-of-the-art baselines and achieves superior online adaptation on out-of-distribution instances.

We teach AI systems to solve complex logistical puzzles, like finding the fastest delivery routes or efficiently packing 3D boxes. However, these AI solvers are notoriously brittle—they often break down when the environments or rules change unexpectedly. We wondered if this fragility could be solved by changing how the AI makes its choices. We discovered that teaching the AI to identify a broad list of "good enough" options is much more reliable across different scenarios than forcing it to pick the single perfect move. To take advantage of this, we built a two-step framework called ASAP. Instead of making one rigid decision, the system first acts as a robust filter to quickly narrow down a shortlist of promising moves. Then, a second component rapidly adapts on the fly to select the best final action from that shortlist for the specific situation. We tested our system on classic routing and packing problems. By splitting the decision process, we found that our AI could adapt to completely new, unfamiliar conditions significantly better and faster than current state-of-the-art methods.