Pasar al contenido principal

RAZONAMIENTO, SATISFACCION Y OPTIMIZACION

TIN2015-71799-C2-1-P

•
Nombre agencia financiadora Ministerio de Economía y Competitividad
Acrónimo agencia financiadora MINECO
Programa Programa Estatal de Fomento de la Investigación Científica y Técnica de Excelencia
Subprograma Subprograma Estatal de Generación de Conocimiento
Convocatoria Proyectos de I+D (Excelencia / Generación de Conocimiento)
Año convocatoria 2015
Plan Estatal 2013-2016 Plan Estatal de Investigación Científica y Técnica y de Innovación
Unidad de gestión Secretaría de Estado de Educación, Formación Profesional y Universidades
Centro beneficiario AGENCIA ESTATAL CONSEJO SUPERIOR DE INVESTIGACIONES CIENTIFICAS (CSIC)
Identificador persistente http://dx.doi.org/10.13039/501100003329

Resultados relacionados

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

DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

An Effective Learnt Clause Minimization Approach for CDCL SAT Solvers

  • Luo, Mao
  • Li, Chu Min
  • Xiao, Fan
  • Manyà, Felip
  • Lü, Zhipeng
Learnt clauses in CDCL SAT solvers often contain redundant literals. This may have a negative impact on performance because redundant literals may deteriorate both the effectiveness of Boolean constraint propagation and the quality of subsequent learnt clauses. To overcome this drawback, we define a new inprocessing SAT approach which eliminates redundant literals from learnt clauses by applying Boolean constraint propagation. Learnt clause minimization is activated before the SAT solver triggers some selected restarts, and affects only some learnt clauses during the search process. Moreover, we conducted an empirical evaluation on instances coming from the hard combinatorial and application categories of recent SAT competitions. The results show that a remarkable number of additional instances are solved when the approach is incorporated into five of the best performing CDCL SAT solvers. Copyright © 2018, IJCAI, Research partially supported by the National Natural Science Foundation of China (Grants no. 61370183, 61370184, 61472147), the Generalitat de Catalunya grant AGAUR 2014-SGR-118, and the MINECO-FEDER project RASO TIN2015-71799-C2-1-P., Peer Reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

An Exact Algorithm for the Maximum Weight Clique Problem in Large Graphs

  • Jiang, Hua
  • Li, Chu Min
  • Manyà, Felip
We describe an exact branch-and-bound algorithm for the maximum weight clique problem (MWC), called WLMC, that is especially suited for large vertex-weighted graphs. WLMC incorporates two original contributions: a preprocessing to derive an initial vertex ordering and to reduce the size of the graph, and incremental vertex-weight splitting to reduce the number of branches in the search space. Experiments on representative large graphs from real-world applications show that WLMC greatly outperforms relevant exact and heuristic MWC algorithms, and refute the prevailing hypothesis that exact MWC algorithms are less adequate for large graphs than heuristic algorithms. Copyright © 2017, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved., This work is supported by NSFC Grants No. 61272014, No.61370183, No. 61472147 and No. 61370184, the MeCS platform of the University of Picardie Jules Verne and the HPC platform of Jianghan Univeristy. The third author was supported by Mobility Grant PRX16/00215 of the Ministerio de Educación, Cultura y Deporte, the Generalitat de Catalunya grant AGAUR 2014-SGR-118, and the MINECO-FEDER project RASO TIN2015-71799-C2-1-P, Peer Reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

A two-stage MaxSAT reasoning approach for the maximum weight clique problem

  • Jiang, Hua
  • Min Li, Chu
  • Liu, Yanli
  • Manyà, Felip
Trabajo presentado en la The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18), celebrada en Hilton New Orleans Riverside, New Orleans (Estados Unidos), del 2 al 7 febrero de 2018, MaxSAT reasoning is an effective technology used in modern branch-and-bound (BnB) algorithms for the Maximum Weight Clique problem (MWC) to reduce the search space. However, the current MaxSAT reasoning approach for MWC is carried out in a blind manner and is not guided by any relevant strategy. In this paper, we describe a new BnB algorithm for MWC that incorporates a novel two-stage MaxSAT reasoning approach. In each stage, the MaxSAT reasoning is specialised and guided for different tasks. Experiments on an extensive set of graphs show that the new algorithm implementing this approach significantly outperforms relevant exact and heuristic MWC algorithms in both small/medium and massive real-world graphs., This work is supported by NSFC Grant No. 61272014, No.61472147, No. 61370183 and No. 61370184, the Metrics platform of University of Picardie Jules Verne, the HPC platform of JHUN, and the MINECO-FEDER project RASO TIN2015-71799-C2-1-P., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

Connecting systems of Mathematical fuzzy logic with fuzzy concept lattices

  • Codara, Pietro
  • Esteva, Francesc
  • Godo, Lluis
  • Valota, Diego
Trabajo presentado en el 17th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU) celebrado en Cádiz (España) del 11 al 15 de junio de 2018, In this paper our aim is to explore a new look at formal systems of fuzzy logics using the framework of (fuzzy) formal concept analysis (FCA). Let L be an extension of MTL complete with respect to a given L-chain. We investigate two possible approaches. The first one is to consider fuzzy formal contexts arising from L where attributes are identified with L-formulas and objects with L-evaluations: every L-evaluation (object) satisfies a formula (attribute) to a given degree, and vice-versa. The corresponding fuzzy concept lattices are shown to be isomorphic to quotients of the Lindenbaum algebra of L. The second one, following an idea in a previous paper by two of the authors for the particular case of Gödel fuzzy logic, is to use a result by Ganter and Wille in order to interpret the (lattice reduct of the) Lindenbaum algebra of L-formulas as a (classical) concept lattice of a given context., The authors are thankful to the anonymous reviewers for their helpful comments. Pietro Codara is supported by the INdAM-Marie Curie Cofund project LaVague (FP7-PEOPLE-2012-COFUND 600198). Francesc Esteva and Lluis Godo acknowledge partial support by the FEDER/MINECO project TIN2015-71799- C2-1-P., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

Logics for strict-coherence and Carnap-regular probability functions

  • Flaminio, Tommaso
Trabajo presentado en el 17th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU) celebrado en Cádiz (España) del 11 al 15 de junio de 2018, In this paper we provide a characterization of strict coherence in terms of the logical consistency of suitably defined formulas in fuzzy-modal logics for probabilistic reasoning. As a direct consequence of our characterization, we also show the decidability for the problem of checking the strict coherence of rational-valued books on classical events. Further, we introduce a fuzzy modal logic that captures Carnap-regular probability functions, that is normalized and finitely additive measures which maps to 0 only the impossible event., The author acknowledges partial support by the Spanish Ramon y Cajal research program RYC-2016-19799; the Spanish FEDER/MINECO project TIN2015-71799-C2-1-P and the SYSMICS project (EU H2020-MSCA-RISE-2015 Project 689176)., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

Term-graph anti-unification

  • Baumgartner, Alexander
  • Kutsia, Temur
  • Levy, Jordi
  • Villaret, Mateu
Trabajo presentado en el 3rd International Conference on Formal Structures for Computation and Deduction (FSCD), celebrado en Oxford (Inglaterra), del 9 al 12 de julio de 2018, We study anti-unification for possibly cyclic, unranked term-graphs and develop an algorithm, which computes a minimal complete set of generalizations for them. For bisimilar graphs the algorithm computes the join in the lattice generated by a functional bisimulation. These results generalize anti-unification for ranked and unranked terms to the corresponding term-graphs, and solve also anti-unification problems for rational terms and dags. Our results open a way to widen anti-unification based code clone detection techniques from a tree representation to a graph representation of the code., Supported by the Austrian Science Fund (FWF) under the projects P 28789-N32 and J 3909-N31, by MINECO/FEDER projects TIN2015-71799-C2-1-P (RASO) and TIN2015-66293-R (LoCos), and by UdG project MPCUdG2016/055., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

On implication-free reducts of MVn-algebras

  • Coniglio, Marcelo E.
  • Esteva, Francesc
  • Flaminio, Tommaso
  • Godo, Lluis
Trabajo presentado en Logic, Algebra and Truth Degrees (LATD 2018), celebrado en Bern (Suiza), del 27 al 31 de agosto de 2018, The authors acknowledge partial support by the H2020 MSCA-RISE-2015project SYSMICS. Coniglio also acknowledges support by the CNPq grant 308524/2014-4. Flaminio acknowledges support by the Ramon y Cajal research program RYC-2016-19799. Esteva, Flaminio and Godo also acknowledge the FEDER/MINECO project TIN2015-71799-C2-1-P, Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

An argumentative recommendation approach based on contextual aspects

  • Lionel Teze, Juan Carlos
  • Godo, Lluis
  • Simari, Guillermo
Trabajo presentado en el 12th International Scalable Uncertainty Management (SUM 2018), celebrado en Milán (Italia), del 3 al 5 de octubre de 2018, Argumentation-based recommender systems constitute an interesting tool to provide reasoned recommendations in complex domains with unresolved contradictory information situations and incomplete information. In these systems, the use of contextual information becomes a central issue in order to come up with personalized recommendations. An argumentative recommender system that offers mechanisms to handle contextual aspects of the recommendation domain provides an important ability that can be exploited by the user. However, in most of existing works, this issue has not been extensively studied. In this work, we propose an argumentation-based formalization for dealing with this issue. We present a general framework that allows the design of recommender systems capable of handling queries that can include (possibly inconsistent) contextual information under which recommendations should be computed. To answer a query, in the proposed argumentationbased approach, the system first selects alternative instances according to the user’s supplied contextual information, and then makes recommendations, in both cases through a defeasible argumentative analysis., This work has been partially supported by EU H2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No. 690974 for the project MIREL: MIning and REasoning with Legal texts, and by funds provided by CONICET, Universidad Nacional del Sur by PGI-UNS (grant 24/N040), and Universidad Nacional de Entre Rıos. Godo acknowledges the Spanish FEDER/MINECO project TIN2015-71799- C2-1-P., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

Inferring quantitative preferences: beyond logical deduction

  • Martínez, Vanina
  • Godo, Lluis
  • Simari, Gerardo I.
Trabajo presentado en el 12th International Scalable Uncertainty Management (SUM 2018), celebrado en Milán (Italia), del 3 al 5 de octubre de 2018, In this paper we consider a hybrid possibilistic-probabilistic alternative approach to Probabilistic Preference Logic Networks (PPLNs). Namely, we first adopt a possibilistic model to represent the beliefs about uncertain strict preference statements, and then, by means of a pignistic probability transformation, we switch to a probabilistic-based credulous inference of new preferences for which no explicit (or transitive) information is provided. Finally, we provide a tractable approximate method to compute these probabilities., Martinez and Simari have been partially supported by EU H2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No. 690974 for the project MIREL: MIning and REasoning with Legal texts; and funds provided by Universidad Nacional del Sur (UNS), Agencia Nacional de Promocion Cientifica y Tecnologica, and CONICET, Argentina. Godo acknowledges the EU H2020 project SYSMICS (MSCA-RISE-2015 Project 689176) and the Spanish FEDER/MINECO project TIN2015-71799-C2-1-P, Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

Clause Branching in MaxSAT and MinSAT

  • Argelich, Josep
  • Li, Chu Min
  • Manyà, Felip
  • Zhu, Zhu
Trabajo presentado en el 21st International Conference of the Catalan Association for Artificial Intelligence (CCIA 2018), celebrada en Roses (España) del 8 al 10 de Octubre de 2018, We describe a new exact procedure, inspired on recent works on tableaux, for simultaneously solving MaxSAT and MinSAT. The main novelty of our procedure is that it implements a clause branching rule that preserves both the minimum and the maximum number of clauses than can be unsatisfied. Moreover, we prove the correctness of the procedure, and provide a review of the different types of branchings which are available for MaxSAT and MinSAT. We also give some preliminary experimental results that show that the new branching rule, when implemented into an existing branch-and-bound MaxSAT solver, produces substantial gains on industrial instances of the MaxSAT Evaluation., This work was supported by Project LOGISTAR from the EU H2020 Research and Innovation Programme under Grant Agreement No. 769142, and MINECO-FEDER projects RASO (TIN2015-71799-C2-1-P/2-P)., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

Phase Transition in Realistic Random SAT Models

  • Ansotegui, Carlos
  • Bonet, María Luisa
  • Levy, Jordi
Phase-transition in random SAT formulas is one of the properties best studied by theoretical SAT researchers. There exists a constant rk depending on k such that, if we choose randomly a k-SAT formula over n variables and m clauses, it will be satisfiable with high probability, if m/n < r, and unsatisfiable, otherwise. However, this criterion is useless in practice, because real-world or industrial instances have some properties not shown in random formulas. In the last years, several models of realistic random formulas have been proposed. Here we discuss about the phase transition in these models, and about the size of unsatisfiability proofs. We observe that in these models, like in real-world formulas, there is not a sharp phase transition, the transition occurs for smaller values of r, and the proofs on unsatisfiable formulas are smaller than in the classical random model. We also discuss about the strategies used by modern SAT solvers to exploit these properties., Research partially supported by the EU H2020 Research and Innovation Program under the LOGISTAR project (Grant Agreement No. 769142) and the MINECO-FEDER projects RASO (TIN2015-71799-C2-1-P) and TASSAT 3 (TIN2016-76573-C2-2-P).