University of York · Computer Science

Peter Nightingale

Contact

E-mail
First name dot surname at york dot ac dot uk
Room
CSE/141
Address
Department of Computer Science,
Deramore Lane, University of York,
Heslington, York, YO10 5GH, UK
Peter Nightingale

Research Interests

My main research interests are in discrete optimization, constraint programming, SAT and related areas of artificial intelligence. I work on modelling and solving methods for discrete optimization and constraint satisfaction problems. I am also interested in statistical inference, in particular applying discrete optimization and machine learning to statistical inference tasks.

The way in which a discrete optimization or satisfaction problem is modelled (presented to the solver) makes a huge difference to the performance of the solver, and modelling requires extensive human expertise. My research into modelling has two aspects: to generalise and automate modelling techniques used by expert modellers, and to automatically select and sequence these techniques to create high-performance models, starting with a naïve model or an abstract specification. The ultimate goal is to exceed the performance of models written by experts. As part of this research I am developing a tool called Savile Row implementing some of the ideas above, and I am collaborating on another tool named Conjure. Some aspects of both of these tools are described in papers listed below.

I am also interested in solving methods, including propagation algorithms for constraint solvers. Most of my work in this area has been implemented in the Minion solver or the Dominion constraint solver synthesizer.

If you are interested in coming to the beautiful city of York and studying for a PhD in artificial intelligence, please have a look at my PhD topics page.

PhD Students

Fun Stuff

Publications

Indexes: Google Scholar, Scopus, DBLP.

Journal

A Review of Literature on Parallel Constraint Solving

Ian P. Gent, Ciaran McCreesh, Ian Miguel, Neil C.A. Moore, Peter Nightingale, Patrick Prosser, Chris Unsworth

Theory and Practice of Logic Programming, Volume 18, Special Issue 5-6 (Special Issue on Parallel and Distributed Logic Programming), Pages 725-758, 2018.

Journal

Complexity of n-Queens Completion

Ian P. Gent, Christopher Jefferson, Peter Nightingale

Journal of Artificial Intelligence Research, Volume 59, Pages 815-848, 2017.

Journal

Search in the Patience Game 'Black Hole'

Ian P. Gent, Christopher Jefferson, Tom Kelsey, Inês Lynce, Ian Miguel, Peter Nightingale, Barbara M. Smith, and S. Armagan Tarim

AI Communications, Volume 20, Number 3, pages 211-226, 2007.

Conference

Constraint Models for Klondike

Nguyen Dang, Ian P. Gent, Peter Nightingale, Felix Ulrich-Oltean, Jack Waller

in Proceedings of the 31st International Conference on Principles and Practice of Constraint Programming (CP 2025), 2025.

Conference

Cross-Paradigm Modelling: A Study of Puzznic

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

in Proceedings of the 36th IEEE International Conference on Tools with Artificial Intelligence (ICTAI), 2024.

Conference

Metamorphic Testing of Constraint Solvers

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

in Proceedings of the 24th International Conference on Principles and Practice of Constraint Programming (CP), pages 727-736, 2018.

Conference

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, and James Wetter

in Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 1242-1248, 2018.

Conference

Automated Symmetry Breaking and Model Selection in Conjure

Özgür Akgün, Alan M. Frisch, Ian P. Gent, Bilal Syed Hussain, Christopher Jefferson, Lars Kotthoff, Ian Miguel and Peter Nightingale

in Proceedings of the 19th International Conference on Principles and Practice of Constraint Programming (CP), pages 107-116, 2013.

Workshop

Towards a Model of Puzznic

Joan Espasa Arxer, Ian Gent, Ian Miguel, Peter Nightingale, András Z. Salamon and Mateu Villaret

The 22nd workshop on Constraint Modelling and Reformulation (ModRef 2023), 2023.

Workshop

An Automated Constraint Modelling and Solving Toolchain

Özgür Akgün, Alan M. Frisch, Ian Gent, Bilal Syed Hussain, Christopher Jefferson, Lars Kotthoff, Ian Miguel and Peter Nightingale

in Proceedings of the 20th Automated Reasoning Workshop (ARW2013), School of Computing, University of Dundee, UK, 2013.

Workshop

Modelling Equidistant Frequency Permutation Arrays in Constraints

Ian P. Gent, Paul McKay, Ian Miguel, Peter Nightingale and Sophie Huczynska

in Proceedings of the Eighth Symposium on Abstraction, Reformulation and Approximation (SARA 2009). This paper is superseded by Modelling Equidistant Frequency Permutation Arrays: An Application of Constraints to Mathematics (CP 2009).

Workshop

A New Encoding of AllDifferent into SAT

Ian P. Gent and Peter Nightingale

in Proceedings 3rd International Workshop on Modelling and Reformulating Constraint Satisfaction Problems (ModRef 2004), co-located with CP 2004, Toronto, Canada, Frisch, AM, Miguel, I (eds), pages 95-110, 2004.

Software

Savile Row -- I'm the lead author of Savile Row, a tool for translating the Essence Prime modelling language to the input languages of constraint, SAT, and SMT solvers. Savile Row implements various reformulations intended to improve the model, most of which are described in the papers above.

Minion -- I wrote the network flow propagators for Minion, and they are described in papers Generalised Arc Consistency for the AllDifferent Constraint: An Empirical Survey and The Extended Global Cardinality Constraint: An Empirical Survey.

Dominion is a constraint solver synthesizer -- given a particular problem class or instance, it can create a constraint solver specifically for that class or instance by assembling a library of components.

Queso is a non-binary QCSP solver written in Java for my PhD. The source code is available on the basis that it is unsupported, but I may be able to help with some simple problems. (There is a timing component written in C for Linux, but this can probably be easily removed if you wish to run it on other systems.)

queso-15-9-08.tgz

Activities

Unfortunately this section is almost a decade out of date.

Co-chair (with Özgür Akgün) of ModRef 2015.

Co-chair (with Christopher Jefferson and Guido Tack) of TRICS 2013.

PC member for AAAI 2011 - 25th Conference on Artificial Intelligence.

PC member for CP 2011 -- 17th International Conference on Principles and Practice of Constraint Programming.

PC member for CP 2010 - 16th International Conference on Principles and Practice of Constraint Programming.

Co-chair (with Standa Živný) of the CP 2010 Doctoral Programme.

Chair (with Chris Jefferson and Guido Tack) of TRICS 2010 - 3rd workshop on Techniques foR Implementing Constraint programming Systems

Publicity for CSCLP 2011, Annual ERCIM Workshop on Constraint Solving and Constraint Logic Programming.