Ian P. Gent

AAAI Conference 2026 Conference Paper

Faster Symmetry Breaking Constraints for Abstract Structures

• Özgür Akgün
• Mun See Chang
• Ian P. Gent
• Christopher Jefferson

In constraint programming and related paradigms, a modeller specifies their problem in a modelling language for a solver to search and return its solution(s). Using high-level modelling languages such as ESSENCE, a modeller may express their problems in terms of abstract structures. These are structures not natively supported by the solvers, and so they have to be transformed into or represented as other structures before solving. For example, nested sets are abstract structures, and they can be represented as matrices in constraint solvers. Many problems contain symmetries and one very common and highly successful technique used in constraint programming is to “break” symmetries, to avoid searching for symmetric solutions. This can speed up the solving process by many orders of magnitude. Most of these symmetry-breaking techniques involve placing some kind of ordering for the variables of the problem, and picking a particular member under the symmetries, usually the smallest. Unfortunately, applying this technique to abstract variables produces a very large number of complex constraints that perform poorly in practice. In this paper, we demonstrate a new incomplete method of breaking the symmetries of abstract structures by better exploiting their representations. We apply the method in breaking the symmetries arising from indistinguishable objects, a commonly occurring type of symmetry, and show that our method is faster than the previous methods proposed in (Akgün et al. 2025).

IJCAI Conference 2023 Conference Paper

Conjure: Automatic Generation of Constraint Models from Problem Specifications (Extended Abstract)

• Özgür Akgün
• Alan M. Frisch
• Ian P. Gent
• Christopher Jefferson
• Ian Miguel
• Peter Nightingale

When solving a combinatorial problem, the formulation or model of the problem is critical to the efficiency of the solver. Automating the modelling process has long been of interest given the expertise and time required to develop an effective model of a particular problem. We describe a method to automatically produce constraint models from a problem specification written in the abstract constraint specification language Essence. Our approach is to incrementally refine the specification into a concrete model by applying a chosen refinement rule at each step. Any non-trivial specification may be refined in multiple ways, creating a diverse space of models to choose from. The handling of symmetries is a particularly important aspect of automated modelling. We show how modelling symmetries may be broken automatically as they enter a model during refinement, removing the need for an expensive symmetry detection step following model formulation. Our approach is implemented in a system called Conjure. We compare the models produced by Conjure to constraint models from the literature that are known to be effective. Our empirical results confirm that Conjure can reproduce successfully the kernels of the constraint models of 42 benchmark problems found in the literature.

AIJ Journal 2022 Journal Article

Conjure: Automatic Generation of Constraint Models from Problem Specifications

• Özgür Akgün
• Alan M. Frisch
• Ian P. Gent
• Christopher Jefferson
• Ian Miguel
• Peter Nightingale

When solving a combinatorial problem, the formulation or model of the problem is critical to the efficiency of the solver. Automating the modelling process has long been of interest because of the expertise and time required to produce an effective model of a given problem. We describe a method to automatically produce constraint models from a problem specification written in the abstract constraint specification language Essence. Our approach is to incrementally refine the specification into a concrete model by applying a chosen refinement rule at each step. Any non-trivial specification may be refined in multiple ways, creating a space of models to choose from. The handling of symmetries is a particularly important aspect of automated modelling. Many combinatorial optimisation problems contain symmetry, which can lead to redundant search. If a partial assignment is shown to be invalid, we are wasting time if we ever consider a symmetric equivalent of it. A particularly important class of symmetries are those introduced by the constraint modelling process: modelling symmetries. We show how modelling symmetries may be broken automatically as they enter a model during refinement, obviating the need for an expensive symmetry detection step following model formulation. Our approach is implemented in a system called Conjure. We compare the models produced by Conjure to constraint models from the literature that are known to be effective. Our empirical results confirm that Conjure can reproduce successfully the kernels of the constraint models of 42 benchmark problems found in the literature.

IJCAI Conference 2018 Conference Paper

A Framework for Constraint Based Local Search using Essence

• Özgür Akgün
• Saad Attieh
• Ian P. Gent
• Christopher Jefferson
• Ian Miguel
• Peter Nightingale
• András Z. Salamon
• Patrick Spracklen

Structured Neighbourhood Search (SNS) is a framework for constraint-based local search for problems expressed in the Essence abstract constraint specification language. The local search explores a structured neighbourhood, where each state in the neighbourhood preserves a high level structural feature of the problem. SNS derives highly structured problem-specific neighbourhoods automatically and directly from the features of the Essence specification of the problem. Hence, neighbourhoods can represent important structural features of the problem, such as partitions of sets, even if that structure is obscured in the low-level input format required by a constraint solver. SNS expresses each neighbourhood as a constrained optimisation problem, which is solved with a constraint solver. We have implemented SNS, together with automatic generation of neighbourhoods for high level structures, and report high quality results for several optimisation problems.

IJCAI Conference 2018 Conference Paper

Complexity of n-Queens Completion (Extended Abstract)

• Ian P. Gent
• Christopher Jefferson
• Peter Nightingale

The n-Queens problem is to place n chess queens on an n by n chessboard so that no two queens are on the same row, column or diagonal. The n-Queens Completion problem is a variant, dating to 1850, in which some queens are already placed and the solver is asked to place the rest, if possible. We show that n-Queens Completion is both NP-Complete and #P-Complete. A corollary is that any non-attacking arrangement of queens can be included as a part of a solution to a larger n-Queens problem. We introduce generators of random instances for n-Queens Completion and the closely related Blocked n-Queens and Excluded Diagonals Problem. We describe three solvers for these problems, and empirically analyse the hardness of randomly generated instances. For Blocked n-Queens and the Excluded Diagonals Problem, we show the existence of a phase transition associated with hard instances as has been seen in other NP-Complete problems, but a natural generator for n-Queens Completion did not generate consistently hard instances. The significance of this work is that the n-Queens problem has been very widely used as a benchmark in Artificial Intelligence, but conclusions on it are often disputable because of the simple complexity of the decision problem. Our results give alternative benchmarks which are hard theoretically and empirically, but for which solving techniques designed for n-Queens need minimal or no change.

AIJ Journal 2017 Journal Article

Automatically improving constraint models in Savile Row

• Peter Nightingale
• Özgür Akgün
• Ian P. Gent
• Christopher Jefferson
• Ian Miguel
• Patrick Spracklen

When solving a combinatorial problem using Constraint Programming (CP) or Satisfiability (SAT), modelling and formulation are vital and difficult tasks. Even an expert human may explore many alternatives in modelling a single problem. We make a number of contributions in the automated modelling and reformulation of constraint models. We study a range of automated reformulation techniques, finding combinations of techniques which perform particularly well together. We introduce and describe in detail a new algorithm, X-CSE, to perform Associative–Commutative Common Subexpression Elimination (AC-CSE) in constraint problems, significantly improving existing CSE techniques for associative and commutative operators such as +. We demonstrate that these reformulation techniques can be integrated in a single automated constraint modelling tool, called Savile Row, whose architecture we describe. We use Savile Row as an experimental testbed to evaluate each reformulation on a set of 50 problem classes, with 596 instances in total. Our recommended reformulations are well worthwhile even including overheads, especially on harder instances where solver time dominates. With a SAT solver we observed a geometric mean of 2. 15 times speedup compared to a straightforward tailored model without recommended reformulations. Using a CP solver, we obtained a geometric mean of 5. 96 times speedup for instances taking over 10 seconds to solve.

JAIR Journal 2017 Journal Article

Complexity of n-Queens Completion

• Ian P. Gent
• Christopher Jefferson
• Peter Nightingale

The n-Queens problem is to place n chess queens on an n by n chessboard so that no two queens are on the same row, column or diagonal. The n-Queens Completion problem is a variant, dating to 1850, in which some queens are already placed and the solver is asked to place the rest, if possible. We show that n-Queens Completion is both NP-Complete and #P-Complete. A corollary is that any non-attacking arrangement of queens can be included as a part of a solution to a larger n-Queens problem. We introduce generators of random instances for n-Queens Completion and the closely related Blocked n-Queens and Excluded Diagonals Problem. We describe three solvers for these problems, and empirically analyse the hardness of randomly generated instances. For Blocked n-Queens and the Excluded Diagonals Problem, we show the existence of a phase transition associated with hard instances as has been seen in other NP-Complete problems, but a natural generator for n-Queens Completion did not generate consistently hard instances. The significance of this work is that the n-Queens problem has been very widely used as a benchmark in Artificial Intelligence, but conclusions on it are often disputable because of the simple complexity of the decision problem. Our results give alternative benchmarks which are hard theoretically and empirically, but for which solving techniques designed for n-Queens need minimal or no change.

ECAI Conference 2014 Conference Paper

Breaking Conditional Symmetry in Automated Constraint Modelling with CONJURE

• Özgür Akgün
• Ian P. Gent
• Christopher Jefferson
• Ian Miguel
• Peter Nightingale

Many constraint problems contain symmetry, which can lead to redundant search. If a partial assignment is shown to be invalid, we are wasting time if we ever consider a symmetric equivalent of it. A particularly important class of symmetries are those introduced by the constraint modelling process: model symmetries. We present a systematic method by which the automated constraint modelling tool CONJURE can break conditional symmetry as it enters a model during refinement. Our method extends, and is compatible with, our previous work on automated symmetry breaking in CONJURE. The result is the automatic and complete removal of model symmetries for the entire problem class represented by the input specification. This applies to arbitrarily nested conditional symmetries and represents a significant step forward for automated constraint modelling.

AIJ Journal 2014 Journal Article

Generating custom propagators for arbitrary constraints

• Ian P. Gent
• Christopher Jefferson
• Steve Linton
• Ian Miguel
• Peter Nightingale

Constraint Programming (CP) is a proven set of techniques for solving complex combinatorial problems from a range of disciplines. The problem is specified as a set of decision variables (with finite domains) and constraints linking the variables. Local reasoning (propagation) on the constraints is central to CP. Many constraints have efficient constraint-specific propagation algorithms. In this work, we generate custom propagators for constraints. These custom propagators can be very efficient, even approaching (and in some cases exceeding) the efficiency of hand-optimised propagators. Given an arbitrary constraint, we show how to generate a custom propagator that establishes GAC in small polynomial time. This is done by precomputing the propagation that would be performed on every relevant subdomain. The number of relevant subdomains, and therefore the size of the generated propagator, is potentially exponential in the number and domain size of the constrained variables. The limiting factor of our approach is the size of the generated propagators. We investigate symmetry as a means of reducing that size. We exploit the symmetries of the constraint to merge symmetric parts of the generated propagator. This extends the reach of our approach to somewhat larger constraints, with a small run-time penalty. Our experimental results show that, compared with optimised implementations of the table constraint, our techniques can lead to an order of magnitude speedup. Propagation is so fast that the generated propagators compare well with hand-written carefully optimised propagators for the same constraints, and the time taken to generate a propagator is more than repaid.

SoCS Conference 2011 Conference Paper

A Preliminary Evaluation of Machine Learning in Algorithm Selection for Search Problems

• Lars Kotthoff
• Ian P. Gent
• Ian Miguel

Machine learning is an established method of selecting algorithms to solve hard search problems. Despite this, to date no systematic comparison and evaluation of the different techniques has been performed and the performance of existing systems has not been critically compared to other approaches. We compare machine learning techniques for algorithm selection on real-world data sets of hard search problems. In addition to well-established approaches, for the first time we also apply statistical relational learning to this problem. We demonstrate that most machine learning techniques and existing systems perform less well than one might expect. To guide practitioners, we close by giving clear recommendations as to which machine learning techniques are likely to perform well based on our experiments.

IJCAI Conference 2011 Conference Paper

Exploiting Short Supports for Generalised Arc Consistency for Arbitrary Constraints

• Peter Nightingale
• Ian P. Gent
• Christopher Jefferson
• Ian Miguel

Special-purpose constraint propagation algorithms (such as those for the element constraint) frequently make implicit use of short supports - by examining a subset of the variables, they can infer support for all other variables and values and save substantial work. However, to date general purpose propagation algorithms (such as GAC-Schema) rely upon supports involving all variables. We demonstrate how to employ short supports in a new general purpose propagation algorithm called ShortGAC. This works when provided with either an explicit list of allowed short tuples, or a function to calculate the next supporting short tuple. Empirical analyses demonstrate the efficiency of ShortGAC compared to other general-purpose propagation algorithms. In some cases ShortGAC even exhibits similar performance to special-purpose propagators.

ECAI Conference 2010 Conference Paper

Learning When to Use Lazy Learning in Constraint Solving

• Ian P. Gent
• Christopher Jefferson
• Lars Kotthoff
• Ian Miguel
• Neil C. A. Moore
• Peter Nightingale
• Karen E. Petrie

Learning in the context of constraint solving is a technique by which previously unknown constraints are uncovered during search and used to speed up subsequent search. Recently, lazy learning, similar to a successful idea from satisfiability modulo theories solvers, has been shown to be an effective means of incorporating constraint learning into a solver. Although a powerful technique to reduce search in some circumstances, lazy learning introduces a substantial overhead, which can outweigh its benefits. Hence, it is desirable to know beforehand whether or not it is expected to be useful. We approach this problem using machine learning (ML). We show that, in the context of a large benchmark set, standard ML approaches can be used to learn a simple, cheap classifier which performs well in identifying instances on which lazy learning should or should not be used. Furthermore, we demonstrate significant performance improvements of a system using our classifier and the lazy learning and standard constraint solvers over a standard solver. Through rigorous cross-validation across the different problem classes in our benchmark set, we show the general applicability of our learned classifier.

AIJ Journal 2008 Journal Article

Generalised arc consistency for the AllDifferent constraint: An empirical survey

• Ian P. Gent
• Ian Miguel
• Peter Nightingale

The AllDifferent constraint is a crucial component of any constraint toolkit, language or solver, since it is very widely used in a variety of constraint models. The literature contains many different versions of this constraint, which trade strength of inference against computational cost. In this paper, we focus on the highest strength of inference, enforcing a property known as generalised arc consistency (GAC). This work is an analytical survey of optimizations of the main algorithm for GAC for the AllDifferent constraint. We evaluate empirically a number of key techniques from the literature. We also report important implementation details of those techniques, which have often not been described in published papers. We pay particular attention to improving incrementality by exploiting the strongly-connected components discovered during the standard propagation process, since this has not been detailed before. Our empirical work represents by far the most extensive set of experiments on variants of GAC algorithms for AllDifferent. Overall, the best combination of optimizations gives a mean speedup of 168 times over the same implementation without the optimizations.

AIJ Journal 2008 Journal Article

Solving quantified constraint satisfaction problems

• Ian P. Gent
• Peter Nightingale
• Andrew Rowley
• Kostas Stergiou

We make a number of contributions to the study of the Quantified Constraint Satisfaction Problem (QCSP). The QCSP is an extension of the constraint satisfaction problem that can be used to model combinatorial problems containing contingency or uncertainty. It allows for universally quantified variables that can model uncertain actions and events, such as the unknown weather for a future party, or an opponent's next move in a game. In this paper we report significant contributions to two very different methods for solving QCSPs. The first approach is to implement special purpose algorithms for QCSPs; and the second is to encode QCSPs as Quantified Boolean Formulas and then use specialized QBF solvers. The discovery of particularly effective encodings influenced the design of more effective algorithms: by analyzing the properties of these encodings, we identify the features in QBF solvers responsible for their efficiency. This enables us to devise analogues of these features in QCSPs, and implement them in special purpose algorithms, yielding an effective special purpose solver, QCSP-Solve. Experiments show that this solver and a highly optimized QBF encoding are several orders of magnitude more efficient than the initially developed algorithms. A final, but significant, contribution is the identification of flaws in simple methods of generating random QCSP instances, and a means of generating instances which are not known to be flawed.

AAAI Conference 2007 Conference Paper

Data Structures for Generalised Arc Consistency for Extensional Constraints

• Ian P. Gent
• Ian Miguel

Extensional (table) constraints are an important tool for attacking combinatorial problems with constraint programming. Recently there has been renewed interest in fast propagation algorithms for these constraints. We describe the use of two alternative data structures for maintaining generalised arc consistency on extensional constraints. The first, the Next-Difference list, is novel and has been developed with this application in mind. The second, the trie, is well known but its use in this context is novel. Empirical analyses demonstrate the efficiency of the resulting approaches, both in GACschema, and in the watched-literal table constraint in Minion.

ECAI Conference 2006 Conference Paper

Minion: A Fast Scalable Constraint Solver

• Ian P. Gent
• Christopher Jefferson
• Ian Miguel

We present Minion, a new constraint solver. Empirical results on standard benchmarks show orders of magnitude performance gains over state-of-the-art constraint toolkits. These gains increase with problem size – MINION delivers scalable constraint solving. MINION is a general-purpose constraint solver, with an expressive input language based on the common constraint modelling device of matrix models. Focussing on matrix models supports a highly-optimised implementation, exploiting the properties of modern processors. This contrasts with current constraint toolkits, which, in order to provide ever more modelling and solving options, have become progressively more complex at the cost of both performance and usability. MINION is a black box from the user point of view, deliberately providing few options. This, combined with its raw speed, makes MINION a substantial step towards Puget's ‘Model and Run’ constraint solving paradigm.

SAT Conference 2005 Conference Paper

Local and Global Complete Solution Learning Methods for QBF

• Ian P. Gent
• Andrew G. D. Rowley

Abstract Solvers for Quantified Boolean Formulae (QBF) use many analogues of technique from SAT. A significant amount of work has gone into extending conflict based techniques such as conflict learning to solution learning, which is irrelevant in SAT but can play a large role in success in QBF. Unfortunately, solution learning techniques have not been highly successful to date. We argue that one reason for this is that solution learning techniques have been ‘incomplete’. That is, not all the information implied in a solution is learnt. We introduce two new techniques for learning as much as possible from solutions, and we call them complete methods. The two methods contrast in how long they keep information. One, Complete Local Solution Learning, discards solutions on backtracking past a previous existential variable. The other, Complete Global Solution Learning, keeps solutions indefinitely. Our detailed experimental analysis suggests that both can improve search over standard solution learning, while the local method seems to offer a more suitable tradeoff than global learning.

IJCAI Conference 2005 Conference Paper

QCSP-Solve: A Solver for Quantified Constraint Satisfaction Problems

• Ian P. Gent
• Peter Nightingale
• Kostas

The Quantified Constraint Satisfaction Problem (QCSP) is a generalization of the CSP in which some variables are universally quantified. It has been shown that a solver based on an encoding of QCSP into QBF can outperform the existing direct QCSP approaches by several orders of magnitude. In this paper we introduce an efficient QCSP solver. We show how knowledge learned from the successful encoding of QCSP into QBF can be utilized to enhance the existing QCSP techniques and speed up search by orders of magnitude. We also show how the performance of the solver can be further enhanced by incorporating advanced lookback techniques such as CBJ and solution-directed pruning. Experiments demonstrate that our solver is several orders of magnitude faster than existing direct approaches to QCSP solving, and significantly outperforms approaches based on encoding QCSPs as QBFs.

ECAI Conference 2004 Conference Paper

Encoding Quantified CSPs as Quantified Boolean Formulae

• Ian P. Gent
• Peter Nightingale
• Andrew G. D. Rowley

ECAI Conference 2004 Conference Paper

Tractable Symmetry Breaking Using Restricted Search Trees

• Colva M. Roney-Dougal
• Ian P. Gent
• Tom W. Kelsey
• Steve Linton

SAT Conference 2003 Conference Paper

Watched Data Structures for QBF Solvers

• Ian P. Gent
• Enrico Giunchiglia
• Massimo Narizzano
• Andrew G. D. Rowley
• Armando Tacchella

Abstract In the last few years, we have seen a tremendous boost in the efficiency of SAT solvers, this boost being mostly due to Chaff. Chaff owes some of its efficiency to its “two-literal watching” data structure. In this paper we present watched data structures for Quantified Boolean Formula (QBF) satisfiability solvers. In particular, we propose ( i ) two Chaff -like literal watching schemes for unit clause detection; and ( ii ) two other watched data structures, one for detecting pure literals and the other for detecting void quantifiers. We have conducted an experimental evaluation of the proposed data structures, using both randomly generated and real-world benchmarks. Our results indicate that clause watching is very effective, while the 2 and 3 literal watching data structures become more effective as the clause length increases. The quantifier watching structure does not appear to be effective on the instances considered.

ECAI Conference 2002 Conference Paper

An Empirical Study of the Stable Marriage Problem with Ties and Incomplete Lists

• Ian P. Gent
• Patrick Prosser

ECAI Conference 2002 Conference Paper

Arc Consistency in SAT

• Ian P. Gent

ECAI Conference 2000 Conference Paper

Local Search on Random 2+p-SAT

• Josh Singer
• Ian P. Gent
• Alan Smaill

ECAI Conference 2000 Conference Paper

Symmetry Breaking in Constraint Programming

• Ian P. Gent
• Barbara M. Smith

AAAI Conference 1999 Conference Paper

Beyond NP: The QSAT Phase Transition

• Ian P. Gent
• Toby Walsh
• University of Strathclyde

Weshowthat phase transition behavior similar to that observed in NP-completeproblems like random3-SAT occurs further up the polynomialhierarchy in problems like random 2-QSAT. The differences between QSAT and SAT in phase transition behavior that Cadoli et al report are largely dueto the presenceof trivially unsatisfiable problems. Oncethey are removed, wesee behavior more familiar from SAT and other NP-complete domains. There are, however, somedifferences. Problemswith short clauses showa large gap betweenworst case behavior and median, and the easy-hard-easy pattern is restricted to higherpercentiles of search cost. Wecomputethe "constralnedness" of k-QSAT problems for anyk, anduse this to predict the location of phase transitions. Weconjecture that these predictions are less accurate than in NP-completeproblems because of the super-exponential size of the state space, and of the weaknessof first moment methodsin complexity classes aboveNP. Finally, wepredict that similar phase transition behavior will occur in other PSPAeEcomplete problemslike planning and gameplaying.

AAAI Conference 1999 Conference Paper

Morphing: Combining Structure and Randomness

• Ian P. Gent
• University of Strathclyde; Holger H. Hoos
• University of British Columbia; Patrick Prosser
• Toby Walsh
• University of Strathclyde

We introduce a mechanism called “morphing” for introducing structure or randomness into a wide variety of problems. We illustrate the usefulness of morphing by performing several different experimental studies. These studies identify the impact of a “small-world” topology on the cost of coloring graphs, of asymmetry on the cost of finding the optimal TSP tour, and of the dimensionality of space on the cost of finding the optimal TSP tour. We predict that morphing will find many other uses.

AIJ Journal 1999 Journal Article

Paul R. Cohen's Empirical Methods for Artificial Intelligence

• Ian P. Gent
• Toby Walsh

IJCAI Conference 1997 Conference Paper

From Approximate to Optimal Solutions: Constructing Pruning and Propagation Rules

• Ian P. Gent
• Toby Walsh

At the heart of many optimization procedures are powerful pruning and propagation rules. This paper presents a case study in the construction of such rules. We develop a new algorithm, Complete Decreasing Best Fit, that finds the optimal packing of objects into bins. The algorithm use a branching rule based on the well known Decreasing Best Fit approximation algorithm. In addition, it includes a powerful pruning rule derived from a bound on the solution to the remaining subproblem. The bound is constructed by using modular arithmetic to decompose the numerical constraints. We show that the pruning rule adds essentially a constant factor overhead to runtime, whilst reducing search significantly. On the hardest problems, runtime can be reduced by an order of magnitude. Finally we demonstrate how propagation rules can be built by adding lookahead to pruning rules. This general approach - optimization procedures built from branching rules based on good approximation algorithms, and pruning and propagation rules derived from bounds on the remaining subproblem - may be effective on other NP-complete problems.

AAAI Conference 1997 Conference Paper

The Scaling of Search Cost

• Ian P. Gent
• Patrick Prosser

We show that a resealed constrainedness parameter provides the basis for accurate numerical models of search cost for both backtracking and local search algorithms. In the past, the scaling of performance has been restricted to critically constrained problems at the phase transition. Here, we show how to extend models of search cost to the full width of the phase transition. This enables the direct comparison of algorithms on both under-constrained and overconstrained problems. We illustrate the generality of the approach using three different problem domains (satisfiability, constraint satisfaction and travelling salesperson problems) with both backtracking algorithms like the Davis-Putnam procedure and local search algorithms like GSAT. As well as modelling data from experiments, we give accurate predictions for results beyond the range of the experiments.

ECAI Conference 1996 Conference Paper

Phase Transitions and Annealed Theories: Number Partitioning as a Case Study

• Ian P. Gent
• Toby Walsh

AAAI Conference 1996 Conference Paper

The Constrainedness of Search

• Ian P. Gent
• Patrick Prosser

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.

AIJ Journal 1996 Journal Article

The satisfiability constraint gap

• Ian P. Gent
• Toby Walsh

We describe an experimental investigation of the satisfiability phase transition for several different classes of randomly generated problems. We show that the “conventional” picture of easy-hard-easy problem difficulty is inadequate. In particular, there is a region of very variable problem difficulty where problems are typically underconstrained and satisfiable. Within this region, problems can be orders of magnitude harder than problems in the middle of the satisfiability phase transition. These extraordinarily hard problems appear to be associated with a “constraint gap”. That is, a region where search is a maximum as the amount of constraint propagation is a minimum. We show that the position and shape of this constraint gap change little with problem size. Unlike hard problems in the middle of the satisfiability phase transition, hard problems in the variable region are not critically constrained between satisfiability and unsatisfiability. Indeed, hard problems in the variable region often contain a small and unique minimal unsatisfiable subset or reduce at an early stage in search to a hard unsatisfiable subproblem with a small and unique minimal unsatisfiable subset. The difficulty in solving such problems is thus in identifying the minimal unsatisfiable subset from the many irrelevant clauses. The existence of a constraint gap greatly hinders our ability to find such minimal unsatisfiable subsets. However, it remains open whether these problems remain hard for more intelligent backtracking procedures. We conjecture that these results will generalize both to other SAT problem classes, and to the phase transitions of other NP-hard problems.

AIJ Journal 1996 Journal Article

The TSP phase transition

• Ian P. Gent
• Toby Walsh

The traveling salesman problem is one of the most famous combinatorial problems. We identify a natural parameter for the two-dimensional Euclidean traveling salesman problem. We show 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. Hard instances of the traveling salesman problem are associated with this transition. Similar results are seen both with randomly generated problems and benchmark problems using geographical data. Surprisingly, finite-size scaling methods developed in statistical mechanics describe the behaviour around the critical value in random problems. Such phase transition phenomena appear to be ubiquitous. Indeed, we have yet to find an NP-complete problem which lacks a similar phase transition.

AIJ Journal 1994 Journal Article

Easy problems are sometimes hard

• Ian P. Gent
• Toby Walsh

We present a detailed experimental investigation of the easy-hard-easy phase transition for randomly generated instances of satisfiability problems. Problems in the hard part of the phase transition have been extensively used for benchmarking satisfiability algorithms. This study demonstrates that problem classes and regions of the phase transition previously thought to be easy can sometimes be orders of magnitude more difficult than the worst problems in problem classes and regions of the phase transition considered hard. These difficult problems are either hard unsatisfiable problems or are satisfiable problems which give a hard unsatisfiable subproblem following a wrong split. Whilst these hard unsatisfiable problems may have short proofs, these appear to be difficult to find, and other proofs are long and hard.

ECAI Conference 1994 Conference Paper

The SAT Phase Transition

• Ian P. Gent
• Toby Walsh

AAAI Conference 1993 Conference Paper

Towards an Understanding of Hill-Climbing Procedures for SAT

• Ian P. Gent

Recently several local hill-climbing procedures for propositional satisfiability have been proposed which are able to solve large and difficult problems beyond the reach of conventional algorithms like Davis-Putnam. By the introduction of some new variants of these procedures, we provide strong experimental evidence to support our conjecture that neither greediness nor randomness is important in these procedures. One of the variants introduced seems to offer significant improvements over earlier procedures. In addition, we investigate experimentally how performance depends on their parameters. Our results suggest that runtime scales less than simply exponentially in the problem size.