AD-Lib: An Aggregation-Disaggregation LIBrary for sequential decision models – AD-LIB
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 problem 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. Moerover, 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.
Project coordinator
Monsieur François CLAUTIAUX (Centre de Recherche Inria Bordeaux - Sud-Ouest)
The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.
Partner
LAAS-CNRS Laboratoire d'analyse et d'architecture des systèmes
TOULOUSE BUSINESS SCHOOL - TBS
INRIA Bordeaux Sud-Ouest Centre de Recherche Inria Bordeaux - Sud-Ouest
Help of the ANR 500,409 euros
Beginning and duration of the scientific project:
September 2022
- 48 Months