HyP-ASO: A Hybrid Policy-based Adaptive Search Optimization Framework for Large-Scale Integer Linear Programs

• URL: http://arxiv.org/abs/2509.15828v2
• Date: Mon, 22 Sep 2025 02:59:50 GMT
• Title: HyP-ASO: A Hybrid Policy-based Adaptive Search Optimization Framework for Large-Scale Integer Linear Programs
• Authors: Ning Xu, Junkai Zhang, Yang Wu, Huigen Ye, Hua Xu, Huiling Xu, Yifan Zhang,
• Abstract summary: HyP-ASO is a hybrid policy-based adaptive search optimization framework that combines a customized formula with deep Reinforcement Learning (RL)<n>Experiments demonstrate that HyP-ASO significantly outperforms existing LNS-based approaches for large-scale ILPs.<n>Additional experiments show it is lightweight and highly scalable, making it well-suited for solving large-scale ILPs.
• Score: 29.446016007712114
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Directly solving large-scale Integer Linear Programs (ILPs) using traditional solvers is slow due to their NP-hard nature. While recent frameworks based on Large Neighborhood Search (LNS) can accelerate the solving process, their performance is often constrained by the difficulty in generating sufficiently effective neighborhoods. To address this challenge, we propose HyP-ASO, a hybrid policy-based adaptive search optimization framework that combines a customized formula with deep Reinforcement Learning (RL). The formula leverages feasible solutions to calculate the selection probabilities for each variable in the neighborhood generation process, and the RL policy network predicts the neighborhood size. Extensive experiments demonstrate that HyP-ASO significantly outperforms existing LNS-based approaches for large-scale ILPs. Additional experiments show it is lightweight and highly scalable, making it well-suited for solving large-scale ILPs.

Related papers

• TL-GRPO: Turn-Level RL for Reasoning-Guided Iterative Optimization [97.18886232580131]
  Large language models have demonstrated strong reasoning capabilities in complex tasks through tool integration.<n>We propose Turn-Level GRPO, a lightweight RL algorithm that performs turn-level group sampling for fine-grained optimization.
  arXiv  Detail & Related papers  (2026-01-23T06:21:33Z)
• SPL-LNS: Sampling-Enhanced Large Neighborhood Search for Solving Integer Linear Programs [59.91461374628034]
  Large Neighborhood Search (LNS) is a common in optimization that iteratively searches over a large neighborhood of the current solution for a better one.<n>This paper introduces SPL-LNS, a sampling-enhanced neural LNS solver that leverages locally-informed proposals to escape local optima.
  arXiv  Detail & Related papers  (2025-08-22T07:49:33Z)
• Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
  Reinforcement Learning (RL) has emerged as a powerful tool for neural optimization, enabling models learns that solve complex problems without requiring expert knowledge.<n>Despite significant progress, existing RL approaches face challenges such as diminishing reward signals and inefficient exploration in vast action spaces.<n>We propose Preference Optimization, a novel method that transforms quantitative reward signals into qualitative preference signals via statistical comparison modeling.
  arXiv  Detail & Related papers  (2025-05-13T16:47:00Z)
• Learning Reward and Policy Jointly from Demonstration and Preference Improves Alignment [58.049113055986375]
  We develop a single stage approach named Alignment with Integrated Human Feedback (AIHF) to train reward models and the policy.<n>The proposed approach admits a suite of efficient algorithms, which can easily reduce to, and leverage, popular alignment algorithms.<n>We demonstrate the efficiency of the proposed solutions with extensive experiments involving alignment problems in LLMs and robotic control problems in MuJoCo.
  arXiv  Detail & Related papers  (2024-06-11T01:20:53Z)
• Large Neighborhood Prioritized Search for Combinatorial Optimization with Answer Set Programming [3.759879849096294]
  We propose Large Neighborhood Prioritized Search (LNPS) for solving optimization problems in Answer Set Programming (ASP) LNPS is a metaheuristic that starts with an initial solution and then iteratively tries to find better solutions by alternately destroying and prioritized searching for a current solution. We present an implementation of LNPS based on ASP. The resulting heulingo solver demonstrates that LNPS can significantly enhance the solving performance of ASP for optimization.
  arXiv  Detail & Related papers  (2024-05-18T14:37:43Z)
• Entropy-Regularized Token-Level Policy Optimization for Language Agent Reinforcement [67.1393112206885]
  Large Language Models (LLMs) have shown promise as intelligent agents in interactive decision-making tasks. We introduce Entropy-Regularized Token-level Policy Optimization (ETPO), an entropy-augmented RL method tailored for optimizing LLMs at the token level. We assess the effectiveness of ETPO within a simulated environment that models data science code generation as a series of multi-step interactive tasks.
  arXiv  Detail & Related papers  (2024-02-09T07:45:26Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• Reinforcement Learning Methods for Wordle: A POMDP/Adaptive Control Approach [0.3093890460224435]
  We address the solution of the popular Wordle puzzle, using new reinforcement learning methods. For the Wordle puzzle, they yield on-line solution strategies that are very close to optimal at relatively modest computational cost.
  arXiv  Detail & Related papers  (2022-11-15T03:46:41Z)
• Online Control of Adaptive Large Neighborhood Search using Deep Reinforcement Learning [4.374837991804085]
  We introduce a Deep Reinforcement Learning based approach called DR-ALNS that selects operators, adjusts parameters, and controls the acceptance criterion throughout the search. We evaluate the proposed method on a problem with orienteering weights and time windows, as presented in an IJCAI competition. The results show that our approach outperforms vanilla ALNS, ALNS tuned with Bayesian optimization, and two state-of-the-art DRL approaches.
  arXiv  Detail & Related papers  (2022-11-01T21:33:46Z)
• Simulation-guided Beam Search for Neural Combinatorial Optimization [13.072343634530883]
  We propose simulation-guided beam search (SGBS) for neural optimization problems. We hybridize SGBS with efficient active search (EAS), where SGBS enhances the quality of solutions backpropagated in EAS. We evaluate our methods on well-known CO benchmarks and show that SGBS significantly improves the quality of the solutions found under reasonable assumptions.
  arXiv  Detail & Related papers  (2022-07-13T13:34:35Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.