License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2023.25
URN: urn:nbn:de:0030-drops-190625
URL: https://drops.dagstuhl.de/opus/volltexte/2023/19062/
Go to the corresponding LIPIcs Volume Portal


Marty, Tom ; Fran├žois, Tristan ; Tessier, Pierre ; Gautier, Louis ; Rousseau, Louis-Martin ; Cappart, Quentin

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

pdf-format:
LIPIcs-CP-2023-25.pdf (2 MB)


Abstract

Constraint programming is known for being an efficient approach to solving combinatorial problems. Important design choices in a solver are the branching heuristics, 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. Although several generic variable-selection heuristics are available in the literature, the options for value-selection heuristics are more scarce. 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. Experiments on graph coloring, maximum independent set, and maximum cut problems show that this framework competes with the well-known impact-based and activity-based search heuristics and can find solutions close to optimality without requiring a large number of backtracks.

BibTeX - Entry

@InProceedings{marty_et_al:LIPIcs.CP.2023.25,
  author =	{Marty, Tom and Fran\c{c}ois, Tristan and Tessier, Pierre and Gautier, Louis and Rousseau, Louis-Martin and Cappart, Quentin},
  title =	{{Learning a Generic Value-Selection Heuristic Inside a Constraint Programming Solver}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{25:1--25:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19062},
  URN =		{urn:nbn:de:0030-drops-190625},
  doi =		{10.4230/LIPIcs.CP.2023.25},
  annote =	{Keywords: Branching heuristic, Deep reinforcement learning}
}

Keywords: Branching heuristic, Deep reinforcement learning
Collection: 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)
Issue Date: 2023
Date of publication: 22.09.2023
Supplementary Material: Software (Source Code): https://github.com/corail-research/SeaPearl.jl archived at: https://archive.softwareheritage.org/swh:1:dir:fd35f1159af064307cb36323831a0254e9d4060f


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI