Peter Nightingale

Contact information

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

Pages

Main page

PhD topics

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.

Publications

Indexes: Google Scholar, Scopus, DBLP.

Journal papers

Felix Ulrich-Oltean, Peter Nightingale, and James Alfred Walker,
Learning to Select SAT Encodings for Pseudo-Boolean and Linear Integer Constraints,
Constraints, Volume 28, pages 397-426, DOI: 10.1007/s10601-023-09364-1, 2023.

Ozgur Akgun, Alan M. Frisch, Ian P. Gent, Christopher Jefferson, Ian Miguel, and Peter Nightingale,
Conjure: Automatic Generation of Constraint Models from Problem Specifications,
Artificial Intelligence 310:103751, DOI: 10.1016/j.artint.2022.103751, 2022.

Miquel Bofill, Jordi Coll, Peter Nightingale, Josep Suy, Felix Ulrich-Oltean, and Mateu Villaret,
SAT Encodings for Pseudo-Boolean Constraints Together With At-Most-One Constraints,
Artificial Intelligence 302:103604, DOI: 10.1016/j.artint.2021.103604, 2022.

David L. Borchers, Peter Nightingale, Ben C. Stevenson, Rachel M. Fewster,
A latent capture history model for digital aerial surveys,
Biometrics 78:1, DOI: 10.1111/biom.13403, 2022.

Xu Zhu, Miguel A. Nacenta, Özgür Akgün, Peter Nightingale,
How people visually represent discrete constraint problems,
IEEE Transactions on Visualization and Computer Graphics, Volume 26, Issue 8, DOI: 10.1109/TVCG.2019.2895085, 2020.

Glenna F. Nightingale, Janine B. Illian, Ruth King, Peter Nightingale,
Area interaction point processes for bivariate point patterns in a Bayesian context,
Journal of Environmental Statistics, Volume 9, Issue 2, 2019.

Ian P. Gent, Ciaran McCreesh, Ian Miguel, Neil C.A. Moore, Peter Nightingale, Patrick Prosser, Chris Unsworth,
A Review of Literature on Parallel Constraint Solving,
Theory and Practice of Logic Programming, Volume 18, Special Issue 5-6 (Special Issue on Parallel and Distributed Logic Programming), Pages 725-758, 2018.

Peter Nightingale, Özgür Akgün, Ian P. Gent, Christopher Jefferson, Ian Miguel, Patrick Spracklen,
Automatically Improving Constraint Models in Savile Row,
Artificial Intelligence, Volume 251, Pages 35-61, DOI: 10.1016/j.artint.2017.07.001, 2017.
Some additional results are in a technical report.

James Caldwell, Ian P. Gent, Peter Nightingale,
Generalized Support and Formal Development of Constraint Propagators,
AI Communications, Volume 30, Pages 325-346, 2017.

Ian P. Gent, Christopher Jefferson, Peter Nightingale,
Complexity of n-Queens Completion,
Journal of Artificial Intelligence Research, Volume 59, Pages 815-848, 2017.

Glenna F. Nightingale, Kevin N. Laland, William Hoppitt, and Peter Nightingale,
Bayesian Spatial NBDA for Diffusion Data with Home-Base Coordinates,
PLoS ONE 10(7): e0130326. DOI: 10.1371/journal.pone.0130326, 2015.

Ian Gent, Sergey Kitaev, Alexander Konovalov, Steve Linton, and Peter Nightingale,
S-Crucial and Bicrucial Permutations with Respect to Squares,
Journal of Integer Sequences, Volume 18 issue 6, article 15.6.5, 2015.

Ian P. Gent, Christopher Jefferson, Steve Linton, Ian Miguel, and Peter Nightingale,
Generating Custom Propagators for Arbitrary Constraints,
Artificial Intelligence, Volume 211, pages 1-33, DOI: 10.1016/j.artint.2014.03.001, 2014.

Thomas W. Kelsey, Lars Kotthoff, Christopher A. Jefferson, Stephen A. Linton, Ian Miguel, Peter Nightingale, and Ian P. Gent,
Qualitative Modelling via Constraint Programming,
Constraints (Special issue on future directions for constraint programming), Volume 19, pages 163-173, DOI: 10.1007/s10601-014-9158-6, 2014.

Peter Nightingale, Ian P. Gent, Christopher Jefferson, and Ian Miguel,
Short and Long Supports for Constraint Propagation,
Journal of Artificial Intelligence Research, Volume 46, pages 1-45, 2013.

Peter Nightingale,
The Extended Global Cardinality Constraint: An Empirical Survey,
Artificial Intelligence, Volume 175 issue 2, pages 586-614, DOI: 10.1016/j.artint.2010.10.005, 2011.

Christopher Jefferson, Neil Moore, Peter Nightingale, and Karen E. Petrie,
Implementing Logical Connectives in Constraint Programming,
Artificial Intelligence, Volume 174, pages 1407-1429, 2010.

Peter Nightingale,
Non-binary Quantified CSP: Algorithms and Modelling,
Constraints, Volume 14, pages 539-581, 2009.

Ian P. Gent, Ian Miguel and Peter Nightingale,
Generalised Arc Consistency for the AllDifferent Constraint: An Empirical Survey,
Artificial Intelligence, Volume 172 number 18, pages 1973-2000, 2008.
Unfortunately this paper contains an error in one of the pseudocode algorithms. Errata

Ian P. Gent, Peter Nightingale, Andrew Rowley and Kostas Stergiou,
Solving Quantified Constraint Satisfaction Problems,
Artificial Intelligence, Volume 172, pages 738–771, 2008.

Ian P. Gent, Christopher Jefferson, Tom Kelsey, Inês Lynce, Ian Miguel, Peter Nightingale, Barbara M. Smith, and S. Armagan Tarim
Search in the Patience Game 'Black Hole',
AI Communications, Volume 20, Number 3, pages 211-226, 2007.

Alan M. Frisch, Timothy J. Peugniez, Anthony J. Doggett and Peter Nightingale,
Solving Non-Boolean Satisfiability Problems with Stochastic Local Search: A Comparison of Encodings,
Journal of Automated Reasoning, Volume 35, pages 143-179, 2005.

Iain Bate, John McDermid and Peter Nightingale,
Establishing Timing Requirements for Control Loops in Real-Time Systems,
Journal of Microprocessors and Microsystems, 27(4), 159-169, 2003.

Conference papers

Carlo Cena, Özgür Akgün, Zeynep Kiziltan, Ian Miguel, Peter Nightingale, Felix Ulrich-Oltean,
Learning When to Use Automatic Tabulation in Constraint Model Reformulation,
in Proceedings of the 32nd International Joint Conference on Artificial Intelligence, 2023.

Özgür Akgün, Alan M. Frisch, Ian P. Gent, Christopher Jefferson, Ian Miguel, Peter Nightingale,
Conjure: Automatic Generation of Constraint Models from Problem Specifications (Extended Abstract),
in Proceedings of the 32nd International Joint Conference on Artificial Intelligence, 2023.

Miquel Bofill, Jordi Coll, Peter Nightingale, Josep Suy, Felix Ulrich-Oltean, Mateu Villaret,
SAT Encodings for Pseudo-Boolean Constraints Together With At-Most-One Constraints (Extended Abstract),
in Proceedings of the 32nd International Joint Conference on Artificial Intelligence, 2023.

Felix Ulrich-Oltean, Peter Nightingale, James Alfred Walker,
Selecting SAT Encodings for Pseudo-Boolean and Linear Integer Constraints,
in Proceedings of the 28th International Conference on Principles and Practice of Constraint Programming, 2022.

Nguyen Dang, Özgür Akgün, Joan Espasa, Ian Miguel, Peter Nightingale,
A Framework for Generating Informative Benchmark Instances,
in Proceedings of the 28th International Conference on Principles and Practice of Constraint Programming, 2022.

Ewan Davidson, Özgür Akgün, Joan Espasa, Peter Nightingale,
Effective Encodings of Constraint Programming Models to SMT,
in Proceedings of the 26th International Conference on Principles and Practice of Constraint Programming, pages 143-159, 2020.

Carlos Ansótegui, Miquel Bofill, Jordi Coll, Nguyen Dang, Juan Luis Esteban, Ian Miguel, Peter Nightingale, András Z. Salamon, Josep Suy, Mateu Villaret,
Automatic Detection of At-Most-One and Exactly-One Relations for Improved SAT Encodings of Pseudo-Boolean Constraints,
in Proceedings of the 25th International Conference on Principles and Practice of Constraint Programming, pages 20-36, 2019.

Saad Attieh, Nguyen Dang, Christopher Jefferson, Ian Miguel, Peter Nightingale,
Athanor: High-Level Local Search Over Abstract Constraint Specifications in Essence,
in Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 1056-1063, 2019.

Özgür Akgün, Ian P. Gent, Christopher Jefferson, Ian Miguel, Peter Nightingale, and András Z. Salamon,
Automatic Discovery and Exploitation of Promising Subproblems for Tabulation,
in Proceedings of the 24th International Conference on Principles and Practice of Constraint Programming (CP), pages 3-12, 2018.

Özgür Akgün, Ian P. Gent, Christopher Jefferson, Ian Miguel, and Peter Nightingale,
Metamorphic Testing of Constraint Solvers,
in Proceedings of the 24th International Conference on Principles and Practice of Constraint Programming (CP), pages 727-736, 2018.

Özgür Akgün, Saad Attieh, Ian P. Gent, Christopher Jefferson, Ian Miguel, Peter Nightingale, András Z. Salamon, Patrick Spracklen, and James Wetter,
A Framework for Constraint Based Local Search using Essence,
in Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 1242-1248, 2018.

Ian P. Gent, Christopher Jefferson, and Peter Nightingale,
Complexity of n-Queens Completion (Extended Abstract),
in Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 5608-5611, 2018.

Özgür Akgün, Ian P. Gent, Christopher Jefferson, Ian Miguel, and Peter Nightingale,
Exploiting Short Supports for Improved Encoding of Arbitrary Constraints into SAT,
in Proceedings of the 22nd International Conference on Principles and Practice of Constraint Programming (CP), pages 3-12, 2016.

Peter Nightingale, Patrick Spracklen, and Ian Miguel,
Automatically Improving SAT Encoding of Constraint Problems through Common Subexpression Elimination in Savile Row,
in Proceedings of the 21st International Conference on Principles and Practice of Constraint Programming (CP), pages 330-340, 2015.

Peter Nightingale, Özgür Akgün, Ian P. Gent, Christopher Jefferson, and Ian Miguel,
Automatically Improving Constraint Models in Savile Row through Associative-Commutative Common Subexpression Elimination (slides),
in Proceedings of the 20th International Conference on Principles and Practice of Constraint Programming (CP), pages 590-605, 2014.

Ian P. Gent, Bilal Syed Hussain, Christopher Jefferson, Lars Kotthoff, Ian Miguel, Glenna F. Nightingale, and Peter Nightingale,
Discriminating Instance Generation for Automated Constraint Model Selection,
in Proceedings of the 20th International Conference on Principles and Practice of Constraint Programming (CP), pages 356-365, 2014.

Özgür Akgün, Ian P. Gent, Christopher Jefferson, Ian Miguel and Peter Nightingale,
Breaking Conditional Symmetry in Automated Constraint Modelling with Conjure,
in Proceedings of the 21st European Conference on Artificial Intelligence (ECAI), pages 3-8, 2014.

Özgür Akgün, Alan M. Frisch, Ian P. Gent, Bilal Syed Hussain, Christopher Jefferson, Lars Kotthoff, Ian Miguel and Peter Nightingale,
Automated Symmetry Breaking and Model Selection in Conjure,
in Proceedings of the 19th International Conference on Principles and Practice of Constraint Programming (CP), pages 107-116, 2013.

Christopher Jefferson and Peter Nightingale,
Extending Simple Tabular Reduction with Short Supports (slides, poster),
in Proceedings of 23nd International Joint Conference on Artificial Intelligence (IJCAI), pages 573-579, 2013.

Dharini Balasubramaniam, Chris Jefferson, Lars Kotthoff, Ian Miguel, Peter Nightingale,
An automated approach to generating efficient constraint solvers,
in Proceedings of 34th International Conference on Software Engineering (ICSE), pages 661-671, 2012.

Peter Nightingale, Ian P. Gent, Chris Jefferson and Ian Miguel,
Exploiting Short Supports for Generalised Arc Consistency for Arbitrary Constraints, (slides, poster)
in Proceedings of 22nd International Joint Conference on Artificial Intelligence (IJCAI), pages 623-628, 2011.

Dharini Balasubramaniam, Lakshitha de Silva, Chris Jefferson, Lars Kotthoff, Ian Miguel and Peter Nightingale,
Dominion: An Architecture-driven Approach to Generating Efficient Constraint Solvers,
in Proceedings of 9th Working IEEE/IFIP Conference on Software Architecture (WICSA), pages 228-231, 2011.

Ian P. Gent, Chris Jefferson, Ian Miguel, and Peter Nightingale,
Generating Special-purpose Stateless Propagators for Arbitrary Constraints,
in Proceedings of 16th International Conference on Principles and Practice of Constraint Programming (CP 2010), pages 206-220, 2010.

Lars Kotthoff, Ian Miguel and Peter Nightingale,
Ensemble classification for constraint solver configuration,
in Proceedings of 16th International Conference on Principles and Practice of Constraint Programming (CP 2010), pages 321-329, 2010.

Ian P. Gent, Lars Kotthoff, Ian Miguel, Neil C.A. Moore, Peter Nightingale and Karen E. Petrie,
Learning When to Use Lazy Learning in Constraint Solving,
in Proceedings of the 19th European Conference on Artificial Intelligence (ECAI 2010), pages 873-878, 2010.

Sophie Huczynska, Paul McKay, Ian Miguel and Peter Nightingale,
Modelling Equidistant Frequency Permutation Arrays: An Application of Constraints to Mathematics, (slides)
in Proceedings of Principles and Practice of Constraint Programming (CP 2009), pages 50-64, 2009.

Ian P. Gent, Christopher Jefferson, Ian Miguel and Peter Nightingale,
Data Structures for Generalised Arc Consistency for Extensional Constraints, (slides)
in Proceedings of the Twenty Second Conference on Artificial Intelligence (AAAI-07), pages 191-197, 2007.

Ian P. Gent, Peter Nightingale and Kostas Stergiou,
QCSP-Solve: A Solver for Quantified Constraint Satisfaction Problems,
in Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005), pages 138-143, 2005.

Peter Nightingale,
Consistency for Quantified Constraint Satisfaction Problems,
Poster and short paper in Proceedings of the 11th International Conference on Principles and Practice of Constraint Programming (CP 2005), pages 792-796, 2005.

Ian P. Gent, Peter Nightingale and Andrew Rowley,
Encoding Quantified CSPs as Quantified Boolean Formulae, (slides)
in Proceedings of the 16th European Conference on Artificial Intelligence (ECAI 2004), pages 176-180, 2004.

Iain Bate, Peter Nightingale and Anton Cervin,
Establishing Timing Requirements and Control Attributes for Control Loops in Real-Time Systems,
in Proceedings of the 15th Euromicro Conference on Real-Time Systems, 121-128, 2003.

Abstracts and Invited Talks

Automated Reformulation of Constraint Models in Savile Row, tutorial presented at CP 2014.

The Extended Global Cardinality Constraint: An Empirical Survey: Extended Abstract (slides, poster),
in Proceedings of 23nd International Joint Conference on Artificial Intelligence (IJCAI), 2013. This is an abstract of the Artificial Intelligence Journal paper, presented in the IJCAI 2013 Journal Track.

Watched Literals and Generating Propagators in Constraint Programming, 21st International Symposium on Mathematical Programming (ISMP 2012). For slides click here.

The Alldifferent Constraint: Efficiency Measures, ACP Summer School 2008. For slides click here.

Workshop papers

Ozgur Akgun, Alan M. Frisch, Ian P. Gent, Christopher Jefferson, Ian Miguel, Peter Nightingale, and András Z. Salamon,
Towards Reformulating Essence Specifications for Robustness,
The 20th workshop on Constraint Modelling and Reformulation -- ModRef 2021.

Felix Ulrich-Oltean, Peter Nightingale, and James Alfred Walker,
Selecting SAT Encodings for Pseudo-Boolean and Linear Constraints: Preliminary Results,
The 20th workshop on Constraint Modelling and Reformulation -- ModRef 2021.

Lars Malmqvist, Tommy Yuan, Peter Nightingale, and Suresh Manandhar,
Determining the Acceptability of Abstract Arguments with Graph Convolutional Networks,
Systems and Algorithms for Formal Argumentation (SAFA@COMMA 2020), pages 47-56, 2020.

Gokberk Kocak, Ozgur Akgun, Ian Miguel, and Peter Nightingale,
Closed Frequent Itemset Mining with Arbitrary Side Constraints,
Workshop on Optimization Based Techniques for Emerging Data Mining Problems (OEDM 2018), co-located with IEEE ICDM 2018.

Özgür Akgün, Alan M. Frisch, Ian Gent, Bilal Syed Hussain, Christopher Jefferson, Lars Kotthoff, Ian Miguel and Peter Nightingale,
An Automated Constraint Modelling and Solving Toolchain,
in Proceedings of the 20th Automated Reasoning Workshop (ARW2013), School of Computing, University of Dundee, UK, 2013.

Ian P. Gent, Chris Jefferson, Ian Miguel, Neil C.A. Moore, Peter Nightingale, Patrick Prosser and Chris Unsworth,
A Preliminary Review of Literature on Parallel Constraint Solving,
in Proceedings PMCS’11 Workshop on Parallel Methods for Constraint Solving, September 2011.

Ian Gent, Lars Kotthoff, Ian Miguel and Peter Nightingale,
Machine learning for constraint solver design — a case study for the alldifferent constraint,
in Proceedings of the 3rd Workshop on Techniques for Implementing Constraint Programming Systems (TRICS), St Andrews, Scotland, September 2010.

Ian P. Gent, Paul McKay, Ian Miguel, Peter Nightingale and Sophie Huczynska,
Modelling Equidistant Frequency Permutation Arrays in Constraints,
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).

Peter Nightingale,
Consistency for Quantified Constraint Satisfaction Problems, (slides)
in Proceedings of 1st Workshop on Quantification in Constraint Programming, Kostas Stergiou (ed), 2005.

Ian P. Gent and Peter Nightingale,
A New Encoding of AllDifferent into SAT,
in Proceedings 3rd International Workshop on Modelling and Reformulating Constraint Satisfaction Problems, CP2004, Toronto, Canada, Frisch, AM, Miguel, I (eds), pages 95-110, 2004.

Thesis

Peter Nightingale, Consistency and the Quantified Constraint Satisfaction Problem,
PhD thesis, University of St Andrews, 2007. Available from the University of St Andrews repository and also here.

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 Ozgur Akgun) 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.