AD-Lib: An Aggregation-Disaggregation LIBrary for sequential decision models

The ubiquity of SAT, Constraint Programming (CP) and Mixed Integer Programming (MIP) solvers in the optimization community has demonstrated the importance of generic algorithms able to solve any problem that can be expressed in a specific paradigm.

In particular, any optimization methods have achieved great success for problems that can be expressed as sequential decision processes. These problems have mathematical formulations with nice theoretical properties, and a large portfolio of dedicated efficient algorithms. However an important downside of these formulations is their typically exponential or pseudo- polynomial number of variables and constraints. To overcome this limitation, several methods based on variable/constraint aggregation/disaggregation have been introduced in different communities.

The conclusions of a preliminary survey of the relevant literature is that similar techniques are used under different names in different fields (MIP, DP, CP/SAT), leading to a scattered scientific literature. Moreover, there is a need for more effective algorithms for controlling the aggregation process.

Our main goals in this project are threefold: a generic formalism that encompasses the aforementioned techniques ; more efficient algorithms to control the aggregation procedures ; open-source codes that leverage and integrate these algorithms to efficiently solve hard combinatorial problems in different application fields.

We will jointly study two types of approaches, MIP and SAT, to reach our goals. Their complementary will by instrumental in the success of our algorithms.

The first work package consists in sharing knowledge and insights between the two fields. The second will study generic strategies for aggregation/disaggregation. The third will focus on clause-learning-based methods in CP. All our algorithms will be embedded in an open-source platform, which will be used to achieve state-on-the-art results for hard benchmark problems.

The AD-Lib project is coordinated by the INRIA Research Centre in Bordeaux Sud-Ouest, with the LAAS-CNRS Systems Analysis and Architecture Laboratory and TBS Education as partners.
It is financed by the ANR (National Research Agency) as part of the 2022 generic call for projects.
This is the first collaborative project for TBS Education in collaboration with the LAAS-CNRS and INRIA financed by the ANR.

The project is planned to last 48 months from October 1, 2022 to September 30, 2026.

It is led within TBS Education by Simon BELIERES, teacher-researcher in the Finance, Economics and Econometrics research laboratory.