Scippy

SCIP

Solving Constraint Integer Programs

prop.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2014 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 email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file prop.c
17  * @brief methods and datastructures for propagators
18  * @author Tobias Achterberg
19  * @author Timo Berthold
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include <assert.h>
25 #include <string.h>
26 
27 #include "scip/def.h"
28 #include "scip/set.h"
29 #include "scip/stat.h"
30 #include "scip/clock.h"
31 #include "scip/paramset.h"
32 #include "scip/var.h"
33 #include "scip/scip.h"
34 #include "scip/prop.h"
35 #include "scip/pub_message.h"
36 #include "scip/pub_misc.h"
37 
38 #include "scip/struct_prop.h"
39 
40 
41 
42 /** compares two propagators w. r. to their priority */
43 SCIP_DECL_SORTPTRCOMP(SCIPpropComp)
44 { /*lint --e{715}*/
45  return ((SCIP_PROP*)elem2)->priority - ((SCIP_PROP*)elem1)->priority;
46 }
47 
48 /** compares two propagators w. r. to their priority */
49 SCIP_DECL_SORTPTRCOMP(SCIPpropCompPresol)
50 { /*lint --e{715}*/
51  return ((SCIP_PROP*)elem2)->presolpriority - ((SCIP_PROP*)elem1)->presolpriority;
52 }
53 
54 /** comparison method for sorting propagators w.r.t. to their name */
55 SCIP_DECL_SORTPTRCOMP(SCIPpropCompName)
56 {
57  return strcmp(SCIPpropGetName((SCIP_PROP*)elem1), SCIPpropGetName((SCIP_PROP*)elem2));
58 }
59 
60 /** method to call, when the priority of a propagator was changed */
61 static
62 SCIP_DECL_PARAMCHGD(paramChgdPropPriority)
63 { /*lint --e{715}*/
64  SCIP_PARAMDATA* paramdata;
65 
66  paramdata = SCIPparamGetData(param);
67  assert(paramdata != NULL);
68 
69  /* use SCIPsetPropPriority() to mark the props unsorted */
70  SCIP_CALL( SCIPsetPropPriority(scip, (SCIP_PROP*)paramdata, SCIPparamGetInt(param)) ); /*lint !e740*/
71 
72  return SCIP_OKAY;
73 }
74 
75 /** method to call, when the presolving priority of a propagator was changed */
76 static
77 SCIP_DECL_PARAMCHGD(paramChgdPropPresolPriority)
78 { /*lint --e{715}*/
79  SCIP_PARAMDATA* paramdata;
80 
81  paramdata = SCIPparamGetData(param);
82  assert(paramdata != NULL);
83 
84  /* use SCIPsetPropPriority() to mark the props unsorted */
85  SCIP_CALL( SCIPsetPropPresolPriority(scip, (SCIP_PROP*)paramdata, SCIPparamGetInt(param)) ); /*lint !e740*/
86 
87  return SCIP_OKAY;
88 }
89 
90 /** copies the given propagator to a new scip */
91 SCIP_RETCODE SCIPpropCopyInclude(
92  SCIP_PROP* prop, /**< propagator */
93  SCIP_SET* set /**< SCIP_SET of SCIP to copy to */
94  )
95 {
96  assert(prop != NULL);
97  assert(set != NULL);
98  assert(set->scip != NULL);
99 
100  if( prop->propcopy != NULL )
101  {
102  SCIPdebugMessage("including propagator %s in subscip %p\n", SCIPpropGetName(prop), (void*)set->scip);
103  SCIP_CALL( prop->propcopy(set->scip, prop) );
104  }
105  return SCIP_OKAY;
106 }
107 
108 /** creates a propagator */
109 SCIP_RETCODE SCIPpropCreate(
110  SCIP_PROP** prop, /**< pointer to propagator data structure */
111  SCIP_SET* set, /**< global SCIP settings */
112  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
113  BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
114  const char* name, /**< name of propagator */
115  const char* desc, /**< description of propagator */
116  int priority, /**< priority of the propagator (>= 0: before, < 0: after constraint handlers) */
117  int freq, /**< frequency for calling propagator */
118  SCIP_Bool delay, /**< should propagator be delayed, if other propagators found reductions? */
119  SCIP_PROPTIMING timingmask, /**< positions in the node solving loop where heuristic should be executed */
120  int presolpriority, /**< priority of the propagator (>= 0: before, < 0: after constraint handlers) */
121  int presolmaxrounds, /**< maximal number of presolving rounds the propagator participates in (-1: no limit) */
122  SCIP_Bool presoldelay, /**< should presolving be delayed, if other presolvers found reductions? */
123  SCIP_DECL_PROPCOPY ((*propcopy)), /**< copy method of propagator or NULL if you don't want to copy your plugin into sub-SCIPs */
124  SCIP_DECL_PROPFREE ((*propfree)), /**< destructor of propagator */
125  SCIP_DECL_PROPINIT ((*propinit)), /**< initialize propagator */
126  SCIP_DECL_PROPEXIT ((*propexit)), /**< deinitialize propagator */
127  SCIP_DECL_PROPINITPRE ((*propinitpre)), /**< presolving initialization method of propagator */
128  SCIP_DECL_PROPEXITPRE ((*propexitpre)), /**< presolving deinitialization method of propagator */
129  SCIP_DECL_PROPINITSOL ((*propinitsol)), /**< solving process initialization method of propagator */
130  SCIP_DECL_PROPEXITSOL ((*propexitsol)), /**< solving process deinitialization method of propagator */
131  SCIP_DECL_PROPPRESOL ((*proppresol)), /**< presolving method */
132  SCIP_DECL_PROPEXEC ((*propexec)), /**< execution method of propagator */
133  SCIP_DECL_PROPRESPROP ((*propresprop)), /**< propagation conflict resolving method */
134  SCIP_PROPDATA* propdata /**< propagator data */
135  )
136 {
137  char paramname[SCIP_MAXSTRLEN];
138  char paramdesc[SCIP_MAXSTRLEN];
139 
140  assert(prop != NULL);
141  assert(name != NULL);
142  assert(desc != NULL);
143  assert(freq >= -1);
144  assert(propexec != NULL);
145 
146  SCIP_ALLOC( BMSallocMemory(prop) );
147  SCIP_ALLOC( BMSduplicateMemoryArray(&(*prop)->name, name, strlen(name)+1) );
148  SCIP_ALLOC( BMSduplicateMemoryArray(&(*prop)->desc, desc, strlen(desc)+1) );
149  (*prop)->priority = priority;
150  (*prop)->freq = freq;
151  (*prop)->propcopy = propcopy;
152  (*prop)->propfree = propfree;
153  (*prop)->propinit = propinit;
154  (*prop)->propexit = propexit;
155  (*prop)->propinitpre = propinitpre;
156  (*prop)->propexitpre = propexitpre;
157  (*prop)->propinitsol = propinitsol;
158  (*prop)->propexitsol = propexitsol;
159  (*prop)->proppresol = proppresol;
160  (*prop)->propexec = propexec;
161  (*prop)->propresprop = propresprop;
162  (*prop)->propdata = propdata;
163  SCIP_CALL( SCIPclockCreate(&(*prop)->setuptime, SCIP_CLOCKTYPE_DEFAULT) );
164  SCIP_CALL( SCIPclockCreate(&(*prop)->proptime, SCIP_CLOCKTYPE_DEFAULT) );
165  SCIP_CALL( SCIPclockCreate(&(*prop)->sbproptime, SCIP_CLOCKTYPE_DEFAULT) );
166  SCIP_CALL( SCIPclockCreate(&(*prop)->resproptime, SCIP_CLOCKTYPE_DEFAULT) );
167  SCIP_CALL( SCIPclockCreate(&(*prop)->presoltime, SCIP_CLOCKTYPE_DEFAULT) );
168  (*prop)->ncalls = 0;
169  (*prop)->nrespropcalls = 0;
170  (*prop)->ncutoffs = 0;
171  (*prop)->ndomredsfound = 0;
172  (*prop)->presolwasdelayed = FALSE;
173  (*prop)->wasdelayed = FALSE;
174  (*prop)->initialized = FALSE;
175 
176  /* add parameters */
177  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "propagating/%s/priority", name);
178  (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "priority of propagator <%s>", name);
179  SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
180  &(*prop)->priority, TRUE, priority, INT_MIN/4, INT_MAX/4,
181  paramChgdPropPriority, (SCIP_PARAMDATA*)(*prop)) ); /*lint !e740*/
182 
183  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "propagating/%s/freq", name);
184  (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "frequency for calling propagator <%s> (-1: never, 0: only in root node)", name);
185  SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
186  &(*prop)->freq, FALSE, freq, -1, INT_MAX, NULL, NULL) );
187 
188  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "propagating/%s/delay", name);
189  SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem, paramname,
190  "should propagator be delayed, if other propagators found reductions?",
191  &(*prop)->delay, TRUE, delay, NULL, NULL) ); /*lint !e740*/
192 
193  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "propagating/%s/timingmask", name);
194  (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "timing when propagator should be called (%u:BEFORELP, %u:DURINGLPLOOP, %u:AFTERLPLOOP, %u:ALWAYS))", SCIP_PROPTIMING_BEFORELP, SCIP_PROPTIMING_DURINGLPLOOP, SCIP_PROPTIMING_AFTERLPLOOP, SCIP_PROPTIMING_ALWAYS);
195  SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
196  (int*)(&(*prop)->timingmask), TRUE, timingmask, (int) SCIP_PROPTIMING_BEFORELP, (int) SCIP_PROPTIMING_ALWAYS, NULL, NULL) ); /*lint !e713*/
197 
198  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "propagating/%s/presolpriority", name);
199  (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "presolving priority of propagator <%s>", name);
200  SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
201  &(*prop)->presolpriority, TRUE, presolpriority, INT_MIN/4, INT_MAX/4,
202  paramChgdPropPresolPriority, (SCIP_PARAMDATA*)(*prop)) ); /*lint !e740*/
203 
204  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "propagating/%s/maxprerounds", name);
205  SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname,
206  "maximal number of presolving rounds the propagator participates in (-1: no limit)",
207  &(*prop)->maxprerounds, FALSE, presolmaxrounds, -1, INT_MAX, NULL, NULL) ); /*lint !e740*/
208 
209  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "propagating/%s/presoldelay", name);
210  SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem, paramname,
211  "should presolving be delayed, if other presolvers found reductions?",
212  &(*prop)->presoldelay, TRUE, presoldelay, NULL, NULL) ); /*lint !e740*/
213 
214  return SCIP_OKAY;
215 }
216 
217 /** calls destructor and frees memory of propagator */
218 SCIP_RETCODE SCIPpropFree(
219  SCIP_PROP** prop, /**< pointer to propagator data structure */
220  SCIP_SET* set /**< global SCIP settings */
221  )
222 {
223  assert(prop != NULL);
224  assert(*prop != NULL);
225  assert(!(*prop)->initialized);
226  assert(set != NULL);
227 
228  /* call destructor of propagator */
229  if( (*prop)->propfree != NULL )
230  {
231  SCIP_CALL( (*prop)->propfree(set->scip, *prop) );
232  }
233 
234  SCIPclockFree(&(*prop)->presoltime);
235  SCIPclockFree(&(*prop)->resproptime);
236  SCIPclockFree(&(*prop)->sbproptime);
237  SCIPclockFree(&(*prop)->proptime);
238  SCIPclockFree(&(*prop)->setuptime);
239  BMSfreeMemoryArray(&(*prop)->desc);
240  BMSfreeMemoryArray(&(*prop)->name);
241  BMSfreeMemory(prop);
242 
243  return SCIP_OKAY;
244 }
245 
246 /** initializes propagator */
247 SCIP_RETCODE SCIPpropInit(
248  SCIP_PROP* prop, /**< propagator */
249  SCIP_SET* set /**< global SCIP settings */
250  )
251 {
252  assert(prop != NULL);
253  assert(set != NULL);
254 
255  if( prop->initialized )
256  {
257  SCIPerrorMessage("propagator <%s> already initialized\n", prop->name);
258  return SCIP_INVALIDCALL;
259  }
260 
261  if( set->misc_resetstat )
262  {
263  SCIPclockReset(prop->proptime);
264  SCIPclockReset(prop->sbproptime);
265  SCIPclockReset(prop->resproptime);
266  SCIPclockReset(prop->presoltime);
267  SCIPclockReset(prop->setuptime);
268 
269  prop->ncalls = 0;
270  prop->nrespropcalls = 0;
271  prop->ncutoffs = 0;
272  prop->ndomredsfound = 0;
273  prop->lastnfixedvars = 0;
274  prop->lastnaggrvars = 0;
275  prop->lastnchgvartypes = 0;
276  prop->lastnchgbds = 0;
277  prop->lastnaddholes = 0;
278  prop->lastndelconss = 0;
279  prop->lastnaddconss = 0;
280  prop->lastnupgdconss = 0;
281  prop->lastnchgcoefs = 0;
282  prop->lastnchgsides = 0;
283  prop->nfixedvars = 0;
284  prop->naggrvars = 0;
285  prop->nchgvartypes = 0;
286  prop->nchgbds = 0;
287  prop->naddholes = 0;
288  prop->ndelconss = 0;
289  prop->naddconss = 0;
290  prop->nupgdconss = 0;
291  prop->nchgcoefs = 0;
292  prop->nchgsides = 0;
293  prop->npresolcalls = 0;
294  prop->wasdelayed = FALSE;
295  prop->presolwasdelayed = FALSE;
296  }
297 
298  if( prop->propinit != NULL )
299  {
300  /* start timing */
301  SCIPclockStart(prop->setuptime, set);
302 
303  SCIP_CALL( prop->propinit(set->scip, prop) );
304 
305  /* stop timing */
306  SCIPclockStop(prop->setuptime, set);
307  }
308  prop->initialized = TRUE;
309 
310  return SCIP_OKAY;
311 }
312 
313 /** calls exit method of propagator */
314 SCIP_RETCODE SCIPpropExit(
315  SCIP_PROP* prop, /**< propagator */
316  SCIP_SET* set /**< global SCIP settings */
317  )
318 {
319  assert(prop != NULL);
320  assert(set != NULL);
321 
322  if( !prop->initialized )
323  {
324  SCIPerrorMessage("propagator <%s> not initialized\n", prop->name);
325  return SCIP_INVALIDCALL;
326  }
327 
328  if( prop->propexit != NULL )
329  {
330  /* start timing */
331  SCIPclockStart(prop->setuptime, set);
332 
333  SCIP_CALL( prop->propexit(set->scip, prop) );
334 
335  /* stop timing */
336  SCIPclockStop(prop->setuptime, set);
337  }
338  prop->initialized = FALSE;
339 
340  return SCIP_OKAY;
341 }
342 
343 /** informs propagator that the presolving process is being started */
344 SCIP_RETCODE SCIPpropInitpre(
345  SCIP_PROP* prop, /**< propagator */
346  SCIP_SET* set /**< global SCIP settings */
347  )
348 {
349  assert(prop != NULL);
350  assert(set != NULL);
351 
352  prop->lastnfixedvars = 0;
353  prop->lastnaggrvars = 0;
354  prop->lastnchgvartypes = 0;
355  prop->lastnchgbds = 0;
356  prop->lastnaddholes = 0;
357  prop->lastndelconss = 0;
358  prop->lastnaddconss = 0;
359  prop->lastnupgdconss = 0;
360  prop->lastnchgcoefs = 0;
361  prop->lastnchgsides = 0;
362  prop->presolwasdelayed = FALSE;
363  prop->wasdelayed = FALSE;
364 
365  /* call presolving initialization method of propagator */
366  if( prop->propinitpre != NULL )
367  {
368  /* start timing */
369  SCIPclockStart(prop->setuptime, set);
370 
371  SCIP_CALL( prop->propinitpre(set->scip, prop) );
372 
373  /* stop timing */
374  SCIPclockStop(prop->setuptime, set);
375  }
376 
377  return SCIP_OKAY;
378 }
379 
380 /** informs propagator that the presolving process is finished */
381 SCIP_RETCODE SCIPpropExitpre(
382  SCIP_PROP* prop, /**< propagator */
383  SCIP_SET* set /**< global SCIP settings */
384  )
385 {
386  assert(prop != NULL);
387  assert(set != NULL);
388 
389  /* call presolving deinitialization method of propagator */
390  if( prop->propexitpre != NULL )
391  {
392  /* start timing */
393  SCIPclockStart(prop->setuptime, set);
394 
395  SCIP_CALL( prop->propexitpre(set->scip, prop) );
396 
397  /* stop timing */
398  SCIPclockStop(prop->setuptime, set);
399  }
400 
401  return SCIP_OKAY;
402 }
403 
404 /** informs propagator that the prop and bound process is being started */
405 SCIP_RETCODE SCIPpropInitsol(
406  SCIP_PROP* prop, /**< propagator */
407  SCIP_SET* set /**< global SCIP settings */
408  )
409 {
410  assert(prop != NULL);
411  assert(set != NULL);
412 
413  /* call solving process initialization method of propagator */
414  if( prop->propinitsol != NULL )
415  {
416  /* start timing */
417  SCIPclockStart(prop->setuptime, set);
418 
419  SCIP_CALL( prop->propinitsol(set->scip, prop) );
420 
421  /* stop timing */
422  SCIPclockStop(prop->setuptime, set);
423  }
424 
425  return SCIP_OKAY;
426 }
427 
428 /** informs propagator that the prop and bound process data is being freed */
429 SCIP_RETCODE SCIPpropExitsol(
430  SCIP_PROP* prop, /**< propagator */
431  SCIP_SET* set, /**< global SCIP settings */
432  SCIP_Bool restart /**< was this exit solve call triggered by a restart? */
433  )
434 {
435  assert(prop != NULL);
436  assert(set != NULL);
437 
438  /* call solving process deinitialization method of propagator */
439  if( prop->propexitsol != NULL )
440  {
441  /* start timing */
442  SCIPclockStart(prop->setuptime, set);
443 
444  SCIP_CALL( prop->propexitsol(set->scip, prop, restart) );
445 
446  /* stop timing */
447  SCIPclockStop(prop->setuptime, set);
448  }
449 
450  return SCIP_OKAY;
451 }
452 
453 /** executes presolving method of propagator */
454 SCIP_RETCODE SCIPpropPresol(
455  SCIP_PROP* prop, /**< propagator */
456  SCIP_SET* set, /**< global SCIP settings */
457  SCIP_Bool execdelayed, /**< execute presolving even if it is marked to be delayed */
458  int nrounds, /**< number of presolving rounds already done */
459  int* nfixedvars, /**< pointer to total number of variables fixed of all presolvers */
460  int* naggrvars, /**< pointer to total number of variables aggregated of all presolvers */
461  int* nchgvartypes, /**< pointer to total number of variable type changes of all presolvers */
462  int* nchgbds, /**< pointer to total number of variable bounds tightened of all presolvers */
463  int* naddholes, /**< pointer to total number of domain holes added of all presolvers */
464  int* ndelconss, /**< pointer to total number of deleted constraints of all presolvers */
465  int* naddconss, /**< pointer to total number of added constraints of all presolvers */
466  int* nupgdconss, /**< pointer to total number of upgraded constraints of all presolvers */
467  int* nchgcoefs, /**< pointer to total number of changed coefficients of all presolvers */
468  int* nchgsides, /**< pointer to total number of changed left/right hand sides of all presolvers */
469  SCIP_RESULT* result /**< pointer to store the result of the callback method */
470  )
471 {
472  assert(prop != NULL);
473  assert(set != NULL);
474  assert(nfixedvars != NULL);
475  assert(naggrvars != NULL);
476  assert(nchgvartypes != NULL);
477  assert(nchgbds != NULL);
478  assert(naddholes != NULL);
479  assert(ndelconss != NULL);
480  assert(naddconss != NULL);
481  assert(nupgdconss != NULL);
482  assert(nchgcoefs != NULL);
483  assert(nchgsides != NULL);
484  assert(result != NULL);
485 
486  *result = SCIP_DIDNOTRUN;
487 
488  if( prop->proppresol == NULL )
489  return SCIP_OKAY;
490 
491  /* check number of presolving rounds */
492  if( prop->maxprerounds >= 0 && nrounds >= prop->maxprerounds && !prop->presolwasdelayed )
493  return SCIP_OKAY;
494 
495  /* check, if presolver should be delayed */
496  if( !prop->presoldelay || execdelayed )
497  {
498  int nnewfixedvars;
499  int nnewaggrvars;
500  int nnewchgvartypes;
501  int nnewchgbds;
502  int nnewaddholes;
503  int nnewdelconss;
504  int nnewaddconss;
505  int nnewupgdconss;
506  int nnewchgcoefs;
507  int nnewchgsides;
508 
509  SCIPdebugMessage("calling presolving method of propagator <%s>\n", prop->name);
510 
511  /* calculate the number of changes since last call */
512  nnewfixedvars = *nfixedvars - prop->lastnfixedvars;
513  nnewaggrvars = *naggrvars - prop->lastnaggrvars;
514  nnewchgvartypes = *nchgvartypes - prop->lastnchgvartypes;
515  nnewchgbds = *nchgbds - prop->lastnchgbds;
516  nnewaddholes = *naddholes - prop->lastnaddholes;
517  nnewdelconss = *ndelconss - prop->lastndelconss;
518  nnewaddconss = *naddconss - prop->lastnaddconss;
519  nnewupgdconss = *nupgdconss - prop->lastnupgdconss;
520  nnewchgcoefs = *nchgcoefs - prop->lastnchgcoefs;
521  nnewchgsides = *nchgsides - prop->lastnchgsides;
522 
523  /* remember the number of changes prior to the call of the presolver method of the propagator */
524  prop->lastnfixedvars = *nfixedvars;
525  prop->lastnaggrvars = *naggrvars;
526  prop->lastnchgvartypes = *nchgvartypes;
527  prop->lastnchgbds = *nchgbds;
528  prop->lastnaddholes = *naddholes;
529  prop->lastndelconss = *ndelconss;
530  prop->lastnaddconss = *naddconss;
531  prop->lastnupgdconss = *nupgdconss;
532  prop->lastnchgcoefs = *nchgcoefs;
533  prop->lastnchgsides = *nchgsides;
534 
535  /* start timing */
536  SCIPclockStart(prop->presoltime, set);
537 
538  /* call external method */
539  SCIP_CALL( prop->proppresol(set->scip, prop, nrounds,
540  nnewfixedvars, nnewaggrvars, nnewchgvartypes, nnewchgbds, nnewaddholes,
541  nnewdelconss, nnewaddconss, nnewupgdconss, nnewchgcoefs, nnewchgsides,
542  nfixedvars, naggrvars, nchgvartypes, nchgbds, naddholes,
543  ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides, result) );
544 
545  /* stop timing */
546  SCIPclockStop(prop->presoltime, set);
547 
548  /* add/count the new changes */
549  prop->nfixedvars += *nfixedvars - prop->lastnfixedvars;
550  prop->naggrvars += *naggrvars - prop->lastnaggrvars;
551  prop->nchgvartypes += *nchgvartypes - prop->lastnchgvartypes;
552  prop->nchgbds += *nchgbds - prop->lastnchgbds;
553  prop->naddholes += *naddholes - prop->lastnaddholes;
554  prop->ndelconss += *ndelconss - prop->lastndelconss;
555  prop->naddconss += *naddconss - prop->lastnaddconss;
556  prop->nupgdconss += *nupgdconss - prop->lastnupgdconss;
557  prop->nchgcoefs += *nchgcoefs - prop->lastnchgcoefs;
558  prop->nchgsides += *nchgsides - prop->lastnchgsides;
559 
560  /* check result code of callback method */
561  if( *result != SCIP_CUTOFF
562  && *result != SCIP_UNBOUNDED
563  && *result != SCIP_SUCCESS
564  && *result != SCIP_DIDNOTFIND
565  && *result != SCIP_DIDNOTRUN
566  && *result != SCIP_DELAYED )
567  {
568  SCIPerrorMessage("propagator <%s> returned invalid result <%d>\n", prop->name, *result);
569  return SCIP_INVALIDRESULT;
570  }
571 
572  /* increase the number of presolving calls, if the propagator tried to find reductions */
573  if( *result != SCIP_DIDNOTRUN && *result != SCIP_DELAYED )
574  ++(prop->npresolcalls);
575  }
576  else
577  {
578  SCIPdebugMessage("presolving of propagator <%s> was delayed\n", prop->name);
579  *result = SCIP_DELAYED;
580  }
581 
582  /* remember whether presolving was delayed */
583  prop->presolwasdelayed = (*result == SCIP_DELAYED);
584 
585  return SCIP_OKAY;
586 }
587 
588 /** calls execution method of propagator */
589 SCIP_RETCODE SCIPpropExec(
590  SCIP_PROP* prop, /**< propagator */
591  SCIP_SET* set, /**< global SCIP settings */
592  SCIP_STAT* stat, /**< dynamic problem statistics */
593  int depth, /**< depth of current node */
594  SCIP_Bool execdelayed, /**< execute propagator even if it is marked to be delayed */
595  SCIP_Bool instrongbranching, /**< are we currently doing strong branching? */
596  SCIP_PROPTIMING proptiming, /**< current point in the node solving process */
597  SCIP_RESULT* result /**< pointer to store the result of the callback method */
598  )
599 {
600  assert(prop != NULL);
601  assert(prop->propexec != NULL);
602  assert(prop->freq >= -1);
603  assert(set != NULL);
604  assert(set->scip != NULL);
605  assert(stat != NULL);
606  assert(depth >= 0);
607  assert(result != NULL);
608 
609  if( (depth == 0 && prop->freq == 0) || (prop->freq > 0 && depth % prop->freq == 0) )
610  {
611  if( !prop->delay || execdelayed )
612  {
613  SCIP_Longint oldndomchgs;
614  SCIP_Longint oldnprobdomchgs;
615 
616  SCIPdebugMessage("executing propagator <%s>\n", prop->name);
617 
618  oldndomchgs = stat->nboundchgs + stat->nholechgs;
619  oldnprobdomchgs = stat->nprobboundchgs + stat->nprobholechgs;
620 
621  /* start timing */
622  if( instrongbranching )
623  SCIPclockStart(prop->sbproptime, set);
624  else
625  SCIPclockStart(prop->proptime, set);
626 
627  /* call external propagation method */
628  SCIP_CALL( prop->propexec(set->scip, prop, proptiming, result) );
629 
630  /* stop timing */
631  if( instrongbranching )
632  SCIPclockStop(prop->sbproptime, set);
633  else
634  SCIPclockStop(prop->proptime, set);
635 
636  /* update statistics */
637  if( *result != SCIP_DIDNOTRUN && *result != SCIP_DELAYED )
638  prop->ncalls++;
639  if( *result == SCIP_CUTOFF )
640  prop->ncutoffs++;
641 
642  /* update domain reductions; therefore remove the domain
643  * reduction counts which were generated in probing mode */
644  prop->ndomredsfound += stat->nboundchgs + stat->nholechgs - oldndomchgs;
645  prop->ndomredsfound -= (stat->nprobboundchgs + stat->nprobholechgs - oldnprobdomchgs);
646 
647  /* evaluate result */
648  if( *result != SCIP_CUTOFF
649  && *result != SCIP_REDUCEDDOM
650  && *result != SCIP_DIDNOTFIND
651  && *result != SCIP_DIDNOTRUN
652  && *result != SCIP_DELAYED )
653  {
654  SCIPerrorMessage("execution method of propagator <%s> returned invalid result <%d>\n",
655  prop->name, *result);
656  return SCIP_INVALIDRESULT;
657  }
658  }
659  else
660  {
661  SCIPdebugMessage("propagator <%s> was delayed\n", prop->name);
662  *result = SCIP_DELAYED;
663  }
664 
665  /* remember whether propagator was delayed */
666  prop->wasdelayed = (*result == SCIP_DELAYED);
667  }
668  else
669  *result = SCIP_DIDNOTRUN;
670 
671  return SCIP_OKAY;
672 }
673 
674 /** resolves the given conflicting bound, that was deduced by the given propagator, by putting all "reason" bounds
675  * leading to the deduction into the conflict queue with calls to SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPaddConflictBd(),
676  * SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), SCIPaddConflictRelaxedBd(), or SCIPaddConflictBinvar();
677  *
678  * @note it is sufficient to explain the relaxed bound change
679  */
680 SCIP_RETCODE SCIPpropResolvePropagation(
681  SCIP_PROP* prop, /**< propagator */
682  SCIP_SET* set, /**< global SCIP settings */
683  SCIP_VAR* infervar, /**< variable whose bound was deduced by the constraint */
684  int inferinfo, /**< user inference information attached to the bound change */
685  SCIP_BOUNDTYPE inferboundtype, /**< bound that was deduced (lower or upper bound) */
686  SCIP_BDCHGIDX* bdchgidx, /**< bound change index, representing the point of time where change took place */
687  SCIP_Real relaxedbd, /**< the relaxed bound */
688  SCIP_RESULT* result /**< pointer to store the result of the callback method */
689  )
690 {
691  assert(prop != NULL);
692  assert((inferboundtype == SCIP_BOUNDTYPE_LOWER
693  && SCIPvarGetLbAtIndex(infervar, bdchgidx, TRUE) > SCIPvarGetLbGlobal(infervar))
694  || (inferboundtype == SCIP_BOUNDTYPE_UPPER
695  && SCIPvarGetUbAtIndex(infervar, bdchgidx, TRUE) < SCIPvarGetUbGlobal(infervar)));
696  assert(result != NULL);
697 
698  *result = SCIP_DIDNOTRUN;
699 
700  if( prop->propresprop != NULL )
701  {
702 
703  /* start timing */
704  SCIPclockStart(prop->resproptime, set);
705 
706  SCIP_CALL( prop->propresprop(set->scip, prop, infervar, inferinfo, inferboundtype, bdchgidx,
707  relaxedbd, result) );
708 
709  /* stop timing */
710  SCIPclockStop(prop->resproptime, set);
711 
712  /* update statistic */
713  prop->nrespropcalls++;
714 
715  /* check result code */
716  if( *result != SCIP_SUCCESS && *result != SCIP_DIDNOTFIND )
717  {
718  SCIPerrorMessage("propagation conflict resolving method of propagator <%s> returned invalid result <%d>\n",
719  prop->name, *result);
720  return SCIP_INVALIDRESULT;
721  }
722  }
723  else
724  {
725  SCIPerrorMessage("propagation conflict resolving method of propagator <%s> is not implemented\n", prop->name);
726  return SCIP_PLUGINNOTFOUND;
727  }
728 
729  return SCIP_OKAY;
730 }
731 
732 /** gets user data of propagator */
733 SCIP_PROPDATA* SCIPpropGetData(
734  SCIP_PROP* prop /**< propagator */
735  )
736 {
737  assert(prop != NULL);
738 
739  return prop->propdata;
740 }
741 
742 /** sets user data of propagator; user has to free old data in advance! */
743 void SCIPpropSetData(
744  SCIP_PROP* prop, /**< propagator */
745  SCIP_PROPDATA* propdata /**< new propagator user data */
746  )
747 {
748  assert(prop != NULL);
749 
750  prop->propdata = propdata;
751 }
752 
753 /** sets copy method of propagator */
754 void SCIPpropSetCopy(
755  SCIP_PROP* prop, /**< propagator */
756  SCIP_DECL_PROPCOPY ((*propcopy)) /**< copy method of propagator or NULL if you don't want to copy your plugin into sub-SCIPs */
757  )
758 {
759  assert(prop != NULL);
760 
761  prop->propcopy = propcopy;
762 }
763 
764 /** sets destructor method of propagator */
765 void SCIPpropSetFree(
766  SCIP_PROP* prop, /**< propagator */
767  SCIP_DECL_PROPFREE ((*propfree)) /**< destructor of propagator */
768  )
769 {
770  assert(prop != NULL);
771 
772  prop->propfree = propfree;
773 }
774 
775 /** sets initialization method of propagator */
776 void SCIPpropSetInit(
777  SCIP_PROP* prop, /**< propagator */
778  SCIP_DECL_PROPINIT ((*propinit)) /**< initialize propagator */
779  )
780 {
781  assert(prop != NULL);
782 
783  prop->propinit = propinit;
784 }
785 
786 /** sets deinitialization method of propagator */
787 void SCIPpropSetExit(
788  SCIP_PROP* prop, /**< propagator */
789  SCIP_DECL_PROPEXIT ((*propexit)) /**< deinitialize propagator */
790  )
791 {
792  assert(prop != NULL);
793 
794  prop->propexit = propexit;
795 }
796 
797 /** sets solving process initialization method of propagator */
798 void SCIPpropSetInitsol(
799  SCIP_PROP* prop, /**< propagator */
800  SCIP_DECL_PROPINITSOL((*propinitsol)) /**< solving process initialization method of propagator */
801  )
802 {
803  assert(prop != NULL);
804 
805  prop->propinitsol = propinitsol;
806 }
807 
808 /** sets solving process deinitialization method of propagator */
809 void SCIPpropSetExitsol(
810  SCIP_PROP* prop, /**< propagator */
811  SCIP_DECL_PROPEXITSOL ((*propexitsol)) /**< solving process deinitialization method of propagator */
812  )
813 {
814  assert(prop != NULL);
815 
816  prop->propexitsol = propexitsol;
817 }
818 
819 /** sets preprocessing initialization method of propagator */
820 void SCIPpropSetInitpre(
821  SCIP_PROP* prop, /**< propagator */
822  SCIP_DECL_PROPINITPRE((*propinitpre)) /**< preprocessing initialization method of propagator */
823  )
824 {
825  assert(prop != NULL);
826 
827  prop->propinitpre = propinitpre;
828 }
829 
830 
831 
832 /** sets preprocessing deinitialization method of propagator */
833 void SCIPpropSetExitpre(
834  SCIP_PROP* prop, /**< propagator */
835  SCIP_DECL_PROPEXITPRE((*propexitpre)) /**< preprocessing deinitialization method of propagator */
836  )
837 {
838  assert(prop != NULL);
839 
840  prop->propexitpre = propexitpre;
841 }
842 
843 /** sets presolving method of propagator */
844 void SCIPpropSetPresol(
845  SCIP_PROP* prop, /**< propagator */
846  SCIP_DECL_PROPPRESOL ((*proppresol)), /**< presolving method */
847  int presolpriority, /**< presolving priority of the propagator (>= 0: before, < 0: after constraint handlers) */
848  int presolmaxrounds, /**< maximal number of presolving rounds the propagator participates in (-1: no limit) */
849  SCIP_Bool presoldelay /**< should presolving be delayed, if other presolvers found reductions? */
850  )
851 {
852  assert(prop != NULL);
853 
854  prop->proppresol = proppresol;
855  prop->presolpriority = presolpriority;
856  prop->presoldelay = presoldelay;
857  prop->maxprerounds = presolmaxrounds;
858 }
859 
860 /** sets propagation conflict resolving callback of propagator */
861 void SCIPpropSetResprop(
862  SCIP_PROP* prop, /**< propagator */
863  SCIP_DECL_PROPRESPROP ((*propresprop)) /**< propagation conflict resolving callback */
864  )
865 {
866  assert(prop != NULL);
867 
868  prop->propresprop = propresprop;
869 }
870 
871 /** gets name of propagator */
872 const char* SCIPpropGetName(
873  SCIP_PROP* prop /**< propagator */
874  )
875 {
876  assert(prop != NULL);
877 
878  return prop->name;
879 }
880 
881 /** gets description of propagator */
882 const char* SCIPpropGetDesc(
883  SCIP_PROP* prop /**< propagator */
884  )
885 {
886  assert(prop != NULL);
887 
888  return prop->desc;
889 }
890 
891 /** gets priority of propagator */
892 int SCIPpropGetPriority(
893  SCIP_PROP* prop /**< propagator */
894  )
895 {
896  assert(prop != NULL);
897 
898  return prop->priority;
899 }
900 
901 /** gets presolving priority of propagator */
902 int SCIPpropGetPresolPriority(
903  SCIP_PROP* prop /**< propagator */
904  )
905 {
906  assert(prop != NULL);
907 
908  return prop->presolpriority;
909 }
910 
911 /** sets priority of propagator */
912 void SCIPpropSetPriority(
913  SCIP_PROP* prop, /**< propagator */
914  SCIP_SET* set, /**< global SCIP settings */
915  int priority /**< new priority of the propagator */
916  )
917 {
918  assert(prop != NULL);
919  assert(set != NULL);
920 
921  prop->priority = priority;
922  set->propssorted = FALSE;
923 }
924 
925 /** sets presolving priority of propagator */
926 void SCIPpropSetPresolPriority(
927  SCIP_PROP* prop, /**< propagator */
928  SCIP_SET* set, /**< global SCIP settings */
929  int presolpriority /**< new priority of the propagator */
930  )
931 {
932  assert(prop != NULL);
933  assert(set != NULL);
934 
935  prop->presolpriority = presolpriority;
936  set->propspresolsorted = FALSE;
937 }
938 
939 /** gets frequency of propagator */
940 int SCIPpropGetFreq(
941  SCIP_PROP* prop /**< propagator */
942  )
943 {
944  assert(prop != NULL);
945 
946  return prop->freq;
947 }
948 
949 /** gets time in seconds used for setting up this propagator for new stages */
950 SCIP_Real SCIPpropGetSetupTime(
951  SCIP_PROP* prop /**< propagator */
952  )
953 {
954  assert(prop != NULL);
955 
956  return SCIPclockGetTime(prop->setuptime);
957 }
958 
959 /** sets frequency of propagator */
960 void SCIPpropSetFreq(
961  SCIP_PROP* prop, /**< propagator */
962  int freq /**< new frequency of propagator */
963  )
964 {
965  assert(prop != NULL);
966  assert(freq >= -1);
967 
968  prop->freq = freq;
969 }
970 
971 /** gets time in seconds used in this propagator for propagation */
972 SCIP_Real SCIPpropGetTime(
973  SCIP_PROP* prop /**< propagator */
974  )
975 {
976  assert(prop != NULL);
977 
978  return SCIPclockGetTime(prop->proptime);
979 }
980 
981 /** gets time in seconds used in this propagator for propagation during strong branching */
982 SCIP_Real SCIPpropGetStrongBranchPropTime(
983  SCIP_PROP* prop /**< propagator */
984  )
985 {
986  assert(prop != NULL);
987 
988  return SCIPclockGetTime(prop->sbproptime);
989 }
990 
991 /** gets time in seconds used in this propagator for resolve propagation */
992 SCIP_Real SCIPpropGetRespropTime(
993  SCIP_PROP* prop /**< propagator */
994  )
995 {
996  assert(prop != NULL);
997 
998  return SCIPclockGetTime(prop->resproptime);
999 }
1000 
1001 /** gets time in seconds used in this propagator for presolving */
1002 SCIP_Real SCIPpropGetPresolTime(
1003  SCIP_PROP* prop /**< propagator */
1004  )
1005 {
1006  assert(prop != NULL);
1007 
1008  return SCIPclockGetTime(prop->presoltime);
1009 }
1010 
1011 /** gets the total number of times, the propagator was called */
1012 SCIP_Longint SCIPpropGetNCalls(
1013  SCIP_PROP* prop /**< propagator */
1014  )
1015 {
1016  assert(prop != NULL);
1017 
1018  return prop->ncalls;
1019 }
1020 
1021 /** gets the total number of times, the propagator was called for resolving a propagation */
1022 SCIP_Longint SCIPpropGetNRespropCalls(
1023  SCIP_PROP* prop /**< propagator */
1024  )
1025 {
1026  assert(prop != NULL);
1027 
1028  return prop->nrespropcalls;
1029 }
1030 
1031 /** gets total number of times, this propagator detected a cutoff */
1032 SCIP_Longint SCIPpropGetNCutoffs(
1033  SCIP_PROP* prop /**< propagator */
1034  )
1035 {
1036  assert(prop != NULL);
1037 
1038  return prop->ncutoffs;
1039 }
1040 
1041 /** gets total number of domain reductions found by this propagator */
1042 SCIP_Longint SCIPpropGetNDomredsFound(
1043  SCIP_PROP* prop /**< propagator */
1044  )
1045 {
1046  assert(prop != NULL);
1047 
1048  return prop->ndomredsfound;
1049 }
1050 
1051 /** should propagator be delayed, if other propagators found reductions? */
1052 SCIP_Bool SCIPpropIsDelayed(
1053  SCIP_PROP* prop /**< propagator */
1054  )
1055 {
1056  assert(prop != NULL);
1057 
1058  return prop->delay;
1059 }
1060 
1061 /** should propagator be delayed during presolving, if other propagators found reductions? */
1062 SCIP_Bool SCIPpropIsPresolDelayed(
1063  SCIP_PROP* prop /**< propagator */
1064  )
1065 {
1066  assert(prop != NULL);
1067 
1068  return prop->presoldelay;
1069 }
1070 
1071 /** was propagator delayed at the last call? */
1072 SCIP_Bool SCIPpropWasDelayed(
1073  SCIP_PROP* prop /**< propagator */
1074  )
1075 {
1076  assert(prop != NULL);
1077 
1078  return prop->wasdelayed;
1079 }
1080 
1081 /** was presolving of propagator delayed at the last call? */
1082 SCIP_Bool SCIPpropWasPresolDelayed(
1083  SCIP_PROP* prop /**< propagator */
1084  )
1085 {
1086  assert(prop != NULL);
1087 
1088  return prop->presolwasdelayed;
1089 }
1090 
1091 /** is propagator initialized? */
1092 SCIP_Bool SCIPpropIsInitialized(
1093  SCIP_PROP* prop /**< propagator */
1094  )
1095 {
1096  assert(prop != NULL);
1097 
1098  return prop->initialized;
1099 }
1100 
1101 /** gets number of variables fixed during presolving of propagator */
1102 int SCIPpropGetNFixedVars(
1103  SCIP_PROP* prop /**< propagator */
1104  )
1105 {
1106  assert(prop != NULL);
1107 
1108  return prop->nfixedvars;
1109 }
1110 
1111 /** gets number of variables aggregated during presolving of propagator */
1112 int SCIPpropGetNAggrVars(
1113  SCIP_PROP* prop /**< propagator */
1114  )
1115 {
1116  assert(prop != NULL);
1117 
1118  return prop->naggrvars;
1119 }
1120 
1121 /** gets number of variable types changed during presolving of propagator */
1122 int SCIPpropGetNChgVarTypes(
1123  SCIP_PROP* prop /**< propagator */
1124  )
1125 {
1126  assert(prop != NULL);
1127 
1128  return prop->nchgvartypes;
1129 }
1130 
1131 /** gets number of bounds changed during presolving of propagator */
1132 int SCIPpropGetNChgBds(
1133  SCIP_PROP* prop /**< propagator */
1134  )
1135 {
1136  assert(prop != NULL);
1137 
1138  return prop->nchgbds;
1139 }
1140 
1141 /** gets number of holes added to domains of variables during presolving of propagator */
1142 int SCIPpropGetNAddHoles(
1143  SCIP_PROP* prop /**< propagator */
1144  )
1145 {
1146  assert(prop != NULL);
1147 
1148  return prop->naddholes;
1149 }
1150 
1151 /** gets number of constraints deleted during presolving of propagator */
1152 int SCIPpropGetNDelConss(
1153  SCIP_PROP* prop /**< propagator */
1154  )
1155 {
1156  assert(prop != NULL);
1157 
1158  return prop->ndelconss;
1159 }
1160 
1161 /** gets number of constraints added during presolving of propagator */
1162 int SCIPpropGetNAddConss(
1163  SCIP_PROP* prop /**< propagator */
1164  )
1165 {
1166  assert(prop != NULL);
1167 
1168  return prop->naddconss;
1169 }
1170 
1171 /** gets number of constraints upgraded during presolving of propagator */
1172 int SCIPpropGetNUpgdConss(
1173  SCIP_PROP* prop /**< propagator */
1174  )
1175 {
1176  assert(prop != NULL);
1177 
1178  return prop->nupgdconss;
1179 }
1180 
1181 /** gets number of coefficients changed during presolving of propagator */
1182 int SCIPpropGetNChgCoefs(
1183  SCIP_PROP* prop /**< propagator */
1184  )
1185 {
1186  assert(prop != NULL);
1187 
1188  return prop->nchgcoefs;
1189 }
1190 
1191 /** gets number of constraint sides changed during presolving of propagator */
1192 int SCIPpropGetNChgSides(
1193  SCIP_PROP* prop /**< propagator */
1194  )
1195 {
1196  assert(prop != NULL);
1197 
1198  return prop->nchgsides;
1199 }
1200 
1201 /** gets number of times the propagator was called in presolving and tried to find reductions */
1202 int SCIPpropGetNPresolCalls(
1203  SCIP_PROP* prop /**< propagator */
1204  )
1205 {
1206  assert(prop != NULL);
1207 
1208  return prop->npresolcalls;
1209 }
1210 
1211 /** returns the timing mask of the propagator */
1212 SCIP_PROPTIMING SCIPpropGetTimingmask(
1213  SCIP_PROP* prop /**< propagator */
1214  )
1215 {
1216  assert(prop != NULL);
1217 
1218  return prop->timingmask;
1219 }
1220 
1221 /** does the propagator perform presolving? */
1222 SCIP_Bool SCIPpropDoesPresolve(
1223  SCIP_PROP* prop /**< propagator */
1224  )
1225 {
1226  assert(prop != NULL);
1227 
1228  return (prop->proppresol != NULL);
1229 }
1230