Publications for Ian Gent

Note

I have broken down publications by date, not type. So appearance here does not mean for example that a paper has been peer-reviewed. I do include some workshop papers, tech reports, etc, but this is haphazard. Many such papers are not here, and there is no logic behind which are included are which are not.

Style of citation and form of the paper is equally haphazard. Papers may be in pdf, ps, and compressed or archived.

Indeed, please feel free to contact me for a copy of any paper you are having trouble finding.

Ian Gent, Feb 17, 2009.

Other Sources

There are other sources of my papers and bibliographic information on-line.

• Many tech reports are missing from the following lists, but might be obtainable from the:
  • CIRCA Preprints series; or
  • CPPod reports page; or
  • APES reports page.
• St Andrews Research Expertise list of publications for me. This link may have papers not on this page, and vice versa.
• DBLP Bibliographic Server for Ian Gent
• Google Scholar search for Ian Gent as Author.

2008

• Ian P. Gent and Ian Miguel and Peter Nightingale,
  Generalised Arc Consistency for the AllDifferent Constraint: An Empirical Survey,
  Artificial Intelligence, Volume 172 number 18 pages 1973-2000. We have also made available a small correction to the paper.

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

• Common Subexpression Elimination in Automated Constraint Modelling
  Ian P. Gent, Ian Miguel and Andrea Rendl.
  Proceedings of the Workshop on Modeling and Solving Problems with Constraints

2007

• Search in the Patience Game "Black Hole".
  I.P. Gent, C. Jefferson, T. Kelsey, I. Lynce, I. Miguel, P. Nightingale, B.M. Smith. To appear in AI Communications. Link is to a preprint.

• Tailoring Solver-independent Constraint Models: A Case Study with Essence' and Minion.
  Andrea Rendl, Ian P. Gent, Ian Miguel. Proceedings of SARA 07.

• Data Structures for Generalised Arc Consistency for Extensional Constraints.
  I.P. Gent, C. Jefferson, I. Miguel, P. Nightingale. Proceedings of the Twenty Second Conference on Artificial Intelligence, 2007.

• Groupoids and Conditional Symmetry
  I.P. Gent, Tom Kelsey, S. A. Linton, J. Pearson, Colva M. Roney-Dougal. In Proceedings CP 2007.: 823-830. 2007.

2006

• Minion: A Fast, Scalable Constraint Solver.
  I.P. Gent, C. Jefferson, I. Miguel. Proceedings of the Seventeenth European Conference on Artificial Intelligence, 98-102, 2006. This was judged by the chairs to be one of the ten best papers submitted to the conference. Click for more information on the Minion Constraint Solver.

• Symmetry in Constraint Programming.
  I.P. Gent, K.E. Petrie, and J.-F. Puget. In F. Rossi, P. van Beek, T. Walsh (eds), The Handbook of Constraint Programming, 2006. Chapter 10.

  • Slides in PDF (30MB) from my lectures at the 2007 Summer School in Constraint Programming, Lloret de Mar, June. Also slides in handout form in black and white (3.7MB).

• Watched Literals for Constraint Propagation in Minion.
  I.P. Gent, C. Jefferson, I. Miguel. Proceedings of the Twelfth International Conference on Principles and Practice of Constraint Programming, 182-197, 2006.

2005

• Conditional Symmetry Breaking.
  I.P. Gent, T. Kelsey, S.A. Linton, I. McDonald, I. Miguel, B.M. Smith. Proceedings of the 11th International Conference on Principles and Practice of Constraint Programming (CP), 256-270, 2005.

• Symmetry and Consistency.
  Ian P. Gent, Tom Kelsey, Steve Linton, Colva M. Roney-Dougal: CP 2005: 271-285

• QCSP-Solve: A Solver for Quantified Constraint Satisfaction Problems.
  Ian P. Gent, Peter Nightingale, Kostas Stergiou: IJCAI 2005: 138-143

• Local and Global Complete Solution Learning Methods for QBF.
  Ian P. Gent, Andrew G. D. Rowley: SAT 2005: 91-106

2004

• Tractable Symmetry Breaking Using Restricted Search Trees.
  Colva M. Roney-Dougal, Ian P. Gent, Tom Kelsey, Steve Linton: ECAI 2004: 211-215. This was judged by the chairs to be one of the ten best papers submitted to the conference.

• Approaches to Conditional Symmetry Breaking.
  I.P. Gent, I. McDonald, I. Miguel, B.M. Smith. Proceedings of the 4th International Workshop on Symmetry and Constraint Satisfaction Problems, 2004.

• Models and Symmetry Breaking for 'Peaceable Armies of Queens'.
  Barbara M. Smith, Karen E. Petrie, Ian P. Gent: CPAIOR 2004: 271-286

• Encoding Quantified CSPs as Quantified Boolean Formulae.
  Ian P. Gent, Peter Nightingale, Andrew Rowley: ECAI 2004: 176-180

2003

• Generic SBDD Using Computational Group Theory.
  Ian P. Gent, Warwick Harvey, Tom Kelsey, Steve Linton. CP 2003: 333-347

• Conditional Symmetry in the All-Interval Series Problem
  Ian P. Gent, Iain McDonald, and Barbara M. Smith, In Proceedings, SymCon03, pages 55-65, 2003.

• Using Stochastic Local Search to Solve Quantified Boolean Formulae.
  Ian P. Gent, Holger H. Hoos, Andrew G. D. Rowley and Kevin Smyth. In Principles and Practice of Constraint Programming CP 2003 (pdf)

• Supertree Construction with Constraint Programming.
  Ian P. Gent, Patrick Prosser, Barbara M. Smith, and Wu Wei. In Principles and Practice of Constraint Programming CP 2003

• Watched Data Structures for QBF Solvers.
  Ian Gent, Enrico Giunchiglia, Massimo Narizzano, Andrew Rowley, and Armando Tacchella. Proceedings of SAT-2003, 2003.

2002

• Groups and Constraints: Symmetry Breaking During Search
  Ian P. Gent, Warwick Harvey, and Tom Kelsey, In Principles and Practice of Constraint Programming - CP2002, ed. Pascal van hentenryck, Springer, LNCS 2470, pp. 415-430, 2002

• Arc Consistency in SAT
  Ian P. Gent Proceedings of ECAI 2002: the 15th European Conference on Artificial Intelligence. (pdf, postscript)

• An Empirical Study of the Stable Marriage Problem with Ties and Incomplete Lists
  Ian P. Gent and Patrick Prosser. Proceedings of ECAI 2002: the 15th European Conference on Artificial Intelligence. (pdf, postscript)

• SAT Encodings of the Stable Marriage Problem with Ties and Incomplete Lists
  Ian P. Gent and Patrick Prosser, Proceedings of SAT-2002, 2002.

• Models and Symmetry Breaking for Peaceable Armies of Queens
  Barbara M. Smith, Keren E. Petrie and Ian P. Gent, in ECAI 2002 workshop W9 Modelling and Solving Problems with Constraints

• A 0/1 encoding of the GACLex constraint for pairs of vectors
  Ian P. Gent, Patrick Prosser, and Barbara M. Smith, in ECAI 2002 workshop W9 Modelling and Solving Problems with Constraints

• Ian P. Gent, Toby Walsh: Satisfiability in the Year 2000. J. Autom. Reasoning 28(2): 99 (2002) (Journal editorial.)

• Automatically reformulating SAT-encoded CSPs. L. Drake, A. M. Frisch, I.P. Gent and T. Walsh. In Proceedings of the International Workshop on Reformulating Constraint Satisfaction Problems, CP 2002, September 2002.

2001

• Frozen Development in Graph Colouring,
  Joseph Culberson and Ian Gent, Theoretical Computer Science, vol. 265, pp. 227-264, 2001.

• Random Constraint Satisfaction: flaws and structures
  I.P. Gent, E. MacIntyre, P. Prosser, B.M. Smith and T. Walsh, Journal of Constraints 6 (4), pp. 345-372, October 2001.

• A Constraint Programming Approach to the Stable Marriage Problem
  Ian P. Gent, Robert W. Irving, David Manlove, Patrick Prosser and Barbara M. Smith. Principles and Practice of Constraint Programming - CP 2001, ed. Toby Walsh, Springer, LNCS 2239, pp. 225-239, 2001. (pdf, compressed postscript, uncompressed postscript)

2000

• SAT 2000: Highlights of Satisfiability Research in the Year 2000
  Eds. Ian Gent, Hans van Maaren and Toby Walsh, IOS Press, Frontiers in Artificial Intelligence and Applications, vol 63, 561 pages. (This volume collects together papers in Journal of Automated Reasoning, Volume 24, Issue 1/2, February 2000, and Issue 4, May 2000, guest edited by Ian Gent and Toby Walsh.)

• Search Algorithms in Type Theory
  James L. Caldwell, Ian P. Gent and Judith L. Underwood, Theoretical Computer Science, Vol. 123, pp. 133-156, 2000.

• Decomposable constraints
  Ian Gent, Kostas Stergiou, and Toby Walsh Artificial Intelligence 123, pp. 133-156, October 2000.

• Ian P. Gent, Toby Walsh: Satisfiability in the Year 2000. J. Autom. Reasoning 24(1/2): 1-3 (2000) (Journal Editorial.)

• Backbone Fragility and the Local Search Cost Peak
  Josh Singer, Ian Gent and Alan Smaill.
  Journal of Artificial Intelligence Research 12 (2000) 235-270. 

• Symmetry Breaking in Constraint Programming
  Ian P. Gent and Barbara M. Smith, Proc. ECAI 2000, ed W. Horn, pp. 599-603.

• Local Search on Random 2+p-SAT.
  Josh Singer, Ian P. Gent, Alan Smaill: ECAI 2000: 113-117

• Parallel Heuristic Search Techniques for Propositional Satisfiability using Haskell
  Michelle Cope, Ian Gent, and Kevin Hammond. In Trends in Functional Programming Vol 2., S. Gilmore (ed.), pages 65-77. (Proc. 2nd Scottish Functional Programming Workshop. 2000). (gzipped postscript) (postscript) (pdf)

1999

• A response to 'On Method Overfitting', I.P. Gent,
  Journal of Heuristics, Vol 5, number 1, pages 109-111, April 1999.

• Beyond NP: The QSAT Phase Transition
  Ian Gent and Toby Walsh. Proceedings of AAAI-99, pp. 648-653. Note that this paper is copyright AAAI and placed on this web page with permission. 

• Morphing: Combining Structure and Randomness
  Ian Gent, Holger Hoos, Patrick Prosser and Toby Walsh. Proceedings of AAAI-99, pp. 654-660. Note that this paper is copyright AAAI and placed on this web page with permission. 

• CSPLib: a benchmark library for constraints
  Ian P. Gent and Toby Walsh. (Shorter version). Principles and Practice of Constraint Programming - CP'99, ed. Joxan Jaffar, pp. 480-481, Springer-Verlag, LNCS 1713, 1999.

• Thinking on your feet in undergraduate computer science: a constructivist approach to developing and assessing critical thinking I.P. Gent, B. Johnston, and P. Prosser, Teaching in Higher Education,  Vol 4., Number 4, 1999, pages 511-522.  Special issue on Critical Thinking

• Ian P. Gent, Toby Walsh: Paul R. Cohen's Empirical Methods for Artificial Intelligence. Artif. Intell. 113(1-2): 285-290 (1999) (Book review.)

1998

• Analysis of Heuristics for Number Partitioning
  Ian Gent and Toby Walsh. Computational Intelligence, 14 (3), pp. 430-451, 1998. Link is to a preprint.

• Heuristic Solution of Open Bin Packing Problems
  Ian Gent, Journal of Heuristics, 3(4), pp. 299-304, 1998. Link is to a preprint but also see this note added in proof.

• On the Stupid Algorithm for Satisfiability
  Ian Gent. APES Report APES-03-1998. APES Research Group. April 1998.

• Two Results on Car-sequencing Problems
  Ian Gent. APES Report APES-02-1998. APES Research Group. April 1998.

1997

• Asymptotic and Finite Size Parameters for Phase Transitions: Hamiltonian Circuit as a Case Study
  Jeremy Frank, Ian Gent and Toby Walsh. Information Processing Letters 65, pp. 241-245, 1998. Link is to a preprint.

• The Logic of Search Algorithms: Theory and Applications 
  Ian Gent and Judith Underwood. Principles and Practice of Constraint Programming - CP-97, pages 77-91. Springer, LNCS 1330, 1997. (The Scheme code from the Appendix of the paper is here.)

• The Constrainedness of Arc Consistency
  Ian Gent, Ewan MacIntyre, Patrick Prosser, Paul Shaw, and Toby Walsh. Principles and Practice of Constraint Programming - CP-97, pages 327-340. Springer, LNCS 1330, 1997. (presentation slides) 

• From Approximate to Optimal Solutions: Constructing Pruning and Propagation Rules
  Ian Gent and Toby Walsh. Proceedings of IJCAI-97, pages 1396-1401.

• The Scaling of Search Cost 
  Ian Gent, Ewan MacIntyre, Patrick Prosser, and Toby Walsh. Proceedings of AAAI-97, pages 315-320.

• How Not To Do It
  Ian P Gent, Stuart A Grant, Ewan MacIntyre, Patrick Prosser, Paul Shaw, Barbara M Smith and Toby Walsh. Research Report 97.27, School of Computer Studies, University of Leeds. May 1997. 

1996

• The Satisfiability Constraint Gap
  Ian Gent and Toby Walsh. Artificial Intelligence, 81 (1-2), pp. 59-80, 1996. The link is to a preprint.

• The TSP Phase transition
  Ian Gent and Toby Walsh. Artificial Intelligence, 88 (1-2), pp. 349-358, 1996. This paper is no longer available on-line as copyright has passed to the journal. Please contact the authors for a reprint.

• Local Search and the Number of Solutions.
  Dave Clark, Jeremy Frank, Ian Gent, Ewan MacIntyre, Neven Tomov and Toby Walsh. Principles and Practice of Constraint Programming - CP96, ed. E.C. Freuder, pp. 119-133, Springer-Verlag, LNCS 1118, 1996.

• An empirical study of dynamic variable ordering heuristics for the constraint satisfaction problem
  Ian Gent, Ewan MacIntyre, Patrick Prosser, Barbara Smith, and Toby Walsh. Principles and Practice of Constraint Programming - CP96, ed. E.C. Freuder, pp. 179-193, Springer-Verlag, LNCS 1118, 1996.

• The Constrainedness of Search.
  Ian Gent, Ewan MacIntyre, Patrick Prosser, and Toby Walsh. Proceedings of AAAI-96, pages 246-252, 1996. Note that this paper is copyright AAAI and placed on this web page with permission.

• Phase transitions and annealed theories: Number partitioning as a case study
  Ian Gent and Toby Walsh. Proceedings of ECAI-96, pages 170-174, John Wiley and Sons 1996. Earlier version available as The Number Partition Phase Transition Research Report 95-185, University of Strathclyde. 

1995

• Scaling Effects in the CSP Phase Transition
  Ian Gent, Ewan MacIntyre, Patrick Prosser, and Toby Walsh. In the proceedings of First International Conference on Principles and Practice of Constraint Programming, 1995. Preliminary version available as Research Report/95/179, Department of Computer Science, University of Strathclyde.

• Computational Phase Transitions from Real Problems
  Ian Gent and Toby Walsh, Proceedings of the 8th International Symposium on AI, pages 356-364, 1995.

• Unsatisfied Variables in Local Search
  Ian Gent and Toby Walsh. in `Hybrid Problems, Hybrid Solutions', ed. J. Hallam, IOS Press, Amsterdam, 1995, pages 73-85. (Proceedings of AISB-95.) Preliminary version (with less data but some more details on some points) available as Research Paper 721 from the Department of Artificial Intelligence, Edinburgh, 1994. 

• The TSP Phase Transition
  Ian Gent and Toby Walsh. Presented at the First Workshop on AI and OR, 1995.

• The 50% Point in Constraint Satisfaction Problems
  Ian Gent and Patrick Prosser, Research Report/95/180, Department of Computer Science, University of Strathclyde. 

1994

• How Not To Do It
  Ian Gent and Toby Walsh. AAAI-94 Workshop on Experimental Evaluation of Reasoning and Search Methods, 1994. Available as Research Paper 714 from the Department of Artificial Intelligence, Edinburgh.

• The SAT Phase Transition
  Ian Gent and Toby Walsh. Proceedings of ECAI-94, ed. A G Cohn, John Wiley & Sons, pages 105-109, 1994. 

• Easy Problems are Sometimes Hard,
  I.P. GENT  and T. WALSH, Artificial Intelligence, Vol. 70, 1994, pages 335-345.

• The Hardest Random Sat Problems,
  I.P. GENT and T. WALSH, KI-94: Advances in Artificial Intelligence. 18th German Annual Conference on Artificial Intelligence, 1994, pages 355-366.

• Proof Systems for Fourteen Logics of Counterfactuals, I.P. GENT, Journal of Symbolic Logic, unreviewed abstract, 1994.

1993

• An Empirical Analysis of Search in GSAT
  Ian Gent and Toby Walsh, Journal of Artificial Intelligence Research, Vol. 1, September 1993. 

• Analytic Proof Systems for Classical and Modal Logics of Restricted Quantification, I.P. GENT, Research Report 246, Department of Computer Science, University of Warwick, 1993. PhD thesis. (Tarred and gzipped archive containing postscript files of the chapters.)

• Towards an Understanding of Hill-climbing Procedures for SAT, I.P. GENT  and T. WALSH, Proceedings of AAAI-93, Morgan Kauffman, 1993, pages 28-33. (Note that the link is not the published version but a preprint.)

• Theory Matrices (for Modal Logics) using Alphabetical Monotonicity, I.P. GENT, Studia Logica, Vol. 52, May 1993.

1992

• The Enigma of Hill-climbing Procedures for SAT,
  I.P. GENT and T. WALSH , Research Paper 605, Department of Artificial Intelligence, University of Edinburgh, 1992.

• A Tableau- or Sequent-style System for Lewis's Counterfactual Logic VC, I.P. GENT, Notre Dame Journal of Formal Logic, Vol. 33, Summer 1992.

1991

• Theory Tableaux, I.P. GENT, Technical Report 91-62, Mathematical Sciences Institute, Cornell University, 1991.

• Reasoning about Hybrid Reasoning: a discussion, I.P. GENT and A.G.COHN, Research Report 193, Department of Computer Science, University of Warwick, 1991. Presented at the AAAI Symposium on Principles of Hybrid Reasoning, 1991.

• Finding Problems in Knowledge Bases Using Modal Logics, I.P. GENT, Research Report 173, Department of Computer Science, University of Warwick, 1991

1987

• A Unification Grammar Development Environment, I.P. GENT, Department of Artificial Intelligence, University of Edinburgh, 1987. MSc thesis.

Page maintained by Ian Gent