SeaPearl: A Constraint Programming Solver guided by Reinforcement\n Learning Article Swipe
YOU?
·
· 2021
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2102.09193
The design of efficient and generic algorithms for solving combinatorial\noptimization problems has been an active field of research for many years.\nStandard exact solving approaches are based on a clever and complete\nenumeration of the solution set. A critical and non-trivial design choice with\nsuch methods is the branching strategy, directing how the search is performed.\nThe last decade has shown an increasing interest in the design of machine\nlearning-based heuristics to solve combinatorial optimization problems. The\ngoal is to leverage knowledge from historical data to solve similar new\ninstances of a problem. Used alone, such heuristics are only able to provide\napproximate solutions efficiently, but cannot prove optimality nor bounds on\ntheir solution. Recent works have shown that reinforcement learning can be\nsuccessfully used for driving the search phase of constraint programming (CP)\nsolvers. However, it has also been shown that this hybridization is challenging\nto build, as standard CP frameworks do not natively include machine learning\nmechanisms, leading to some sources of inefficiencies. This paper presents the\nproof of concept for SeaPearl, a new CP solver implemented in Julia, that\nsupports machine learning routines in order to learn branching decisions using\nreinforcement learning. Support for modeling the learning component is also\nprovided. We illustrate the modeling and solution performance of this new\nsolver on two problems. Although not yet competitive with industrial solvers,\nSeaPearl aims to provide a flexible and open-source framework in order to\nfacilitate future research in the hybridization of constraint programming and\nmachine learning.\n
Related Topics To Compare & Contrast
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2102.09193
- https://arxiv.org/pdf/2102.09193
- OA Status
- green
- References
- 48
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4287326329