|
Constraint Logic Programming via ECLiPSe |
Forword,i
1 Introduction, 1
1.1 What is Constraint Logic Programming?,1
1.2 Why use Constraint Logic Programming?, 2
1.3 What do we mean by ’constraints’?, 5
1.4 Constraint logic programming and artificial intelligence, 6
1.5 Constraint logic programming and operations research, 8
1.6 Constraint logic programming and knowledge engineering, 9
1.7 How to use the book?, 10
2 In the beginning was Prolog 15
2.1 Prolog basics, 15
2.1.1 Domain of inference, 16
2.1.2 Modes of variables, 20
2.1.3 Operations, 21
2.1.4 Unification, 23
2.1.5 Tree search without trees, 24
2.1.6 Failing usefully, 28
2.1.7 Recursive definitions, 29
2.1.8 Basic list operations, 31
2.1.9 Generating lists, 33
2.1.10 Controlling backtracking with ’cut’, 35
2.1.11 Lameness of Prolog’s logic, 38
2.2 Prolog and CLP problems classification, 39
2.3 Configuring a 3-element system, 40
2.3.1 Exhaustive search for a feasible configuration, 41
2.3.2 Backtracking search for a feasible configuration, 44
2.3.3 Branch-and-bound search for optimum configurations, 47
2.4 Golfers, 50
2.5 Three cubes, 53
2.6 Who is the killer?, 55
2.7 Placing queens, 57
2.7.1 Exhaustive search for queens, 57
2.7.2 Backtracking search for queens, 59
2.8 Examination - backtracking search, 66
2.9 Paradoxes in Prolog, 68
2.10 How to become your own grandfather?, 69
2.11 Maze, 71
2.12 Mine field, 74
2.13 Farmer-wolf-goat-cabbage, 77
2.14 Missionaries and cannibals, 81
2.15 Towers of Hanoi, 86
2.16 Water jugs problem, 88
2.17 Exercises, 92
3 CLP with elementary constraints for feasible solutions, 103
3.1 How CLP languages differ from Prolog?, 103
3.1.1 Queens - CLP approaches, 105
3.1.2 Forward Checking for queens, 106
3.1.3 Looking Ahead+Forward Checking for queens, 107
3.2 Search heuristics, 109
3.3 Consistency techniques, 112
3.4 Propagating constraints with failure, 113
3.5 Successful propagation of constraints, 118
3.6 Who with whom? - propagation, 120
3.7 Students and languages - propagation, 122
3.8 Propagation and search: three equations in integers, 127
3.9 Golfers again, 129
3.10 Watchtowers - search and propagation, 131
3.11 Examination - search and propagation, 132
3.13 Feasible configuration - search and
propagation, 135
3.14 Righteous Oppositionists and Secret
Collaborators, 136
3.15 Exercises, 141
4 CLP with global constraints for feasible solutions, 147
4.1 Introductory remarks, 147
4.2 The ”alldifferent/1” built-in, 148
4.3 The ”element/3” built-in, 50
4.4 SendMoreMoney, 151
4.5 Who with whomone more time, 152
4.6 Golfers again, 154
4.7 Three cubes again, 157
4.8 Queens again, 159
4.9 Five rooms, 160
4.10 Ten rooms, 164
4.11 All Things to All People, 171
4.12 Seven machines - seven tasks, 174
4.13 Threemachines - three fromfive tasks, 177
4.14 Threemachines - five tasks, 178
4.15 Data handling, 180
4.15.1 Structures and arrays, 180
4.15.2 How to get hold of matrix elements?, 184
4.15.3 Recursions and iterations - bye, bye declarativity!, 184
4.16 Scalar product, 191
4.17 Queens onemore time, 192
4.18 Sudoku, 193
4.19 Queens for the last time, 96
4.20 Dinner calamity, 196
4.21 Bob’s Shish Kebab, 200
4.22 Exercises, 207
5 CLP with elementary constraints for optimal solutions, 213
5.1 General remarks, 213
5.2 Upgrading Branch-and-Bound, 214
5.2.1 Optimum queen placement - standard Branch-and-Bound, 215
5.2.2 Optimum queen placement - Branch and Bound + Forward Checking, 217
5.2.3 Optimum queen placement - Branch-and-Bound + Looking
Ahead + Forward Checking, 217
5.3 Basic built-ins, 217
5.3.1 The ”bbmin/3” built-in, 218
5.3.2 The ”search/6” built-in, 219
5.4 How to increase the pension fund while going green at the same time?, 221
5.5 General optimization approaches, 224
5.6 Optimum configuration - OR approach, 225
5.7 Optimum configuration - CLP approach, 228
5.8 Optimizing tasks allocation for 7 machines - OR approach, 230
5.9 Optimizing tasks allocation for 7 machines - CLP approach, 235
5.10 Delivering mining output 1, 237
5.11 Delivering mining output 2, 240
5.12 Delivering mining output 3, 241
5.13 Map coloring, 243
5.14 Knapsack problem1, 245
5.15 Reified constraints, 247
5.16 Constraints for sets, 249
5.17 Knapsack problem2, 253
5.18 Warehouse location problem - OR approach, 254
5.19 Warehouse location problem - CLP approach, 256
5.20 Warehouse location problem 1 professional, 258
5.21 Warehouse location problem 2 professional, 262
5.22 Basic crew rostering, 265
5.22.1 Workforce constraints, 265
5.22.2 The power and misery of optimization, 267
5.23 Basic scheduling, 272
5.23.1 Precedence constraints - building a house, 273
5.23.2 Disjunctive constraints - limited resources, 278
5.24 Optimization and conflicting constraints - a photo, 280
5.25 Appointing a parliamentary committee, 285
5.26 Fighting for rainfall justice, 288
5.27 How to cut optimally?, 292
5.28 SendMostMoney, 294
5.29 Exercises, 295
6 CLP with global constraints for optimal solutions, 303
6.1 Introduction, 303
6.2 The ”cumulative/4” built-in, 304
6.3 Cumulative scheduling 1, 304
6.4 Cumulative scheduling 2, 306
6.5 The ”disjunctive/2” built-in, 309
6.6 Disjunctive scheduling 1, 309
6.7 Reading newspapers 1, 310
6.8 Reading newspapers 2, 316
6.9 Reading newspapers 3, 320
6.10 Assembling bicycles, 323
6.11 Ship unloading and loading, 337
6.12 What is a job-shop?, 344
6.13 A difficult job-shop scheduling problem - benchmark MT10, 347
6.14 Traveling Salesman Problems, 360
6.14.1 Hamiltonian circuits, 360
6.14.2 Scheduling a process line, 363
6.14.3 Scheduling a salesman, 365
6.15 Exercises, 370
7 CLP for continuous variables, 375
7.1 CCSP and CCOP, 375
7.2 The blessing and curse of compound interest, 376
7.2.1 To retire as millionaire - 1, 377
7.2.2 To retire as millionaire - 2, 378
7.2.3 Those cursed mortgages!, 379
7.3 Warehouses - suppliers, 381
7.4 Refining and blending oils, 385
7.5 How to make easymoney?, 387
7.6 Making shrewd investments, 390
7.7 Yet another financial Perpetuum Mobile!, 395
7.8 Exercises, 402
Afterword, 407
Glossary, 409
References, 417