Home

ECL PS Constraint Library Manual

1. mixed integer programming interface to 75 102 most 48 neg 1 12 21 nodbgcomp 63 66 68 normalise_cstrs 3 91 notin 2 fd sets 38 occurrences 3 34 ic symbolic 44 operator declaration 62 options chr 62 or 2 12 21 ordered 2 34 ordered sum 2 34 ordered sum 2 34 poss conflict vars 2 108 potential members 2 amp 127 Precision 26 profile 4 34 propagation 25 109 propagation rule 58 Propia 47 propositional logic 49 57 quadratic programming interface to 75 102 r_conflict 2 106 r_conflict_prop 2 106 r_conflict 2 106 r_conflict_prop 2 106 reals 1 78 87 93 ic 19 reduced cost pruning 2 103 110 repair repair 1 resource allocation rotate 3 50 44 ic_symbolic sameset 2 fd_sets scheduling search 6 ic 23 39 49 118 session_close 1 session commit 1 session rollback 1 118 118 session sql 3 119
2. 24 get solver type 2 get threshold 1 ic 25 global cuts 91 67 guard 58 60 handler declaration ic 11 63 61 ic integers 1 87 ic_cumulative cumulative 4 ic_cumulative profile 4 ic event 1 ic kernel 29 ic_global alldifferent 1 ic_global alldifferent 2 ic_global sorted 2 ic global sorted 3 ic global sumlist 2 34 34 34 28 ic_kernel 30 3l ic stat 1 ic kernel 29 ic stat get 1 ic kernel 29 ic_stat_register_event 2 ic_kernel 29 impose_bounds 3 impose_max 2 impose_min 2 in 2 fd_sets includes 2 fd_sets 38 39 3l 31 31 40 indomain 1 ic 23 infers 47 insetdomain 4 integers 1 eplex ic 19 78 intersection 3 126 34 fd sets 39 intset 3 38 intsets 4 38 is 2 17 108 is_in_domain 2 ic 24 is_in_domain 3 ic 24 is_solver_type 1 24 is_solver_var 1 24 label_with declaration labeling CHR built in 64 labeling 1 ic 23 l
3. 88 9 4 4 Accessing the Solver State 22222 89 9 4 5 Expandable Problem and Constraints 90 9 4 6 Changing Solver State Settings 90 9 4 7 Destroying a Solver State lin 91 9 4 8 Miscellaneous Predicates 91 9 5 Cutpool Constraints lens 91 9 5 1 Solving a Problem with Cutpool Constraints 92 9 5 2 Predicate specific Support 93 9 6 Multiple Solver States nn 94 9 7 External Solver Output and Log EUNT A ey es 95 9 8 Dealing with Large and Other Non standard Numbers 95 9 9 Error Handling Vu ee pe Scene ee ee ee 96 9 10 Solver Behaviour Differences ooo 97 9 11 Solver Specific Information 97 9 11 1 Versions and Licences len 98 9 11 2 Solver Differences 2 2222 2 2 nn 99 9 11 3 Access to External Solver s Control Parameters 101 10 REPAIR Constraint Based Repair 103 10 1 Introduction zo RR moo o St E RR ES 103 10 1 1 Using the Library 103 10 2 Tentative Values on nn 104 10 2 1 Attaching and Retrieving Tentative Values 104 10 2 2 Te nabiltv i e s e emg 2399 Romo m xL 9s 104 10 2 3 The Tentative Assignment 105 10 2 4 Variables with No Tentative Value 105 10 2 5 Unification 2 4 ar aaa eR fe ee en 105 10 2 6 Copying Cm 106 10 3 Repair Constraints a 106 10 4 Conflict Set lle 10
4. 120 session sql prepare 4 session sql prepare query 5 session sql query 4 session sql query 5 119 120 123 122 123 121 121 123 session start 4 118 session transaction 2 118 119 57 set constraints set_range 3 38 set_threshold 1 ic 25 set_threshold 2 ic 25 set_var_type 2 31 set_vars_type 2 31 shift 1 ic_symbolic 44 simpagation rule 58 simplex solver interface to 75 simplification rule 58 sorted 2 34 sorted 3 34 squash 26 27 squash 3 27 ic 23 subset 2 fd sets 39 sumlist 2 34 suspend 3 32 suspension list ga chg 109 symbol domain index 3 symdiff 3 fd sets 39 temporal constraints tenable 104 tent call 3 109 tent get 2 106 tent is 2 109 tent set 2 106 tent call 3 108 tent is 2 108 tentative assignment Tentative Values 104 term constraints 56 terminological constraints tree constraints 57 105 unification eplex var
5. 3 1 Introduction 3 1 1 What IC does 3 1 2 Differences between IC and FD 3 1 3 Differences between IC and RIA 11 11 3 1 4 Notes about interval arithmetic 3 1 5 Intervalarithmetic and IC 0 3 50 Us ge s sa so e bee 9 ee RU Voy 3 1 7 Arithmetic Expressions 3 2 Library Predicates ccs 3 2 1 Domain constraints 2 2 2 2 Cm on 3 2 2 Arithmetic constraints 2 2 2 2m m mn 3 2 3 Reified constraints clle 3 2 4 Miscellaneous constraints 3 2 5 Integer labeling predicates 2 2 2 2 3 2 0 Real domain refinement predicates 3 2 7 Variable query predicates 3 2 8 Propagation threshold predicates 3 2 9 Solving by Interval Propagation 3 2 10 Reducing Ranges Further 3 2 41 Obtaining Solver Statistics 3 3 General Guidelines for the Use of the IC library 3 4 User defined constraints 00004 3 4 1 Modifying variable domains 3 42 The IC attribute l eee 4 Additional Finite Domain Constraints 4 1 V
6. conflict vars 1 52 consistent constraint annotation constraint handling rules constraint solvers constraints disjunctive constraints declaration control sound 57 106 56 49 copy term 2 106 CPLEX 98 cumulative 4 3A 35 cumulative 5 35 cursor all execute 2 cursor all tuples 2 59 62 119 121 121 123 cursor close 1 118 119 cursor N execute 4 cursor N tuples 4 11 9 121 121 123 cursor_next_execute 2 cursor_next_execute 3 cursor_next_tuple 2 cutpool constraints database interface to 119 121 123 123 121 123 91 1134123 dbgcomp 63 66 68 debug_compile flag declarations CHR 61 default range 26 delayed goals 25 delayed goals number 2 109 demon 1 40 difference 3 fd_sets disjoint 2 fd_sets 39 39 63 68 66 disjunctive constraints disjunctive 2 35 domain constraints 125 57 domain spli
7. 44 39 all intersection 2 39 all union 2 39 alldifferent 1 33 23 ic ic symbolic 44 alldifferent 2 33 already_in_heads option already_in_store option and 2 12 21 63 63 annotation 106 approximate generalised propagation 52 arithmetic constraints atmost 3 ic_symbolic boolean constraints 57 branch and bound 23 breal 2 14 check guard bindings option 57 44 66 67 CHR 55 chr 1 63 chr2pl 1 63 chr get constraint 1 chr get constraint 2 chr label with 1 chr labeling 0 chr notrace 0 64 64 chr resolve 1 64 chr trace 0 63 collection to list 2 18 19 column generation Ip add columns 4 Ip add constraints 4 committed choice common solver interface 7 conflict constraint 90 57 10 106 63 conflict constraints conflict variables conflict constraints 2 conflict constraints 2 107 107 106 108 107
8. the predicate can be used as a constraint X 1 10 notin3to6 X infers most X X 1 2 7 10 Yes 0 00s cpu In this example there are no delayed constraints since all valuations for X satisfying the above conditions are solutions Propia detects this and therefore avoids delaying the constraint again In scheduling applications it is necessary to constrain two tasks that require the same machine not to be performed at the same time Specifically one must end before the other begins or vice versa If one task starting at time ST1 has duration D1 and another task starting at time S72 has duration D2 the above disjunctive constraint is expressed as follows noclash ST1 D1 ST2 D2 ST1 gt ST2 D2 noclash ST1 D1 ST2 D2 ST2 gt ST1 D1 Generalised Propagation on this constraint allows useful information to be extracted even before it is decided in which order the tasks should be run lib ic ST1 ST2 1 10 noclash ST1 5 ST2 7 infers most STi ST1 1 5 8 4013 ST2 ST2 1 3 6 10 There is 1 delayed goal Yes 0 00s cpu The values 6 and 7 are removed from the domain of ST1 because the goal noclash ST1 5 ST2 7 cannot be satisfied if ST1 is either 6 or 7 For example if ST1 is 6 then either 6 gt ST2 7 to satisfy the first clause defining noclash or else ST2 gt 6 4 5 to satisfy the second clause There is no value for ST2in 1 10 that makes either i
9. X gt 5 X X 5 0 Delayed goals X 5 0 i L 0Inf gt 5 ic Yes 0 00s cpu 1 0Inf Note that the lower bound of X is still five despite the fact that X has been constrained to be strictly greater than five Further note the presence of a delayed goal which will fail should X be constrained to be exactly five eclipse 5 integers X X gt 5 X X 6 1 0Inf Yes 0 00s cpu In this example since X is known to be integral the lower bound of X can be set to 6 as there are no integers between five and six 3 4 User defined constraints The library ic_kernel provides a number of facilities useful for implementing IC constraints or otherwise extending the facilities provided by the standard IC library While the ic_kernel library exposes the structure of the IC attribute to the programmer see below accessing it directly is strongly discouraged if for no other reason the internals of IC may continue to evolve For accessing information about a variable and its domain use the predicates described earlier in section 3 2 7 Variable query predicates For modifying a variable it is particularly important to go through the access predicates in order 30 to make sure that the internal state remains consistent that appropriate constraints are scheduled for execution as a result of the change etc The predicates available for modifying a variable are discussed in the n
10. repair ConflictSet no more conflicts true 4 a solution is found 2s The predicate is recursive and terminates when there are no more variables or constraints in conflict Repair search often finishes without labeling all variables a solution has been found and a set of tenable variables are still uninstantiated Thus even 110 after the search is finished Repair library delayed goals used for monitoring constraints will be present in anticipation of further changes To remove them one has to ground these tenable variables to their tentative values Note that the example code never changes tentative values This has the advantage that this is still a complete monotonic and cycle free algorithm However it is not very realistic when the problem is difficult and the solution is not close enough to the initial tentative assignment In that case one would like to exploit the observation that it is often possible to repair some conflict constraints by changing tentative values During search one would update the tentative values to be as near as pssible to what one wants while maintaining consistency If the search leads to a failure these changes are of course undone 111 112 Chapter 11 DBI ECL PS SQL Database Interface 11 1 Introduction The ECL PS SQL database interface is a low level interface to the SQL language As far as possible it has been attempted to give the full power of the SQL interface to the
11. 2 22 eee 9 2 1 Linear Constraints 22 22 nn 9 2 2 Linear Expressions 2 2 2 2 llle 9 2 3 _Bounds s senma ey ea gx wesen ii 43 43 44 44 45 45 AT 4T 48 52 55 95 56 56 58 58 59 61 61 62 62 63 64 66 66 66 68 68 69 TO 70 71 71 74 74 9 24 Integralityl onen 78 9 2 5 Solving Simple Eplex Problems 78 92 6 Exaxupl S ss kee a ome a ne 79 9 3 Advanced Use of Eplex Instances 80 9 3 1 Obtaining Solver State Information 80 9 3 2 Creating Eplex Instances Dynamically 82 9 3 3 Interface for CLP Integration Solver Demons 82 9 3 4 Encapsulated Modification of the Problem Probing 85 9 3 5 Destroying the Solver State 2 2 2 2 mn nn 86 9 3 6 Eplex Instance Interface Example definition of optimize 2 9 4 Low Level Solver Interface 22 222 nn 86 9 4 1 Setting Up a Solver State 2 2 2 22 nenne 87 9 4 2 Adding Constraints to a Solver State 88 9 4 3 Running a Solver State Explicitly
12. 39 Seti Set2 intersection Seti Set2 union Seti Set2 4 difference When such set expressions occur they are translated into auxiliary inter section 3 union 3 and difference 3 constraints respectively 5 5 Search Support The insetdomain 4 predicate can be used to enumerate all ground instan tiations of a set variable much like indomain 1 in the finite domain case insetdomain Set CardSel ElemSel Order Instantiate Set to a possible value 5 6 Example The following program computes so called Steiner triplets These are triplets of numbers from 1 to N such that any two triplets have at most one element in common lib fd sets lib fd steiner N Sets NB is N N 1 6 compute number of triplets intsets Sets NB 1 N 4 initialise the set variables foreach S Sets do S 3 constrain their cardinality Js fromto Sets S1lS8s Ss do foreach S2 Ss param S1 do S1 N S2 C constrain the cardinality C lt 1 of pairwise intersections label sets Sets 4 search label sets label sets S Ss insetdomain S _ _ _ label_sets Ss Here is an example of running this program 40 steiner 9 X X 1 2 3 1 4 5 1 6 7 1 8 9 2 545 76 5 25 5281 15 5 9 Bl 3 5 7 3 6 8 4 7 8 5 6 9 More 41 42 Chapter 6 The Symbolic Domain Library The ic_symbolic library is a solver for const
13. Handle optimizer param ParamName Value Set a control parameter for the external solver for the problem represented by Handle If the external solver does not have problem specific parameters this will raise an unimplemented functionality exception The parameters are as in lp get 3 EplexInstance eplex_set optimizer_param ParamName Value Like Ip set 3 but set a control parameter for the external solver associated with the specified eplex instance 101 Ip set optimizer param 4 ParamName 4 Value Set a control parameter for the external solver for the problem globally If the external solver does not have global parameters this will set the global default for the parameter The parameters are as in lp get 3 Ip get optimizer Value and lp get optimizer version Value Retrieve the name currently cplex xpress or osi and version of the external optimizer This can be used to write portable code even when using solver specific settings begin verbatim lp_get optimizer lp_set Handler lp_get optimizer lp_set Handler lp_get optimizer xpress gt optimize_param maxnode 100 cplex gt optimize_param node_limit 100 osi gt lp get optimizer version clpcbc gt lp set Handler optimize param node limit 100 true 102 Chapter 10 REPAIR Constraint Based Repair 10 1 Introduction The Repair library provides two simple fundamental features
14. Head2 lt gt Body is equivalent to the simplification rule Headl Head2 lt gt Body Head1 However the simpagation rule is more compact to write more efficient to execute and has better termination behavior than the corresponding simplification rule 58 Example Assume you want to write a constraint handler for minimum and maximum based on inequality constraints The complete code can be found in the handler file minmax chr handler minmax constraints leq 2 neq 2 minimum 3 maximum 3 built in X leq Y lt gt nonground X nonground Y X lt Y reflexivity X leq X lt gt true antisymmetry X leq Y Y leq X lt gt X Y transitivity X leq Y Y leq Z gt X Y Y Z X Z X leq Z built in X neq Y lt gt X Y true irreflexivity X neq X lt gt fail subsumption X lss Y X neq Y lt gt true simplification X neq Y X leq Y lt gt X lss Y min eq minimum X X Y lt gt X Y min eq minimum X Y X lt gt X leq Y min eq minimum X Y Y lt gt Y leq X propagation minimum X Y Z gt Z leq X Z leq Y Procedurally a rule can fire only if its guard succeeds A firing simplifi cation rule replaces the head constraints by the body constraints a firing propagation rule keeps the head constraints and adds the body A firing simpagation rule keeps the first head and replaces the second head by the body See the next subs
15. lo cate 2 is equivalent to calling locate 3 with log as the third argu ment locate LocateVars SquashVars Precision LinLog As per locate 3 but also applies the squashing algorithm to SquashVars both before splitting commences and then again after each split squash Vars Precision LinLog Refine the intervals of Vars by the squash ing algorithm 23 3 2 7 Variable query predicates These predicates allow one to retrieve various properties of an IC variable and usually work on ground numbers as well is solver var Var Succeeds if an only if Var is an IC variable is solver type Term Succeeds if an only if Term is an IC variable or a number get solver type Var Type Returns whether Var is an integer variable or a real variable get bounds Var Lo Hi Returns the current bounds of Var get min Var Lo Returns the current lower bound of Var get max Var Hi Returns the current upper bound of Var get float bounds Var Lo Hi Returns the current bounds of Var as floats get integer bounds Var Lo Hi Returns the current bounds of the in teger variable Var infinite bounds are returned as floats Constrains Var to be integral if it isn t already get finite integer bounds Var Lo Hi Returns the current finite bounds of the integer variable Var Constrains Var to be finite and integral if it isn t already get domain size Var Size Returns the number of elements in the IC domain for Var Current
16. For example one can retrieve a date as either a string or an atom What type combinations are supported will depend on the underlying database It is possible to write SQL queries with parameters SQL placeholders so that one can use the same query several times with different values This feature together with the availability of any number of cursors can be used to write complex queries not expressible with a singe SQL statement If the database has a generic binary format such as Binary Long Object BLOB fields one can store and retrieve arbitrary terms in them auto matically using the interface To exchange ECL PS terms with other ap plications via the database the terms can be converted to EXDR data in terchange format see the Embedding and Interfacing chapter for details before storing them in the database It is possible to open several sessions to different databases simultaneously Transactions apply to one session only though The code is written so that it will be relatively easy to extend it to interface to different kinds of databases The currently supported database is MySQL 11 2 Using the SQL database interface The SQL database interface is contained in the dbi library eclipse 1 lib dbi yes Your environment must be set up so that you can connect to a database supported by lib dbi Normally a database administrator will have written a script to do this automatically MySQL specific note on some platform
17. When the constraint goes into conflict it will show up in the conflict set denoted by ConflictSet from where it can be retrieved using conflict constraints 2 Constraint can be any goal that works logically it should be useable as a ground check and work on any instantiation pat tern Typically it will be a constraint from some solver library ConflictSet can be a user defined name an atom or it can be a variable in which case the system returns a conflict set handle that can later be passed to con flict constraints 2 Example constraint with annotation fd Capacity gt sum Weights r conflict cap cstr Note that using different conflict sets for different groups of constraints will often make the search algorithm easier and more efficient A sec ond allowed form of the r conflict 2 annotation is Constraint r conflict ConflictSet ConflictData If this is used ConflictData will appear in the conflict set instead of the Constraint itself This feature can be used to pass additional information to the search algorithm Constraint r conflict prop ConflictSet In addition to what r conflict 2 does the r conflict prop 2 annotation causes the Constraint to be activated as a goal as soon as it goes into conflict for the first time If Constraint is a finite domain constraint for 106 example this means that domain based propagation on Constraint will start at that point in time Note that if you want constraint propagation from th
18. by the particular solver Note that some further restrictions may apply for a particular solver For example the eplex solver can only handle linear expressions Refer to the documentation for each individual solver to see what restrictions might apply Note that the last line labelled arith is not really a constraint solver but represents just the standard arithmetic tests which require all variables to be instantiated This behaviour is provided by the automatically imported module eclipse language It can be somewhat confusing that these standard arithmetic tests have the same names as the corresponding constraints One one hand they have the same declarative meaning On the other hand they are not really inter changeable because they can only be used as tests not as active constraints The following synonyms are therefore provided to make the distinction vis ible where needed and to reduce the need for module qualification 2 2 2 2 gt 2 gt 2 lt 2 lt 2 gt 2 gt 2 lt 2 lt 2 2 3 Using the constraints To use the constraints ECL PS needs to know which solver to pass a par ticular constraint to The easiest method for doing this is to module qualify the constraint For example ic A gt B passes the constraint A gt B to the ic solver The solver must be loaded first e g via lib 1 before any constraint can be passed to it A constraint c
19. for example non binary string types such as VARCHAR does not accept generic binary strings and SQL data and time types must be in the correct syntax consult the database manual for the syntax for these types Integers and Floats are converted to C integers and doubles which are then converted to the specified SQL numeric types The numbers are passed to the database s C API at the maximum precision and size supported by the database s API Note that the exact behaviour of passing a number that is too large for the corresponding SQL numeric type specified in the SQL statement query depends on the database General terms are converted to ECL PS s internal dbformat a flat bi nary representation of the term and then to an appropriate SQL bi nary type This allows ECL PS to store and retrieve general terms but if it is required to exchange Prolog terms with external sources via 116 the database then the term should be first converted to EXDR for mat and the EXDR string can then be passed to the database Note that EXDR can only represent a subset of terms see the Embedding and Interfacing manual for details 11 3 2 Specifying buffer sizes in templates Prolog terms strings and atoms can have variable sizes but when they are passed into and out of the database they pass through fixed size buffers for reasons of efficiency In the case of fetching data from fixed size database fields the size of these buffers is by de
20. suspension list which is attached to every repair variable The programmer has therefore all the tools to write specialised efficient versions of tent call 3 Follow the following pattern my invariant In Out In tent get TentIn compute TentOut from TentIn suspend my invariant In Out Susp 3 In gt ga_chg Out tent set TentOut This can be made more efficient by using a demon demon 1 10 6 Examples More examples of repair library use in particular in the area of local search can be found in the Tutorial on Search Methods 10 6 1 Interaction with Propagation In the following example we set up three constraints as both repair and fd constraints using the r conflict prop annotation and install an ini tial tentative assignment using tent set We then observe the result by retrieving the conflict sets eclipse 1 lib repair lib fd libraries needed here yes eclipse 2 fd X Y Z 1 3 the problem variables fd Y X r conflict prop confset state the constraints fd Y Z r conflict prop confset fd Y 3 r conflict prop confset of X Y Z tent_set 1 2 3 set initial assignment X Y Z tent get NewX NewY NewZ get repaired solution conflict constraints confset Cs 4 see the conflicts conflict vars Vs X X fd 1 3 repair 1 Y 3 Z Z fd 1 2 repair 3 NewX 1 NewY 3 NewZ 3 109 Cs Vs 3 Zifd 1 2 repair 3 Z fd 1 2 r
21. 1 delayed goal Yes 0 00s cpu In the second example by contrast infers unique yields the same result as infers most p X X infers unique X 3 Yes 0 00s cpu The next example shows that unique can even capture nonground answers p 2 X infers unique X Z Yes 0 00s cpu The next approximation we shall describe is even weaker it tests if there is an answer and if not it fails If there is an answer it checks to see if the constraint is already true p 1 X infers consistent X X There is 1 delayed goal Yes 0 00s cpu p 1 a infers consistent Yes 0 00s cpu p 1 X infers consistent X b No 0 00s cpu 53 The strongest language infers most extracts any information possible from the loaded constraint solvers The solvers currently handled by Propia are unification which is the built in solver of Prolog ic and ic_symbolic The IC library is loaded by 1ib ic and the symbolic library by 1ib ic symbolic These libraries are described elsewhere If both libraries are loaded then infers most extracts information from unification IC domains and sym bolic domains For example p X 1 X gt 0 X lt 10 p X 1 X 12 with the above program p X Y infers most X f 338 0 0 12 09 Y Y 1 2 There is 1 delayed goal Yes 0 00s cpu The approximation infers ic is similar to infers most However while infers most extracts information based on
22. Output and Log The external solver s output can be controlled using lp set SolverChannel Stream Send output from SolverChannel to the ECL PS I O stream Stream lp set SolverChannel Stream Stop sending output from SolverChan nel to the ECL PS I O stream Stream SolverChannelis one of result channel error channel warning channel log channel and Stream is an ECL PS stream identifier e g output or the result of an open 3 operation By default error channel is directed to ECL PS s error stream warning channel to warning output stream while result channel and log channel are suppressed To see the output on these channels do for instance lp set result channel output lp set log channel log output Similarly to create a log file open mylog log write logstream lp set log channel logstrean and to stop logging lp set log channel logstream close logstream 9 8 Dealing with Large and Other Non standard Numbers In many external solvers infinities or very large numbers are not handled directly Instead these solvers define a large floating point number to be infinity However the problem that is sent to the external solver may contain values greater than the solver s notion of infinity This is handled in the following way e If a variable s range extends beyond the solver s infinity the range is rounded down e If some coefficient constant in the problem is outside
23. Replace all operator 3 with op 3 declarations e The other declarations handler constraints option are now han dled as normal Prolog declarations i e they must be preceded with This is to conform with standard Prolog syntax The syntax for naming a rule has been changed because the old method using clashes with the use of in modules The new operator for naming rules is Here is part of the minmax handler in the new syntax handler minmax constraints leq 2 neq 2 minimum 3 maximum 3 op 700 xfx leq built_in X leq Y lt gt nonground X nonground Y X lt Y reflexivity X leq X lt gt true 70 8 9 3 Compiling After loading the extended chr library programs containing CHR code can be compiled directly Thus CHR code can be freely mixed with normal Prolog code in any file In particular a compilation may now compile code from different files in different modules which may all contain CHR codes This was not a problem with the old library because CHR code had to be compile separately In the extended library CHR code can occur anywhere in a particular mod ule and for each module all the CHR code which may reside in different files will all be compiled into one unit handler declarations are ignored by the system they are present for compatibility purposes only with the same constraint store CHR code in different modules are entirely separate and independent from e
24. Restrict the external solver to assign so lution values for the eplex problem within the bounds specified by Lo Hi Passes to the external solver the bounds for the variables in Vars Lo Hi are the lower and upper bounds respectively Note that the bounds are only passed to the external solver if they would nar row the current bounds and failure will occur if the resulting interval is empty Note also that the external solver does not do any bound propagation and will thus not change the bounds on its own The de fault bounds for variables are notionally 1 0Inf 1 0Inf where infinity is actually defined as the solver s notion of infinity 9 2 4 Integrality The difference between using an LP vs an MIP solver is made by declaring integrality to the solver via the integers 1 constraint EplexInstance integers Vars Inform the external solver to treat the variables Vars as integral It does not impose the integer type on Vars However when a typed_solution is retrieved via lp get 3 or Ip var get 3 this will be rounded to the nearest integer Note that unless eplex integers 1 or lp add 3 see section 9 4 2 is invoked any invocation of the eplex external solver via Ip solve 2 Ip probe 3 or lp demon setup 5 will only solve a continuous relax ation even when problem variables have been declared as integers in other solvers e g ic Note that all the above constraints are local to the eplex instance they do no
25. Set BoolArr BoolArr is an array of booleans describing Set 38 5 3 2 Cardinality Set Card Card is the cardinality of the integer set Set 5 3 3 Set Relations difference Set1 Set2 Set3 Set3 is the difference of the integer sets Setl and Set2 Set1 disjoint Set2 The integer sets Set1 and Set2 are disjoint Set1 includes Set2 Set1 includes is a superset of the integer set Set2 intersection Set1 Set2 Set3 Set3 is the intersection of the integer sets Setl and Set2 Set1 sameset Set2 The sets Set1 and Set2 are equal Set1 subset Set2 Setl is a subset of the integer set Set2 symdiff Set1 Set2 Set3 Set3 is the symmetric difference of the in teger sets Setl and Set2 union Set1 Set2 Set3 Set3 is the union of the integer sets Set1 and Set2 5 3 4 N ary Set Relations all disjoint Sets Sets is a list of integers sets which are all disjoint all union 4 Sets SetUnion SetUnion is the union of all the sets in the list Sets all intersection 4 Sets SetIntersection SetIntersection is the inter section of all the sets in the list Sets 5 3 5 Set Weights weight Set Element Weights Weight According to the array of element weights the weight of set Setl is Weight 5 4 Set Expressions In most positions where a set or set variable is expected one can also use a set expression A set expression is composed from ground sets integer lists set variables and the following set operators
26. ac uk cplex 75 0 licence mule icparc ic ac uk xpress 1520 my xpress license 0 The hostname must match the result of get_flag hostname H converted to an atom this is normally the complete Internet domain name rather than just the machine Version is formed from the concatenation of the major and minor version numbers The meaning of LicStr and LicNum depends on the optimiser For an open source solver both LicStr and LicNum are unused as no license is required For CPLEX with normal licenses they are unused the environment variable ILOG_LICENSE_FILE should be set to the CPLEX license file access ilm as usual J For XPRESS MP LicStr is a string specifying the directory where licence file is located overrides value of XPRESS environment variable LicNum is unused If a machine has more than one licence and lib eplex is called the first one listed in eplex lic info ecl will be used Note that it is not sufficient that you have a valid license and solver libraries for a particular version of the solver That solver version must also be supported by the release of ECL PS you are using 98 9 11 2 Solver Differences While the eplex library allows the user to write code in a solver independent way there are differences between the solvers that the user should be aware of e Different solvers may support different features In particular solvers may support different methods of solvin
27. allows a solver state to be set up without the overhead of an eplex in stance The solver state will not collect any constraints automatically when it is invoked instead the constraints must be added explicitly via the handle using 1p add constraints 3 By default the external solver is invoked once after set up by 1p demon setup if any TriggerModes is specified Otherwise the solver is not invoked and the predicate returns after set up lp_setup NormConstraints Objective ListOfOptions Handle This is an even lower level primitive setting up a solver state without any automatic triggering It creates a new solver state for the set of constraints NormConstraints see below for how to obtain a set of normalised con straints Apart from the explicitly listed constraints the variable s ranges will be taken into account as the variable bounds for the simplex algorithm Undeclared variables are implicitly declared as reals 1 However when variables have been declared integers in other solvers e g using ic integers 1 that is not taken into account by the solver by de fault This means that the solver will only work on the relaxed problem ie ignoring the integrality constraints unless specified otherwise in the options Objective is either min Expr or max Expr where Expr is a lin ear or quadratic expression ListOfOptions is a list of solver options the same as for Ip demon setup 5 and eplex_solver_setup 4 except for
28. an interface to external Database Management Systems allowing users to add and retrieve data from the database within an ECL PS program Any ECL PS user who has implemented a constraint solver is welcome to send the code to the ECL PS team so that it can be added to the available libraries Comments and suggestions on the existing libraries are also welcome Chapter 2 Common Solver Interface 2 1 Introduction ECL PS now provides a common syntax for the main arithmetic constraints provided by different constraint solvers The basic idea is that the name and syntax of the constraint determines the declarative meaning while the operational semantics the algorithmic constraint behaviour is determined by the module which implements the constraint l his principle simplifies the development of applications that use hybrid solution methods Constraints can be passed easily to different even multiple solvers 2 2 Common constraints The constraints can be divided into the following groups e the numeric type constraints reals 1 and integers 1 Note that in this context integers are considered a subset of the reals e the range constraints 2 and 2 which give upper and lower bounds to their variables In addition 2 and can also imply integrality e arithmetic equality inequality and disequality over the mathematical real numbers e g gt gt and their symnonyms gt gt Note th
29. an option off to improve the efficiency of the handler at the cost of safety Options are 62 e check guard bindings When executing a guard it is checked that no global variables variables of the rule heads are touched see sub section on how CHRs work If the option is on guards involving cut if then else or negation may not work correctly if a global variable has been touched before If switched off guard checking may be signifi cantly faster but only safe if the user makes sure that global variables are not touched To ensure that the variables are sufficiently bound tests like nonvar 1 or delays can be added to the predicates used in the guards e already in store Before adding a user defined constraint to the constraint store it is checked if there is an identical one already in the store If there is the new constraint needs not to be added The han dling of the duplicate constraint is avoided This option can be set to off because the checking may be too expensive if duplicate constraints rarely occur Specific duplicate constraints can still be removed by a simpagation rule of the form Constraint Constraint lt gt true e already_in_heads In two headed simplification rules the intention is often to simplify the two head constraints into a stronger version of one of the constraints However a straightforward encoding of the rule may include the case where the new constraint is identical to the corresponding head
30. are N tasks each starting at a certain start time having a certain duration and consuming a certain constant amount of resource then the sum of resource usage of all the tasks does not exceed ResourceLimit at any time This constraint can propagate more information than the implementation in library cumulative cumulative StartTimes Durations Resources Area ResourceLimit In this variant an area the product of duration and resource us age of a task can be specified e g if duration or resource usage are not known in advance The edge finder algorithm can make use of this information to derive bound updates 35 36 Chapter 5 The Integer Sets Library The fd sets library is a solver for constraints over the domain of finite sets of integers Unlike conjunto it cannot deal with sets elements that are not integers On the other hand fd sets is usually faster for integer sets than conjunto 5 1 Ground Integer Sets Ground integer sets are simply sorted duplicate free lists of integers e g Set fThree 1 3 7 EmptySet Lists which contain non integers are unsorted or contain duplicates are not sets in the sense of this library 5 2 Set Variables 5 2 1 Declaring Set variables are variables which can eventually take a ground integer set as their value They are characterized by a lower bound the set of elements that are definitely in the set and an upper bound the set of elements that may be
31. e chr resolve Constraint uses the ECL PS clauses to solve a con straint used for built in labeling e chr get constraint Constraint gets a constraint unifying with Con straint from the constraint store and removes it gets another con straint on backtracking e chr get constraint Variable Constraint is the same as chr get constraint 1 except that the constraint constrains the variable Variable 8 6 Labeling In a constraint logic program constraint handling is interleaved with making choices Typically without making choices constraint problems cannot be solved completely Labeling is a controlled way to make choices Usually a labeling predicate is called at the end of the program which chooses values for the variables constrained in the program We will understand labeling in the most general sense as a procedure introducing arbitrary choices additional constraints on constrained variables in a systematic way The CHR run time system provides built in labeling for user defined con straints The idea is to write clauses for user defined constraints that are used for labeling the variables in the constraint These clauses are not used during constraint handling but only during built in labeling Therefore the Head of a clause may be a user defined Constraint The label with declaration restricts the use of the clauses for built in labeling see subsec tion on declarations There can be several label_wi
32. functions when used in IC should be deterministic User defined constraints functions which leave choice points may not behave as expected 15 Variables appearing in arithmetic IC constraints at compile time are as sumed to be IC variables unless they are wrapped in an eval 1 term See section 3 1 7 for an more detailed explanation of usage The following arithmetic expression can be used inside the constraints X Variables If X is not yet a interval variable it is turned into one by implicitly constraining it to be a real variable 123 Integer constants They are assumed to be exact and are used as is 0 1 Floating point constants These are assumed to be exact and are con verted to a zero width bounded reals pi e Intervals enclosing the constants 7 and e respectively inf Floating point infinity Expr Identity Expr Sign change Expr Expr or Expr The result is an interval enclosing both If however either bound is infeasible then the result is the bound that is feasible If neither bound is feasible the goal fails abs Expr The absolute value of Expr E1 E2 Addition E1 E2 Subtraction E1 E2 Multiplication E1 E2 Division E1 E2 Exponentiation min E1 E2 Minimum max E1 E2 Maximum sqr Expr Square Logically equivalent to Expr Expr but with better op erational behaviour sqrt Expr Square root always positive exp Expr Same as e Expr In Expr Natural logarithm the reverse
33. in a generic constraint programming library The behaviour of these constraints is to prune the finite domains of their vari ables in just the same way as the standard constraints Therefore ECL PS offers several further libraries which implement more constraints using the ic library 1 2 8 Global Constraints 2c global One such library is ic global It supports a variety of constraints each of which takes as an argument a list of finite domain variables of unspecified length Such constraints are called global constraints 2 Examples of such constraints available from the ic global library are alldifferent 1 maxlist 2 occurrences 3 and sorted 2 1 2 4 Scheduling Constraints There are several ECL PS libraries implementing global constraints for scheduling applications The constraints have the same semantics but differ ent propagation The constraints take a list of tasks start times durations and resource needs and a maximum resource level They reduce the finite domains of the task start times by reasoning on resource bottlenecks 13 Three ECL PS libraries implementing scheduling constraints are cumula tive edge finder and edge finder3 1 3 Sets ECL PS offers constraint solving over the domain of finite sets of integers The ic_sets library works together with the ic library to reason about sets and set cardinality 10 3 There is also an older implementation the conjunto library
34. in the constraint store This can have an effect on execution For example in the finite domain example in the old chr directory domain chr there is the following rule X 1t Y X AIL lt gt nonground Y remove higher Y A L L1 remove Y L1 L2 X L2 T1 Unfortunately this rule is not sufficiently specified in the extended CHR and can lead to looping under certain circumstances The two remove predicate in the guard removes elements from the domain but if no elements are removed because X 1t Y is redundant e g X 1t 5 with X 1 2 then in the old CHR execution the body goal the constraint X L2 would not be actually executed because the older constraint in the head the one that matched X A L has not yet been removed when the new constraint is imposed With the extended CHR the old constraint is removed after the guard so the X L2 is executed and this can lead to looping The rule should thus be written as X 1t Y X AIL lt gt nonground Y remove higher Y A L L1 remove Y L1 L2 L2N A L X L2 Executing Propagation and simpagation rules Consider the following propagation rule p X q Y gt Body p X The execution of this rule started by calling p X will try to match all q Y in the constraint store and thus it can be satisfied with Body executed multiple number of times with different q Y Body for a particular q Y will be executed first before
35. more than two heads have not yet been added Simplification and simpagation rules with more than two heads are currently supported e The compiler does not try to reorder the CHR any more Instead they are ordered in the way they are written by the user 69 e label with is no longer supported It can be replaced with user de fined labelling e The operational semantics of rules have been clarified e The CHR are run at the same priority before and after suspensions Priorities can be specified for CHR constraints e There is no special support for debugging yet The CHR code would be seen by the debugger as the transformed Prolog code that is generated by the compiler 8 9 1 Invoking the extended CHR library The extended library is invoked by lib ech Given that it is now integrated into the compiler It can be invoked from a file that contains CHR code as lib ech as long as this occurs before the CHR code 8 9 2 Syntactic Differences As programs containing CHRs are no longer compiled by a separate process the chr extension is no longer implicitly supported Files with the chr extension can still be compiled by explicitly specifying the extension in the compile command as in file chr Associated with this change there are some changes to the declarations of the chr format e operator 3 does not exist It is not needed because the standard Pro log op 3 declaration can now handle all operator declarations
36. of the exp function sin Expr Sine 16 cos Expr Cosine atan Expr Arcus tangens Returns value between pi 2 and pi 2 rsqr Expr Reverse of the sqr function Equivalent to sqrt Expr rpow E1 E2 Reverse of exponentiation i e finds X in E1 X E2 sub Expr A subinterval of Expr sum ExprList Sum of a list of expressions min ExprList Minimum of a list of expressions max ExprList Maximum of a list of expressions and Reified constraint conjunction e g B X gt 3 and X 8 or Reified constraint disjunction e g B X gt 3 or X lt 8 gt Reified constraint implication e g B X gt 3 gt X 8 neg Reified constraint negation e g B neg X gt 3 gt gt lt lt gt gt lt lt gt gt FS lt and or gt neg Any arithmetic or logical constraint that can be issued as a goal may also appear within an expression Within the expression context the constraint evaluates to its reified truth value If the constraint is entailed by the state of the constraint store then the sub expression evaluates to 1 If it is dis entailed by the state of the constraint store then it evaluates to O If its reified status is unknown then it evaluates to an integral variable O 1 Note The simple cases e g Bool X gt 5 are equivalent to di rectly calling the reified forms of the basic constraints e g t X 5 Bool foo Argi A
37. one of the atoms lt lt gt gt ordered_sum List Sum The list elements are ordered and their sum is Sum occurrences 4 Value List N The value Value occurs in List N times Operationally N gets up dated to reflect the number of possible occurrences in the List List elements may get instantiated to Value or Value may be removed from their domain if required by N sorted List Sorted Sorted is a sorted permutation of List sorted List Sorted Positions Sorted is a sorted permutation of List and Positions is a list whose elements indicating the position of each unsorted list element within the sorted list sumlist List Sum The sum of the list elements is Sum This constraint is more efficient than a general IC sum constraint if the list is long and Sum is not constrained frequently 4 2 Cumulative Constraint and Resource Profiles The library cumulative implements the cumulative scheduling constraint It is based on the IC library and is loaded using one of use_module library ic_cumulative lib ic_cumulative cumulative Start Times Durations Resources ResourceLimit A cumulative scheduling constraint Start Times Durations and Re sources are lists of equal length N of integer variables or integers Re sourceLimit is an integer The declarative meaning is If there are N tasks each starting at a certain start time having a certain duration and consuming a certain c
38. other constraints solvers or even with other CHR rules as a woken CHR executes at much higher priority than the initial run With the current ech execution the rules are executed at the same priority before and after suspension for the same active constraint The default priority is set at 9 so that it is very likely to be lower than the priority used in other constraint solvers The user is now allowed to alter the priority of specific ECH con straints to allow the user more control so that for example a labelling rule can run at a lower priority than the other constraints 73 8 9 5 Options and Built In Predicates The check guard bindings and already in store options from the old chr library are supported Note that the extended compiler can actually detect some cases where guard bindings cannot constrain any global variables for example var 1 and will in such cases no check guard bindings New options intended to control the way the compiler tries to optimise code are introduced These are intended for the developers of the compiler and will not be discussed in detail here The only currently supported option in this category is single symmetric simpagation Another new option default chr priority allows the default priority to be changed e g option default chr priority 6 changes the default priority to 6 so the compiler would generate new CHR code which defaults to this priority unless overridden in the constra
39. set 7 X X fd 1 5 repair 7 produces an untenable variable Note that unlike logical assignments the tentative value can be changed eclipse 3 fd X 1 5 X tent_set 7 X tent_set 3 X X fd 1 5 repair 3 104 tenable Var Succeeds if the given variable is tenable This predicate is the link between repair and any underlying solver that maintains a domain for a variable 10 2 3 The Tentative Assignment The notion of a tentative assignment is the means of integration with the consistency methods of ECL PS The tentative assignment is used for iden tifying whether a repair constraint is being violated The tentative assignment is a function of the groundness and tenability of problem variables according to the following table Variable Groundness Variable Tenability Value in Tentative Assignment Ground Tenable Ground Value Ground Not Tenable Ground Value Not Ground Tenable Tentative Value Not Ground Not Tenable Undefined A repair constraint is violated under two conditions e The tentative assignment is undefined for any of its variables e The constraint fails under the tentative assignment 10 2 4 Variables with No Tentative Value It has been noted above that variables with no associated tentative value are considered to be tenable Since no single value has been selected as a tentative value the Repair library checks constraints for consistency with respect
40. the 87 collect from and initial solve options which are specific for the demon solvers 9 4 2 Adding Constraints to a Solver State Constraints can be added directly to a solver state without posting them to an eplex instance This is done by Ip add constraints 4 Handle 4 Constraints NewlIntegers Add new constraints with possibly new variables to the solver state repre sented by Handle The new constraints will be taken into account the next time the solver is run The constraints will be removed on backtracking The constraints are first normalised and simple constraints filtered out as discussed in section 9 2 1 before they are added to the external solver by calling lp add 3 described below Ip add Handle NewNormConstraints NewlIntegers This adds the constraints both linear and integrality to the external solver represented by Handle The linear arithmetic constraints must be nor malised Note that it is possible to add trivial constraints which would be filtered out by the higher level 1p add constraints 3 using this predi cate Integrality constraints on non problem variables are filtered out and a warning given Ip add vars Handle Vars This adds the variables in Vars to the external solver state represented by Handle The variables should not contain variables which are already prob lem variables The variables are given the default bounds of infinity infinity Ip var
41. the arguments correspond to the position of the select list items The example template above might be used for a query like SQL select enum ename esalary ejob from employees where esalary gt 1000 Template emp 1234 some name 1000 0 some job session sql query H Template SQL Cursor cursor next tuple Cursor Tuple Tuple is now somthing like emp 1001 E G SMITH 1499 08 editor If a structure or list appears in one of the argument positions this stands for a general term to be stored or retrieved in external database format This way one is not limited to atomic types which have natural mappings to database types 11 3 1 Conversion between ECL PS and database types Data is passed from ECL PS into the database via placeholders in prepared SQL statements and passed from the database to ECL PS via the results tuples returned by executing SQL queries The interface takes care of the conversion of data to from ECL PS types to the external C API types and the database then converts these to from the internal types of the database as determined by the SQL statement used The exact internal database types and the exact conversion rules between the C type and the database type is dependent on the database s API but in general the following should hold for ECL PS types Strings and atoms are converted to C char type This should be used for non numeric data Restrictions may apply depending on the SQL datatype
42. then adding the interger information back This is be cause the CPLEX API does not provide access to the root node of the MIP solve CPLEX have only global parameters OSI The features provided by eplex OSI is determined by the actual solver s used via OSI and to a lesser extent by what the OSI API supports The OSI API is mainly designed to support solving of linear and to a lesser extent 99 MILP problems However for specific solvers in particular the CLP CBC combination eplex directly access the solvers own API to provide some functionality not supportable via OSI Note however the OSI API is con stantly evolving and improving so some of the features may be directly supported via OSI in the future Features not supported by OSI e changing of solving method it does support specifying if the problem should be solved as a primal or dual e problems with a quadratic objective e time outs from solving a problem e obtaining detailed information about the MIP solving process espe cially when the MIP search was not complete such as the best MIP objective bound e determining if an aborted solve have a suboptimal solution e use of Special Order Set SOS osi clpcbc Supports primal and dual simplex methods for solving linear and MILP problems It also supports time outs and is better at determining the state of an aborted problem than using OSI on its own For the MIP related functionality the MIP solver CBC is ac
43. to the domain of that variable A temporary variable with identical domains is substituted in the constraint check 10 2 5 Unification If two variables with distinct tentative values are unified only one is kept for the unified variable Preference is given to a tentative value that would result in a tenable unified variable If you wish to write your own solver and have it cooperate with repair you have to define a test_unify handler 105 10 2 6 Copying If a variable with a repair attribute is copied using copy_term 2 or similar the repair attribute is stripped If you wish the copy to have the same tenta tive value as the original you will need to call tent get 2 and tent set 2 yourself 10 3 Repair Constraints Once a constraint has been declared to be a repair constraint it is monitored for violation Whether a repair constraint is considered to be violated de pends on the states of its variables A temporary assignment of the variables is used for checking constraints This assignment is called the tentative as signment and is described above A constraint which is violated in this way is called a conflict constraint Normal constraints are turned into repair constraints by giving them one of the following annotations Constraint r conflict ConflictSet This is the simplest form of annotation r conflict 2 makes a constraint known to the repair library i e it will initiate monitoring of Constraint for conflicts
44. transaction Transactions are local to one session so there is no way to safely make an update relating to several sessions recorded transfer Session Date Amount FromAccount ToAccount session transaction Session transfer Session Amount FromAccount ToAccount check overdraft limit FromAccount record_transfer Date Amount FromAccount ToAccount transfer Session Amount FromAccount ToAccount Session transaction Session transfer Session Amount FromAccount ToAccount In the above example we can see two nested transactions One simple bank transfer that is not recorded and an outer transaction recording the occur rence of the transfer and checking the balance Since a nested transaction is simply a call of its goal with no partial rollbacks care has to be taken not to redo transactions on failure unless one is sure one is at an outer transaction 11 4 2 Database Updates For database updates lib dbi provides predicates to execute SQL state ments on the database without returning results session sql 3 executes an SQL statement directly session sql prepare 4 is used to prepare SQL statements returning a cursor to the prepared statement which can then be executed multiple times with different placeholder values using either cur sor next execute 2 or cursor all execute 2 or cursor N execute 4 Cursors are automatically closed if the program backtracks or aborts be yond the predicate that created it Alte
45. trying to match the next q Y The execution of Body may however cause the removal of p X In this case no further matching with q Y will be performed Note that there is no commitment with propagation and simpagation rule if the constraint being matched is not removed p X q Y gt lt Body1 gt p X r Y gt lt Body2 gt ge p X Both rules will always be executed The body of a rule is executed as soon as its guard succeeds In the case of propagation rules this means that the other propagation rules for this constraint will not be tried until the body goals have all been executed This is unlike the old CHR where for propagation rules the body is not executed until all the propagation rules have been tried and if more than one 72 propagation rule has fired successful in its guard execution then the most recently fired rule s body is executed first For properly written mutually exclusive propagation rule this should not make a difference modulo the effect of the removal of constraints in the body Execution Priority The priority at which an ECH rule is executed depends on the active con straint i e the constraint that triggered the execution of the rules Normally the ECH rules are executed at the default priority but a different priority can be associated with a constraint when it is declared specifying the pri ority at which the ECH rules will be executed when that constraint is the ac
46. which are the basis for the development of repair algorithms and non monotonic search methods in ECL PS e The maintenance of tentative values for the problem variables These tentative values may together form a partial or even inconsistent ten tative assignment Modifications to or extensions of this assignment may be applied until a correct solution is found e The monitoring of constraints the so called repair constraints for be ing either satisfied or violated under the current tentative assignment Search algorithms can then access the set of constraints that are vio lated at any point in the search and perform repairs by changing the tentative assignment of the problem variables This functionality allows the implementation of classical local search meth ods within a CLP environment see Tutorial on Search Methods However the central aim of the Repair library is to provide a framework for the inte gration of repair based search with the consistency techniques available in ECL PS such as the domains and constraints of the FD library A more detailed description of the theory and methods that are the basis of the Repair library is available 5 10 1 1 Using the Library To use the repair library you need to load it using lib repair 103 Normally you will also want to load one more of the fd ic fd sets or conjunto solvers This is because of the notion of tenability i e whether a tentative
47. which is generally less efficient but implements sets of symbolic elements as well as integer sets 2 1 4 Intervals Besides finite domains ECL PS also offers continuous domains in the form of numeric intervals These are also implemented by the ic library which is an integration of an integer finite domain solver and interval reasoning over continuous intervals It solves equations and inequations between general arithmetic expressions over continuous or integral variables The expressions can include non linear functions such as sin built in constants such as pi Piecewise linear unary functions are also available In addition to constraints ic offers search techniques splitting 20 and squashing 17 for solving problems involving continuous numeric variables 1 5 User Defined Constraints 1 5 1 Generalised Propagation propia The predicate infers takes as one argument any user defined predicate and as a second argument a form of propagation to be applied to that predicate This functionality enables the user to turn any predicate into a constraint 16 The forms of propagation include finite domains and intervals 1 5 2 Constraint Handling Rules The user can also specify predicates using rules with guards 9 They delay until the guard is entailed or disentailed and then execute or terminate accordingly This functionality enables the user to implement constraints in a way that is clearer than directly usi
48. will not propagate all possible in formation for reasons of efficiency It is the purpose of this section to point out ways that may help IC to solve problems more efficiently Typical constraint satisfaction problems are solved by iteratively propagat ing information from basic constraints until no more propagation can take place i e a fixed point has been reached and then reducing the domain of a variable so as to prompt more propagation As with most constraint solvers the propagation provided by the builtin constraints is rarely able to solve large problems completely without the need for some form of search A number of factors affect the speed of the propagation phase 1 The size of the initial domains Smaller domains typically result in propagation reaching a fixed point sooner So give explicit initial do mains to as many variables as possible 29 2 Integer domains allow more propagation n important point to note here is that as in mathematics IC treats integers as a strict subset of the reals and as such the integer domain O 100 contains signif icantly fewer values than the real domain 0 0 100 0 With this in mind IC attempts to infer integrality where possible e g the sum of two integer variables is constrained to be integer however integer domains where applicable should be used in user code The difference becomes apparent when dealing with strict inequalities for example eclipse 4 reals X
49. 0 12 8QL 1 Update cursor next execute Update incbal Deduct FromAccount cursor next execute Update incbal Amount ToAccount In the example a cursor is prepared to modify account balances It is used twice once to deduct an amount and once to add that same amount to another account Note the example uses MySQL s syntax for prepared statement which may differ from other databases Consult your database manual for prepared statement syntax 120 cursor next execute 4 Cursor Tuple Execute the prepared SQL statement represented by Cursor with Tuple supplying the values for any parameter values This call can be executed any number of times on the same cursor cursor all execute Cursor TupleList The SQL statement of Cursor is executed once for each Tuple in TupleList This could be defined as cursor all execute Cursor cursor all execute Cursor Tuple Tuples cursor next execute Cursor Tuple cursor all execute Cursor Tuples cursor N execute Cursor Executed TupleList Rest TupleList Some databases supports the execution of multiple tuples of parameter val ues at once doing this more efficiently than executing each tuple of param eter values one by one This predicate is provided to support this Note that for databases that does not support execution of multiple tu ples this predicate is implemented by executing the Tuples one by one as in cursor next execute 2 and the
50. 7 86 10 5 Invariants s poiss eom 3 LR oom 10 6 Examples 10 6 1 Interaction with Propagation 10 6 2 Repair Labeling Pn 11 DBI ECL PS SQL Database Interface 11 1 Introduction 11 2 Using the SQL database interface 11 3 Data Templates 11 3 1 Conversion between ECL PS and database types 11 4 1 Sessions 11 4 2 Database Updates 11 4 8 Database Queries 11 4 4 Parametrised Database Queries Index Bibliography 113 113 114 115 116 117 118 118 119 121 123 124 131 vi Chapter 1 Introduction This manual documents the major ECL PS libraries They are enabling tools for the development and delivery of planning and scheduling applica tions Since this is an area of active research and new developments these libraries are subject to technical improvements addition of new features and redesign as part of our ongoing work In this section we shall briefly summarize the constraint solvers that are available as ECL PS libraries No examples are given here each solver has its own documentation with examples for the interested reader 1 1 Suspended Goals suspend The constraint solvers of ECL PS are all implemented using suspended
51. ECL PS Constraint Library Manual Release 5 10 Pascal Brisset Hani El Sakkout Thom Fr hwirth Carmen Gervet Warwick Harvey Micha Meier Stefano Novello Thierry Le Provost Joachim Schimpf Kish Shen Mark Wallace March 31 2008 1990 2006 Cisco Systems Inc Contents Contents 1 Introduction 1 1 Suspended Goals suspend E 1 2 Finite Domains ic Sheds eR dra Uus ede un 1 2 1 Integer Domain 1 2 2 Symbolic Domain ic symbolic 1 2 3 Global Constraints ic global 1 2 4 Scheduling Constraints 1 7 1 External Linear Solvers eplex i 1 7 2 elpgn ior ek ko ks 1 7 3 Piecewise Linear eplez relaa 1 7 4 Probing for Scheduling T 18 Other Libraries 2 Common Solver Interface 2 1 Introduction 2 2 Common constraints 2 3 Usingtheconstraints 2 4 The Solvers 1 3 Sets agus ck de ee ok oP mum be AY 4b ERE a d 1 4 Intervals e oosa au a a a a a E 1 5 User Defined Constraints 1 5 1 Generalised Propagation propia 1 5 2 Constraint Handling Rules 1 6 Repain s s s e a es sk ee he ed Poe oe we ead oj 1 7 Linear Constraints IC A Hybrid Finite Domain Real Number Interval Constraint Solver
52. FD does not e FD supports symbolic domains IC does not use the ic_symbolic li brary e In FD numeric domains are more or less limited to 10000000 10000000 this default domain can be modified but the larger one makes it the more likely one is to run into machine integer overflow problems In IC there is no limit as such and bounds on integer variables can be infinite though variables should not be assigned infinite values However since floating point numbers are used in the underlying im plementation not every integer value is representable Specifically in teger variables and constraints ought to behave as expected until the values being manipulated become large enough that they approach the precision limit of a double precision floating point number 2 or so Beyond this lack of precision may mean that the solver cannot be sure which integer is intended in which case the solver starts behav ing more like an interval solver than a traditional finite domain solver Note however that this precision limit is way beyond what is normally supported by finite domain solvers typically substantially less than 232 Note also that deliberately working with integer variables in this kind of range is not particularly recommended the main intention is for the computation to be safe if it strays up into this region by ensuring no overflow problems e C usually requires that expressions constructed at runtime be wrapped in ev
53. a solver option for the eplex instance EplexInstance eplex write Format File Write out the problem in the the eplex instance s solver state to the file File in format Format The writing is done by the external solver Use the use var name yes option in eplex solver setup 4 so that the writ ten file uses ECL PS variable names Also the write before solve option of eplex solver setup 4 can be used to write out a problem just before it is solved by the external solver this allows problem to be written in places where eplex write 2 cannot be added e g for probing problems EplexInstance eplex read Format File Read a MP problem in the file File in format Format into a solver state and associate the solver with the eplex instance No solver must already be setup for the eplex instance The solver state that is setup can only be triggered explicitly So for the simple MIP example lib eplex eplex instance my instance mip_example2 X Y Cost my_instance X Y gt 3 my_instance X Y 0 my_instance integers X my_instance eplex_solver_setup min X my_instance eplex solve Cost my instance eplex var get X typed solution X my instance eplex var get Y typed solution Y eclipse 2 mip_example2 X Y C lt NNN o o 81 In the example only X is returned as an integer as Y was not explicitly constrained to be an integer Note that if there are multiple epl
54. ach other In order to allow CHR code to occur anywhere inside a module and also because it is difficult to define a meaning for replacing multi heads rules compilation of CHR code is always incremental i e any existing CHR code in a module is not replaced by a new compilation Instead the rules from the new compilation is added to the old ones It is possible to clear out old CHR code before compiling a file This is done with the chr 1 predicate This first remove any existing CHR code in any module before the compilation starts It thus approximates the semantics of chr 1 of the old library but no Prolog file is generated 8 9 4 Semantics Addition and removal of constraints In the old chr library it was not clearly defined when a constraint will be added to or removed from the constraint store during the execution of a rule In the extended chr library all head constraints that occur in the head of a rule are mutually exclusive i e they cannot refer to the same constraint This ensures that similar heads in a rule will match different constraints in the constraint store Beyond this the state of a constraint if it is in the constraint store or not that has been matched in the head is not defined during the execution of the rest of the head and guard As soon as the guard is satisfied any constraints removed by a rule will no longer be in the constraint store and any constraint that is not removed by the rule will be present
55. ad a compiled constraint handler File The CHR library is automatically loaded to provide the necessary runtime environment ECL PS is in coroutining mode You can compile your chr file and load the resulting p1 file at once using the query chr File 8 3 Example Constraint Handlers All example files are in the subdirectory 1ib chr of the installation directory of ECL PS which can be found using get_flag installation_directory Dir The files chr pl examples relevant to a particular constraint system can be found by looking at all files that match the pattern given in the follow ing listing with each example handler The examples include a color graphic demo about optimal sender placement for wire less devices in buildings and company sites small constraint handlers for e minimum maximum of and inequalities between terms minmax e terms functor 3 arg 3 as constraints term 56 e lists similar to Prolog III list e rational trees tree e sound if then else negation and checking lazy conjunction and dis junction control e geometric reasoning about rectangles demo and larger constraint handlers for e booleans for propositional logic bool e finite and infinite domains inspired by CHIP domain e sets set e terminological reasoning similar to KL ONE 8 kl one e temporal reasoning over time points and intervals 7 time e equ
56. agation adds new con straints which are logically redundant but may cause further simplification e g X gt Y Y gt Z gt X gt Z Repeatedly applying CHRs incrementally simpli 55 fies and finally solves user defined constraints e g A gt B B gt C C gt A leads to fail With multiple heads and propagation rules CHRs provide two features which are essential for non trivial constraint handling The declarative reading of CHRs as formulas of first order logic allows one to reason about their correctness On the other hand regarding CHRs as a rewrite system on logical formulas allows one to reason about their termination and confluence In the next section it is explained how to use CHRs Then example con straint handlers and the color graphic demo are listed The next section introduces the basics of the CHR language and how it works The next section describes more of the CHR language the section after the built in la beling feature Then there is a section on how to write good CHR programs Next the debuggers for CHRs are introduced 8 2 Using Constraint Handling Rules Here are the steps to be taken from writing to using CHRs e Write a CHR program in a file File chr e In ECL PS load the chr library with the query lib chr It contains both the compiler and runtime system for CHRs Now ECL PS is in coroutining mode e Compile your chr file into a pl file with the query chr2p1 File e In any ECL PS session you can lo
57. aints are consistent with the problem i e none of the constraints are violated T he cutpool constraints can either be added to the problem matrix immediately or they can be checked for violation after the solver solves the problem Any violated constraints are then added to the problem and the problem resolved This is repeated until either a fix point is reached where no constraints are violated or if the external solver is unable to solve the problem If the external solver does not produce a solution then e if the problem is unbounded any outstanding cutpool constraints are added to the problem matrix without checking for violation and the external solver is invoked for one more time This is because the extra constraints may make the problem bounded e if the problem is infeasible then failure occurs as normal This multiple invocation of the solver occurs within an eplex s call to the external solver to solve a problem and so the process should be transparent to the user except that the setting of the timeout applies to each solver invocation rather than to the whole solving process The user can specify how the cutpool constraints are treated they can be either added to the problem matrix before invoking the solver or only added if violated In addition cutpool constraints can be made inactive in which case they are not considered for adding to the problem matrix at all and are not checked for violations This is provi
58. al 1 when they appear in constraints otherwise the variable rep resenting the express may be assumed to be an IC variable resulting in a type error See section 3 1 7 for more details We hope to remove this limitation in a future release e IC does not support the lt 2 syntax for less than or equal con straints Use lt 2 the standard ECL PS operator for integer less than or equal constraints instead Similarly use 2 instead of 3 3 2 e The reified connectives provided by the two solvers are different FD s 1 2 2 gt 2 and lt gt 2 and their reified versions correspond to IC s neg 1 and 2 or 2 gt 2 and 2 and their reified versions Note that IC has better reification sup port in that any constraint may be embedded in any other constraint expression evaluating to that constraint s reified value 12 e The primitives for accessing and manipulating the domains of variables are different see the section on variable query predicates section 3 2 7 for details of IC s support for this 3 1 3 Differences between IC and RIA The main difference between IC s interval solving and RIA s is that IC is aware of and utilises the bounded real numeric type This means bounded reals may appear in IC constraints and IC variables may be unified with bounded reals though direct unification is not recommended it is preferable to use an equality constraint to do the as
59. al truth value of a constraint when reified can be used to enforce the constraint or its negation during search The following three examples are equivalent X gt 4 B X gt 4 B 1 B X lt 4 B 0 By unifying the value of the reified truth value the constraint changes from being passive to being active Once actively true or actively false the constraint will prune domains as though it had been posted as a simple non reified constraint User defined reified constraints Reified constraints are implemented using the the 3 argument form of the constraint predicate if it exists and it does exist for the arithmetic relation constraints User defined constraints will be treated as reifiable if they appear in an expression context and as such should provide forms where the last argument is the reified truth value reflected into a variable The user defined constraint should behave as follows depending on the state of the reified variable Reified variable is unbound When the reified variable is unbound the constraint should not perform any domain reduction on its arguments but should check to see if the constraint has become entailed or dis entailed setting the reified variable to 1 or O respectively Reified variable is bound to 0 In the event that the reified variable becomes bound to 0 then the constraint should actively propagate its nega tion Reified variable is bound to 1 In the event that the reif
60. all the variables their bounds and constraints of the eplex problem Like other solvers each eplex instance has its own module To use an eplex instance it must first be declared so that the module can be created This is done by eplex_instance Name This predicate will initialise an eplex instance Name Once initialised a Name module will exist to which the user can post the constraints for the eplex problem and setup and use the external solver state to solve the eplex problem Normally this predicate should be issued as a directive in the user s program so that the program code can refer to the instance directly in their code For example eplex_instance instance For convenience the eplex library declares eplex as an eplex instance when the library is loaded 9 2 1 Linear Constraints The constraints provided are equalities and inequalities over linear expres sions Their operational behaviour is as follows e When they contain no variables they simply succeed or fail e When they contain exactly one variable they are translated into a bound update on that variable which may in turn fail succeed or even instantiate the variable Note that if the variable s type is integer the bound will be adjusted to the next suitable integral value e Otherwise the constraint is transferred to the external solver state if the state has been setup If it has not the constraint delays and is transferred to the external
61. an also be passed to more than one solver by specifying a list in the module qualification For example Lic suspend A gt B will pass the constraint to both the ic and suspend solvers Module qualification is not needed if the constraint is defined by an imported module and there is no other imported module which defines the same constraint For example if ic is the only imported module which defines gt 2 then gt 2 can be used without qualification A gt B Note that for constraints that are defined for eclipse language such as gt the standard arithmetic test the default behaviour when an unqualified call to such a constraint is made is to pass it to eclipse_language even if another solver which defines the constraint is imported Thus for example A gt B will by default have standard i e non suspending test semantics even if e g the ic library which also defines gt 2 is imported To access the ic version module qualification should be added ic A gt B Alternatively the synonymous gt 2 constraint could be used A B In general module qualifications are recommended if the programmer wants to ensure a particular constraint behaviour regardless of which other mod ules might be loaded On the other hand if the intention is to switch easily between different solvers by simply loading a different library module qual ification is best omitted Finally it i
62. and Goal infers consistent The strongest constraint is generated by Goal infers most but it can be expensive to compute The other al ternatives may be evaluated more efficiently and may yield a better overall performance on different applications We call them approximations since the information they produce during propagation is a weaker approxima tion of the information produced by the strongest constraint We illustrate the different approximations supported by the current version of Propia on a single small example The results for Goal infers most reflect the problem that structured terms cannot appear in IC integer domains p 1 a p 2 f 2 p 3 3 p X Y infers most X X 1 3 Y Y There is 1 delayed goal Yes 0 00s cpu 7 X 1 3 p X Y infers most X X 1 3 Y Y There is 1 delayed goal Yes 0 00s cpu p 2 Y infers most 52 Y f _326 There is 1 delayed goal Yes 0 00s cpu The first approximation we will introduce in this section is one that searches for the unique answer to the query It is written Goal infers unique This is cheap because as soon as two different answers to the query have been found the constraint evaluation terminates and the constraint is delayed again until new information becomes available Here are two examples of this approximation In the first example notice that no domain is produced for X p X Y infers unique X X YS y There is
63. ared statements is that provided by the database but a common syntax is to use to indicate a placeholder For example insert into employees enum ename esalary ejob values 7 would be used to add rows to the employees relation Such an SQL statement has to be prepared before execution It can then be executed in batches to insert several tuples in one go Preparation involves parsing the SQL statement and setting up a buffer for the tuples A data template is used as an example buffer For the insert command above it might look like emp 1234 some name 1000 0 some job The argument positions correspond to the order of the placeholder in the SQL statement The types of the data will be used to type check the tuples when they are inserted The following ECL PS goal uses a template to create a cursor for an insert command SQL insert into employees enum ename esalary ejob values 7 7 Template emp 1234 some name 1000 0 some job session_sql_prepare H Template SQL Cursor H is a handle to a database session and Cursor is the cursor created for the prepared statement SQL The cursor can then be used to insert several rows into the employee table cursor next execute Cursor emp 1001 E G SMITH 1499 08 editor cursor next execute Cursor emp 1002 D E JONES 1499 08 journalist 115 Similarly for queries a data template specifies the types of the columns retrieved The positions of
64. arious Constraints on Lists cres 4 2 Cumulative Constraint and Resource Profiles 4 3 Edge findey leen 5 The Integer Sets Library 5 1 Ground Integer Sets 22 2 2 Cm m nn 5 2 Set Variables 2 do ok Ge Sa Se eS Ss EE a 5 2 1 Declaring dus Ca hus pu fae deta ede dinh WEE ER Ge gS Ende 5 2 2 Priol 2 4330 ke aa eh ee e eS PGR Rae 5 23 Domain Access m nn 0000 eee eee Constraints oo mon 5 3 1 Membership 2 2 lll 5 32 Cardinality s s 2202 2 2088 ES Sa En 5 3 8 Set Relations 2 2 2 Cm mn 5 3 4 N ary Set Relations 22 2 m mn 5 8 5 Set Weights nn Set Expressions a Search Support o aoo 5 3 5 4 5 5 5 6 Example 6 The Symbolic Domain Library 6 1 Domains and Domain Variables 22 2 22 2 nn nn 6 2 Basic Constraints 0 sirara saa 6 3 Global Constraints ss sro sar ares ka daraa 6 4 Internals 4 2 ll ers 6 5 Extending and Interfacing this Library 7 Propia A Library Supporting Generalised Propagation CL Overview o os xor ops X69 we Be o o9 3 AQUA Rus dS 7 2 Invoking and Using Propia 7 3 Approximate Generalised Propagatio
65. at in this context integers are considered a subset of the reals and can therefore occur in these constraints e arithmetic equality inequality and disequality which in addition to the above constrain all variables within their arguments to integers Syntactically these generally have a leading e g lt Not all constraints are supported by all the solvers For example the eplex solver does not support any strict inequality constraints Table 2 1 shows 7 2 2 gt 2 2 lt 2 2 2 gt 2 gt 2 gt 2 gt 2 gt 2 lt 2 lt 2 lt 2 lt 2 lt 2 2 2 2 2 integers 1 reals 1 suspend yes yes yes yes yes yes yes yes ic yes yes yes yes yes yes yes yes eplex yes yes yes yes yes colgen yes yes yes yes arith yes yes e If integer bounds are given to the eplex version of 2 the external solver does not consider this as an integrality constraint and only solves the con tinuous relaxation which can then be rounded to the next integer To make the external solver solve a mixed integer problem use the eplex version of integers 1 Table 2 1 Supported constraints for various arithmetic solvers the constraints that are available from the various constraint solvers In the table a yes entry indicates that the particular constraint is supported
66. ation solving over real numbers similar to CLP R or rational numbers math CHRs have also been used as a committed choice programming language on their own prime The example handlers can be loaded using chr lib File For instance the finite domain handler can be made available as follows the current directory must have write permission so that the pl file can be created eclipse 1 lib chr chr lib domain domain pl compiled traceable 241028 bytes in 1 22 seconds yes eclipse 2 X 1 10 X ne 5 X X Constraints 4 X g1165 1 2 3 4 6 7 8 9 10 yes 57 8 4 The CHR Language User defined constraints are defined by constraint handling rules and op tional ECL PS clauses for the built in labeling feature The constraints must be declared before they are defined A CHR program file extension chr may also include other declarations options and arbitrary ECL PS clauses Program Statement Program Statement Declaration Option Rule Clause Constraint handling rules involving the same constraint can be scattered across a file as long as they are in the same module and compiled together For readability declarations and options should precede rules and clauses In the following subsections we introduce constraint handling rules and explain how they work The next section describes declarations clauses options and built in predicates for CHRs 8 4 1 Const
67. before Y in the domain order 7X amp Y X is strictly after Y in the domain order 7X amp lt Y X is the same as Y or before Y in the domain order 7X amp gt Y X is the same as Y or after Y in the domain order shift X C Y Y is C places above X in the domain order X and Y have symbolic domains C has an integer domain rotate X C Y like shift 3 but wraps at domain boundary element Index 4 4 List Value Value occurs List at position Index Value has a symbolic domain Index has an integer domain List is a number of symbolic domain values For example X Y amp weekday X amp Y X X mo tu we th fr sal Y Y tu we th fr sa sul Yes 0 00s cpu X amp weekday X amp we X X mo tu vel Yes 0 00s cpu 6 3 Global Constraints A number of global constraints are available which directly correspond and are in fact implemented via their counterparts in lib ic global alldifferent List All list elements are different occurrences Value 4 List N Value occurs N times in List atmost N List Value Value occurs at most N times in List 44 6 4 Internals Internally symbolic domains are mapped to integer ranges from 1 up to the number of domain elements The first value in the domain declaration corre sponds to 1 the second to 2 and so on Similarly symbolic domain variables can be mapped to a corresponding IC integer variable This mapping is accessibl
68. bound is empty all the unified columns are constrained to integers if one of them was constrained to integer previously and an equality constraint between the two variables is sent to the solver state but the user can only obtain one eplex value from the unified variable even though in the external solver the variable is still represented as two variables columns in the matrix It is possible to turn off this automatic sending of the equality constraints by specifying no for the option post equality when unified in solver setup or via eplex set 2 The reason is that some solvers automatically perform unification when they know that two variables are the same For example for the constraint X Y Z if Y becomes 0 then X and Z may be unified by the solver maintaining the constraint If the same constraint was also posted to the eplex solver state then there is no need to send the redundant constraint However if the external solver state did not have the constraint then it can become inconsistent with that of ECL PS if the equality constraint is not sent Therefore only turn off sending of equality constraints if you are certain you know what you are doing 94 The merging of the bounds may trigger the solver if the bounds trigger condition was specified Note however that the deviating bounds trigger condition is not tested for because there is no longer a valid solution value for the merged columns 9 7 External Solver
69. btain some bounds on the optimal objective value The best and worst bounds on the optimal objective can be obtained using the best bound and worst bound options of eplex_get 2 respectively 9 3 3 Interface for CLP Integration Solver Demons To implement hybrid algorithms where a run of a simplex MIP solver is only a part of the global solving process the black box model presented above is 82 not appropriate anymore With eplex instances we can call eplex solve 1 repeatedly to re solve the problem perhaps after adding more constraints to the problem or after changes in the variable bounds However the solver must be invoked explicitly We require more sophisticated methods of in voking the solver This can be done by setting up a solver demon and specifying the conditions in which the demon is to wake up and invoke the external solver EplexInstance eplex solver setup 4 Objective Cost ListOfOp tions TriggerModes This is a more sophisticated set up for a new solver state than eplex_solver_setup 1 in fact eplex solver setup 1 is a special case of eplex_solver_setup 4 The main idea is that a list of trigger conditions are specified in TriggerModes and along with setting up the solver state a demon goal is created which is woken up when one of the specified trigger condition is met This demon goal will then invoke the solver with any constraints posted to the eplex instance since the solver was last invoked taken into a
70. ccount to re solve the problem The ListOfOptions is a list of solver options for setting up the solver state Some of these affect the way the external solver solves the problem such as if presolve should be applied before solving the problem See the reference manual for eplex solver setup 4 for details on the available options and trigger modes As the solver is designed to be invoked repeatedly it is inappropriate to directly bind Cost to the objective value Instead the objective value is exported as a bound to Cost For a minimisation problem each solution s cost becomes a lower bound for maximisation an upper bound on Cost This technique allows for repeated re solving with reduced variable bounds or added constraints Note that the bound update is done only if the solution is optimal Note also that Cost is not automatically made a problem variable and thus may not have bounds associated with in In order for the bounds information not to be lost some bounds should be given to Cost e g making it a problem variable but this might introduce unnecessarily self waking on bounds change or via another solver with bounds e g ic Note that when a solver demon runs frequently on relatively small problems it can be important for efficiency to switch the external solver s presolving off for this demon as part of the ListOfOptions during the setup of the problem to reduce overheads Example The simplest case of having a simplex solv
71. cessed directly rather than through OSI and this provides better MIP support more information on the MIP solver state is available and a more sophisticated MIP search based on sample code supplied with CBC than the default is performed generally leading to faster MIP solves The problem representation is stored by CLP and one performance issue when using CLP is that incrementally adding new constraints to a problem after solver setup can be expensive as the whole problem has to be copied and expanded for each addition It is therefore more efficient to either post the constraints before problem setup or add a large number of constraints in one go e g by using eplex add constraints 3 Unfortunately this can be less memory efficient than incrementally adding the constraints if those constraints are only needed by eplex and not at the ECL PS level osisymclp Supports primal and dual simplex methods for solving linear and MILP problems MILP is currently performed via the standard OSI API and so has the same restrictions Special Order Sets SOS are not supported Time outs are not supported Another restriction is due to SYMPHONY which does not allow the objec tive coefficients to be modified after a problem have been solved once Thus the objective changing probes are not supported 100 XPRESS XPRESS supports solving of linear and mixed integer problems both with a linear objective LP and MILP and also with a quadratic obje
72. checks are made to see if the constraint has become entailed necessarily true or dis entailed necessarily false The simplest and arguably most natural way to reify a constraint is to place it in an expression context i e on either side of a gt etc and assign its truth value to a variable For example TruthValue X gt 4 It is also possible to use the 3 argument form of the constraint predicates where the third argument is the reified truth value for example gt X 4 TruthValue But in general the previous form is recommended as it can be easily extended to handle the truth values of a combination of constraints by using the infix operators and logical conjunction or logical disjunction and gt logical implication or the prefix operator neg logical negation e g TruthValue X gt 4 and Y lt 6 Again as mentioned earlier there are a number of reified connectives which can be used to combine reified constraints using logical operations on their truth values and 2 Reified constraint conjunction e g B X gt 3 and X lt 8 or X gt 3 and X 8 or 2 Reified constraint disjunction e g B X gt 3 or X lt 8 or X gt 3 or X lt 8 gt 2 Reified constraint implication e g B X gt 3 gt X lt 8 or X gt 3 gt X lt 8 neg 1 Reified constraint negation e g B neg X gt 3 orneg X gt 3 21 Enforcing constraints The logic
73. constraint Removing the head constraint and adding it again in the body is inefficient and may cause termination problems If the already_in_heads option is on in such a case the head constraint is kept and the body constraint ignored Note however that this optimization currently only works if the body constraint is the only goal of the body or the first goal in the conjunction comprising the body of the rule see the example handler for domains The option may be too expensive if identical head body constraints rarely occur e Note that the ECL PS environment flag debug compile set and un set with dbgcomp and nodbgcomp is also taken into account by the CHR compiler The default is on If switched off the resulting code is more efficient but cannot be debugged anymore see section 8 8 8 5 4 CHR Built In Predicates There are some built in predicates to compile chr files for debugging built in labeling and to inspect the constraint store and remove its constraints e chr2p1 File compiles File from a chr to pl file e chr File compiles File from a chr to pl file and loads the p1 file e chr_trace activates the standard debugger and shows constraint han dling 63 e chr notrace stops either debugger e chr labeling provides built in labeling see corresponding subsec tion e chr label with Constraint checks if Constraint satisfies a label with declaration used for built in labeling
74. cross the chr file as long as they are in the same module The rules are tried in some order determined by the CHR compiler Due to optimizations this order is not necessarily the textual order in which the rules where written In addition the incremental addition of constraints at run time causes constraints to be tried for application of rules in some dynamically determined order 8 7 2 Optimizations Single headed rules should be preferred to two headed rules which involve the expensive search for a partner constraint Rules with two heads can be avoided by changing the granularity of the constraints For example as sume one wants to express that n variables are different from each other It is more efficient to have a single constraint all_different List_of_n_Vars 66 than n inequality constraints see handler domain chr However the ex treme case of having a single constraint modeling the whole constraint store will usually be inefficient Rules with two heads are more efficient if the two heads of the rule share a variable which is usually the case Then the search for a partner con straint has to consider less candidates Moreover two rules with identical or sufficiently similar heads can be merged into one rule so that the search for a partner constraint is only performed once instead of twice Rules with more than two heads are not allowed for efficiency reasons If needed they can usually be written as several r
75. ctive QP and MIQP It supports simplex primal and dual and barrier solving methods XPRESS does not maintain an optimisation direction with the problem instead it requires this to be specified each time the problem is solved As such the optimisation direction given in a LP format specification of the problem is ignored when a problem is read in and when writing a problem minimisation is assumed 9 11 3 Access to External Solver s Control Parameters The external solver has a number of control parameters that affect the way it works These can be queried and modified using the Ip get 2 eplex get 2 Ip get 3 and lp set 2 eplex set 2 lp set 3 predicates respectively Ip get 4 Handle optimizer_param ParamName Value Retrieve the value of a control parameter for the external solver for the problem represented by Handle These parameters are solver specific see Ip get 3 for more details EplexInstance eplex get optimizer param ParamName Value Like Ip get 3 but get a control parameter for the external solver associated with the specified eplex instance Ip get optimizer param ParamName Value Retrieve the global value of a control parameter for the external solver The parameters and the exact meaning of global is solver specific if the solver does not have global parameters this gets the global default value rather than the globally applicable value The parameters are as in lp get 3 Ip set
76. d subexpressions to be integral Thus with integer constraints the solver does very much behave like a traditional 19 integer solver with any temporary variables and intermediate results as sumed to be integral This means that it makes little sense to use many of the nonlinear functions available for use in expressions e g sin cos In exp in integer constraints It also means that one should take care using such things as division X 2 Y 2 1 and X Y 2 are different constraints with the former constraining X and Y to be even That said if all the constants and variables are integral already and the subexpressions clearly so as a consequence then the integer 72 constraints and general constraints may be used integerchangeably ExprX ExprY ic ExprX ExprY ExprX is equal to ExprY ExprX and ExprY are general expressions ExprX gt ExprY ic ExprX gt ExprY ExprX is greater than or equal to ExprY ExprX and ExprY are general expressions ExprX lt ExprY ic ExprX lt ExprY ExprX is less than or equal to ExprY ExprX and ExprY are general expressions ExprX gt ExprY ic ExprX gt ExprY ExprX is strictly greater than ExprY ExprX and ExprY are general expressions ExprX lt ExprY ic ExprX lt ExprY ExprX is strictly less than ExprY ExprX and ExprY are general expressions ExprX ExprY ic ExprX ExprY ExprX is not equal to Ex prY ExprX and ExprY are general expressio
77. ded for efficiency reason if the user knows for certain constraints would not be violated by the solution they can be made inactive It is the user s responsibility to ensure the correctness in this case 92 Unlike normal problem constraints cutpool constraints cannot add new vari ables to the problem i e the constraint must only involve problem variables that are present in the problem during solver set up This is because cutpool constraints are globally valid and so cannot involve variables that may not exist after backtracking Variables can be added to a problem before solver set up by posting constraints involving them including reals 1 which sim ply declares variables as problem variables Additionally each cutpool constraint belongs to a named group specified when the constraint is added This allows the user to classify the cutpool constraints into different groups and then manipulate a groups of constraints as a whole e g making them all inactive A default group is predefined to which cutpool constraints belongs unless specified otherwise To add cutpool constraints to other groups the group name must first be created with the cutpool group option of Ip get 3 9 5 2 Predicate specific Support Constraints are added to the cutpool using lp_add_cutpool_constraints 4 Add the constraints to the cut pool associated with the problem specified by the handle By default the constraints belong to the default group a
78. ds a better cost bound on the problem In the example below an upper bound for the cost of 1 5 is found initially eclipse 5 ic Cost 1 0Inf 1 0Inf eplex X Y lt 1 eplex Y Z lt 1 eplex X Z 1 eplex eplex_solver_setup max X Y Z Cost solution no bounds X X 1e 20 1e 20 Y Y 1et20 1e 20 Z Z 1e 20 1e 20 Cost Cost 1 0Inf 1 500001 Delayed goals lp demon prob Yes 0 00s cpu 84 Note that the ranges for X Y and Z is 1e4 20 1e 20 as 1e 20 is this external solver s notion of infinity If the variable bounds change subsequently the solver will be re triggered improving the cost bound to 1 3 eclipse 6 ic Cost 1 0Inf 1 0Inf eplex X Y lt 1 eplex Y Z 1 eplex X Z lt 1 eplex eplex_solver_setup max X Y Z Cost solution no bounds eplex Y lt 0 3 X X 1e 20 1e 20 Z Z 1e 20 1e 20 Cost Cost 1 0Inf 1 300001 Y Y 1e 20 0 3 Delayed goals lp_demon prob Yes 0 00s cpu A further example is the implementation of a MIP style branch and bound procedure Source code is provided in the library file mip pl 9 3 4 Encapsulated Modification of the Problem Probing The external mathematical programming solvers often provides the facility for the user to change the problem being solved This includes the addition or removal of constraints and the changing of the objecti
79. e Calling this predicate again with the same cursor will retrieve further tuples Any NULL values are re turned as uninstantiated variables Once all the tuples have been retrieved this predicate fails If Tuple does not unify with the retrieved tuple the predicate fails check overdraft limit Session Account L select count id from accounts where id Account and balance lt overdraft concat string L SQL session sql query Session c 0 SQL OverdraftCheck cursor next tuple verdraftCheck c Count Count O In this example a query is built to verify that the balance of an account is not less than its overdraft facility All comparisons are done within the database and we are just interested in checking that no rows match the where clause For this kind of application one would not normally use concat string 2 SQL placeholders would be used instead See session sql prepare query 5 cursor all tuples Cursor TupleList The SQL query represented by the cursor is executed and all the matching tuples are collected in TupleList This could be defined as cursor all tuples Cursor Tuples cursor next tuple Cursor T gt Tuples T Ts cursor all tuples Cursor Ts Tuples 122 cursor N tuples Cursor Retrieved TupleList RestTupleList If the underlying DB supports the retrieving mutule tuples in one go then a buffer full of tuples matching the query is retrieved other
80. e e g 1 0Inf 5 5 1 0Inf then a delayed goal will be setup to exclude values when the bounds become sufficiently narrow Note that calling the reified form of will result in the Variable becoming constrained to be integral even if Bool is uninstantiated Further note that like other reified predicates can be used in fix in an IC expression e g B X 1 10 is equivalent to X 1 10 B See section 3 2 3 for more information of reified constraints Vars Domain Constrains Vars to take only integer values from the domain specified by Domain Vars may be a variable or a collection of variables la collection to list 2 Domain can be specified as a simple range Lo Hi or as a list of subranges and or individ ual elements integer variables only Also allowed are the untyped symbolic bound values inf inf and inf Vars Domain Constrains Vars to take real values from the domain specified by Domain Vars may be a variable or a collection of variables la collection to list 2 Domain must represent one contiguous interval reals Vars Declares that the given variables are IC variables integers Vars Constrains the given variables to take integer values only 3 2 2 Arithmetic constraints Note that the integer forms of the constraints are essentially the same as the general forms except that they check that all constants are integers and generally constrain all variables an
81. e through the predicate symbol_domain_index 3 symbol domain index fr D I D weekday I 5 Yes 0 00s cpu X amp weekday symbol domain index X D I X Xi mo tu we th fr sa sul D weekday I I 1 7 Yes 0 00s cpu X amp weekday X amp we symbol domain index X D I X X mo tu th fr sa sul D weekday I 141152 4 TL Yes 0 00s cpu The integer variable I mirrors the domain of the symbolic variable X and vice versa 6 5 Extending and Interfacing this Library Because of the mapping of symbols to integers new constraints over symbolic variables can be implemented simply by placing numeric IC constraints on the corresponding integer variables Similarly the facilities of the ic search library can be exploited when working with symbolic variables Instead of labeling the symbolic variables one can use the various facilities of ic search to label the corresponding integer variables instead 45 46 Chapter 7 Propia A Library Supporting Generalised Propagation 7 1 Overview Propia is the name for the implementation of Generalised Propagation in BOL PS Generalised propagation is not restricted to integer domains but can be applied to any goal the user cares to specify even if the variables don t have domains Effectively the system looks ahead to determine if an approximation to the possible answers has a non trivial generalization It is non tri
82. e very beginning you should simply write the constraint twice once without and once with anno tation 10 4 Conflict Sets Given a tentative assignment there are two kinds of conflicts that can occur e Untenable variables e Violated constraints To obtain a tentative assignment which is a solution to the given problem both kinds of conflicts must be repaired The repair library supports this task by dynamically maintaining conflict sets Typically a search algorithm examines the conflict set s and attempts to repair the tentative assignment such that the conflicts disappear When all conflict sets are empty a solution is found conflict vars Vars When a variable becomes untenable it appears in the set of conflict variable when it becomes tenable it disappears This primitive returns the list of all currently untenable variables Note that all these variables must be reassigned in any solution there is no other way to repair untenability Variable reassignment can be achieved by changing the variable s tentative value with tent set 2 or by instantiating the variable Care should be taken whilst implementing repairs through tentative value changes since this is a non monotonic operation conflicting repairs may lead to cycles and the computation may not terminate conflict constraints 4 ConflictSet Constraints When a repair constraint goes into conflict i e when it does not satisfy the tentative assignment of its var
83. ection for more details 8 4 2 How CHRs Work ECL PS will first solve the built in constraints then user defined con straints by CHRs then the other goals Example contd eclipse chr minmax minmax chr compiled traceable 106874 bytes in 3 37 seconds minmax pl compiled traceable 124980 bytes in 1 83 seconds yes eclipse minimum X Y Z maximum X Y 2 X Y Z _g496 yes 59 Each user defined constraint is associated with all rules in whose heads it occurs by the CHR compiler Every time a user defined constraint goal is added or re activated it checks itself the applicability of its associated CHRs by trying each CHR To try a CHR one of its heads is matched against the constraint goal If a CHR has two heads the constraint store is searched for a partner constraint that matches the other head If the matching succeeded the guard is executed as a test Otherwise the rule delays and the next rule is tried The guard either succeeds fails or delays If the guard succeeds the rule fires Otherwise the rule delays and the next rule is tried In the current implementation a guard succeeds if its execution succeeds without delayed goals and attempts to touch a global variable one that occurs in the heads A variable is touched if it is unified with a term including other variables if it gets more constrained by built in constraints e g finite domains or equations over rationals or if a goal delays on it see also
84. ension list names can be used in suspend 3 and related predicates to denote an appropriate waking condition The attribute of a domain variable can be accessed with the predicate get ic attr 2 As noted above direct access and manipulation of the attribute is discour aged use the access predicates instead 32 Chapter 4 Additional Finite Domain Constraints 4 1 Various Constraints on Lists The library ic global implements a number of constraints over lists of inte ger variables It is loaded using one of use module library ic global lib ic global The following predicates are provided alldifferent List A version of alldifferent 1 with strong propagation alldifferent List Capacity Like alldifferent 1 but every value may occur Capacity times minlist List Min Min is the minimum of the values in List Operationally Min gets updated to reflect the current range of the minimum of variables and values in List Likewise the list elements get constrained to the mini mum given maxlist List Max Max is the maximum of the values in List Operationally Max gets updated to reflect the current range of the maximum of variables and values in List Likewise the list elements get constrained to the maximum given lexico le 4 Listl List2 Imposes a lexicographic ordering between the two lists 33 ordered Relation List Constrains List to be ordered according to Relation Relation is
85. epair 3 Delayed goals yes Initially only the third constraint Y 3 is inconsistent with the tentative assignment According to the definition of r_conflict_prop this leads to the constraint Y 3 being propagated which causes Y to be intantiated to 3 thus rendering the tentative value 2 irrelevant Now the constraint Y Z is in conflict since Y is now 3 and Z has the tentative value 3 as well The constraint starts to propagate and removes 3 from the domain of Z 1 2 As a result Z becomes a conflict variable since its tentative value 3 is no longer in its domain The Y Z constraint remains in the conflict constraint set because Z has no valid tentative assignment The constraint Y X is not affected it neither goes into conflict nor is its fd version ever activated To repair the remaining conflicts and to find actual solutions the repair 0 predicate described below could be used 10 6 2 Repair Labeling This is an example for how to use the information provided by the repair library to improve finite domain labeling You can find the repair 1 predicate in the repairfd library file repair ConflictSet conflict vars Cl gt 4 label conflict indomain C variables first repair ConflictSet conflict constraints ConflictSet Cl gt term variables C Vars choose one variable in deleteffc Var Vars _ the conflict constraint Var tent get Val Var Val fd Var Val
86. equests the CPLEX solver the second line explicitly requests the XPRESS MP solver Note that these solvers must be avail able for your machine for the above to work The third line requests the CLP CBC solver and the fourth line requests the SYMPHONY solver 9 11 1 Versions and Licences All the solvers supported by the library come in various versions The set of supported solver versions may vary between different releases of ECL PS please refer to the release notes Depending on which solver licence you have for the commercial solvers which version of it and which hardware and operating system you need to use the matching version of this interface Because an ECL PS installation can be shared between several computers on a network we have provided you with the possibility to tell the system which licence you have on which ma chine To configure your local installation simply add one line for each com puter with the appropriate licence to the file eclipsedir lib eplex lic info ecl where lt eclipsedir gt is the directory or folder where your ECL PS instal lation resides The file contains lines of the form licence Hostname Solver Version LicStr LicNum For example if you have CPLEX version 7 5 on machine workhorse and XPRESS MP version 15 20 with the license file located in my xpress license on machine mule and your Internet domain is icparc ic ac uk you would add the lines licence workhorse icparc ic
87. er automatically cooperating with a CLP program is to set up a solver demon which will repeatedly check 83 whether the continuous relaxation of a set of constraints is still feasible The code could look as follows we use the eplex instance in this example simplex eplex eplex solver setup min 0 C solution no bounds First the constraints are normalised and checked for linearity Then a solver with a dummy objective function is set up The option solution no indi cates that we are not interested in solution values Then we start a solver demon which will re examine the problem whenever a change of variable bounds occurs The demon can be regarded as a compound constraint im plementing the conjunction of the individual constraints It is able to detect some infeasibilities that for instance could not be detected by a finite do mains solver e g eclipse 2 eplex X Y Z gt K eplex X Y Z lt 1 eplex eplex_solver_setup min 0 C solution no bounds K 2 No 0 00s cpu In the example the initial simplex is successful but instantiating K wakes the demon again and the simplex fails this time A further step is to take advantage of the cost bound that the simplex procedure provides To do this we need to give the objective The setup is similar to above but we accept an objective function and add a cost variable The bounds of the cost variable will be updated whenever a simplex invocation fin
88. er being used The solution that is returned can also depend on the detailed settings of the floating point unit of the processor Thus changing some of these settings may change the solution that is returned It is thus possible for eplex to give different solutions on the same machine and solver if these settings are changed e g when ECL PS is embedded into a Java application 9 11 Solver Specific Information The external solvers currently supported by the eplex library are e XPRESS MP a product of Dash Optimisation www dashoptimization com e CPLEX a product of ILOG www ilog com e Solvers accessed via OSI an Open Source solver interface of the COIN OR project www coin or org Various solvers are supported via OSI using the generic interface The following are currently distributed clpcbe COIN OR s CLP linear solver in combination with the CBC branch and cut framework for MIP problems Eplex pro vides specialised support for this combination which enhance the features provided and improve performance for solving larger MIP problems symclp COIN OR s SYMPHONY MILP solver with CLP as the linear solver Supported via the generic OSI API Both Dash and ILOG offer academic licences at discounted prices or aca demic partner programs To load a specific solver explicitly use lib eplex cplex lib eplex xpress lib eplex osi clpcbc lib eplex osi symclp 97 The first line explicitly r
89. eturned unchanged in NonlinConstr 9 5 Cutpool Constraints In eplex constraints added to a problem are removed on backtracking How ever it is sometimes possible to discover constraints that are valid for the whole problem which the user wish to apply even after backtracking such constraints are referred to as global cuts In addition the user may want to remove some constraints from the problem being solved because they do not help to constrain the problem but they slow down the solving of the problem 91 To support this eplex allow constraints to be added to a cutpool associated with a problem instead of directly to the problem The main differences from the normal problem constraints are e they are not removed on backtracking Once added to a cutpool a constraint exists until the problem itself is destroyed e they are handled differently during solving and the user has more control on how the external solver takes the constraints into account 9 5 1 Solving a Problem with Cutpool Constraints Logically cutpool constraints are always valid for the problem and so should be considered when the problem is solved Unlike normal constraints cut pool constraints are not necessarily added to the solver s problem matrix and if they are added they are added only for the solving and removed from the problem matrix after the solving When the external solver solves the problem eplex ensures that the cutpool constr
90. ex instances and a variable is shared between the instances then the solver state for each instance can have a different optimal value to the variable 9 3 2 Creating Eplex Instances Dynamically So far we have shown the use of eplex instance 1 as a directive to de clare an eplex instance For some applications it might be necessary to create eplex instances dynamically at run time The can be done by calling eplex instance 1 at run time In this case the instance name should not be used to module qualify any predicates in the code since this will raise a compiler warning complaining about an unknown module new pool X Y INCORRECT eplex instance pool pool X gt Y will generate a warning Of course in the above code the instance name pool is already known at compile time so it can always be declared by a directive If the name is truly generated dynamically this can be done as follows new pool Pool X Y eplex instance Pool Pool X gt Y Obtaining Bounds on the Objective Value The external solver does not always return the optimal objective value for example when the optimisation was aborted However even when the solver returns an optimal solution it may actually not be the exact optimal be cause of solver settings e g for MIP problems the MIP search will termi nate when the solution found is within certain tolerance of the best possible solution value In these cases it may be useful to o
91. exico_le 2 33 lexico_le 2 33 lib eplex 10 lib ic 10 lib suspend 10 library chr pl 55H74 fd sets 37 41 ic 11432 ic symbolic 43H45 lin 26 linear programming interface to 75 102 list constraints 57 local search 1103 locate 2 23 27 ic 23 locate 3 23 27 ic 123 locate 4 27 ic 23 log 26 Ip add 3 88 Ip add columns 2 90 64 66 eplex 93 Ip add vars 2 88 Ip cleanup 1 91 Ip demon setup 5 87 Ip get 2 101 102 Ip get 3 89 93 94 101 Ip read 3 91 Ip set 2 101 102 Ip set 3 91 93 101 Ip setup 4 87 Ip solve 2 88 Ip var get 4 89 Ip add constraints 3 88 Ip add constraints 4 90 Ip add cutpool constraints 4 Ip var get bounds 4 89 Ip var set bounds 4 88 Ip write 3 91 94 mathematical programming interface to 75 102 maxlist 2 33 membership booleans 2 fd sets 38 minlist 2 33 minmax constraints 56
92. ext section 3 4 1 Modifying variable domains When using IC variables in normal code one would typically use the lt and gt family of constraints to resp remove a value reduce the upper bound or increase the lower bound of a variable While these constraints are good for normal CSP solving they have a num ber of properties which may be less desirable when writing new constraints In particular they may leave unwanted delayed goals behind and may per form extra propagation before returning it may be desirable to perform all required bound updates before allowing further propagation to occur To give the constraint writer more control over such matters special pred icates exist in the ic_kernel module which allow direct modification of the domain without the waking of goals they are scheduled for execution but not actually executed These predicates generally accept an IC variable a non IC variable which will be constrained to make it a real IC variable or a number Full details on these predicates can be found in the reference manual they are listed here for completeness Note that with the exception of im pose_bounds 3 none of the goals call wake 0 so the programmer is free to do so at a convenient time impose_min 2 Set the lowerbound impose_max 2 Set the upperbound impose_bounds 3 Sets both upper and lower bounds exclude 2 Excludes an integer from an integral variable exclude_range 3 Excludes a range o
93. f integers from an integral variable set_var_type 2 Makes the variable be of the given type set_vars_type 2 Like set_var_type but works for lists and submatrices of variables as well 3 4 2 The IC attribute The IC attribute is a meta term which is attached to all variables which take part in IC constraints ic_kernel defines the IC attribute as a structure of the following form 31 ic var type Type lo Lo hi Hi bitmap Bitmap min SuspMin max SuspMax hole SuspHole type SuspType This structure holds var type The type of the variable This defaults to real but may become integer after an explicit call to integers 1 by being included in an integer constraint e g or by inferences made during constraint propagation lo The lower bound of the variable s domain as a float hi The lower bound of the variable s domain as a float bitmap Where relevant a bitmap representation of the integer domain where not relevant it holds the atom undefined min Suspension list of goals to be woken on lower bound changes max Suspension list of goals to be woken on upper bound changes hole Suspension list of goals to be woken when a value is removed from the middle of a domain Such removals only happen for integer variables whose domain is finite type Suspension list of goals to be woken when a variable s type becomes more constrained i e when a variable goes from being real to being integer The susp
94. fault the size of the field in the database In the case of variable sized fields and of placeholders a default size is chosen Rather than taking the default it is possible to write templates that specify a size T his is done by mentioning the size in the argument of the template 123 defines an atom datatype where the maximum length in bytes is 123 The length is given as a decimal number 7123 defines a string datatype where the maximum length in bytes is 123 The length is given as a decimal number s 123 X Describes any Prolog term that occupies up to 123 bytes in exter nal database format Any structure whose first argument is an integer can be used For example the following two templates specify the same type of tuple but the second one defines some sizes for the different elements in the tuple as well emp 1234 name Rules job emp 1234 10 rules 4000 10 The size information is used to define the minimum size of the buffer used to pass data between ECLiPSe and the database Depending on the database and the situation input output prepared direct statements such an in termediate buffer may not be used in such cases the buffer size will be ignored Otherwise if the data is too big to fit into the buffer an error will be raised The data in the buffer is passed to from the database which may have its own size specification for the data This is independent of the size informa tion specified in the templa
95. feasible has no solution or unbounded Cost is not bounded by the constraints then the predicate fails 9 2 6 Examples Here is a simple linear program handled by the predefined eplex instance eplex lib eplex lp_example Cost eplex eplex solver setup min X eplex X Y gt 3 eplex X Y 0 eplex eplex solve Cost The same example using a user defined eplex instance lib eplex eplex instance my instance lp_example Cost my_instance eplex_solver_setup min X my_instance X Y gt 3 my_instance X Y 0 my_instance eplex_solve Cost Running the program gives the optimal value for Cost eclipse 2 lp_example Cost Cost 1 5 Note that if the eplex eplex instance is used instead of my instance then the eplex instance 1 declaration is not necessary By declaring one variable as integer we obtain a Mixed Integer Problem 79 lib eplex eplex instance my instance mip example Cost my instance X Y gt 3 my_instance X Y 0 my_instance integers X my_instance eplex_solver_setup min X my_instance eplex_solve Cost eclipse 2 mip_example Cost Cost 2 0 The cost is now higher because X is constrained to be an integer Note also that in this example we posted the constraints before setting up the exter nal solver whereas in the previous example we set up the solver first The solver set up and constraint postin
96. g can be done in any order If integers 1 constraints are only posted after problem setup the problem will be auto matically converted from an LP to a MIP problem This section has introduced the most basic ways to use the eplex library We will discuss more advanced methods of using the eplex instances in sec tion 9 3 9 3 Advanced Use of Eplex Instances 9 3 1 Obtaining Solver State Information The black box interface binds both the objective value Cost and the prob lem variables by bindings these variables On the other hand eplex_solve 1 binds the objective value but does not bind the problem variables These values can be obtained by EplexInstance eplex_var_get Var What Value Retrieve infor mation about the solver state associated with the eplex instance for the variable Var If What is solution or typed_solution then the value assigned to this variable by the solver state to obtain the optimal solution is returned in Value solution returns the value as a float and typed_solution returns the value as either a float or a rounded integer depending on if the variable was constrained to an integer in the eplex problem EplexInstance eplex_get What Value Retrieve information about solver state associated with the eplex instance This returns informa 80 tion such as the problem type the constraints for the eplex problem See the reference manual for more details EplexInstance eplex set What Value Set
97. g the problem and solving of problems with a quadratic objective is not supported for all solvers At the very minimum solvers must be able to solve optimise linear problems with a linear objective Currently all supported solvers can solve linear and MIP problems with a Simplex solver e Some features may be poorly supported by a particular solver and some feature such as the relaxed probe of eplex_probe 2 may be supported slightly differently e Performance for specific problem may vary very significantly orders of magnitude between different solvers This does not necessarily indicate that one solver would consistently out perform another In addition the different solvers may return a different optimal solution to specific problems i e with the same objective value but different solution values for the variables e The solvers have different solver parameters to control tune the solver These can be accessed from eplex and is one of the only places where the user code may need to be solver specific CPLEX CPLEX supports solving of linear and mixed integer problems both with a linear objective LP and MILP and also with a quadratic objective QP and MIQP It supports various solving methods simplex primal and dual barrier network simplex and sifting In recent versions of CPLEX the relaxed and fixed probes are implemented by removing the integer information from the problem and solving the re laxed problem and
98. get 4 Handle What Value Retrieve information about solver state and results See the reference manual description of 1p get 3 for a detailed description of the available values for What For example it is possible to obtain the solution values from the last suc cessful invocation of the external solver using the following instantiate solution Handle lp get Handle vars Vars lp get Handle typed solution Values Vars Values Ip var get 4 Handle Var What Value Retrieve information about solver state represented by Handle related to a specific variable Var Again see the reference manual for the available parameters Ip var get bounds Handle Var Lo Hi Retrieve the bounds of the problem variable Var from the solver state rep resented by Handle 89 reduced cost pruning Handle GlobalCost This predicate implements a technique to prune variable bounds based on a global cost bound and the reduced costs of some solution to a problem relaxation The assumptions are that there is a global problem whose cost variable is GlobalCost and that Handle refers to a linear relaxation of this global problem The pruning potentially affects all variables involved in the relaxed problem 9 4 5 Expandable Problem and Constraints We provide low level primitives to expand an eplex problem Such a prob lem is considered to have as yet unspecified components in the objective function and posted c
99. gnitude maz lt 10 x min the somewhat cheaper linear splitting may be used In general log splitting is recom mended locate Vars Precision 26 locate Vars Precision lin log Locate solution intervals for the given variables with the required precision This works well if the problem has a finite number of solutions locate 2 3 work by non deterministically splitting the ranges of the variables until they are narrower than Precision squash Vars Precision lin log Use the squash algorithm see below on these variables This is a deterministic reduction of the ranges of variables done by searching for domain restrictions which cause failure and then reducing the domain to the complement of that which caused the failure This algorithm is appropriate when the problem has continuous solution ranges where locate would return many adjacent solutions locate LocateVars SquashVars Precision lin log A variant of locate 2 3 with interleaved squashing The squash algorithm see be low is applied once to the SquashVars initially and then again after each splitting step i e each time one of the LocateVars has been split nondeterministically A variable may occur both in LocateVars and SquashVars Squash algorithm A stronger propagation algorithm is also included This is built upon the normal bound consistency It guarantees that if you take any variable and restrict its range to a small domain nea
100. goals In fact the simplest implementation of any constraint is to suspend it until all its variables are sufficiently instantiated and then test it The library suspend contains versions of the mathematical constraints gt gt lt lt which behave like this 1 2 Finite Domains c 1 2 1 Integer Domain The standard constraint solver offered by most constraint programming sys tems is the finite domain solver which applies constraint propagation tech niques developed in the AI community 21 ECL PS supports finite do main constraints via the ic library This library implements finite domains Note that the global flag coroutine has a similar effect it causes the arithmetic comparisons as well as many other built in predicates to delay until they are sufficiently instantiated There is also an older implementation the fd library whose use is deprecated of integers and the usual functions and constraints on variables over these domains 1 2 2 Symbolic Domain 2c symbolic In addition to integer domains ECL PS offers finite domains of ordered non numeric values for example red green blue These are implemented by the ic_symbolic library Whilst there is a standard set of constraints supported by the ic library in ECL PS and in most constraint programming systems many more finite domain constraints have been introduced which have uses in specific appli cations and do not belong
101. h antisymmetry RULE antisymmetry FIRED TRY 4 maximum _g601 Var _g601 with max_eq RULE max_eq FIRED ADD 6 leq Var _g601 TRY 3 leq _g601 Var 6 leq Var _g601 with antisymmetry RULE antisymmetry FIRED TRY 1 minimum _g601 _g601 _g601 with min_eq RULE min eq FIRED ADD 7 leq _g601 _g601 TRY 7 leq _g601 _g601 with reflexivity RULE reflexivity FIRED X Y Z _g558 8 5 More on the CHR Language The following subsections describe declarations clauses options and built in predicates of the CHR language 8 5 1 Declarations Declarations name the constraint handler its constraints specify their syn tax and use in built in labeling Declaration handler Name constraints SpecList operator Precedence Associativity Name label_with Constraint if Guard The optional handler declaration documents the name of the constraint handler Currently it can be omitted but will be useful in future releases for combining handlers 61 The mandatory constraints declaration lists the constraints defined in the handler A SpecList is a list of Name Arity pairs for the constraints The declaration of a constraint must appear before the constraint handling rules and ECL PS clauses which define it otherwise a syntax error is raised There can be several constraints declarations The optional operator declaration declares an operator with the same ar gu
102. he external solver Optimal solutions and other solutions can be returned to ECL PS as required Search can be carried out either in ECL PS or in the external solver 1 7 2 clpqr The clpqr library offers two implementations of the Simplex method for solving linear constraints 11 One version uses rationals and is exact The other version uses floats This library employs public domain software and can be used for small problems with less than 100 variables 1 7 8 Piecewise Linear eplex relax This library handles any user defined piecewise linear function as a con straint closely integrated with eplex It offers better pruning than the stan dard handling of piecewise linear constraints in the external solvers 1 1 7 4 Probing for Scheduling For scheduling applications where the cost is dependent on each start time a combination of solvers can be very powerful For example we can use finite domain propagation to reason on resources and linear constraint solving to reason on cost 4 The probing_for_scheduling library supports such a combination via a similar user interface to the cumulative constraint mentioned above 1 8 Other Libraries The solvers described above are just a few of the many libraries available in ECLiPSe and listed in the ECL PS library directory 4 Libraries are not only for constraint solvers for example the ECI PSe SQL Database Interface library provides
103. he standard way See the corresponding user manual for more information 8 8 1 Using the Debugger In order to use the debugging tool the debug_compile flag must have been on default during compilation chr to pl and loading of the produced ECL PS code e The query trace activates the standard debugger tracing user defined constraints like predicates e The query chr trace activates the standard debugger showing more information about the handling of constraints application of CHRs e The query chr notrace stops either debugger The debugger displays user defined constraints and application of CHRs User defined constraints are treated as predicates and the information about application of CHRs is displayed without stopping See the subsection on how CHRs work for an example trace The additional ports are e add A new constraint is added to the constraint store e already in A constraint to be added was already present The ports related to application of rules are e try rule A rule is tried e delay rule The last tried rule cannot fire because the guard did not succeed 68 e fire rule The last tried rule fires The ports related to labeling are e try label A label with declaration is checked e delay label The last label with declaration delays because the guard did not succeed e fire label The last tried label with declaration succeeds so the clauses of the associated constraint will be used f
104. iables it appears in a conflict set once it satisfies the tentative assignment it disappears This primitive returns the list of all current conflict constraints in the given conflict set ConflictSet is the conflict set name or handle which has been used in the corresponding constraint annotation For example conflict constraints cap cstr Conflicts would retrieve all constraints that were annotated with cap cstr and are currently in conflict 107 At least one variable within a conflict constraint must be reassigned to get a repaired solution Variable reassignment can be achieved by changing the variable s tentative value with tent set 2 or by instantiating the variable Care should be taken whilst implementing repairs through tentative value changes since this is a non monotonic operation conflicting repairs may lead to cycles and the computation may not terminate Note that any repair action can change the conflict set therefore con flict constraints 2 should be called again after a change has been made in order to obtain an up to date conflict set poss conflict vars 4 ConflictSet Vars The set of variables within the conflict constraints This is generally a mixture of tenable and untenable variables 10 5 Invariants For writing sophisticated search algorithms it is useful to be able not only to detect conflicts caused by tentative value changes but also to compute consequences of these changes For example it
105. iables union 3 40 fd sets unique 52 39 106 violation wake 0 weight 3 31 39 128 XPRESS MP 129 130 Bibliography 1 F Ajili and H El Sakkout LP probing for piecewise linear optimiza tion in scheduling Programme and papers presented at CPAIOR 01 www icparc ic ac uk cpAIORO1 2001 N Beldiceanu and E Contjean Introducing global constraints in CHIP Mathematical and Computer Modelling 12 97 123 1994 citeseer nj nec com beldiceanu94introducing html A Bockmayr and T Kasper Branch and infer A unifying frame work for integer and finite domain constraint programming INFORMS Journal on Computing 10 3 287 300 1998 H H El Sakkout and M G Wallace Probe backtrack search for min imal perturbation in dynamic scheduling Constraints 5 4 359 388 2000 Hani El Sakkout Improving Backtrack Search Three Case Studies of Localized Dynamic Hybridization PhD thesis Imperial College Lon don June 1999 T Fruehwirth Constraint simplification rules Technical Report ECRC 92 18 ECRC Munich Germany July 1992 presented at CLP workshop at ICLP 92 Washington USA November 1992 T Fruehwirth Temporal reasoning with constraint handling rules Technical Report Core 93 8 ECRC Munich Germany January 1993 T Fruehwirth and Ph Hanschke Terminological reasoning with con straint hand
106. ied variable becomes bound to 1 then the constraint should actively propagate its normal semantics 22 3 2 4 Miscellaneous constraints alldifferent Vars Constrains all elements of a list to be different from all other elements of the list element Index List Value Constrains Value to be the Index th ele ment of the list of integers List 3 2 5 Integer labeling predicates These predicates can be used to enumerate solutions to a set of constraints over integer variables For optimisation see also the branch and bound library indomain Var Instantiates an integer IC variable to an element of its domain labeling Vars Instantiates all IC variables in a list to elements of their domains search Vars Arg Select Choice Method Options Instantiates the variables Vars by performing a search based on the parameters pro vided by the user 3 2 6 Real domain refinement predicates These predicates can be used to locate real solutions to a set of constraints They are essentially the same as those that were available in RIA more details of the algorithms used can be found in section 3 2 10 locate Vars Precision Locate solution intervals for Vars by splitting and search Precision indicates how accurate the intervals have to be in absolute or relative terms before splitting stops locate Vars Precision LinLog As per locate 2 but LinLog specifies wither linear lin or logarithmic log splitting should be used
107. ime system Several constraint handlers are provided in example files in the directory chr The current chr library has now been modified to function correctly without the Opium debugger which is no longer supported In addition the Prolog code produced by the chr command is now more readable In addition there is now an experimental extended implementation of CHRs This extended implementation is faster than the existing chr library and contains some extensions and changes This is described in section 8 9 8 1 Introduction Constraint handling rules CHRs CHR home page http www cs kuleuven ac be dtai projects CHI 6 are a high level language extension to write user defined constraints CHRs are essentially a committed choice language consisting of guarded rules with multiple heads The high level CHRs are an excellent tool for rapid prototyping and imple mentation of constraint handlers The usual abstract formalism to describe a constraint system i e inference rules rewrite rules sequents formulas ex pressing axioms and theorems can be written as CHRs in a straightforward way Starting from this executable specification the rules can be refined and adapted to the specifics of the application CHRs define simplification of and propagation over user defined constraints Simplification replaces constraints by simpler constraints while preserving logical equivalence e g X gt Y Y gt X lt gt fail Prop
108. in the set A set variable can be declared as follows SetVar 1 2 3 4 5 6 7 If the lower bound is the empty set like in this case this can be written as SetVar subset 1 2 3 4 5 6 7 If the lower bound is the empty set and the upper bound is a set of consec utive integers one can also declare it like 37 intset SetVar 1 7 which is equivalent to the above The predicates to declare sets are Set Lwb Upb Set is an integer set within the given bounds intset Set Min Max Set is a set containing numbers between Min and Max intsets Sets N Min Max Sets is a list of N sets containing num bers between Min and Max 5 2 2 Printing Set variables are by default printed in a particular way e g X 2 3 1 2 3 4 write X X 2 3 V O 1 4 _308 2 41H The curly brackets contain 1 the lower bound of the set 2 the union symbol 3 the set of optional values that may or may not be in the set 4 a colon 5 a finite domain indicating the admissible cardinality for the set 5 2 3 Domain Access potential members Set List List is the list of elements of whose mem bership in Set is currently uncertain set range Set Lwb Upb Lwb and Upb are the current lower and upper bounds on Set 5 3 Constraints 5 3 1 Membership X in Set The integer X is member of the integer set Set X notin Set The integer X is not a member of the integer set Set membership booleans
109. ing labeling 8 7 Writing Good CHR Programs This section gives some programming hints For maximum efficiency of your constraint handler see also the subsection on options especially on check guard bindings and the debug compile flag 8 7 1 Choosing CHRs Constraint handling rules for a given constraint system can often be derived from its definition in formalisms such as inference rules rewrite rules se quents formulas expressing axioms and theorems CHRs can also be found by first considering special cases of each constraint and then looking at interactions of pairs of constraints sharing a variable Cases that don t occur in the application can be ignored CHRs can also improve appli cation programs by turning certain predicates into constraints to provide short cuts lemmas For example to the predicate append 3 one can add append L1 L2 lt gt L1 L2 together with label with append L1 L2 L3 if true Starting from an executable specification the rules can then be refined and adapted to the specifics of the application Efficiency can be improved by strengthening or weakening the guards to perform simplification as early as needed and to do the just right amount of propagation Propagation rules can be expensive because no constraints are removed If the speed of the final handler is not satisfactory it can be rewritten using meta terms or auxiliary C functions The rules for a constraint can be scattered a
110. ints declaration The available values are from 1 to 11 The old CHR built ins chr get constraint 1 and chr get constraint 2 are both implemented in this library A new built in predicate in chrstore 1 is used to inspect the constraint store in_chrstore Constraint is used to test if Constraint is in the constraint store or not It can be used to prevent the addition of redundant constraints X leq Y Y leq Z gt in_chrstore X leq Z X leq Z The above usage is only useful if the already_in_store option is off Note that as the state of a constraint that appears in the head is not defined in the guard it is strongly suggested that the user does not perform this test in the guard for such constraints 8 9 6 Compiler generated predicates A source to source transformation is performed on CHR code by the compiler and the resulting code is compiled in the same module as the CHR code These transformed predicates all begin with CHR so the user should avoid using such predicates 74 Chapter 9 EPLEX The ECL PS LP MIP Interface 9 1 Usage This library allows the use of an external mathematical programming LP MIP or quadratic solver from within ECL PS It provides a largely solver independent API to the programmer so many programs will run with any supported external solver See section 9 11 for more details on the supported solvers The most generic way to load the library is lib ep
111. is possible to repair certain constraints automatically by re computing one or more of their variable s tentative values based on the others e g a sum constraint can be repaired by updating the tentative value of the sum variable whenever the tentative value of one of the other variables changes We provide two predicates for this purpose Result tent is Expression This is similar to the normal arithmetic is 2 predicate but evaluates the expression based on the tentative assignment of its variables The result is delivered as an update to the tentative value of the Result variable Once initiated tent is will stay active and keep updating Results tentative value eagerly whenever the tentative assignment of any variable in Expression changes tent call In Out Goal This is completely general meta predicate to support computations with tentative values Goal is a general goal and In and Out are lists or other terms containing subsets of Goal s variables A copy of Goal is called with the In variables replaced by their tentative values and the Out variables replaced by fresh variables Goal is expected to return values for the Out variables These values are then used to update the tentative values of the original Out variables This process repeats whenever the tentative value of any In variable changes 108 Waking on Tentative Assignment Change The predicates tent is 2 and tent call 3 are implemented using the ga chg
112. ke any choices sum V1 V2 V3 Comp1 Comp2 Profit V1 Viii 9 V2 v2 1 9 V3 V3 1 9 Compi Compi 3 57 Comp2 Comp2 3 57 Profit Profit 3 15 There are 9 delayed goals Yes 0 01s cpu Using the second version of sum it is simple to write a program which produces lists of products which use less than a given number Maxi and Max2 of each component and yields more than a given profit MinProfit solve Products Batch Max1 Max2 MinProfit length Products Batch Compi lt Maxi Comp2 lt Max2 Profit gt MinProfit sum Products Comp1 Comp2 Profit labeling Products 51 The following query finds which products to manufacture in order to make a profit of 40 without using more than 95 of either kind of component solve P 9 95 95 40 P 2 15 4 5 b 5b b 5 5b 5 Yes 0 03s cpu solution 1 maybe more Constraints can be dropped as soon as they became redundant i e as soon as they were entailed by the current partial solution The check for entailment can be expensive so Propia only drops constraints if a simple syntactic check allows it For infers most this check succeeds if the IC library is loaded and the constraint has only one remaining variable 7 3 Approximate Generalised Propagation The syntax Goal infers most can also be varied to invoke different levels of Generalised Propagation Other alternatives are Goal infers ic Goal infers unique
113. lex This will try to load an appropriate external solver available on the com puter It is also possible to request a specific solver explicitly see section 9 11 for details Note that the ECL PS library described here is just an interface to an external solver In order to be able to use it you need to have access to a solver supported by the library For commercial solvers this requires a licence for the solver on your machine For more details see section 9 11 For open source solvers the required solver library may be distributed with ECL PS if its licence allows this 9 2 Eplex Instances In this chapter the problem passed to the external solver will be referred to as an eplex problem An eplex problem consists of a set of linear arithmetic constraints whose variables have bounds and may possibly have integrality constraints The external solver will solve such a problem by optimising these constraints with respect to an objective function 75 With the eplex library it is possible to have more than one eplex problem within one program The simplest way to write such programs with the library is through Eplez Instances An eplex instance is an instance of the eplex solver to which an eplex problem can be sent An external solver state can be associated with each eplex instance which can be invoked to solve the eplex problem Declaratively an eplex instance can be seen as a compound constraint consisting of
114. ling rules In First Workshop on the Principles and Practice of Constraint Programming Newport RI USA April 1993 T Friihwirth Theory and practice of constraint handling rules Logic Programming 37 1 3 95 138 1988 C Gervet Interval propagation to reason about sets Definition and im plementation of a practical language Constraints 1 3 191 244 1997 131 11 12 13 14 15 16 18 19 20 C Holzbauer OFAI clp q r Manual Technical Report TR 95 09 Austrian Research Institute for AI Vienna 1995 ILOG CPLEX www ilog com products cplex 2001 C Le Pape and P Baptiste Resource constraints for preemptive job shop scheduling Constraints 3 4 263 287 1998 T Le Provost Approximate Generalised Propagation ESPRIT Project Deliverable CORE 93 7 also as CHIC WP5 D 5 2 3 3 ECRC GmbH January 1993 T Le Provost and M G Wallace Domain independent propagation or Generalised Propagation In Proceedings of the International Confer ence on Fifth Generation Computer Systems FGCS 92 pages 1004 1011 June 1992 T Le Provost and M G Wallace Generalized constraint propagation over the CLP Scheme Journal of Logic Programming 16 3 4 319 359 July 1993 Special Issue on Constraint Logic Programming Olivier Lhomme Arnaud Gotlieb Michel Rueher and Patrick Tail libert Boosting the interval narrowing algorithm In Joint Interna tional Conference and Symposium on Logic Pr
115. ly Var needs to be of type integer get domain Var Domain Returns a ground representation of the cur rent IC domain for Var get domain as list Var Domain Returns a list of all the elements in the IC domain for Var Currently Var needs to be of type integer get median Var Median Returns the median of the interval of Var get delta Var Delta Returns the width of the interval of Var is in domain Var Value Succeeds if and only if Value is contained in the current domain of Var is in domain Var Value Result Binds Result to yes no or maybe depending on whether Value is in the current domain of Var delayed goals number Var Number Returns the number of delayed goals suspended on the IC attribute This approximates the number of IC constraints that Var is involved in 24 3 2 8 Propagation threshold predicates With interval constraint propagation it is sometimes useful to limit prop agation for efficiency reasons In IC this is controlled by the propagation threshold The way it works is that for non integer variables bounds are only changed if the absolute and relative changes of the bound exceed this threshold i e small changes are suppressed This means that constraints over real variables are only guaranteed to be consistent up to the current threshold over and above any normal widening which occurs Note that a higher threshold speeds up computations but reduces precision and may in the extreme ca
116. ly access the solver state instead of going through the abstraction of the eplex instances This section describes lower level operations like how to set up solvers manually In fact these lower level predicates are used to implement the predicates provided with eplex instances 86 These predicates accesses the external solver state via a handle which is returned when the solver state is set up and subsequently used to access a particular solver state by the other predicates The handle should be treated as a opaque data structure that is used by the eplex library to refer to a particular solver state 9 4 1 Setting Up a Solver State lp_demon_setup Objective Cost ListOfOptions TriggerModes Handle This is used to set up a demon solver and eplex solver setup 4 calls this predicate There is one extra argument compared to eplex_solver_setup 4 the solver state handle Handle which is returned by this predicate when the new solver state is created The other arguments are the same as in eplex solver setup 4 except that there is an additional option in ListOfOptions collect from 1 This is used to specify which if any eplex instance the solver state should be collecting constraints from If an eplex instance is specified as pool Instance then the solver state is as sociated with that instance If the eplex instance is not to be associated with an eplex instance none should be given as the argument to collect from This
117. ments as op 3 in ECL PS However while the usual operator declara tions are ignored during compilation from chr to pl files the CHR operator declarations are taken into account see also the subsection on clauses The optional label with declaration specifies when the ECL PS clauses of a constraint can be used for built in labeling see subsection on labeling Example contd The first lines of the minmax handler are declarations handler minmax constraints leq 2 neq 2 minimum 3 maximum 3 operator 700 xfx leq operator 700 xfx neq 8 5 2 ECL PS Clauses A constraint handler program may also include arbitrary ECL PS code written with the four operators 1 2 and 1 2 Clause Head Body Head Body u Body Body Note that 1 and 1 behave different from each other in CHR pro grams Clauses starting with are copied into the pl file by the CHR compiler clauses with are executed by the compiler As the op decla ration needs both copying and execution we have introduced the special operator declaration see previous subsection on declarations A Head can be a Constraint such clauses are used for built in labeling only see section on labeling 8 5 3 Options The option command allows the user to set options in the CHR compiler Option option Option On or off Options can be switched on or off Default is on Advanced users may switch
118. n 8 The Constraint Handling Rules Library 8 1 Introduction 2 5 2 ee ah x ok y ko EK Pe ee BG 8 2 Using Constraint Handling Rules oo core 8 3 Example Constraint Handlers 84 The CHR Language 22 22 nn nennen 8 4 1 Constraint Handling Rules 84 2 How CHRs Work 22 22 oo onen 8 5 More on the CHR Language 8 5 Declarations rs 8 5 2 ECL PS Owen siehe te 8 5 3 Options os lox en x os en 85 4 CHR Built In Predicates les 8 6 Labeling eb eA ee BE TUTTI 8 7 Writing Good CHR Programs 8 7 1 Choosing CHRg nme 8 7 2 Optimizationg 2 22 Coon 8 8 Debugging CHR Programs 0 000085 8 8 1 Using the Debugger 8 9 The Extended CHR Implementation 8 9 1 Invoking the extended CHR library 8 9 2 Syntactic Differences 2 2 2222 8 9 3 Compilng een 8 99 4 Semantics oo moon 8 9 5 Options and Built In Predicates 8 9 6 Compiler generated predicates 9 EPLEX The ECL PS LP MIP Interface 9 1 Ms ge rri ndo Rec x Ro Di eiai badk y e Sov m Ro 9 2 Eplex Instances
119. n Vars may be a variable or a collection of variables la collection to list 2 Domain can be specified as a simple range Lo Hi or as a list of subranges and or individual ele ments Multiple subranges and or individual elements are allowed in integer domains only If all subrange bounds and individual elements are integers the domain is considered an integer domain and the vari ables Vars are constrained to be integral otherwise it is considered a real domain and the type of the variables is not constrained Also allowed are the untyped symbolic bound values inf inf and inf 18 Vars Domain Bool Provides a reified form of the 2 domain assign ment predicate This reified 3 is defined only to work for one vari able and only integer variables unlike 2 hence only the Domain formats suitable for integers may be supplied to this predicate For a single variable V the Bool will be instantiated to 0 if the current domain of V does not intersect with Domain It will be instantiated to 1 iff the domain of V is wholly contained within Domain Finally the Boolean will remain an integer variable in the range 0 1 if neither of the above two conditions hold Instantiating Bool to 1 will cause the constraint to behave exactly like 2 Instantiating Bool to 0 will cause Domain to be excluded from the domain of all the variables in Vars where such an exclusion is representable If such an integer domain is unrepresentabl
120. n the guard and the body Several handlers can be used simultaneously if they don t share user defined constraints The current implementation will not work correctly if the same constraint is defined in rules of different handlers that have been compiled separately In such a case the handlers must be merged by hand This means that the source code has to be edited so that the rules for the shared constraint are together in one module Changes may be necessary like strengthening guards to avoid divergence or loops in the computation 67 Constraint handlers can be tightly integrated with constraints defined with other extensions of ECL PS e g meta terms by using the ECL PS built in predicate notify constrained Var to notify ECL PS each time a vari able becomes more constrained This happens if a user defined constraint is called for the first time or if a user defined constraint is rewritten by a CHR into a stronger constraint with the same functor For pretty printing of the user defined constraints in the answer at the top level and debuggers ECL PS macro transformation for write mode can be used This is especially useful when the constraints have some not so readable notation inside the handler For an example see the constraint handler bool bool chr 8 8 Debugging CHR Programs User defined constraints including application of CHRs can be traced with the standard debugger Debugging of the ECL PS code is done in t
121. nd are active and have the add initially status set These can be over ridden by the Options argument The predicate returns a list of indices for these constraints in Idxs Information on cutpool constraints can be obtained using the cutpool_info option of Ip_get 3 The status of a cutpool constraint such as its active status can be set using the cutpool_option option of Ip set 3 the change is non logical i e it is not undone on backtracking Using lp get 3 and lp set 3 the user can program their own algorithms to control how the cutpool constraints are treated when the problem is solved For example the user may want to make a whole group of constraints inactive because they seem to slow the solver down but do not produce better solutions In this case the user can use lp get 3 to obtain all the current constraints in the group and then use lp set 3 to set these constraints to inactive As cutpool constraints are not added directly to the problem matrix this affects the library predicates that deals with the problem state e row wise solution states like dual and slack values include only the cutpool constraints that are actually added to the problem These are added after the normal constraints and their order in the matrix can be obtained using the cutpool info last added index option of Ip get 3 93 e the constraints and constraints norm options of lp get 3 returns only the normal constraints Other options
122. nequality true and so 6 is removed from the domain of ST1 By a similar reasoning 4 and 5 are removed from the domain of ST2 We next take a simple example from propositional logic In this example the result of constraint propagation is reflected not only in the variable domains but also in the unification of problem variables We first define logical conjunction by its truth table 49 land true true true land true false false land false true false land false false false Now we ask for an X Y Z satisfying land X Y Z X Y Both solutions have X Y Z and this information is produced solely by propagating on the land constraint land X Y Z infers most X Y Z kX X X Y X There is 1 delayed goal Yes 0 00s cpu We now illustrate the potential efficiency benefits of Generalised Propagation with a simple resource allocation problem company makes 9 products each of which require two kinds of components in their manufacture and yields a certain profit This information is held in the following table product Name Component1 Component2 Profit product 1 1 19 1 product 2 2 17 2 product 3 3 15 3 product 4 4 13 4 product 5 10 8 5 product 6 16 4 4 product 7 17 3 3 product 8 18 2 2 product 9 19 1 1 We wish to find which products to manufacture in order to make a certain profit without using more than a certain number of either kind of compo nent We fi
123. ng the underlying suspend library 1 6 Repair The repair library allows a tentative value to be associated with any variable 22 This tentative value may violate constraints on the variable in which case the constraint is recorded in a list of violated constraints The repair library also supports propagation invariants 18 Using invariants if a vari able s tentative value is changed the consequences of this change can be propagated to any variables whose tentative values depend on the changed one The use of tentative values in search is illustrated in the ECL PS Tutorial on Search Methods The ic library replaces the old ria interval solver and covers most of the functionality of the finite domain solver fd 1 7 Linear Constraints There are two libraries supporting linear constraint solving The first eplex provides an interface to external linear programming packages It offers flexibility and scalability but may require a license for the external software The second cipgr can support infinite precision but is less efficient and scalable and offers fewer facilities 1 7 1 External Linear Solvers eplex eplex supports a tight integration 3 between external linear solvers CPLEX 12 and XPRESS 19 and ECL PS Constraints as well as variables can appear in both the external linear solver and other ECL PS solvers Vari able bounds are automatically passed from the ECL PS range solver to t
124. ns ExprX ExprY ExprX is equal to ExprY ExprX and ExprY are con strained to be integer expressions ExprX gt ExprY ExprX is greater than or equal to ExprY ExprX and ExprY are constrained to be integer expressions ExprX lt ExprY ExprX is less than or equal to ExprY ExprX and ExprY are constrained to be integer expressions ExprX gt ExprY ExprX is greater than ExprY ExprX and ExprY are constrained to be integer expressions ExprX lt ExprY ExprX is less than ExprY ExprX and ExprY are con strained to be integer expressions ExprX ExprY ExprX is not equal to ExprY ExprX and ExprY are constrained to be integer expressions ac eq X Y C Arc consistent implementation of X Y C X and Y are constrained to be integer variables and to have reasonable bounds C must be an integer 20 The comparison constraints 2 gt 2 lt 2 and 2 have the same syntax as the standard ECL PS built in comparison operators and those of other constraint solvers Unless explicitly qualified the ECL PS built ins are used To use these constraints without the need to qualify them use the alternative dollar syntax 3 2 3 Reified constraints As mentioned earlier when constraints appear in an expression context then they evaluate to their reified truth value Practically this means that the constraints are posted in a passive check but do not propagate mode whereby no variable domains are modified but
125. nswer This is the principle behind the bounded real arithmetic type Note that interval arithmetic does not guarantee small errors it just provides a way of knowing how large the error may have become One drawback of the interval approach is that arithmetic comparisons can no longer always be answered with a simple yes or no sometimes the only possible answer is don t know This is reflected in the behaviour of arithmetic comparators gt etc when applied to bounded reals which overlap each other In such a case one cannot know whether the true value of one is greater than less than or equal to the other and so a delayed goal is left behind This delayed goal indicates that the computation 13 succeeded contingent on whether the condition in the delayed goal is true For example if the delayed goal left behind was 0 2 0 4 gt 0 1 0 3 this indicates that the computation should be considered a success only if the true value represented by the bounded real on the left is greater than or equal to that of the bounded real on the right If the width of the intervals in any such delayed goals is non trivial then this indicates a problem with numerical accuracy It is up to the user to decide how large an error is tolerable for any given application 3 1 5 Interval arithmetic and IC In order to ensure the soundness of the results it produces the IC solver does almost all computation using interval arithmetic As
126. nt an error and abort The default behaviours can be overridden for each problem by giving a user defined goal to handle each case during problem setup in eplex solver setup 4 Ip setup 4 lp_demon_setup 5 or later with eplex set 2 or lp set 3 as an option If given the user defined goal will be executed instead The user de fined handler could for instance change parameter settings and call Ip solve again The default behaviour is implemented by raising the events eplex suboptimal eplex unbounded eplex unknown and eplex abort for the different abort cases These events can themselves be redefined to change the default be haviours However as this changes the behaviour globally it is not recom mended Note that in the user defined handlers it may be possible to extract some useful bound information on the optimal objective value using the best bound and worst bound options of Ip get 3 96 9 10 Solver Behaviour Differences In general an MP problem can have more than one optimal solution i e different sets of assignments to the problem variables that gives the optimal objective value Any of these solutions is correct and the external solver will return one of them It is possible for a different solver or even a different version of the same solver to return another of these solutions If the user s program uses the solution values then it is possible that the detailed behaviour of the program could depend on the solv
127. nvoking and Using Propia Propia is an ECL PS library loaded by calling lib propia A goal such as member X 1 2 3 is turned into a constraint by annotat ing it using the infers operator The second argument of infers defines how much propagation should be attempted on the constraint and will be de scribed in section 7 3 below In this section we shall use Goal infers most which infers as much information as possible given the loaded constraint solvers If the IC solver is loaded then IC information is extracted and Propia reduces the domains to achieve arc consistency We first show the behaviour of the original goal member X 1 2 3 X 1 Yes 0 00s cpu solution 1 maybe more X 2 Yes 0 02s cpu solution 2 maybe more X 3 Yes 0 02s cpu solution 3 Constraint propagation is invoked by infers most lib ic member X 1 2 3 infers most X X 1 3 Yes 0 00s cpu Note that the information produced by the constraint solves the correspond ing goal as well The constraint can thus be dropped In case there remains information not yet extracted the constraint must delay so that completeness is preserved member X Y infers most X X Y H3 T3 Delayed goals member X H3 T3 infers most yes 48 Propia copes correctly with built in predicates such as gt and lt so after compiling this simple program notin3to6 X X lt 3 notin3to6 X X gt 6
128. ocated for the session to be freed To free all resources associated with a session all cursors of the session should also be closed with cursor close 1 session commit Session If executed outside the scope of a session transaction 2 goal this commits any transactional updates to the database made within Session Otherwise it simply succeeds without doing anything session rollback Session If executed outside the scope of a session transaction 2 goal this undoes all transactional changes made to the database since the last commit for this session Otherwise it will simply abort the complete outer transaction Note not all changes can be rolled back consult the DB manual for details 1Some databases supports both transactional and non transactional updates and not all updates can be rolled back Consult the database manual for more details 118 session transaction 4 Session Goal This executes Goal as a database transaction This predicate is only useful if the database supports transactions Data base updates within Goal are committed if Goal succeeds if Goal fails or aborts the updates are rolled back Calls of this predicate can be nested but only the outermost transaction is real All the inner transactions are simply equivalent to call Goal This way it is possible to write a call to session transaction 2 into some code that implements a simple update but then to include that simple update into a larger
129. ogramming pages 378 392 1996 L Michel and P Van Hentenryck Localizer modeling language for local search Lecture Notes in Computer Science 1330 1997 Dash Optimization XPRESS MP www dash co uk 2001 P Van Hentenryck D McAllester and D Kapur Solving polynomial systems using a branch and prune approach SIAM Journal on Numer ical Analysis 1995 Pascal Van Hentenryck Constraint Satisfaction in Logic Programming Logic Programming Series MIT Press Cambridge MA 1989 M G Wallace and J Schimpf Finding the right hybrid algorithm a combinatorial meta problem Annals of Mathematics and Artificial Intelligence 34 4 259 270 2002 132
130. on Cursor SQL select count id from accounts where ID and balance lt overdraft session sql prepare query Session a 0 c 0 SQL 1 Cursor check overdraft limit Check Account cursor next execute Check a Account cursor next tuple Check c Count Count O The check overdraft limit 2 predicate uses the cursor to check an account This cursor can be re used to check any number of accounts 123 Index lt 2 ic 20 gt 2 ic 20 gt 2 ic 20 272 fd sets 38 ic 18 278 ic 19 lt 2 ic 20 gt 2 n2 21 zum ic 20 2 ic 20 lt 2 ic 20 lt gt 2 B lt 2 D gt 2 ic 20 gt 2 ic 20 2 fd_sets 39 u 2 ic 19 lt 2 12 ic 20 gt 2 BR 2 12 eplex 77 ic 20 eplex 77 ic 20 2 ic 20 amp lt 2 ic symbolic 44 amp 2 ic_symbolic amp lt 2 ic_symbolic amp gt 2 ic_symbolic amp gt 2 124 ic symbolic amp 2 ic symbolic ac eq 3 20 all disjoint 1
131. onstant amount of resource then the sum of resource usage of all the tasks does not exceed ResourceLimit at any time profile Start Times Durations Resources Profile StartTimes Durations Resources and Profile are lists of equal length 34 N of integer variables or integers with the same meaning as in cumu lative 4 The list Profile indicates the level of resource usage at the starting point of each task 4 3 Edge finder The libraries ic edge finder and ic edge finder3 implement stronger ver sions of the disjunctive and cumulative scheduling constraints They employ a technique known as edge finding to derive stronger bounds on the starting times of the tasks The library is loaded using either use module library ic edge finder to get a weaker variant with quadratic complexity or use module library ic edge finder3 to get a stronger variant with cubic complexity disjunctive Start Times Durations A disjunctive scheduling constraint Start Times and Durations are lists of equal length N of integer variables or integers The declarative meaning is that the N tasks with certain start times and duration do not overlap at any point in time cumulative StartTimes Durations Resources ResourceLimit A cumulative scheduling constraint StartTimes Durations and Re sources are lists of equal length N of integer variables or integers Re sourceLimit is an integer The declarative meaning is If there
132. onstraints These constraints are known as expand able constraints The as yet unspecified component involve variables that have not yet been added to the problem When these variables are added coefficients for the variables can be added to the expandable constraints as well as the objective function These primitives are the basis for implement ing column generation and are used by the column generation library lib colgen These primitives modify an existing eplex problem non monotonically and can only be used on problems that are not represented by an eplex instance and was not setup as a demon solver i e no trigger conditions are specified Ip add constraints 4 Handle Constraints Ints Idxs This adds expandable constraints Constraints to the solver state represented by Handle The predicate returns a list of indices for these constraints in Idxs The indices are used to refer to the constraints when new variables are added to expand the problem Ip add columns 4 Handle Columns This expands the problem by adding new variables columns to the solver state represented by Handle Columns is a list of variable column specification pair where variable is the variable to be added as a new column and column specification the specification for the non zero components of the column ie coefficients for the expandable constraints referred to using the index obtained from lp add constraints 4 and the objective for this
133. or built in labeling When displayed each constraint is labeled with a unique integer identifier Each rule is labeled with its name as given in the chr source using the operator If a rule does not have a name it is displayed together with a unique integer identifier 8 9 The Extended CHR Implementation A new extended chr library has been developed with the intention of providing the basis for a system that will allow more optimisations than the previous implementation At the same time some of the syntax of the CHR has been changed to conform better to standard Prolog The system is still experimental and provides no special support for debug ging CHR code Please report any problems encountered while using this system The main user visible differences from the original chr library are as follows e The extended library produces code that generally runs about twice as fast as the old non debugging code It is expected that further improvements should be possible e CHR code is no longer compiled with a special command the normal compile command will now recognise and compile CHR code when the extended chr library is loaded No intermediate Prolog file is produced The chr extension is no longer supported implicitly e Syntax of some operators have been changed to conform better to standard Prolog e A framework for supporting more than two head constraints has been introduced However support for propagation rules with
134. owever it guarantees that there are no solutions out side these ranges Note that since variables by default range from minus to plus infinity we could have written the above example as eclipse 2 sqr X 7 X X gt 0 X X 2 1925824014821353 2 1925824127108307 Delayed goals yes If too little information is given the interval propagation may not be able to infer any interesting bounds eclipse 2 sqr X 7 X X X 1 0Inf 7 0 Delayed goals yes 3 2 10 Reducing Ranges Further There are two methods for further domain reduction They both rely on search and splitting the domains There are two parameters to specify how domains are to be split The Precision parameter is used to specify the minimum required precision i e the maximum size of the resulting intervals in either absolute or relative terms Note that the propagation threshold section 3 2 8 needs to be one or several orders of magnitude smaller than precision otherwise the solver may not be able to achieve the required precision The lin log parameter guides the way domains are split If it is set to lin then the split is in the arithmetic middle If it is set to log the split is such as to have roughly the same number of floats to either side of the split This is to take the logarithmic distribution of the floats into account If the ranges of variables at the start of the squashing algorithm are known not to span several orders of ma
135. part of this the first thing done to a constraint when it is given to the solver is to convert all non integer numbers in it to bounded reals Note that for this conversion floating point numbers are assumed to refer to the closest representable float value as per the type conversion predicate breal 2 This lack of widening when converting floating point numbers to bounded reals is fine if the floating point number is exactly the intended real number but if there is any uncertainty that uncertainty should be encoded by using a bounded real in the constraint instead of a float One of the drawbacks of this approach is that the user is not protected from the fundamental inaccuracies that may occur when trying to represent decimal numbers with floating point values in binary T he user should be aware therefore that some numbers given explicitly as part of their program may not be safely represented as a bounded real that spans the exact decimal value e g X 0 1 or equivalently X is breal 0 1 This may lead to unexpected results such as eclipse 2 X 0 1 Y 0 09999999999999999 X gt Y X 0 1__0 1 Y 0 099999999999999992__0 099999999999999992 Yes 0 00s cpu eclipse 3 X 0 1 Y 0 099999999999999999 X gt Y No 0 00s cpu This potential source of confusion arises only with values which are explicitly given within a program By replacing the assignment to Y with an expression which evaluates to the same real val
136. programmer A number of features are designed to permit transfer of large amounts of data with minimal overhead e The buffered retrieval of multiple tuples from a relation or view e Buffered multiple updates and inserts e Re use of SQL statements that are parametrised with placeholders e Tuple templates to permit the allocation and re use of fixed size buffers The interface provides safe handles to database cursors Higher level inter faces can be constructed on top of this For example e Viewing an SQL query as a predicate that yields different tuples on backtracking e Viewing an SQL query as a lazily constructed list of tuples On backtracking cursors as well as database sessions are automatically closed This is required if one is to build abstractions where they are hidden from the programmer Nowhere in the interface are SQL commands ever looked into They are always passed straight from the user to the database This means that any SQL command supported by the underlying database will be accessible Note also any differences in the SQL between different databases are also 113 not hidden from the user so the SQL written by the user must be valid SQL for the database that is being interfaced to When retrieving or inserting tuples tuple templates are used to specify the types of the different fields being retrieved or inserted This allows for a flexible mapping between database internal types and the tuples retrieved
137. r of linear constraints set up ic_lin_prop The number of times a linear constraint is propagated ic_uni_prop ic_bin_prop ic_tern_prop The number of times a non linear unary binary ternary operator is propagated 28 ic split The number of domain splits in locate 2 3 4 ic squash The number of squash attempts in squash 3 or locate 4 Users who wish to track activity within their own programs may if they wish use the same mechanism New event types can be registered see below and actions recorded by calling the ic event Event predicate The counters are controlled using the primitives ic stat on ic stat off Enables disable collection of statistics Default is off ic stat reset Reset statistics counters ic stat print Print statistics counters to the standard output stream ic stat get Stat Returns a list of CounterName CounterValue pairs summarising the computation since the last reset ic event 4 Name Records the fact that the named event has happened ic stat register event Name 4 Description Registers a new event type and sets the counter to 0 This allows user defined predicates to record their own events within the same framework 3 3 General Guidelines for the Use of the IC li brary Whilst IC has been designed to provide a flexible consistent and yet powerful framework for many sorts of constraint satisfaction problems it can not be all things to all people There are circumstances under which IC
138. r one of its bounds the original bound consistency solver will not find any constraint unsatisfied All points X Y Y gt X lying within the intersection of 2 circles with radius 2 one centred at 0 0 the other at 1 1 eclipse 2 4 gt X 2 Y 2 4 gt X 1 2 Y 1 2 Y gt X Y X Y 1 0000000000000004 2 0000000000000004 X 1 0000000000000004 2 0000000000000004 Delayed goals yes The bound consistency solution does not take into account the X gt Y constraint Intuitively this is because it passes through the corners of the box denoting the solution to the problem of simply intersecting the two circles eclipse 2 4 gt X 2 Y 2 4 gt X 1 2 Y 1 2 Y gt X squash X Y 1e 5 lin 27 y gt x Squashing solution fee f Bound propagation solution Figure 3 1 Propagation with Squash algorithm example X 1 0000000000000004 1 4142135999632601 Y 0 41421359996326 2 0000000000000004 X Y Delayed goals yes 3 2 11 Obtaining Solver Statistics Using the facilities described in this section requires importing the ic kernel module Also since they depend on the internals of the IC library the details presented here are subject to change without notice Often it is difficult to know where the solver spends its time The library has built in counters which keep track of the number of times various events occur ic_lin_create The numbe
139. raint Handling Rules A constraint handling rule has one or two heads an optional guard a body and an optional name A Head is a Constraint A Constraint is an ECL PS callable term i e atom or structure whose functor is a declared constraint A Guard is an ECL PS goal The guard is a test on the ap plicability of a rule The Body of a rule is an ECL PS goal including constraints The execution of the guard and the body should not involve side effects like assert 1 write 1 for more information see the section on writing CHR programs A rule can be named with a RuleName which can be any ECL PS term including variables from the rule During de bugging see section 8 8 this name will be displayed instead of the whole rule There are three kinds of constraint handling rules Rule SimplificationRule PropagationRule SimpagationRule SimplificationRule RuleName Head Head lt gt Guard Body PropagationRule RuleName Head Head gt Guard Body SimpagationRule RuleName Head Head lt gt Guard Body Declaratively a rule relates heads and body provided the guard is true A simplification rule means that the heads are true if and only if the body is true propagation rule means that the body is true if the heads are true A simpagation rule is a combination of a simplification and propagation rule The rule Head1
140. raints over ordered symbolic do mains It is implemented on top of library ic see 3 by mapping symbolic domains to finite integer domains There are also several mixed domain constraints which have both symbolic and integer arguments 6 1 Domains and Domain Variables This library uses the domain feature provided by the ECLiPSe kernel This means that domains need to be declared The declaration specifies the domain values and their order For example local domain weekday mo tu we th fr sa su declares a domain with name weekday and values mo tu etc The do main values are implicitly ordered with mo corresponding to 1 until su corresponding to 7 Domain values must be unique within one ECLiPSe module i e a symbolic value can belong to at most one domain A variable of a declared domain can then be created using X amp weekday X Xi mo tu we th fr sa sul Yes 0 00s cpu or multiple variables using X Y Z amp weekday X Xi mo tu we th fr sa sul Y Y mo tu we th fr sa sul Z Z mo tu we th fr sa sul Yes 0 00s cpu 43 6 2 Basic Constraints The following constraints implement the basic relationships between two do main values The constraints require their arguments to come from identical domains otherwise an error is raised 7X amp Y X is the same as Y 7X amp Y X is different from Y 7X amp gt Y X is strictly
141. re is no gain in efficiency over using cursor next execute 2 transfer Session Amount FromAccount ToAccount SQL update accounts set balance balance where id Deduct is Amount session_sql_prepare Session incbal 1 0 12 SQL 2 Update Updates incbal Deduct FromAccount incbal Amount ToAccount cursor N execute Update 2 Updates The example shows how to re code the bank transfer predicate from cur sor next execute 2 to execute both updates with one call This could lead to some performance improvement in a client server setting for databases that supports multiple parameter tuples 11 4 3 Database Queries For database queries lib dbi provides predicates to execute SQL statements and extract the results returned by the database session sql query 4 or session sql query 5 executes an SQL statement returning a cursor to allow the results to be extracted from the database The predicates to do this are cursor next tuple 2 cursor all tuples 2 and cursor_N_tuples 4 121 The datatypes of the results tuple is specified by a template given to ses sion sql query 4 5 See section 11 3 for details on the templates session sql query 4 Session Template SQL Cursor This executes SQL and creates the handle Cursor for the SQL query Tem plate specifies the datatypes of the results tuples cursor next tuple Cursor Tuple A single tuple is retrieved from the databas
142. rg2 ArgN module foo Argi Arg2 ArgN Any terms found in the expression whose principle functor is not listed above will be replaced in the expression by a newly created auxiliary variable This same variable will be appended to the term as an extra argument and then the term will be called as call foo Argi Arg2 ArgN Aux If no lookup module is specified then the current module will be used This behaviour mimics that of is 2 eval Expr See section 3 1 7 for an explanation of eval 1 usage 17 eval The eval 1 wrapper inside arithmetic constraints is used to indicate that a variable will be bound to an expression at run time This feature will only be used by programs which generate their constraints dynamically at run time for example broken sum Xs Sum foreach X Xs fromto Expr S1 S2 0 do S1 X 52 Sum Expr The above implementation of a summation constraint will not work as in tended because the variable Expr will be treated like an IC variable when it is in fact the term X1 X2 which is constructed in the for loop In order to get the desired functionality one must wrap the variable Expr in an eval 1 working sum Xs Sum foreach X Xs fromto Expr 81 82 0 do S1 X 52 Sum eval Expr 3 2 Library Predicates 3 2 1 Domain constraints Vars Domain Constrains Vars to take only integer or real values from the domain specified by Domai
143. rnatively the cursor can be closed explicitly by cursor close 1 119 The datatypes of the parameters for the prepared statement is specified by a template given to session sql prepare 4 See section 11 3 for details on the templates session sql Session SQL RowProcessedCount This is the simplest interface to execute an SQL statement with no place holders make accounts Session session sql Session create table accounts id decimal 4 not null balance decimal 9 2 default 0 0 not null overdraft decimal 9 2 default 0 0 not null J icd session sql Session insert into accounts id balance values 1001 1200 0 1 session sql Session insert into accounts id balance values 1002 4300 0 1 In the example we see session sq1 3 used first to create a table and then to initialise it with two rows The rows processed counts are checked to make sure exactly one row is processed per statement This code assumes a session with handle Handle has been started before hand session sql prepare 4 Session Template SQL Cursor This creates Cursor which is a handle to the prepared statement possibly with placeholders Template specifies the types of the placeholders see section 11 3 transfer Session Amount FromAccount ToAccount SQL update accounts set balance balance where id Deduct is Amount session sql prepare Session incbal 1
144. rst define a predicate sum Products Comp1 Comp2 Profit which re lates a list of products eg Products 1 5 1 to the number of each component required to build all the products in the list and the profit for 1 5 1 Comp1 12 and Comp2 46 and Profit 7 sum 1 0 0 0 sum Name Products Counti Count2 Profit Counti Count2 Profit 0 100 product Name Ctia Ct2a Profita Counti Ctla Ctib 1To keep the example simple there is no optimisation 50 Count2 Ct2a Ct2b Profit Profita Profitb sum Products Ctib Ct2b Profitb If sum is invoked with a list of variables as its first argument eg V1 V2 V3 then the only choice made during execution is at the call to product In short for each variable in the input list there are 2 alternative products that could be chosen For a list of three variables there are consequently 9 729 alternatives If we assume a production batch of 9 units then the number of alternative ways of solving sum is 9 or nearly 400 million To avoid exploring so many possibilities we simply annotate the call to product Name Ct1a Ct2a Profita as a Generalised Propagation constraint Thus the new definition of sum is sum 0 0 0 sum Name Products Counti Count2 Profit Count1 Count2 Profit 0 100 product Name Ctla Ct2a Profita infers most Counti Ctlat Ctib Count2 Ct2a Ct2b Profit Profita Profitb sum Products Ctib Ct2b Profitb Now sum refuses to ma
145. s the MySQL client library is pro vided as a dynamic load library libmysqlclient so in most Unix systems lib mysql dll in Windows systems This file is not provided with ECL PS dis tribution as it is part of the MySQL system and is covered by its own license MySQL can be downloaded from http dev mysql com downloads To successfully load the dbi library in such cases you must have a version of this library file that match the one that your copy of ECL PS was compiled with and in addition ECL PS must be able to find this library file when the dbi library is loaded Normally the person who installed your ECL PS system should also make sure that ECL PS can find this client library file 114 using the normal way that the operating system can find dynamic load li braries e g by putting the file in a standard system library location or in the ECL PS dynamic library directory for the platform in your ECL PS directory On Unix systems it is also possible for the user to set an envi ronment variable usually LD_LIBRARY_PATH to point to where the dynamic library is 11 3 Data Templates If supported by the database the interface allows the use of prepared SQL statements with parameters placeholders Prepared SQL statements are pre parsed by the database and can be executed more efficiently for multiple times with the placeholders acting like variables taking on different values for each execution The syntax used for prep
146. s also possible to let the running program determine which solver to use In this case the program has a variable in the module position which will only be bound at runtime Solver A gt B This will however prevent the solver from performing any compile time pre processing on the constraint 2 4 The Solvers suspend This is the simplest possible solver Its behaviour is to wait until all variables in a constraint have been instantiated to numbers Then it performs a test to check whether the constraint is satisfied and fails if this is not the case ic A new hybrid solver combining integer and real interval constraint solv ing This solver is intended to replace the FD and the already dis continued RIA solver For more information please see chapter 3i eplex An interface to an LP or MIP solver i e it implements linear con straints over reals or integers arith This is not really a solver but just the implementation of simple arithmetic tests in module eclipse language These require that all variables are instantiated when the test is invoked The reason to list it here is that the proper solvers use the same syntax and can be considered generalisations of the traditional tests 10 Chapter 3 IC A Hybrid Finite Domain Real Number Interval Constraint Solver 3 1 Introduction The IC Interval Constraint library is a hybrid integer real interval arith metic constraint solver Its aim is to make i
147. se prevent the system from being able to locate individual solutions The default threshold is 1e 8 get threshold Threshold Returns the current propagation threshold set threshold Threshold Sets the propagation threshold Note that if the threshold is reduced using this predicate requiring a higher level of precision the current state of the system may not be consistent with respect to the new threshold If it is important that the new level of precision be realised for all or part of the system before computation proceeds set threshold 2 should be used instead set threshold Threshold WakeVars Sets the propagation threshold with re computation If the threshold has been reduced all constraints suspended on the bounds of the variables in the list WakeVars are woken 3 2 9 Solving by Interval Propagation Some problems can be solved just by interval propagation for example eclipse 9 X 0 0 100 0 sqr X 7 X X X 2 1925824014821353 2 1925824127108307 Delayed goals yes There are two things to note here e The solver typically does not instantiate real variables it only reduces them to narrow ranges e In general many delayed goals remain at the end of propagation This reflects the fact that the variable s ranges could possibly be further reduced later on during the computation It also reflects he fact that 25 e the solver does not guarantee the existence of solutions in the com puted ranges H
148. set bounds 4 Handle Var Lo Hi This updates the bounds for the problem variable Var in the external solver state represented by Handle Failure occurs if Var is not a problem variable 9 4 3 Running a Solver State Explicitly Ip solve 4 Handle Cost Apply the external solver s LP or MIP solver to the problem represented by Handle Precisely which method is used depends on the options given to lp setup 4 lp solve 2 fails if there is no solution or succeeds if an op timal solution is found returning the solution s cost in Cost unlike with Ip demon setup 6 Cost gets instantiated to a number After a success 88 various solution and status information can be retrieved using lp get 3 and Ip var get 4 The set of constraints considered by the solver is the one given when the solver was created plus any new constraints that were added e g by Ip add constraints 3 in the meantime If there was an error condition or limits were exceeded lp solve 2 raises an event See section 9 9 for details Ip probe Handle Probes Cost Similar to Ip solve 2 but optimize for a modified problem as specified by Probes This is the predicate called by eplex probe 2 9 4 4 Accessing the Solver State In section 9 3 1 we discussed how solver state information can be accessed via the eplex instance Here are the lower level predicates that directly access this information via the solver state s handle Ip
149. signment In contrast RIA will fail with a type error if bounded reals are used in either of these cases 3 1 4 Notes about interval arithmetic The main problem with using floating point arithmetic instead of real arith metic for doing any kind of numerical computation or constraint solving is that it is only approximate Finite precision means a floating point value may only approximate the intended real it also means there may be round ing errors when doing any computation Worse is that one does not know from looking at an answer how much error has crept into the computation it may be that the result one obtains is very close to the true solution or it may be that the errors have accumulated to the point where they are significant This means it can be hard to know whether or not the answer one obtains is actually a solution it may have been unintentionally included due to er rors or worse whether or not answers have been missed unintentionally excluded due to errors Interval arithmetic is one way to manage the error problem Essentially each real number is represented by a pair of floating point bounds The true value of the number may not be known but it is definitely known to lie between the two bounds Any arithmetic operation to be performed is then done using these bounds with the resulting interval widened to take into account any possible error in the operation thus ensuring that the resulting interval contains the true a
150. solver state when it is setup This mech anism makes it possible to interface to a non incremental black box solver that requires all constraints at once or to send constraints to the solver in batches 76 As with all predicates defined for an eplex instance these constraints should be module qualified with the name of the eplex instance In the following they are shown qualified with the eplex instance Other instances can be used if they have been declared using eplex instance 1 EplexInstance X Y X is equal to Y X and Y are linear expressions EplexInstance X gt Y X is greater or equal to Y X and Y are linear expressions EplexInstance X Y X is less or equal to Y X and Y are linear expressions 9 2 2 Linear Expressions The following arithmetic expression can be used inside the constraints X Variables If X is not yet a problem variable it is turned into one via an implicit declaration X 1 0Inf 1 0Inf 123 3 4 Integer or floating point constants Expr Identity Expr Sign change E1 E2 Addition sum ListOfExpr Equivalent to the sum of all list elements E1 E2 Subtraction E1 E2 Multiplication ListOfExpr1 ListOfExpr2 Scalar product The sum of the products of the corresponding elements in the two lists The lists must be of equal length 9 2 3 Bounds Bounds for variables can be given to an eplex instance via the 2 con straint 77 EplexIntance Vars Lo Hi
151. t convenient for programmers to write hybrid solutions to problems mixing together integer and real con straints and variables Previously if one wished to mix integer and real constraints one had to import separate solvers for each with the solvers using different represen tations for the domains of variables This meant any variable appearing in both kinds of constraints would end up with two domain representations with extra constraints necessary to keep the two representations synchro nised 3 1 1 What IC does IC is a general interval propagation solver which can be used to solve prob lems over both integer and real variables Integer variables behave much like those from the old finite domain solver FD while real variables behave much like those from the old real interval arithmetic solver RIA IC allows both kinds of variables to be mixed seamlessly in constraints since with a few exceptions the same propagation algorithms are used throughout and all variables have the same underlying representation indeed a real vari able can be turned into an integer variable simply by imposing an integrality constraint on it IC replaces the fd ria and range libraries Since IC does not support symbolic domains there is a separate symbolic solver library ic_symbolic 11 to provide the non numeric functionality of fd 3 1 2 Differences between IC and FD e IC supports real variables and constraints
152. t place any restrictions on the variables for other eplex instances or solvers Failure will occur only when inconsistency is detected within the same eplex instance unless the user explicitly try to merge the constraints from different solvers eplex instance A counterpart reals 1 constraint also exists this simply declares the variables specified are problem variables and does not actually place any other constraint on the variables 9 2 5 Solving Simple Eplex Problems In order to solve an eplex problem the eplex instance must be set up for an external solver state The solver state can then be invoked to solve the problem The simplest way to do this is to use EplexInstance eplex_solver_setup Objective This predicate creates a new external solver state and associates it with the eplex instance Any arithmetic integrality and bound constraints posted for this eplex 78 instance are collected to create the external solver state After this the solver state can be invoked to solve the eplex problem Objective is either min Expr or max Expr where Expr is a linear expression or quadratic if supported by the external solver EplexInstance eplex solve Cost Explicitly invokes the external solver state Any new constraints posted are taken into account If the external solver can find an optimal solution to the eplex problem then the predicate succeeds and Cost is instantiated to the optimal value If the problem is in
153. te In the case of passing data to the database and the data is too large for the database the exact behaviour is dependent on the database 117 11 4 Built Ins 11 4 1 Sessions These predicates deal with sessions as a whole A session is used to identify a connection to a database Associated to that session are a number of cursors These are handles to SQL statements which are currently being executed For example a query where only some of the matching rows have been fetched Database transactions where updates to the database are local to the session until committed and where uncommitted changes can be rolled back are supported if the external database supports transactions session start J Login Password Options Session This create a new session by establishing a new connections to the database server and associates it with a handle returned in Session The session remains in existence in subsequent goals It is automatically closed if the program fails or aborts back beyond this call The session is used as a access handle to the database in subsequent calls to this interface The automatic closure is particularly useful in case of a program aborting due to a runtime error Closing the database ensures any database updates that have not been committed will be undone session close Session This closes a session disconnecting from the database server It takes effect immediately This allow resources all
154. th declarations for a constraint Example contd label_with minimum X Y Z if true minimum X Y Z X leq Y Z X minimum X Y 2 Y lss X Z Y The built in labeling is invoked by calling the CHR built in predicate chr 1abeling O no arguments Once called whenever no more constraint handling is pos sible the built in labeling will choose a constraint goal whose label with declaration is satisfied for labeling It will introduce choices using the clauses of the constraint Example contd A query without and with built in labeling 64 eclipse minimum X Y Z maximum X Y W Z neq W X _g357 Y _g389 Z _g421 W _g1227 Constraints 1 minimum _g357 _g389 _g421 2 _g421 leq _g357 3 _g421 leq _g389 4 maximum _g357 _g389 _g1227 5 _g357 leq _g1227 7 _g389 leq _g1227 10 _g421 1ss _g1227 yes eclipse minimum X Y Z maximum X Y W Z neq W chr labeling X Z _g363 Y W _g395 Constraints 10 _g363 lss _g395 More X W _g363 Y Z _g395 Constraints 17 _g395 1ss _g363 yes Advanced users can write their own labeling procedure taking into account the constraints in the constraint store see next subsection for CHR built in predicates to inspect and manipulate the constraint store Example The predicate chr 1abeling O0 can be defined as labeling chr get constraint C chr label with C gt 65 chr resolve C label
155. that returns information about the problem e g num rows also do not include the cutpool constraints e eplex write 2 and lp write 3 will dump all the active cutpool con straints with the problem This may be different from the actual problem solved by the external solver because not all active cutpool constraints need be added to the problem and the order of these con straints could be different To dump the exact problem solved by the external solver use the write before solve option of the solver instead 9 6 Multiple Solver States This library allows multiple solver states to be maintained in the same pro gram Each solver state represents an eplex problem For the external solver each solver state is completely independent For ECL PS the solver states may share variables in the constraints or objective functions but the constraints posted to the problem and to the cutpools are specific to each solver state The eplex library maintains separate solution values for each solver state and it is up to the user to reconcile these solution values if they are different When two eplex variables are unified then the library ensures that the now single variable maintains the eplex values from both variables The one exception is when two variables from the same solver state is unified In this case eplex will merge its representations of the two columns into one the bounds of the columns are merged and failure will occur if the merged
156. the check guard bindings option Currently built in constraints used in a guard act as tests only see also the section on writing good CHR programs If the firing CHR is a simplification rule the matched constraint goals are removed and the body of the CHR is executed Similarly for a firing sim pagation rule except that the first head is kept If the firing CHR is a propagation rule the body of the CHR is executed and the next rule is tried It is remembered that the propagation rule fired so it will not fire again with the same partner constraint if the constraint goal is re activated If the constraint goal has not been removed and all rules have been tried it delays until a variable occurring in the constraint is touched Then the constraint is re activated and all its rules are tried again Example contd The following trace is edited rules that are tried in vain and redelay have been removed eclipse chr trace yes Debugger switched on creep mode eclipse notrace trace only constraints Debugger switched off yes eclipse minimum X Y Z maximum X Y 2 ADD 1 minimum X Y Z TRY 1 minimum g218 _g220 _g222 with propagation RULE propagation FIRED ADD 2 leq g665 _g601 ADD 3 leq g665 Var 60 ADD 4 maximum g601 Var g665 TRY 4 maximum g601 Var _g665 with propagation RULE propagation FIRED ADD 5 leq g601 _g665 TRY 5 leq _g601 _g665 2 leq _g665 _g601 wit
157. the solver s range an out of range error would be raised when this is detected and the problem is not passed to the external solver 95 In addition ECL PS supports numeric types that are not generally avail able e g bounded real and rational T hese are converted into floating point numbers before they are passed to the external solver 9 9 Error Handling The external solver s optimisation can abort without completely solving the problem because of some error or some resource limit was reached Eplex classifies these into the following cases with default ways of handling them suboptimal This means that a solution was found but it may be subopti mal The default behaviour is to print a warning and succeed unbounded This means that the problem is unbounded The default be haviour is to bind Cost to infinity positive or negative depending on the optimisation direction print a warning and succeed CAUTION No solution values are computed when the problem is unbounded so unless the problem was set up with the solution no option an error will occur when trying to continue as if the optimisation had succeeded unknown This means that due to the solution method chosen it is un known whether the problem is unbounded or infeasible The default behaviour is to print a warning and fail even though this may be logically wrong abort Some other error condition occurred during optimisation The de fault behaviour is to pri
158. tive constraint constraints chr labeling 0 at lower 1 this specifies that if chr labeling O was the active constraint then the rules will be executed at a lower priority than the default The priorities are mapped to the priority system of ECL PS and at lower 1 maps to a priority one lower than the default so that ECH rules executing at the default priority will execute first This is particularly useful for labelling as this allow the other ECH constraints to be executed during the labelling process rather than afterwards The priority specified can be at 1ower N at higher N orat absolute priority N For at lower N the priority is the default N for at higher N it is the default N at absolute priority N sets the priority to N regardless of the default and its use is not recommended The available priorities are from 1 highest to 11 lowest The default priority is initially set to 9 but can be changed with the chr priority option Note that the priority at which the rules will run at is determined at compile time and changing the default priority will only affect new constraints compiled after the change It should therefore only be used in a directive before any of the ECH rules This behaviour is different from the old chr library and from older versions of ech library where the rules ran at different priorities before and after suspension This can lead to different behaviours with the same rule either with
159. tting 43 domain 1 element 3 ic 23 ic ic_symbolic eplex 75 instance eplex_instance 1 Ip probe 3 89 presolve 8 3 eplex eplex get eplex add constraints 3 0 86 eplex_cleanup 2 101 91 101 eplex get 2 80 eplex_instance 1 epex 76 eplex_probe 2 82 85 99 89 eplex read 2 8l eplex set 2 81 101 eplex_solve 1 79 eplex_solver_setup 1 eplex_solver_setup 4 eplex var get 3 78 81 87 83 80 eplex write 2 81 94 eplex cplex 98 eplex xpress 9 8 equation solving exclude 2 31 exclude range existence of solutions geometric constraints 57 3 181 get_bounds 3 24 get_delta 2 ic 24 get domain 2 24 get domain as list 2 get domain size 2 get finite integer bounds 3 get float bounds 3 get ic attr 2 32 get integer bounds 3 24 get max 2 24 24 24 24 get median 2 ic 24 get min 2
160. ue we get eclipse 4 X 0 1 Y 0 1 0 000000000000000001 X gt Y 14 X 0 1__0 1 0 099999999999999992__0 1 lt Il Delayed goals ic 0 gt 1 3877787807814457e 17__ 0 0 Yes 0 00s cpu Note the delayed goal indicating the conditions under which the original goal should be considered to have succeeded 3 1 6 Usage To load the IC library into your program simply add the following directive at an appropriate point in your code lib ic 3 1 7 Arithmetic Expressions The IC library solves constraint problems over the reals It is not limited to linear constraints so it can be used to solve general problems like eclipse 2 1n X gt sin X X X10 36787944117144228 1 0Inf Delayed goals Yes 0 01s cpu The IC library treats linear and non linear constraints differently Linear constraints are handled by a single propagator whereas non linear con straints are broken down into simpler ternary binary unary propagators Any relational constraint gt etc can be reified simply by includ ing it in an expression where it will evaluate to its reified truth value User defined constraints may also be included in constraint expressions where they will be treated in a similar manner to user defined functions found in expressions handled by is 2 That is to say they will be called at run time with an extra argument to collect the result Note however that user de fined constraint
161. ules with two heads For example in the handler for set constraints set chr the propagation rule set union S1 S2 S set S1 S1Glb SiLub set S2 S2Glb S2Lub gt s union Si1Glb S2Glb SGlb s union SiLub S2Lub SLub set S SGlb SLub is translated into set union Si1 S2 S set S1 S1Glb SiLub gt set union S2 S1 S1Glb SiLub S set S2 S2Glb S2Lub set union S2 S1 S1Glb SiLub S lt gt s union Si1Glb S2Glb SGlb s union SiLub S2Lub SLub set S SGlb SLub As guards are tried frequently they should be simple tests not involving side effects For efficiency and clarity reasons one should also avoid using user defined constraints in guards Currently besides conjunctions disjunc tions are allowed in the guard but they should be used with care The use of other control built in predicates of ECL PS is discouraged Negation and if then else can be used if their first arguments are either simple goals see ECL PS user manual or goals that don t touch global variables Sim ilarly goals preceding a cut must fulfill this condition Built in constraints e g finite domains rational arithmetic work as tests only in the current implementation Head matching is more efficient than explicitly checking equalities in the guard which requires the check guard bindings flag to be on In the current implementation local variables those that do not occur in the heads can be shared betwee
162. user In effect the eplex instance is reinitialised Note that this is a non logical operation Backtracking into code before eplex cleanup O will not restore the solver state and any attempt to reuse the solver state will not be possible the execution will abort with an error Normally it is recommended to let ECL PS perform the cleanup automatically for instance when execution fails across the solver setup or when an unused solver state handle gets garbage collected However call ing eplex_cleanup 0 may cause resources memory and licence to be freed earlier 9 3 6 Eplex Instance Interface Example definition of opti mize 2 A black box setup and solve predicate optimize 2 can be defined as optimize ptExpr ObjVal eplex eplex_solver_setup OptExpr eplex eplex solve 0bjVal eplex eplex get vars VArr eplex eplex get typed solution SolutionVector VArr SolutionVector do the bindings eplex eplex_cleanup A solver state is set up for the eplex instance eplex to allow constraints that were previously posted to eplex to be collected This happens once the solver is invoked by eplex_solve 1 If there is a solution the solution vector is obtained and the variables are instantiated to those solutions 9 4 Low Level Solver Interface For many applications the facilities presented so far should be appropriate for using Simplex MIP through ECL PS However sometimes it may be more convenient or efficient to direct
163. value is in a domain is checked by communicating with a different solver that keeps that domain 10 2 Tentative Values 10 2 1 Attaching and Retrieving Tentative Values A problem variable may be associated with a tentative value Typically this tentative value is used to record preferred or previous assignments to this variable Vars tent set Values Assigns tentative values for the variables in a term These are typically used to register values the variables are given in a partial or initially inconsistent solution These values may be changed through later calls to the same predicate Vars can be a variable a list of variables or any nonground term Values must be a corresponding ground term The tentative values of the variables in Vars are set to the corresponding ground values in Values Vars tent get Values Query the variable s tentative values Values is a copy of the term Vars with the tentative values filled in place of the variables If a variable has no tentative value a variable is returned in its place 10 2 2 Tenability A problem variable is tenable when it does not have a tentative value or when it has a tentative value that is consistent e g with its finite domain For example eclipse 3 fd X 1 5 X tent set 3 X X fd 1 5 repair 3 produces a tenable variable note how the tentative value is printed as the variable s repair attribute while on the other hand eclipse 3 fd X 1 5 X tent
164. variable 9 4 6 Changing Solver State Settings In addition to accessing information from the solver state some options a subset of those specified during solver set up can be changed by 90 Ip set Handle 4 What Value This primitive can be used to change some of the initial options even after setup Handle refers to an existing solver state See the reference manual for details 9 4 7 Destroying a Solver State Ip cleanup 4 Handle Destroy the specified solver state free all memory etc If the solver state is associated with an eplex handle the solver state is disassociated with the eplex instance However unlike eplex cleanup 0 the outstanding con straints not yet collected by the solver is not removed As with eplex_cleanup 0 care should be taken before using this non logical predicate 9 4 8 Miscellaneous Predicates Ip read FFile Format Handle Read a problem from a file and setup a solver for it Format is 1p or mps The result is a handle similar to the one obtained by Ip setup 4 Ip write Handle Format File Write out the problem in the solver state represented by Handle to the file File in format Format normalise cstrs 4 Constraints NormConstraints NonlinConstr where Constraints is a list of terms of the form X Y X gt Y or X Y where X and Y are arithmetic expressions The linear constraints are returned in normalised form in NormConstraints the nonlinear ones are r
165. ve function We have already seen how extra constraints can be added As ECL PS is a logic programming language removal of constraints is automatically achieved by backtracking We do not allow the user to explicitly remove constraints that have been collected by the external solver as this makes the problem non monotonic For the same reason we do not allow the objective function to be changed However we do allow the problem including the objective function to be temporarily changed in certain specified ways This allows the problem to be probed with these changes EplexInstance eplex probe Probes Cost Similar to eplex solve 1 but the problem is first temporarily modified as specified in Probes before the optimisation The Cost value is instantiated to the objective value for this new modified problem and any solution state requested are also updated lHowever some monotonic changes are allowed in the low level interface for imple menting column generation see section 9 4 5 85 9 3 5 Destroying the Solver State EplexInstance eplex_cleanup Destroy the specified solver free all memory etc Note that ECL PS will normally do the cleanup automatically for instance when execution fails across the solver setup or when a solver handle gets garbage collected The solver is disassociated with the eplex instance and any outstanding constraints not yet collected by the solver are removed with a warning to the
166. vial if it en ables any variables in the goal to become further instantiated thus reducing search The background and motivation for Generalised Propagation is given in ref erences 15 14 16 This section focusses on how to use it Further examples of the use of Propia are distributed with ECL PS in the doc examples propia directory A simple demonstration of Propia in action on Lewis Carroll s Zebra problem can be run by compiling zebra pl and issuing the query lib ic zebra Houses ic An slightly more complex application of Propia to crossword generation can be run by compiling crossword Using Propia it is easy to take a standard Prolog program and with mini mal syntactic change to turn it into a constraint logic program Any goal Goal in the Prolog program can be transformed into a constraint by an notating it thus Goal infers most The resulting constraint admits just the same answers as the original goal but its behaviour is quite different Instead of evaluating the goal by non deterministically selecting a clause in its definition and evaluating the clause body Propia evaluates the resulting constraint by extracting information from it deterministically Propia ex 47 tracts as much information as possible from the constraints before selecting an ordinary Prolog goal and evaluating it In this way Propia reduces the number of choices that need to be explored and thus makes programs more efficient 7 2 I
167. whatever constraint solvers are loaded the others only infers information derived from the specified con straint solver Here s the same example using infers ic p X Y infers ic X f 35310 0 12 0 Y Y 1 2 There is 1 delayed goal Yes 0 00s cpu One rather special approximation langue is infers ac where ac stands for arc consistency This has similar semantics to infers ic but is im plemented very efficiently using the built in element constraint of the IC solver The limitation is that Goal infers ac is implemented by execut ing the goal repeatedly to find all the solutions and then manipulating the complete set of solutions It will only work in case there are finitely many solutions and they are all ground Finally it is possible to invoke Propia in such a way as to influence its waking conditions To do this use the standard suspend syntax For example forward checking can be implemented as follows propagate Goal fc suspend Goal 7 Goal gt inst infers most In this case the Propia constraint wakes up each time a variable in the goal is instantiated The default priority for Propia constraints is 3 However in the above example the priority of the Propia constraint has been set to 7 54 Chapter 8 The Constraint Handling Rules Library The chr library implements constraint handling rules CHRs It includes a compiler which translates CHR programs into ECL PS programs and a runt
168. wise all the remaining tuples are retrieved TupleList and Rest TupleList form a difference list containing these tuples Retrieved is the number of tuples retrieved 11 4 4 Parametrised Database Queries The library allow SQL queries to be prepared and parameterised if prepared SQL statements are supported by the underlying database Templates are needed for specifying the datatypes of the parame ters as with session sql prepare 4 and for the results tuples as with session sql query 4 An SQL query is prepared by ses sion sql prepare query 5 it then needs to be executed by cur sor next execute 2 or cursor next execute 3 cursor next execute 3 allows the specification of options for the cursor and the results can then be retrieved by cursor next tuple 2 cursor all tuples 2 and cur sor N tuples 4 After executing cursor next execute 2 it can be executed again with a new tuple of parameter values Any unretrieved results from the previous execute are discarded Note that this is non logical the discarded results are not recovered on backtracking session sql prepare query Session ParamT QueryT SQL Cursor This creates Cursor which is a handle to the prepared SQL query By changing the placeholders one gets a fresh query and can start extracting tuples again In this example a generic query is built to check whether an account is overdrawn and a cursor for this query is created make check overdraft limit Sessi

ECL PS Constraint Library Manual

Contents

Download Pdf Manuals

Related Search

Related Contents