| 2015 |
| Instantiation of Meta-models Constrained with OCL: a CSP Approach Adel Ferdjoukh, Anne-Elisabeth Baert, Eric Bourreau, Annie Chateau, Rémi Coletta & Clémentine Nebut In MODELSWARD, International Conference on Model-Driven Engineering and Software Development., pp. 213-222, 2015. |
| Abstract: The automated generation of models that conform to a given meta-model is an important challenge in Model Driven Engineering, as well for model transformation testing, as for designing and exploring new meta-models. Amongst the main issues, we are mainly concerned by scalability, flexibility and a reasonable computing time. This paper presents an approach for model generation, which relies on Constraint Programming. After the translation of a meta-model into a CSP, our software generates models that conform to this meta-model, using a Constraint Solver. Our model also includes the most frequent types of OCL constraints. Since we are concerned by the relevance of the produced models, we describe a first attempt to improve them. We outperform the existing approaches from the mentioned point of view, and propose a configurable, easy-to-use and free-access tool, together with an on-line demonstrator. |
BibTeX:
@inproceedings{modelsward15,
author = {Ferdjoukh, Adel and Baert, Anne-Elisabeth and Bourreau, Eric and Chateau, Annie and Coletta, Rémi and Nebut, Clémentine},
title = {Instantiation of Meta-models Constrained with OCL: a CSP Approach},
booktitle = {MODELSWARD, International Conference on Model-Driven Engineering and Software Development},
year = {2015},
pages = {213-222}
}
|
| 2014 |
| Boosting Constraint Acquisition via Generalization Queries Christian Bessiere, Remi Coletta, Abderrazak Daoudi, Nadjib Lazaar, Younes Mechqrane & El-Houssine Bouyakhf In ECAI 2014 - 21st European Conference on Artificial Intelligence, 18-22 August 2014., pp. 99-104, 2014. |
| Abstract: Constraint acquisition assists a non-expert user in modeling her problem as a constraint network. In existing constraint acquisition systems the user is only asked to answer very basic questions. The drawback is that when no background knowledge is provided, the user may need to answer a great number of such questions to learn all the constraints. In this paper, we introduce the concept of generalization query based on an aggregation of variables into types. We present a constraint generalization algorithm that can be plugged into any constraint acquisition system. We propose several strategies to make our approach more efficient in terms of number of queries. Finally we experimentally compare the recent QUACQ system to an extended version boosted by the use of our generalization functionality. The results show that the extended version dramatically improves the basic QUACQ. |
BibTeX:
@inproceedings{GeneralisationECAI14,
author = {Christian Bessiere and |
| Solve a Constraint Problem without Modeling It Christian Bessiere, Remi Coletta & Nadjib Lazaar In ICTAI 2014, Limassol, Cyprus, November 10-12, 2014., pp. 1-7, 2014. |
| Abstract: We study how to find a solution to a constraint problem without modeling it. Constraint acquisition systems such as Conacq or ModelSeeker are not able to solve a single instance of a problem because they require positive examples to learn. The recent QuAcq algorithm for constraint acquisition does not require positive examples to learn a constraint network. It is thus able to solve a constraint problem without modeling it: we simply exit from QuAcq as soon as a complete example is classified as positive by the user. In this paper, we propose ASK&SOLVE, an elicitation-based solver that tries to find the best tradeoff between learning and solving to converge as soon as possible on a solution. We propose several strategies to speed-up ASK&SOLVE. Finally we give an experimental evaluation that shows that our approach improves the state of the art. |
BibTeX:
@inproceedings{ICTAI14,
author = {Christian Bessiere and |
| An Integer Linear Programming Approach for Genome Scaffolding Nicolas Briot, Annie Chateau andRemi Coletta, Simon de Givry, Philippe Leleux & Thomas Schiex In 10th Workshop on Constraint-Based Methods for Bioinformatics., pp. 1-15, 2014. |
BibTeX:
@inproceedings{WAnnie14,
author = {Nicolas Briot and |
| 2013 |
| Adaptive Parameterized Consistency Amine Balafrej, Christian Bessiere, Remi Coletta & El-Houssine Bouyakhf In CP., pp. 143-158. Springer, 2013. |
| Abstract: State-of-the-art constraint solvers uniformly maintain the same level of local consistency (usually arc consistency) on all the instances. We propose parameterized local consistency, an original approach to adjust the level of consistency depending on the instance and on which part of the instance we propagate. We do not use as parameter one of the features of the instance, as done for instance in portfolios of solvers. We use as parameter the stability of values, which is a feature based on the state of the arc consistency algorithm during its execution. Parameterized local consistencies choose to enforce arc consistency or a higher level of local consistency on a value depending on whether the stability of the value is above or below a given threshold. We also propose a way to dynamically adapt the parameter, and thus the level of local consistency, during search. This approach allows us to get a good trade-off between the number of values pruned and the computational cost. We validate our approach on various problems from the CSP competition. |
BibTeX:
@inproceedings{cp13,
author = {Amine Balafrej and |
| Constrained Wine Blending Philippe Vismara, Remi Coletta & Gilles Trombettoni In CP., pp. 864-879. Springer, 2013. |
| Abstract: Assemblage consists in blending base wines in order to create a target wine. Recent advances in aroma analysis allow us to measure chemical compounds impacting the taste of wines. This chemical analysis makes it possible to design a decision tool for the following problem: given a set of target wines, determine which volumes must be extracted from each base wine to produce wines that satisfy constraints on aroma concentration, volumes, alcohol contents and price. This paper describes the modeling of wine assemblage as a non linear constrained Min-Max problem (minimizing the gap to the desired concentrations for every aromatic criterion) efficiently handled by the Ibex interval branch and bound. |
BibTeX:
@inproceedings{cp13wine,
author = {Philippe Vismara and |
| A CSP Approach for Metamodel Instantiation Adel Ferdjoukh, Anne-Elisabeth Baert, Annie Chateau, Remi Coletta & Clémentine Nebut In ICTAIHerndon, VA, USA, November 4-6, 2013 ., pp. 1044-1051, 2013. |
| Abstract: This work is a contribution of Artificial Intelli- gence to Software Engineering. We present a comprehensive approach to metamodel instantiation using CSP. The gener- ation of models which conform to a given metamodel is a crucial issue in Software Engineering, especially when it comes to produce a variate and large dataset of relevant models to test model transformations or to properly design new metamodels. We define an original constraint modeling of the problem of generating a model conform to a metamodel, also taking into account its additional OCL constraints. The generation process we describe appears to be quicker, more efficient and flexible than any other state-of-the-art approach. |
BibTeX:
@inproceedings{ictai13,
author = {Adel Ferdjoukh and |
| Constraint Acquisition via Partial Queries Christian Bessiere, Remi Coletta, Emmanuel Hebrard, George Katsirelos, Nadjib Lazaar, Nina Narodytska, Claude-Guy Quimper & Toby Walsh In IJCAI., pp. 475-481, 2013. |
| Abstract: We learn constraint networks by asking the user partial queries. That is, we ask the user to classify assignments to subsets of the variables as positive or negative. We provide an algorithm that, given a negative example, focuses onto a constraint of the target network in a number of queries logarithmic in the size of the example. We give information theoretic lower bounds for learning some simple classes of constraint networks and show that our generic algorithm is optimal in some cases. Finally we evaluate our algorithm on some benchmarks. |
BibTeX:
@inproceedings{ijcai13,
author = {Christian Bessiere and |
| A Declarative Approach to View Selection Modeling Imene Mami, Zohra Bellahsene and Remi Coletta T. Large-Scale Data- and Knowledge-Centered Systems. Lecture Notes in Computer Science. Vol. 10, pp. 115-145. Springer, 2013. |
BibTeX:
@article{MamiBC13,
author = {Imene Mami and |
| 2012 |
| Breaking Variable Symmetry in Almost Injective Problems Philippe Vismara & Remi Coletta In CP. Lecture Notes in Computer Science., pp. 664-671. Springer, 2012. |
| Abstract: Lexicographic constraints are commonly used to break vari- able symmetries. In the general case, the number of constraint to be posted is potentially exponential in the number of variables. For injective problems (AllDiff), Puget’s method breaks all variable symmetries with a linear number of constraints. In this paper we assess the number of constraints for “almost” injective problems. We propose to characterize them by a parameter μ based on Global Cardinality Constraint as a generalization of the AllDiff constraint. We show that for almost injective problems, variable symmetries can be broken with no more than `n ́ constraints which is XP in the μ framework of parameterized complexity. When only ν variables can take duplicated values, the number of constraints is FPT in μ and ν. |
BibTeX:
@inproceedings{cp12,
author = {Philippe Vismara and |
| View Selection under Multiple Resource Constraints in a Distributed Context Imene Mami, Zohra Bellahsene & Remi Coletta In DEXA . Lecture Notes in Computer Science., pp. 281-296. Springer, 2012. |
| Abstract: The use of materialized views in commercial database systems and data warehousing systems is a common technique to improve the query performance. In past research, the view selection issue has es- sentially been investigated in the centralized context. In this paper, we address the view selection problem in a distributed scenario. We extend the AND-OR view graph to capture the distributed features. Then, we propose a solution using constraint programming for modeling and solving the view selection problem under multiple resource constraints in a distributed context. Finally, we experimentally show that our approach provides better performance resulting from evaluating the quality of the solutions in terms of cost saving. |
BibTeX:
@inproceedings{dexa12,
author = {Imene Mami and |
| Public data integration with WebSmatch Remi Coletta, Emmanuel Castanier, Patrick Valduriez, Christian Frisch, DuyHoa Ngo & Zohra Bellahsene In WOD '12, Nantes, France, May 25, 2012., pp. 5-12. ACM, 2012. |
| Abstract: Integrating open data sources can yield high value informa- tion but raises major problems in terms of metadata extraction, data source integration and visualization of integrated data. In this paper, we describe WebSmatch, a flexible environment for Web data integration, based on a real, end-to-end data integration scenario over public data from Data Publica1. WebSmatch supports the full process of importing, refining and integrating data sources and uses third party tools for high quality visualization. We use a typical scenario of public data integration which involves problems not solved by currents tools: poorly structured input data sources (XLS files) and rich visualization of integrated data. |
BibTeX:
@inproceedings{wod12,
author = {Remi Coletta and |
| 2011 |
| A Flexible System for Ontology Matching DuyHoa Ngo, Zohra Bellahsene & Remi Coletta In CAiSE Forum (Selected Papers). Lecture Notes in Business Information Processing., pp. 79-94. Springer, 2011. |
BibTeX:
@inproceedings{caise11,
author = {DuyHoa Ngo and |
| Matching and Alignment: What Is the Cost of User Post-Match Effort? - (Short Paper) Fabien Duchateau, Zohra Bellahsene & Remi Coletta In OTM Conferences., pp. 421-428, 2011. |
| Abstract: Generating new knowledge from scientific databases, fusioning products information of business companies or computing an overlap between various data collections are a few examples of applications that require data integration. A crucial step during this integration process is the discovery of correspondences between the data sources, and the evaluation of their quality. For this purpose, the overall metric has been designed to compute the post-match effort, but it suffers from major drawbacks. Thus, we present in this paper two related metrics to com- pute this effort. The former is called post-match effort, i.e., the amount of work that the user must provide to correct the correspondences that have been discovered by the tool. The latter enables the measurement of human-spared resources, i.e., the rate of automation that has been gained by using a matching tool. |
BibTeX:
@inproceedings{DBLP:conf/otm/DuchateauBC11,
author = {Fabien Duchateau and |
| Modeling View Selection as a Constraint Satisfaction Problem Imene Mami, Remi Coletta & Zohra Bellahsene In DEXA ., pp. 396-410, 2011. |
| Abstract: Using materialized views can highly speed up the query pro- cessing time. This paper deals with the view selection issue, which consists in finding a set of views to materialize that minimizes the expected cost of evaluating the query workload, given a limited amount of re- source such as total view maintenance cost and/or storage space. However, the solution space is huge since it entails a large number of possible combinations of views. For this matter, we have designed a solution in- volving constraint programming, which has proven to be a powerful approach for modeling and solving combinatorial problems. The efficiency of our method is evaluated using workloads consisting of queries over the schema of the TPC-H benchmark. We show experimentally that our approach provides an improvement in the solution quality (i.e., the quality of the obtained set of materialized views) in term of cost saving com- pared to genetic algorithm in limited time. Furthermore, our approach scales well with the query workload size. |
BibTeX:
@inproceedings{dexa11,
author = {Imene Mami and |
| YAM++ results for OAEI 2011 DuyHoa Ngo, Zohra Bellahsene & Remi Coletta In OM. CEUR Workshop Proceedings. Volume 814. CEUR-WS.org, 2011. |
| Abstract: The YAM++ system is a self configuration, flexible and extensible ontology matching system. The key idea behind YAM++ system is based on machine learning and similarity flooding approaches. In this paper, we briefly present the YAM++ and its results on Benchmark and Conference tracks on OAEI 2011 campaign. |
BibTeX:
@inproceedings{oaei11,
author = {DuyHoa Ngo and |
| A Generic Approach for Combining Linguistic and Context Profile Metrics in Ontology Matching DuyHoa Ngo, Zohra Bellahsene & Remi Coletta In OTM Conferences., pp. 800-807, 2011. |
| Abstract: Ontology matching is needed in many application domains. In this paper, we present a machine learning approach for combining metrics, which exploits various linguistic and context profiles features in order to discover mappings between entities of different ontologies. Our approach has been implemented and the experimental results over Benchmark and Conference test cases on OAEI 2010 campaign1 demonstrate its effectiveness and efficiency in terms of quality of matching and flexibility. |
BibTeX:
@inproceedings{odbase11,
author = {DuyHoa Ngo and |
| 2010 |
| FORUM: a flexible data integration system based on data semantics Zohra Bellahsene et al. SIGMOD Record. Vol. 39(2), pp. 11-18, 2010. |
BibTeX:
@article{sigmod10,
author = {Zohra Bellahsene and |
| 2009 |
| (Not) yet another matcher Fabien Duchateau, Remi Coletta, Zohra Bellahsene & Renee J. Miller In CIKM, Hong Kong, China, November 2-6, 2009., pp. 1537-1540, 2009. |
| Abstract: Discovering correspondences between schema elements is a crucial task for data integration. Most schema matching tools are semi-automatic, e.g. an expert must tune some parameters (thresholds, weights, etc.). They mainly use several methods to combine and aggregate similarity measures. However, their quality results often decrease when one requires to integrate a new similarity measure or when matching particular domain schemas. This paper describes YAM (Yet Another Matcher), which is a schema matcher factory. Indeed, it enables the generation of a dedicated matcher for a given schema matching scenario, according to user inputs. Our approach is based on machine learning since schema matchers can be seen as classifiers. Several bunches of experiments run against matchers generated by YAM and traditional matching tools show how our approach is able to generate the best matcher for a given scenario. |
BibTeX:
@inproceedings{cikm09,
author = {Fabien Duchateau and |
| YAM: a schema matcher factory Fabien Duchateau, Remi Coletta, Zohra Bellahsene & Renee J. Miller In CIKM , Hong Kong, China, November 2-6, 2009., pp. 2079-2080, 2009. |
| Abstract: In this paper, we present YAM, a schema matcher factory. YAM (Yet Another Matcher) is not (yet) another schema matching system as it enables the generation of a la carte schema matchers according to user requirements. These requirements include a preference for recall or precision, a training data set (schemas already matched) and provided expert correspondences. YAM uses a knowledge base that includes a (possibly large) set of similarity measures and classifiers. Based on the user requirements, YAM learns how to best apply these tools (similarity measures and classifiers) in concert to achieve the best matching quality. In our demonstration, we will let users apply YAM to build the best schema matcher for different user requirements. |
BibTeX:
@inproceedings{cikmDemo09,
author = {Fabien Duchateau and |
| 2008 |
| A Flexible Approach for Planning Schema Matching Algorithms Fabien Duchateau, Zohra Bellahsene & Remi Coletta In OTM, Mexico, November 9-14, 2008. Lecture Notes in Computer Science. Volume 5331, pp. 249-264. Springer, 2008. |
| Abstract: Mostoftheschemamatchingtoolsareassembledfrommultiplematch algorithms, each employing a particular technique to improve matching accu- racy and making matching systems extensible and customizable to a particular domain. Recently, it has been pointed out that the main issue is how to select the most suitable match algorithms to execute for a given domain and how to adjust the multiple knobs (e.g. threshold, performance, quality, etc.). The solutions provided by current schema matching tools consist in aggregating the results obtained by several match algorithms to improve the quality of the discovered matches. However, aggregation entails several drawbacks. In this article, we present a novel method for combining schema matching algorithms. The matching engine makes use of a decision tree to combine the most appropriate match algorithms. As a first consequence of using the decision tree, the performance of the system is improved since the complexity is bounded by the height of the decision tree. Thus, only a subset of these match algorithms is used during the matching process. The second advantage is the improvement of the quality of matches. Indeed, for a given domain, only the most suitable match algorithms are used. The experiments show the effectiveness of our approach w.r.t. other matching tools. |
BibTeX:
@inproceedings{otm08,
author = {Fabien Duchateau and |
| 2007 |
| Learning Implied Global Constraints Christian Bessiere, Remi Coletta & Thierry Petit In IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, January 6-12, 2007., pp. 44-49, 2007. |
| Abstract: Finding a constraint network that will be efficiently solved by a constraint solver requires a strong ex- pertise in Constraint Programming. Hence, there is an increasing interest in automatic reformulation. This paper presents a general framework for learning implied global constraints in a constraint network assumed to be provided by a non-expert user. The learned global constraints can then be added to the network to improve the solving process. We apply our technique to global cardinality constraints. Experiments show the significance of the approach. |
BibTeX:
@inproceedings{ijcai07implied,
author = {Christian Bessiere and |
| Query-Driven Constraint Acquisition Christian Bessiere, Remi Coletta, Barry O'Sullivan & Mathias Paulin In IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, January 6-12, 2007., pp. 50-55, 2007. |
| Abstract: The modelling and reformulation of constraint networks are recognised as important problems. The task of automatically acquiring a constraint net- work formulation of a problem from a subset of its solutions and non-solutions has been presented in the literature. However, the choice of such a subset was assumed to be made independently of the acquisition process. We present an approach in which an interactive acquisition system actively selects a good set of examples. We show that the number of examples required to acquire a constraint network is significantly reduced using our approach. |
BibTeX:
@inproceedings{ijcai07queries,
author = {Christian Bessiere and |
| 2006 |
| Acquiring Constraint Networks Using a SAT-based Version Space Algorithm Christian Bessiere, Remi Coletta, Frederic Koriche & Barry O'Sullivan In AAAI July 16-20, 2006, Boston, Massachusetts, USA., 2006. |
| Abstract: Constraint programming is a commonly used technology for solving complex combinatorial problems. However, users of this technology need significant expertise in order to model their problems appropriately. We propose a basis for addressing this problem: a new SAT-based version space algorithm for acquiring constraint networks from examples of solutions and non-solutions of a target problem. An important advan- tage of the algorithm is the ease with which domain-specific knowledge can be exploited. |
BibTeX:
@inproceedings{aaai06,
author = {Christian Bessiere and |
| 2005 |
| Acquiring Parameters of Implied Global Constraints Christian Bessiere, Remi Coletta & Thierry Petit In CP, Sitges, Spain, October 1-5, 2005, Proceedings., pp. 747-751, 2005. |
| Abstract: Many models may exist to encode a problem as a constraint satisfac- tion problem. One lack of constraint programming is the strong expertise required to build a model that leads to an efficient solving. Hence, there is an increasing interest in automatic reformulation of models. This paper presents a technique consisting of learning implied constraints from allowed and forbidden assign- ments of values to sets of variables. Such constraints can be added to a model to improve the solving process. We propose a general framework to learn parameterized implied constraints. We apply this framework to the case of the global cardinality constraint and we show by experiments the interest of our approach. |
BibTeX:
@inproceedings{cp05,
author = {Christian Bessiere and |
| A SAT-Based Version Space Algorithm for Acquiring Constraint Satisfaction Problems Christian Bessière, Remi Coletta, Frédéric Koriche & Barry O'Sullivan In Machine Learning: ECML 2005, 16th European Conference on Machine Learning, Porto, Portugal, October 3-7, 2005, Proceedings. Lecture Notes in Computer Science. Volume 3720, pp. 23-34. Springer, 2005. |
| Abstract: Constraint programming is a commonly used technology for solving complex combinatorial problems. However, users of this technology need significant expertise in order to model their problems appropriately. We propose a basis for address- ing this problem: a new SAT-based version space algorithm for acquiring constraint networks from examples of solutions and non-solutions of a target problem. An important advantage of the algorithm is the ease with which domain-specific knowledge can be exploited. |
BibTeX:
@inproceedings{ecml05,
author = {Christian Bessière and |
| Apprentissage de Contraintes Globales Implicites Remi Coletta, Christian Bessiere & Joël Quinqueton In Premières Journées Francophones de Programmation par Contraintes, Lens, du 8 au 10 juin 2005., pp. 249-258, 2005. |
BibTeX:
@inproceedings{jfpc05,
author = {Remi Coletta and |
| 2004 |
| Leveraging the Learning Power of Examples in Automated Constraint Acquisition Christian Bessire, Remi Coletta, Eugene C. Freuder & Barry O'Sullivan In CP, Toronto, Canada, September 27 - October 1, 2004. Lecture Notes in Computer Science. Volume 3258, pp. 123-137. Springer, 2004. |
| Abstract: Constraintprogrammingisrapidlybecomingthetechnologyofchoice for modeling and solving complex combinatorial problems. However, users of constraint programming technology need significant expertise in order to model their problem appropriately. The lack of availability of such expertise can be a significant bottleneck to the broader uptake of constraint technology in the real world. In this paper we are concerned with automating the formulation of con- straint satisfaction problems from examples of solutions and non-solutions. We combine techniques from the fields of machine learning and constraint programming. In particular we present a portfolio of approaches to exploiting the semantics of the constraints that we acquire to improve the efficiency of the acquisition process. We demonstrate how inference and search can be used to extract useful information that would otherwise be hidden in the set of examples from which we learn the target constraint satisfaction problem. We demonstrate the utility of the approaches on a case-study domain. |
BibTeX:
@inproceedings{cp04,
author = {Christian Bessire and |
| 2003 |
| Constraint Acquisition as Semi-Automatic Modeling Remi Coletta, Christian Bessiere, Barry O'Sullivan, Eugene C. Freuder, Sarah O'Connell & Joel Quinqueton In AI, Cambridge, UK 15th-17th December 2003., pp. 111-124, 2003. |
BibTeX:
@inproceedings{ai03,
author = {Remi Coletta and |
| Semi-automatic Modeling by Constraint Acquisition Remi Coletta, Christian Bessière, Barry O'Sullivan, Eugene C. Freuder, Sarah O'Connell & Joël Quinqueton In CP Kinsale, Ireland, September 29 - October 3, 2003, Proceedings. Lecture Notes in Computer Science. Volume 2833, pp. 812-816. Springer, 2003. |
| Abstract: Constraint programming is a technology which is now widely used to solve combinatorial problems in industrial applications. However, using it requires considerable knowledge and expertise in the field of constraint reasoning. This paper introduces a framework for automatically learning constraint networks from sets of instances that are either acceptable solutions or non-desirable as- signments of the problem we would like to express. Such an approach has the potential to be of assistance to a novice who is trying to articulate her constraints. By restricting the language of constraints used to build the network, this could also assist an expert to develop an efficient model of a given problem. This paper provides a theoretical framework for a research agenda in the area of interactive constraint acquisition, automated modelling and automated constraint program- ming. |
BibTeX:
@inproceedings{cp03,
author = {Remi Coletta and |
| Modélisation Semi-Automatique par Acquisition de Contraintes Remi Coletta, Christian Bessière & Joël Quinqueton In Neuvièmes Journées Nationales sur la résolution Pratique de Problèmes NP-Complets Amiens, du 17 au 19 Juin 2003., pp. 129-144, 2003. |
BibTeX:
@inproceedings{jnpc03,
author = {Remi Coletta and |
Created by JabRef