Contributions to automatic configuration and selection for satisfiability

dc.contributor
Universitat de Lleida. Departament d'Informàtica i Enginyeria Industrial
dc.contributor.author
Pon Farreny, Josep
dc.date.accessioned
2022-03-03T10:00:49Z
dc.date.available
2022-07-16T02:00:13Z
dc.date.issued
2021-07-16
dc.identifier.uri
http://hdl.handle.net/10803/673622
dc.description.abstract
En l’àrea de les ciències de la computació, és sabut que els algoritmes poden exhibir comportaments completament diferents depenent de com estiguin configurats els seus paràmetres, fet que s’aguditza quan els problemes que s’aborden són NPComplets. Per exemple, s’ha demostrat experimentalment que configurar solvers pels problemes de la SATisfactibilitat (SAT), la Màxima SATisfactibilitat (MaxSAT) o la programació lineal d’enters mixta (MIP), pot resultar en millores d’ordres de magnitud. En aquesta tesi, mostrem com algoritmes metaheurístics configurats de manera automàtica poden resoldre de forma eficient diverses families d’instancies industrials i artificails del problema MaxSAT. A continuació, ens centrem a millorar el configurador automàtic d’algoritmes GGA proporcionant un nou configurador distribuït que el supera en diverses famílies d’instancis industrials i artificials dels problemes SAT i MIP. Finalment, per fer aquesta tecnologia més accessible a totes les comunitats científiques i la indústria, presentem l’eina PyDGGA que implementa el nostre nou configurador. A més, presentem el paquet OptiLog, el qual permet la creació ràpida de sistemes basats en SAT que addicionalment incorpora un mòdul de configuració automàtica per facilitar l’ús de diverses eines de configuració.
en_US
dc.description.abstract
En el área de las ciencas de la computación, es sabido que los algoritmos pueden exhibir comportamientos completamente diferentes dependiendo de como estén configurados sus parámetros, agudizándose este fenómeno cuando los problemas que se abordan son NP-Completos. Por ejemplo, se ha demostrado experimentalmente que configurar solvers para los problemas de la SATisfactibilidad (SAT), la Maxima SATisfactibilidad (MaxSAT) o la programación lineal de enteros mixta (MIP), puede resultar en mejoras de órdenes de magnitud. En esta tesis, mostramos cómo algoritmos metaheurísticos configurados de manera automática pueden resolver de forma eficiente diversas familias de instancias industriales y artificiales del problema MaxSAT. A continuación, nos centramos en mejorar el configurador automático de algoritmos GGA proporcionando un nuevo configurador distribuido que lo supera en varias familias de instancias industriales y artificiales de los problemas SAT y MIP. Finalmente, para hacer que esta tecnología sea más accesible para todas las comunidades científicas y la industria, presentamos la herramienta PyDGGA que implementa nuestro nuevo configurador. Además, presentamos el paquete OptiLog el cual permite la creación rápida de sistemas basados en SAT que adicionalmente incorpora un módulo de configuración automática para facilitar el uso de varias herramientas de configuración.
en_US
dc.description.abstract
Within the computer science community, it is well known that algorithms may exhibit completely different behaviours depending on how their parameters are configured. This is even more obvious when the problems being tackled are NP-Complete. For example it has been proved experimentally that configuring solvers for the SATisfiabilty (SAT) problem, the Maximum SATisfiability (MaxSAT) problem or for Mixed Integer Programming (MIP), can result in improvements of orders of magnitude. In this thesis, we show how automatically configured metahueristic algorithms can efficiently solve families of industrial and crafted instances of the MaxSAT problem. Then, we focus on improving the automatic algorithm configurator GGA providing a new distributed configurator which outperforms GGA on families of industrial and crafted SAT and MIP instances. Finally, in our aim of making this technology more accessible for all research communities and industry we present the tool PyDGGA that implements our new configurator. We additionally introduce the OptiLog framework for rapid prototyping of SAT-based systems that also incorporates a module for automatic configuration for the easy application of several configuration tools.
en_US
dc.format.extent
87 p.
en_US
dc.format.mimetype
application/pdf
dc.language.iso
eng
en_US
dc.publisher
Universitat de Lleida
dc.rights.license
ADVERTIMENT. Tots els drets reservats. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.
dc.source
TDX (Tesis Doctorals en Xarxa)
dc.subject
Configuració Automàtica
en_US
dc.subject
Algorisme Genètic
en_US
dc.subject
Optimització
en_US
dc.subject
Configuración Automática
en_US
dc.subject
Algoritmo Genético
en_US
dc.subject
Optimización
en_US
dc.subject
Automatic Configuration
en_US
dc.subject
Genetic Algorithm
en_US
dc.subject
Optimization
en_US
dc.subject.other
Ciències de la Computació i Intel·ligència Artificial
en_US
dc.title
Contributions to automatic configuration and selection for satisfiability
en_US
dc.type
info:eu-repo/semantics/doctoralThesis
dc.type
info:eu-repo/semantics/publishedVersion
dc.subject.udc
004
en_US
dc.contributor.director
Ansótegui Gil, Carlos José
dc.embargo.terms
12 mesos
en_US
dc.rights.accessLevel
info:eu-repo/semantics/openAccess


Documentos

Tjpf1de1.pdf

1.428Mb PDF

Este ítem aparece en la(s) siguiente(s) colección(ones)