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