Relevant bibliographies by topics / Constraint satisfaction problem formalisms

Academic literature on the topic 'Constraint satisfaction problem formalisms'

Author: Grafiati
Published: 4 June 2021
Last updated: 20 February 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Contents

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Constraint satisfaction problem formalisms.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Constraint satisfaction problem formalisms"

1

Kumar, Mohit, Samuel Kolb, Clement Gautrais, and Luc De Raedt. "Democratizing Constraint Satisfaction Problems through Machine Learning." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 18 (May 18, 2021): 16057–59. http://dx.doi.org/10.1609/aaai.v35i18.18011.

Full text
Abstract:
Constraint satisfaction problems (CSPs) are used widely, especially in the field of operations research, to model various real world problems like scheduling or planning. However,modelling a problem as a CSP is not trivial, it is labour intensive and requires both modelling and domain expertise. The emerging field of constraint learning deals with this problem by automatically learning constraints from a given dataset. While there are several interesting approaches for constraint learning, these works are hard to access for a non-expert user. Furthermore, different approaches have different underlying formalism and require different setups before they can be used. This demo paper combines these researches and brings it to non-expert users in the form of an interactive Excel plugin. To do this, we translate different formalism for specifying CSPs into a common language, which allows multiple constraint learners to coexist, making this plugin more powerful than individual constraint learners. Moreover, we integrate learning of CSPs from data with solving them, making it a self sufficient plugin. For the developers of different constraint learners, we provide an API that can be used to integrate their work with this plugin by implementing a handful of functions.
APA, Harvard, Vancouver, ISO, and other styles
2

Eiter, Thomas, and Rafael Kiesel. "On the Complexity of Sum-of-Products Problems over Semirings." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 7 (May 18, 2021): 6304–11. http://dx.doi.org/10.1609/aaai.v35i7.16783.

Full text
Abstract:
Many important problems in AI, among them SAT, #SAT, and probabilistic inference, amount to Sum-of-Products Problems, i.e. evaluating a sum of products of values from some semiring R. While efficiently solvable cases are known, a systematic study of the complexity of this problem is missing. We characterize the latter by NP(R), a novel generalization of NP over semiring R, and link it to well-known complexity classes. While NP(R) is unlikely to be contained in FPSPACE(poly) in general, for a wide range of commutative (resp. in addition idempotent) semirings, there are reductions to #P (resp. NP) and solutions are thus only mildly harder to compute. We finally discuss NP(R)-complete reasoning problems in well-known semiring formalisms, among them Semiring-based Constraint Satisfaction Problems, obtaining new insights into their computational properties.
APA, Harvard, Vancouver, ISO, and other styles
3

Bożek, Andrzej, and Marian Wysocki. "Off-Line and Dynamic Production Scheduling – A Comparative Case Study." Management and Production Engineering Review 7, no. 1 (March 1, 2016): 21–32. http://dx.doi.org/10.1515/mper-2016-0003.

Full text
Abstract:
Abstract A comprehensive case study of manufacturing scheduling solutions development is given. It includes highly generalized scheduling problem as well as a few scheduling modes, methods and problem models. The considered problem combines flexible job shop structure, lot streaming with variable sublots, transport times, setup times, and machine calendars. Tabu search metaheuristic and constraint programming methods have been used for the off-line scheduling. Two dynamic scheduling methods have also been implemented, i.e., dispatching rules for the completely reactive scheduling and a multi-agent system for the predictivereactive scheduling. In these implementations three distinct models of the problem have been used, based on: graph representation, optimal constraint satisfaction, and Petri net formalism. Each of these solutions has been verified in computational experiments. The results are compared and some findings about advantages, disadvantages, and suggestions on using the solutions are formulated.
APA, Harvard, Vancouver, ISO, and other styles
4

Arnaoutaki, Konstantina, Efthimios Bothos, Babis Magoutas, Attila Aba, Domokos Esztergár-Kiss, and Gregoris Mentzas. "A Recommender System for Mobility-as-a-Service Plans Selection." Sustainability 13, no. 15 (July 23, 2021): 8245. http://dx.doi.org/10.3390/su13158245.

Full text
Abstract:
Transportation and mobility in smart cities are undergoing a grave transformation as new ways of mobility are introduced to facilitate seamless traveling, addressing travelers’ needs in a personalized manner. A novel concept that has been recently introduced is Mobility-as-a-Service (MaaS), where mobility services are bundled in MaaS Plans and offered to end-users through a single digital platform. The present paper introduces a recommender system for MaaS Plans selection that supports travelers to select bundles of mobility services that fit their everyday transportation needs. The recommender filters out unsuitable plans and then ranks the remaining ones on the basis of their similarity to the users’ characteristics, habits and preferences. The recommendation approach is based on Constraint Satisfaction Problem (CSP) formalisms combined with cosine similarity techniques. The proposed method was evaluated in experimental settings and was further embedded in real-life pilot MaaS applications. The experimental results showed that the proposed approach provides lists of MaaS PlanMaaS Plans that users would choose in a real-life MaaS setting, in most of the cases. Moreover, the results of the real-life pilots showed that the majority of the participants chose an actual MaaS Plan from the top three places of the recommendation lists.
APA, Harvard, Vancouver, ISO, and other styles
5

Tkachov, Igor. "A New Approach to Solving the Problem of Generating Sets of Complex Structural Objects Based on a Quasi-Equivalent Transformation of a Labeling Scheme." Cybernetics and Computer Technologies, no. 1 (March 30, 2021): 43–53. http://dx.doi.org/10.34229/2707-451x.21.1.4.

Full text
Abstract:
The paper presents the results of a theoretical study related to the development of methods for constructing generating structures based on labeling schemes for generating sets of complex structural objects. In a theoretical aspect, generated objects are mappings of sets of objects into a set of labels, and in practical terms, they can be, in particular, visual images. The scientific and practical interest in generative constructions is that they can be used to determine whether objects belong to a certain class, that is, to solve the problem of pattern recognition. The problem of constructing generating labeling scheme belongs to a wide section of modern applied informatics that embraces Constraint Satisfaction Problem and related themes [1–4]. But this problem has not been posed before and there are still no regular methods for solving it. The analysis of the above methods is based on the formalism of the consistent labeling problem [6, 10, 11], which is, on the one hand, a generalization of many statements of discrete problems of Constraint Satisfaction, and, on the other hand, a transparent theoretical construction with a well-developed mathematical foundation. The problem of constructing a relational scheme (in this case, labeling scheme) that generates a given set of mappings, by analogy with linguistic models, may be named “the problem of grammar restoration” [12–14]. In previous studies it was shown that to solve this problem it makes sense to use equivalent transformations of the labeling scheme [11]. This is because the source table listing all the complex objects that should be generated by the target scheme is itself a trivial variant of the scheme with a given set of consistent labelings. This means that the source scheme and target scheme are equivalent. However, one of the equivalent operations – disunion of a column – cannot be used regularly, since it requires certain conditions to be met regarding the internal structure of the column. In this case, to expand the capabilities of four known equivalent transformations of the labeling scheme – deleting and appending nonexistent labeling, as well as joining of columns and column disunion – a non-equivalent transformation was added – "coloring the column labelings". The purpose of the paper is to introduce and investigate operation of "coloring the column labelings" that leads to a non-equivalent transformation of a labeling scheme. Show the advisability of using the known equivalent and the introduced quasi-equivalent transformations of the labeling scheme to solve the problem of constructing generating structures based on labeling schemes. Results. The transformation of the labeling scheme, called "coloring the labelings of the scheme column", has been introduced. It is shown that its implementation leads to a quasi-equivalent labeling scheme, by solving which it is possible to uniquely restore the solution of the original problem. A method is proposed for using the newly introduced operation to transform the labeling scheme into a quasi-equivalent labeling scheme, in which it becomes possible to regularly perform the column decoupling operation. This ability of the operation of "coloring the column labelings" opens the way to the creation of a method for solving the problem of restoring a labeling scheme that generates a given set of consistent labelings. Keywords: relational scheme, consistent labeling scheme, equivalent labeling scheme transformations, constraint satisfaction problem.
APA, Harvard, Vancouver, ISO, and other styles
6

Bocewicz, Grzegorz, Peter Nielsen, Małgorzata Jasiulewicz-Kaczmarek, and Zbigniew Banaszak. "Dynamic Planning of Mobile Service Teams’ Mission Subject to Orders Uncertainty Constraints." Applied Sciences 10, no. 24 (December 11, 2020): 8872. http://dx.doi.org/10.3390/app10248872.

Full text
Abstract:
This paper considers the dynamic vehicle routing problem where a fleet of vehicles deals with periodic deliveries of goods or services to spatially dispersed customers over a given time horizon. Individual customers may only be served by predefined (dedicated) suppliers. Each vehicle follows a pre-planned separate route linking points defined by the customer location and service periods when ordered deliveries are carried out. Customer order specifications and their services time windows as well as vehicle travel times are dynamically recognized over time. The objective is to maximize a number of newly introduced or modified requests, being submitted dynamically throughout the assumed time horizon, but not compromising already considered orders. Therefore, the main question is whether a newly reported delivery request or currently modified/corrected one can be accepted or not. The considered problem arises, for example, in systems in which garbage collection or DHL parcel deliveries as well as preventive maintenance requests are scheduled and implemented according to a cyclically repeating sequence. It is formulated as a constraint satisfaction problem implementing the ordered fuzzy number formalism enabling to handle the fuzzy nature of variables through an algebraic approach. Computational results show that the proposed solution outperforms commonly used computer simulation methods.
APA, Harvard, Vancouver, ISO, and other styles
7

Richta, Tomáš, and Martin Hrubý. "Dynamic object-oriented geospatial modeling." Geoinformatics FCE CTU 4 (February 1, 2009): 29–44. http://dx.doi.org/10.14311/gi.4.2.

Full text
Abstract:
Published literature about moving objects (MO) simplifies the problem to the representation and storage of moving points, moving lines, or moving regions. The main insufficiency of this approach is lack of MO inner structure and dynamics modeling – the autonomy of moving agent. This paper describes basics of the object-oriented geospatial methodology for modeling complex systems consisting of agents, which move within spatial environment. The main idea is that during the agent movement, different kinds of connections with other moving or stationary objects are established or disposed, based on some spatial constraint satisfaction or nonfulfilment respectively. The methodology is constructed with regard to following two main conditions – 1) the inner behavior of agents should be represented by any formalism, e.g. Petri net, finite state machine, etc., and 2) the spatial characteristic of environment should be supplied by any information system, that is able to store defined set of spatial types, and support defined set of spatial operations. Finally, the methodology is demonstrated on simple simulation model of tram transportation system.
APA, Harvard, Vancouver, ISO, and other styles
8

Stolcke, Andreas. "Unification as Constraint Satisfaction in Structured Connectionist Networks." Neural Computation 1, no. 4 (December 1989): 559–67. http://dx.doi.org/10.1162/neco.1989.1.4.559.

Full text
Abstract:
Unification is a basic concept in several traditional symbolic formalisms that should be well suited for a connectionist implementation due to the intuitive nature of the notions it formalizes. It is shown that by approaching unification from a graph matching and constraint satisfaction perspective a natural and efficient realization in a structured connectionist network can be found.
APA, Harvard, Vancouver, ISO, and other styles
9

Barto, Libor. "Constraint satisfaction problem and universal algebra." ACM SIGLOG News 1, no. 2 (October 14, 2014): 14–24. http://dx.doi.org/10.1145/2677161.2677165.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

BARTO, LIBOR. "THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA." Bulletin of Symbolic Logic 21, no. 3 (September 2015): 319–37. http://dx.doi.org/10.1017/bsl.2015.25.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Constraint satisfaction problem formalisms"

1

Pham, Duc Nghia, and n/a. "Modelling and Exploiting Structures in Solving Propositional Satisfiability Problems." Griffith University. Institute for Integrated and Intelligent Systems, 2006. http://www4.gu.edu.au:8080/adt-root/public/adt-QGU20070216.143447.

Full text
Abstract:
Recent research has shown that it is often preferable to encode real-world problems as propositional satisfiability (SAT) problems and then solve using a general purpose SAT solver. However, much of the valuable information and structure of these realistic problems is flattened out and hidden inside the corresponding Conjunctive Normal Form (CNF) encodings of the SAT domain. Recently, systematic SAT solvers have been progressively improved and are now able to solve many highly structured practical problems containing millions of clauses. In contrast, state-of-the-art Stochastic Local Search (SLS) solvers still have difficulty in solving structured problems, apparently because they are unable to exploit hidden structure as well as the systematic solvers. In this thesis, we study and evaluate different ways to effectively recognise, model and efficiently exploit useful structures hidden in realistic problems. A summary of the main contributions is as follows: 1. We first investigate an off-line processing phase that applies resolution-based pre-processors to input formulas before running SLS solvers on these problems. We report an extensive empirical examination of the impact of SAT pre-processing on the performance of contemporary SLS techniques. It emerges that while all the solvers examined do indeed benefit from pre-processing, the effects of different pre-processors are far from uniform across solvers and across problems. Our results suggest that SLS solvers need to be equipped with multiple pre-processors if they are ever to match the performance of systematic solvers on highly structured problems. [Part of this study was published at the AAAI-05 conference]. 2. We then look at potential approaches to bridging the gap between SAT and constraint satisfaction problem (CSP) formalisms. One approach has been to develop a many-valued SAT formalism (MV-SAT) as an intermediate paradigm between SAT and CSP, and then to translate existing highly efficient SAT solvers to the MV-SAT domain. In this study, we follow a different route, developing SAT solvers that can automatically recognise CSP structure hidden in SAT encodings. This allows us to look more closely at how constraint weighting can be implemented in the SAT and CSP domains. Our experimental results show that a SAT-based mechanism to handle weights, together with a CSP-based method to instantiate variables, is superior to other combinations of SAT and CSP-based approaches. In addition, SLS solvers based on this many-valued weighting approach outperform other existing approaches to handle many-valued CSP structures. [Part of this study was published at the AAAI-05 conference]. 3. Finally, we propose and evaluate six different schemes to encode temporal reasoning problems, in particular the Interval Algebra (IA) networks, into SAT CNF formulas. We then empirically examine the performance of local search as well as systematic solvers on the new temporal SAT representations, in comparison with solvers that operate on native IA representations. Our empirical results show that zChaff (a state-of-the-art complete SAT solver) together with the best IA-to-SAT encoding scheme, can solve temporal problems significantly faster than existing IA solvers working on the equivalent native IA networks. [Part of this study was published at the CP-05 workshop].
APA, Harvard, Vancouver, ISO, and other styles
2

Pham, Duc Nghia. "Modelling and Exploiting Structures in Solving Propositional Satisfiability Problems." Thesis, Griffith University, 2006. http://hdl.handle.net/10072/365503.

Full text
Abstract:
Recent research has shown that it is often preferable to encode real-world problems as propositional satisfiability (SAT) problems and then solve using a general purpose SAT solver. However, much of the valuable information and structure of these realistic problems is flattened out and hidden inside the corresponding Conjunctive Normal Form (CNF) encodings of the SAT domain. Recently, systematic SAT solvers have been progressively improved and are now able to solve many highly structured practical problems containing millions of clauses. In contrast, state-of-the-art Stochastic Local Search (SLS) solvers still have difficulty in solving structured problems, apparently because they are unable to exploit hidden structure as well as the systematic solvers. In this thesis, we study and evaluate different ways to effectively recognise, model and efficiently exploit useful structures hidden in realistic problems. A summary of the main contributions is as follows: 1. We first investigate an off-line processing phase that applies resolution-based pre-processors to input formulas before running SLS solvers on these problems. We report an extensive empirical examination of the impact of SAT pre-processing on the performance of contemporary SLS techniques. It emerges that while all the solvers examined do indeed benefit from pre-processing, the effects of different pre-processors are far from uniform across solvers and across problems. Our results suggest that SLS solvers need to be equipped with multiple pre-processors if they are ever to match the performance of systematic solvers on highly structured problems. [Part of this study was published at the AAAI-05 conference]. 2. We then look at potential approaches to bridging the gap between SAT and constraint satisfaction problem (CSP) formalisms. One approach has been to develop a many-valued SAT formalism (MV-SAT) as an intermediate paradigm between SAT and CSP, and then to translate existing highly efficient SAT solvers to the MV-SAT domain. In this study, we follow a different route, developing SAT solvers that can automatically recognise CSP structure hidden in SAT encodings. This allows us to look more closely at how constraint weighting can be implemented in the SAT and CSP domains. Our experimental results show that a SAT-based mechanism to handle weights, together with a CSP-based method to instantiate variables, is superior to other combinations of SAT and CSP-based approaches. In addition, SLS solvers based on this many-valued weighting approach outperform other existing approaches to handle many-valued CSP structures. [Part of this study was published at the AAAI-05 conference]. 3. Finally, we propose and evaluate six different schemes to encode temporal reasoning problems, in particular the Interval Algebra (IA) networks, into SAT CNF formulas. We then empirically examine the performance of local search as well as systematic solvers on the new temporal SAT representations, in comparison with solvers that operate on native IA representations. Our empirical results show that zChaff (a state-of-the-art complete SAT solver) together with the best IA-to-SAT encoding scheme, can solve temporal problems significantly faster than existing IA solvers working on the equivalent native IA networks. [Part of this study was published at the CP-05 workshop].
Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
Institute for Integrated and Intelligent Systems
Full Text
APA, Harvard, Vancouver, ISO, and other styles
3

Thebault, Patricia. "Formalisme CSP (Constraint Satisfaction Problem) et localisation de motifs structurés dans les textes génomiques." Phd thesis, Université Paul Sabatier - Toulouse III, 2004. http://tel.archives-ouvertes.fr/tel-00011452.

Full text
Abstract:
La recherche d'occurrences de gènes d'ARN dans les séquences
génomiques est un problème dont l'importance est renouvelée par la
découverte récente de très nombreux ARN fonctionnels, opérant
souvent en interaction avec d'autres molécules.

Le formalisme des réseaux de contraintes est approprié à cette problématique aussi bien sur le plan de la modélisation que sur les développements algorithmiques qu'il permet de proposer.

Après une analyse et une comparaison des outils existants plongés dans le cadre des réseaux de contraintes, nous
montrons comment l'utilisation conjointe des réseaux de contraintes,
des techniques de résolution associées et des algorithmes et
structures de données du "pattern matching" permet de modéliser et de
rechercher efficacement des motifs structurés en interaction (faisant
intervenir plusieurs textes génomiques simultanément).
APA, Harvard, Vancouver, ISO, and other styles
4

Fulla, Peter. "On the valued constraint satisfaction problem." Thesis, University of Oxford, 2018. http://ora.ox.ac.uk/objects/uuid:bb2491ef-d802-4c5d-a388-a042644a4b47.

Full text
Abstract:
The Valued Constraint Satisfaction Problem (VCSP) is a framework which captures many natural decision and optimisation problems. An instance of the VCSP consists of a set of variables, which are to be assigned labels from a finite domain, and a collection of local constraints, each specified by a weighted relation mapping labellings of the variables in the constraint's scope to values. The objective is to minimise the total value from all constraints. The VCSP is commonly parameterised by a language, i.e. a set of weighted relations that are available for use in the constraints. Languages are classified according to the computational complexity of the VCSP as tractable, for which the problem can be solved in polynomial time, and intractable, for which the problem is NP-hard. The recently proved VCSP dichotomy theorem established a classification of all languages into these two categories. Additionally, various structural restrictions can be imposed to limit the set of admissible instances further, thus potentially changing the complexity of the VCSP. Our first contribution relates to the algebraic approach to the VCSP, which proved instrumental in recent advances in the field. We generalise the Galois connection between weighted relational clones and weighted clones so that it applies to infinite sets as well. Second, we study a structural restriction requiring that the incidence graph be planar. In this setting, we establish a complexity classification of conservative languages (i.e. languages containing all {0,1}-valued unary weighted relations) and a necessary tractability condition for Boolean languages (i.e. languages over a two-element domain). Third, we study the surjective variant of the VCSP, in which labellings are required to assign every domain element to at least one variable. We establish a complexity classification of Boolean languages, which encompasses a new tractable class of problems.
APA, Harvard, Vancouver, ISO, and other styles
5

Nightingale, Peter. "Consistency and the quantified constraint satisfaction problem /." St Andrews, 2007. http://hdl.handle.net/10023/759.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Nightingale, Peter William. "Consistency and the Quantified Constraint Satisfaction Problem." Thesis, University of St Andrews, 2007. http://hdl.handle.net/10023/759.

Full text
Abstract:
Constraint satisfaction is a very well studied and fundamental artificial intelligence technique. Various forms of knowledge can be represented with constraints, and reasoning techniques from disparate fields can be encapsulated within constraint reasoning algorithms. However, problems involving uncertainty, or which have an adversarial nature (for example, games), are difficult to express and solve in the classical constraint satisfaction problem. This thesis is concerned with an extension to the classical problem: the Quantified Constraint Satisfaction Problem (QCSP). QCSP has recently attracted interest. In QCSP, quantifiers are allowed, facilitating the expression of uncertainty. I examine whether QCSP is a useful formalism. This divides into two questions: whether QCSP can be solved efficiently; and whether realistic problems can be represented in QCSP. In attempting to answer these questions, the main contributions of this thesis are the following: - the definition of two new notions of consistency; - four new constraint propagation algorithms (with eight variants in total), along with empirical evaluations; - two novel schemes to implement the pure value rule, which is able to simplify QCSP instances; - a new optimization algorithm for QCSP; - the integration of these algorithms and techniques into a solver named Queso; - and the modelling of the Connect 4 game, and of faulty job shop scheduling, in QCSP. These are set in context by a thorough review of the QCSP literature.
APA, Harvard, Vancouver, ISO, and other styles
7

Zhang, Lixi. "Solving the timetabling problem using constraint satisfaction programming." Access electronically, 2005. http://www.library.uow.edu.au/adt-NWU/public/adt-NWU20051104.155838/index.html.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Powell, Robert David. "Complexity classifications for the valued constraint satisfaction problem." Thesis, Durham University, 2016. http://etheses.dur.ac.uk/11485/.

Full text
Abstract:
In a valued constraint satisfaction problem (VCSP), the goal is to find an assignment of values to variables that minimizes a given sum of functions. Each function in the sum depends on a subset of variables, takes values which are rational numbers or infinity, and is chosen from a fixed finite set of functions called a constraint language. We study how the computational complexity of this problem depends on the constraint language. We often consider the case where infinite values are disallowed, and refer to such constraint languages as being finite-valued. If we consider such finite-valued constraint languages, the case where we allow variables to take two values was classified by Cohen et al., who show that submodular functions essentially give rise to the only tractable case. Non-submodular functions can be used to express the NP-hard Max Cut problem. We consider the case where the variables can take three values, and identify a new infinite set of functions called skew bisubmodular functions which imply tractability. We prove that submodularity with respect to some total order and skew bisubmodularity give rise to the only tractable cases, and in all other cases Max Cut can be expressed. We also show that our characterisation of tractable cases is tight, that is, none of the conditions can be omitted. Thus, our results provide a new dichotomy theorem in constraint satisfaction research. We also negatively answer the question of whether multimorphisms can capture all necessary tractable constraint languages. We then study the VCSP as a homomorphism problem on digraphs. By adapting a proof designed for CSPs we show that each VCSP with a fixed finite constraint language is equivalent to one where the constraint language consists of one {0,infinity}-valued binary function (i.e. a digraph) and one finite-valued unary function. This latter problem is known as the Minimum Cost Homomorphism Problem for digraphs. We also show that our reduction preserves a number of useful algebraic properties of the constraint language. Finally, given a finite-valued constraint language, we consider the case where the variables of our VCSP are allowed to take four values. We prove that 1-defect chain multimorphisms, which are required in the four element dichotomy of Min CSP, are a special case of more general fractional polymorphisms we call {a,b}-1-defect fractional polymorphisms. We conclude with a conjecture for the four element case, and some interesting open problems which might lead to a tighter description of tractable finite-valued constraint languages on finite domains of any size.
APA, Harvard, Vancouver, ISO, and other styles
9

Andersson, Jakob. "Automatic Invoice Data Extraction as a Constraint Satisfaction Problem." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-411596.

Full text
Abstract:
Invoice processing has traditionally been heavily dependent onmanual labor, where the task is to identify and move certaininformation from an origin to a destination. A time demandingtask with a high interest of automation to reduce time ofexecution, fault-risk and cost.With the evergrowing interest in automation and ArtificialIntelligence (AI), this thesis will explore the possibilities ofautomating the task of extracting and mapping information ofinterest by defining the problem as a Constraint OptimizationProblem (COP) using numeric relations between present information.The problem is then solved by extracting the numericalvalues in a document and utilizing it as an input space whereeach combination of numeric values are tested using a backendsolver.Several different models were defined, using different approachesand constraints on relations between possible existingfields. A solution to an invoice was considered correct if thetotal, tax, net and rounding amounts were estimated correctly.The final best achieved results were 84.30% correct and8.77% incorrect solutions on a set of 1400 various types of invoices.The achieved results show a promising alternative route toproposed solutions using e.g. machine learning or other intelligentsolutions using graphical or positional data. While only regardingthe numerical values present in each document, the proposedsolution becomes decentralized and therefor can be implementedand ran on any set of invoices without any pre-training phase.
APA, Harvard, Vancouver, ISO, and other styles
10

Magaji, Amina Sambo-Muhammad. "Combining search strategies for distributed constraint satisfaction." Thesis, Robert Gordon University, 2015. http://hdl.handle.net/10059/1374.

Full text
Abstract:
Many real-life problems such as distributed meeting scheduling, mobile frequency allocation and resource allocation can be solved using multi-agent paradigms. Distributed constraint satisfaction problems (DisCSPs) is a framework for describing such problems in terms of related subproblems, called a complex local problem (CLP), which are dispersed over a number of locations, each with its own constraints on the values their variables can take. An agent knows the variables in its CLP plus the variables (and their current value) which are directly related to one of its own variables and the constraints relating them. It knows little about the rest of the problem. Thus, each CLP is solved by an agent which cooperates with other agents to solve the overall problem. Algorithms for solving DisCSPs can be classified as either systematic or local search with the former being complete and the latter incomplete. The algorithms generally assume that each agent has only one variable as they can solve DisCSP with CLPs using “virtual” agents. However, in large DisCSPs where it is appropriate to trade completeness off against timeliness, systematic search algorithms can be expensive when compared to local search algorithms which generally converge quicker to a solution (if a solution is found) when compared to systematic algorithms. A major drawback of local search algorithms is getting stuck at local optima. Significant researches have focused on heuristics which can be used in an attempt to either escape or avoid local optima. This thesis makes significant contributions to local search algorithms for DisCSPs. Firstly, we present a novel combination of heuristics in DynAPP (Dynamic Agent Prioritisation with Penalties), which is a distributed synchronous local search algorithm for solving DisCSPs having one variable per agent. DynAPP combines penalties on values and dynamic agent prioritisation heuristics to escape local optima. Secondly, we develop a divide and conquer approach that handles DisCSP with CLPs by exploiting the structure of the problem. The divide and conquer approach prioritises the finding of variable instantiations which satisfy the constraints between agents which are often more expensive to satisfy when compared to constraints within an agent. The approach also exploits concurrency and combines the following search strategies: (i) both systematic and local searches; (ii) both centralised and distributed searches; and (iii) a modified compilation strategy. We also present an algorithm that implements the divide and conquer approach in Multi-DCA (Divide and Conquer Algorithm for Agents with CLPs). DynAPP and Multi-DCA were evaluated on several benchmark problems and compared to the leading algorithms for DisCSPs and DisCSPs with CLPs respectively. The results show that at the region of difficult problems, combining search heuristics and exploiting problem structure in distributed constraint satisfaction achieve significant benefits (i.e. generally used less computational time and communication costs) over existing competing methods.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Books on the topic "Constraint satisfaction problem formalisms"

1

Artificial intelligence: A modern approach. 2nd ed. Upper Saddle River, N.J: Prentice Hall, 2003.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

Peter, Norvig, ed. Artificial intelligence: A modern approach. Englewood Cliffs, N.J: Prentice Hall, 1995.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
3

Peter, Norvig, ed. Artificial intelligence: A modern approach. 2nd ed. Upper Saddle River, N.J: Prentice Hall/Pearson Education, 2003.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
4

Ghedira, Khaled. Constraint Satisfaction Problems: CSP Formalisms and Techniques. Wiley & Sons, Incorporated, John, 2013.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
5

Ghedira, Khaled. Constraint Satisfaction Problems: CSP Formalisms and Techniques. Wiley & Sons, Incorporated, John, 2013.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
6

Ghedira, Khaled. Constraint Satisfaction Problems: CSP Formalisms and Techniques. Wiley & Sons, Incorporated, John, 2013.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
7

Ghedira, Khaled. Constraint Satisfaction Problems: CSP Formalisms and Techniques. Wiley & Sons, Incorporated, John, 2012.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
8

Ghedira, Khaled. Constraint Satisfaction Problems: CSP Formalisms and Techniques. Wiley & Sons, Limited, John, 2013.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
9

Ghedira, Khaled. Constraint Satisfaction Problems: CSP Formalisms and Techniques. Wiley & Sons, Incorporated, John, 2013.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
10

Russell, Stuart J., and Peter Norvig. Artificial Intelligence: A Modern Approach (2nd Edition). Prentice Hall, 2002.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Book chapters on the topic "Constraint satisfaction problem formalisms"

1

Yokoo, Makoto. "Constraint Satisfaction Problem." In Distributed Constraint Satisfaction, 1–45. Berlin, Heidelberg: Springer Berlin Heidelberg, 2001. http://dx.doi.org/10.1007/978-3-642-59546-2_1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Yokoo, Makoto. "Distributed Constraint Satisfaction Problem." In Distributed Constraint Satisfaction, 47–54. Berlin, Heidelberg: Springer Berlin Heidelberg, 2001. http://dx.doi.org/10.1007/978-3-642-59546-2_2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Miguel, Ian. "The Constraint Satisfaction Problem." In Dynamic Flexible Constraint Satisfaction and its Application to AI Planning, 13–64. London: Springer London, 2004. http://dx.doi.org/10.1007/978-0-85729-378-7_2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Paredis, Jan. "Co-evolutionary constraint satisfaction." In Parallel Problem Solving from Nature — PPSN III, 46–55. Berlin, Heidelberg: Springer Berlin Heidelberg, 1994. http://dx.doi.org/10.1007/3-540-58484-6_249.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Hirayama, Katsutoshi, and Makoto Yokoo. "Distributed partial constraint satisfaction problem." In Principles and Practice of Constraint Programming-CP97, 222–36. Berlin, Heidelberg: Springer Berlin Heidelberg, 1997. http://dx.doi.org/10.1007/bfb0017442.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Madelaine, Florent, and Stéphane Secouard. "Quantified Valued Constraint Satisfaction Problem." In Lecture Notes in Computer Science, 295–311. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-98334-9_20.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Udovićić, Mirna. "Constraint Satisfaction Problem: Professor Weekly Schedule." In Lecture Notes in Networks and Systems, 290–98. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-71321-2_27.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Kozik, Marcin, and Joanna Ochremiak. "Algebraic Properties of Valued Constraint Satisfaction Problem." In Automata, Languages, and Programming, 846–58. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015. http://dx.doi.org/10.1007/978-3-662-47672-7_69.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Belaidouni, Meriema, and Jin-Kao Hao. "Landscapes and the Maximal Constraint Satisfaction Problem." In Lecture Notes in Computer Science, 242–53. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000. http://dx.doi.org/10.1007/10721187_18.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Montesino-Guerra, Juan A., Héctor Puga, J. Martín Carpio, Manuel Ornelas-Rodríguez, A. Rojas-Domínguez, and Lucero Ortiz-Aguilar. "Combinatorial Designs on Constraint Satisfaction Problem (VRP)." In Intuitionistic and Type-2 Fuzzy Logic Enhancements in Neural and Optimization Algorithms: Theory and Applications, 509–26. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-35445-9_36.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Constraint satisfaction problem formalisms"

1

El Khattabi, Ghizlane, Soumia Lahboub, Bouyakhf El Houssine, and Imade Benelallam. "Contribution to Modeling Smart Grid Problem with the Constraint Satisfaction Problem Formalism." In the 2nd Mediterranean Conference. New York, New York, USA: ACM Press, 2018. http://dx.doi.org/10.1145/3177148.3180084.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Bodirsky, Manuel, Peter Jonsson, Barnaby Martin, and Antoine Mottet. "Classification Transfer for Qualitative Reasoning Problems." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. California: International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/175.

Full text
Abstract:
We study formalisms for temporal and spatial reasoning in the modern context of Constraint Satisfaction Problems (CSPs). We show how questions on the complexity of their subclasses can be solved using existing results via the powerful use of primitive positive (pp) interpretations and pp-homotopy. We demonstrate the methodology by giving a full complexity classification of all constraint languages that are first-order definable in Allen's Interval Algebra and contain the basic relations (s) and (f). In the case of the Rectangle Algebra we answer in the affirmative the old open question as to whether ORD-Horn is a maximally tractable subset among the (disjunctive, binary) relations. We then generalise our results for the Rectangle Algebra to the r-dimensional Block Algebra.
APA, Harvard, Vancouver, ISO, and other styles
3

Matar, Jad, Raphael Chenouard, and Alain Bernard. "A New Integration Framework for Modeling and Optimizing Systems in Preliminary Design Phase." In ASME 2012 11th Biennial Conference on Engineering Systems Design and Analysis. American Society of Mechanical Engineers, 2012. http://dx.doi.org/10.1115/esda2012-82623.

Full text
Abstract:
In this paper we propose a new integration framework model for simplifying the feasible space exploration and product optimization in early design phases. Hence, modeling and optimizing tasks are core activities in this framework. Currently, system engineering problems are modeled and optimized using a wide range of domain-specific languages. One should not duplicate these languages by creating a new system engineering language capable of modeling and optimizing every aspect of a system. Thus we combine the UML2 language and the formalism of Constraint Optimization Problems (COPs). UML2 is a visual modeling language, which provides a set of diagrams and constructs for modeling the major aspects of a product. In order to optimize design parameters, we reformulate some of this modeling knowledge into a COP. A COP may be defined as a regular constraint satisfaction problem (CSP) augmented with a set of objective functions. Thus the optimization problem to be solved is stated declaratively with acausal constraints. Then, COP solvers are based on generic solving algorithms computing a set of optimal solutions. In this paper, generic concepts integrating variability modeling concepts and based on architecture description languages are introduced. We also briefly describe transformation strategy using ATL language to perform a bidirectional mapping between UML2 constructs and the corresponding COP models.
APA, Harvard, Vancouver, ISO, and other styles
4

Zhuk, Dmitriy. "An Algorithm for Constraint Satisfaction Problem." In 2017 IEEE 47th International Symposium on Multiple-Valued Logic (ISMVL). IEEE, 2017. http://dx.doi.org/10.1109/ismvl.2017.20.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Takaci, Aleksandar, Srdjan Skrbic, and Aleksandar Perovic. "Generalised Prioritised Fuzzy Constraint Satisfaction Problem." In 2009 7th International Symposium on Intelligent Systems and Informatics (SISY). IEEE, 2009. http://dx.doi.org/10.1109/sisy.2009.5291177.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Zhuk, Dmitriy. "No-Rainbow Problem and the Surjective Constraint Satisfaction Problem." In 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). IEEE, 2021. http://dx.doi.org/10.1109/lics52264.2021.9470632.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Mortazavi, Reza, and Saeed Jalili. "Iterative constraint satisfaction method for microaggregation problem." In 2014 11th International ISC Conference on Information Security and Cryptology (ISCISC). IEEE, 2014. http://dx.doi.org/10.1109/iscisc.2014.6994048.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Dirakkhunakon, Sipang, and Yoothana Suansook. "Stochastic Search Algorithm for Constraint Satisfaction Problem." In 2008 International Conference on Computer and Electrical Engineering (ICCEE). IEEE, 2008. http://dx.doi.org/10.1109/iccee.2008.85.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Wintz, Julien, Pascal Schreck, and Pascal Mathis. "A framework for geometric constraint satisfaction problem." In the 2006 ACM symposium. New York, New York, USA: ACM Press, 2006. http://dx.doi.org/10.1145/1141277.1141509.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Löffler, Sven, Ke Liu, and Petra Hofstedt. "A Meta Constraint Satisfaction Optimization Problem for the Optimization of Regular Constraint Satisfaction Problems." In 11th International Conference on Agents and Artificial Intelligence. SCITEPRESS - Science and Technology Publications, 2019. http://dx.doi.org/10.5220/0007260204350442.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Constraint satisfaction problem formalisms"

1

Sadeh, Norman, Katia Sycara, and Yalin Xiong. Backtracking Techniques for the Job Shop Scheduling Constraint Satisfaction Problem. Fort Belvoir, VA: Defense Technical Information Center, January 1994. http://dx.doi.org/10.21236/ada289435.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Sadeh, Norman M., and Mark S. Fox. Variable and Value Ordering Heuristics for the Job Shop Scheduling Constraint Satisfaction Problem. Fort Belvoir, VA: Defense Technical Information Center, November 1995. http://dx.doi.org/10.21236/ada311303.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Constraint satisfaction problem formalisms' for particular source types:
Journal articles Dissertations / Theses Books
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography