1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file sepa.c
17 * @ingroup OTHER_CFILES
18 * @brief methods and datastructures for separators
19 * @author Tobias Achterberg
20 * @author Timo Berthold
21 */
22
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24
25 #include <assert.h>
26 #include <string.h>
27
28 #include "scip/def.h"
29 #include "scip/set.h"
30 #include "scip/stat.h"
31 #include "scip/clock.h"
32 #include "scip/paramset.h"
33 #include "scip/sepastore.h"
34 #include "scip/scip.h"
35 #include "scip/sepa.h"
36 #include "scip/pub_message.h"
37 #include "scip/pub_misc.h"
38
39 #include "scip/struct_sepa.h"
40
41
42 /** compares two separators w. r. to their priority */
SCIP_DECL_SORTPTRCOMP(SCIPsepaComp)43 SCIP_DECL_SORTPTRCOMP(SCIPsepaComp)
44 { /*lint --e{715}*/
45 return ((SCIP_SEPA*)elem2)->priority - ((SCIP_SEPA*)elem1)->priority;
46 }
47
48 /** comparison method for sorting separators w.r.t. to their name */
SCIP_DECL_SORTPTRCOMP(SCIPsepaCompName)49 SCIP_DECL_SORTPTRCOMP(SCIPsepaCompName)
50 {
51 return strcmp(SCIPsepaGetName((SCIP_SEPA*)elem1), SCIPsepaGetName((SCIP_SEPA*)elem2));
52 }
53
54 /** method to call, when the priority of a separator was changed */
55 static
SCIP_DECL_PARAMCHGD(paramChgdSepaPriority)56 SCIP_DECL_PARAMCHGD(paramChgdSepaPriority)
57 { /*lint --e{715}*/
58 SCIP_PARAMDATA* paramdata;
59
60 paramdata = SCIPparamGetData(param);
61 assert(paramdata != NULL);
62
63 /* use SCIPsetSepaPriority() to mark the sepas unsorted */
64 SCIP_CALL( SCIPsetSepaPriority(scip, (SCIP_SEPA*)paramdata, SCIPparamGetInt(param)) ); /*lint !e740*/
65
66 return SCIP_OKAY;
67 }
68
69 /** copies the given separator to a new scip */
SCIPsepaCopyInclude(SCIP_SEPA * sepa,SCIP_SET * set)70 SCIP_RETCODE SCIPsepaCopyInclude(
71 SCIP_SEPA* sepa, /**< separator */
72 SCIP_SET* set /**< SCIP_SET of SCIP to copy to */
73 )
74 {
75 assert(sepa != NULL);
76 assert(set != NULL);
77 assert(set->scip != NULL);
78
79 if( sepa->sepacopy != NULL )
80 {
81 SCIPsetDebugMsg(set, "including separator %s in subscip %p\n", SCIPsepaGetName(sepa), (void*)set->scip);
82 SCIP_CALL( sepa->sepacopy(set->scip, sepa) );
83 }
84 return SCIP_OKAY;
85 }
86
87 /** internal method for creating a separator */
88 static
doSepaCreate(SCIP_SEPA ** sepa,SCIP_SET * set,SCIP_MESSAGEHDLR * messagehdlr,BMS_BLKMEM * blkmem,const char * name,const char * desc,int priority,int freq,SCIP_Real maxbounddist,SCIP_Bool usessubscip,SCIP_Bool delay,SCIP_DECL_SEPACOPY ((* sepacopy)),SCIP_DECL_SEPAFREE ((* sepafree)),SCIP_DECL_SEPAINIT ((* sepainit)),SCIP_DECL_SEPAEXIT ((* sepaexit)),SCIP_DECL_SEPAINITSOL ((* sepainitsol)),SCIP_DECL_SEPAEXITSOL ((* sepaexitsol)),SCIP_DECL_SEPAEXECLP ((* sepaexeclp)),SCIP_DECL_SEPAEXECSOL ((* sepaexecsol)),SCIP_SEPADATA * sepadata)89 SCIP_RETCODE doSepaCreate(
90 SCIP_SEPA** sepa, /**< pointer to separator data structure */
91 SCIP_SET* set, /**< global SCIP settings */
92 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
93 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
94 const char* name, /**< name of separator */
95 const char* desc, /**< description of separator */
96 int priority, /**< priority of separator (>= 0: before, < 0: after constraint handlers) */
97 int freq, /**< frequency for calling separator */
98 SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound compared
99 * to best node's dual bound for applying separation */
100 SCIP_Bool usessubscip, /**< does the separator use a secondary SCIP instance? */
101 SCIP_Bool delay, /**< should separator be delayed, if other separators found cuts? */
102 SCIP_DECL_SEPACOPY ((*sepacopy)), /**< copy method of separator or NULL if you don't want to copy your plugin into sub-SCIPs */
103 SCIP_DECL_SEPAFREE ((*sepafree)), /**< destructor of separator */
104 SCIP_DECL_SEPAINIT ((*sepainit)), /**< initialize separator */
105 SCIP_DECL_SEPAEXIT ((*sepaexit)), /**< deinitialize separator */
106 SCIP_DECL_SEPAINITSOL ((*sepainitsol)), /**< solving process initialization method of separator */
107 SCIP_DECL_SEPAEXITSOL ((*sepaexitsol)), /**< solving process deinitialization method of separator */
108 SCIP_DECL_SEPAEXECLP ((*sepaexeclp)), /**< LP solution separation method of separator */
109 SCIP_DECL_SEPAEXECSOL ((*sepaexecsol)), /**< arbitrary primal solution separation method of separator */
110 SCIP_SEPADATA* sepadata /**< separator data */
111 )
112 {
113 char paramname[SCIP_MAXSTRLEN];
114 char paramdesc[SCIP_MAXSTRLEN];
115
116 assert(sepa != NULL);
117 assert(name != NULL);
118 assert(desc != NULL);
119 assert(freq >= -1);
120 assert(0.0 <= maxbounddist && maxbounddist <= 1.0);
121 assert(sepaexeclp != NULL || sepaexecsol != NULL);
122
123 SCIP_ALLOC( BMSallocMemory(sepa) );
124 BMSclearMemory(*sepa);
125
126 SCIP_ALLOC( BMSduplicateMemoryArray(&(*sepa)->name, name, strlen(name)+1) );
127 SCIP_ALLOC( BMSduplicateMemoryArray(&(*sepa)->desc, desc, strlen(desc)+1) );
128 (*sepa)->priority = priority;
129 (*sepa)->freq = freq;
130 (*sepa)->maxbounddist = maxbounddist;
131 (*sepa)->usessubscip = usessubscip;
132 (*sepa)->sepacopy = sepacopy;
133 (*sepa)->sepafree = sepafree;
134 (*sepa)->sepainit = sepainit;
135 (*sepa)->sepaexit = sepaexit;
136 (*sepa)->sepainitsol = sepainitsol;
137 (*sepa)->sepaexitsol = sepaexitsol;
138 (*sepa)->sepaexeclp = sepaexeclp;
139 (*sepa)->sepaexecsol = sepaexecsol;
140 (*sepa)->sepadata = sepadata;
141 SCIP_CALL( SCIPclockCreate(&(*sepa)->setuptime, SCIP_CLOCKTYPE_DEFAULT) );
142 SCIP_CALL( SCIPclockCreate(&(*sepa)->sepaclock, SCIP_CLOCKTYPE_DEFAULT) );
143 (*sepa)->lastsepanode = -1;
144 (*sepa)->ncalls = 0;
145 (*sepa)->ncutoffs = 0;
146 (*sepa)->ncutsfound = 0;
147 (*sepa)->ncutsapplied = 0;
148 (*sepa)->nconssfound = 0;
149 (*sepa)->ndomredsfound = 0;
150 (*sepa)->ncallsatnode = 0;
151 (*sepa)->ncutsfoundatnode = 0;
152 (*sepa)->lpwasdelayed = FALSE;
153 (*sepa)->solwasdelayed = FALSE;
154 (*sepa)->initialized = FALSE;
155
156 /* add parameters */
157 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "separating/%s/priority", name);
158 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "priority of separator <%s>", name);
159 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
160 &(*sepa)->priority, TRUE, priority, INT_MIN/4, INT_MAX/4,
161 paramChgdSepaPriority, (SCIP_PARAMDATA*)(*sepa)) ); /*lint !e740*/
162
163 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "separating/%s/freq", name);
164 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "frequency for calling separator <%s> (-1: never, 0: only in root node)", name);
165 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
166 &(*sepa)->freq, FALSE, freq, -1, SCIP_MAXTREEDEPTH, NULL, NULL) );
167
168 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "separating/%s/maxbounddist", name);
169 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "maximal relative distance from current node's dual bound to primal bound compared to best node's dual bound for applying separator <%s> (0.0: only on current best node, 1.0: on all nodes)",
170 name);
171 SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, paramname, paramdesc,
172 &(*sepa)->maxbounddist, TRUE, maxbounddist, 0.0, 1.0, NULL, NULL) );
173
174 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "separating/%s/delay", name);
175 SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem, paramname,
176 "should separator be delayed, if other separators found cuts?",
177 &(*sepa)->delay, TRUE, delay, NULL, NULL) ); /*lint !e740*/
178
179 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "separating/%s/expbackoff", name);
180 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "base for exponential increase of frequency at which separator <%s> is called (1: call at each multiple of frequency)", name);
181 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
182 &(*sepa)->expbackoff, TRUE, 4, 1, 100, NULL, NULL) ); /*lint !e740*/
183
184 return SCIP_OKAY;
185 }
186
187 /** creates a separator */
SCIPsepaCreate(SCIP_SEPA ** sepa,SCIP_SET * set,SCIP_MESSAGEHDLR * messagehdlr,BMS_BLKMEM * blkmem,const char * name,const char * desc,int priority,int freq,SCIP_Real maxbounddist,SCIP_Bool usessubscip,SCIP_Bool delay,SCIP_DECL_SEPACOPY ((* sepacopy)),SCIP_DECL_SEPAFREE ((* sepafree)),SCIP_DECL_SEPAINIT ((* sepainit)),SCIP_DECL_SEPAEXIT ((* sepaexit)),SCIP_DECL_SEPAINITSOL ((* sepainitsol)),SCIP_DECL_SEPAEXITSOL ((* sepaexitsol)),SCIP_DECL_SEPAEXECLP ((* sepaexeclp)),SCIP_DECL_SEPAEXECSOL ((* sepaexecsol)),SCIP_SEPADATA * sepadata)188 SCIP_RETCODE SCIPsepaCreate(
189 SCIP_SEPA** sepa, /**< pointer to separator data structure */
190 SCIP_SET* set, /**< global SCIP settings */
191 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
192 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
193 const char* name, /**< name of separator */
194 const char* desc, /**< description of separator */
195 int priority, /**< priority of separator (>= 0: before, < 0: after constraint handlers) */
196 int freq, /**< frequency for calling separator */
197 SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound compared
198 * to best node's dual bound for applying separation */
199 SCIP_Bool usessubscip, /**< does the separator use a secondary SCIP instance? */
200 SCIP_Bool delay, /**< should separator be delayed, if other separators found cuts? */
201 SCIP_DECL_SEPACOPY ((*sepacopy)), /**< copy method of separator or NULL if you don't want to copy your plugin into sub-SCIPs */
202 SCIP_DECL_SEPAFREE ((*sepafree)), /**< destructor of separator */
203 SCIP_DECL_SEPAINIT ((*sepainit)), /**< initialize separator */
204 SCIP_DECL_SEPAEXIT ((*sepaexit)), /**< deinitialize separator */
205 SCIP_DECL_SEPAINITSOL ((*sepainitsol)), /**< solving process initialization method of separator */
206 SCIP_DECL_SEPAEXITSOL ((*sepaexitsol)), /**< solving process deinitialization method of separator */
207 SCIP_DECL_SEPAEXECLP ((*sepaexeclp)), /**< LP solution separation method of separator */
208 SCIP_DECL_SEPAEXECSOL ((*sepaexecsol)), /**< arbitrary primal solution separation method of separator */
209 SCIP_SEPADATA* sepadata /**< separator data */
210 )
211 {
212 assert(sepa != NULL);
213 assert(name != NULL);
214 assert(desc != NULL);
215 assert(freq >= -1);
216 assert(0.0 <= maxbounddist && maxbounddist <= 1.0);
217 assert(sepaexeclp != NULL || sepaexecsol != NULL);
218
219 SCIP_CALL_FINALLY( doSepaCreate(sepa, set, messagehdlr, blkmem, name, desc, priority, freq, maxbounddist,
220 usessubscip, delay, sepacopy, sepafree, sepainit, sepaexit, sepainitsol, sepaexitsol, sepaexeclp,
221 sepaexecsol, sepadata), (void) SCIPsepaFree(sepa, set) );
222
223 return SCIP_OKAY;
224 }
225
226 /** calls destructor and frees memory of separator */
SCIPsepaFree(SCIP_SEPA ** sepa,SCIP_SET * set)227 SCIP_RETCODE SCIPsepaFree(
228 SCIP_SEPA** sepa, /**< pointer to separator data structure */
229 SCIP_SET* set /**< global SCIP settings */
230 )
231 {
232 assert(sepa != NULL);
233 if( *sepa == NULL )
234 return SCIP_OKAY;
235 assert(!(*sepa)->initialized);
236 assert(set != NULL);
237
238 /* call destructor of separator */
239 if( (*sepa)->sepafree != NULL )
240 {
241 SCIP_CALL( (*sepa)->sepafree(set->scip, *sepa) );
242 }
243
244 SCIPclockFree(&(*sepa)->sepaclock);
245 SCIPclockFree(&(*sepa)->setuptime);
246 BMSfreeMemoryArrayNull(&(*sepa)->name);
247 BMSfreeMemoryArrayNull(&(*sepa)->desc);
248 BMSfreeMemory(sepa);
249
250 return SCIP_OKAY;
251 }
252
253 /** initializes separator */
SCIPsepaInit(SCIP_SEPA * sepa,SCIP_SET * set)254 SCIP_RETCODE SCIPsepaInit(
255 SCIP_SEPA* sepa, /**< separator */
256 SCIP_SET* set /**< global SCIP settings */
257 )
258 {
259 assert(sepa != NULL);
260 assert(set != NULL);
261
262 if( sepa->initialized )
263 {
264 SCIPerrorMessage("separator <%s> already initialized\n", sepa->name);
265 return SCIP_INVALIDCALL;
266 }
267
268 if( set->misc_resetstat )
269 {
270 SCIPclockReset(sepa->setuptime);
271 SCIPclockReset(sepa->sepaclock);
272
273 sepa->lastsepanode = -1;
274 sepa->ncalls = 0;
275 sepa->ncutoffs = 0;
276 sepa->ncutsfound = 0;
277 sepa->ncutsapplied = 0;
278 sepa->nconssfound = 0;
279 sepa->ndomredsfound = 0;
280 sepa->ncallsatnode = 0;
281 sepa->ncutsfoundatnode = 0;
282 sepa->lpwasdelayed = FALSE;
283 sepa->solwasdelayed = FALSE;
284 }
285
286 if( sepa->sepainit != NULL )
287 {
288 /* start timing */
289 SCIPclockStart(sepa->setuptime, set);
290
291 SCIP_CALL( sepa->sepainit(set->scip, sepa) );
292
293 /* stop timing */
294 SCIPclockStop(sepa->setuptime, set);
295 }
296 sepa->initialized = TRUE;
297
298 return SCIP_OKAY;
299 }
300
301 /** calls exit method of separator */
SCIPsepaExit(SCIP_SEPA * sepa,SCIP_SET * set)302 SCIP_RETCODE SCIPsepaExit(
303 SCIP_SEPA* sepa, /**< separator */
304 SCIP_SET* set /**< global SCIP settings */
305 )
306 {
307 assert(sepa != NULL);
308 assert(set != NULL);
309
310 if( !sepa->initialized )
311 {
312 SCIPerrorMessage("separator <%s> not initialized\n", sepa->name);
313 return SCIP_INVALIDCALL;
314 }
315
316 if( sepa->sepaexit != NULL )
317 {
318 /* start timing */
319 SCIPclockStart(sepa->setuptime, set);
320
321 SCIP_CALL( sepa->sepaexit(set->scip, sepa) );
322
323 /* stop timing */
324 SCIPclockStop(sepa->setuptime, set);
325 }
326 sepa->initialized = FALSE;
327
328 return SCIP_OKAY;
329 }
330
331 /** informs separator that the branch and bound process is being started */
SCIPsepaInitsol(SCIP_SEPA * sepa,SCIP_SET * set)332 SCIP_RETCODE SCIPsepaInitsol(
333 SCIP_SEPA* sepa, /**< separator */
334 SCIP_SET* set /**< global SCIP settings */
335 )
336 {
337 assert(sepa != NULL);
338 assert(set != NULL);
339
340 sepa->lpwasdelayed = FALSE;
341 sepa->solwasdelayed = FALSE;
342
343 /* call solving process initialization method of separator */
344 if( sepa->sepainitsol != NULL )
345 {
346 /* start timing */
347 SCIPclockStart(sepa->setuptime, set);
348
349 SCIP_CALL( sepa->sepainitsol(set->scip, sepa) );
350
351 /* stop timing */
352 SCIPclockStop(sepa->setuptime, set);
353 }
354
355 return SCIP_OKAY;
356 }
357
358 /** informs separator that the branch and bound process data is being freed */
SCIPsepaExitsol(SCIP_SEPA * sepa,SCIP_SET * set)359 SCIP_RETCODE SCIPsepaExitsol(
360 SCIP_SEPA* sepa, /**< separator */
361 SCIP_SET* set /**< global SCIP settings */
362 )
363 {
364 assert(sepa != NULL);
365 assert(set != NULL);
366
367 /* call solving process deinitialization method of separator */
368 if( sepa->sepaexitsol != NULL )
369 {
370 /* start timing */
371 SCIPclockStart(sepa->setuptime, set);
372
373 SCIP_CALL( sepa->sepaexitsol(set->scip, sepa) );
374
375 /* stop timing */
376 SCIPclockStop(sepa->setuptime, set);
377 }
378
379 return SCIP_OKAY;
380 }
381
382 /** calls LP separation method of separator */
SCIPsepaExecLP(SCIP_SEPA * sepa,SCIP_SET * set,SCIP_STAT * stat,SCIP_SEPASTORE * sepastore,int depth,SCIP_Real bounddist,SCIP_Bool allowlocal,SCIP_Bool execdelayed,SCIP_RESULT * result)383 SCIP_RETCODE SCIPsepaExecLP(
384 SCIP_SEPA* sepa, /**< separator */
385 SCIP_SET* set, /**< global SCIP settings */
386 SCIP_STAT* stat, /**< dynamic problem statistics */
387 SCIP_SEPASTORE* sepastore, /**< separation storage */
388 int depth, /**< depth of current node */
389 SCIP_Real bounddist, /**< current relative distance of local dual bound to global dual bound */
390 SCIP_Bool allowlocal, /**< should the separator be asked to separate local cuts */
391 SCIP_Bool execdelayed, /**< execute separator even if it is marked to be delayed */
392 SCIP_RESULT* result /**< pointer to store the result of the callback method */
393 )
394 {
395 assert(sepa != NULL);
396 assert(sepa->freq >= -1);
397 assert(0.0 <= sepa->maxbounddist && sepa->maxbounddist <= 1.0);
398 assert(0.0 <= bounddist && bounddist <= 1.0);
399 assert(set != NULL);
400 assert(set->scip != NULL);
401 assert(stat != NULL);
402 assert(depth >= 0);
403 assert(result != NULL);
404
405 if( sepa->sepaexeclp != NULL && SCIPsetIsLE(set, bounddist, sepa->maxbounddist) &&
406 ( (depth == 0 && sepa->freq != -1) ||
407 (sepa->freq > 0 && depth % sepa->freq == 0 &&
408 (sepa->expbackoff == 1 || SCIPsetIsIntegral(set, LOG2(depth * (1.0 / sepa->freq)) / LOG2((SCIP_Real)sepa->expbackoff)))) ||
409 sepa->lpwasdelayed )
410 )
411 {
412 if( (!sepa->delay && !sepa->lpwasdelayed) || execdelayed )
413 {
414 SCIP_CUTPOOL* cutpool;
415 SCIP_CUTPOOL* delayedcutpool;
416 SCIP_Longint oldndomchgs;
417 SCIP_Longint oldnprobdomchgs;
418 int oldncuts;
419 int oldnactiveconss;
420 int ncutsfound;
421
422 SCIPsetDebugMsg(set, "executing separator <%s> on LP solution\n", sepa->name);
423
424 cutpool = SCIPgetGlobalCutpool(set->scip);
425 delayedcutpool = SCIPgetDelayedGlobalCutpool(set->scip);
426 oldndomchgs = stat->nboundchgs + stat->nholechgs;
427 oldnprobdomchgs = stat->nprobboundchgs + stat->nprobholechgs;
428 oldncuts = SCIPsepastoreGetNCuts(sepastore) + SCIPcutpoolGetNCuts(cutpool) + SCIPcutpoolGetNCuts(delayedcutpool);
429 oldnactiveconss = stat->nactiveconss;
430
431 /* reset the statistics for current node */
432 if( sepa->lastsepanode != stat->ntotalnodes )
433 {
434 sepa->ncallsatnode = 0;
435 sepa->ncutsfoundatnode = 0;
436 }
437
438 /* start timing */
439 SCIPclockStart(sepa->sepaclock, set);
440
441 /* call external separation method */
442 SCIP_CALL( sepa->sepaexeclp(set->scip, sepa, result, allowlocal) );
443
444 /* stop timing */
445 SCIPclockStop(sepa->sepaclock, set);
446
447 /* update statistics */
448 if( *result != SCIP_DIDNOTRUN && *result != SCIP_DELAYED )
449 {
450 sepa->ncalls++;
451 sepa->ncallsatnode++;
452 sepa->lastsepanode = stat->ntotalnodes;
453 }
454 if( *result == SCIP_CUTOFF )
455 sepa->ncutoffs++;
456
457 ncutsfound = SCIPsepastoreGetNCuts(sepastore) + SCIPcutpoolGetNCuts(cutpool) +
458 SCIPcutpoolGetNCuts(delayedcutpool) - oldncuts;
459
460 sepa->ncutsfound += ncutsfound;
461 sepa->ncutsfoundatnode += ncutsfound;
462 sepa->nconssfound += MAX(stat->nactiveconss - oldnactiveconss, 0); /*lint !e776*/
463
464 /* update domain reductions; therefore remove the domain
465 * reduction counts which were generated in probing mode */
466 sepa->ndomredsfound += stat->nboundchgs + stat->nholechgs - oldndomchgs;
467 sepa->ndomredsfound -= (stat->nprobboundchgs + stat->nprobholechgs - oldnprobdomchgs);
468
469 /* evaluate result */
470 if( *result != SCIP_CUTOFF
471 && *result != SCIP_CONSADDED
472 && *result != SCIP_REDUCEDDOM
473 && *result != SCIP_SEPARATED
474 && *result != SCIP_NEWROUND
475 && *result != SCIP_DIDNOTFIND
476 && *result != SCIP_DIDNOTRUN
477 && *result != SCIP_DELAYED )
478 {
479 SCIPerrorMessage("execution method of separator <%s> returned invalid result <%d>\n",
480 sepa->name, *result);
481 return SCIP_INVALIDRESULT;
482 }
483 }
484 else
485 {
486 SCIPsetDebugMsg(set, "separator <%s> was delayed\n", sepa->name);
487 *result = SCIP_DELAYED;
488 }
489
490 /* remember whether separator was delayed */
491 sepa->lpwasdelayed = (*result == SCIP_DELAYED);
492 }
493 else
494 *result = SCIP_DIDNOTRUN;
495
496 return SCIP_OKAY;
497 }
498
499 /** calls primal solution separation method of separator */
SCIPsepaExecSol(SCIP_SEPA * sepa,SCIP_SET * set,SCIP_STAT * stat,SCIP_SEPASTORE * sepastore,SCIP_SOL * sol,int depth,SCIP_Bool allowlocal,SCIP_Bool execdelayed,SCIP_RESULT * result)500 SCIP_RETCODE SCIPsepaExecSol(
501 SCIP_SEPA* sepa, /**< separator */
502 SCIP_SET* set, /**< global SCIP settings */
503 SCIP_STAT* stat, /**< dynamic problem statistics */
504 SCIP_SEPASTORE* sepastore, /**< separation storage */
505 SCIP_SOL* sol, /**< primal solution that should be separated */
506 int depth, /**< depth of current node */
507 SCIP_Bool allowlocal, /**< should the separator allow local cuts */
508 SCIP_Bool execdelayed, /**< execute separator even if it is marked to be delayed */
509 SCIP_RESULT* result /**< pointer to store the result of the callback method */
510 )
511 {
512 assert(sepa != NULL);
513 assert(sepa->freq >= -1);
514 assert(set != NULL);
515 assert(set->scip != NULL);
516 assert(stat != NULL);
517 assert(depth >= 0);
518 assert(result != NULL);
519
520 if( sepa->sepaexecsol != NULL &&
521 ( (depth == 0 && sepa->freq != -1) ||
522 (sepa->freq > 0 && depth % sepa->freq == 0 &&
523 (sepa->expbackoff == 1 || SCIPsetIsIntegral(set, LOG2(depth * (1.0 / sepa->freq) / LOG2((SCIP_Real)sepa->expbackoff))))) ||
524 sepa->solwasdelayed )
525 )
526 {
527 if( (!sepa->delay && !sepa->solwasdelayed) || execdelayed )
528 {
529 SCIP_Longint oldndomchgs;
530 SCIP_Longint oldnprobdomchgs;
531 int oldncuts;
532 int oldnactiveconss;
533 int ncutsfound;
534
535 SCIPsetDebugMsg(set, "executing separator <%s> on solution %p\n", sepa->name, (void*)sol);
536
537 oldndomchgs = stat->nboundchgs + stat->nholechgs;
538 oldnprobdomchgs = stat->nprobboundchgs + stat->nprobholechgs;
539 oldncuts = SCIPsepastoreGetNCuts(sepastore);
540 oldnactiveconss = stat->nactiveconss;
541
542 /* reset the statistics for current node */
543 if( sepa->lastsepanode != stat->ntotalnodes )
544 {
545 sepa->ncallsatnode = 0;
546 sepa->ncutsfoundatnode = 0;
547 }
548
549 /* start timing */
550 SCIPclockStart(sepa->sepaclock, set);
551
552 /* call external separation method */
553 SCIP_CALL( sepa->sepaexecsol(set->scip, sepa, sol, result, allowlocal) );
554
555 /* stop timing */
556 SCIPclockStop(sepa->sepaclock, set);
557
558 /* update statistics */
559 if( *result != SCIP_DIDNOTRUN && *result != SCIP_DELAYED )
560 {
561 sepa->ncalls++;
562 sepa->ncallsatnode++;
563 sepa->lastsepanode = stat->ntotalnodes;
564 }
565 if( *result == SCIP_CUTOFF )
566 sepa->ncutoffs++;
567 ncutsfound = SCIPsepastoreGetNCuts(sepastore) - oldncuts;
568 sepa->ncutsfound += ncutsfound;
569 sepa->ncutsfoundatnode += ncutsfound;
570 sepa->nconssfound += MAX(stat->nactiveconss - oldnactiveconss, 0); /*lint !e776*/
571
572 /* update domain reductions; therefore remove the domain
573 * reduction counts which were generated in probing mode */
574 sepa->ndomredsfound += stat->nboundchgs + stat->nholechgs - oldndomchgs;
575 sepa->ndomredsfound -= (stat->nprobboundchgs + stat->nprobholechgs - oldnprobdomchgs);
576
577 /* evaluate result */
578 if( *result != SCIP_CUTOFF
579 && *result != SCIP_CONSADDED
580 && *result != SCIP_REDUCEDDOM
581 && *result != SCIP_SEPARATED
582 && *result != SCIP_NEWROUND
583 && *result != SCIP_DIDNOTFIND
584 && *result != SCIP_DIDNOTRUN
585 && *result != SCIP_DELAYED )
586 {
587 SCIPerrorMessage("execution method of separator <%s> returned invalid result <%d>\n",
588 sepa->name, *result);
589 return SCIP_INVALIDRESULT;
590 }
591 }
592 else
593 {
594 SCIPsetDebugMsg(set, "separator <%s> was delayed\n", sepa->name);
595 *result = SCIP_DELAYED;
596 }
597
598 /* remember whether separator was delayed */
599 sepa->solwasdelayed = (*result == SCIP_DELAYED);
600 }
601 else
602 *result = SCIP_DIDNOTRUN;
603
604 return SCIP_OKAY;
605 }
606
607 /** gets user data of separator */
SCIPsepaGetData(SCIP_SEPA * sepa)608 SCIP_SEPADATA* SCIPsepaGetData(
609 SCIP_SEPA* sepa /**< separator */
610 )
611 {
612 assert(sepa != NULL);
613
614 return sepa->sepadata;
615 }
616
617 /** sets user data of separator; user has to free old data in advance! */
SCIPsepaSetData(SCIP_SEPA * sepa,SCIP_SEPADATA * sepadata)618 void SCIPsepaSetData(
619 SCIP_SEPA* sepa, /**< separator */
620 SCIP_SEPADATA* sepadata /**< new separator user data */
621 )
622 {
623 assert(sepa != NULL);
624
625 sepa->sepadata = sepadata;
626 }
627
628 /* new callback/method setter methods */
629
630 /** sets copy method of separator */
SCIPsepaSetCopy(SCIP_SEPA * sepa,SCIP_DECL_SEPACOPY ((* sepacopy)))631 void SCIPsepaSetCopy(
632 SCIP_SEPA* sepa, /**< separator */
633 SCIP_DECL_SEPACOPY ((*sepacopy)) /**< copy method of separator or NULL if you don't want to copy your plugin into sub-SCIPs */
634 )
635 {
636 assert(sepa != NULL);
637
638 sepa->sepacopy = sepacopy;
639 }
640
641 /** sets destructor method of separator */
SCIPsepaSetFree(SCIP_SEPA * sepa,SCIP_DECL_SEPAFREE ((* sepafree)))642 void SCIPsepaSetFree(
643 SCIP_SEPA* sepa, /**< separator */
644 SCIP_DECL_SEPAFREE ((*sepafree)) /**< destructor of separator */
645 )
646 {
647 assert(sepa != NULL);
648
649 sepa->sepafree = sepafree;
650 }
651
652 /** sets initialization method of separator */
SCIPsepaSetInit(SCIP_SEPA * sepa,SCIP_DECL_SEPAINIT ((* sepainit)))653 void SCIPsepaSetInit(
654 SCIP_SEPA* sepa, /**< separator */
655 SCIP_DECL_SEPAINIT ((*sepainit)) /**< initialize separator */
656 )
657 {
658 assert(sepa != NULL);
659
660 sepa->sepainit = sepainit;
661 }
662
663 /** sets deinitialization method of separator */
SCIPsepaSetExit(SCIP_SEPA * sepa,SCIP_DECL_SEPAEXIT ((* sepaexit)))664 void SCIPsepaSetExit(
665 SCIP_SEPA* sepa, /**< separator */
666 SCIP_DECL_SEPAEXIT ((*sepaexit)) /**< deinitialize separator */
667 )
668 {
669 assert(sepa != NULL);
670
671 sepa->sepaexit = sepaexit;
672 }
673
674 /** sets solving process initialization method of separator */
SCIPsepaSetInitsol(SCIP_SEPA * sepa,SCIP_DECL_SEPAINITSOL ((* sepainitsol)))675 void SCIPsepaSetInitsol(
676 SCIP_SEPA* sepa, /**< separator */
677 SCIP_DECL_SEPAINITSOL ((*sepainitsol)) /**< solving process initialization method of separator */
678 )
679 {
680 assert(sepa != NULL);
681
682 sepa->sepainitsol = sepainitsol;
683 }
684
685 /** sets solving process deinitialization method of separator */
SCIPsepaSetExitsol(SCIP_SEPA * sepa,SCIP_DECL_SEPAEXITSOL ((* sepaexitsol)))686 void SCIPsepaSetExitsol(
687 SCIP_SEPA* sepa, /**< separator */
688 SCIP_DECL_SEPAEXITSOL ((*sepaexitsol)) /**< solving process deinitialization method of separator */
689 )
690 {
691 assert(sepa != NULL);
692
693 sepa->sepaexitsol = sepaexitsol;
694 }
695
696 /** gets name of separator */
SCIPsepaGetName(SCIP_SEPA * sepa)697 const char* SCIPsepaGetName(
698 SCIP_SEPA* sepa /**< separator */
699 )
700 {
701 assert(sepa != NULL);
702
703 return sepa->name;
704 }
705
706 /** gets description of separator */
SCIPsepaGetDesc(SCIP_SEPA * sepa)707 const char* SCIPsepaGetDesc(
708 SCIP_SEPA* sepa /**< separator */
709 )
710 {
711 assert(sepa != NULL);
712
713 return sepa->desc;
714 }
715
716 /** gets priority of separator */
SCIPsepaGetPriority(SCIP_SEPA * sepa)717 int SCIPsepaGetPriority(
718 SCIP_SEPA* sepa /**< separator */
719 )
720 {
721 assert(sepa != NULL);
722
723 return sepa->priority;
724 }
725
726 /** sets priority of separator */
SCIPsepaSetPriority(SCIP_SEPA * sepa,SCIP_SET * set,int priority)727 void SCIPsepaSetPriority(
728 SCIP_SEPA* sepa, /**< separator */
729 SCIP_SET* set, /**< global SCIP settings */
730 int priority /**< new priority of the separator */
731 )
732 {
733 assert(sepa != NULL);
734 assert(set != NULL);
735
736 sepa->priority = priority;
737 set->sepassorted = FALSE;
738 }
739
740 /** gets frequency of separator */
SCIPsepaGetFreq(SCIP_SEPA * sepa)741 int SCIPsepaGetFreq(
742 SCIP_SEPA* sepa /**< separator */
743 )
744 {
745 assert(sepa != NULL);
746
747 return sepa->freq;
748 }
749
750 /** sets frequency of separator */
SCIPsepaSetFreq(SCIP_SEPA * sepa,int freq)751 void SCIPsepaSetFreq(
752 SCIP_SEPA* sepa, /**< separator */
753 int freq /**< new frequency of separator */
754 )
755 {
756 assert(sepa != NULL);
757
758 sepa->freq = freq;
759 }
760
761 /** get maximal bound distance at which the separator is called */
SCIPsepaGetMaxbounddist(SCIP_SEPA * sepa)762 SCIP_Real SCIPsepaGetMaxbounddist(
763 SCIP_SEPA* sepa /**< separator */
764 )
765 {
766 assert(sepa != NULL);
767
768 return sepa->maxbounddist;
769 }
770
771 /** does the separator use a secondary SCIP instance? */
SCIPsepaUsesSubscip(SCIP_SEPA * sepa)772 SCIP_Bool SCIPsepaUsesSubscip(
773 SCIP_SEPA* sepa /**< separator */
774 )
775 {
776 assert(sepa != NULL);
777
778 return sepa->usessubscip;
779 }
780
781 /** enables or disables all clocks of \p sepa, depending on the value of the flag */
SCIPsepaEnableOrDisableClocks(SCIP_SEPA * sepa,SCIP_Bool enable)782 void SCIPsepaEnableOrDisableClocks(
783 SCIP_SEPA* sepa, /**< the separator for which all clocks should be enabled or disabled */
784 SCIP_Bool enable /**< should the clocks of the separator be enabled? */
785 )
786 {
787 assert(sepa != NULL);
788
789 SCIPclockEnableOrDisable(sepa->setuptime, enable);
790 SCIPclockEnableOrDisable(sepa->sepaclock, enable);
791 }
792
793 /** gets time in seconds used in this separator for setting up for next stages */
SCIPsepaGetSetupTime(SCIP_SEPA * sepa)794 SCIP_Real SCIPsepaGetSetupTime(
795 SCIP_SEPA* sepa /**< separator */
796 )
797 {
798 assert(sepa != NULL);
799
800 return SCIPclockGetTime(sepa->setuptime);
801 }
802
803 /** gets time in seconds used in this separator */
SCIPsepaGetTime(SCIP_SEPA * sepa)804 SCIP_Real SCIPsepaGetTime(
805 SCIP_SEPA* sepa /**< separator */
806 )
807 {
808 assert(sepa != NULL);
809
810 return SCIPclockGetTime(sepa->sepaclock);
811 }
812
813 /** gets the total number of times, the separator was called */
SCIPsepaGetNCalls(SCIP_SEPA * sepa)814 SCIP_Longint SCIPsepaGetNCalls(
815 SCIP_SEPA* sepa /**< separator */
816 )
817 {
818 assert(sepa != NULL);
819
820 return sepa->ncalls;
821 }
822
823 /** gets the number of times, the separator was called at the current node */
SCIPsepaGetNCallsAtNode(SCIP_SEPA * sepa)824 int SCIPsepaGetNCallsAtNode(
825 SCIP_SEPA* sepa /**< separator */
826 )
827 {
828 assert(sepa != NULL);
829
830 return sepa->ncallsatnode;
831 }
832
833 /** gets total number of times, the separator detected a cutoff */
SCIPsepaGetNCutoffs(SCIP_SEPA * sepa)834 SCIP_Longint SCIPsepaGetNCutoffs(
835 SCIP_SEPA* sepa /**< separator */
836 )
837 {
838 assert(sepa != NULL);
839
840 return sepa->ncutoffs;
841 }
842
843 /** gets the total number of cutting planes found by this separator */
SCIPsepaGetNCutsFound(SCIP_SEPA * sepa)844 SCIP_Longint SCIPsepaGetNCutsFound(
845 SCIP_SEPA* sepa /**< separator */
846 )
847 {
848 assert(sepa != NULL);
849
850 return sepa->ncutsfound;
851 }
852
853 /** gets the total number of cutting planes applied to lp */
SCIPsepaGetNCutsApplied(SCIP_SEPA * sepa)854 SCIP_Longint SCIPsepaGetNCutsApplied(
855 SCIP_SEPA* sepa /**< separator */
856 )
857 {
858 assert(sepa != NULL);
859
860 return sepa->ncutsapplied;
861 }
862
863 /** increase count of applied cuts */
SCIPsepaIncNAppliedCuts(SCIP_SEPA * sepa)864 void SCIPsepaIncNAppliedCuts(
865 SCIP_SEPA* sepa /**< separator */
866 )
867 {
868 assert( sepa != NULL );
869
870 ++sepa->ncutsapplied;
871 }
872
873 /** increase count of found cuts */
SCIPsepaIncNCutsFound(SCIP_SEPA * sepa)874 void SCIPsepaIncNCutsFound(
875 SCIP_SEPA* sepa /**< separator */
876 )
877 {
878 assert( sepa != NULL );
879
880 ++sepa->ncutsfound;
881 }
882
883 /** increase count of found cuts at current node */
SCIPsepaIncNCutsFoundAtNode(SCIP_SEPA * sepa)884 void SCIPsepaIncNCutsFoundAtNode(
885 SCIP_SEPA* sepa /**< separator */
886 )
887 {
888 assert( sepa != NULL );
889
890 ++sepa->ncutsfoundatnode;
891 }
892
893 /** gets the number of cutting planes found by this separator at the current node */
SCIPsepaGetNCutsFoundAtNode(SCIP_SEPA * sepa)894 SCIP_Longint SCIPsepaGetNCutsFoundAtNode(
895 SCIP_SEPA* sepa /**< separator */
896 )
897 {
898 assert(sepa != NULL);
899
900 return sepa->ncutsfoundatnode;
901 }
902
903 /** gets total number of additional constraints added by this separator */
SCIPsepaGetNConssFound(SCIP_SEPA * sepa)904 SCIP_Longint SCIPsepaGetNConssFound(
905 SCIP_SEPA* sepa /**< separator */
906 )
907 {
908 assert(sepa != NULL);
909
910 return sepa->nconssfound;
911 }
912
913 /** gets total number of domain reductions found by this separator */
SCIPsepaGetNDomredsFound(SCIP_SEPA * sepa)914 SCIP_Longint SCIPsepaGetNDomredsFound(
915 SCIP_SEPA* sepa /**< separator */
916 )
917 {
918 assert(sepa != NULL);
919
920 return sepa->ndomredsfound;
921 }
922
923 /** should separator be delayed, if other separators found cuts? */
SCIPsepaIsDelayed(SCIP_SEPA * sepa)924 SCIP_Bool SCIPsepaIsDelayed(
925 SCIP_SEPA* sepa /**< separator */
926 )
927 {
928 assert(sepa != NULL);
929
930 return sepa->delay;
931 }
932
933 /** was separation of the LP solution delayed at the last call? */
SCIPsepaWasLPDelayed(SCIP_SEPA * sepa)934 SCIP_Bool SCIPsepaWasLPDelayed(
935 SCIP_SEPA* sepa /**< separator */
936 )
937 {
938 assert(sepa != NULL);
939
940 return sepa->lpwasdelayed;
941 }
942
943 /** was separation of the primal solution delayed at the last call? */
SCIPsepaWasSolDelayed(SCIP_SEPA * sepa)944 SCIP_Bool SCIPsepaWasSolDelayed(
945 SCIP_SEPA* sepa /**< separator */
946 )
947 {
948 assert(sepa != NULL);
949
950 return sepa->solwasdelayed;
951 }
952
953 /** is separator initialized? */
SCIPsepaIsInitialized(SCIP_SEPA * sepa)954 SCIP_Bool SCIPsepaIsInitialized(
955 SCIP_SEPA* sepa /**< separator */
956 )
957 {
958 assert(sepa != NULL);
959
960 return sepa->initialized;
961 }
962