Learning a Generic Value-Selection Heuristic Inside a Constraint Programming Solver

Abstract

Constraint programming is known for being an efficient approach for solving combinatorial problems. Important design choices in a solver are the branching heuristics, which are designed to lead the search to the best solutions in a minimum amount of time. However, developing these heuristics is a time-consuming process that requires problem-specific expertise. This observation has motivated many efforts to use machine learning to automatically learn efficient heuristics without expert intervention. To the best of our knowledge, it is still an open research question. Although several generic variable-selection heuristics are available in the literature, the options for a generic value-selection heuristic are more scarce. In this paper, we propose to tackle this issue by introducing a generic learning procedure that can be used to obtain a value-selection heuristic inside a constraint programming solver. This has been achieved thanks to the combination of a deep Q-learning algorithm, a tailored reward signal, and a heterogeneous graph neural network architecture. Experiments on graph coloring, maximum independent set, and maximum cut problems show that our framework is able to find better solutions close to optimality without requiring a large amounts of backtracks while being generic.

arXiv comment15 pages

References in corpus (6)

• Adam: A Method for Stochastic Optimization
• Dueling Network Architectures for Deep Reinforcement Learning
• Learning to Communicate with Deep Multi-Agent Reinforcement Learning
• Multi-agent Reinforcement Learning in Sequential Social Dilemmas
• The Complexity of Decentralized Control of Markov Decision Processes
• Investigating Recurrence and Eligibility Traces in Deep Q-Networks

Cited by in corpus (92)

• Is Independent Learning All You Need in the StarCraft Multi-Agent Challenge?
• Theory of Mind for Multi-Agent Collaboration via Large Language Models
• A Survey on Reinforcement Learning in Aviation Applications
• The Multi-Agent Reinforcement Learning in MalmÖ (MARLÖ) Competition
• Multi-Agent Common Knowledge Reinforcement Learning
• A Bayesian Framework for Digital Twin-Based Control, Monitoring, and Data Collection in Wireless Systems
• Simplified Action Decoder for Deep Multi-Agent Reinforcement Learning
• The AI Economist: Improving Equality and Productivity with AI-Driven Tax Policies
• Online Multi-agent Reinforcement Learning for Decentralized Inverter-based Volt-VAR Control
• Multi-Agent Reinforcement Learning Based on Representational Communication for Large-Scale Traffic Signal Control
• Rethinking the Implementation Tricks and Monotonicity Constraint in Cooperative Multi-Agent Reinforcement Learning
• UPDeT: Universal Multi-agent Reinforcement Learning via Policy Decoupling with Transformers
• Optimizing Online Matching for Ride-Sourcing Services with Multi-Agent Deep Reinforcement Learning
• Multi-Agent Reinforcement Learning: A Report on Challenges and Approaches
• Spatial Intention Maps for Multi-Agent Mobile Manipulation
• Succinct and Robust Multi-Agent Communication With Temporal Message Control
• Integrating independent and centralized multi-agent reinforcement learning for traffic signal network optimization
• Shared Experience Actor-Critic for Multi-Agent Reinforcement Learning
• Reward Design in Cooperative Multi-agent Reinforcement Learning for Packet Routing
• Multi-Agent Collaboration via Reward Attribution Decomposition
• Value Functions Factorization with Latent State Information Sharing in Decentralized Multi-Agent Policy Gradients
• Towards Cooperation in Sequential Prisoner's Dilemmas: a Deep Multiagent Reinforcement Learning Approach
• RMIX: Learning Risk-Sensitive Policies for Cooperative Reinforcement Learning Agents
• Benchmarking Multi-Agent Deep Reinforcement Learning Algorithms in Cooperative Tasks
• Learning to Collaborate: Multi-Scenario Ranking via Multi-Agent Reinforcement Learning
• Applications of Multi-Agent Reinforcement Learning in Future Internet: A Comprehensive Survey
• V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL
• Cooperative Multi-Agent Transfer Learning with Level-Adaptive Credit Assignment
• Efficient Collaborative Multi-Agent Deep Reinforcement Learning for Large-Scale Fleet Management
• QR-MIX: Distributional Value Function Factorisation for Cooperative Multi-Agent Reinforcement Learning
• Stratospheric Aerosol Injection as a Deep Reinforcement Learning Problem
• Distributed Multi-agent Meta Learning for Trajectory Design in Wireless Drone Networks
• Graph Exploration for Effective Multi-agent Q-Learning
• Continuous Coordination As a Realistic Scenario for Lifelong Learning
• UneVEn: Universal Value Exploration for Multi-Agent Reinforcement Learning
• A Maximum Mutual Information Framework for Multi-Agent Reinforcement Learning
• Multi-Agent Determinantal Q-Learning
• Coach-Player Multi-Agent Reinforcement Learning for Dynamic Team Composition
• On the Use and Misuse of Absorbing States in Multi-agent Reinforcement Learning
• Bi-level Off-policy Reinforcement Learning for Volt/VAR Control Involving Continuous and Discrete Devices
• Event-Triggered Multi-agent Reinforcement Learning with Communication under Limited-bandwidth Constraint
• Value-Decomposition Multi-Agent Actor-Critics
• Efficient Ridesharing Dispatch Using Multi-Agent Reinforcement Learning
• Independent Natural Policy Gradient Always Converges in Markov Potential Games
• Agent Modelling under Partial Observability for Deep Reinforcement Learning
• Which Heroes to Pick? Learning to Draft in MOBA Games with Neural Networks and Tree Search
• Coordination in Adversarial Sequential Team Games via Multi-Agent Deep Reinforcement Learning
• Multi-Agent Coordination in Adversarial Environments through Signal Mediated Strategies
• Permutation Invariant Policy Optimization for Mean-Field Multi-Agent Reinforcement Learning: A Principled Approach
• LINDA: Multi-Agent Local Information Decomposition for Awareness of Teammates
• Attentional Policies for Cross-Context Multi-Agent Reinforcement Learning
• Dimension-Free Rates for Natural Policy Gradient in Multi-Agent Reinforcement Learning
• Mean-Field Multi-Agent Reinforcement Learning: A Decentralized Network Approach
• Correcting Experience Replay for Multi-Agent Communication
• Inter-Level Cooperation in Hierarchical Reinforcement Learning
• Centralized Model and Exploration Policy for Multi-Agent RL
• Learning to Communicate with Reinforcement Learning for an Adaptive Traffic Control System
• Human and Multi-Agent collaboration in a human-MARL teaming framework
• Using reinforcement learning to minimize taxi idle times
• Learning Multi-Robot Decentralized Macro-Action-Based Policies via a Centralized Q-Net
• HAVEN: Hierarchical Cooperative Multi-Agent Reinforcement Learning with Dual Coordination Mechanism
• Causal Mean Field Multi-Agent Reinforcement Learning
• Off-Belief Learning
• Robust Temporal Difference Learning for Critical Domains
• Vehicular Network Slicing for Reliable Access and Deadline-Constrained Data Offloading: A Multi-Agent On-Device Learning Approach
• Distributed Policy Iteration for Scalable Approximation of Cooperative Multi-Agent Policies
• Learning to Represent Action Values as a Hypergraph on the Action Vertices
• Learning Complex Multi-Agent Policies in Presence of an Adversary
• Mimicking Evolution with Reinforcement Learning
• Embedding Contextual Information through Reward Shaping in Multi-Agent Learning: A Case Study from Google Football
• MMD-MIX: Value Function Factorisation with Maximum Mean Discrepancy for Cooperative Multi-Agent Reinforcement Learning
• Decentralized Multi-Agents by Imitation of a Centralized Controller
• Inducing Cooperation via Team Regret Minimization based Multi-Agent Deep Reinforcement Learning
• Scaling Up Multiagent Reinforcement Learning for Robotic Systems: Learn an Adaptive Sparse Communication Graph
• Structured Diversification Emergence via Reinforced Organization Control and Hierarchical Consensus Learning
• Independent Reinforcement Learning for Weakly Cooperative Multiagent Traffic Control Problem
• Neural Auto-Curricula
• DSDF: An approach to handle stochastic agents in collaborative multi-agent reinforcement learning
• Augmenting the action space with conventions to improve multi-agent cooperation in Hanabi
• Cooperative and Asynchronous Transformer-based Mission Planning for Heterogeneous Teams of Mobile Robots
• Learning Cooperation and Online Planning Through Simulation and Graph Convolutional Network
• Evaluating Generalization and Transfer Capacity of Multi-Agent Reinforcement Learning Across Variable Number of Agents
• DeCOM: Decomposed Policy for Constrained Cooperative Multi-Agent Reinforcement Learning
• Stateless actor-critic for instance segmentation with high-level priors
• Learning to Coordinate via Multiple Graph Neural Networks
• Two-stage training algorithm for AI robot soccer
• Growing Action Spaces
• BGC: Multi-Agent Group Belief with Graph Clustering
• Logical Team Q-learning: An approach towards factored policies in cooperative MARL
• Iterative Update and Unified Representation for Multi-Agent Reinforcement Learning
• Agent Probing Interaction Policies
• Influence-Based Reinforcement Learning for Intrinsically-Motivated Agents