Log in

Relevant bibliographies by topics / Constraint satisfaction problem formalisms / Journal articles

Journal articles on the topic 'Constraint satisfaction problem formalisms'

To see the other types of publications on this topic, follow the link: 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:

Consult the top 50 journal articles for your research 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.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

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

11

HULUBEI, TUDOR, EUGENE C. FREUDER, and RICHARD J. WALLACE. "The Goldilocks problem." Artificial Intelligence for Engineering Design, Analysis and Manufacturing 17, no. 1 (February 2003): 3–11. http://dx.doi.org/10.1017/s0890060403171028.

Full text

Abstract:

Constraint-based reasoning is often used to represent and find solutions to configuration problems. In the field of constraint satisfaction, the major focus has been on finding solutions to difficult problems. However, many real-life configuration problems, although not extremely complicated, have a huge number of solutions, few of which are acceptable from a practical standpoint. In this paper we present a value ordering heuristic for constraint solving that attempts to guide search toward solutions that are acceptable. More specifically, by considering weights that are assigned to values and sets of values, the heuristic can guide search toward solutions for which the total weight is within an acceptable interval. Experiments with random constraint satisfaction problems demonstrate that, when a problem has numerous solutions, the heuristic makes search extremely efficient even when there are relatively few solutions that fall within the interval of acceptable weights. In these cases, an algorithm that is very effective for finding a feasible solution to a given constraint satisfaction problem (the “maintained arc consistency” algorithm or MAC) does not find a solution in the same weight interval within a reasonable time when it is run without the heuristic.

APA, Harvard, Vancouver, ISO, and other styles

12

Đapić, Petar, Petar Marković, and Barnaby Martin. "Quantified Constraint Satisfaction Problem on Semicomplete Digraphs." ACM Transactions on Computational Logic 18, no. 1 (April 13, 2017): 1–47. http://dx.doi.org/10.1145/3007899.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Subramanian, S., and E. c. Freuder. "Compiling rules from constraint satisfaction problem solving." ACM SIGART Bulletin, no. 108 (April 1989): 177–78. http://dx.doi.org/10.1145/63266.63307.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Prosser, Patrick. "HYBRID ALGORITHMS FOR THE CONSTRAINT SATISFACTION PROBLEM." Computational Intelligence 9, no. 3 (August 1993): 268–99. http://dx.doi.org/10.1111/j.1467-8640.1993.tb00310.x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Jiang, Xiao, Pingyuan Cui, Rui Xu, Ai Gao, and Shengying Zhu. "An Action Guided Constraint Satisfaction Technique for Planning Problem." International Journal of Software Science and Computational Intelligence 8, no. 3 (July 2016): 39–53. http://dx.doi.org/10.4018/ijssci.2016070103.

Full text

Abstract:

This paper presents an action guided constraint satisfaction technique for planning problem. Different from the standard algorithms which are almost domain independence and cannot reflect the characteristics of the planning progress, this paper discusses how the action rules in planning act in constraint satisfaction problems. Based on the conclusion, an action directed constraint is proposed to guide the variable selected procedure in constraint satisfaction problems. Through theoretical analysis, this technique is prior an order of magnitude in variable select procedure over the ordinary heuristic technique and can be used in constraint-programmed planning problem generally. With the simulation experiments it shows that the algorithm with action guided constraint can effectively reduce the number of constraint checks during the planning procedure and has a better performance on total running time over the standard version.

APA, Harvard, Vancouver, ISO, and other styles

16

GOMES, CARLA P. "Artificial intelligence and operations research: challenges and opportunities in planning and scheduling." Knowledge Engineering Review 15, no. 1 (March 2000): 1–10. http://dx.doi.org/10.1017/s0269888900001090.

Full text

Abstract:

Both the Artificial Intelligence (AI) and the Operations Research (OR) communities are interested in developing techniques for solving hard combinatorial problems, in particular in the domain of planning and scheduling. AI approaches encompass a rich collection of knowledge representation formalisms for dealing with a wide variety of real-world problems. Some examples are constraint programming representations, logical formalisms, declarative and functional programming languages such as Prolog and Lisp, Bayesian models, rule-based formalism, etc. The downside of such rich representations is that in general they lead to intractable problems, and we therefore often cannot use such formalisms for handling realistic size problems. OR, on the other hand, has focused on more tractable representations, such as linear programming formulations. OR-based techniques have demonstrated the ability to identify optimal and locally optimal solutions for well-defined problem spaces. In general, however, OR solutions are restricted to rigid models with limited expressive power. AI techniques, on the other hand, provide richer and more flexible representations of real-world problems, supporting efficient constraint-based reasoning mechanisms as well as mixed initiative frameworks, which allow the human expertise to be in the loop. The challenge lies in providing representations that are expressive enough to describe real-world problems and at the same time guaranteeing good and fast solutions.

APA, Harvard, Vancouver, ISO, and other styles

17

WESTFOLD, STEPHEN J., and DOUGLAS R. SMITH. "Synthesis of efficient constraint-satisfaction programs." Knowledge Engineering Review 16, no. 1 (March 2001): 69–84. http://dx.doi.org/10.1017/s0269888901000029.

Full text

Abstract:

In this paper we describe the framework we have developed in KIDS (Kestrel Interactive Development System) for generating efficient constraint satisfaction programs. We have used KIDS to synthesise global search scheduling programs that have proved to be dramatically faster than other programs running the same data. We focus on the underlying ideas that lead to this efficiency. The key to the efficiency is the reduction of the size of the search space by an effective representation of sets of possible solutions (solution spaces) that allows efficient constraint propagation and pruning at the level of solution spaces. Moving to a solution space representation involves a problem reformulation. Having found a solution to the reformulated problem, an extraction phase extracts solutions to the original problem. We show how constraints from the original problem can be automatically reformulated and specialised in order to derive efficient propagation code automatically. Our solution methods exploit the semi-lattice structure of our solution spaces.

APA, Harvard, Vancouver, ISO, and other styles

18

Baba, Satomi, Atsushi Iwasaki, Makoto Yokoo, Marius C. Silaghi, Katsutoshi Hirayama, and Toshihiro Matsui. "Cooperative Problem Solving against Adversary: Quantified Distributed Constraint Satisfaction Problem." Transactions of the Japanese Society for Artificial Intelligence 26 (2011): 136–46. http://dx.doi.org/10.1527/tjsai.26.136.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Krokhin, Andrei, and Jakub Opršal. "An invitation to the promise constraint satisfaction problem." ACM SIGLOG News 9, no. 3 (July 2022): 30–59. http://dx.doi.org/10.1145/3559736.3559740.

Full text

Abstract:

The study of the complexity of the constraint satisfaction problem (CSP), centred around the Feder-Vardi Dichotomy Conjecture, has been very prominent in the last two decades. After a long concerted effort and many partial results, the Dichotomy Conjecture has been proved in 2017 independently by Bulatov and Zhuk. At about the same time, a vast generalisation of CSP, called promise CSP, has started to gain prominence. In this survey, we explain the importance of promise CSP and highlight many new very interesting features that the study of promise CSP has brought to light. The complexity classification quest for the promise CSP is wide open, and we argue that, despite the promise CSP being more general, this quest is rather more accessible to a wide range of researchers than the dichotomy-led study of the CSP has been.

APA, Harvard, Vancouver, ISO, and other styles

20

Liu, Ya'nan. "Sharp Thresholds for a Random Constraint Satisfaction Problem." Open Journal of Applied Sciences 07, no. 10 (2017): 574–84. http://dx.doi.org/10.4236/ojapps.2017.710041.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Surgwon Sohn. "Constraint Satisfaction Optimization for RFID Reader Interference Problem." International Journal of Advancements in Computing Technology 3, no. 7 (August 31, 2011): 237–43. http://dx.doi.org/10.4156/ijact.vol3.issue7.28.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Yokoo, M., E. H. Durfee, T. Ishida, and K. Kuwabara. "The distributed constraint satisfaction problem: formalization and algorithms." IEEE Transactions on Knowledge and Data Engineering 10, no. 5 (1998): 673–85. http://dx.doi.org/10.1109/69.729707.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

HABBAS, ZINEB, MICHAËL KRAJECKI, and DANIEL SINGER. "SHARED MEMORY IMPLEMENTATION OF CONSTRAINT SATISFACTION PROBLEM RESOLUTION." Parallel Processing Letters 11, no. 04 (December 2001): 487–501. http://dx.doi.org/10.1142/s0129626401000749.

Full text

Abstract:

Many problems in Computer Science, especially in Artificial Intelligence, can be formulated as Constraint Satisfaction Problems (CSP). This paper presents a parallel implementation of the Forward-Checking algorithm for solving a binary CSP over finite domains. Its main contribution is to use a simple decomposition strategy in order to distribute dynamically the search tree among machines. The feasibility and benefit of this approach are studied for a Shared Memory model. An implementation is drafted using the new emergent standard OpenMP library for shared memory, thus controlling load balancing. We mainly highlight satisfactory efficiencies without using any tricky load balancing policy. All the experiments were carried out running on the Sillicon Graphics Origin 2000 parallel machine.

APA, Harvard, Vancouver, ISO, and other styles

24

Bulatov, Andrei A. "The complexity of the counting constraint satisfaction problem." Journal of the ACM 60, no. 5 (October 2013): 1–41. http://dx.doi.org/10.1145/2528400.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Djenouri, Youcef, Djamel Djenouri, Zineb Habbas, Jerry Chun-Wei Lin, Tomasz P. Michalak, and Alberto Cano. "When the Decomposition Meets the Constraint Satisfaction Problem." IEEE Access 8 (2020): 207034–43. http://dx.doi.org/10.1109/access.2020.3038228.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Popescu, Ilié. "Using artificial neural networks for constraint satisfaction problem." Nonlinear Analysis: Theory, Methods & Applications 30, no. 5 (December 1997): 2937–44. http://dx.doi.org/10.1016/s0362-546x(97)00340-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Kelsey, Tom, and Lars Kotthoff. "Exact Closest String as a Constraint Satisfaction Problem." Procedia Computer Science 4 (2011): 1062–71. http://dx.doi.org/10.1016/j.procs.2011.04.113.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Gu, Jun, Xiaofei Huang, and Bin Du. "A quantitative solution to Constraint Satisfaction Problem (CSP)." New Generation Computing 13, no. 1 (December 1994): 99–115. http://dx.doi.org/10.1007/bf03038310.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Wang, Lin, Shi-Sheng Zhong, and Yong-Jian Zhang. "Process configuration based on generative constraint satisfaction problem." Journal of Intelligent Manufacturing 28, no. 4 (January 6, 2015): 945–57. http://dx.doi.org/10.1007/s10845-014-1031-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Lorterapong, Pasit, and Mongkol Ussavadilokrit. "Construction Scheduling Using the Constraint Satisfaction Problem Method." Journal of Construction Engineering and Management 139, no. 4 (April 2013): 414–22. http://dx.doi.org/10.1061/(asce)co.1943-7862.0000582.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Bergman, Clifford, and David Failing. "Commutative idempotent groupoids and the constraint satisfaction problem." Algebra universalis 73, no. 3-4 (April 29, 2015): 391–417. http://dx.doi.org/10.1007/s00012-015-0323-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Nešetřil, Jaroslav, Mark H. Siggers, and László Zádori. "A combinatorial constraint satisfaction problem dichotomy classification conjecture." European Journal of Combinatorics 31, no. 1 (January 2010): 280–96. http://dx.doi.org/10.1016/j.ejc.2009.02.007.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Baykan, Can A., and Mark S. Fox. "Spatial synthesis by disjunctive constraint satisfaction." Artificial Intelligence for Engineering Design, Analysis and Manufacturing 11, no. 4 (September 1997): 245–62. http://dx.doi.org/10.1017/s0890060400003206.

Full text

Abstract:

AbstractThe spatial synthesis problem addressed in this paper is the configuration of rectangles in 2D space, where the sides of the rectangles are parallel to an orthogonal coordinate system. Variables are the locations of the edges of the rectangles and their orientations. Algebraic constraints on these variables define a layout and constitute a constraint satisfaction problem. We give a new O(n2) algorithm for incremental path-consistency, which is applied after adding each algebraic constraint. Problem requirements are formulated as spatial relations between the rectangles, for example, adjacency, minimum distance, and nonoverlap. Spatial relations are expressed by Boolean combinations of the algebraic constraints; called disjunctive constraints. Solutions are generated by backtracking search, which selects a disjunctive constraint and instantiates its disjuncts. The selected disjuncts describe an equivalence class of configurations that is a significantly different solution. This method generates the set of significantly different solutions that satisfy all the requirements. The order of instantiating disjunctive constraints is critical for search efficiency. It is determined dynamically at each search state, using functions of heuristic measures called textures. Textures implement fail-first and prune-early strategies. Extensions to the model, that is, 3D configurations, configurations of nonrectangular shapes, constraint relaxation, optimization, and adding new rectangles during search are discussed.

APA, Harvard, Vancouver, ISO, and other styles

34

Bodirsky, Manuel, Hubie Chen, and Michał Wrona. "Tractability of quantified temporal constraints to the max." International Journal of Algebra and Computation 24, no. 08 (December 2014): 1141–56. http://dx.doi.org/10.1142/s0218196714500507.

Full text

Abstract:

A temporal constraint language is a set of relations that are first-order definable over (ℚ;<). We show that several temporal constraint languages whose constraint satisfaction problem is maximally tractable are also maximally tractable for the more expressive quantified constraint satisfaction problem. These constraint languages are defined in terms of preservation under certain binary polymorphisms. We also present syntactic characterizations of the relations in these languages.

APA, Harvard, Vancouver, ISO, and other styles

35

Hyvönen, Eero. "Spreadsheets based on interval constraint satisfaction." Artificial Intelligence for Engineering Design, Analysis and Manufacturing 8, no. 1 (1994): 27–34. http://dx.doi.org/10.1017/s0890060400000433.

Full text

Abstract:

AbstractSpreadsheets are difficult to use in applications, where only incomplete or inexact data (e.g., intervals) are available-a typical situation in various design and planning tasks. It can be argued that this is due to two fundamental shortcomings of the computational paradigm underlying spreadsheets. First, the distinction between input and output cells has to be fixed before computations. Second, cells may have only exact values. As a result, spread-sheets support the user only with primitive iterative problem solving schemes based on trial-and-error methods. A constraint-based computational paradigm for next generation interval spreadsheets is presented. The scheme makes it possible to exploit incomplete/inexact data (intervals), and it can support problem solving in a top-down fashion. Current spreadsheets constitute a special case of the more general interval constraint spreadsheets proposed.

APA, Harvard, Vancouver, ISO, and other styles

36

Sudo, Yasuhiro, Masahito Kurihara, and Tamotsu Mitamura. "Extending Fuzzy Constraint Satisfaction Problems." Journal of Advanced Computational Intelligence and Intelligent Informatics 10, no. 4 (July 20, 2006): 465–71. http://dx.doi.org/10.20965/jaciii.2006.p0465.

Full text

Abstract:

This paper propose a new type of Fuzzy CSP (Constraint Satisfaction Problem) that have a mixture of discrete and continuous domains, and a Spread-Repair algorithm. In traditional CSP and Fuzzy CSP, values for the variables are chosen from the discrete domains. However, this is often inconvenient when one wants to express real world problems. We show that this model, called HDFCSP (Hybrid Domain Fuzzy CSP), can be solved by Spread-Repair, an extension of the well known iterative improvement algorithms. Experimental results on some test problems show that the algorithm actually has an ability of finding partial approximate solutions with high probability in a computation time much shorter than the traditional, discrete-domain FCSP.

APA, Harvard, Vancouver, ISO, and other styles

37

Gao, Y., and J. Culberson. "Consistency and Random Constraint Satisfaction Models." Journal of Artificial Intelligence Research 28 (April 29, 2007): 517–57. http://dx.doi.org/10.1613/jair.2155.

Full text

Abstract:

In this paper, we study the possibility of designing non-trivial random CSP models by exploiting the intrinsic connection between structures and typical-case hardness. We show that constraint consistency, a notion that has been developed to improve the efficiency of CSP algorithms, is in fact the key to the design of random CSP models that have interesting phase transition behavior and guaranteed exponential resolution complexity without putting much restriction on the parameter of constraint tightness or the domain size of the problem. We propose a very flexible framework for constructing problem instances withinteresting behavior and develop a variety of concrete methods to construct specific random CSP models that enforce different levels of constraint consistency. A series of experimental studies with interesting observations are carried out to illustrate the effectiveness of introducing structural elements in random instances, to verify the robustness of our proposal, and to investigate features of some specific models based on our framework that are highly related to the behavior of backtracking search algorithms.

APA, Harvard, Vancouver, ISO, and other styles

38

Barto, Libor, Jakub Bulín, Andrei Krokhin, and Jakub Opršal. "Algebraic Approach to Promise Constraint Satisfaction." Journal of the ACM 68, no. 4 (July 7, 2021): 1–66. http://dx.doi.org/10.1145/3457606.

Full text

Abstract:

The complexity and approximability of the constraint satisfaction problem (CSP) has been actively studied over the past 20 years. A new version of the CSP, the promise CSP (PCSP), has recently been proposed, motivated by open questions about the approximability of variants of satisfiability and graph colouring. The PCSP significantly extends the standard decision CSP. The complexity of CSPs with a fixed constraint language on a finite domain has recently been fully classified, greatly guided by the algebraic approach, which uses polymorphisms—high-dimensional symmetries of solution spaces—to analyse the complexity of problems. The corresponding classification for PCSPs is wide open and includes some long-standing open questions, such as the complexity of approximate graph colouring, as special cases. The basic algebraic approach to PCSP was initiated by Brakensiek and Guruswami, and in this article, we significantly extend it and lift it from concrete properties of polymorphisms to their abstract properties. We introduce a new class of problems that can be viewed as algebraic versions of the (Gap) Label Cover problem and show that every PCSP with a fixed constraint language is equivalent to a problem of this form. This allows us to identify a “measure of symmetry” that is well suited for comparing and relating the complexity of different PCSPs via the algebraic approach. We demonstrate how our theory can be applied by giving both general and specific hardness/tractability results. Among other things, we improve the state-of-the-art in approximate graph colouring by showing that, for any k ≥ 3, it is NP-hard to find a (2 k -1)-colouring of a given k -colourable graph.

APA, Harvard, Vancouver, ISO, and other styles

39

Brafman, Ronen, Enrico Pilotto, Francesca Rossi, Domenico Salvagnin, Kristen Venable, and Toby Walsh. "The Next Best Solution." Proceedings of the AAAI Conference on Artificial Intelligence 25, no. 1 (August 4, 2011): 1537–40. http://dx.doi.org/10.1609/aaai.v25i1.7958.

Full text

Abstract:

We study the computational complexity of finding the next most preferred solution in some common formalisms for representing constraints and preferences. The problem is computationally intractable for CSPs, but is polynomial for tree-shaped CSPs and tree-shaped fuzzy CSPs. On the other hand, it is intractable for weighted CSPs, even under restrictions on the constraint graph. For CP-nets, the problem is polynomial when the CP-net is acyclic. This remains so if we add (soft) constraints that are tree-shaped and topologically compatible with the CP-net.

APA, Harvard, Vancouver, ISO, and other styles

40

Gorti, Sreenivasa Rao, Salal Humair, Ram D. Sriram, Sarosh Talukdar, and Sesh Murthy. "Solving constraint satisfaction problems using ATeams." Artificial Intelligence for Engineering Design, Analysis and Manufacturing 10, no. 1 (January 1996): 1–19. http://dx.doi.org/10.1017/s0890060400001256.

Full text

Abstract:

AbstractThis paper presents an approach to solving constraint satisfaction problems using Asynchronous Teams of autonomous agents (ATeams). The focus for the constraint satisfaction problem is derived from an effort to support spatial layout generation in a conceptual design framework. The constraint specification allows a high-level representation and manipulation of qualitative geometric information. We present a computational technique based on ATeams to instantiate solutions to the constraint satisfaction problem. The technique uses a search for a solution in numerical space. This permits us to handle both qualitative relationships and numerical constraints in a unified framework. We show that simple knowledge, about human spatial reasoning and about the nature of arithmetic operators can be hierarchically encapsulated and exploited efficiently in the search. An example illustrates the generality of the approach for conceptual design. We also present empirical studies that contrast the efficiency of ATeams with a search based on genetic algorithms. Based on these preliminary results, we argue that the ATeams approach elegantly handles arbitrary sets of constraints, is computationally efficient, and hence merits further investigation.

APA, Harvard, Vancouver, ISO, and other styles

41

Yeoh, William, and Makoto Yokoo. "Distributed Problem Solving." AI Magazine 33, no. 3 (September 20, 2012): 53. http://dx.doi.org/10.1609/aimag.v33i3.2429.

Full text

Abstract:

Distributed problem solving is a subfield within multiagent systems, where agents are assumed to be part of a team and collaborate with each other to reach a common goal. In this article, we illustrate the motivations for distributed problem solving and provide an overview of two distributed problem solving models, namely distributed constraint satisfaction problems (DCSPs) and distributed constraint optimization problems (DCOPs), and some of their algorithms.

APA, Harvard, Vancouver, ISO, and other styles

42

Quach, Xuan Hung, and Thi Lan Giao Hoang. "Dealing with fuzzy ontology integration problem by using constraint satisfaction problem." International Journal of Advanced Computer Research 7, no. 30 (April 12, 2017): 81–87. http://dx.doi.org/10.19101/ijacr.2017.729009.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Delafosse, Mélanie, Arnaud Clerentin, Laurent Delahoche, Eric Brassart, and Bruno Marhic. "The mobile robot localization problem treated as a constraint satisfaction problem." IFAC Proceedings Volumes 37, no. 8 (July 2004): 394–99. http://dx.doi.org/10.1016/s1474-6670(17)32008-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Barták, Roman, Radomír Černoch, Ondřej Kuželka, and Filip Železný. "Formulating the template ILP consistency problem as a constraint satisfaction problem." Constraints 18, no. 2 (February 12, 2013): 144–65. http://dx.doi.org/10.1007/s10601-013-9141-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Chun, Andy. "Train Outstable Scheduling as Constraint Satisfaction." Proceedings of the AAAI Conference on Artificial Intelligence 27, no. 2 (July 14, 2013): 1513–18. http://dx.doi.org/10.1609/aaai.v27i2.18992.

Full text

Abstract:

This paper outlines the design of a scheduling algorithm that allocates outstabling locations to railway trains. From time to time railway trains may need to be outstabled to temporary locations, such as stations, sidings, depots, etc., until they are needed for regular operations. This is common for urban rail transit, and especially so for those that do not operate 24 hours. During non-traffic hours (NTH), trains are outstabled to various locations along the rail network so that when operations start again next day, the trains will be nearby their originating station or conveniently located so that they can be put into service whenever needed. However, this is complicated by the fact that engineering works, such as rail testing, installation, regular maintenance, etc. are done during the NTH. Therefore, passenger trains must be outstabled in such a way that they do not interfere with night-time engineering works or the movements of associated engineering trains. Since the engineering works scheduling is done separate to outstabling, this is a mixed-system problem. This paper shows how we modeled this as a constraint-satisfaction problem (CSP) and implemented into an “Outstabling System” (OSS) for the Hong Kong Mass Transit Railway (MTR) using a two-stage search algorithm

APA, Harvard, Vancouver, ISO, and other styles

46

LARROSA, JAVIER, and GABRIEL VALIENTE. "Constraint satisfaction algorithms for graph pattern matching." Mathematical Structures in Computer Science 12, no. 4 (August 2002): 403–22. http://dx.doi.org/10.1017/s0960129501003577.

Full text

Abstract:

Graph pattern matching is a central problem in many application fields. Since it is NP-complete, we cannot expect to find algorithms with a good worst-case performance. However, there is still room for general procedures with a good average performance. In this paper we explore four different solving approaches within the constraint satisfaction framework, and introduce a new algorithm, which we call nRF+. The algorithm is a refinement of really full look ahead that takes advantage of the problem structure in order to enhance the look ahead procedure. We give a formal proof that nRF+ is superior to the other approaches in terms of number of visited nodes. An additional contribution of this paper is the introduction of a new benchmark for testing algorithms in this domain. It is formed by a large set of well-defined graphs of very diverse nature. In this benchmark, we show that nRF+ can efficiently solve a broad range of problems, while still leaving many problem instances unsolved. The use of this challenging benchmark is encouraged for future algorithms evaluation.

APA, Harvard, Vancouver, ISO, and other styles

47

Deruyver, A., and Y. Hodé. "Constraint satisfaction problem with bilevel constraint: application to interpretation of over-segmented images." Artificial Intelligence 93, no. 1-2 (June 1997): 321–35. http://dx.doi.org/10.1016/s0004-3702(97)00022-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Ďuriš, Viliam. "Algorithmic Verification of Constraint Satisfaction Method on Timetable Problem." Mathematics and Statistics 8, no. 6 (November 2020): 728–39. http://dx.doi.org/10.13189/ms.2020.080614.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Helzerman, R. A., and M. P. Harper. "MUSE CSP: An Extension to the Constraint Satisfaction Problem." Journal of Artificial Intelligence Research 5 (November 1, 1996): 239–88. http://dx.doi.org/10.1613/jair.298.

Full text

Abstract:

This paper describes an extension to the constraint satisfaction problem (CSP) called MUSE CSP (MUltiply SEgmented Constraint Satisfaction Problem). This extension is especially useful for those problems which segment into multiple sets of partially shared variables. Such problems arise naturally in signal processing applications including computer vision, speech processing, and handwriting recognition. For these applications, it is often difficult to segment the data in only one way given the low-level information utilized by the segmentation algorithms. MUSE CSP can be used to compactly represent several similar instances of the constraint satisfaction problem. If multiple instances of a CSP have some common variables which have the same domains and constraints, then they can be combined into a single instance of a MUSE CSP, reducing the work required to apply the constraints. We introduce the concepts of MUSE node consistency, MUSE arc consistency, and MUSE path consistency. We then demonstrate how MUSE CSP can be used to compactly represent lexically ambiguous sentences and the multiple sentence hypotheses that are often generated by speech recognition algorithms so that grammar constraints can be used to provide parses for all syntactically correct sentences. Algorithms for MUSE arc and path consistency are provided. Finally, we discuss how to create a MUSE CSP from a set of CSPs which are labeled to indicate when the same variable is shared by more than a single CSP.

APA, Harvard, Vancouver, ISO, and other styles

50

Dyer, Martin, and David Richerby. "An Effective Dichotomy for the Counting Constraint Satisfaction Problem." SIAM Journal on Computing 42, no. 3 (January 2013): 1245–74. http://dx.doi.org/10.1137/100811258.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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!