University of Alberta University College, Cork Glasgow University Huddersfield University Leeds University University of St Andrews University of Strathclyde University of Waterloo University of York
Research Reports of the APES Group

 
HOME
INFORMATION
MEMBERS
ALUMNI
RESEARCH
PUBLICATIONS
REPORTS
EVENTS
RESOURCES

 

 

APES-87-2005: Filtering Algorithms for the NValue Constraint
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, and Toby Walsh. January 2005.   (Bibtex entry)

APES-86-2004: Combining SBDS and SBDD
Karen E. Petrie. July 2004.   (Bibtex entry)

APES-84-2004: Disjoint, Partition and Intersection Constraints for Set and Multiset Variables
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, and Toby Walsh. May 2004.   (Bibtex entry)

APES-83-2004: The Tractability of Global Constraints
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, and Toby Walsh. May 2004.   (Bibtex entry)

APES-82-2004: The Optimality of a Fast CNF Conversion and its Use with SAT
Paul Jackson and Daniel Sheridan. March 2004.   (Bibtex entry) (postscript).

APES-81-2004: Dynamic Symmetry Breaking in Constraint Programming and Linear Programming Hybrids
Karen E. Petrie and Barbara Smith and Neil Yorke-Smith. February 2004.   (Bibtex entry) (postscript).

APES-80-2004: Solution Learning and Solution Directed Backjumping, Revisited
Ian Gent and Andrew Rowley. February 2004.   (Bibtex entry) (postscript).

APES-79-2004: Encoding Quantified CSPs as Quantified Boolean Formulae
Ian Gent, Peter Nightingale, and Andrew Rowley. February 2004.   (Bibtex entry) (postscript).

APES-78-2004: Algorithms for Quantified Constraint Satisfaction Problems
Nikos Mamoulis, and Kostas Stergiou, January 2004.   (Bibtex entry)

APES-77-2004: A Constraint Algebra
Fahiem Bacchus and Toby Walsh, January 2004.   (Bibtex entry) (postscript).

APES-76-2004: The Complexity of Global Constraints
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, and Toby Walsh, January 2004.   (Bibtex entry)

APES-75-2004: Refining and Abstract Specification of the Golomb Ruler Problem
A.M. Frisch, C. Jefferson, B. Martinez-Hernandez, I. Miguel, December 2003.   (Bibtex entry)

APES-74-2004: Symmetry-breaking as a Prelude to Implied Constraints: A Constraint Modelling Pattern
A.M. Frisch, C. Jefferson, I. Miguel, December 2003.   (Bibtex entry)

APES-73-2003: The Extended Literal Encoding of SAT into CSP
Ian Gent, Patrick Prosser, and Toby Walsh, November 2003.   (Bibtex entry) (postscript).

APES-72-2003: TETRAVEX is NP-complete
Toby Walsh, October 2003.   (Bibtex entry).

APES-71-2003: Why SBDD can be worse than SBDS
Karen Petrie, August 2003.   (Bibtex entry), (pdf).

APES-70-2003: Search Strategies for Optimization: Modelling the SONET Problem
Barbara Smith, August 2003.   (Bibtex entry).

APES-69-2003: Symmetry Breaking Ordering Constraints
Zeynep Kiziltan, April 2003.   (Bibtex entry), (pdf).

APES-68-2003: Encoding Connect-4 using Quantified Boolean Formulae
Ian Gent and Andrew Rowley, July 2003.   (Bibtex entry), (pdf).

APES-67-2003: Constraint Programming in Practice: Scheduling a Rehearsal
Barbara Smith, September 2003.   (Bibtex entry).

APES-66-2003: Super CSPs
Emmanuel Hebrard, Brahim Hnich and Toby Walsh, July 2003.   (Bibtex entry), (pdf).

APES-65-2003: A Framework for Comparing Symmetry Breaking methods
Karen E. Petrie, June 2003.   (Bibtex entry), (pdf).

APES-64-2003: Learning Good Variable Orderings
Paula Sturdy, June 2003.   (Bibtex entry), (pdf).

APES-63-2003: CPPlaner: A Temporal Planning System using Critical Paths
Tien Ba Dinh, and Barbara Smith, July 2003.   (Bibtex entry), (pdf).

APES-62-2003: Watching Clauses in Quantified Boolean Formulae
Andrew G D Rowley, July 2003.   (Bibtex entry), (pdf).

APES-61-2003: NuSBDS: Symmetry Breaking made Easy
Iain McDonald, July 2003.   (Bibtex entry), (pdf).

APES-60-2003: Symmetry Group generation for CSPs
Warwick Harvey, Tom Kelsey, and Karen Petrie, July 2003.   (Bibtex entry), (pdf).

APES-59-2003: Global constraints by composition: lexicographic ordering with sums
Brahim Hnich, Zeynep Kiziltan, and Toby Walsh, April 2003.   (Bibtex entry), (pdf).

APES-58-2003: Using Stochastic Local Search to Solve Quantified Boolean Formulae
Ian P Gent, Holger H Hoos, Andrew G D Rowley and Kevin Smyth, January 2003.   (Bibtex entry), (pdf).

APES-57-2003: Generic SBDD using GAP and ECLiPSe
Ian Gent, Warwick Harvey, Tom Kelsey and Steve Linton, January 2003.   (Bibtex entry), (pdf).

APES-56a-2003: Symmetry Breaking in Graceful Graphs
Karen E. Petrie and Barbara M. Smith, June 2003.   (Bibtex entry)

APES-56-2003: Symmetry Breaking in Graceful Graphs
Karen E. Petrie and Barbara M. Smith, January 2003.   (Bibtex entry)

APES-55-2003: Multiset ordering constraints Alan Frisch, Brahim Hnich, Zeynep Kiziltan, Ian Miguel and Toby Walsh, January 2003.  (pdf).

APES-54-2003: Reasoning about soft constraints and conditional preferences: complexity results and approximation techniques Carmel Domshlak, Francesca Rossi, Brent Venable, and Toby Walsh, January 2003.  (pdf).

APES-53-2003: Scenario Based Stochastic Constraint Programming
Suresh Manandhar, Armagan Tarim, Toby Walsh, January 2003.   (pdf). This paper has been submitted to IJCAI2003.

APES-52-2002: Supertree Construction with Constraint Programming: first steps
Ian P. Gent, Patrick Prosser, Barabra M. Smith, December 2002.   (Bibtex entry), (pdf).

APES-51-2002: Global constraints for lexicographic orderings
Alan Frisch, Brahim Hnich, Zeynep Kiziltan, Ian Miguel, Toby Walsh, September 2002.   (Bibtex entry), (pdf). This paper has been submitted to the CP2002.

APES-50-2002: Models and Symmetry breaking for `Peaceable Armies of Queens'
Barbara Smith, Karen Petrie and Ian Gent, May 2002.   (Bibtex entry), (pdf). This paper has been submitted to the ECAI2002 workshop on Modelling and Solving Problems with Constraints.

APES-49-2002: Partial Symmetry Breaking
Iain McDonald, Barbara Smith, May 2002.   (Bibtex entry), (pdf). This paper has been submitted to CP2002.

APES-48-2002: Groups and Constraints: Symmetry Breaking During Search
I.P. Gent, W. Harvey, T. Kelsey, May 2002.   (Bibtex entry), (pdf). This paper has been submitted to CP2002.

APES-47-2002: Graph Transformations for the Vehicle Routing and Job Shop Scheduling Problems
J.C. Beck, P. Prosser, E. Selensky, March 2002.   (Bibtex entry), (pdf). This paper has been submitted to ICGT02.

APES-46-2002: Solving 2-CNF Quantified Boolean Formulae using Variable Assignment and Propagation
Ian P. Gent and Andrew G. D. Rowley.  (Bibtex entry), (ps) This paper has been submitted to the QBF workshop at SAT-2002.

APES-45-2002: A case study of constraint programming for configuration problems
Kevin McDonald and Patrick Prosser.  (Bibtex entry), (pdf). This paper has been submitted to AIEDAM Special ssue on Configuration.

APES-44-2002: On the Reformulation of Vehicle Routing Problems and Scheduling Problems
J.C. Beck, P. Prosser, E. Selensky, February 2002.   (Bibtex entry), (pdf). This paper has been submitted to SARA2002.

APES-43-2002: Adding resolution to the DPLL procedure for Boolean satisfiability
L. Drake, A.M. Frisch, and T. Walsh, February 2002.   (Bibtex entry), (pdf). This paper has been submitted to SAT-2002.

APES-42-2002: CGRASS: A System for Transforming Constraint Satisfaction Problems
A.M. Frisch, I. Miguel and T. Walsh, January 2002.   (Bibtex entry), (pdf). This paper has been submitted to ECAI-2002.

APES-41-2002: Using Fixpoint Characterisations of LTL for Bounded Model Checking
D. Sheridan, January 2002.   (Bibtex entry), (pdf).

APES-40-2002: An Empirical Study of the Stable Marriage Problem with Ties and Incomplete Lists
I.P. Gent and P. Prosser, January 2002.   (Bibtex entry), (pdf). This paper has been submitted to ECAI-2002.

APES-39A-2002: Arc Consistency in SAT
I.P. Gent, June 2002.   (Bibtex entry), (pdf). This is an extended version of a paper appearing in ECAI-2002, and replaces an earlier version of this report which is no longer available.

APES-38-2002: A Dual Graph Translation of a Problem in `Life'
B.M. Smith, January 2002.   (Bibtex entry), (pdf). This paper has been submitted to ECAI-2002.

APES-37-2002: The Interface between P and NP: COL, XOR, NAE, 1-in-k, and Horn SAT
T. Walsh, 2002.   (Bibtex entry), (pdf).

APES-36-2001: Matrix Modelling
P. Flener, A. Frisch, B. Hnich, Z. Kiziltan, I. Miguel and T. Walsh, 2001.   (Bibtex entry), (pdf).

APES-35-2001: Finding the Answer by Looking in the Wrong Place
E. Oliveira and Barbara M. Smith, September 2001.   (Bibtex entry) , (pdf).

APES-34-2001: On the Encoding of Constraint Satisfaction Problems with 0/1 variables
Patrick Prosser and Evgeny Selensky , 2001.   (Bibtex entry), (pdf).

APES-33-2001: A Symmetry Breaking Constraint for Indistinguishable Values
I.P. Gent, 2001.   (Bibtex entry), (pdf).

APES-32-2001: Automatic Generation of Implied and Induced Constraints
S. Colton and I. Miguel, 2001.   (Bibtex entry), (pdf).

APES-31-2001: Reducing Symmetry in Matrix Models: SBDS vs. Constraints
B.M. Smith and I.P. Gent, 2001.   (Bibtex entry), (pdf).

APES-30-2001: Symmetry in Matrix Models
P. Flener, A. Frisch, B. Hnich, Z. Kiziltan, I. Miguel, J. Pearson and T. Walsh, October 2001.   (Bibtex entry), (pdf).

APES-29-2001: Tightness of Constraint Satisfaction Problems
J. Culberson and T. Walsh, January 2001.   (Bibtex entry), (pdf).

APES-28-2001: Relational Consistencies
T. Walsh, January 2001.   (Bibtex entry), (pdf).

APES-27-2001: Search on High Degree Graphs
T. Walsh, January 2001.   (Bibtex entry), (pdf).

APES-26-2001: Permutation Problems and Channelling Constraints
T. Walsh, January 2001.   (Bibtex entry), (pdf).

APES-25-2001: Benford's Law
I.P. Gent and T. Walsh, January 2001.   (Bibtex entry), (pdf).

APES-24-2001: Backbones in Optimization and Approximation
J. Slaney and T. Walsh, January 2001.   (Bibtex entry), (pdf).

APES-23-2000: Stochastic Constraint Programming
T. Walsh, October 2000.   (Bibtex entry)
, (pdf).

APES-22-2000: Symmetry Breaking in the Alien Tiles Puzzle
I.P. Gent, S.A. Linton and B.M. Smith, October 2000.   (Bibtex entry), (pdf).

APES-21-2000: Experiments with Local Search on Random-2+p-SAT
Josh Singer, Ian P. Gent and Alan Smaill, July 2000.   (Bibtex entry).

APES-20-2000: Inside MAC and FC
Ian P. Gent and Patrick Prosser, May 2000.   (Bibtex entry).

APES-19-2000: Frozen Development in Graph Coloring
Joseph Culberson and Ian P. Gent, February 2000. Submitted to Theoretical Computer Science   (Bibtex entry).

APES-18-2000: Using auxiliary variables and implied constraints to model non-binary problems
Barbara Smith, Kostas Stergiou and Toby Walsh. January 2000.   (Bibtex entry)

APES-17-1999: Backbone Fragility Causes the Local Search Cost Peak
Josh Singer, Ian P. Gent and Alan Smaill. December 1999.   (Bibtex entry)

APES-16-1999: Empirical Evidence for Discontinuity in the Backbone of the 3-Coloring Phase Transition
Joseph Culberson and Ian P. Gent, September 1999.   (Bibtex entry)

APES-15-1999: On the Completeness of WalkSAT for 2-SAT
Joseph Culberson and Ian P. Gent, September 1999.   (Bibtex entry)
APES-15A-2000: On the Probabilistic Approximate completeness of WalkSAT for 2-SAT is a revised and extended version of report APES-15, by Joseph Culberson, Ian P. Gent, and Holger Hoos, February 2000, submitted to Information Processing Letters. (Bibtex entry)

APES-14-1999: Decomposable Constraints
Ian Gent, Kostas Stergiou and Toby Walsh. September 1999.   (Bibtex entry)

APES-13-1999: Well out of reach: Why hard problems are hard
Joseph Culberson and Ian P. Gent, June 1999.   (Bibtex entry)

APES-12-1999: Constrainedness of Search
Ian P. Gent, Patrick Prosser and Toby Walsh. June 1999. 

APES-11-1999: Modelling the Golomb Ruler Problem
Barbara Smith, Kostas Stergiou and Toby Walsh. May 1999.

APES-10-1999:An Empirical Study of Constraint Satisfaction Problems
Final Report Summary of EPSRC grant GR/K65706

APES-09-1999: CSPLib: a benchmark library for constraints
Ian Gent and Toby Walsh. April 1999.

APES-08-1998: Random Constraint Satisfaction: Flaws and Structure
Ian Gent, Ewan MacIntyre, Patrick Prosser, Barbara Smith and Toby Walsh. Revised version, September 1999. The revised version corrects mistakes and contains significant new results. For historical reasons the October 1998 version is also available.

APES-07-1998: Search in a Small World
Toby Walsh. October 1998.

APES-06-1998: Dynamic VRPs: A Study of Scenarios
Philip Kilby, Patrick Prosser and Paul Shaw. September 1998.

APES-05-1998: Beyond NP: the QSAT phase transition
Ian Gent and Toby Walsh. July 1998. Note A revised version of this paper is in proceedings of AAAI-99. That paper is available online from here, and is copyright AAAI and is placed here with AAAI's permission.

APES-04-1998: Backtracking Algorithms for Disjunctions of Temporal Constraints
Kostas Stergiou. April 1998.

APES-03-1998: On the Stupid Algorithm for Satisfiability
Ian Gent. April 1998.

APES-02-1998: Two Results on Car-sequencing Problems
Ian Gent. April 1998.

APES-01-1998: Implementation of LNS for Constrained VRPs
Philip Kilby, Patrick Prosser, and Paul Shaw. April 1998. 

 

Why do we issue our own reports? 
 

Some of these reports contain results that will appear (or have later appeared) in refereed publications. By making the results available within an APES Research Report, we hope to provide the research community with earlier access to results that might be of value. 
 

Others of these reports contain results that are perhaps not substantial enough for a refereed publication. However, they may still be of interest to people outside the APES group. 


 
 
 
 
CONTACT US


apes-request@dcs.st-and.ac.uk

 

 

 

 

Last updated 9 May 2002