Back to search

FRINATEK-Fri prosj.st. mat.,naturv.,tek

AutoCSP: Self-Supervised Neuro-Symbolic Solvers for Constraint Satisfaction

Alternative title: AutoCSP: Selvlærte neurosymboliske «constraint solvers» for begrensning tilfredshet

Awarded: NOK 3.8 mill.

Project Manager:

Project Number:

324674

Project Period:

2021 - 2024

Location:

Partner countries:

The AutoCSP project addresses problems where the solution is a combination of multiple decision variables, so-called combinatorial optimization problems. The goal is to find a combination that fulfills all constraints that the problem has while optimizing an objective function. Examples for these problems include machine or job scheduling, timetabling, lot sizing, or vehicle routing, all of which are highly relevant in industrial settings like production planning or delivery scheduling and are embedded in intelligent decision support systems. The state-of-the-art technique to solve these problems are dedicated constraint solvers, which are highly optimized and have been investigated for a long time. Still, searching for good or even optimal solutions often is time-consuming due to the enormous number of possible combinations that need to be explored while facing strong restrictions on which combinations form a feasible solution. This is especially true when the same problem has to be repeatedly solved with different inputs, for example in daily production planning or fleet scheduling tasks. Even though the general problem stays the same, experiences from earlier solutions are not used to solve new instances faster. AutoCSP advances the scientific knowledge and state-of-the-art through problem-specific solvers that combine data-driven machine learning (ML) models and logic-driven constraint solvers in a hybrid intelligent system. These solvers are automatically generated from a constraint model, i.e. the description of the problem to be solved, and are self-taught to solve constraint satisfaction and optimization problems while maintaining correctness and time-efficiency. To achieve this goal, the project investigates a) how to generate training data just from the problem description, b) how to present the data such that the ML model understands it, c) how to efficiently learn from this data, and d) how to bring everything together in one system.

The AutoCSP project aims to enable the creation of fast and accurate problem-specific solvers for combinatorial optimization problems with strict constraints that automatically improve themselves. Examples of these problems include machine or job scheduling, timetabling, lot sizing, or vehicle routing. These problems are highly relevant in industrial settings like production planning or delivery scheduling and are embedded in intelligent decision support systems for other problem settings. The state-of-the-art technology to solve these problems are dedicated constraint solvers, which are highly optimized, but still require in-depth expertise to be correctly tuned and deployed. Searching for good or even optimal solutions often is time-consuming due to the enormous number of possible combinations that need to be explored while facing strong restrictions on which combinations form a feasible solution. This limitation is especially true when repeatedly solving the same problem with different input parameters, such as frequent production planning or fleet scheduling tasks. Even though the constraint model remains fixed, the solver does not use earlier solutions to accelerate solving new instances. AutoCSP advances the scientific knowledge for solving combinatorial optimization problems through a framework for creating problem-specific solvers as a hybrid intelligent system. This system combines data-driven machine learning (ML) models and logic-driven constraint solvers that verify and improve the ML model’s initial solution candidates. Our hybrid solvers are automatically generated and tuned from a constraint model to solve constraint satisfaction and optimization problems while maintaining exactness and time-efficiency.

Activity:

FRINATEK-Fri prosj.st. mat.,naturv.,tek