2025· Neural Information Processing Systems· pp. 152298-152338· 0 citations· 46 references
Computer Science
TL;DR
Evaluated on synthetic and large-scale real-world MILP problems, DynSep speeds up average solving time by 64% on easy and medium datasets, and reduces primal-dual gap integral within the given time limit by 16% on hard datasets.
Abstract
Cutting planes (cuts) are essential for solving mixed-integer linear programming (MILP) problems, as they tighten the feasible solution space and accelerate the solving process. Modern MILP solvers offer diverse cutting plane separators to generate cuts, enabling users to leverage their potential complementary strengths to tackle problems with different structures. Recent machine learning approaches learn to configure separators based on problem-specific features, selecting effective separators and deactivating ineffective ones to save unnecessary computing time. However, they ignore the dynamics of separator efficacy at different stages of cut generation and struggle to adapt the configurations for the evolving problems after multiple rounds of cut generation. To address this challenge, we propose a novel dyn amic sep arator configuration ( DynSep ) method that models separator configuration in different rounds as a reinforcement learning task, making decisions based on an incremental triplet graph updated by iteratively added cuts. Specifically, we tokenize the incremental subgraphs and utilize a decoder-only Transformer as our policy to autoregressively predict when to halt separation and which separators to activate at each round. Evaluated on synthetic and large-scale real-world MILP problems, DynSep speeds up average solving time by 64% on easy and medium datasets, and reduces primal-dual gap integral within the given time limit by 16% on hard datasets
This work proposes an LLM-guided cutting-plane management framework that removes dependence on domain-specific training data and substantially reduces reliance on expert-crafted configurations.
This paper finds that solutions produced at the early search stage of MILP solvers are often structurally close to the solutions found after full-budget search, and proposes a new solver-informed paradigm that shifts the learning target from variable assignment to early-to-final consistency.
Guanli Li, Chengrui Gao, Chenguang Wang et al.· 0 citations
Column generation (CG) is central to many large-scale optimization algorithms, including branch-price-and-cut methods for vehicle routing problems, but unstable dual solutions can substantially slow its convergence. Existing deep dual-optimal inequalities can reduce this instability by restricting the dual space. Their construction, however, typically relies on problem-specific exchange arguments that are difficult to establish for routing problems with capacity limits, time windows, and other resource constraints. We introduce learned pairwise deep dual-optimal inequalities (L-PDDOIs), a learning framework that predicts pairwise orderings between dual variables and incorporates their primal counterparts directly into the master problem. To construct training labels, the framework samples optimal dual solutions and selects pairwise order relations that hold simultaneously on a sufficiently large common subset of the samples. A classifier then assigns a score to each candidate relation. Because conflicts and redundancies among the predicted relations can impair performance, graph-based postprocessing filters and compresses the candidate set before deployment. We further introduce a recovery procedure that selectively relaxes learned inequalities and provides a certificate when the baseline CG bound has been restored. On the main test sets for the capacitated vehicle routing problem and the vehicle routing problem with time windows, direct deployment of L-PDDOIs reduces the geometric mean root CG time by 89.7% and 93.9%, respectively, while incurring mean bound losses of only 1.3% and 0.5%. The recovery procedure retains corresponding time reductions of 54.8% and 83.1%, respectively, while guaranteeing no loss in the CG bound.
Zhengzhong You, Bo Tang, Haoran Liu et al.· 0 citations
The shortest path problem (SPP) with constraints constitutes a fundamental yet computationally prohibitive NP-hard challenge in operations research and logistics. Traditional optimization algorithms, including both exact and approximate methods, often suffer from prohibitive computational times and severe scalability bottlenecks on large-scale instances. In contrast, emerging Neural Combinatorial Optimization (NCO) approaches offer the potential for rapid inference but frequently fail to guarantee structural feasibility under strict constraints. To bridge this gap, this study introduces E2E_GERL, a novel end-to-end graph-embedded reinforcement learning algorithm for the time-constrained SPP. The problem is reformulated as a structure-aware and resource-aware sequential decision-making process, where a neural graph embedding network, structure2vec, is integrated to capture the long-term structural equivalence of critical graph nodes. In our framework, a ReLU-based Lagrangian penalty is introduced to embed time constraint violation into the learning objective, and n-step Q-learning is employed to effectively overcome delayed path-level consequences. Extensive experiments on synthetic graphs, modified benchmark instances, and a real-world logistics network demonstrate the superiority of the proposed algorithm, E2E_GERL. It achieves better results with substantially lower inference time than classical and NCO baselines, which also validate the potential of integrating NCO into constrained optimization problem algorithms.
Shu-Hao Yang, Min Huang, Shengxiang Yang et al.· Mathematics· 0 citations
Large traveling salesman problem (TSP) instances require a solver to allocate limited computation while preserving the validity of its outputs. Existing neural--operations-research (OR) hybrids predict guidance without requiring learned transitions to satisfy constraints discovered during search. DualCert introduces \emph{constraint-coupled learning}, in which current degree equations and dynamically separated subtour-elimination constraints (SECs) define each learned transition. At each refinement, the degree equations and selected, strictly satisfied SEC equations, with positive slacks, define an iterate-dependent primal-slack Karush--Kuhn--Tucker (KKT) manifold. Repaired dual variables and violated SEC rows define a local cost field. An exact constrained mirror-descent step maps each finite state to a positive state on the same manifold. Where selected rows and deterministic ties remain fixed, implicit differentiation maps parameter perturbations into the manifold tangent space and reuses the forward constraint operator for the local-cost-field derivative. The terminal edge state allocates computation across Held--Karp ascent, candidate-graph edge tests, and tour construction under a fixed budget. Deterministic verification recomputes original costs and accepts only verified candidate-graph lower bounds and edge decisions. On 1,000 held-out TSP1000 instances, DualCert attains a mean tour-cost gap of \(0.0573\%\) from Lin--Kernighan--Helsgaun version 3 (LKH-3) reference tours in \(9.55\) batch-amortized seconds per instance. It returns a verified candidate-graph lower bound for every instance and achieves \(81.46\%\) edge-decision coverage. The mean gap is \(67.1\%\) smaller than the reported NeuroLKH mean gap. Thus, optimization constraints govern learning, while deterministic verification preserves output validity.
Yancheng Song, Yong-Zhi Qi, Wei Qi et al.· 0 citations
Neural Combinatorial Optimization (NCO) has emerged as a promising paradigm for solving Vehicle Routing Problems (VRPs), offering a compelling alternative to traditional heuristics. However, extending NCO to VRPs with complex constraints remains a significant challenge, as existing methods largely rely on hand-crafted feasibility masks, thereby bypassing the core difficulty of intrinsic constraint reasoning. In this paper, we identify a critical phenomenon in constrained VRPs termed the Global Cascading Effect: myopic local decisions can irreversibly lead to the collapse of the future feasible space, resulting in severe constraint violations. We systematically analyze why the prevailing Heavy Encoder Light Decoder (HELD) paradigm, typically trained via reinforcement learning, fails to capture this effect, attributing the failure to three critical couplings: static architectural embeddings, ambiguous trajectory-level feedback, and entangled feature representations. To address these issues, we propose DeCo (Decoupled Constrained Optimization), a streamlined end-to-end framework designed to systematically dismantle these couplings. DeCo leverages a heavy decoder architecture to achieve real-time feasibility perception through step-wise re-embedding, incorporates dense supervised learning for precise credit assignment, and introduces a Decoupled Attention Block with a dual-stream structure to eliminate feature interference. Extensive experiments on complex constrained benchmarks, such as Traveling Salesman Problem with Time Windows (TSPTW) and Draft Limits (TSPDL), demonstrate that DeCo achieves state-of-the-art (SOTA) performance under a pure end-to-end paradigm without any auxiliary masking mechanisms.
Rui Cao, Zhiguang Cao, Yihan Huang et al.· Proceedings of the 32nd ACM...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
