PaperlayerView exact revision on arXiv

Source-linked AI summary

Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization

Quentin Cappart, Thierry Moisan, Louis-Martin Rousseau, Isabeau Prémont-Schwarz, Andre Cire

arXiv:2006.01610v1cs.AIcs.LG

TL;DR

Combinatorial optimization becomes difficult as the number of possibilities grows exponentially, while existing DRL and CP approaches have complementary limitations. The paper bridges DRL and CP through dynamic programming and reports competitive performance on two challenging problems. Its main practical limitation is the cost of repeatedly invoking neural-network predictions inside the solver.

  • Problem

    Existing DRL methods often target specific problems and provide approximate solutions without systematic optimality guarantees, while CP search depends critically on branching decisions.

  • Method

    The framework encodes one dynamic-programming model as both an RL environment and a CP model, using learned branching strategies to guide complete CP search.

  • Results

    The framework is competitive with standard approaches and industrial solvers on TSPTW and 4-moments portfolio optimization for instances up to 100 variables.

  • Takeaways & Limitations

    The results support a generic and complete hybrid solver for combinatorial optimization problems that can be modeled using dynamic programming.

  • Takeaways & Limitations

    Neural-network prediction is expensive when called repeatedly inside the solver, creating a bottleneck for larger instances.

Abstract

from arXiv · show

Combinatorial optimization has found applications in numerous fields, from aerospace to transportation planning and economics. The goal is to find an optimal solution among a finite set of possibilities. The well-known challenge one faces with combinatorial optimization is the state-space explosion problem: the number of possibilities grows exponentially with the problem size, which makes solving intractable for large problems. In the last years, deep reinforcement learning (DRL) has shown its promise for designing good heuristics dedicated to solve NP-hard combinatorial optimization problems. However, current approaches have two shortcomings: (1) they mainly focus on the standard travelling salesman problem and they cannot be easily extended to other problems, and (2) they only provide an approximate solution with no systematic ways to improve it or to prove optimality. In another context, constraint programming (CP) is a generic tool to solve combinatorial optimization problems. Based on a complete search procedure, it will always find the optimal solution if we allow an execution time large enough. A critical design choice, that makes CP non-trivial to use in practice, is the branching decision, directing how the search space is explored. In this work, we propose a general and hybrid approach, based on DRL and CP, for solving combinatorial optimization problems. The core of our approach is based on a dynamic programming formulation, that acts as a bridge between both techniques. We experimentally show that our solver is efficient to solve two challenging problems: the traveling salesman problem with time windows, and the 4-moments portfolio optimization problem. Results obtained show that the framework introduced outperforms the stand-alone RL and CP solutions, while being competitive with industrial solvers.

1 Introduction

The paper combines deep reinforcement learning and constraint programming to address complementary weaknesses in combinatorial optimization: efficient approximate search versus complete optimization. Dynamic programming provides the shared representation connecting both techniques.

  • Exact optimization: Exact algorithms can find optimal solutions but may become prohibitive as execution time grows exponentially with instance size.Constraint programming is generic across many combinatorial optimization problems, but its branching strategy strongly affects search.
  • Complementary strengths: Heuristic methods compute solutions efficiently but cannot prove optimality, whereas complete methods retain that guarantee at potentially prohibitive cost.This motivates combining the strengths of exact search and learned decision-making.
  • Learning-based heuristics: DRL can efficiently produce high-quality approximate solutions, but typically requires known instance distributions and substantial training data.Existing learning approaches are also concentrated on specific problem families, especially the traveling salesman problem.
  • Dynamic programming bridge: Dynamic programming links reinforcement learning and constraint programming through recursive subproblems, while its own state-space growth can become infeasible.The number of generated subproblems may grow exponentially, creating a curse of dimensionality.
  • Contribution: The proposed solver encodes dynamic-programming models in both an RL environment and a CP model, then learns branching strategies for CP search.It uses DQN and PPO, integrates learned strategies with three CP search procedures, and evaluates TSPTW and 4-moments portfolio optimization.
  • Scope: The framework targets dynamic-programming formulations because they do not generally fit standard integer-programming techniques without assumptions such as linearity or convexity.The paper evaluates the resulting hybrid solving process on two case studies.

2 A Unifying Representation Combining Learning and Searching

The framework uses one dynamic-programming representation to support both reinforcement-learning training and constraint-programming search. It combines learned action selection with CP constraints, validity checks, dominance pruning, and optimization.

  • Architecture: The architecture has learning and solving phases connected by a unifying representation that serves as a bridge between them.The framework contains adapted known algorithms alongside the paper’s original components.
  • Dynamic programming model: Dynamic programming decomposes a combinatorial optimization problem into linked subproblems solved recursively through state transitions and rewards.The optimal solution is recovered by backtracking values after computing the initial state value.
  • Dynamic programming model: DP can suffer from the curse of dimensionality because the state-action space may remain too large even after dominated actions are pruned.Dominated actions are either strictly worse than alternatives or unable to lead to feasible solutions.
  • RL encoding: The RL encoding pairs each problem instance with a dynamic DP state and restricts actions to those consistent with validity and dominance conditions.Transitions reproduce the DP transition function, while the reward design prioritizes reaching feasible solutions before maximizing reward.
  • Learning: DQN and PPO learn branching information from randomly generated instances sampled from a distribution similar to the target problems.The neural architecture is designed for variable-sized instances and invariance to input permutations.
  • CP encoding: The CP encoding separates auxiliary state variables from decision variables, with search performed only on the decision variables.Constraints enforce initial states, valid transitions, and removal of dominated actions.
  • CP encoding: The CP objective maximizes the accumulated transition rewards across the stages, using the same DP formulation that defines the RL environment.This consistency allows learned knowledge to guide CP search.

3 Experimental Results

Experiments compare the hybrid DRL–CP framework with CP, stand-alone RL, and industrial solvers on TSPTW and portfolio optimization. The hybrid methods generally combine effective solution discovery with optimality proving, with performance varying by problem size and variant.

  • Experimental setup: The experiments compare three learning-based CP searches with CP, stand-alone RL, and industrial solvers on TSPTW and portfolio optimization.The evaluated procedures are BaB-DQN, ILDS-DQN, and RBS-PPO.
  • TSPTW: On TSPTW, hybrid approaches outperform OR-Tools, CP-model, and DQN, while remaining effective for both finding solutions and proving optimality as instances grow.CP-nearest is better for proving optimality and PPO for discovering feasible solutions, but both face greater difficulty on larger instances.
  • TSPTW: DQN-based hybrid searches give the best TSPTW results for both solution finding and optimality proving.This comparison concerns the hybrid approaches.
  • TSPTW: Caching reduces BaB-DQN value-selection time from 34 milliseconds to 0.16 milliseconds for 100-city instances, though CP-nearest takes 0.004 milliseconds.The hybrid approach still achieves the best results despite higher heuristic cost than CP-nearest.
  • PORT: For PORT, BaB-DQN⋆, ILDS-DQN⋆, and CP-model perform best on the smallest continuous instances, but only BaB-DQN⋆ proves optimality for all instances.For larger continuous instances, non-linear solvers perform best and RBS-PPO⋆ closely follows.
  • PORT: In the discrete PORT variant, ILDS-DQN⋆ and BaB-DQN⋆ perform best on smaller instances, while RBS-PPO⋆ performs best on larger ones.The hybrid approaches do not rely on the continuity assumptions affecting non-linear solvers.

4 Discussion and Limitations

The discussion places the approach among machine-learning-guided optimization methods and reports improved solution quality and runtime in most situations. It also identifies neural-network inference and language interoperability as efficiency bottlenecks.

  • Discussion: The approach belongs to the class of machine learning alongside optimization algorithms, alongside earlier methods such as imitation-learning-augmented branch-and-bound.
  • Discussion: In most situations, the approach obtains more and better solutions with smaller execution time than the other methods.
  • Limitations: Neural-network predictions are costly inside the solver because they are called repeatedly, making inference a bottleneck for larger instances.Caching, knowledge distillation, and more compact networks are proposed as possible remedies.
  • Limitations: The Python–C++ Pybind11 binding introduces additional inefficiency, motivating a possible single-language implementation.

5 Conclusion

The paper introduces a hybrid DRL–CP framework that encodes dynamic-programming models into both reinforcement-learning and constraint-programming formulations. Experiments on TSPTW and 4-moments portfolio optimization find it competitive with standard approaches and industrial solvers up to 100 variables.

  • Conclusion: The framework combines deep reinforcement learning and constraint programming, using a dynamic-programming encoding as the interface between them.
  • Conclusion: The encoding expresses a dynamic-programming model as both a reinforcement-learning environment and a constraint-programming model.
  • Conclusion: Experiments on TSPTW and 4-moments portfolio optimization show competitiveness with standard approaches and industrial solvers for instances up to 100 variables.
  • Conclusion: The results suggest the framework is a promising avenue for solving challenging combinatorial optimization problems.

A Technical Background on Reinforcement Learning

The background introduces reinforcement learning as sequential decision-making over states and actions, with returns evaluated through value functions. It distinguishes value-based and policy-based methods, then describes DQN and PPO as the algorithms used in the paper.

  • RL formulation: A reinforcement-learning environment is represented by states, actions, transitions, and rewards, with a policy selecting actions from states.
  • RL formulation: The return sums rewards across subsequent decisions without discounting when all decisions have equal importance in non-temporal COPs.
  • Value functions: Action-value and state-value functions quantify action quality and state return, while the optimal policy maximizes final return.
  • RL methods: Value-based methods learn action values, whereas policy-based methods learn the policy directly.
  • DQN and PPO: DQN approximates the action-value function with a neural network and selects actions using a greedy policy.
  • DQN and PPO: PPO learns a policy that maximizes expected initial-state return while limiting excessively large policy updates during gradient ascent.

B Technical Background on Constraint Programming

Constraint programming combines complete search with propagation, branching heuristics, and restart strategies to solve combinatorial optimization problems. The proposed hybrid procedures use learned value or policy guidance while retaining CP's complete-search framework.

  • Constraint-programming search: CP can prove optimality through complete search, but exponential search-tree growth makes large problems difficult.Propagation reduces possible choices, while branch-and-bound tightens the objective after feasible solutions are found.
  • Constraint-programming search: Variable and value-selection heuristics determine which branches CP explores first, making branching a critical design choice.Depth-first branch-and-bound may reconsider choices late, whereas alternative strategies can alter exploration behavior.
  • Learned search strategies: ILDS restricts deviations from heuristic choices while progressively allowing more discrepancies, combining focused exploration with reconsideration.It is useful when the value-selection heuristic is expected to identify promising choices.
  • Learned search strategies: ILDS-DQN encodes a DP-based problem as CP, selects the first unassigned variable, and uses a trained Q-function to choose its value.The procedure repeats searches with increasing discrepancy thresholds and retains CP mechanisms such as propagation and backtracking.
  • Learned search strategies: RBS-PPO combines restart-based search, Luby thresholds, and a policy-gradient agent whose softmax-guided choices introduce controlled exploration.The procedure uses repeated BaB searches and caches state-policy decisions across the search process.

E Travelling Salesman Problem with Time Windows (TSPTW)

TSPTW extends the travelling salesman problem by requiring every customer to be visited within a time window while minimizing total travel distance. These temporal constraints make it harder to solve in practice despite a smaller search space than standard TSP.

  • Problem definition: TSPTW seeks a minimum-cost Hamiltonian tour from and back to a depot while visiting each customer exactly once.Customers have locations and service time windows, and travel time is determined by pairwise distances.
  • Problem definition: Visits before a window opens require waiting, whereas servicing after its closing time makes the solution infeasible.The depot has no associated time window.
  • Problem definition: Time constraints make TSPTW more difficult to solve in practice, although its search space is smaller than standard TSP.

E.1 Dynamic Programming Model

The TSPTW dynamic-programming model represents partial tours through remaining customers, the last serviced customer, and current time. Actions update these state components and are allowed only when customer and time-window constraints hold.

  • State and actions: The TSPTW DP model has n + 1 stages, with states tracking remaining customers, the last serviced customer, and current time.The final stage corresponds to the completed solution.
  • State and actions: Servicing a customer removes it from the remaining set, makes it the last visited customer, and updates the current time.The action reward is the negative travel distance, with an additional return-to-depot penalty.
  • Validity conditions: An action is valid only when the customer remains unvisited and can be reached within its time window.The initial state starts at the depot at time 0 with all non-depot customers unvisited.
  • Instance generation: Random instances sample customer coordinates on a 100 × 100 grid and use rounded Euclidean distances as travel times.Time windows are generated to preserve at least one feasible solution.

E.3 Neural Architecture

The TSPTW neural architecture uses graph attention to represent the fully connected customer graph before producing action-related outputs for learned search. Experimental setup details include tuned hyperparameters and several comparison solvers.

  • Neural architecture: A graph attention network produces node embeddings from the fully connected customer graph, followed by fully connected layers.For DQN, the final output dimension corresponds to the number of possible customer-selection actions.
  • Neural architecture: Hyperparameters are selected by grid search on 20-city instances and reused for larger instances, except for the softmax temperature.The temperature is tuned separately for each instance size.
  • Baselines: The comparisons include OR-Tools, standard DQN, PPO with beam-search decoding, a CP model solved by Gecode, and a nearest-customer heuristic.The CP formulation uses global constraints including allDifferent, circuit, and increasing.
  • Portfolio case study: The portfolio formulation is a discrete non-linear, non-convex optimization problem that is difficult for integer and general non-linear solvers to solve with optimality guarantees.The considered discrete variant applies floor functions to the roots, making all coefficients integers and potentially worsening local-optimum behavior.
  • Portfolio case study: The portfolio DP processes investments sequentially, using binary inclusion decisions and a state equal to current portfolio cost under a budget constraint.The recurrence initializes cost at zero and prevents the budget from being exceeded.

F.2 Instance Generation

The portfolio instances are generated by sampling investment costs, returns, and financial terms, with the budget fixed relative to total costs and selected λ parameters.

  • Investment costs b_i and expected returns μ_i are sampled uniformly from 0 to 100.
  • The maximum budget B is set to 0.5 × the sum of all investment costs.
  • Financial terms σ_i, γ_i, and κ_i are sampled uniformly from 0 to each investment's expected return μ_i.
  • The instance-generation parameters fix λ_i = 1 and λ_2 = λ_3 = λ_4 = 5.

F.3 Neural Architecture

The portfolio model uses a permutation-invariant SetTransformer architecture because the problem lacks graph structure, with item embeddings and dynamic state features supplied to RL models.

  • The portfolio architecture uses SetTransformer because the problem has no graph structure and requires permutation-invariant processing.Permuting the items produces the same output.
  • SetTransformer first embeds each item, then fully connected layers produce the output; the architecture varies slightly between DQN and PPO.Implementation uses PyTorch and reuses the SetTransformer code from [37].
  • Each item is represented by 5 static and 4 dynamic features describing the investment and its current DP state.Dynamic features indicate whether an investment was considered, is current, would exceed the budget, and the remaining budget.
  • The neural architecture uses an embedding dimension of 40 reused from the initial SetTransformer implementation.
  • The section reports PORT hyper-parameters in Table 4 and compares the model against Knitro, APOPT, DQN, PPO, and a CP formulation.Knitro and APOPT use default solver parameters; PPO uses beam-search decoding of size 64, and the CP model is solved with Gecode.
Loading 2006.01610v1…