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): 6
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.
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Constraint Solving Approaches to the Business-to-Business Meeting Scheduling Problem

  • Bofill, Miquel
  • Coll, Jordi
  • Marín-García, Marc
  • Giráldez-Cru, Jesús
  • Pesant, Gilles
  • Suy, Josep
  • Villaret, Mateu
JAIR distributes articlees for free on the public internet. Individual users may read, download, copy, distribute, print, search, or link to the full texts of indvidual articles, crawl them for indexing, pass them as data to software, or use them for any other lawful purpose as specified in our licensing terms. However, the right to publish complete volumes of the journal in print is reserved exclusively for AAAI, and therefore others may not sell or publish complete volumes of JAIR in print., The Business-to-Business Meeting Scheduling problem consists of scheduling a set of meetings between given pairs of participants to an event, while taking into account participants’ availability and accommodation capacity. A crucial aspect of this problem is that breaks in participants’ schedules should be avoided as much as possible. It constitutes a challenging combinatorial problem that needs to be solved for many real world brokerage events. In this paper we present a comparative study of Constraint Programming (CP), MixedInteger Programming (MIP) and Maximum Satisfiability (MaxSAT) approaches to this problem. The CP approach relies on using global constraints and has been implemented in MiniZinc to be able to compare CP, Lazy Clause Generation and MIP as solving technologies in this setting. We also present a pure MIP encoding. Finally, an alternative viewpoint is considered under MaxSAT, showing best performance when considering some implied constraints. Experiments conducted on real world instances, as well as on crafted ones, show that the MaxSAT approach is the one with the best performance for this problem, exhibiting better solving times, sometimes even orders of magnitude smaller than CP and MIP., Work partially supported by grants PGC2018-101216-B-I00 and RTI2018-095609-B-I00(MICINN/FEDER, UE), fellowships FJCI-2017-32420, IJC2019-040489-I (MICINN/Juande la Cierva),Ayudas para Contratos Predoctorales 2016(grant number BES-2016-076867,funded by MINECO and co-funded by FSE), AMU Institut Archim ́ede and NSERC Dis-covery Grant 218028/2017., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

The Sample Analysis Machine Scheduling Problem: Definition and comparison of exact solving approaches

  • Bofill, Miquel
  • Coll, Jordi
  • Martín, Gerard
  • Suy, Josep
  • Villaret, Mateu
Nowadays there exists a wide variety of automatic machines that perform analytical tests on liquid samples, such as water, blood, urines, saliva, etc. A test can be modelled as a set of activities with given precedences and through sharing a set of limited resources. A scheduling process is therefore required to find a feasible or optimal execution of a set of tests. An important particularity of the machines performing tests are their storage areas of limited capacity. For instance, one activity may require a sample to be moved to an observation area, while another activity may later remove this sample from that observation area. In this paper, we introduce a real problem encountered in the analytical instrument industry known as the Sample Analysis Machine Scheduling Problem (SAMSP). We show that the SAMSP is a particular case of the Resource Constrained Project Scheduling Problem with Cumulative Resources (RCPSP-Cu), and present a successful application of optimization techniques for it. We are interested in exact approaches, since the models presented will be used to prove the maximum throughput of the selected machine layouts. In particular, we compare the performance of approaches based on Constraint Programming (CP), Satisfiability Modulo Theories (SMT), and Mixed Integer Linear Programming (MILP), on real instances of SAMSP., This work was supported by MICINN/FEDER, UE (grant number RTI2018-095609-B-I00) and partially funded by the French Agence Nationale de la Recherche , reference ANR-19-CHIA-0013-01., Peer reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The Impact of Implied Constraints on MaxSAT B2B Instances

  • Bofill Arasa, Miquel
  • Coll Caballero, Jordi
  • Giráldez-Cru, Jesús
  • Suy Franch, Josep
  • Villaret i Ausellé, Mateu
The B2B scheduling optimization problem consists of finding a schedule of a set of meetings between pairs of participants, minimizing their number of idle time periods. Recent works have shown that SAT-based approaches are state-of-the-art on this problem. One interesting feature of such approaches is the use of implied constraints. In this work, we provide an experimental setting to study the impact of using these implied constraints in MaxSAT B2B instances. To this purpose and due to the reduced number of existing real-world B2B instances, we propose a random B2B instance generation model, which reproduces certain features of these problems. In our experimental analysis, we show that the impact of using some implied constraints in the MaxSAT encodings depends on the characteristics of the problem, and we also analyze the benefits of combining them. Finally, we give some insights on how a MaxSAT solver is able to exploit these implied constraint, Miquel Bofill, Josep Suy and Mateu Villaret are partially funded by grant RTI2018-095609-B-I00 (MICINN/FEDER, UE). Jordi Coll is partially funded by the French Agence Nationale de la Recherche, reference ANR-19-CHIA-0013-01. Jesús Giráldez-Cru is supported through the Juan de la Cierva program, fellowship IJC2019-040489-I, funded by MCIN and AEI
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The Sample Analysis Machine Scheduling Problem: Definition and comparison of exact solving approaches

  • Bofill Arasa, Miquel
  • Coll Caballero, Jordi
  • Suy Franch, Josep
  • Villaret i Ausellé, Mateu
Nowadays there exists a wide variety of automatic machines that perform analytical tests on liquid samples, such as water, blood, urines, saliva, etc. A test can be modelled as a set of activities with given precedences and through sharing a set of limited resources. A scheduling process is therefore required to find a feasible or optimal execution of a set of tests. An important particularity of the machines performing tests are their storage areas of limited capacity. For instance, one activity may require a sample to be moved to an observation area, while another activity may later remove this sample from that observation area. In this paper, we introduce a real problem encountered in the analytical instrument industry known as the Sample Analysis Machine Scheduling Problem (SAMSP). We show that the SAMSP is a particular case of the Resource Constrained Project Scheduling Problem with Cumulative Resources (RCPSP-Cu), and present a successful application of optimization techniques for it. We are interested in exact approaches, since the models presented will be used to prove the maximum throughput of the selected machine layouts. In particular, we compare the performance of approaches based on Constraint Programming (CP), Satisfiability Modulo Theories (SMT), and Mixed Integer Linear Programming (MILP), on real instances of SAMSP, This work was supported by MICINN/FEDER, UE (grant number RTI2018-095609-B-I00) and partially funded by the French Agence Nationale de la Recherche, reference ANR-19-CHIA-0013-01, Open Access funding provided thanks to the CRUE-CSIC agreement with Elsevier
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.