1% BEGIN LICENSE BLOCK 2% Version: CMPL 1.1 3% 4% The contents of this file are subject to the Cisco-style Mozilla Public 5% License Version 1.1 (the "License"); you may not use this file except 6% in compliance with the License. You may obtain a copy of the License 7% at www.eclipse-clp.org/license. 8% 9% Software distributed under the License is distributed on an "AS IS" 10% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See 11% the License for the specific language governing rights and limitations 12% under the License. 13% 14% The Original Code is The ECLiPSe Constraint Logic Programming System. 15% The Initial Developer of the Original Code is Cisco Systems, Inc. 16% Portions created by the Initial Developer are 17% Copyright (C) 2006 Cisco Systems, Inc. All Rights Reserved. 18% 19% Contributor(s): Mark Wallace and Hani El Sakkout, IC-Parc 20% 21% END LICENSE BLOCK 22:- module(ic_probe). 23 24:- lib(ic). 25:- lib(repair). 26:- lib(eplex). 27:- use_module(ic_probe_support). 28 29:- export set_up_probe/5. 30:- export add_con/3. 31:- export set_probect/1, get_probect/1. 32 33:- local variable(probect). 34 35set_probect(X) :- 36 setval(probect,X). 37get_probect(X) :- 38 getval(probect,X). 39 40/* 41add_con(?Con,++Solvers,+Options) 42ConsList - a list of numeric equations or inequations: X=:=Y, X>=Y, X>Y, X=<Y, X<Y 43Solvers - A list of solvers - [ic,linear] or any subset 44Options - options structure 45 46The constraint is added to the listed solvers at one higher than the 47specified priority 48 49*/ 50 51add_con(ConsList,Solvers,Options) :- 52 Options = options with [granularity:Gran,priority:Priority], 53 handle_diseq(ConsList,Gran,NewConsList), 54 ThisPrior is Priority-1, 55 call_priority( 56 (foreach(Solver,Solvers),param(NewConsList) 57 do add_ineq(Solver,NewConsList) 58 ), 59 ThisPrior). 60 61handle_diseq(ConsList,Gran,NewConsList) :- 62 ( foreach(Cons,ConsList), 63 foreach(NewCons,NewConsList), 64 param(Gran) 65 do 66 diseq_to_ineq(Cons,Gran,NewCons) 67 ). 68 69diseq_to_ineq(X > Y, Gran, X >= Y+Gran) :- !. 70diseq_to_ineq(X < Y, Gran, X+Gran =< Y) :- !. 71diseq_to_ineq(Other,_,Other). 72 73add_ineq(ic,ConsList) :- 74 ( foreach(Cons,ConsList) 75 do 76 convert_to_type(ic,Cons,TypedCons), 77 ic:TypedCons 78 ). 79 80add_ineq(linear(Handle),ConsList) :- 81 lp_add_constraints(Handle,ConsList,[]). 82 83% If the following lines are uncommented, the number of probes 84% increases dramatically! 85 86 87%add_ineq(linear(Handle),ConsList) :- 88% term_variables(ConsList,Vars), 89% select_ic_vars(Vars,ICVars), 90% normalise_cstrs(ConsList,LinCons,[]), 91% lp_add(Handle,LinCons,ICVars), 92% lp_add(Handle,LinCons,[]), 93% ( test_tent(ConsList) -> true 94% ; 95% schedule_suspensions(lp_add), 96% wake 97% ). 98% 99%select_ic_vars(InVars,OutVars) :- 100% ( foreach(Var,InVars), 101% fromto([],This,Next,OutVars) 102% do 103% (is_solver_var(Var) -> Next = [Var|This] ; Next=This) 104% ). 105% 106%test_tent(ConsList) :- 107% ConsList tent_get GConsList, 108% ( foreach(GCons,GConsList) do (ground(GCons), call(GCons))). 109 110convert_to_type(ic,X=:=Y,X#=Y). 111convert_to_type(ic,X>=Y,X#>=Y). 112convert_to_type(ic,X=<Y,X#=<Y). 113 114 115 116/* 117set_up_probe(+Tasks,+Constraints,-Cost,++Options,-Handle) 118Tasks - A list of tasks using the task structure defined in probe_lib 119Constraints - A list of numeric equations and inequations, as above 120Cost - A variable, to be minimised during search 121Options - options structure 122 123set_up_probe simply adds all the constraints to the linear solver. 124They are added to the ic store as well - otherwise the cost 125never becomes constrained and min_max returns a cost of 0 immediately! 126 127The method must be primal as the dual becomes infeasible when a new 128constraint is added, and thus causes an error: 129Eplex: Optimization aborted (optimizer status = 3) in cplex_optimise... 130*/ 131 132set_up_probe(Tasks,Constraints,Cost,Options,Handle) :- 133 add_con(Constraints,[ic],Options), 134 eplex:integers([Cost]), 135 Options=options with priority:Priority, 136 Prior is Priority-1, 137 eplex:lp_demon_setup(min(Cost), 138 Cost, 139 [ initial_solve(no), 140 collect_from(none), 141 method(primal), 142 sync_bounds(yes), 143 priority(Priority), 144 presolve(no)], 145 [ suspension(Susp), 146 new_constraint, 147 pre(incval(probect)), 148 post(set_ans_to_tent(Handle))], 149 Handle), 150 set_up_deviating_bounds_demon(Tasks, Prior, Susp, Handle), 151 add_con(Constraints,[linear(Handle)], Options). 152 153set_ans_to_tent(Handle) :- 154 eplex:lp_get(Handle,vars,VarVector), 155 (foreacharg(Var,VarVector), param(Handle) do 156 eplex:lp_var_get(Handle, Var, solution, Sol0), 157 get_solver_type(Var, VType), 158 ( VType == integer -> 159 Sol is fix(round(Sol0)) 160 ; integer(Var) -> 161 Sol is fix(round(Sol0)) 162 ; 163 Sol0 = Sol 164 ), 165 Var tent_set Sol 166 ). 167 168set_up_deviating_bounds_demon( Tasks,Priority,Susp,Handle) :- 169 (foreach(task with [start:S,duration:D], Tasks), 170 fromto([],This,Next,List) 171 do Next =[S,D|This] 172 ), 173 (foreach(V, List), param(Priority,Handle,Susp) do 174 ( nonvar(V) -> true 175 ; is_solver_var(V) -> 176 lp_add_vars(Handle, [V]), 177 suspend(deviating_bounds_demon(V,Handle,Susp,OwnSusp), Priority, 178 [V->ic:min,V->ic:max], OwnSusp) 179 ; lp_var_occurrence(V, Handle, _) -> true 180 ; fail 181 ) 182 ). 183 184tolerance(1e-05). 185 186:- demon deviating_bounds_demon/4. 187deviating_bounds_demon(X, Handle, Susp, OwnSusp) :- 188 tolerance(Tol), 189 (lp_var_get(Handle, X, solution, Sol) -> 190 ic:get_bounds(X, Min, Max), 191 (Min-Tol =< Sol, Sol =< Max+Tol -> 192 schedule_suspensions(1, eplex([Susp])), 193 wake 194 ; 195 true 196 ), 197 (nonvar(X) -> kill_suspension(OwnSusp) ; true) 198 ; 199 true % no solution yet 200 ). 201 202:- comment(categories, ["Constraints","Techniques"]). 203:- comment(summary, "Probing"). 204:- comment(author, "Mark Wallace, Hani El Sakkout"). 205:- comment(date, "$Date: 2012/07/31 13:21:45 $"). 206:- comment(copyright, "Cisco Systems, Inc."). 207 208:- comment(desc, html("<P> 209 This implementation of probing is a call to an external linear solver, 210 whose optimal solution is assigned to the problem variables as tentative 211 variables. 212</P><P> 213A counter is created an initialised to zero. At every probe it is incremented. 214The counter can be set using <B>set_probect(N)</B>, and can be read using 215<B>get_probect(N)</B> 216</P>" ) 217 ). 218 219:- comment(set_up_probe/5, [ 220 summary : "Sets up a linear probe for a set of constraints", 221 amode : set_up_probe(+,+,-,++,-), 222 args :["Tasks" : "A term containing some variables", 223 "Constraints" :"A list of numerical constraints", 224 "Cost" :"A cost variable", 225 "Options" :"An options structure", 226 "Handle" :"A variable which will record the handle of the matrix 227used by the linear solver" 228 ], 229 resat :no, 230 see_also :[probe_cstr_sched/7,add_con/3,lp_demon_setup/5], 231 desc :html("<P> 232The constraints are passed to <B>add_con</B>, which adds them to both the 233ic and linear solvers. The cost is declared to be an integer. All the 234finite domain variables in the term <B>Tasks</B> are associated with a demon 235which forwards their bounds to the linear solver. (The priority of this 236demon is one higher than that of the probe.) 237</P><P> 238<B>lp_demon_setup</B> is then invoked to set up the linear solver, with the 239priority specified in the <B>Options</B> parameter. Solutions returned 240by the linear solver are automatically used to update the tentative values 241of all the variables. 242</P> 243"), 244 eg:" 245?- Options = options{granularity:3,priority:5}, 246 Cost=X1, 247 set_up_probe([X1,X2,X3],[X1>X2,X2>X3],Cost,Options,H). 248"]). 249 250:- comment(add_con/3 , [ 251 summary : "Add a constraint to the ic and linear solvers", 252 amode :add_con(+,++,+), 253 args :["Constraint": "A numerical constraint, with functor 254 '=:=', '>=', '=<', '>' or '<'", 255 "Options":"An options structure", 256 "Handle":"A linear solver handle" 257 ], 258 resat :no, 259 see_also :[set_up_probe/5], 260 desc :html(" <P> 261If the inequality is strict, <B>X>Y</B> or <B>X'<'Y</B>, then the granularity 262 specified in the options is added to the smaller term to create a non-strict 263 inequality, which can be passed to the linear solver. Thus if the granularity 264 is 3, then for <B>X>Y</B> the constraint <B>X>=Y+3</B> is added to the 265 linear solver and <B>X#>=Y+3</B> is added to the ic solver. 266</P> 267")]). 268 269 270