Pasar al contenido principal

SATISFACTIBILIDAD PARA PROGRAMACION DE TAREAS, PLANIFICACION Y OPTIMIZACION

RTI2018-095609-B-I00

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos I+D+i Retos de Investigación
Año convocatoria 2018
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSITAT DE GIRONA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 2
Encontrada(s) 1 página(s)

Repositori Obert UdL
Publicación Contribución de congreso (ConferenceOutput)

Automatic Detection of At-Most-One and Exactly-One Relations for Improved SAT Encodings of Pseudo-Boolean Constraints

  • Ansótegui Gil, Carlos José
  • Bofill, Miquel
  • Coll, Jordi
  • Dang, Nguyen
  • Esteban, Juan Luis
  • Miguel, Ian
  • Nightingale, Peter
  • Salamon, András Z.
  • Suy, Josep
  • Villaret, Mateu
Pseudo-Boolean (PB) constraints often have a critical role in constraint satisfaction and optimisation problems. Encoding PB constraints to SAT has proven to be an efficient approach in many applications, however care must be taken to encode them compactly and with good propagation properties. It has been shown that at-most-one (AMO) and exactly-one (EO) relations over subsets of the variables can be exploited in various encodings of PB constraints, improving their compactness and solving performance. In this paper we detect AMO and EO relations completely automatically and exploit them to improve SAT encodings that are based on Multi-Valued Decision Diagrams (MDDs). Our experiments show substantial reductions in encoding size and dramatic improvements in solving time thanks to automatic AMO and EO detection., Work supported by grants TIN2015-66293-R, TIN2016-76573-C2-1/2-P (MINECO/ FEDER, UE), Ayudas para Contratos Predoctorales 2016 (grant number BES2016- 076867, funded by MINECO and co-funded by FSE), RTI2018-095609-B-I00 (MICINN/FEDER, UE), and EPSRC EP/P015638/1.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Automatic Detection of At-Most-One and Exactly-One Relations for Improved SAT Encodings of Pseudo-Boolean Constraints

  • Ansótegui Gil, Carlos José
  • Bofill, Miquel
  • Coll, Jordi
  • Dang, Nguyen
  • Esteban, Juan Luis
  • Miguel, Ian
  • Nightingale, Peter
  • Salamon, András Z.
  • Suy, Josep
  • Villaret, Mateu
Pseudo-Boolean (PB) constraints often have a critical role in constraint satisfaction and optimisation problems. Encoding PB constraints to SAT has proven to be an efficient approach in many applications, however care must be taken to encode them compactly and with good propagation properties. It has been shown that at-most-one (AMO) and exactly-one (EO) relations over subsets of the variables can be exploited in various encodings of PB constraints, improving their compactness and solving performance. In this paper we detect AMO and EO relations completely automatically and exploit them to improve SAT encodings that are based on Multi-Valued Decision Diagrams (MDDs). Our experiments show substantial reductions in encoding size and dramatic improvements in solving time thanks to automatic AMO and EO detection., Work supported by grants TIN2015-66293-R, TIN2016-76573-C2-1/2-P (MINECO/ FEDER, UE), Ayudas para Contratos Predoctorales 2016 (grant number BES2016- 076867, funded by MINECO and co-funded by FSE), RTI2018-095609-B-I00 (MICINN/FEDER, UE), and EPSRC EP/P015638/1.