Learning Heuristics for Minimum Latency Problem with RL and GNN

On the Runtime Analysis of Reinforcement Learning Hyper-Heuristics

Selection Hyper-heuristics (HHs) automate algorithmic design by selecting from a set of low-level heuristics which one to apply at each stage of the optimisation process. Several impressive results have been recently rigorously proven regarding the performance of selection hyper-heuristics (HHs) for standard benchmark functions. However, the learning mechanisms employed by these HHs are considerably simplified compared to the machine learning techniques typically used in real world applications. In this paper we analyse a Reinforcement Learning Hyper-heuristic (RLHH) from the literature. The only previous result available proved that for a wide range of parameter settings, RLHH does not learn to select heuristics appropriately for the standard LeadingOnes benchmark function. In this paper, we rigorously prove that with appropriate parameter values RLHH equipped with two random local search operators, RLS_1 and RLS_2 optimises the LeadingOnes benchmark function in the best possible expected runtime achievable with the two operators up to lower order terms. Experiments show that for realistic problem sizes it is faster than the Generalised Random Gradient HH which was previously proven to also have optimal expected runtime up to lower order terms.

Reinforcement Learning for Code Optimization

This work makes execution time learnable through three stages: how code is tested, by building DMC-Optim with large optimization tests and a calibrated sandbox; how speed is turned into reward, by composing correctness and speed in the RL environment and using an offline simulator to predict the most promising configurations.

SEER: Supervised Learning to Control Energetic Reasoning

One of the main strengths of Constraint Programming is the ability to reduce the search space via propagation. However, propagation is a double-edged sword, with more pruning power coming at the price of larger computation time. For each problem constraint, the best propagator depends on the specific instance and may change at search time. In the literature, Machine Learning (ML) techniques and activity-based heuristics have been applied respectively for choosing (statically) the propagators for a batch of problems and to adapt (dynamically) the propagation strength. We propose to merge those efforts by using an oracle function, obtained via ML, to decide whether to run complex propagators for a target constraint. A combination of design choices makes the approach flexible and easy to embed in state-of-the-art solvers. In this paper, we focus on investigating the feasibility of building an oracle for the Energetic Reasoning propagator. Our experiments show that high prediction accuracy can be obtained, provide suggestions for classification features, and highlight important issues to address when building such an oracle.

Learning Early-to-Final Solution Consistency for MILP Acceleration

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.

RLDMGO: a reinforcement learning-driven hybrid framework for complex optimization problems

Deep Reinforcement Learning for Combinatorial Optimization Problems: A Challenge-Driven Methodology and Systematic Review

Combinatorial optimization problems (COPs) offer essential mathematical frameworks and algorithmic foundations for modeling complex real-world decision-making tasks. Recent advances in deep reinforcement learning (DRL) have shown promising results for solving COPs, offering the potential to reduce dependence on domain-specific expertise and improve generalization across problem instances. These developments have accelerated research in the field and spurred the emergence of numerous innovative methods. Nevertheless, significant theoretical and practical challenges remain. A systematic synthesis of these challenges and their corresponding solutions is critical to guiding the future development of DRL-based approaches. To address this need, we propose a unified challenge-driven framework consisting of four core components: an environment, a state–action–reward mechanism, a solver, and an evaluation module. Using this framework, we conduct a systematic review of approximately 300 recent studies, mapping the evolution of challenges and the progress made in addressing them. We provide a multidimensional analysis of solver designs, training paradigms, and state-of-the-art (SOTA) performance, while documenting publicly available code repositories. Finally, we identify key open problems within the proposed framework to stimulate novel research directions.