Towards Sequence-to-Sequence Reinforcement Learning for Constraint Solving with Constraint-Based Local Search

Helge SpiekerAAAI 2019 · DOI

Abstract

This paper introduces a hybrid framework for solving constraint optimization problems (COPs) by integrating Sequence-to-Sequence (S2S) Reinforcement Learning (RL) with Constraint-Based Local Search (CBLS). Traditional Constraint Programming (CP) solvers often struggle with computational efficiency in large search spaces, while supervised machine learning models are limited by the need for expensive optimal labels. Our approach utilizes an RL agent to generate initial solution candidates, which are subsequently refined by a CBLS component. Experimental results on the Maximum Increasing with Limits (MIWL) problem demonstrate that this hybrid system achieves high feasibility rates and significantly reduces the computational burden on traditional solvers without requiring pre-computed optimal solutions.

Introduction

Constraint Programming (CP) is essential for solving complex combinatorial problems such as scheduling and routing. However, dedicated solvers are often computationally expensive when traversing vast search spaces. While machine learning (ML) offers a potential shortcut via fast inference, its application to CP is hindered by the "supervised trap": generating a massive corpus of optimal solutions for training is costly, and models often merely mimic specific solver heuristics rather than discovering better strategies.

To address these challenges, we propose a method that learns problem-solving strategies using only scalar rewards—representing solution quality or legality—rather than explicit "correct" answers. By shifting the heavy lifting from the inference phase to the training phase, we aim to create a system capable of generating high-quality solutions almost instantaneously.

Methodology

The proposed hybrid framework bridges the gap between neural networks and traditional constraint solvers. The architecture consists of two primary components: an RL Agent and a Constraint-Based Local Search (CBLS) solver.

The hybrid RL-CBLS framework for constraint solving.

The RL Agent

We employ an Advantage Actor-Critic (A2C) architecture designed for Sequence-to-Sequence tasks. The agent takes variable-length problem parameters as input and outputs a sequence of variable assignments. Integers are treated as categorical data and mapped to dense embeddings. To manage the search space, we apply domain knowledge to "tighten" variable domains during preprocessing, which prunes the agent's action space and stabilizes learning.

The Hybrid Loop

Instead of relying solely on the neural network for a final answer, the predicted "solution candidate" is passed to the CBLS solver. The CBLS component performs three critical functions:

  1. Verification: Checks the candidate for constraint violations.
  2. Repair: Fixes violations to achieve feasibility.
  3. Optimization: Spends additional time improving the objective value if necessary.

The agent is trained using a scalar reward function. Unfeasible solutions receive negative rewards based on the number of violations, while feasible solutions receive positive rewards based on the objective value. This feedback loop allows the agent to explore the search space independently and discover novel strategies.

Evaluation

The framework was evaluated on a synthetic constraint problem: Maximum Increasing with Limits (MIWL). The task involves finding the maximum sum of a strictly increasing sequence of integers, where each element is bounded by a specific limit.

Experimental Setup

The model was trained on 150,000 random instances with sequences up to 250 elements long. We compared the performance of an agent trained solely with supervised pre-training against one further refined by RL.

Key Results

The experiments demonstrated a significant "learning curve" during the transition from supervised learning to RL:

  • Feasibility Boost: After 10 epochs of supervised pre-training, the agent produced feasible solutions only 32% of the time. After just one epoch of RL, feasibility jumped to 88%, eventually reaching a plateau at 92%.
  • Error Reduction: The "worst-case" performance improved dramatically. Initial candidates from the supervised model had up to 88 violations; after RL convergence, the worst candidates had only 10 violations, making them significantly easier for the CBLS component to repair.
  • Convergence: Both the number of feasible solutions and the total reward converged steadily over 20 epochs, validating the stability of the A2C approach for S2S constraint solving.

Discussion and Future Work

Our results suggest that RL can effectively serve as a "warm start" for traditional solvers. By providing near-feasible, high-quality starting points, the RL agent drastically reduces the workload for the local search component.

However, limitations remain. The MIWL problem, while a successful proof-of-concept, is relatively simple. Future research will focus on testing the framework on complex benchmarks like job-shop scheduling and exploring modern architectures like Transformers or Graph Neural Networks (GNNs) to better capture complex constraint relationships. By breaking the dependence on supervised labels and leveraging the strengths of both neural networks and local search, this hybrid approach paves the way for more efficient and flexible constraint solving.

Summary updated

BibTeX
@inproceedings{spieker2019towards,
  author = {Helge Spieker},
  title = {{Towards Sequence-to-Sequence Reinforcement Learning for Constraint Solving with Constraint-Based Local Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.330110037},
}
Figure