Search

International audience; In French, as well as in other Romance languages, attributive adjectives (A) can appear both before or after the noun (N): (1) une agréable soirée (anteposed) / une soirée agréable (postposed) ‘a nice evening’.Semantically, the general idea is that anteposed As tend to be subsective or intensional, whereas the postposed ones tend to be intersective (or predicative). However, there is no semantic property categorically associated with one position (Abeillé & Godard 1999). Thus, the semantics do not account for the entire phenomenon (contra Bouchard 1998) and the choice of the position is driven by the syntax. First, As followed by a dependent must be postposed to the N: (2) une musique agréable à écouter / *une agréable à écouter musique ‘a music nice to hear”This is the only categorical constraint; the other syntactic constraints do not impose, but rather favor one position over the other. For example, long and complex APs tend to be postposed, respecting the generalization that in SVO languages the “heavy” constituents tend to appear last (Behagel 1909, Hawkins 1994). This means that while long As as well as coordinations of As can appear in both positions as shown in (3), they tend to prefer postposition.(3) un petit et confortable canapé / un canapé petit et confortable ‘a small and comfortable sofa’In this paper, we focus on the syntactic aspects of adjective ordering. We postulate that this phenomenon is led by various factors interacting in a complex way and favoring one position over the other. Thus we need an experimental approach in order to determine which factors are indeed involved in the choice and how they interact. Our approach is based on experiences using corpus data and questionnaires. The methodology is inspired by the work by Bresnan et al. (2007) and Bresnan & Ford (2010) on dative alternation in English. Using statistical modeling (logistic regression – Agresti, 2007 – and mixed-effect models – Gelman & Hill, 2006), we tested syntactic factors found in the literature (Abeillé & Godard 1999, Wilmet 1981, Forsgren 1978 Blinkenberg 1933, a. o.) with attested data extracted from corpora. We assume that, with statistical tools, we are able to free ourselves from variations due to the sampling of the corpora. Moreover, one advantage of the mixed-effect logistic regression is that it is predictive, in the sense that one can build a model on a set of data and use this model to predict the choice between anteposition and postposition on unseen data. This way, we can evaluate how well the model generalizes from the training set. To build our database, we first extracted the attributive As that appeared in both positions in the syntactically annotated newspaper corpus French Treebank (FTB, Abeillé & Clément 2004), leaving aside As with post-adjectival dependents. We then extracted the same As from the spoken corpus C-ORAL-ROM (CORAL, Cresti & Moneglia 2005). These data were annotated for 10 variables concerning the syntactic environment of each A in context: (1) the A is coordinated, (2) the A is modified by an adverbial element; the NP contains (3) an other A in postposition, (4) a relative clause, (5) a PP; the determiner of the NP is (6) demonstrative, (7) possessive, (8) definite; a measure of collocation for (9) the ordered sequence A+N and (10) the ordered sequence N+A (collocations estimated with χ2, Manning & Schütze, 1999). We also differentiated two lemmas in context for 9 As: ancien ‘ancient/former’, pur ‘pure’, seul ‘alone/single’, simple ‘simple/modest’, sacré ‘sacred/brilliant’, commun ‘ordinary/shared’, pauvre ‘poor/unfortunate’, propre ‘own/clean’, cher ‘expensive/dear’. The database contains 6621 occurrences of attributive As (4994 in FTB, 1627 in CORAL) representing 171 lemmas, with 68.8% of anteposition (67% in FTB, 74.2% in CORAL). There is variation according to the lemmas: for instance, the A unique ‘unique’ is anteposed in 20% of the cases, whereas sérieux ‘serious’ appears in this position in 51,4% and petit ‘small’ in 98.6%. Moreover, there is less alternation in spoken data than in written ones: the 171 lemmas appear in both positions in FTB, while only 56 (25%) of them are really alternating in CORAL. This seems to reveal that in spoken French, the As tend to have a more fixed behavior than in the written variant. We hypothesize that in order to not put the A in its preferred position, that is the more frequent position, the syntactic conditions must strongly favor the non-preferred position in the case of spoken French. Multi-factorial statistical modeling We used mixed-effects logistic regression to estimate the probability that the anteposition will be chosen as a function of 11 predictive variables (the 10 syntactic variables and the mode of production: written or spoken). The construction of the model consists in estimating the coefficients that are associated with each variable. Besides the predictive variables, also called fixed effects, mixed-effects models are able to take into account the variation in the data by means of random-effects. In our case, the adjectival lemmas are the random effects in order to model the adjectival idiosyncrasies. We built a model with 11 fixed-effects and 1 random-effect. All the effects are significant and thus participate in predicting the position of the As. This model has a mean accuracy of 0.88 (10-fold cross-validation) and the mean concordance probability is C = 0.947 (10-fold cross-validation). These numbers indicate that the model’s predictions are very accurate.Results Each coefficient associated with fixed-effects can be interpreted as the preference for a position: a positive coefficient indicates a preference for anteposition and a negative one for postposition. Thus the model shows that the nature of the determiner influences the position: demonstrative, possessive and definite determiners favor the anteposition. Moreover, APs containing coordinated As or adverbial modifiers tend to be postposed, which confirms that speakers tend to put “heavy” APs after the N. The occurrence of a relative clause, a PP or another A after the N also favors the anteposition. Finally, the N the A is combined with affects the choice: the more the A and the N tend to be a collocation in a given order, as in à justeA titreN ‘understandably’, the more the sequence tend to occur in the given order. The corpus model estimates the probability of anteposition of each adjectival occurrence given the syntactic environment and taking into account the specificities of each lemma (random-effect). A questionnaire experiment was then conducted to test whether these probabilities are related to the judgments of native speakers. Our hypothesis is that, for many speakers, the frequency of choice for anteposition will correspond to the probability of anteposition estimated in the corpus model. In this study, participants had to choose the preferred order for an A N sequence in context. The questionnaire is made up of 29 sentences extracted from the database (FTB part) and selected according to their probability in order to have a sample containing the all range of possible probabilities (from 0 to 1). For each tested A, the participant sees a pair of sentences: the original sentence and a modified version with the sequence A N in the opposite order. In both versions of the sentence, the NP is in bold and colored letters in order to help the participant to notice the difference in the pair. The pairs and the sentences within the pairs are randomly ordered in each questionnaire. The participants were contacted via social networks and scientific mailing lists. 141 participants completed the questionnaire online.As predicted, the proportion of choice for anteposed As significantly correlates with the probability of anteposition estimated in the corpus model: 0.74 (p.value < 0.0001). The correlation suggests that speakers tend to be sensitive to the syntactic constraints used in the corpus model and thus that the statistical modeling proposed on the basis of usage data is an appropriate way of describing and accounting for a rather complex syntactic phenomenon such as attributive A alternation. This result is in accordance with Bresnan’s (2007) experimental work, which suggests that the implicit knowledge of the language “is more powerful than has been recognized under the idealizations of categorical models of grammaticality”. Other Romance languages also display the attributive A alternation: (4) Italian: / un triste racconto / un racconto triste‘a sad story’(5) Romanian: o tristă poveste / o poveste tristă‘a sad story’(6) Portuguese: um imenso escritorio / um escritorio imenso ‘a huge office’(7) Spanish: un inmenso escritorio / un escritorio inmenso‘a huge office’Our study on French data suggests that this phenomenon should be analyzed in the light of quantitative and experimental approaches in other Romance languages. Using the same kind of statistical modeling employed here will allow us to observe and quantify cross-linguistic differences and similarities. Selected References: Abeillé A. & Godard D. 1999, La position de l’adjectif épithète en français : le poids des mots. Recherches Linguistiques de Vincennes, 28, 9-32. Agresti, A. 2007. An Introduction to Categorical Data Analysis. Wiley. Behaghel O. 1909, “Von deutsher wortstellung”, Insogermanische Forschungen, 25. Blinkenberg A. 1933, L’ordre des mots en français moderne. Deuxième partie, Copenhague : Levin & Munksgaard. Bresnan J. 2007, Is syntactic knowledge probabilistic ? Experiments with the English dative alternation, In S. Featherston & W. Sternefeld, Eds., Roots : Linguistics in Search of Its Evidential Base, p. 77-96. Berlin : Mouton de Gruyter. Bresnan, J., A. Cueni, T. Nikitina, and H. Baayen. 2007. Predicting the dative alternation. In Boume, Kraemer, and Zwarts (Eds.), Cognitive Foundations of Interpretation. Amsterdam: Royal Netherlands Academy of Science. Bresnan, J. & M. Ford, 2010, “Predicting syntax: Processing dative constructions in American and Australian varieties of English” Language 86 (1). Forsgren M. 1978. La place de l’adjectif épithète en français contemporain, étude quantitative et sémantique. Stockholm : Almqvist & Wilksell. Gelman, A. & J. Hill, 2006, Data Analysis Using Regression and Multilevel/ Hierarchical Models, Cambridge: Cambridge University Press. Hawkins, J. 1994, A performance theory of order and constituency, Cambridge: Cambridge University Press. Manning, C. D. & H. Schütze, 1999, Foundations of Statistical Natural Language Processing, Cambridge, MA : The MIT Press. Wilmet M. 1981, La place de l’épithète qualificative en français contemporain : étude grammaticale et stylistique, Revue de linguistique romane, 45, 17-73.

Many practical applications of control require that constraints on the inputs and states of the system be respected, while optimizing some performance criterion. In the presence of model uncertainties or disturbances, for many control applications it suffices to keep the state constraints at least for a prescribed share of the time, as e.g. in building climate control or load mitigation for wind turbines. For such systems, a new control method of Scenario-Based Model Predictive Control (SCMPC) is presented in this paper. It optimizes the control inputs over a finite horizon, subject to robust constraint satisfaction under a finite number of random scenarios of the uncertainty and/or disturbances. While previous approaches have shown to be conservative (i.e. to stay far below the specified rate of constraint violations), the new method is the first to account for the special structure of the MPC problem in order to significantly reduce the number of scenarios. In combination with a new framework for interpreting the probabilistic constraints as average-in-time, rather than pointwise-in-time, the conservatism is eliminated. The presented method retains the essential advantages of SCMPC, namely the reduced computational complexity and the handling of arbitrary probability distributions. It also allows for adopting sample-and-remove strategies, in order to trade performance against computational complexity., Pre-print submitted to Automatica

In decision making problems where we need to choose a particular decision or alternative from a set of possible choices, we often have some preferences which determine if we prefer one decision over another. When these preferences give us an ordering on the decisions that is complete, then it is easy to choose the best or one of the best decisions. However it often occurs that the preferences relation is partially ordered, and we have no best decision. In this thesis, we look at what happens when we have such a partial order over a set of decisions, in particular when we have multiple orderings on a set of decisions, and we present a framework for qualitative decision making. We look at the different natural notions of optimal decision that occur in this framework, which gives us different optimality classes, and we examine the relationships between these classes. We then look in particular at a qualitative preference relation called Sorted-Pareto Dominance, which is an extension of Pareto Dominance, and we give a semantics for this relation as one that is compatible with any order-preserving mapping of an ordinal preference scale to a numerical one. We apply Sorted-Pareto dominance to a Soft Constraints setting, where we solve problems in which the soft constraints associate qualitative preferences to decisions in a decision problem. We also examine the Sorted-Pareto dominance relation in the context of our qualitative decision making framework, looking at the relevant optimality classes for the Sorted-Pareto case, which gives us classes of decisions that are necessarily optimal, and optimal for some choice of mapping of an ordinal scale to a quantitative one. We provide some empirical analysis of Sorted-Pareto constraints problems and examine the optimality classes that result.

We extend Constraint Automata by replacing boolean constraints with semiring-based soft constraints. The obtained general formal tool can be used to represent preference-based and similarity-based queries, which allow a user more freedom in choosing the behavior of the service to finally use, among all possible choices. A user states his preferences through a “soft” query, and obtains results that satisfy this query with different levels of preference. The soft requirements may involve a parameter data of the service operations, or the (names of the) operations themselves. Moreover, we introduce a first implementation of the search procedure by using declarative (Soft) Constraint Programming.

We extend algorithms for local arc consistency proposed in the literature in order to deal with (absorptive) semirings that may not be invertible. As a consequence, these consistency algorithms can be used as a pre-processing procedure in soft Constraint Satisfaction Problems (CSPs) defined over a larger class of semirings, such as those obtained from the Cartesian product of two (or more) semirings. One important instance of this class of semirings is adopted for multi-objective CSPs. First, we show how a semiring can be transformed into a novel one where the + operator is instantiated with the least common divisor (LCD) between the elements of the original semiring. The LCD value corresponds to the amount we can ''safely move'' from the binary constraint to the unary one in the arc consistency algorithm. We then propose a local arc consistency algorithm which takes advantage of this LCD operator.

Timetabling is the task of assigning sets of events to periods of time, taking into account resource-constraints and preferences among assignments. It is a well-studied field of research and is generally recognized to be a hard problem, both from the perspective of encoding it as from a computational point of view. In recent years, there has been increased interest in combining efficient search algorithms with modelling languages capable of high-level representations of real-world domains. Research into such systems is conducted, a.o., in the fields of Constraint Programming and Knowledge Representation. In this paper, we investigate the use of the modelling language of first-order logic extended with constructs such as aggregates, types, definitions and arithmetic, and the \idp system, which implements model generation for this language, to the timetabling problem. We show the feasibility of the approach and argue that there are important advantages both from the modelling point of view, leading to natural representation of the problem, and from the solving point of view, taking advantage of efficient automated search techniques like SAT and constraint propagation. ispartof: pages:31-45 ispartof: Proceedings of the 11th workshop on Preferences and Soft Constraints (SofT 2011) pages:31-45 ispartof: Workshop on Preferences and Soft Constraints location:Perugia date:12 Sep - 12 Sep 2011 status: published

The constraint satisfaction problem (CSP) is a central generic problem in computer science and artificial intelligence: it provides a common framework for many theoretical problems as well as for many real-life applications. Valued constraint problems are a generalisation of the CSP which allow the user to model optimisation problems. Considerable effort has been made in identifying properties which ensure tractability in such problems. In this work, we initiate the study of hybrid tractability of valued constraint problems; that is, properties which guarantee tractability of the given valued constraint problem, but which do not depend only on the underlying structure of the instance (such as being tree-structured) or only on the types of valued constraints in the instance (such as submodularity). We present several novel hybrid classes of valued constraint problems in which all unary constraints are allowed, which include a machine scheduling problem, constraint problems of arbitrary arities with no overlapping nogoods, and the SoftAllDiff constraint with arbitrary unary valued constraints. An important tool in our investigation will be the notion of forbidden substructures.

Öbekleme önemli bir insan aktivitesidir. Aynı özellikleri paylaşan nesne grupları insanların dünyayı algılamasında ve tanımlamasında önemli rol oynar. Öbekleme birçok uygulama alanına sahiptir. Gerçek dünya uygulamaları çeşitli kısıtları sağlayacak şekilde bir öbekleme analizini gerektirir. Fakat, özellikle çok boyutlu ve/veya hacimli veri kümeleri söz konusu olduğunda, yalnızca öbekleme parametrelerine dayanarak anlamlı öbekler yaratmak zor olabilmektedir. Bundan dolayı, birçok uygulamada kullanıcının seçimleri ve koyduğu kısıtların göz önüne alınması istenir. Bizim çalışmamızda esnek kısıtlar kullanılarak, kesişmeyen kısmi öbeklemelerin elde edilmesi hedeflenmiştir. Öbeklemelerin yerine getirilmesi ve verilen kısıtları sağlamada ne kadar başarılı olduğunu ölçmek için bulanık, olasılıksal ve ağırlıklı yarı halka modelleri kullanılmıştır. Optimizasyon için ise genetik algoritmalardan faydalanılmıştır. Bahsi geçen işlemlerin gerçekleştirilmesinde kullanılmak üzere Java programlama dili kullanılarak bir araç geliştirilmiştir. Geliştirilen araç esnek kısıtların tanımlanması, öbekleme algoritmalarının çalıştırılması, veri kümeleri ve öbeklemelerin görsel olarak gösterilmesi, sonuçların hesaplanması ve öbek doğrulama yöntemlerinin kullanılmasını sağlamaktadır. Bu araçtan faydalanılarak seçilen veri kümeleri üzerinde kullanıcı tanımlı esnek kısıtlarına göre anlamlı öbekler oluşturmaya çalışan deneysel çalışmalar da yapılmıştır. Deney sonuçları kapsamlı olarak sunulmuş ve sonuçlar analiz edilmiştir., Clustering is an important human activity. Object groups sharing the same characteristics have a significant role in human perception of the world. Clustering has many application areas. Real world applications demand for cluster analysis which satisfies various user/domain constraints. But, it becomes an important challenge to obtain meaningful clusters by solely tuning clustering parameters, especially when high dimensional and/or high volume data sets are considered. As a result, in many of such applications, user preferences and domain constraints should be taken into consideration. The objective with this work is to obtain disjoint partial clusterings by employing soft constraints. Fuzzy, probabilistic and weighted semi-rings are used to do the clustering and as well to assess the degree of soft constraints satisfaction. Genetic algorithms are used for optimization purposes. A tool, written in Java, is developed to implement what is considered. The tool has the capability of accepting/exploiting user defined soft constraints, executing clustering algorithms, displaying data sets and resulting clusterings, and calculating the clustering metrics and validity indices. The tool is experimentally evaluated on select datasets to obtain soft constraints based clusterings. To assess the performance, extensive experimental results are presented and analyzed.

Websites aiming to assist users in finding a new house are becoming increasingly popular. Finding a potential relevant house is based on the users’ search criteria and the ability to define these criteria in an easy-to-use search user interface. Due to hard constraints, over-specification is one of the problems many users encounter when searching for a house online. In this paper, we propose a soft constraint based search user interface for the housing domain. Our analysis of existing websites and user opinions suggests the need for an interface with more flexibility towards the user, with a focus on ranking relevant items according to the user’s weighted importance for selected filters. The proposed interface design is evaluated with five potential users and reflects on the impact and possible improvements.

Preferences and uncertainty are common in many real-life problems. In this paper, we focus on bipolar preferences and on uncertainty modelled via uncontrollable variables, and we assume that uncontrollable variables are specified by possibility distributions over their domains. To tackle such problems, we concentrate on uncertain bipolar problems with totally ordered preferences, and we eliminate the uncertain part of the problem, while making sure that some desirable properties hold about the robustness of the problem and its relationship with the preference of the optimal solutions. We also consider several semantics to order the solutions according to different attitudes with respect to the notions of preference and robustness.

This paper examines the justification for the hypothesis of extended cognition (HEC). HEC claims that human cognitive processes can, and often do, extend outside our head to include objects in the environment. HEC has been justified by inference to the best explanation (IBE). Both advocates and critics of HEC claim that we can infer the truth value of HEC based on whether HEC makes a positive or negative explanatory contribution to cognitive science. I argue that IBE cannot play this epistemic role. A serious rival to HEC exists with a differing truth value, and this invalidates IBEs for both the truth and the falsity of HEC. Explanatory value to cognitive science is not a guide to the truth value of HEC.

We present a formal model to represent and solve the unicast/multicast routing problem in networks with Quality of Service (QoS) requirements. To attain this, first we translate the network adapting it to a weighted graph (unicast) or and-or graph (multicast), where the weight on a connector corresponds to the multidimensional cost of sending a packet on the related network link: each component of the weights vector represents a different QoS metric value (e.g. bandwidth, cost, delay, packet loss). The second step consists in writing this graph as a program in Soft Constraint Logic Programming (SCLP): the engine of this framework is then able to find the best paths/trees by optimizing their costs and solving the constraints imposed on them (e.g. delay < 40msec), thus finding a solution to QoS routing problems. Moreover, c-semiring structures are a convenient tool to model QoS metrics. At last, we provide an implementation of the framework over scale-free networks and we suggest how the performance can be improved., 45 pages

We extend algorithms for arc consistency proposed in the literature in order to deal with (absorptive) semirings that are not invertible. As a consequence, these consistency algorithms can be used as a pre-processing procedure in soft Constraint Satisfaction Problems (CSPs) defined over a larger class of semirings: among other instances, for those semirings obtained as the cartesian product of any family of semirings. The main application is that the new arc consistency algorithm can be used for multi-criteria soft CSPs. To reach this objective, we first show that any semiring can be transformed into a new one where the + operator is instantiated with the Least Common Divisor (LCD) between the elements of the original semiring. The LCD value corresponds to the amount we can "safely move" from the binary constraint to the unary one in the arc consistency algorithm (when the × operator of the semiring is not idempotent). We then propose an arc consistency algorithm which takes advantage of this LCD operator.

Real-life problems present several kinds of preferences. We focus on problems with both positive and negative preferences, which we call bipolar preference problems. Although seemingly specular notions, these two kinds of preferences should be dealt with differently to obtain the desired natural behaviour. We technically address this by generalising the soft constraint formalism, which is able to model problems with one kind of preference. We show that soft constraints model only negative preferences, and we add to them a new mathematical structure which allows to handle positive preferences as well. We also address the issue of the compensation between positive and negative preferences, studying the properties of this operation. Finally, we extend the notion of arc consistency to bipolar problems, and we show how branch and bound (with or without constraint propagation) can be easily adapted to solve such problems.

Many computational problems linked to uncertainty and preference management can be expressed in terms of computing the marginal(s) of a combination of a collection of valuation functions. Shenoy and Shafer showed how such a computation can be performed using a local computation scheme. A major strength of this work is that it is based on an algebraic description: what is proved is the correctness of the local computation algorithm under a few axioms on the algebraic structure. The instantiations of the framework in practice make use of totally ordered scales. The present paper focuses on the use of partially ordered scales and examines how such scales can be cast in the Shafer---Shenoy framework and thus benefit from local computation algorithms. It also provides several examples of such scales, thus showing that each of the algebraic structures explored here is of interest.

International audience; The Valued Constraint Satisfaction Problem (VCSP) is a generic optimization problem defined by a network of local cost functions defined over discrete variables. It has applications in Artificial Intelligence, Operations Research, Bioinformatics and has been used to tackle optimization problems in other graphical models (including discrete Markov Random Fields and Bayesian Networks). The incremental lower bounds produced by local consistency filtering are used for pruning inside Branch and Bound search. In this paper, we extend the notion of arc consistency by allowing fractional weights and by allowing several arc consistency operations to be applied simultaneously. Over the rationals and allowing simultaneous operations, we show that an optimal arc consistency closure can theoretically be determined in polynomial time by reduction to linear programming. This defines Optimal Soft Arc Consistency (OSAC). To reach a more practical algorithm, we show that the existence of a sequence of arc consistency operations which increases the lower bound can be detected by establishing arc consistency in a classical Constraint Satisfaction Problem (CSP) derived from the original cost function network. This leads to a new soft arc consistency method, called, Virtual Arc Consistency which produces improved lower bounds compared with previous techniques and which can solve submodular cost functions. These algorithms have been implemented and evaluated on a variety of problems, including two difficult frequency assignment problems which are solved to optimality for the first time. Our implementation is available in the open source toulbar2 platform.

Several types of constraints must be satisfied by schedules of real world sports leagues, e. g. stadium unavailability, fixed matches, forbidden matches, minimum number of breaks. Taking into account such constraints, determining a feasible schedule becomes a challenging task. Usually, there is no schedule satisfying all given constraints and, hence, some of the constraints are considered as 'soft' ones. There are various models appropriately describing the environment of real sport leagues. Only heuristic methods are known from the literature for solving instances of such models for real dimensions. We consider here a model which satisfies the demands of many sports leagues. We solve our model by a method which consists in formulating the problem as series of instances of the propositional satisfiability problem and adaption of a satisfiability solver for these specific instances. We test our method on two real world sports leagues and solve the problem optimally in each case. Our solver shows good computational results also on generated test instances, which are motivated by real life requirements of sports league scheduling. Our solver can be easily extended to meet the demands of other sports leagues.

The notion of optimality naturally arises in many areas of applied mathematics and computer science concerned with decision making. Here we consider this notion in the context of two formalisms used for different purposes and in different research areas: graphical games and soft constraints. We relate the notion of optimality used in the area of soft constraint satisfaction problems (SCSPs) to that used in graphical games, showing that for a large class of SCSPs that includes weighted constraints every optimal solution corresponds to a Nash equilibrium that is also a Pareto efficient joint strategy.We also study alternative mappings including one that maps graphical games to SCSPs, for which Pareto efficient joint strategies and optimal solutions coincide.

The notion of optimality naturally arises in many areas of applied mathematics and computer science concerned with decision making. Here we consider this notion in the context of two formalisms used for different purposes and in different research areas: graphical games and soft constraints. We relate the notion of optimality used in the area of soft constraint satisfaction problems (SCSPs) to that used in graphical games, showing that for a large class of SCSPs that includes weighted constraints every optimal solution corresponds to a Nash equilibrium that is also a Pareto efficient joint strategy.

The notion of optimality naturally arises in many areas of applied mathematics and computer science concerned with decision making. Here we consider this notion in the context of three formalisms used for different purposes in reasoning about multi-agent systems: strategic games, CP-nets, and soft constraints. To relate the notions of optimality in these formalisms we introduce a natural qualitative modification of the notion of a strategic game. We show then that the optimal outcomes of a CP-net are exactly the Nash equilibria of such games. This allows us to use the techniques of game theory to search for optimal outcomes of CP-nets and vice-versa, to use techniques developed for CP-nets to search for Nash equilibria of the considered games. Then, we relate the notion of optimality used in the area of soft constraints to that used in a generalization of strategic games, called graphical games. In particular we prove that for a natural class of soft constraints that includes weighted constraints every optimal solution is both a Nash equilibrium and Pareto efficient joint strategy. For a natural mapping in the other direction we show that Pareto efficient joint strategies coincide with the optimal solutions of soft constraints., Comment: 39 pages. To appear in Annals of Mathematics and Artificial Intelligence

Por vezes com a utilização, real, dos sistemas de informação somos confrontados com situações cujo carácter excepcional não permite, ao modelador de sistemas de informação, representar todas as propriedades que revestem as relações entre as entidades do mundo real. Isto acontece porque as associações entre classes de objectos, que representam as entidades do mundo real, dependem de restrições rígidas, verificadas por um valor “sim” ou “não” das quais depende a formação dos objectos da associação. Nestes casos não basta retirar a restrição imposta e permitir a associação, porque a representação da realidade sairia empobrecida, em vez disso torna-se necessário o enriquecimento gráfico e semântico do diagrama de classes da UML, possibilitando a caracterização de um novo tipo de restrição: a restrição deôntica. É proposta uma metodologia de levantamento e descrição de casos reais em que a utilização de sistemas de informação justifique a utilização de restrições deônticas. Através dos mecanismos de extensão da uml e do recurso à linguagem de modelação ocl pretende-se definir uma representação genérica, a aplicar a estes casos. Em qualquer sistema de informação é fundamental preservar a persistência da informação, assim o modelo relacional será utilizado para o efeito. Como o diagrama de classes implementa o modelo orientado ao objecto é necessário proceder ao mapeamento do diagrama de classes para o modelo relacional, para o efeito é proposta uma metodologia que assenta na aplicação nas regras generalistas de mapeamento entre os dois modelos; seguidas da criação de tabelas adicionais para mapear e preservar a informação relativa às restrições deônticas; e da criação de uma estrutura de triggers que implementam a semântica, ou seja o comportamento esperado das restrições deônticas. Pretende-se após representação, no diagrama de classes, do sistema, e das restrições deônticas, que seja criado automaticamente o diagrama relacional que lhes corresponde. Para o efeito é proposto o desenvolvimento de uma aplicação, em Prolog, que lê os dados do diagrama de classes, processa os mesmos, e finalmente, cria automaticamente, a estrutura relacional correspondente. Sometimes we are faced with exceptional situations that cannot be represented, by the modeler, as they exist in the real world. This happens because the associations between object classes, that represent the real world entities, depend on strong constraints, verified by a value "yes" or "no", on which depends the creation of the association objects. In these cases it is not enough to remove the restriction imposed and allow the association, because this would impoverished reality demonstration, instead it is necessary to enrich the graphical and semantic representation of the UML class diagram, allowing the characterization of a new type of restriction called deontic, or soft, constraint. A methodology for survey and description of actual cases in which the use of information systems justify the application use of soft constraints, is proposed. Through the extension mechanisms of UML and the use of OCL modeling language, it is intended to define a generic representation, to apply to such cases. In any information system it is essential to preserve the persistence of information, so the relational model will be used for this purpose. As the diagram of classes implements the object oriented model it is necessary to map from this model to the relational one. To achieve this it is proposed a methodology based on the application of general mapping rules between the two models; followed by the creation of additional tables, to map and preserve the information of soft constraints; and the creation of trigger structures that implement the semantics, or in other words the expected behavior, of those kinds of constraints. After representation in the class diagram of the system and soft constraints, it is intended to be automatically created the relational diagram that represents them. The aim is to develop an application in Prolog, which reads data from the diagram of classes, processes them, and finally, automatically generates the correspondent relational structure.

The paradigm of pattern discovery based on constraints was introduced with the aim of providing to the user a tool to drive the discovery process towards potentially interesting patterns, with the positive side effect of achieving a more efficient computation. So far the research on this paradigm has mainly focused on the latter aspect: the development of efficient algorithms for the evaluation of constraint-based mining queries. Due to the lack of research on methodological issues, the constraint-based pattern mining framework still suffers from many problems which limit its practical relevance. In this paper, we analyze such limitations and we show how they flow out from the same source: the fact that in the classical constraint-based mining, a constraint is a rigid boolean function which returns either true or false. Indeed, interestingness is not a dichotomy. Following this consideration, we introduce the new paradigm of pattern discovery based on Soft Constraints, where constraints are no longer rigid boolean functions. Albeit based on a simple idea, our proposal has many merits: it provides a rigorous theoretical framework, which is very general (having the classical paradigm as a particular instance), and which overcomes all the major methodological drawbacks of the classical constraint-based paradigm, representing an important step further towards practical pattern discovery.

Soft constraints extend classical constraints to represent multiple consistency levels, and thus provide a way to express preferences, fuzziness, and uncertainty. While there are many soft constraint solving formalisms, even distributed ones, by now there seems to be no concurrent programming framework where soft constraints can be handled. In this paper we show how the classical concurrent constraint (cc) programming framework can work with soft constraints, and we also propose an extension of cc languages which can use soft constraints to prune and direct the search for a solution. We believe that this new programming paradigm, called soft cc (scc), can be also very useful in many web-related scenarios. In fact, the language level allows web agents to express their interaction and negotiation protocols, and also to post their requests in terms of preferences, and the underlying soft constraint solver can find an agreement among the agents even if their requests are incompatible., Comment: 25 pages, 4 figures, submitted to the ACM Transactions on Computational Logic (TOCL), zipped files

The paradigm of pattern discovery based on constraints was introduced with the aim of providing to the user a tool to drive the discovery process towards potentially interesting patterns, with the positive side effect of achieving a more effcient computation. So far the research on this paradigm has mainly focussed on the latter aspect: the development of effcient algorithms for the evaluation of constraint-based mining queries. Due to the lack of research on methodological issues, the constraint-based pattern mining framework still suffers from many problems which limit its practical relevance. As a solution, in this paper we introduce the new paradigm of pattern discovery based on Soft Constraints. Albeit simple, the proposed paradigm overcomes all the major methodological drawbacks of the classical constraint-based paradigm, representing an important step further towards practical pattern discovery.

Security protocols stipulate how the remote principals of a computer network should interact in order to obtain specific security goals. The crucial goals of confidentiality and authentication may be achieved in various forms, each of different strength. Using soft (rather than crisp) constraints, we develop a uniform formal notion for the two goals. They are no longer formalised as mere yes/no properties as in the existing literature, but gain an extra parameter, the security level. For example, different messages can enjoy different levels of confidentiality, or a principal can achieve different levels of authentication with different principals. The goals are formalised within a general framework for protocol analysis that is amenable to mechanisation by model checking. Following the application of the framework to analysing the asymmetric Needham-Schroeder protocol, we have recently discovered a new attack on that protocol as a form of retaliation by principals who have been attacked previously. Having commented on that attack, we then demonstrate the framework on a bigger, largely deployed protocol consisting of three phases, Kerberos., 29 pages, To appear in Theory and Practice of Logic Programming (TPLP) Paper for Special Issue (Verification and Computational Logic)

Soft constraints are a generalization of classical constraints, which allow for the description of preferences rather than strict requirements. In soft constraints, constraints and partial assignments are given preference or importance levels, and constraints are combined according to combinators which express the desired optimization criteria. On the other hand, constraint handling rules (CHR) constitute a high-level natural formalism to specify constraint solvers and propagation algorithms. We present a framework to design and specify soft constraint solvers by using CHR. In this way, we extend the range of applicability of CHR to soft constraints rather than just classical ones, and we provide a straightforward implementation for soft constraint solvers.

We describe a set of necessary conditions that are useful for generating propagation algorithms for the cardinality operator as well as for over-constrained problems with preferences. Constructive disjunction as well as the entailments rules originally proposed for the cardinality operator can be seen as simple cases of these necessary conditions. In addition these necessary conditions have the advantage of providing more pruning.

Local computation in join trees or acyclic hypertrees has been shown to be linked to a particular algebraic structure, called valuation algebra. There are many models of this algebraic structure ranging from probability theory to numerical analysis, relational databases and various classical and non-classical logics. It turns out that many interesting models of valuation algebras may be derived from semiring valued mappings. In this paper we study how valuation algebras are induced by semirings and how the structure of the valuation algebra is related to the algebraic structure of the semiring. In particular, c-semirings with idempotent multiplication induce idempotent valuation algebras and therefore permit particularly efficient architectures for local computation. Also important are semirings whose multiplicative semigroup is embedded in a union of groups. They induce valuation algebras with a partially defined division. For these valuation algebras, the well-known architectures for Bayesian networks apply. We also extend the general computational framework to allow derivation of bounds and approximations, for when exact computation is not feasible.

Clustering is an important human activity. Object groups sharing the same characteristics have a significant role in human perception of the world. Clustering has many application areas. Real world applications demand for cluster analysis which satisfies various user/domain constraints. But, it becomes an important challenge to obtain meaningful clusters by solely tuning clustering parameters, especially when high dimensional and/or high volume data sets are considered. As a result, in many of such applications, user preferences and domain constraints should be taken into consideration. The objective with this work is to obtain disjoint partial clusterings by employing soft constraints. Fuzzy, probabilistic and weighted semi-rings are used to do the clustering and as well to assess the degree of soft constraints satisfaction. Genetic algorithms are used for optimization purposes. A tool, written in Java, is developed to implement what is considered. The tool has the capability of accepting/exploiting user defined soft constraints, executing clustering algorithms, displaying data sets and resulting clusterings, and calculating the clustering metrics and validity indices. The tool is experimentally evaluated on select datasets to obtain soft constraints based clusterings. To assess the performance, extensive experimental results are presented and analyzed., Öbekleme önemli bir insan aktivitesidir. Aynı özellikleri paylaşan nesne grupları insanların dünyayı algılamasında ve tanımlamasında önemli rol oynar. Öbekleme birçok uygulama alanına sahiptir. Gerçek dünya uygulamaları çeşitli kısıtları sağlayacak şekilde bir öbekleme analizini gerektirir. Fakat, özellikle çok boyutlu ve/veya hacimli veri kümeleri söz konusu olduğunda, yalnızca öbekleme parametrelerine dayanarak anlamlı öbekler yaratmak zor olabilmektedir. Bundan dolayı, birçok uygulamada kullanıcının seçimleri ve koyduğu kısıtların göz önüne alınması istenir. Bizim çalışmamızda esnek kısıtlar kullanılarak, kesişmeyen kısmi öbeklemelerin elde edilmesi hedeflenmiştir. Öbeklemelerin yerine getirilmesi ve verilen kısıtları sağlamada ne kadar başarılı olduğunu ölçmek için bulanık, olasılıksal ve ağırlıklı yarı halka modelleri kullanılmıştır. Optimizasyon için ise genetik algoritmalardan faydalanılmıştır. Bahsi geçen işlemlerin gerçekleştirilmesinde kullanılmak üzere Java programlama dili kullanılarak bir araç geliştirilmiştir. Geliştirilen araç esnek kısıtların tanımlanması, öbekleme algoritmalarının çalıştırılması, veri kümeleri ve öbeklemelerin görsel olarak gösterilmesi, sonuçların hesaplanması ve öbek doğrulama yöntemlerinin kullanılmasını sağlamaktadır. Bu araçtan faydalanılarak seçilen veri kümeleri üzerinde kullanıcı tanımlı esnek kısıtlarına göre anlamlı öbekler oluşturmaya çalışan deneysel çalışmalar da yapılmıştır. Deney sonuçları kapsamlı olarak sunulmuş ve sonuçlar analiz edilmiştir.

This paper constructs a logic of soft constraints where the set of degrees of preference forms a partially ordered set. When the partially ordered set is a distributive lattice, this reduces to the idempotent semiring-based CSP approach, and the lattice operations can be used to define a sound and complete proof theory. For the general case, it is shown how sound and complete deduction can be performed by using a particular embedding of a partially ordered set in a distributive lattice.

We present a new generic problem solving approach for over-constrained problems based on Max-SAT. We first define a Boolean clausal form formalism, called soft CNF formulas, that deals with blocks of clauses instead of individual clauses, and that allows one to declare each block either as hard (i.e., must be satisfied by any solution) or soft (i.e., can be violated by some solution). We then present two Max-SAT solvers that find a truth assignment that satisfies all the hard blocks of clauses and the maximum number of soft blocks of clauses. Our solvers are branch and bound algorithms equipped with original lazy data structures, powerful inference techniques, good quality lower bounds, and original variable selection heuristics. Finally, we report an experimental investigation on a representative sample of instances (random 2-SAT, Max-CSP, graph coloring, pigeon hole and quasigroup completion) which provides experimental evidence that our approach is very competitive compared with the state-of-the-art approaches developed in the CSP and SAT communities. Research partially supported by projects TIN2004-07933-C03-03 and TIC2003-00950 funded by the Ministerio de Educacion y Ciencia. The second author is supported by a grant Ramon y Cajal.

Substitutability and interchangeability in constraint satisfaction problems (CSPs) have been used as a basis for search heuristics, solution adaptation and abstraction techniques. In this paper, we consider how the same concepts can be extended to soft constraint satisfaction problems (SCSPs). We introduce two notions: threshold alpha and degradation factor delta for substitutability and interchangeability, ( (alpha) substitutability/interchangeability and (delta) substitutability/interchangeabi-lity respectively). We show that they satisfy analogous theorems to the ones already known for hard constraints. In (alpha) interchangeability, values are interchangeable in any solution that is better than a threshold alpha, thus allowing to disregard differences among solutions that are not sufficiently good anyway. In (delta) interchangeability, values are interchangeable if their exchange could not degrade the solution by more than a factor of delta. We give efficient algorithms to compute ( (delta) / (alpha) )interchangeable sets of values for a large class of SCSPs, and show an example of their application. Through experimental evaluation based on random generated problem we measure first, how often neighborhood interchangeable values are occurring, second, how well they can approximate fully interchangeable ones, and third, how efficient they are when used as preprocessing techniques for branch and bound search.

The work presented in this thesis concerns the problem of timetabling at universities – particularly course-timetabling, and examines the various ways in which metaheuristic techniques might be applied to these sorts of problems. Using a popular benchmark version of a university course timetabling problem, we examine the implications of using a “twostaged” algorithmic approach, whereby in stage-one only the mandatory constraints areconsidered for satisfaction, with stage-two then being concerned with satisfying the remaining constraints but without re-breaking any of the mandatory constraints in the process. Consequently, algorithms for each stage of this approach are proposed and analysed in detail.For the first stage we examine the applicability of the so-called Grouping Genetic Algorithm (GGA). In our analysis of this algorithm we discover a number of scaling-upissues surrounding the general GGA approach and discuss various reasons as to why this is so. Two separate ways of enhancing general performance are also explored. Secondly, an Iterated Heuristic Search algorithm is also proposed for the same problem, and in experiments it is shown to outperform the GGA in almost all cases. Similar observations to these are also witnessed in a second set of experiments, where the analogous problem of colouring equipartite graphs is also considered.Two new metaheuristic algorithms are also proposed for the second stage of the twostaged approach: an evolutionary algorithm (with a number of new specialised evolutionaryoperators), and a simulated annealing-based approach. Detailed analyses of both algorithms are presented and reasons for their relative benefits and drawbacks are discussed.Finally, suggestions are also made as to how our best performing algorithms might be modified in order to deal with further “real-world” constraints. In our analyses of these modified algorithms, as well as witnessing promising behaviour in some cases, we are also able to highlight some of the limitations of the two-stage approach in certain cases.