Network-based heuristics for constraint-satisfaction problems

DOI10.1016/0004-3702(87)90002-6zbMath0643.68156OpenAlexW2061734130MaRDI QIDQ1102137

Rina Dechter, Judea Pearl

Publication date: 1988

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0004-3702(87)90002-6

zbMATH Keywords

constraint-satisfaction problemssparse networks of constraints

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (only showing first 100 items - show all)

Reduction operations in fuzzy or valued constraint satisfaction ⋮ On neighbourhood singleton-style consistencies for qualitative spatial and temporal reasoning ⋮ Tractability in constraint satisfaction problems: a survey ⋮ Non-local configuration of component interfaces by constraint satisfaction ⋮ Investigating production system representations for non-combinatorial match ⋮ Experimental evaluation of preprocessing algorithms for constraint satisfaction problems ⋮ Problem solving by searching for models with a theorem prover ⋮ Local consistency in parallel constraint satisfaction networks ⋮ Partition search for non-binary constraint satisfaction ⋮ An optimal backtrack algorithm for tree-structured constraint satisfaction problems ⋮ Model-based inference in CHARME. ⋮ Mixed deterministic and probabilistic networks ⋮ Iterative coloring extension of a maximum clique ⋮ Constraint relaxation may be perfect ⋮ Probability propagation ⋮ Parallel consistent labeling algorithms ⋮ Some fundamental properties of local constraint propagation ⋮ Domain permutation reduction for constraint satisfaction problems ⋮ Semiring induced valuation algebras: exact and approximate local computation algorithms ⋮ Symbolic techniques in satisfiability solving ⋮ Distributed CSPs by graph partitioning ⋮ Tree clustering for constraint networks ⋮ Qualitative probabilities for default reasoning, belief revision, and causal modeling ⋮ Default reasoning using classical logic ⋮ From chaotic iteration to constraint propagation ⋮ Metaheuristics: A bibliography ⋮ On computing minimal models ⋮ Interleaving solving and elicitation of constraint satisfaction problems based on expected cost ⋮ Propositional semantics for disjunctive logic programs ⋮ No more ``Partial and ``Full Looking Ahead ⋮ Locating the phase transition in binary constraint satisfaction problems ⋮ Structure-driven algorithms for truth maintenance ⋮ On the hardness of approximate reasoning ⋮ A statistical approach to adaptive problem solving ⋮ From local to global consistency in temporal constraint networks ⋮ Local and global relational consistency ⋮ The complexity of constraint satisfaction revisited ⋮ Uncovering trees in constraint networks ⋮ A non-binary constraint ordering heuristic for constraint satisfaction problems ⋮ Processing disjunctions in temporal constraint networks ⋮ Linear-programming design and analysis of fast algorithms for Max 2-CSP ⋮ Learning heuristic functions for large state spaces ⋮ Portfolios in stochastic local search: efficiently computing most probable explanations in Bayesian networks ⋮ Constant-degree graph expansions that preserve treewidth ⋮ Decomposing a relation into a tree of binary relations ⋮ Accelerating exact and approximate inference for (distributed) discrete optimization with GPUs ⋮ Fuzzy reasoning in a multidimensional space of hypotheses ⋮ Tradeoffs in the Complexity of Backdoor Detection ⋮ Hybrid tractability of valued constraint problems ⋮ A logic-based analysis of Dempster-Shafer theory ⋮ The essence of constraint propagation ⋮ Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search ⋮ Polynomial algorithm of limited propositional deduction ⋮ Bounded-width QBF is PSPACE-complete ⋮ A unified theory of structural tractability for constraint satisfaction problems ⋮ The complexity of reasoning with global constraints ⋮ Controlled generation of hard and easy Bayesian networks: Impact on maximal clique size in tree clustering ⋮ Unifying tree decompositions for reasoning in graphical models ⋮ An optimal coarse-grained arc consistency algorithm ⋮ Asynchronous backtracking without adding links: a new member in the ABT family ⋮ Temporal constraint networks ⋮ A canonical form for generalized linear constraints ⋮ Distributed personnel scheduling -- negotiation among scheduling agents ⋮ From local to global consistency ⋮ Integer programs for logic constraint satisfaction ⋮ Solving the minimum-weighted coloring problem ⋮ On some partial line graphs of a hypergraph and the associated matroid ⋮ A generic arc-consistency algorithm and its specializations ⋮ Scheduling with neural networks -- the case of the Hubble Space Telescope ⋮ Constraint reasoning based on interval arithmetic: The tolerance propagation approach ⋮ Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems ⋮ Structure identification in relational data ⋮ Constraint solving for proof planning ⋮ Combinatorial problems raised from 2-semilattices ⋮ A new tractable class of constraint satisfaction problems ⋮ A polynomial relational class of binary CSP ⋮ Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination ⋮ Understanding the scalability of Bayesian network inference using clique tree growth curves ⋮ Constraint Satisfaction ⋮ The job shop scheduling problem: Conventional and new solution techniques ⋮ Constraints, consistency and closure ⋮ AND/OR search spaces for graphical models ⋮ Maintaining reversible DAC for Max-CSP ⋮ A methodology for the reduction of imprecision in the engineering process ⋮ A framework for decision support systems of scheduling problems ⋮ Backtracking algorithms for disjunctions of temporal constraints ⋮ Constraint propagation techniques for the disjunctive scheduling problem ⋮ Querying temporal and spatial constraint networks in PTIME ⋮ A comparison of structural CSP decomposition methods ⋮ Tractable reasoning via approximation ⋮ Counting representable sets on simple graphs ⋮ Backjump-based backtracking for constraint satisfaction problems ⋮ Dynamic variable ordering in graph based backjumping algorithms for csps ⋮ Compiling constraint satisfaction problems ⋮ Decomposing constraint satisfaction problems using database techniques ⋮ Characterising tractable constraints ⋮ Fuzzy constraint networks for signal pattern recognition ⋮ A tabu search approach to the constraint satisfaction problem as a general problem solver ⋮ Constraint solving in uncertain and dynamic environments: A survey ⋮ High-order consistency in valued constraint satisfaction

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• A method for computing heuristics in problem solving
• Consistency in networks of relations
• Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis
• Networks of constraints: Fundamental properties and applications to picture processing
• Planning in a hierarchy of abstraction spaces
• Nonserial dynamic programming
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Intelligent Backtracking in Plan-Based Deduction
• A sufficient condition for backtrack-bounded search
• The average complexity of depth-first search with backtracking and cutoff
• A Sufficient Condition for Backtrack-Free Search
• Estimating the Efficiency of Backtrack Programs

This page was built for publication: Network-based heuristics for constraint-satisfaction problems