This project pivots around the satisfiability and constraint optimization problems for logical languages including propositional logic (SAT) and more general expressive constraint satisfaction problems (CSP). Our purpose is to conduct frontier research in this area exploiting the expertise of the four groups that participate in the project. TASSAT 2 is the continuation of the project that gives birth to it, TASSAT, that already proved its potential and viability. For this reason, the main objectives of this project are partly follow-ups on those of the previous project and partly new, with the following concrete goals in particular: In SAT we want to continue studying the structure of instances arising in industry, and apply this knowledge to develop more efficient solvers, both for SAT and for MAXSAT. In CSP we want to continue contributing to the problem of classification of tractable constraint languages. We will also study algorithms for geometric instances of MAXCSP and combinatorial problems of interest in computational complexity theory. An important novelty of the present proposal is its stronger emphasis in the implementation of practical solvers, including new branch-and-bound algorithms for MAXSAT, soft learning for MAXSAT, better variable selection techniques, portfolios, etc. We want to expand our presence in international solver competitions and participate in the solution of industrial problems. Another significant novelty in the goals is that we plan to expand the range of applications of the geometric methods to include graph isomorphism problems and other structures of interest in combinatorics and other areas of science. This new goal derives from some of the results obtained in the previous project that already had a notable international impact. Efficiency appears as one of the keywords in the ICT-related activities of the European H2020 (see SC4 and SC5 in "Societal challenges"). This may refer to efficiency in energy distribution, logistics applications, etc. SAT and MAXSAT solvers are a relatively new technology for optimization that can be applied in some of these areas. One of our goals in this project is to consolidate a consortium of research groups in the area, to compete in the application of European research projects.
Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016
Programa Estatal de Fomento de la Investigación Científica y Técnica de Excelencia
Subprograma Estatal de Generación de Conocimiento
Excelencia: Proyectos I+D
Gobierno De España. Ministerio De Economía Y Competitividad, Mineco
Atserias, A.; Mancinska, L.; Roberson, D.; Samal, R.; Severini, S.; Varvitsiotis, A. Journal of combinatorial theory. Series B Vol. 136, p. 289-328 DOI: 10.1016/j.jctb.2018.11.002 Date of publication: 2019-05 Journal article