Log in

Relevant bibliographies by topics / Constraint satisfaction / Journal articles

Journal articles on the topic 'Constraint satisfaction'

To see the other types of publications on this topic, follow the link: Constraint satisfaction.

Author: Grafiati

Published: 4 June 2021

Last updated: 29 July 2024

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.'

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

Pu, Jiantao, and Karthik Ramani. "Priority-Based Geometric Constraint Satisfaction." Journal of Computing and Information Science in Engineering 7, no. 4 (June 14, 2007): 322–29. http://dx.doi.org/10.1115/1.2795301.

Full text

Abstract:

A well-constrained geometric system seldom occurs in practice, especially at the sketch-based initial conceptual design stage. Usually, it is either under- or overconstrained because design is a progressive process and it is difficult for a designer to specify all involved constraints in a consistent way. This paper presents a priority-based graph-reduction solution, in which each constraint is assigned with a priority to guide the reduction of a geometric constraint graph. The advantage of this method lies in its ability to find the optimal solutions to a geometric constraint system automatically, without requiring interactive intervention from users.

APA, Harvard, Vancouver, ISO, and other styles

2

Detassis, Fabrizio, Michele Lombardi, and Michela Milano. "Teaching the Old Dog New Tricks: Supervised Learning with Constraints." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 5 (May 18, 2021): 3742–49. http://dx.doi.org/10.1609/aaai.v35i5.16491.

Full text

Abstract:

Adding constraint support in Machine Learning has the potential to address outstanding issues in data-driven AI systems, such as safety and fairness. Existing approaches typically apply constrained optimization techniques to ML training, enforce constraint satisfaction by adjusting the model design, or use constraints to correct the output. Here, we investigate a different, complementary, strategy based on "teaching" constraint satisfaction to a supervised ML method via the direct use of a state-of-the-art constraint solver: this enables taking advantage of decades of research on constrained optimization with limited effort. In practice, we use a decomposition scheme alternating master steps (in charge of enforcing the constraints) and learner steps (where any supervised ML model and training algorithm can be employed). The process leads to approximate constraint satisfaction in general, and convergence properties are difficult to establish; despite this fact, we found empirically that even a naive setup of our approach performs well on ML tasks with fairness constraints, and on classical datasets with synthetic constraints.

APA, Harvard, Vancouver, ISO, and other styles

3

Frank, Jeremy. "Revisiting dynamic constraint satisfaction for model-based planning." Knowledge Engineering Review 31, no. 5 (November 2016): 429–39. http://dx.doi.org/10.1017/s0269888916000242.

Full text

Abstract:

AbstractAs planning problems become more complex, it is increasingly useful to integrate complex constraints on time and resources into planning models, and use constraint reasoning approaches to help solve the resulting problems. Dynamic constraint satisfaction is a key enabler of automated planning in the presence of such constraints. In this paper, we identify some limitations with the previously developed theories of dynamic constraint satisfaction. We identify a minimum set of elementary transformations from which all other transformations can be constructed. We propose a new classification of dynamic constraint satisfaction transformations based on a formal criteria, namely the change in the fraction of solutions. This criteria can be used to evaluate elementary transformations of a constraint satisfaction problem as well as sequences of transformations. We extend the notion of transformations to include constrained optimization problems. We discuss how this new framework can inform the evolution of planning models, automated planning algorithms, and mixed-initiative planning.

APA, Harvard, Vancouver, ISO, and other styles

4

LIU, BING. "SPECIFIC CONSTRAINT HANDLING IN CONSTRAINT SATISFACTION PROBLEMS." International Journal on Artificial Intelligence Tools 03, no. 01 (March 1994): 79–96. http://dx.doi.org/10.1142/s0218213094000066.

Full text

Abstract:

Abundant literatures exist on consistency techniques for solving Constraint Satisfaction Problems (CSPs). These literatures, however, focused mainly on finding efficient general techniques to achieve network consistency and to solve CSPs. So far, many techniques have been reported, e.g., node consistency, arc consistency, path consistency, k-consistency, forward checking, lookahead, partial lookahead, etc. Not enough attention has been given to individual constraints, and how constraint specific features may be exploited for more efficient consistency check. Many types of constraints exist in real problems, and each has its own features. These features may allow specific consistency techniques to be designed such that they are more efficient than the general algorithms. To analyze this issue, we divide a consistency algorithm into three parts: (1) activating constraints for check; (2) selecting the next constraint to be checked; and (3) checking the selected constraint. We will discuss how constraint specific features may influence each of these aspects and how special handling techniques may be designed to improve the efficiency. In order to allow these individual constraint handling techniques to be used, a new consistency algorithm is also proposed.

APA, Harvard, Vancouver, ISO, and other styles

5

Bulatov, Andrei A., and Dániel Marx. "Constraint satisfaction problems and global cardinality constraints." Communications of the ACM 53, no. 9 (September 2010): 99–106. http://dx.doi.org/10.1145/1810891.1810914.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Deville, Yves, Olivier Barette, and Pascal Van Hentenryck. "Constraint satisfaction over connected row-convex constraints." Artificial Intelligence 109, no. 1-2 (June 1999): 243–71. http://dx.doi.org/10.1016/s0004-3702(99)00012-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Brito, Ismel, Amnon Meisels, Pedro Meseguer, and Roie Zivan. "Distributed constraint satisfaction with partially known constraints." Constraints 14, no. 2 (May 15, 2008): 199–234. http://dx.doi.org/10.1007/s10601-008-9048-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Rossi, Francesca, Kristen Brent Venable, and Toby Walsh. "Preferences in Constraint Satisfaction and Optimization." AI Magazine 29, no. 4 (December 28, 2008): 58. http://dx.doi.org/10.1609/aimag.v29i4.2202.

Full text

Abstract:

We review constraint-based approaches to handle preferences. We start by defining the main notions of constraint programming, then give various concepts of soft constraints and show how they can be used to model quantitative preferences. We then consider how soft constraints can be adapted to handle other forms of preferences, such as bipolar, qualitative, and temporal preferences. Finally, we describe how AI techniques such as abstraction, explanation generation, machine learning, and preference elicitation, can be useful in modelling and solving soft constraints.

APA, Harvard, Vancouver, ISO, and other styles

9

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

10

Duffy, Ken R., Charles Bordenave, and Douglas J. Leith. "Decentralized Constraint Satisfaction." IEEE/ACM Transactions on Networking 21, no. 4 (August 2013): 1298–308. http://dx.doi.org/10.1109/tnet.2012.2222923.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Bulatov, Andrei A. "Constraint satisfaction problems." ACM SIGLOG News 5, no. 4 (November 12, 2018): 4–24. http://dx.doi.org/10.1145/3292048.3292050.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Nadel, Bernard A. "Constraint satisfaction algorithms." Computational Intelligence 5, no. 3 (September 1989): 188–224. http://dx.doi.org/10.1111/j.1467-8640.1989.tb00328.x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Freuder, Eugene C., and Richard J. Wallace. "Partial constraint satisfaction." Artificial Intelligence 58, no. 1-3 (December 1992): 21–70. http://dx.doi.org/10.1016/0004-3702(92)90004-h.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Van Hentenryck, Pascal, Helmut Simonis, and Mehmet Dincbas. "Constraint satisfaction using constraint logic programming." Artificial Intelligence 58, no. 1-3 (December 1992): 113–59. http://dx.doi.org/10.1016/0004-3702(92)90006-j.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

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

16

KÖKÉNY, TIBOR. "CONSTRAINT SATISFACTION PROBLEMS WITH ORDER-SORTED DOMAINS." International Journal on Artificial Intelligence Tools 04, no. 01n02 (June 1995): 55–72. http://dx.doi.org/10.1142/s0218213095000048.

Full text

Abstract:

In order to improve constraint satisfaction techniques, a promising way is to use special features of constraints and variable domains. This paper examines a special class of CSPs (Constraint Satisfaction Problems) in which a partial order is defined on each domain and the constraints are compatible with these orders. A special arc-consistency algorithm for this case is presented and some questions about finding all solutions are discussed. The presented ideas can be used in constraint systems implemented in an object-oriented language, where inheritance hierarchy of objects is a natural support for the presented CSP type.

APA, Harvard, Vancouver, ISO, and other styles

17

Fellows, Michael, Tobias Friedrich, Danny Hermelin, Nina Narodytska, and Frances Rosamond. "Constraint satisfaction problems: Convexity makes AllDifferent constraints tractable." Theoretical Computer Science 472 (February 2013): 81–89. http://dx.doi.org/10.1016/j.tcs.2012.11.038.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Bessiere, C., I. Brito, P. Gutierrez, and P. Meseguer. "Global Constraints in Distributed Constraint Satisfaction and Optimization." Computer Journal 57, no. 6 (August 30, 2013): 906–23. http://dx.doi.org/10.1093/comjnl/bxt088.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Sharon, Guni. "Partial Domain Search Tree for Constraint-Satisfaction Problems." Proceedings of the International Symposium on Combinatorial Search 6, no. 1 (September 1, 2021): 196–200. http://dx.doi.org/10.1609/socs.v6i1.18370.

Full text

Abstract:

The traditional approach for solving Constraint satisfaction Problems (CSPs) is searching the Assignment Space in which each state represents an assignment to some variables. This paper suggests a new search space formalization for CSPs, the Partial Domain Search Tree (PDST). In each PDST node aunique subset of the original domain is considered, values are excluded from the domains in each node to insure that a given set of constraints is satisfied. We provide theoretical analysis of this new approach showing that searching the PDST is beneficial for loosely constrained problems. Experimental results show that this new formalization is a promising direction for future research. In some cases searching the PDST outperforms the traditional approach by an order of magnitude. Furthermore, PDST can enhance Local Search techniques resulting in solutions that violate up to 30% less constraints.

APA, Harvard, Vancouver, ISO, and other styles

20

Zuenko, Alexander A., Olga V. Fridman, and Olga N. Zuenko. "An approach to finding a global optimum in constrained clustering tasks involving the assessments of several experts." Transaction Kola Science Centre 12, no. 5-2021 (December 27, 2021): 75–90. http://dx.doi.org/10.37614/2307-5252.2021.5.12.007.

Full text

Abstract:

An approach to solving the constrained clustering problem has been developed, based on the aggregation of data obtained as a result of evaluating the characteristics of clustered objects by several independent experts, and the analysis of alternative variants of clustering by constraint programming methods using original heuristics. Objects clusterized are represented as multisets, which makes it possible to use appropriate methods of aggregation of expert opinions. It is proposed to solve the constrained clustering problem as a constraint satisfaction problem. The main attention is paid to the issue of reducing the number and simplifying the constraints of the constraint satisfaction problem at the stage of its formalization. Within the framework of the approach, we have created: a) a method for estimating the optimal value of the objective function by hierarchical clustering of multisets, taking into account a priori constraints of the subject domain, and b) a method for generating additional constraints on the desired solution in the form of “smart tables”, based on the obtained estimate. The approach allows us to find the best partition in the problems of the class under consideration, which are characterized by a high dimension.

APA, Harvard, Vancouver, ISO, and other styles

21

Hawkins, P. J., V. Lagoon, and P. J. Stuckey. "Solving Set Constraint Satisfaction Problems using ROBDDs." Journal of Artificial Intelligence Research 24 (July 1, 2005): 109–56. http://dx.doi.org/10.1613/jair.1638.

Full text

Abstract:

In this paper we present a new approach to modeling finite set domain constraint problems using Reduced Ordered Binary Decision Diagrams (ROBDDs). We show that it is possible to construct an efficient set domain propagator which compactly represents many set domains and set constraints using ROBDDs. We demonstrate that the ROBDD-based approach provides unprecedented flexibility in modeling constraint satisfaction problems, leading to performance improvements. We also show that the ROBDD-based modeling approach can be extended to the modeling of integer and multiset constraint problems in a straightforward manner. Since domain propagation is not always practical, we also show how to incorporate less strict consistency notions into the ROBDD framework, such as set bounds, cardinality bounds and lexicographic bounds consistency. Finally, we present experimental results that demonstrate the ROBDD-based solver performs better than various more conventional constraint solvers on several standard set constraint problems.

APA, Harvard, Vancouver, ISO, and other styles

22

Buscema, Massimo. "Constraint Satisfaction Neural Networks." Substance Use & Misuse 33, no. 2 (January 1998): 389–408. http://dx.doi.org/10.3109/10826089809115873.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Chentsov, A. G. "On approximate constraint satisfaction." Russian Mathematics 55, no. 2 (February 2011): 75–89. http://dx.doi.org/10.3103/s1066369x11020095.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Little, James, and Edward Tsang. "Foundations of Constraint Satisfaction." Journal of the Operational Research Society 46, no. 5 (May 1995): 666. http://dx.doi.org/10.2307/2584541.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Coja-Oghlan, Amin. "Random Constraint Satisfaction Problems." Electronic Proceedings in Theoretical Computer Science 9 (November 15, 2009): 32–37. http://dx.doi.org/10.4204/eptcs.9.4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Little, James. "Foundations of Constraint Satisfaction." Journal of the Operational Research Society 46, no. 5 (May 1995): 666–67. http://dx.doi.org/10.1057/jors.1995.93.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Feder, Tomás, and Pavol Hell. "Full Constraint Satisfaction Problems." SIAM Journal on Computing 36, no. 1 (January 2006): 230–46. http://dx.doi.org/10.1137/s0097539703427197.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Thagard, Paul, and Karsten Verbeurgt. "Coherence as Constraint Satisfaction." Cognitive Science 22, no. 1 (January 1998): 1–24. http://dx.doi.org/10.1207/s15516709cog2201_1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Gabrys, Gareth, and Alan Lesgold. "Coherence: Beyond constraint satisfaction." Behavioral and Brain Sciences 12, no. 3 (September 1989): 475. http://dx.doi.org/10.1017/s0140525x00057137.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Weigel, Rainer, and Boi Faltings. "Compiling constraint satisfaction problems." Artificial Intelligence 115, no. 2 (December 1999): 257–87. http://dx.doi.org/10.1016/s0004-3702(99)00077-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Bodirsky, Manuel, Victor Dalmau, Barnaby Martin, Antoine Mottet, and Michael Pinsker. "Distance constraint satisfaction problems." Information and Computation 247 (April 2016): 87–105. http://dx.doi.org/10.1016/j.ic.2015.11.010.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Hower, Walter. "Revisiting global constraint satisfaction." Information Processing Letters 66, no. 1 (April 1998): 41–48. http://dx.doi.org/10.1016/s0020-0190(98)00023-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Bodirsky, Manuel, and Marcello Mamino. "Tropically Convex Constraint Satisfaction." Theory of Computing Systems 62, no. 3 (April 17, 2017): 481–509. http://dx.doi.org/10.1007/s00224-017-9762-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Kirousis, Lefteris M. "Fast parallel constraint satisfaction." Artificial Intelligence 64, no. 1 (November 1993): 147–60. http://dx.doi.org/10.1016/0004-3702(93)90063-h.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Hamadi, Youssef, and Georg Ringwelski. "Boosting distributed constraint satisfaction." Journal of Heuristics 17, no. 3 (April 20, 2010): 251–79. http://dx.doi.org/10.1007/s10732-010-9134-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Bodirsky, Manuel, and Hubie Chen. "Relatively quantified constraint satisfaction." Constraints 14, no. 1 (July 6, 2008): 3–15. http://dx.doi.org/10.1007/s10601-008-9054-z.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Goyal, Kshitij, Sebastijan Dumancic, and Hendrik Blockeel. "DeepSaDe: Learning Neural Networks That Guarantee Domain Constraint Satisfaction." Proceedings of the AAAI Conference on Artificial Intelligence 38, no. 11 (March 24, 2024): 12199–207. http://dx.doi.org/10.1609/aaai.v38i11.29109.

Full text

Abstract:

As machine learning models, specifically neural networks, are becoming increasingly popular, there are concerns regarding their trustworthiness, specially in safety-critical applications, e.g. actions of an autonomous vehicle must be safe. There are approaches that can train neural networks where such domain requirements are enforced as constraints, but they either cannot guarantee that the constraint will be satisfied by all possible predictions (even on unseen data) or they are limited in the type of constraints that can be enforced. In this paper, we present an approach to train neural networks which can enforce a wide variety of constraints and guarantee that the constraint is satisfied by all possible predictions. The approach builds on earlier work where learning linear models is formulated as a constraint satisfaction problem (CSP). To make this idea applicable to neural networks, two crucial new elements are added: constraint propagation over the network layers, and weight updates based on a mix of gradient descent and CSP solving. Evaluation on various machine learning tasks demonstrates that our approach is flexible enough to enforce a wide variety of domain constraints and is able to guarantee them in neural networks.

APA, Harvard, Vancouver, ISO, and other styles

38

Desaraju, Vishnu R., Alexander E. Spitzer, Cormac O’Meadhra, Lauren Lieu, and Nathan Michael. "Leveraging experience for robust, adaptive nonlinear MPC on computationally constrained systems with time-varying state uncertainty." International Journal of Robotics Research 37, no. 13-14 (September 11, 2018): 1690–712. http://dx.doi.org/10.1177/0278364918793717.

Full text

Abstract:

This paper presents a robust-adaptive nonlinear model predictive control (MPC) technique that leverages past experiences to achieve tractability on computationally constrained systems. We propose a robust extension of the Experience-driven Predictive Control (EPC) algorithm via a Gaussian belief propagation strategy that computes an uncertainty set, bounding the evolution of the system state in the presence of time-varying state uncertainty. This uncertainty set is used to tighten the constraints in the predictive control formulation via a chance-constrained approach, thereby providing a probabilistic guarantee of constraint satisfaction. The parameterized form of the controllers produced by EPC coupled with online uncertainty estimates ensures that this robust constraint satisfaction property persists, even as the system switches controllers and experiences variations in the uncertainty model. We validate the online performance and robust constraint satisfaction of the proposed Robust EPC algorithm through a series of trials with a simulated ground robot and three experimental platforms: (1) a small quadrotor aerial robot executing aggressive maneuvers in wind with degraded state estimates, (2) a skid-steer ground robot equipped with a laser-based localization system, and (3) a hexarotor aerial robot equipped with a vision-based localization system.

APA, Harvard, Vancouver, ISO, and other styles

39

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

40

Hou, Dong-liang, and Fang-rong Chen. "Constraint Satisfaction Technology for Stacking Problem with Ordered Constraints." Procedia Engineering 29 (2012): 3317–21. http://dx.doi.org/10.1016/j.proeng.2012.01.487.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

NAANAA, WADY, and SIMONE PIMONT. "Handling structured and ambiguous constraints in constraint satisfaction problems." Journal of Experimental & Theoretical Artificial Intelligence 10, no. 1 (January 1998): 91–102. http://dx.doi.org/10.1080/095281398146932.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Law, Y. C., and J. H. M. Lee. "Symmetry Breaking Constraints for Value Symmetries in Constraint Satisfaction." Constraints 11, no. 2-3 (June 14, 2006): 221–67. http://dx.doi.org/10.1007/s10601-006-7095-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

De Haan, Ronald, Iyad Kanj, and Stefan Szeider. "On the Subexponential-Time Complexity of CSP." Journal of Artificial Intelligence Research 52 (January 30, 2015): 203–34. http://dx.doi.org/10.1613/jair.4540.

Full text

Abstract:

Not all NP-complete problems share the same practical hardness with respect to exact computation. Whereas some NP-complete problems are amenable to efficient computational methods, others are yet to show any such sign. It becomes a major challenge to develop a theoretical framework that is more fine-grained than the theory of NP-completeness, and that can explain the distinction between the exact complexities of various NP-complete problems. This distinction is highly relevant for constraint satisfaction problems under natural restrictions, where various shades of hardness can be observed in practice. Acknowledging the NP-hardness of such problems, one has to look beyond polynomial time computation. The theory of subexponential-time complexity provides such a framework, and has been enjoying increasing popularity in complexity theory. An instance of the constraint satisfaction problem with n variables over a domain of d values can be solved by brute-force in dn steps (omitting a polynomial factor). In this paper we study the existence of subexponential-time algorithms, that is, algorithms running in do(n) steps, for various natural restrictions of the constraint satisfaction problem. We consider both the constraint satisfaction problem in which all the constraints are given extensionally as tables, and that in which all the constraints are given intensionally in the form of global constraints. We provide tight characterizations of the subexponential-time complexity of the aforementioned problems with respect to several natural structural parameters, which allows us to draw a detailed landscape of the subexponential-time complexity of the constraint satisfaction problem. Our analysis provides fundamental results indicating whether and when one can significantly improve on the brute-force search approach for solving the constraint satisfaction problem.

APA, Harvard, Vancouver, ISO, and other styles

44

Wang, Xiao Fei, Xi Zhang, Yue Bing Chen, Lei Zhang, and Chao Jing Tang. "Spectrum Assignment Algorithm Based on Clonal Selection in Cognitive Radio Networks." Advanced Materials Research 457-458 (January 2012): 931–39. http://dx.doi.org/10.4028/www.scientific.net/amr.457-458.931.

Full text

Abstract:

An improved-immune-clonal-selection based spectrum assignment algorithm (IICSA) in cognitive radio networks is proposed, combing graph theory and immune optimization. It uses constraint satisfaction operation to make encoded antibody population satisfy constraints, and realizes the global optimization. The random-constraint satisfaction operator and fair-constraint satisfaction operator are designed to guarantee efficiency and fairness, respectively. Simulations are performed for performance comparison between the IICSA and the color-sensitive graph coloring algorithm. The results indicate that the proposed algorithm increases network utilization, and efficiently improves the fairness.

APA, Harvard, Vancouver, ISO, and other styles

45

TYAN, CHING-YU, PAUL P. WANG, and DENNIS R. BAHLER. "THE DESIGN OF AN ADAPTIVE MULTIPLE AGENT FUZZY CONSTRAINT-BASED CONTROLLER (MAFCC) FOR A COMPLEX HYDRAULIC SYSTEM." International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 04, no. 06 (December 1996): 537–51. http://dx.doi.org/10.1142/s0218488596000299.

Full text

Abstract:

In this paper, we present a complete design framework for an adaptive multiple agent fuzzy constraint-based controller (MAFCC) based on fuzzy penumbra constraint processing in each fuzzy constraint subnetwork collaborating with a connected constraint network and its corresponding semantic modeling in a first-order predicate calculus (FOPC) language, with application to a complex hydraulic system. The concept of “multiple agent” and “fuzzy constraint subnetwork” in a complex control system is introduced and some basic definitions of penumbra fuzzy constraint processing in a constraint subnetwork and the collaboration with an overall connected constraint network and its semantic modeling are addressed. As a result, a human agent interacts with system agents and allows the constraints to be added or deleted on-line according to the constraints imposed from the outside environment. Near-optimal system performance is accomplished by restricting all the penumbra constraints to be satisfied in each constraint subnetwork simultaneously which are interconnected as a result of constraints that exist between each of them. Following the principle of constraint satisfaction and fuzzy local propagation reasoning, each individual system agent is now constrained to behave in a certain fashion as dictated by the overall constraint network. In addition, the constraint network in MAFCC system provides an update strategy which makes a real time adaptive hydraulic control for all 20 cities possible.

APA, Harvard, Vancouver, ISO, and other styles

46

Satake, Yuki, Hiroshi Unno, and Hinata Yanagi. "Probabilistic Inference for Predicate Constraint Satisfaction." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 02 (April 3, 2020): 1644–51. http://dx.doi.org/10.1609/aaai.v34i02.5526.

Full text

Abstract:

In this paper, we present a novel constraint solving method for a class of predicate Constraint Satisfaction Problems (pCSP) where each constraint is represented by an arbitrary clause of first-order predicate logic over predicate variables. The class of pCSP properly subsumes the well-studied class of Constrained Horn Clauses (CHCs) where each constraint is restricted to a Horn clause. The class of CHCs has been widely applied to verification of linear-time safety properties of programs in different paradigms. In this paper, we show that pCSP further widens the applicability to verification of branching-time safety properties of programs that exhibit finitely-branching non-determinism. Solving pCSP (and CHCs) however is challenging because the search space of solutions is often very large (or unbounded), high-dimensional, and non-smooth. To address these challenges, our method naturally combines techniques studied separately in different literatures: counterexample guided inductive synthesis (CEGIS) and probabilistic inference in graphical models. We have implemented the presented method and obtained promising results on existing benchmarks as well as new ones that are beyond the scope of existing CHC solvers.

APA, Harvard, Vancouver, ISO, and other styles

47

Hasanoglu, Mehmet Sinan, and Melik Dolen. "Feasibility enhanced particle swarm optimization for constrained mechanical design problems." Proceedings of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science 232, no. 2 (December 8, 2016): 381–400. http://dx.doi.org/10.1177/0954406216681593.

Full text

Abstract:

Constrained optimization problems constitute an important fraction of optimization problems in the mechanical engineering domain. It is not uncommon for these problems to be highly-constrained where a specialized approach that aims to improve constraint satisfaction level of the whole population as well as finding the optimum is deemed useful especially when the objective functions are very costly. A new algorithm called Feasibility Enhanced Particle Swarm Optimization (FEPSO), which treats feasible and infeasible particles differently, is introduced. Infeasible particles in FEPSO do not need to evaluate objective functions and fly only based on social attraction depending on a single violated constraint, called the activated constraint, which is selected at each iteration based on constraint priorities and flight occurs only along dimensions of the search space to which the activated constraint is sensitive. To ensure progressive improvement of constraint satisfaction, particles are not allowed to violate a satisfied constraint in FEPSO. The highly-constrained four-stage gear train problem and its two variants introduced in this paper are used to assess the effectiveness of FEPSO. The results suggest that FEPSO is effective and consistent in obtaining feasible points, finding good solutions, and improving the constraint satisfaction level of the swarm as a whole.

APA, Harvard, Vancouver, ISO, and other styles

48

Adil, Bouhouch, Er-Rafyg Aicha, and Ez-Zahout Abderrahmane. "Neural network to solve fuzzy constraint satisfaction problems." IAES International Journal of Artificial Intelligence (IJ-AI) 13, no. 1 (March 1, 2024): 228. http://dx.doi.org/10.11591/ijai.v13.i1.pp228-235.

Full text

Abstract:

<p>It has been proven that solving the constraint satisfaction problem (CSP) is an No Polynomial hard combinatorial optimization problem. This holds true even in cases where the constraints are fuzzy, known as fuzzy constraint satisfaction problems (FCSP). Therefore, the continuous Hopfield neural network model can be utilized to resolve it. The original algorithm was developed by Talaavan in 2005. Many practical problems can be represented as a FCSP. In this paper, we expand on a neural network technique that was initially developed for solving CSP and adapt it to tackle problems that involve at least one fuzzy constraint. To validate the enhanced effectiveness and rapid convergence of our proposed approach, a series of numerical experiments are carried out. The results of these experiments demonstrate the superior performance of the new method. Additionally, the experiments confirm its fast convergence. Specifically, our study focuses on binary instances with ordinary constraints to test the proposed resolution model. The results confirm that both the proposed approaches and the original continuous Hopfield neural network approach exhibit similar performance and robustness in solving ordinary constraint satisfaction problems.</p>

APA, Harvard, Vancouver, ISO, and other styles

49

Xiang, Yang, Younis Mohamed, and Wanling Zhang. "Distributed constraint satisfaction with multiply sectioned constraint networks." International Journal of Information and Decision Sciences 6, no. 2 (2014): 127. http://dx.doi.org/10.1504/ijids.2014.061771.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Creignou, Nadia, Henning Schnoor, and Ilka Schnoor. "Nonuniform Boolean constraint satisfaction problems with cardinality constraint." ACM Transactions on Computational Logic 11, no. 4 (July 2010): 1–32. http://dx.doi.org/10.1145/1805950.1805954.

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!