The constrainedness of search
Published 4 August 1996
Ian P. Gent, Ewan MacIntyre, Patrick Prosser, Toby Walsh
Citations172
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A parameter that measures the "constrainedness" of an ensemble of combinatorial problems is introduced, which generalizes a number of parameters previously used in different NP-complete problem classes and can be directly compared.
Abstract
We introduce a parameter that measures the "constrainedness" of an ensemble of combinatorial problems. If problems are over-constrained, they are likely to be insoluble. If problems are under-constrained, they are likely to be soluble. This constrainedness parameter generalizes a number of parameters previously used in different NP-complete problem classes. Phase transitions in different NP classes can thus be directly compared. This parameter can also be used in a heuristic to guide search. The heuristic captures the intuition of making the most constrained choice first, since it is often useful to branch into the least constrained subproblem. Many widely disparate heuristics can be seen as minimizing constrainedness.
Keywords
Computer ScienceDecision SciencesEngineering
Communications of the ACMNew methods to color the vertices of a graph
1,564 Citations1979Daniel Brélaz
An exact method is given which performs better than the Randall-Brown algorithm and is able to color larger graphs and the new heuristic methods, the classical methods, and the exact method are compared.
Artificial IntelligenceIncreasing tree search efficiency for constraint satisfaction problems
1,114 Citations1980Robert M. Haralick, Gordon L. Elliott
Analytically and experimentally show that a lookahead procedure called forward checking which employs the most likely to fail principle performs better than standard backtracking, Ullman's, Waltz's, Mackworth's, and Haralick's discrete relaxation in all cases tested, and better than Gaschnig's backmarking in the larger problems.
Where the really hard problems are
1,021 Citations1991Peter Cheeseman, Bob Kanefsky +1 more
It is shown that NP-complete problems can be summarized by at least one "order parameter", and that the hard problems occur at a critical value of such a parameter.
National Conference on Artificial IntelligenceHard and easy distributions of SAT problems
801 Citations1992David G. M. Mitchell, Bart Selman +1 more
It is shown that by using the right distribution of instances, and appropriate parameter values, it is possible to generate random formulas that are hard, that is, for which satisfiability testing is quite difficult.
Choice Reviews OnlineEmpirical methods for artificial intelligence
637 Citations1996
Empirical research exploratory data analysis basic issues in experiment design hypothesis testing and estimation computer-intensive statistical methods performance assessment explaining performance - interactions and dependencies modelling tactics for generalization.
ScienceCritical Behavior in the Satisfiability of Random Boolean Expressions
598 Citations1994Scott Kirkpatrick, Bart Selman
Finite-size scaling, a method from statistical physics, can be used to characterize size-dependent effects near the threshold and a relationship can be drawn between thresholds and computational complexity.
Journal of the ACMComputing Partitions with Applications to the Knapsack Problem
565 Citations1974Ellis Horowitz, Sartaj Sahni
A technique is developed which improves all of the dynamic programming methods by asquare root factor and can be incorporated into the more general 0-1 knapsack problem obtaining a square root improvement in the asymptotic behavior.
Computational IntelligenceHYBRID ALGORITHMS FOR THE CONSTRAINT SATISFACTION PROBLEM
519 Citations1993Patrick Prosser
This paper presents an approach that allows base algorithms to be combined, giving us new hybrids, and it is shown that FC‐CBJ is by far the best of the algorithms examined.
Journal of HeuristicsTesting heuristics: We have it all wrong
426 Citations1995John Hooker
This article argues that a more scientific approach of controlled experimentation, similar to that used in other empirical sciences, avoids or alleviates problems of competitive testing in algorithmic experimentation.
Performance measurement and analysis of certain search algorithms.
333 Citations1979John Gaschnig
Artificial IntelligenceExperimental results on the crossover point in random 3-SAT
292 Citations1996James M. Crawford, Larry D. Auton
This paper reports on the most extensive set of experiments to date on the location and nature of the crossover point in satisfiability problems, finding no evidence of any hard problems in the under-constrained region.
Finite-size scaling
292 Citations1988John Cardy
Mick Gets Some (the Odds Are on His Side)
248 Citations1992Vašek Chvátal, Bruce A. Reed
Journal of AlgorithmsAnalysis of Two Simple Heuristics on a Random Instance ofk-sat
227 Citations1996Alan Frieze, Stephen Suen
The performance of two algorithms, GUC and SC, are considered, when applied to a random instance ?
Artificial IntelligenceLocating the phase transition in binary constraint satisfaction problems
219 Citations1996Barbara M. Smith, Martin Dyer
It is shown that the variance of the number of solutions can be used to set bounds on the phase transition and to indicate the accuracy of the prediction.
Experimental results on the crossover point in satisfiability problems
210 Citations1993James M. Crawford, Larry D. Auton
Empirically, it is found that for random 3-SAT problems below the crossover point, the average time complexity of satisfiability problems seems empirically to grow linearly with problem size, and at and above therossover point the complexity seems to grow exponentially, but the rate of growth seems to be greatest near the crossoverpoint.
Artificial IntelligenceAn empirical study of phase transitions in binary constraint satisfaction problems
171 Citations1996Patrick Prosser
It is shown that the theory of binary constraint satisfaction predicts where the hardest problems should occur, in close agreement with the empirical results, except when constraint graphs are sparse.
Management ScienceSome New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem
165 Citations1980G. Carpaneto, Paolo Toth
This paper presents a breadth-first branch and bound algorithm which differs from the method of Smith, Srinivasan and Thompson in the selection of the subtour to be split, in the ordering of the arcs in the selected subtour, and in the computation of different partial lower bounds and in different data structures to facilitate the updating of the cost matrix.
Artificial IntelligenceConsistent-labeling problems and their algorithms: Expected-complexities and theory-based heuristics
150 Citations1983Bernard Nudel
Expected-complexity analyses for the traditional backtrack algorithm as well as for two more recent algorithms that have been found empirically to be significant improvements: forward checking and word-wise forward checking are carried out.
Artificial IntelligenceThe TSP phase transition
141 Citations1996Ian P. Gent, Toby Walsh
It is shown that for random problems there is a rapid transition between soluble and insoluble instances of the decision problem at a critical value of this parameter, a natural parameter for the two-dimensional Euclidean traveling salesman problem.
Artificial IntelligenceCritical behavior in the computational cost of satisfiability testing
135 Citations1996Bart Selman, Scott Kirkpatrick
It is found that the median computational cost takes on a universal form across the transition regime of the UNSAT regime, and the large spread in cost of finding assignments is mainly due to the variability of running time of the Davis-Putnam (DP) procedure.
Artificial IntelligenceThe hardest constraint problems: A double phase transition
134 Citations1994Tad Hogg, Colin P. Williams
The distribution of hard graph coloring problems as a function of graph connectivity is shown to have two distinct transition behaviors, including a peak in the median search cost near the connectivity at which half the graphs have solutions.
Journal of Automated ReasoningBranching rules for satisfiability
131 Citations1995John Hooker, Vishwa Vinay
This work attempts to explain and improve the performance of branching rules with an empirical model-building approach, based on the rationale given for the Jeroslow-Wang rule, variations of which have performed well in recent work.
Artificial IntelligenceExploiting the deep structure of constraint problems
123 Citations1994Colin P. Williams, Tad Hogg
A technique for analyzing the behavior of sophisticated AI search programs working on realistic, large-scale problems is introduced and it is suggested that this type of analysis can be generalized to other kinds of AI problems.
The SAT phase transition
121 Citations1994Ian P. Gent, Toby Walsh
There is a remarkable consistency of fea- tures in the phase transition despite the presence in some of the problem classes of clauses of mixed lengths, which may be of considerable practical and theoretical use in analysing algorithm performance.
Lecture notes in computer scienceAn empirical study of dynamic variable ordering heuristics for the constraint satisfaction problem
116 Citations1996Ian P. Gent, Ewan MacIntyre +3 more
A comparison of the Bz and FF heuristics in forward checking algorithms applied to randomly-generated binary CSP's and the identification of promising new heuristic worthy of further investigation are presented.
Lecture notes in computer scienceRandom constraint satisfaction: A more accurate picture
114 Citations1997Dimitris Achlioptas, Lefteris M. Kirousis +4 more
Random Structures and AlgorithmsTail bounds for occupancy and the satisfiability threshold conjecture
114 Citations1995Anil Kamath, Rajeev Motwani +2 more
Artificial IntelligenceExperimental evaluation of preprocessing algorithms for constraint satisfaction problems
92 Citations1994Rina Dechter, Itay Meiri
An experimental evaluation of two orthogonal schemes for pre-processing constraint satisfaction problems (CSPs) involves a class of local consistency techniques that includes directional arc consistency, directional path consistency, and adaptive consistency, which suggests that maximum cardinality and minimum width are the best preordering strategies.
Phase Transitions and Annealed Theories: Number Partitioning as a Case Study.
72 Citations1996Ian P. Gent, Toby Walsh
Annals of Mathematics and Artificial IntelligenceBranch-and-cut solution of inference problems in propositional logic
69 Citations1990John Hooker, C. Fedjki
A branch-and-cut algorithm for solving inference problems in propositional logic that substantially reduces the size of the search tree when it is large is described and test computationally.
Summarizing CSP hardness with continuous probability distributions
49 Citations1997Daniel Frost, Irina Rish +1 more
Empirical evidence is presented that the distribution of effort required to solve CSPs randomly generated at the 50% satisfiable point, when using a backtracking algorithm, can be approximated by two standard families of continuous probability distribution functions.
Lecture notes in computer scienceScaling effects in the CSP phase transition
40 Citations1995Ian P. Gent, Ewan MacIntyre +2 more
It is shown that within classes, the scaling of behaviour can be modelled by a technique called “finite size scaling”, which applies not only to probability of solubility, as has been observed before in other NP-problems, but also to search cost.
From approximate to optimal solutions: a case study of number partitioning
40 Citations1995Richard E. Korf
This work presents a new algorithm, called Complete Karmarkar Karp (CKK), that optimally solves the general number-partitioning problem, and significantly outperforms the best previously-known algorithms for this problem.
Integrating heuristics for constraint satisfaction problems: a case study
39 Citations1993Steven Minton
MULTI-TAC is a CSP "expert" that can specialize a library of generic algorithms and methods for a particular application that synthesizes constraint satisfaction programs that are on par with hand-coded programs.
An average-case analysis of branch-and-bound with applications: summary of results
37 Citations1992Weixiong Zhang, Richard E. Korf
By formulating IDA* as costbounded BnB, it is shown its average-case optimality, which implies that RBFS is optimal on average, and the existence of an average- case complexity transition of BnBs on the Asymmetric Traveling Salesman Problem is predicted.
Phase Transitions from Real Computational Problems
23 Citations1995Ian P. Gent, Toby Walsh
This work examines phase transitions in problems derived from real computational problems using a wide variety of algorithms and suggests a new methodology for benchmarking algorithms that helps to identify the location of the really hard real problems.
How long will it take
23 Citations1992Ron Musick, Stuart Russell
A method for approximating the expected number of steps required by a heuristic search algorithm to reach a goal from any initial state in a problem space is presented, based on a mapping from the original state space to an abstract space in which states are characterized only by a syntactic "distance" from the nearest goal.
Is there any need for domain-dependent control information? a reply
17 Citations1996Steven Minton
It is proposed that simplifying abstractions are crucial for deriving control knowledge, and, as a result, empirical utility evaluation of the resulting rules will frequently be necessary to validate the utility of derived control knowledge.
Russian Mathematical SurveysThe main properties of random graphs with a large number of vertices and edges
10 Citations1985A. D. Korshunov
Statistical Analysis of Backtracking on Inconsistent CSPs
5 Citations1997Irina Rish, Daniel Frost
ACM Transactions on Mathematical SoftwarePartition of Integers
3 Citations1976Frank Rubin
The integer partitioning problem reqmres enumeration of all of the M-partitions of S for fixed M and S is proposed, which for many cases requires less computation time and less storage space than existing algorithms.