Barbara Smith - Papers on Constraint Programming

Modelling for Constraint Programming

Symmetry

Search and Search Heuristics

Phase Transitions and Random CSPs

Constraint Programming applied to Scheduling

Planning and Other Applications

Review and Tutorial Papers

Modelling for Constraint Programming

  • Dual Formulations of Magic Squares
    Barbara M. Smith. Research Report CPPod-25-2008, July 2008.
  • Automatic generation of redundant models for permutation constraint satisfaction problems.
    Yat Chiu Law, Jimmy H. M. Lee and Barbara M. Smith. Constraints (12), pp. 469-505, 2007. (Abstract)
  • Search in the Patience Game 'Black Hole'.
    Ian Gent, Christopher Jefferson, Ines Lynce, Ian Miguel, Peter Nightingale, Barbara Smith and Armagan Tarim. AI Communications (20), pp. 211-226, 2007. An earlier version appeared as Report CPPod-10-2005. (Abstract)
  • Modelling
    Barbara M. Smith. In Francesca Rossi, Peter van Beek, and Toby Walsh, editors, Handbook of Constraint Programming, Chapter 11, pages 377-406. Elsevier, 2006. ISBN 0-444-52726-5. (Also listed under Survey and Tutorial papers.)
  • Constraint Programming Models for Solitaire Battleships
    Barbara M. Smith. Research Report CPPod-20-2006, November 2006. (Abstract)
  • Improved Models for Graceful Graphs.
    Jean-Francois Puget and Barbara M. Smith. Proceedings of the CP 2006 Workshop on Constraint Modelling and Reformulation, 2006. (Abstract)
  • Constraint Programming Models for Graceful Graphs.
    Barbara M. Smith. In Frederic Benhamou, editor, Principles and Practice of Constraint Programming - CP 2006, LNCS 4204, pages 545-559. Springer, 2006. (Abstract)
  • Constraint Models for the Covering Test Problem
    Brahim Hnich, Steve Prestwich, Evgeny Selensky, and Barbara M. Smith. Constraints, 11:199-219, 2006. (Abstract)
  • Constraint Modelling Challenge 2005
    Barbara M. Smith and Ian P. Gent. Report on the entries to the 1st Constraint Modelling Challenge, 2005.
  • Transforming and Refining Abstract Constraint Specifications
    Alan M. Frisch, Brahim Hnich, Ian Miguel, Barbara M. Smith and Toby Walsh, In Abstraction, Reformulation and Approximation, 6th International Symposium, Proceedings SARA 2005, pp. 76-91, ed. Jean-Daniel Zucker and Lorenza Saitta, Springer, LNCS 3607, 2005. (Abstract)
  • Symmetry and Search in a Network Design Problem
    Barbara M. Smith, In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Proceedings of CPAIOR 2005, pp. 336-350, ed. Roman Bartak and Michela Milano, Springer, LNCS 3524, 2005. (Abstract)
  • Models and Symmetry Breaking for Peaceable Armies of Queens
    Barbara M. Smith, Karen E. Petrie and Ian P. Gent. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Proceedings of CPAIOR 2004, pp. 271-286, ed. Jean-Charles Regin and Michel Rueher, Springer LNCS 3011, 2004. (Abstract)
  • Search Strategies for Optimization: Modelling the SONET Problem
    Barbara M. Smith, Research Report APES-70-2003, August 2003. Presented at the 2nd International Workshop on Reformulating Constraint Satisfaction Problems: Towards Systematisation and Automation, September 2003. (Abstract)
  • Dual Modelling of Permutation and Injection Problems
    Brahim Hnich, Barbara M. Smith and Toby Walsh. JAIR (21) pp. 357-391, 2004. (Abstract)
  • A Dual Graph Translation of a Problem in `Life'
    Barbara M. Smith, in Principles and Practice of Constraint Programming - CP 2002, ed. Pascal van Hentenryck, pp. 402-414, Springer, LNCS 2470, 2002. (Abstract)
  • Towards Model Reformulation at Multiple Levels of Abstraction
    Alan M. Frisch, Brahim Hnich, Ian Miguel, Barbara M. Smith and Toby Walsh, presented at the International Workshop on Reformulating Constraint Satisfaction Problems: Towards Systematisation and Automation, September 2002. (Abstract)
  • A 0/1 encoding of the GACLex constraint for pairs of vectors
    Ian P. Gent, Patrick Prosser and Barbara M. Smith, presented at the ECAI 2002 workshop W9 Modelling and Solving Problems with Constraints.
  • A Constraint Programming Approach to the Stable Marriage Problem
    Ian P. Gent, Robert W. Irving, David F. Manlove, Patrick Prosser, and Barbara M. Smith, in Principles and Practice of Constraint Programming - CP 2001, ed. Toby Walsh, pp. 225-239, Springer, LNCS 2239, 2001. (Abstract)
  • Dual Models of Permutation Problems
    Barbara M. Smith, in Principles and Practice of Constraint Programming - CP 2001, ed. Toby Walsh, pp. 615-619, Springer, LNCS 2239, 2001. (Abstract)
  • Dual Models in Constraint Programming
    Barbara M Smith, School of Computing Research Report 2001.02, University of Leeds, January 2001. (Abstract)
  • Modelling a Permutation Problem
    Barbara M Smith, School of Computing Research Report 2000.18, University of Leeds, June 2000. Presented at the ECAI'2000 Workshop on Modelling and Solving Problems with Constraints. (Abstract)
  • Using auxiliary variables and implied constraints to model non-binary problems
    Barbara M Smith, Kostas Stergiou and Toby Walsh, Report APES-18-2000. In Proceedings AAAI-2000, pp. 182-187. (Abstract)
  • Modelling the Golomb Ruler Problem
    Barbara M Smith, Kostas Stergiou and Toby Walsh, School of Computing Research Report 1999.12, University of Leeds, June 1999. (Presented at the IJCAI'99 Workshop on Non-binary Constraints.) (Abstract)
  • ILP and Constraint Programming Approaches to a Template Design Problem
    Les Proll and Barbara Smith, School of Computing Research Report 97.16, University of Leeds, May 1997. (Revised version in INFORMS Journal of Computing, 10, pp. 265-275, 1998.) (Abstract)
  • Organizing a Social Event - A Difficult Problem of Combinatorial Optimisation
    Sally C. Brailsford, Peter M. Hubbard, Barbara M. Smith and H. Paul Williams, Computers and Operations Research, 23, pp. 845-856,1996. (Abstract)
  • The Progressive Party Problem: Integer Linear Programming and Constraint Programming Compared
    Barbara M Smith, S C Brailsford, P M Hubbard & H P Williams, School of Computing Research Report 95.8, University of Leeds, March 1995. (A revised version appears in Proceedings of First International Conference on Principles and Practice of Constraint Programming (CP'95), Springer Verlag LNCS 976, pp 36-52, Cassis, September 1995. A further revised version appears in Constraints, vol. 1, pp. 119-138, 1996.) (Abstract)

    Symmetry

    (Several of the recent modelling papers also discuss symmetry and how to eliminate it.)
  • Constraint Symmetry for the Soft CSP
    Barbara M. Smith, Stefano Bistarelli, and Barry O'Sullivan. In Ian P. Gent, Steve Linton, and Karen E. Petrie, editors, Proceedings of the International Symmetry Conference, pages 97-111, January 2007. A revised and shortened version appears in: Christian Bessiere, editor, Principles and Practice of Constraint Programming - CP 2007, LNCS 4741, pages 872-879. Springer, 2007. (Abstract)
  • Constraint Symmetry and Solution Symmetry
    David Cohen, Peter Jeavons, Chris Jefferson, Karen E. Petrie, and Barbara M. Smith. In Proceedings of the 21st National Conference in Artificial Intelligence (AAAI-06), pages 1589-1592. (NECTAR stream.) AAAI Press, 2006. (Abstract)
  • Symmetry Definitions for Constraint Programming
    Dave Cohen, Peter Jeavons, Chris Jefferson, Karen E. Petrie and Barbara M. Smith. In Principles and Practice of Constraint Programming - CP 2005, ed. Peter van Beek, pp. 17-31, Springer, LNCS 3709, 2005. (Best Paper award.) (Abstract) (PowerPoint slides)
    An extended version of the paper appears in Constraints, 11:115-137, 2006.
  • Conditional Symmetry Breaking
    Ian P. Gent, Tom Kelsey, Steve A. Linton, Iain McDonald, Ian Miguel and Barbara M. Smith. In Principles and Practice of Constraint Programming - CP 2005, ed. Peter van Beek, pp. 256-270, Springer, LNCS 3709, 2005. (Abstract)
  • Sets of Symmetry Breaking Constraints
    Barbara M. Smith. In Proceedings of SymCon05, the 5th International Workshop on Symmetry in Constraints, 2005
  • Comparison of Symmetry Breaking Methods in Constraint Programming
    Karen E. Petrie and Barbara M. Smith. In Proceedings of SymCon05, the 5th International Workshop on Symmetry in Constraints, 2005
  • Dynamic Symmetry Breaking in Constraint Programming and Linear Programming Hybrids
    Karen E. Petrie, Barbara M. Smith and Neil Yorke-Smith. In Proceedings of STAIRS 2004, the 2nd European Starting AI Researchers Symposium, pp. 96-106, ed. E. Onaindia and S. Staab, IOS Press, 2004.
  • Conditional Symmetry in the All-Interval Series Problem
    Ian P. Gent, Iain McDonald and Barbara M. Smith. Proceedings of SymCon03, the 3rd International Workshop on Symmetry in Constraint Satisfaction Problems, Kinsale, Ireland, September 2003.
  • Symmetry Breaking in Graceful Graphs
    Karen E. Petrie and Barbara M. Smith, Research Report APES-56a-2003, June 2003. A shorter version appears in Principles and Practice of Constraint Programming - CP 2003, ed. Francesca Rossi, Springer, LNCS 2833, pp. 930-934. (Abstract)
  • Partial Symmetry Breaking
    Iain McDonald and Barbara M. Smith, in Principles and Practice of Constraint Programming - CP 2002, ed. Pascal van Hentenryck, pp. 431-445, Springer, LNCS 2470, 2002. (Abstract)
  • Symmetry Breaking Constraints for Matrix Models
    Zeynep Kiziltan and Barbara M. Smith, presented at SymCon'02: The Second International Workshop on Symmetry in Constraint Satisfaction Problems, September 2002. (Abstract)
  • Reducing Symmetry in a Combinatorial Design Problem
    Barbara M Smith, School of Computing Research Report 2001.01, University of Leeds, January 2001. Presented at the CP-AI-OR Workshop, April 2001. (Abstract)
  • Symmetry Breaking in the Alien Tiles Puzzle
    Ian Gent, Steve Linton and Barbara Smith, Report APES-22-2000, October 2000.
  • Symmetry Breaking During Search in Constraint Programming
    Ian P. Gent and Barbara M. Smith, School of Computing Research Report 99.02, University of Leeds, January 1999. (A revised version appears in Proceedings ECAI'2000, ed. W. Horn, pp. 599-603.) (Abstract)

    Search and Search Heuristics

  • Caching Search States in Permutation Problems
    Barbara M. Smith, In Principles and Practice of Constraint Programming - CP 2005, pp. 637-651, ed. Peter van Beek, Springer, LNCS 3709, 2005. (Abstract)
  • Value Ordering for Finding All Solutions
    Barbara M. Smith and Paula Sturdy, Proceedings of IJCAI-05, pp. 311-316. (Abstract)
  • An Empirical Investigation of Value Ordering for Finding All Solutions
    Barbara M. Smith and Paula Sturdy, Report CPPod-9-2004, October 2004.
  • The Brelaz Heuristic and Optimal Static Orderings
    Barbara M. Smith, School of Computing Research Report 1999.13, University of Leeds, June 1999. (Also in Principles and Practice of Constraint Programming - CP'99, ed. Joxan Jaffar, pp. 405-418, Springer-Verlag, LNCS 1713, 1999.) (Abstract)
  • Trying Harder to Fail First
    Barbara M Smith and Stuart A Grant, School of Computing Research Report 97.45, University of Leeds, November 1997. (Also in Proceedings ECAI'98, ed. Henri Prade, pp. 249-253, Wiley, 1998.) (Abstract)
  • Succeed-first or Fail-first: A Case Study in Variable and Value Ordering Heuristics
    Barbara Smith, School of Computing Research Report 96.26, University of Leeds, September 1996. (Presented at the ILOG Solver and ILOG Schedule 2nd International Users' Conference, Paris, July 1996. Also in the Proceedings of PACT'97, pp. 321-330) (Abstract)
  • An Empirical Study of Dynamic Variable Ordering Heuristics for the Constraint Satisfaction Problem
    Ian P Gent, Ewan MacIntyre, Patrick Prosser, Barbara M Smith & Toby Walsh, School of Computing Research Report 96.05, University of Leeds, February 1996. (A revised version appears in Principles and Practice of Constraint Programming - CP96, ed. E.C. Freuder, pp. 179-193, Springer-Verlag, LNCS 1118, 1996.) (Abstract)

    Phase Transitions and Random CSPs

  • Constructing an Asymptotic Phase Transition in Random Binary Constraint Satisfaction Problems
    Barbara M Smith. Journal of Theoretical Computer Science vol. 265, pp. 265-283 (Special Issue on NP-Hardness and Phase Transitions), 2001. An earlier version is available online as School of Computing Research Report 2000.02, University of Leeds, January 2000. (Abstract)
  • Random Constraint Satisfaction: Flaws and Structure
    Ian P Gent, Ewan MacIntyre, Patrick Prosser, Barbara Smith and Toby Walsh. Constraints 6 (4), pp. 345-372, October 2001. An earlier version is available online as Report APES-08-1998, revised 1999. (Abstract)
  • Random Constraint Satisfaction: Theory meets Practice
    Ewan MacIntyre, Patrick Prosser, Barbara Smith and Toby Walsh, in Principles and Practice of Constraint Programming - CP98, ed. Michael Maher and Jean-Francois Puget, pp. 325-339, LNCS 1520, Springer-Verlag, 1998. (Abstract)
  • Modelling Exceptionally Hard Constraint Satisfaction Problems
    Barbara M Smith and Stuart A Grant, School of Computing Research Report 97.26, University of Leeds, May 1997. (A revised version appears in Principles and Practice of Constraint Programming - CP97, ed. Gert Smolka, pp. 182-195, Springer-Verlag, LNCS 1330, 1997.) (Abstract)
  • The Arc and Path Consistency Phase Transitions
    Stuart Grant and Barbara Smith, School of Computing Research Report 96.09, University of Leeds, March 1996. (A shorter version appears in Principles and Practice of Constraint Programming - CP96, ed. E.C. Freuder, pp. 541-542, Springer-Verlag, LNCS 1118, 1996.) (Abstract)
  • Where the Exceptionally Hard Problems Are
    Barbara Smith and Stuart Grant, School of Computing Research Report 95.35, University of Leeds, December 1995. (Revised version of a paper presented at the CP95 workshop on Really Hard Problems, Cassis, September 1995.) (Abstract)
  • The Phase Transition Behaviour of Maintaining Arc Consistency
    Stuart Grant and Barbara Smith, School of Computing Research Report 95.25, University of Leeds, August 1995. (A revised and shortened version appears in Proceedings ECAI'96, pp. 175-179, 1996.) (Abstract)
  • Sparse Constraint Graphs and Exceptionally Hard Problems
    Barbara Smith and Stuart Grant, School of Computing Research Report 94.36, University of Leeds, December 1994. (A shorter version appears in the Proceedings of IJCAI-95, pp 646-651, Montreal, August 1995.) (Abstract)
  • Locating the Phase Transition in Binary Constraint Satisfaction Problems
    Barbara Smith, School of Computing Research Report 94.16, University of Leeds, May 1994. (Revised version (with Martin Dyer) appears in Artificial Intelligence, 81, pp. 155-181, 1996.) (Abstract)
  • In Search of Exceptionally Difficult Constraint Satisfaction Problems
    Barbara Smith, School of Computing Research Report 94.2, University of Leeds, January 1994. (A revised version appears in Constraint Processing, ed. Manfred Meyer, Springer Verlag Lecture Notes in Computer Science 923, pp 139-156, 1995.) (Abstract)
  • The Phase Transition in Constraint Satisfaction Problems: A Closer Look at the Mushy Region
    Barbara Smith, School of Computing Research Report 93.41, University of Leeds, December 1993. (A revised version, with the title `Phase Transition and the Mushy Region in Constraint Satisfaction Problems' appears in the Proceedings of ECAI'94 , ed. A.G.Cohn, pp. 100-104, Amsterdam, 1994.) (Abstract)

    Constraint Programming applied to Scheduling

  • Finding the Answer by Looking in the Wrong Place
    Elias Oliveira and Barbara M Smith, School of Computing Research Report 2001.18, University of Leeds, September 2001.
    Presented at Formul'01, the CP 2001 Post-Conference Workshop on Modelling and Problem Formulation, Paphos, Cyprus, December 2001. (Abstract)
  • A Combined Constraint-Based Search Method for Single-Track Railway Scheduling
    Elias Oliveira and Barbara M Smith. In Progress in Artificial Intelligence Knowledge Extraction, Multi-agent Systems, Logic Programming, and Constraint Solving (Proceedings of the 10th Portuguese Conference on Artificial Intelligence, EPIA 2001.) P. Brazdil and A. Jorge, eds. Springer, LNAI 2258, pp. 371-378, 2001.
  • A Hybrid Constraint-Based Method for Single-Track Railway Scheduling Problems
    Elias Oliveira and Barbara M Smith, School of Computing Research Report 2001.04, University of Leeds, February 2001. (Abstract)
  • A Job-Shop Scheduling Model for the Single-Track Railway Scheduling Problem
    Elias Oliveira and Barbara M Smith, School of Computing Research Report 2000.21, University of Leeds, August 2000. (Abstract)
  • Constructing Driver Schedules using Iterative Repair
    Suniel Curtis, Barbara M Smith and Anthony Wren, School of Computing Research Report 2000.01, University of Leeds, January 2000. (Also in Proceedings of PACLP 2000, pp. 59-78, April 2000.) (Abstract)
  • Forming Bus Driver Schedules using Constraint Programming
    Suniel Curtis, Barbara M Smith and Anthony Wren, School of Computing Research Report 99.05, University of Leeds, March 1999. (Also in Proceedings of PACLP99, pp. 239-254, April 1999.) (Abstract)
  • Bus Relief Point Selection Using Constraint Programming
    Colin Layfield, Barbara Smith and Anthony Wren, School of Computing Research Report 98.22, University of Leeds, October 1998. (Also in Proceedings of PACLP99, pp. 537-552, April 1999.) (Abstract)
  • A Constraint Programming Pre-processor for a Bus Driver Scheduling System
    Barbara Smith, Colin J Layfield and Anthony Wren, presented at the DIMACS Workshop on Constraint Programming and Large Scale Discrete Optimization, September 1998. In Constraint Programming and Large Scale Discrete Optimization, E.C. Freuder and R.J. Wallace (eds.) DIMACS vol. 57, pp. 131-148, 2001. (Abstract)
  • Constraint Programming Approaches to a Scheduling Problem in Steelmaking
    Alan W. Smith and Barbara M. Smith, School of Computing Research Report 97.43, University of Leeds, September 1997. (Presented at the CP97 Workshop on Industrial Constraint-Directed Scheduling, Schloss Hagenberg, Austria, November 1997) (Abstract)
  • Automated scheduling of astronomical observations
    Lewis R. Jones, Jon E. Spragg and Barbara M. Smith, Instrumentation in Astronomy VIII, 2198, pp. 918-923, 1994.

    Planning and Other Applications

  • Computing (Rt,St) Policies in a Non-Stationary Stochastic Demand Inventory System Using Constraint Programming
    S. Armagan Tarim and Barbara M. Smith, Presented at European Chapter on Combinatorial Optimization (ECCO XVIII), Minsk, Belarus, 2005. A revised version of the paper, Constraint Programming for Computing Non-Stationary (R,S) Inventory Policies, will appear in the European Journal of Operational Research. (Abstract)
  • CPPlanner: A Temporal Planning System using Critical Paths
    Tien Ba Dinh and Barbara Smith. Research Report APES-63-2003, July 2003. (Abstract)

    Review and Tutorial Papers

  • Modelling
    Barbara M. Smith. In Francesca Rossi, Peter van Beek, and Toby Walsh, editors, Handbook of Constraint Programming, Chapter 11, pages 377-406. Elsevier, 2006. ISBN 0-444-52726-5.
  • Modelling for Constraint Programming
    Lectures given at the 1st Constraint Programming Summer School, September 2005. (The modelling chapter in the Handbook of Constraint Programming is a revised version of the lecture notes. The slides for the lectures can be found at the Summer School Web site.)
  • Constraint Programming in Practice: Scheduling a Rehearsal
    Barbara Smith. Research Report APES-67-2003, September 2003. (Abstract)
  • Constraint Satisfaction Problems: Algorithms and Applications
    Sally C. Brailsford, Chris N. Potts and Barbara M. Smith, Invited Review, European J. of O.R., 119, pp. 557-581, 1999. (Abstract)
  • How Not To Do It
    Ian P Gent, Stuart A Grant, Ewan MacIntyre, Patrick Prosser, Paul Shaw, Barbara M Smith & Toby Walsh, School of Computing Research Report 97.27, University of Leeds, May 1997. (Abstract)
  • A Tutorial on Constraint Programming
    Barbara Smith, School of Computing Research Report 95.14, University of Leeds, April 1995. (Abstract)

    Barbara Smith, September 2008.