Contents
Chapter 1 Introduction
Chapter 2 Getting started with ECL
i
PS
e
2.1 How do I install the ECL
i
PS
e
system?
2.2 How do I read the online documentation?
2.3 How do I run my ECL
i
PS
e
programs?
2.4 How do I use
tkeclipse
?
2.4.1 Getting started
2.5 How do I write an ECL
i
PS
e
program?
2.5.1 Compiling a program
2.5.2 Executing a query
2.5.3 Editing a file
2.5.4 Debugging a program
2.5.5 File menu
2.5.6 Getting help
2.5.7 Other tools
2.6 How do I make things happen at compile time?
2.7 How do I use ECL
i
PS
e
libraries in my programs?
2.8 Other tips
2.8.1 Recommended file names
Chapter 3 Prolog Introduction
3.1 Terms and their data types
3.1.1 Numbers
3.1.2 Strings
3.1.3 Atoms
3.1.4 Lists
3.1.5 Structures
3.2 Predicates, Goals and Queries
3.2.1 Conjunction and Disjunction
3.3 Unification and Logical Variables
3.3.1 Symbolic Equality
3.3.2 Logical Variables
3.3.3 Unification
3.4 Defining Your Own Predicates
3.4.1 Comments
3.4.2 Clauses and Predicates
3.5 Execution Scheme
3.5.1 Resolution
3.6 Partial data structures
3.7 More control structures
3.7.1 Disjunction
3.7.2 Conditional
3.7.3 Call
3.7.4 All Solutions
3.8 Using Cut
3.8.1 Commit to current clause
3.8.2 Prune alternative solutions
3.9 Common Pitfalls
3.9.1 Unification works both ways
3.9.2 Unexpected backtracking
3.10 Exercises
Chapter 4 ECL
i
PS
e
Programming
4.1 Structure Notation
4.2 Loops
4.3 Working with Arrays of Items
4.4 Storing Information Across Backtracking
4.4.1 Bags
4.4.2 Shelves
4.5 Input and Output
4.5.1 Printing ECL
i
PS
e
Terms
4.5.2 Reading ECL
i
PS
e
Terms
4.5.3 Formatted Output
4.5.4 Streams
4.6 Matching
4.7 List processing
4.8 String processing
4.9 Term processing
4.10 Module System
4.10.1 Overview
4.10.2 Making a Module
4.10.3 Using a Module
4.10.4 Qualified Goals
4.10.5 Exporting items other than Predicates
4.11 Exception Handling
4.12 Time and Memory
4.12.1 Timing
4.13 Exercises
Chapter 5 A Tutorial Tour of Debugging in TkECL
i
PS
e
5.1 The Buggy Program
5.2 Running the Program
5.3 Debugging the Program
5.4 Summary
5.4.1 TkECL
i
PS
e
toplevel
5.4.2 Predicate Browser
5.4.3 Delayed Goals Viewer
5.4.4 Tracer
5.4.5 Tracer Filter
5.4.6 Term Inspector
Chapter 6 Program Analysis
6.1 What tools are available?
6.2 Profiler
6.3 Line coverage
6.3.1 Compilation
6.3.2 Results
Chapter 7 An Overview of the Constraint Libraries
7.1 Introduction
7.2 Implementations of Domains and Constraints
7.2.1 Suspended Goals:
suspend
7.2.2 Interval Solver:
ic
7.2.3 Global Constraints:
ic_global
7.2.4 Scheduling Constraints:
ic_cumulative, ic_edge_finder
7.2.5 Finite Integer Sets:
ic_sets
7.2.6 Linear Constraints:
eplex
7.2.7 Constraints over symbols:
ic_symbolic
7.3 User-Defined Constraints
7.3.1 Generalised Propagation:
propia
7.3.2 Constraint Handling Rules:
ech
7.4 Search and Optimisation Support
7.4.1 Tree Search Methods:
ic_search
7.4.2 Optimisation:
branch_and_bound
7.5 Hybridisation Support
7.5.1 Repair and Local Search:
repair
7.5.2 Hybrid:
ic_probing_for_scheduling
7.6 Other Libraries
Chapter 8 Getting started with Interval Constraints
8.1 Using the Interval Constraints Library
8.2 Structure of a Constraint Program
8.3 Modelling
8.4 Built-in Constraints
8.5 Global constraints
8.5.1 Different strengths of propagation
8.6 Simple User-defined Constraints
8.6.1 Using Reified Constraints
8.6.2 Using Propia
8.6.3 Using the
element
Constraint
8.7 Searching for Feasible Solutions
8.8 Bin Packing
8.8.1 Problem Definition
8.8.2 Problem Model - Using Structures
8.8.3 Handling an Unknown Number of Bins
8.8.4 Constraints on a Single Bin
8.8.5 Symmetry Constraints
8.8.6 Search
8.9 Exercises
Chapter 9 Working with real numbers and variables
9.1 Real number basics
9.2 Issues to be aware of when using bounded reals
9.3 IC as a solver for real variables
9.4 Finding solutions of real constraints
9.5 A larger example
9.6 Exercise
Chapter 10 The Integer Sets Library
10.1 Why Sets
10.2 Finite Sets of Integers
10.3 Set Variables
10.4 Constraints
10.5 Search Support
10.6 Example
10.7 Weight Constraints
10.8 Exercises
Chapter 11 Problem Modelling
11.1 Constraint Logic Programming
11.2 Issues in Problem Modelling
11.3 Modelling with CLP and ECL
i
PS
e
11.4 Same Problem - Different Model
11.5 Rules for Modelling Code
11.5.1 Disjunctions
11.5.2 Conditionals
11.6 Symmetries
Chapter 12 Tree Search Methods
12.1 Introduction
12.1.1 Overview of Search Methods
12.1.2 Optimisation and Search
12.1.3 Heuristics
12.2 Complete Tree Search with Heuristics
12.2.1 Search Trees
12.2.2 Variable Selection
12.2.3 Value Selection
12.2.4 Example
12.2.5 Counting Backtracks
12.3 Incomplete Tree Search
12.3.1 First Solution
12.3.2 Bounded Backtrack Search
12.3.3 Depth Bounded Search
12.3.4 Credit Search
12.3.5 Timeout
12.3.6 Limited Discrepancy Search
12.4 Exercises
Chapter 13 Repair and Local Search
13.1 Motivation
13.2 Syntax
13.2.1 Setting and Getting Tentative Values
13.2.2 Building and Accessing Conflict Sets
13.2.3 Propagating Conflicts
13.3 Repairing Conflicts
13.3.1 Combining Repair with IC Propagation
13.4 Introduction to Local Search
13.4.1 Changing Tentative Values
13.4.2 Hill Climbing
13.5 More Advanced Local Search Methods
13.5.1 The Knapsack Example
13.5.2 Search Code Schema
13.5.3 Random walk
13.5.4 Simulated Annealing
13.5.5 Tabu Search
13.6 Repair Exercise
Chapter 14 Implementing Constraints
14.1 What is a Constraint in Logic Programming?
14.2 Background: Constraint Satisfaction Problems
14.3 Constraint Behaviours
14.3.1 Consistency Check
14.3.2 Forward Checking
14.3.3 Domain (Arc) Consistency
14.3.4 Bounds Consistency
14.4 Programming Basic Behaviours
14.4.1 Consistency Check
14.4.2 Forward Checking
14.5 Basic Suspension Facility
14.6 A Bounds-Consistent IC constraint
14.7 Using a Demon
14.8 Exercises
Chapter 15 Propia and CHR
15.1 Two Ways of Specifying Constraint Behaviours
15.2 The Role of Propia and CHR in Problem Modelling
15.3 Propia
15.3.1 How to Use Propia
15.3.2 Propia Implementation
15.3.3 Propia and Related Techniques
15.4 CHR
15.4.1 How to Use CHR
15.4.2 Multiple Heads
15.5 A Complete Example of a CHR File
15.5.1 CHR Implementation
15.6 Global Reasoning
15.7 Propia and CHR Exercise
Chapter 16 The Eplex Library
16.1 Introduction
16.1.1 What is Mathematical Programming?
16.1.2 Why interface to Mathematical Programming solvers?
16.1.3 Example formulation of an MP Problem
16.2 How to load the library
16.3 Modelling MP problems in ECL
i
PS
e
16.3.1 Eplex instance
16.3.2 Example modelling of an MP problem in ECL
i
PS
e
16.3.3 Getting more solution information from the solver
16.3.4 Adding integrality constraints
16.4 Repeated Solving of an Eplex Problem
16.5 Exercise
Chapter 17 Building Hybrid Algorithms
17.1 Combining Domains and Linear Constraints
17.2 Reasons for Combining Solvers
17.3 A Simple Example
17.3.1 Problem Definition
17.3.2 Program to Determine Satisfiability
17.3.3 Program Performing Optimisation
17.4 Sending Constraints to Multiple Solvers
17.4.1 Syntax and Motivation
17.4.2 Handling Booleans with Linear Constraints
17.4.3 Handling Disjunctions
17.4.4 A More Realistic Example
17.5 Using Values Returned from the Linear Optimum
17.5.1 Reduced Costs
17.5.2 Probing
17.5.3 Probing for Scheduling
17.6 Other Hybridisation Forms
17.7 References
17.8 Hybrid Exercise
Chapter 18 The Colgen Library
18.1 The LP Model
18.2 The Hybrid Colgen Model