Constraint Reasoning for Differential Models

Title page......Page 2
Table of Contents......Page 24
Introduction......Page 28
Global Hull-consistency - A Strong Consistency Criterion......Page 31
Guide to the Dissertation......Page 32
Interval Constraints......Page 36
Constraint Satisfaction Problems......Page 38
Pruning......Page 40
Branching......Page 41
Constraint Satisfaction Problems With Continuous Domains......Page 42
Intervals Representing Unidimensional Continuous Domains......Page 43
Interval Operations and Basic Functions......Page 45
Boxes Representing Multidimensional Continuous Domains......Page 46
Solving Continuous Constraint Satisfaction Problems......Page 47
Summary......Page 48
Interval Arithmetic......Page 50
Extended Interval Arithmetic......Page 52
Interval Functions......Page 53
Interval Extensions......Page 55
Univariate Interval Newton Method......Page 60
Multivariate Interval Newton Method......Page 65
Summary......Page 66
The Propagation Algorithm......Page 68
Associating Narrowing Functions to Constraints......Page 71
Constraint Decomposition Method......Page 73
Constraint Newton Method......Page 76
Complementary Approaches......Page 81
Summary......Page 83
Local Consistency......Page 84
Higher Order Consistency......Page 89
Summary......Page 92
Global Hull-Consistency......Page 94
The Higher Order Consistency Approach......Page 95
Backtrack Search Approaches......Page 96
The BS0 Algorithm......Page 98
The BS1 Algorithm......Page 99
The BS2 Algorithm......Page 100
The BS3 Algorithm......Page 101
Ordered Search Approaches......Page 103
The OS3 Algorithm......Page 104
The Data Structures......Page 105
The Actions......Page 108
The TSA Algorithm......Page 110
Summary......Page 111
Local Search......Page 112
The Line Search Approach......Page 113
Obtaining a Multidimensional Vector - the Newton-Raphson Method......Page 114
Obtaining a New Point......Page 119
Alternative Local Search Approaches......Page 124
Integration of Local Search with Global Hull-Consistency Algorithms......Page 125
Summary......Page 127
A simple example......Page 128
The Census Problem......Page 129
Protein Structure......Page 132
Local Search......Page 133
Summary......Page 134
Interval Constraints for Differential Equations......Page 136
Ordinary Differential Equations......Page 138
Numerical Approaches......Page 140
Taylor Series Methods......Page 141
Errors and Step Control......Page 142
Interval Approaches......Page 143
Interval Taylor Series Methods......Page 144
Validation and Enclosure of Solutions Between two Discrete Points......Page 146
Computation of a Tight Enclosure of Solutions at a Discrete Point......Page 147
Older\'s Constraint Approach......Page 148
Hickey\'s Constraint Approach......Page 150
Jansen, Deville and Van Hentenryck\'s Constraint Approach......Page 151
Summary......Page 153
CSDPs are CSPs......Page 154
Value Restrictions......Page 156
Maximum and Minimum Restrictions......Page 158
Time and Area Restrictions......Page 160
First and Last Value Restrictions......Page 161
Integration of a CSDP within an Extended CCSP......Page 162
Canonical Solutions for Extended CCSPs......Page 164
Local Search for Extended CCSPs......Page 166
Modelling with Extended CCSPs......Page 167
Modelling Parametric ODEs......Page 168
Representing Interval Valued Properties......Page 169
Combining ODE Solution Components......Page 170
Summary......Page 171
The ODE Trajectory......Page 172
Narrowing Functions for Enforcing the ODE Restrictions......Page 174
Value Narrowing Functions......Page 175
Maximum and Minimum Narrowing Functions......Page 176
Time and Area Narrowing Functions......Page 177
First and Last Value Narrowing Functions......Page 179
First and Last Maximum and Minimum Narrowing Functions......Page 181
Narrowing Functions for the Uncertainty of the ODE Trajectory......Page 182
Propagate Narrowing Function......Page 184
Link Narrowing Function......Page 185
Improve Narrowing Functions......Page 187
The Constraint Propagation Algorithm for CSDPs......Page 190
Summary......Page 192
A Differential Model for Diagnosing Diabetes......Page 194
Representing the Model and its Constraints with an Extended CCSP......Page 195
Using the Extended CCSP for Diagnosing Diabetes......Page 196
A Differential Model for Drug Design......Page 197
Representing the Model and its Constraints with an Extended CCSP......Page 199
Using the Extended CCSP for Parameter Tuning......Page 200
The SIR Model of Epidemics......Page 201
Using the Extended CCSP for Predicting the Epidemic Behaviour......Page 202
Summary......Page 204
Interval Constraints for Differential Equations......Page 206
Global Hull-consistency......Page 207
Prototype Implementation: Applications to Biophysical Modelling......Page 208
Conclusions......Page 209
References......Page 212
Appendix A: Interval Analysis Theorems......Page 222
Appendix B: Constraint Propagation Theorems......Page 234