Clusters of sizes ranging from two to five are studied by variational quantum Monte Carlo techniques. The clusters consist of Ar, Ne and hypothetical lighter (``$1 \over 2$-Ne") atoms. A general form of trial function is developed for which the variational bias is considerably smaller than the statistical error of currently available diffusion Monte Carlo estimates. The trial functions are designed by a careful analysis of long- and short-range behavior as a function of inter-atomic distance; at intermediate distances, on the order of the average nearest neighbor distance, the trial functions are constructed to have considerable variational freedom. A systematic study of the relative importance of $n$-body contributions to the quality of the optimized trial wave function is made with $2\le n \le 5$. Algebraic invariants are employed to deal efficiently with the many-body interactions.

Andrei Mushinski M. P. Nightingale

This review covers applications of quantum Monte Carlo methods to quantum mechanical problems in the study of electronic and atomic structure, as well as applications to statistical mechanical problems both of static and dynamic nature. The common thread in all these applications is optimization of many-parameter trial states, which is done by minimization of the variance of the local or, more generally for arbitrary eigenvalue problems, minimization of the variance of the configurational eigenvalue.

M. P. Nightingale C. J. Umrigar

The principle and the efficiency of the Monte Carlo transfer-matrix algorithm are discussed. Enhancements of this algorithm are illustrated by applications to several phase transitions in lattice spin models. We demonstrate how the statistical noise can be reduced considerably by a similarity transformation of the transfer matrix using a variational estimate of its leading eigenvector, in analogy with a common practice in various quantum Monte Carlo techniques. Here we take the two-dimensional coupled $XY$-Ising model as an example. Furthermore, we calculate interface free energies of finite three-dimensional O($n$) models, for the three cases $n=1$, 2 and 3. Application of finite-size scaling to the numerical results yields estimates of the critical points of these three models. The statistical precision of the estimates is satisfactory for the modest amount of computer time spent.

M. P. Nightingale H. W. J. Bloete

Scaling behavior is studied of several dominant eigenvalues of spectra of Markov matrices and the associated correlation times governing critical slowing down in models in the universality class of the two-dimensional Ising model. A scheme is developed to optimize variational approximants of progressively rapid, independent relaxation modes. These approximants are used to reduce the variance of results obtained by means of an adaptation of a quantum Monte Carlo method to compute eigenvalues subject to errors predominantly of statistical nature. The resulting spectra and correlation times are found to be universal up to a single, non-universal time scale for each model.

M. P. Nightingale H. W. J. Bloete

A method is introduced to optimize excited state trial wave functions. The method is applied to ground and vibrationally excited states of bosonic van der Waals clusters of upto seven particles. Employing optimized trial wavefunctions with three-body correlations, we use correlation function Monte Carlo to estimate the corresponding excited state energies.

M. P. Nightingale Vilen Melik-Alaverdian

We study a planning problem based on Plotting, a tile-matching puzzle video game published by Taito in 1989. The objective of this game is to remove a target number of coloured blocks from a grid by sequentially shooting blocks into the grid. Plotting features complex transitions after every shot: various blocks are affected directly, while others can be indirectly affected by gravity. We highlight the challenges of modelling Plotting with PDDL and of solving it with a grounding-based state-of-the-art planner.

Joan Espasa Ian Miguel Peter Nightingale András Z. Salamon Mateu Villaret

We report on progress in modelling and solving Puzznic, a video game requiring the player to plan sequences of moves to clear a grid by matching blocks. We focus here on levels with no moving blocks. We compare a planning approach and three constraint programming approaches on a small set of benchmark instances. The planning approach is at present superior to the constraint programming approaches, but we outline proposals for improving the constraint models.

Joan Espasa Ian P. Gent Ian Miguel Peter Nightingale András Z. Salamon Mateu Villaret

Special-purpose constraint propagation algorithms frequently make implicit use of short supports -- by examining a subset of the variables, they can infer support (a justification that a variable-value pair may still form part of an assignment that satisfies the constraint) for all other variables and values and save substantial work -- but short supports have not been studied in their own right. The two main contributions of this paper are the identification of short supports as important for constraint propagation, and the introduction of HaggisGAC, an efficient and effective general purpose propagation algorithm for exploiting short supports. Given the complexity of HaggisGAC, we present it as an optimised version of a simpler algorithm ShortGAC. Although experiments demonstrate the efficiency of ShortGAC compared with other general-purpose propagation algorithms where a compact set of short supports is available, we show theoretically and experimentally that HaggisGAC is even better. We also find that HaggisGAC performs better than GAC-Schema on full-length supports. We also introduce a variant algorithm HaggisGAC-Stable, which is adapted to avoid work on backtracking and in some cases can be faster and have significant reductions in memory use. All the proposed algorithms are excellent for propagating disjunctions of constraints. In all experiments with disjunctions we found our algorithms to be faster than Constructive Or and GAC-Schema by at least an order of magnitude, and up to three orders of magnitude.

Peter Nightingale Ian Philip Gent Christopher Jefferson Ian Miguel

Constraint programming is a family of techniques for solving combinatorial problems, where the problem is modelled as a set of decision variables (typically with finite domains) and a set of constraints that express relations among the decision variables. One key concept in constraint programming is propagation: reasoning on a constraint or set of constraints to derive new facts, typically to remove values from the domains of decision variables. Specialised propagation algorithms (propagators) exist for many classes of constraints. The concept of support is pervasive in the design of propagators. Traditionally, when a domain value ceases to have support, it may be removed because it takes part in no solutions. Arc-consistency algorithms such as AC2001 make use of support in the form of a single domain value. GAC algorithms such as GAC-Schema use a tuple of values to support each literal. We generalize these notions of support in two ways. First, we allow a set of tuples to act as support. Second, the supported object is generalized from a set of literals (GAC-Schema) to an entire constraint or any part of it. We design a methodology for developing correct propagators using generalized support. A constraint is expressed as a family of support properties, which may be proven correct against the formal semantics of the constraint. Using Curry-Howard isomorphism to interpret constructive proofs as programs, we show how to derive correct propagators from the constructive proofs of the support properties. The framework is carefully designed to allow efficient algorithms to be produced. Derived algorithms may make use of dynamic literal triggers or watched literals for efficiency. Finally, two case studies of deriving efficient algorithms are given.

James Caldwell Ian P. Gent Peter Nightingale

When solving a combinatorial problem using propositional satisfiability (SAT), the encoding of the problem is of vital importance. We study encodings of Pseudo-Boolean (PB) constraints, a common type of arithmetic constraint that appears in a wide variety of combinatorial problems such as timetabling, scheduling, and resource allocation. In some cases PB constraints occur together with at-most-one (AMO) constraints over subsets of their variables (forming PB(AMO) constraints). Recent work has shown that taking account of AMOs when encoding PB constraints using decision diagrams can produce a dramatic improvement in solver efficiency. In this paper we extend the approach to other state-of-the-art encodings of PB constraints, developing several new encodings for PB(AMO) constraints. Also, we present a more compact and efficient version of the popular Generalized Totalizer encoding, named Reduced Generalized Totalizer. This new encoding is also adapted for PB(AMO) constraints for a further gain. Our experiments show that the encodings of PB(AMO) constraints can be substantially smaller than those of PB constraints. PB(AMO) encodings allow many more instances to be solved within a time limit, and solving time is improved by more than one order of magnitude in some cases. We also observed that there is no single overall winner among the considered encodings, but efficiency of each encoding may depend on PB(AMO) characteristics such as the magnitude of coefficient values.

Miquel Bofill Jordi Coll Peter Nightingale Josep Suy Felix Ulrich-Oltean Mateu Villaret