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 highperformance 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
Miquel Bofill, Jordi Coll, Peter Nightingale, Josep Suy, Felix UlrichOltean, and Mateu Villaret,
SAT Encodings for PseudoBoolean Constraints Together With AtMostOne Constraints,
Artificial Intelligence (in press), DOI: 10.1016/j.artint.2021.103604.
David L. Borchers, Peter Nightingale, Ben C. Stevenson, Rachel M. Fewster,
A latent capture history model for digital aerial surveys,
Biometrics (in press).
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 56 (Special Issue on Parallel and Distributed Logic Programming), Pages 725758, 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 3561, 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 325346, 2017.
Ian P. Gent, Christopher Jefferson, Peter Nightingale,
Complexity of nQueens Completion,
Journal of Artificial Intelligence Research, Volume 59, Pages 815848, 2017.
Glenna F. Nightingale, Kevin N. Laland, William Hoppitt, and Peter Nightingale,
Bayesian Spatial NBDA for Diffusion Data with HomeBase Coordinates,
PLoS ONE 10(7): e0130326. DOI: 10.1371/journal.pone.0130326, 2015.
Ian Gent, Sergey Kitaev, Alexander Konovalov, Steve Linton, and Peter Nightingale,
SCrucial 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 133, 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 163173, DOI: 10.1007/s1060101491586, 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 145, 2013.
Peter Nightingale,
The Extended Global Cardinality Constraint: An Empirical
Survey,
Artificial Intelligence, Volume 175 issue 2, pages 586614,
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 14071429, 2010.
Peter Nightingale,
Nonbinary Quantified CSP: Algorithms and Modelling,
Constraints, Volume 14, pages 539581, 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 19732000, 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 211226, 2007.
Alan M. Frisch, Timothy J. Peugniez, Anthony J. Doggett and Peter Nightingale,
Solving NonBoolean Satisfiability Problems with Stochastic Local Search: A Comparison of Encodings,
Journal of Automated Reasoning, Volume 35, pages 143179, 2005.
Iain Bate, John McDermid and Peter Nightingale,
Establishing Timing Requirements for Control Loops in RealTime Systems,
Journal of Microprocessors and Microsystems, 27(4), 159169, 2003.
Conference papers
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 143159, 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 AtMostOne and ExactlyOne Relations for Improved SAT Encodings of PseudoBoolean Constraints,
in Proceedings of the 25th International Conference on Principles and Practice of Constraint Programming, pages 2036, 2019.
Saad Attieh, Nguyen Dang, Christopher Jefferson, Ian Miguel, Peter Nightingale,
Athanor: HighLevel Local Search Over Abstract Constraint Specifications in Essence,
in Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 10561063, 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 312, 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 727736, 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 12421248, 2018.
Ian P. Gent, Christopher Jefferson, and Peter Nightingale,
Complexity of nQueens Completion (Extended Abstract),
in Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 56085611, 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 312, 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 330340, 2015.
Peter Nightingale, Özgür Akgün, Ian P. Gent, Christopher Jefferson, and Ian Miguel,
Automatically Improving Constraint Models in Savile Row through AssociativeCommutative Common Subexpression Elimination
(slides),
in Proceedings of the 20th International Conference on Principles and Practice of Constraint Programming (CP), pages 590605, 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 356365, 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 38, 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 107116, 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 573579, 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 661671, 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 623628, 2011.
Dharini Balasubramaniam, Lakshitha de Silva, Chris Jefferson, Lars Kotthoff, Ian Miguel and Peter Nightingale,
Dominion: An Architecturedriven Approach to Generating Efficient Constraint Solvers,
in Proceedings of 9th Working IEEE/IFIP Conference on Software Architecture (WICSA), pages 228231, 2011.
Ian P. Gent, Chris Jefferson, Ian Miguel, and Peter Nightingale,
Generating Specialpurpose Stateless Propagators for Arbitrary Constraints,
in Proceedings of 16th International Conference on Principles and Practice of Constraint Programming (CP 2010), pages 206220, 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 321329, 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 873878, 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 5064, 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 (AAAI07), pages 191197, 2007.
Ian P. Gent, Peter Nightingale and Kostas Stergiou,
QCSPSolve: A Solver for Quantified Constraint Satisfaction Problems,
in Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005), pages 138143, 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 792796, 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 176180, 2004.
Iain Bate, Peter Nightingale and Anton Cervin,
Establishing Timing Requirements and Control Attributes for Control Loops in RealTime Systems,
in Proceedings of the 15th Euromicro Conference on RealTime Systems, 121128, 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 UlrichOltean, Peter Nightingale, and James Alfred Walker,
Selecting SAT Encodings for PseudoBoolean 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 4756, 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), colocated 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 95110, 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 nonbinary 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.)
queso15908.tgz
Activities
Unfortunately this section is a decade out of date.
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.
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.
