Scippy

SCIP

Solving Constraint Integer Programs

prop_probing.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-2017 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_probing.c
17  * @brief probing propagator
18  * @author Tobias Achterberg
19  * @author Matthias Miltenberger
20  * @author Michael Winkler
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/prop_probing.h"
29 #include "scip/pub_misc.h"
30 
31 
32 #define PROP_NAME "probing"
33 #define PROP_DESC "probing propagator on binary variables"
34 #define PROP_TIMING SCIP_PROPTIMING_AFTERLPLOOP
35 #define PROP_PRIORITY -100000 /**< propagation priority */
36 #define PROP_FREQ -1 /**< propagation frequency */
37 #define PROP_DELAY TRUE /**< should propagation method be delayed, if other propagators found
38  * reductions? */
39 #define PROP_PRESOL_PRIORITY -100000 /**< priority of the presolving method (>= 0: before, < 0: after constraint handlers); combined with presolvers */
40 #define PROP_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolving method (fast, medium, or exhaustive) */
41 #define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no
42  * limit) */
43 #define MAXDNOM 10000LL /**< maximal denominator for simple rational fixed values */
44 
45 
46 /* @todo check for restricting the maximal number of implications that can be added by probing */
47 
48 /* sorting of probing variables, two different variants are implemeneted */
49 /* #define VARIANT_B */
50 
51 
52 /*
53  * Default parameter settings
54  */
55 
56 #define DEFAULT_MAXRUNS 1 /**< maximal number of runs, probing participates in (-1: no limit) */
57 #define DEFAULT_PROPROUNDS -1 /**< maximal number of propagation rounds in probing subproblems */
58 #define DEFAULT_MAXFIXINGS 25 /**< maximal number of fixings found, until probing is interrupted
59  * (0: don't interrupt) */
60 #define DEFAULT_MAXUSELESS 1000 /**< maximal number of successive probings without fixings,
61  * until probing is aborted (0: don't abort) */
62 #define DEFAULT_MAXTOTALUSELESS 50 /**< maximal number of successive probings without fixings, bound changes,
63  * and implications, until probing is aborted (0: don't abort) */
64 #define DEFAULT_MAXSUMUSELESS 0 /**< maximal number of probings without fixings, until probing is aborted
65  * (0: don't abort) */
66 #define DEFAULT_MAXDEPTH -1 /**< maximal depth until propagation is executed(-1: no limit) */
67 #define DEFAULT_RANDSEED 59 /**< random initial seed */
68 
69 /*
70  * Data structures
71  */
72 
73 /** propagator data */
74 struct SCIP_PropData
75 {
76  SCIP_VAR** sortedvars; /**< problem variables sorted by number of rounding locks, used in presolving */
77  int* nprobed; /**< array of numbers how often we already probed on each variables */
78  int noldtotalvars; /**< number of total variables in problem */
79  int nsortedvars; /**< number of problem variables, used in presolving */
80  int nsortedbinvars; /**< number of binary problem variables, used in presolving */
81  int maxruns; /**< maximal number of runs, probing participates in (-1: no limit) */
82  int proprounds; /**< maximal number of propagation rounds in probing subproblems */
83  int maxfixings; /**< maximal number of fixings found, until probing is interrupted
84  * (0: don't interrupt) */
85  int maxuseless; /**< maximal number of successive probings without fixings,
86  * until probing is aborted (0: don't abort) */
87  int maxtotaluseless; /**< maximal number of successive probings without fixings, bound changes,
88  * and implications, until probing is aborted (0: don't abort) */
89  int maxsumuseless; /**< maximal number of probings without fixings, until probing is aborted
90  * (0: don't abort) */
91  int startidx; /**< starting variable index of next call, used in presolving */
92  int lastsortstartidx; /**< last starting variable index where the variables have been sorted, used in presolving */
93  int nfixings; /**< total number of fixings found in probing */
94  int naggregations; /**< total number of aggregations found in probing */
95  int nimplications; /**< total number of implications found in probing */
96  int nbdchgs; /**< total number of bound changes found in probing */
97  int nuseless; /**< current number of successive useless probings */
98  int ntotaluseless; /**< current number of successive totally useless probings */
99  int nsumuseless; /**< current number of useless probings */
100  int maxdepth; /**< maximal depth until propagation is executed */
101  SCIP_Longint lastnode; /**< last node where probing was applied, or -1 for presolving, and -2 for not applied yet */
102  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
103 };
104 
105 
106 /*
107  * Local methods
108  */
109 /** initializes the propagator data */
110 static
112  SCIP* scip, /**< SCIP data structure */
113  SCIP_PROPDATA* propdata /**< propagator data */
114  )
115 {
116  assert(propdata != NULL);
118  propdata->sortedvars = NULL;
119  propdata->nprobed = NULL;
120  propdata->noldtotalvars = 0;
121  propdata->nsortedvars = 0;
122  propdata->nsortedbinvars = 0;
123  propdata->startidx = 0;
124  propdata->lastsortstartidx = -1;
125  propdata->nfixings = 0;
126  propdata->naggregations = 0;
127  propdata->nimplications = 0;
128  propdata->nbdchgs = 0;
129  propdata->nuseless = 0;
130  propdata->ntotaluseless = 0;
131  propdata->nsumuseless = 0;
132  propdata->lastnode = -2;
133  propdata->randnumgen = NULL;
134 
135  return SCIP_OKAY;
136 }
137 
138 /** frees the sorted vars array */
139 static
141  SCIP* scip, /**< SCIP data structure */
142  SCIP_PROPDATA* propdata /**< propagator data */
143  )
144 {
145  assert(propdata != NULL);
147  if( propdata->sortedvars != NULL )
148  {
149  int i;
150 
151  /* release variables */
152  for( i = 0; i < propdata->nsortedvars; ++i )
153  {
154  SCIP_CALL( SCIPreleaseVar(scip, &propdata->sortedvars[i]) );
155  }
156  SCIPfreeMemoryArray(scip, &propdata->sortedvars);
157  propdata->nsortedvars = 0;
158  propdata->nsortedbinvars = 0;
159  }
160 
161  SCIPfreeMemoryArrayNull(scip, &propdata->nprobed);
162  propdata->noldtotalvars = 0;
163 
164  return SCIP_OKAY;
165 }
166 
167 /** sorts the binary variables starting with the given index by rounding locks and implications */
168 static
170  SCIP* scip, /**< SCIP data structure */
171  SCIP_PROPDATA* propdata, /**< propagator data */
172  SCIP_VAR** vars, /**< problem variables to be sorted */
173  int nvars, /**< number of problem variables to be sorted */
174  int firstidx /**< first index that should be subject to sorting */
175  )
176 {
177  SCIP_VAR** sortedvars;
178  int nsortedvars;
179  SCIP_Real* scores;
180  int i;
181  int minnprobings;
182  SCIP_Real maxscore;
183  int nlocksdown;
184  int nlocksup;
185  int nimplzero;
186  int nimplone;
187  int nclqzero;
188  int nclqone;
189 
190  assert(propdata != NULL);
191  assert(propdata->nprobed != NULL);
192 
193  assert(vars != NULL || nvars == 0);
194 
195  nsortedvars = nvars - firstidx;
196  if( nsortedvars <= 0 )
197  return SCIP_OKAY;
198 
199  assert(vars != NULL);
200 
201  sortedvars = &(vars[firstidx]);
202 
203  SCIPdebugMsg(scip, "resorting probing variables %d to %d\n", firstidx, nvars-1);
204 
205  /* sort the variables by number of rounding locks and implications */
206  SCIP_CALL( SCIPallocBufferArray(scip, &scores, nsortedvars) );
207 
208  maxscore = -1.0;
209  minnprobings = INT_MAX;
210 
211  /* determine maximal possible score and minimal number of probings over all variables */
212  for( i = 0; i < nvars; ++i )
213  {
214  SCIP_VAR* var;
215  SCIP_Real tmp;
216 
217  var = vars[i];
218 
219  assert(SCIPvarIsBinary(var));
220  assert(propdata->noldtotalvars > SCIPvarGetIndex(var));
221  assert(propdata->nprobed[SCIPvarGetIndex(var)] >= 0);
222 
223  if( SCIPvarIsActive(var) )
224  {
225  nlocksdown = SCIPvarGetNLocksDown(var);
226  nlocksup = SCIPvarGetNLocksUp(var);
227  nimplzero = SCIPvarGetNImpls(var, FALSE);
228  nimplone = SCIPvarGetNImpls(var, TRUE);
229  nclqzero = SCIPvarGetNCliques(var, FALSE);
230  nclqone = SCIPvarGetNCliques(var, TRUE);
231 
232 #ifndef VARIANT_B
233  tmp = -MAX(nlocksdown, nlocksup)
234  + 10.0 * MIN(nimplzero, nimplone)
235  + 100.0 * MIN(nclqzero, nclqone);
236 #else
237  tmp = - ABS(nlocksdown - nlocksup)
238  + MIN(nlocksdown, nlocksup)
239  + 500.0 * nimplzero + 50.0 * nimplone
240  + 50000.0 * nclqzero + 5000.0 * nclqone;
241 #endif
242 
243  if( tmp > maxscore )
244  maxscore = tmp;
245  if( propdata->nprobed[SCIPvarGetIndex(var)] < minnprobings )
246  minnprobings = propdata->nprobed[SCIPvarGetIndex(var)];
247  }
248  }
249 
250  /* correct number of probings on each variable by minimal number of probings */
251  if( minnprobings > 0 )
252  {
253  for( i = 0; i < nvars; ++i )
254  {
255  SCIP_VAR* var;
256 
257  var = vars[i];
258 
259  if( SCIPvarIsActive(var) )
260  propdata->nprobed[SCIPvarGetIndex(var)] -= minnprobings;
261  }
262  }
263 
264  for( i = 0; i < nsortedvars; ++i )
265  {
266  SCIP_VAR* var;
267  var = sortedvars[i];
268 
269  assert(SCIPvarIsBinary(var));
270 
271  /* prefer variables that we did not already probe on */
272  if( SCIPvarIsActive(var) )
273  {
274  SCIP_Real randomoffset;
275  nlocksdown = SCIPvarGetNLocksDown(var);
276  nlocksup = SCIPvarGetNLocksUp(var);
277  nimplzero = SCIPvarGetNImpls(var, FALSE);
278  nimplone = SCIPvarGetNImpls(var, TRUE);
279  nclqzero = SCIPvarGetNCliques(var, FALSE);
280  nclqone = SCIPvarGetNCliques(var, TRUE);
281 
282  assert(propdata->noldtotalvars > SCIPvarGetIndex(var));
283  assert(propdata->nprobed[SCIPvarGetIndex(var)] >= 0);
284 
285  /* use a random offset to break possible ties arbitrarily */
286  randomoffset = SCIPrandomGetReal(propdata->randnumgen, 0.0, 0.5);
287 
288 #ifndef VARIANT_B
289  scores[i] = -maxscore * propdata->nprobed[SCIPvarGetIndex(var)]
290  - MAX(nlocksdown, nlocksup)
291  + 10.0 * MIN(nimplzero, nimplone)
292  + 100.0 * MIN(nclqzero, nclqone) /*lint !e790*/
293  - randomoffset; /* to break ties randomly */
294 #else
295  scores[i] = -maxscore * propdata->nprobed[SCIPvarGetIndex(var)]
296  - ABS(nlocksdown - nlocksup)
297  + MIN(nlocksdown, nlocksup)
298  + 500.0 * nimplzero + 50.0 * nimplone /*lint !e790*/
299  + 50000.0 * nclqzero + 5000.0 * nclqone /*lint !e790*/
300  - randomoffset; /* to break ties randomly */
301 #endif
302  }
303  else
304  scores[i] = -SCIPinfinity(scip);
305  }
306 
307  SCIPsortDownRealPtr(scores, (void**) sortedvars, nsortedvars);
308 
309  SCIPfreeBufferArray(scip, &scores);
310 
311  return SCIP_OKAY;
312 }
313 
314 /** the main probing loop */
315 static
317  SCIP* scip, /**< SCIP data structure */
318  SCIP_PROPDATA* propdata, /**< propagator data */
319  SCIP_VAR** vars, /**< problem variables */
320  int nvars, /**< number of problem variables */
321  int nbinvars, /**< number of binary variables */
322  int* startidx, /**< pointer to store starting variable index of next call */
323  int* nfixedvars, /**< pointer to store number of fixed variables */
324  int* naggrvars, /**< pointer to store number of aggregated variables */
325  int* nchgbds, /**< pointer to store number of changed bounds */
326  int oldnfixedvars, /**< number of previously fixed variables */
327  int oldnaggrvars, /**< number of previously aggregated variables */
328  SCIP_Bool* delay, /**< pointer to store whether propagator should be delayed */
329  SCIP_Bool* cutoff /**< pointer to store whether cutoff occured */
330  )
331 {
332  SCIP_Real* zeroimpllbs;
333  SCIP_Real* zeroimplubs;
334  SCIP_Real* zeroproplbs;
335  SCIP_Real* zeropropubs;
336  SCIP_Real* oneimpllbs;
337  SCIP_Real* oneimplubs;
338  SCIP_Real* oneproplbs;
339  SCIP_Real* onepropubs;
340  int localnfixedvars;
341  int localnaggrvars;
342  int localnchgbds;
343  int localnimplications;
344  int maxfixings;
345  int maxuseless;
346  int maxtotaluseless;
347  int maxsumuseless;
348  int i;
349  int oldstartidx;
350  SCIP_Bool aborted;
351  SCIP_Bool looped;
352 
353  assert(vars != NULL);
354  assert(nbinvars > 0);
355 
356  maxfixings = (propdata->maxfixings > 0 ? propdata->maxfixings : INT_MAX);
357  maxuseless = (propdata->maxuseless > 0 ? propdata->maxuseless : INT_MAX);
358  maxtotaluseless = (propdata->maxtotaluseless > 0 ? propdata->maxtotaluseless : INT_MAX);
359  maxsumuseless = (propdata->maxsumuseless > 0 ? propdata->maxsumuseless : INT_MAX);
360  aborted = FALSE;
361  looped = FALSE;
362  oldstartidx = *startidx;
363  i = *startidx;
364 
365  /* get temporary memory for storing probing results */
366  SCIP_CALL( SCIPallocBufferArray(scip, &zeroimpllbs, nvars) );
367  SCIP_CALL( SCIPallocBufferArray(scip, &zeroimplubs, nvars) );
368  SCIP_CALL( SCIPallocBufferArray(scip, &zeroproplbs, nvars) );
369  SCIP_CALL( SCIPallocBufferArray(scip, &zeropropubs, nvars) );
370  SCIP_CALL( SCIPallocBufferArray(scip, &oneimpllbs, nvars) );
371  SCIP_CALL( SCIPallocBufferArray(scip, &oneimplubs, nvars) );
372  SCIP_CALL( SCIPallocBufferArray(scip, &oneproplbs, nvars) );
373  SCIP_CALL( SCIPallocBufferArray(scip, &onepropubs, nvars) );
374 
375  /* for each binary variable, probe fixing the variable to zero and one */
376  *delay = FALSE;
377  *cutoff = FALSE;
378  do
379  {
380  for( ; i < nbinvars && !(*cutoff); ++i )
381  {
382  SCIP_Bool localcutoff;
383  SCIP_Bool probingzero;
384  SCIP_Bool probingone;
385 
386  /* check whether probing should be aborted */
387  if( propdata->nuseless >= maxuseless || propdata->ntotaluseless >= maxtotaluseless || propdata->nsumuseless >= maxsumuseless || SCIPisStopped(scip) )
388  {
390  " (%.1fs) probing: %d/%d (%.1f%%) - %d fixings, %d aggregations, %d implications, %d bound changes\n",
391  SCIPgetSolvingTime(scip), i+1, nbinvars, 100.0*(SCIP_Real)(i+1)/(SCIP_Real)nbinvars,
392  propdata->nfixings, propdata->naggregations, propdata->nimplications, propdata->nbdchgs);
393 
394  aborted = TRUE;
395 
396  if( propdata->nuseless >= maxuseless )
397  {
399  " (%.1fs) probing aborted: %d/%d successive useless probings\n", SCIPgetSolvingTime(scip),
400  propdata->nuseless, maxuseless);
401  }
402  else if( propdata->ntotaluseless >= maxtotaluseless )
403  {
405  " (%.1fs) probing aborted: %d/%d successive totally useless probings\n", SCIPgetSolvingTime(scip),
406  propdata->ntotaluseless, maxtotaluseless);
407  }
408  else if( propdata->nsumuseless >= maxsumuseless )
409  {
411  " (%.1fs) probing aborted: %d/%d useless probings in total\n", SCIPgetSolvingTime(scip),
412  propdata->nsumuseless, maxsumuseless);
413  }
414  else
415  {
416  assert(SCIPisStopped(scip));
418  " (%.1fs) probing aborted: solving stopped\n", SCIPgetSolvingTime(scip));
419  }
420  break;
421  }
422 
423  /* check if we already fixed enough variables for this round, or probed on all variables */
424  if( *nfixedvars - oldnfixedvars + *naggrvars - oldnaggrvars >= maxfixings || (looped && oldstartidx == i) )
425  {
426  if( *nfixedvars - oldnfixedvars + *naggrvars - oldnaggrvars > 0 )
427  *delay = TRUE;
428  else
429  aborted = TRUE;
430  break;
431  }
432 
433  /* display probing status */
434  if( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING && (i+1) % 100 == 0 )
435  {
436  SCIP_VERBLEVEL verblevel;
437 
438  verblevel = ((i+1) % 1000 == 0 ? SCIP_VERBLEVEL_HIGH : SCIP_VERBLEVEL_FULL);
439  SCIPverbMessage(scip, verblevel, NULL,
440  " (%.1fs) probing: %d/%d (%.1f%%) - %d fixings, %d aggregations, %d implications, %d bound changes\n",
441  SCIPgetSolvingTime(scip), i+1, nbinvars, 100.0*(SCIP_Real)(i+1)/(SCIP_Real)nbinvars,
442  propdata->nfixings, propdata->naggregations, propdata->nimplications, propdata->nbdchgs);
443  }
444 
445  /* ignore variables, that were fixed, aggregated, or deleted in prior probings */
446  if( !SCIPvarIsActive(vars[i]) || SCIPvarIsDeleted(vars[i])
447  || SCIPvarGetLbLocal(vars[i]) > 0.5 || SCIPvarGetUbLocal(vars[i]) < 0.5 )
448  continue;
449 
450  if( propdata->nuseless > 0 )
451  propdata->nsumuseless++;
452  else
453  propdata->nsumuseless = MAX(propdata->nsumuseless-1, 0);
454  propdata->nuseless++;
455  propdata->ntotaluseless++;
456 
457  /* determine whether one probing should happen */
458  probingone = TRUE;
459  if( SCIPvarGetNLocksUp(vars[i]) == 0 )
460  probingone = FALSE;
461 
462  if( probingone )
463  {
464  /* apply probing for fixing the variable to one */
465  SCIP_CALL( SCIPapplyProbingVar(scip, vars, nvars, i, SCIP_BOUNDTYPE_LOWER, 1.0, propdata->proprounds,
466  oneimpllbs, oneimplubs, oneproplbs, onepropubs, &localcutoff) );
467 
468  if( localcutoff )
469  {
470  SCIP_Bool fixed;
471 
473  {
474  /* the variable can be fixed to FALSE */
475  SCIP_CALL( SCIPfixVar(scip, vars[i], 0.0, cutoff, &fixed) );
476  assert(fixed);
477  }
478  else
479  {
480  SCIP_CALL( SCIPtightenVarUb(scip, vars[i], 0.0, TRUE, cutoff, &fixed) );
481  }
482 
483  if( fixed )
484  {
485  SCIPdebugMsg(scip, "fixed probing variable <%s> to 0.0, nlocks=(%d/%d)\n",
486  SCIPvarGetName(vars[i]), SCIPvarGetNLocksDown(vars[i]), SCIPvarGetNLocksUp(vars[i]));
487  (*nfixedvars)++;
488  propdata->nfixings++;
489  propdata->nuseless = 0;
490  propdata->ntotaluseless = 0;
491  }
492  else if( *cutoff )
493  {
494  SCIPdebugMsg(scip, "tightening upper bound of probing variable <%s> to 0.0 led to a cutoff\n",
495  SCIPvarGetName(vars[i]));
496  }
497  continue; /* don't try downwards direction, because the variable is already fixed */
498  }
499 
500  /* ignore variables, that were fixed, aggregated, or deleted in prior probings
501  * (propagators in one-probe might have found global fixings but did not trigger the localcutoff)
502  */
503  if( !SCIPvarIsActive(vars[i]) || SCIPvarIsDeleted(vars[i])
504  || SCIPvarGetLbLocal(vars[i]) > 0.5 || SCIPvarGetUbLocal(vars[i]) < 0.5 )
505  continue;
506  }
507 
508  /* determine whether zero probing should happen */
509  probingzero = TRUE;
510  if( SCIPvarGetNLocksDown(vars[i]) == 0 )
511  probingzero = FALSE;
512 
513  if( probingzero )
514  {
515  /* apply probing for fixing the variable to zero */
516  SCIP_CALL( SCIPapplyProbingVar(scip, vars, nvars, i, SCIP_BOUNDTYPE_UPPER, 0.0, propdata->proprounds,
517  zeroimpllbs, zeroimplubs, zeroproplbs, zeropropubs, &localcutoff) );
518 
519  if( localcutoff )
520  {
521  SCIP_Bool fixed;
522 
524  {
525  /* the variable can be fixed to TRUE */
526  SCIP_CALL( SCIPfixVar(scip, vars[i], 1.0, cutoff, &fixed) );
527  }
528  else
529  {
530  SCIP_CALL( SCIPtightenVarLb(scip, vars[i], 1.0, TRUE, cutoff, &fixed) );
531  }
532 
533  if( fixed )
534  {
535  SCIPdebugMsg(scip, "fixed probing variable <%s> to 1.0, nlocks=(%d/%d)\n",
536  SCIPvarGetName(vars[i]), SCIPvarGetNLocksDown(vars[i]), SCIPvarGetNLocksUp(vars[i]));
537  (*nfixedvars)++;
538  propdata->nfixings++;
539  propdata->nuseless = 0;
540  propdata->ntotaluseless = 0;
541  }
542  else if( *cutoff )
543  {
544  SCIPdebugMsg(scip, "tightening lower bound of probing variable <%s> to 1.0 led to a cutoff\n",
545  SCIPvarGetName(vars[i]));
546  }
547  continue; /* don't analyze probing deductions, because the variable is already fixed */
548  }
549  }
550 
551  /* not have to check deductions if only one probing direction has been checked */
552  if( !probingzero || !probingone )
553  continue;
554 
555  assert(propdata->noldtotalvars > SCIPvarGetIndex(vars[i]));
556 
557  /* count number of probings on each variable */
558  propdata->nprobed[SCIPvarGetIndex(vars[i])] += 1;
559 
560  /* analyze probing deductions */
561  localnfixedvars = 0;
562  localnaggrvars = 0;
563  localnimplications = 0;
564  localnchgbds = 0;
565  SCIP_CALL( SCIPanalyzeDeductionsProbing(scip, vars[i], 0.0, 1.0,
566  nvars, vars, zeroimpllbs, zeroimplubs, zeroproplbs, zeropropubs, oneimpllbs, oneimplubs, oneproplbs, onepropubs,
567  &localnfixedvars, &localnaggrvars, &localnimplications, &localnchgbds, cutoff) );
568 
569  *nfixedvars += localnfixedvars;
570  *naggrvars += localnaggrvars;
571  *nchgbds += localnchgbds;
572  propdata->nfixings += localnfixedvars;
573  propdata->naggregations += localnaggrvars;
574  propdata->nbdchgs += localnchgbds;
575  propdata->nimplications += localnimplications;
576 
577  if( localnfixedvars > 0 || localnaggrvars > 0 )
578  {
579  SCIPdebugMsg(scip, "probing on <%s> led to %d fixed and %d aggregated variables\n", SCIPvarGetName(vars[i]),
580  localnfixedvars, localnaggrvars);
581  propdata->nuseless = 0;
582  propdata->ntotaluseless = 0;
583  }
584  if( localnimplications > 0 || localnchgbds > 0 )
585  propdata->ntotaluseless = 0;
586  }
587 
588  looped = TRUE;
589 
590  /* check if we reached the end of all binary variables but did not stop, so we start from the beginning */
591  if( i == nbinvars && !(*cutoff) && !(*delay) && !aborted )
592  {
594  " (%.1fs) probing cycle finished: starting next cycle\n", SCIPgetSolvingTime(scip));
595  i = 0;
596 
597  if( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING )
598  {
599  SCIP_VAR** newvars;
600  int nnewvars;
601  int nnewbinvars;
602  int nnewintvars;
603  int nnewimplvars;
604  int lastidx;
605  int v;
606 
607  assert(vars == propdata->sortedvars);
608  assert(nbinvars == propdata->nsortedbinvars);
609 
610  /* release old variables and free memory */
611  for( v = propdata->nsortedvars - 1; v >= 0; --v )
612  {
613  SCIP_CALL( SCIPreleaseVar(scip, &propdata->sortedvars[v]) );
614  }
615  SCIPfreeMemoryArray(scip, &propdata->sortedvars);
616  propdata->nsortedvars = 0;
617  propdata->nsortedbinvars = 0;
618 
619  /* get new variables */
620  nnewvars = SCIPgetNVars(scip);
621  newvars = SCIPgetVars(scip);
622  SCIP_CALL( SCIPduplicateMemoryArray(scip, &(propdata->sortedvars), newvars, nnewvars) ); /*lint !e666*/
623  propdata->nsortedvars = nnewvars;
624 
625  nnewbinvars = SCIPgetNBinVars(scip);
626  nnewintvars = SCIPgetNIntVars(scip);
627  nnewimplvars = SCIPgetNImplVars(scip);
628 
629  /* determine implicit binary variables */
630  lastidx = nnewbinvars + nnewintvars + nnewimplvars;
631  for( v = nnewbinvars; v < lastidx; ++v )
632  {
633  if( SCIPvarIsBinary(propdata->sortedvars[v]) )
634  {
635  SCIPswapPointers((void**) &(propdata->sortedvars[nnewbinvars]), (void**) &(propdata->sortedvars[v]));
636  ++nnewbinvars;
637  }
638  }
639  propdata->nsortedbinvars = nnewbinvars;
640 
641  nbinvars = nnewbinvars;
642  vars = propdata->sortedvars;
643  nvars = propdata->nsortedvars;
644 
645  SCIP_CALL( SCIPreallocBufferArray(scip, &zeroimpllbs, nvars) );
646  SCIP_CALL( SCIPreallocBufferArray(scip, &zeroimplubs, nvars) );
647  SCIP_CALL( SCIPreallocBufferArray(scip, &zeroproplbs, nvars) );
648  SCIP_CALL( SCIPreallocBufferArray(scip, &zeropropubs, nvars) );
649  SCIP_CALL( SCIPreallocBufferArray(scip, &oneimpllbs, nvars) );
650  SCIP_CALL( SCIPreallocBufferArray(scip, &oneimplubs, nvars) );
651  SCIP_CALL( SCIPreallocBufferArray(scip, &oneproplbs, nvars) );
652  SCIP_CALL( SCIPreallocBufferArray(scip, &onepropubs, nvars) );
653 
654  /* correct oldstartidx which is used for early termination */
655  if( oldstartidx >= nbinvars )
656  oldstartidx = nbinvars - 1;
657 
658  /* capture variables to make sure, the variables are not deleted */
659  for( v = propdata->nsortedvars - 1; v >= 0; --v )
660  {
661  SCIP_CALL( SCIPcaptureVar(scip, propdata->sortedvars[v]) );
662  }
663 
664  if( nnewbinvars == 0 )
665  {
666  *startidx = 0;
667  propdata->lastsortstartidx = -1;
668  propdata->nuseless = 0;
669  propdata->ntotaluseless = 0;
670 
671  goto TERMINATE;
672  }
673 
674  /* resorting here might lead to probing a second time on the same variable */
675  SCIP_CALL( sortVariables(scip, propdata, propdata->sortedvars, propdata->nsortedbinvars, 0) );
676  propdata->lastsortstartidx = 0;
677  }
678  }
679 
680  }
681  while( i == 0 && !(*cutoff) && !(*delay) && !aborted );
682 
683  *startidx = i;
684 
685  TERMINATE:
686  /* free temporary memory */
687  SCIPfreeBufferArray(scip, &onepropubs);
688  SCIPfreeBufferArray(scip, &oneproplbs);
689  SCIPfreeBufferArray(scip, &oneimplubs);
690  SCIPfreeBufferArray(scip, &oneimpllbs);
691  SCIPfreeBufferArray(scip, &zeropropubs);
692  SCIPfreeBufferArray(scip, &zeroproplbs);
693  SCIPfreeBufferArray(scip, &zeroimplubs);
694  SCIPfreeBufferArray(scip, &zeroimpllbs);
695 
696  return SCIP_OKAY;
697 }
698 
699 
700 /*
701  * Callback methods of propagator
702  */
703 
704 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
705 static
706 SCIP_DECL_PROPCOPY(propCopyProbing)
707 { /*lint --e{715}*/
708  assert(scip != NULL);
709  assert(prop != NULL);
710  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
711 
712  /* call inclusion method for propagator */
714 
715  return SCIP_OKAY;
716 }
717 
718 
719 /** destructor of propagator to free user data (called when SCIP is exiting) */
720 static
721 SCIP_DECL_PROPFREE(propFreeProbing)
722 { /*lint --e{715}*/
723  SCIP_PROPDATA* propdata;
724 
725  /* free propagator data */
726  propdata = SCIPpropGetData(prop);
727  assert(propdata != NULL);
728  assert(propdata->sortedvars == NULL);
729  assert(propdata->nsortedvars == 0);
730  assert(propdata->nsortedbinvars == 0);
731 
732 
733  SCIPfreeBlockMemory(scip, &propdata);
734  SCIPpropSetData(prop, NULL);
735 
736  return SCIP_OKAY;
737 }
738 
739 
740 /** initialization method of propagator (called after problem was transformed) */
741 static
742 SCIP_DECL_PROPINIT(propInitProbing)
743 { /*lint --e{715}*/
744  SCIP_PROPDATA* propdata;
745 
746  propdata = SCIPpropGetData(prop);
747  assert(propdata != NULL);
749  SCIP_CALL( initPropdata(scip, propdata) );
750 
751  /* create random number generator */
752  SCIP_CALL( SCIPcreateRandom(scip, &propdata->randnumgen,
753  DEFAULT_RANDSEED) );
754 
755 
756  return SCIP_OKAY;
757 }
758 
759 
760 /** deinitialization method of propagator (called before transformed problem is freed) */
761 static
762 SCIP_DECL_PROPEXIT(propExitProbing)
763 { /*lint --e{715}*/
764  SCIP_PROPDATA* propdata;
765 
766  propdata = SCIPpropGetData(prop);
767  assert(propdata != NULL);
769  SCIP_CALL( freeSortedvars(scip, propdata) );
770  assert(propdata->sortedvars == NULL);
771  assert(propdata->nsortedvars == 0);
772  assert(propdata->nsortedbinvars == 0);
773 
774  /* free random number generator */
775  SCIPfreeRandom(scip, &propdata->randnumgen);
776 
777  return SCIP_OKAY;
778 }
779 
780 /** presolving initialization method of propagator (called when presolving is about to begin) */
781 static
782 SCIP_DECL_PROPINITPRE(propInitpreProbing)
783 { /*lint --e{715}*/
784  SCIP_PROPDATA* propdata;
785 
786  propdata = SCIPpropGetData(prop);
787  assert(propdata != NULL);
789  propdata->lastnode = -2;
790 
791  return SCIP_OKAY;
792 }
793 
794 
795 /** presolving deinitialization method of propagator (called after presolving has been finished) */
796 static
797 SCIP_DECL_PROPEXITPRE(propExitpreProbing)
798 { /*lint --e{715}*/
799  SCIP_PROPDATA* propdata;
800 
801  propdata = SCIPpropGetData(prop);
802  assert(propdata != NULL);
804  /* delete the vars array, if the maximal number of runs are exceeded */
805  if( propdata->maxruns >= 0 && SCIPgetNRuns(scip) >= propdata->maxruns )
806  {
807  SCIP_CALL( freeSortedvars(scip, propdata) );
808  assert(propdata->sortedvars == NULL);
809  assert(propdata->nsortedvars == 0);
810  assert(propdata->nsortedbinvars == 0);
811  }
812 
813  return SCIP_OKAY;
814 }
815 
816 
817 /** solving process initialization method of propagator (called when branch and bound process is about to begin) */
818 static
819 SCIP_DECL_PROPINITSOL(propInitsolProbing)
820 {
821  /*lint --e{715}*/
822  SCIP_PROPDATA* propdata;
823 
824  propdata = SCIPpropGetData(prop);
825  assert(propdata != NULL);
826 
827  /* reset all propdata elements for stopping propagation earlier */
828  propdata->nuseless = 0;
829  propdata->ntotaluseless = 0;
830  propdata->nsumuseless = 0;
831 
832  return SCIP_OKAY;
833 }
834 
835 
836 /** presolve method of propagator */
837 static
838 SCIP_DECL_PROPPRESOL(propPresolProbing)
839 { /*lint --e{715}*/
840  SCIP_PROPDATA* propdata;
841  int nvars;
842  int nbinvars;
843  int nintvars;
844  int nimplvars;
845  int oldnfixedvars;
846  int oldnaggrvars;
847  int oldnchgbds;
848  int oldnimplications;
849  int ntotalvars;
850  SCIP_Bool delay;
851  SCIP_Bool cutoff;
852 
853  assert(result != NULL);
854 
855  *result = SCIP_DIDNOTRUN;
856 
857  nbinvars = SCIPgetNBinVars(scip);
858  nintvars = SCIPgetNIntVars(scip);
859  nimplvars = SCIPgetNImplVars(scip);
860 
861  /* if we have no binary variable anymore, we stop probing */
862  if( nbinvars + nintvars + nimplvars == 0 )
863  return SCIP_OKAY;
864 
865  /* get propagator data */
866  propdata = SCIPpropGetData(prop);
867  assert(propdata != NULL);
868 
869  /* check, if probing should be applied in the current run */
870  if( propdata->maxruns >= 0 && SCIPgetNRuns(scip) > propdata->maxruns )
871  return SCIP_OKAY;
872 
873  /* if no domains changed since the last call, we don't need to probe */
874  if( propdata->lastnode == -1 && nnewfixedvars == 0 && nnewaggrvars == 0 && nnewchgbds == 0 && nnewholes == 0 )
875  return SCIP_OKAY;
876 
877  SCIPdebugMsg(scip, "executing probing (used %.1f sec)\n", SCIPpropGetTime(prop));
878 
879  *result = SCIP_DIDNOTFIND;
880 
881  /* allow some additional probings */
882  propdata->nuseless -= propdata->nuseless/10;
883  propdata->ntotaluseless -= propdata->ntotaluseless/10;
884 
885  /* get variable data */
886  if( propdata->sortedvars == NULL )
887  {
888  SCIP_VAR** vars = SCIPgetVars(scip);
889  int lastidx;
890  int v;
891 
892  assert(propdata->startidx == 0);
893 
894  nvars = SCIPgetNVars(scip);
895 
896  SCIP_CALL( SCIPduplicateMemoryArray(scip, &(propdata->sortedvars), vars, nvars) );
897  propdata->nsortedvars = nvars;
898 
899  /* determine implicit binary variables */
900  lastidx = nbinvars + nintvars + nimplvars;
901  for( v = nbinvars; v < lastidx; ++v )
902  {
903  if( SCIPvarIsBinary(propdata->sortedvars[v]) )
904  {
905  SCIPswapPointers((void**) &(propdata->sortedvars[nbinvars]), (void**) &(propdata->sortedvars[v]));
906  ++nbinvars;
907  }
908  }
909  propdata->nsortedbinvars = nbinvars;
910 
911  /* capture variables to make sure, the variables are not deleted */
912  for( v = propdata->nsortedvars - 1; v >= 0 ; --v )
913  {
914  SCIP_CALL( SCIPcaptureVar(scip, propdata->sortedvars[v]) );
915  }
916  }
917 
918  if( propdata->nsortedbinvars == 0 )
919  return SCIP_OKAY;
920 
921  /* number of total variables is not decreasing, and we can identify every variable by their index, so allocate
922  * enough space
923  */
924  ntotalvars = SCIPgetNTotalVars(scip);
925  if( propdata->noldtotalvars < ntotalvars )
926  {
927  SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->nprobed, ntotalvars) );
928  BMSclearMemoryArray(&(propdata->nprobed[propdata->noldtotalvars]), ntotalvars - propdata->noldtotalvars); /*lint !e866*/
929  propdata->noldtotalvars = ntotalvars;
930  }
931 
932  propdata->lastnode = -1;
933 
934  /* sort the binary variables by number of rounding locks, if at least 100 variables were probed since last sort */
935  if( propdata->lastsortstartidx < 0 || propdata->startidx - propdata->lastsortstartidx >= 100 )
936  {
937  SCIP_CALL( sortVariables(scip, propdata, propdata->sortedvars, propdata->nsortedbinvars, propdata->startidx) );
938  propdata->lastsortstartidx = propdata->startidx;
939  }
940 
941  oldnfixedvars = *nfixedvars;
942  oldnaggrvars = *naggrvars;
943  oldnchgbds = *nchgbds;
944  oldnimplications = propdata->nimplications;
945 
946  /* start probing on variables */
947  SCIP_CALL( applyProbing(scip, propdata, propdata->sortedvars, propdata->nsortedvars, propdata->nsortedbinvars,
948  &(propdata->startidx), nfixedvars, naggrvars, nchgbds, oldnfixedvars, oldnaggrvars, &delay, &cutoff) );
949 
950  /* adjust result code */
951  if( cutoff )
952  *result = SCIP_CUTOFF;
953  else
954  {
955  if( delay )
956  {
957  /* probing was interrupted because it reached the maximal fixings parameter, so we want to rerun it at the next call */
958  propdata->lastnode = -2;
959  }
960 
961  if( *nfixedvars > oldnfixedvars || *naggrvars > oldnaggrvars || *nchgbds > oldnchgbds
962  || propdata->nimplications > oldnimplications )
963  *result = SCIP_SUCCESS;
964  }
965 
966  return SCIP_OKAY;
967 }
968 
969 
970 /** execution method of propagator */
971 static
972 SCIP_DECL_PROPEXEC(propExecProbing)
973 { /*lint --e{715}*/
974  SCIP_PROPDATA* propdata;
975  SCIP_VAR** vars;
976  SCIP_VAR** binvars;
977  int nvars;
978  int nbinvars;
979  int i;
980  int nfixedvars;
981  int naggrvars;
982  int nchgbds;
983  int oldnfixedvars;
984  int oldnaggrvars;
985  int oldnchgbds;
986  int oldnimplications;
987  int startidx;
988  int ntotalvars;
989  SCIP_Bool delay;
990  SCIP_Bool cutoff;
991 
992  assert(result != NULL);
993 
994  *result = SCIP_DIDNOTRUN;
995 
996  /* avoid recursive infinity loop */
997  if( SCIPinProbing(scip) )
998  return SCIP_OKAY;
999 
1000  /* only call propagation on branching candidates, if an optimal LP solution is at hand */
1002  return SCIP_OKAY;
1003 
1004  /* get propagator data */
1005  propdata = SCIPpropGetData(prop);
1006  assert(propdata != NULL);
1007 
1008  /* if already called stop */
1009  if( propdata->lastnode == SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) )
1010  return SCIP_OKAY;
1011 
1012  /* if maximal depth for propagation is reached, stop */
1013  if( propdata->maxdepth >= 0 && propdata->maxdepth < SCIPgetDepth(scip) )
1014  return SCIP_OKAY;
1015 
1016  propdata->lastnode = SCIPnodeGetNumber(SCIPgetCurrentNode(scip));
1017 
1018  /* get (number of) fractional variables that should be integral */
1019  /* todo check if integrating fractional implicit integer variables is beneficial for probing */
1020  SCIP_CALL( SCIPgetLPBranchCands(scip, &vars, NULL, NULL, &nvars, NULL, NULL) );
1021  nbinvars = 0;
1022 
1023  /* alloc array for fractional binary variables */
1024  SCIP_CALL( SCIPallocBufferArray(scip, &binvars, nvars) );
1025 
1026  /* copy binary variables to array binvars */
1027  for( i = 0; i < nvars; ++i )
1028  {
1029  SCIP_VAR* var;
1030  var = vars[i];
1031 
1032  assert(var != NULL);
1033  if( SCIPvarIsBinary(var) )
1034  {
1035  assert(SCIPvarGetLbLocal(var) < 0.5);
1036  assert(SCIPvarGetUbLocal(var) > 0.5);
1037 
1038  binvars[nbinvars] = var;
1039  ++nbinvars;
1040  }
1041  }
1042  SCIPdebugMsg(scip, "problem <%s> node %" SCIP_LONGINT_FORMAT " probing propagation found %d of %d possible probing candidates\n", SCIPgetProbName(scip), SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), nbinvars, nvars);
1043 
1044  if( nbinvars == 0 )
1045  {
1046  *result = SCIP_DIDNOTFIND;
1047  goto TERMINATE;
1048  }
1049 
1050  /* number of total variables is not decreasing, and we can identify every variable by their index, so allocate
1051  * enough space
1052  */
1053  ntotalvars = SCIPgetNTotalVars(scip);
1054  if( propdata->noldtotalvars < ntotalvars )
1055  {
1056  SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->nprobed, ntotalvars) );
1057  BMSclearMemoryArray(&(propdata->nprobed[propdata->noldtotalvars]), ntotalvars - propdata->noldtotalvars); /*lint !e866*/
1058  propdata->noldtotalvars = ntotalvars;
1059  }
1060 
1061  /* sort binary variables */
1062  SCIP_CALL( sortVariables(scip, propdata, binvars, nbinvars, 0) );
1063 
1064  oldnfixedvars = 0;
1065  oldnaggrvars = 0;
1066  oldnchgbds = 0;
1067  nfixedvars = 0;
1068  naggrvars = 0;
1069  nchgbds = 0;
1070  startidx = 0;
1071  SCIPdebug( oldnimplications = propdata->nimplications; )
1072 
1073  /* start probing on found variables */
1074  SCIP_CALL( applyProbing(scip, propdata, binvars, nbinvars, nbinvars, &startidx, &nfixedvars, &naggrvars, &nchgbds, oldnfixedvars, oldnaggrvars, &delay, &cutoff) );
1075  SCIPdebugMsg(scip, "probing propagation found %d fixings, %d aggregation, %d nchgbds, and %d implications\n", nfixedvars, naggrvars, nchgbds, (propdata->nimplications) - oldnimplications);
1076 
1077  if( delay )
1078  {
1079  /* probing was interrupted because it reached the maximal fixings parameter, so we want to rerun it at the next call */
1080  propdata->lastnode = -2;
1081  }
1082 
1083  /* adjust result code */
1084  if( cutoff )
1085  *result = SCIP_CUTOFF;
1086  else if( nfixedvars > oldnfixedvars || naggrvars > oldnaggrvars || nchgbds > oldnchgbds )
1087  *result = SCIP_REDUCEDDOM;
1088 
1089  TERMINATE:
1090  SCIPfreeBufferArray(scip, &binvars);
1091 
1092  return SCIP_OKAY;
1093 }
1094 
1095 
1096 /** propagation conflict resolving method of propagator */
1097 static
1098 SCIP_DECL_PROPRESPROP(propRespropProbing)
1099 { /*lint --e{715}*/
1100  *result = SCIP_DIDNOTRUN;
1101 
1102  return SCIP_OKAY;
1103 }
1105 
1106 /*
1107  * propagator specific interface methods
1108  */
1109 
1110 /** creates the probing propagator and includes it in SCIP */
1112  SCIP* scip /**< SCIP data structure */
1113  )
1114 {
1115  SCIP_PROPDATA* propdata;
1116  SCIP_PROP* prop;
1118  /* create probing propagator data */
1119  SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) );
1120  SCIP_CALL( initPropdata(scip, propdata) );
1121 
1122  /* include propagator */
1124  propExecProbing, propdata) );
1125 
1126  assert(prop != NULL);
1127 
1128  /* set optional callbacks via setter functions */
1129  SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyProbing) );
1130  SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeProbing) );
1131  SCIP_CALL( SCIPsetPropInit(scip, prop, propInitProbing) );
1132  SCIP_CALL( SCIPsetPropExit(scip, prop, propExitProbing) );
1133  SCIP_CALL( SCIPsetPropInitsol(scip, prop, propInitsolProbing) );
1134  SCIP_CALL( SCIPsetPropInitpre(scip, prop, propInitpreProbing) );
1135  SCIP_CALL( SCIPsetPropExitpre(scip, prop, propExitpreProbing) );
1136  SCIP_CALL( SCIPsetPropPresol(scip, prop, propPresolProbing, PROP_PRESOL_PRIORITY, PROP_PRESOL_MAXROUNDS,
1137  PROP_PRESOLTIMING) );
1138  SCIP_CALL( SCIPsetPropResprop(scip, prop, propRespropProbing) );
1139 
1140  /* add probing propagator parameters */
1141  SCIP_CALL( SCIPaddIntParam(scip,
1142  "propagating/" PROP_NAME "/maxruns",
1143  "maximal number of runs, probing participates in (-1: no limit)",
1144  &propdata->maxruns, FALSE, DEFAULT_MAXRUNS, -1, INT_MAX, NULL, NULL) );
1145  SCIP_CALL( SCIPaddIntParam(scip,
1146  "propagating/" PROP_NAME "/proprounds",
1147  "maximal number of propagation rounds in probing subproblems (-1: no limit, 0: auto)",
1148  &propdata->proprounds, TRUE, DEFAULT_PROPROUNDS, -1, INT_MAX, NULL, NULL) );
1149  SCIP_CALL( SCIPaddIntParam(scip,
1150  "propagating/" PROP_NAME "/maxfixings",
1151  "maximal number of fixings found, until probing is interrupted (0: don't iterrupt)",
1152  &propdata->maxfixings, TRUE, DEFAULT_MAXFIXINGS, 0, INT_MAX, NULL, NULL) );
1153  SCIP_CALL( SCIPaddIntParam(scip,
1154  "propagating/" PROP_NAME "/maxuseless",
1155  "maximal number of successive probings without fixings, until probing is aborted (0: don't abort)",
1156  &propdata->maxuseless, TRUE, DEFAULT_MAXUSELESS, 0, INT_MAX, NULL, NULL) );
1157  SCIP_CALL( SCIPaddIntParam(scip,
1158  "propagating/" PROP_NAME "/maxtotaluseless",
1159  "maximal number of successive probings without fixings, bound changes, and implications, until probing is aborted (0: don't abort)",
1160  &propdata->maxtotaluseless, TRUE, DEFAULT_MAXTOTALUSELESS, 0, INT_MAX, NULL, NULL) );
1161  SCIP_CALL( SCIPaddIntParam(scip,
1162  "propagating/" PROP_NAME "/maxsumuseless",
1163  "maximal number of probings without fixings, until probing is aborted (0: don't abort)",
1164  &propdata->maxsumuseless, TRUE, DEFAULT_MAXSUMUSELESS, 0, INT_MAX, NULL, NULL) );
1165  SCIP_CALL( SCIPaddIntParam(scip,
1166  "propagating/" PROP_NAME "/maxdepth",
1167  "maximal depth until propagation is executed(-1: no limit)",
1168  &propdata->maxdepth, TRUE, DEFAULT_MAXDEPTH, -1, INT_MAX, NULL, NULL) );
1169 
1170  return SCIP_OKAY;
1171 }
1172 
1173 
1174 /** applies and evaluates probing of a single variable in the given direction and bound */
1176  SCIP* scip, /**< SCIP data structure */
1177  SCIP_VAR** vars, /**< problem variables */
1178  int nvars, /**< number of problem variables */
1179  int probingpos, /**< variable number to apply probing on */
1180  SCIP_BOUNDTYPE boundtype, /**< which bound should be changed */
1181  SCIP_Real bound, /**< which bound should be set */
1182  int maxproprounds, /**< maximal number of propagation rounds (-1: no limit, 0: parameter settings) */
1183  SCIP_Real* impllbs, /**< array to store lower bounds after applying implications and cliques */
1184  SCIP_Real* implubs, /**< array to store upper bounds after applying implications and cliques */
1185  SCIP_Real* proplbs, /**< array to store lower bounds after full propagation */
1186  SCIP_Real* propubs, /**< array to store upper bounds after full propagation */
1187  SCIP_Bool* cutoff /**< pointer to store whether the probing direction is infeasible */
1188  )
1189 {
1190  assert(impllbs != NULL);
1191  assert(implubs != NULL);
1192  assert(proplbs != NULL);
1193  assert(propubs != NULL);
1194  assert(cutoff != NULL);
1195  assert(0 <= probingpos && probingpos < nvars);
1196  assert(SCIPisGE(scip, bound, SCIPvarGetLbLocal(vars[probingpos])));
1197  assert(SCIPisLE(scip, bound, SCIPvarGetUbLocal(vars[probingpos])));
1198 
1199  SCIPdebugMsg(scip, "applying probing on variable <%s> %s %g (nlocks=%d/%d, impls=%d/%d, clqs=%d/%d)\n",
1200  SCIPvarGetName(vars[probingpos]), boundtype == SCIP_BOUNDTYPE_UPPER ? "<=" : ">=", bound,
1201  SCIPvarGetNLocksDown(vars[probingpos]), SCIPvarGetNLocksUp(vars[probingpos]),
1202  SCIPvarGetNImpls(vars[probingpos], FALSE), SCIPvarGetNImpls(vars[probingpos], TRUE),
1203  SCIPvarGetNCliques(vars[probingpos], FALSE), SCIPvarGetNCliques(vars[probingpos], TRUE));
1204 
1205  /* in debug mode we assert above that this trivial infeasibility does not occur (for performance reasons), but in
1206  * optimized mode we return safely
1207  */
1208  if( SCIPisLT(scip, bound, SCIPvarGetLbLocal(vars[probingpos]))
1209  || SCIPisGT(scip, bound, SCIPvarGetUbLocal(vars[probingpos])) )
1210  {
1211  SCIPdebugMsg(scip, " -> trivial infeasibility detected\n");
1212  *cutoff = TRUE;
1213  return SCIP_OKAY;
1214  }
1215 
1216  /* start probing mode */
1217  SCIP_CALL( SCIPstartProbing(scip) );
1218 
1219  /* enables collection of variable statistics during probing */
1220  SCIPenableVarHistory(scip);
1221 
1222  /* fix variable */
1223  if( boundtype == SCIP_BOUNDTYPE_UPPER )
1224  {
1225  SCIP_CALL( SCIPchgVarUbProbing(scip, vars[probingpos], bound) );
1226  }
1227  else
1228  {
1229  assert(boundtype == SCIP_BOUNDTYPE_LOWER);
1230  SCIP_CALL( SCIPchgVarLbProbing(scip, vars[probingpos], bound) );
1231  }
1232 
1233  /* @todo it might pay off to catch the bounds-tightened event on all variables and then only get the implied and
1234  * propagated bounds on those variables which where really changed on propagation
1235  */
1236 
1237  /* apply propagation of implication graph and clique table */
1239  if( !(*cutoff) )
1240  {
1241  int i;
1242 
1243  for( i = 0; i < nvars; ++i )
1244  {
1245  impllbs[i] = SCIPvarGetLbLocal(vars[i]);
1246  implubs[i] = SCIPvarGetUbLocal(vars[i]);
1247  }
1248 
1249  /* apply propagation */
1250  SCIP_CALL( SCIPpropagateProbing(scip, maxproprounds, cutoff, NULL) );
1251  }
1252  else
1253  {
1254  SCIPdebugMsg(scip, "propagating probing implications after <%s> to %g led to a cutoff\n",
1255  SCIPvarGetName(vars[probingpos]), bound);
1256  }
1257 
1258  /* evaluate propagation */
1259  if( !(*cutoff) )
1260  {
1261  int i;
1262 
1263  for( i = 0; i < nvars; ++i )
1264  {
1265  proplbs[i] = SCIPvarGetLbLocal(vars[i]);
1266  propubs[i] = SCIPvarGetUbLocal(vars[i]);
1267 #if 0
1268 #ifdef SCIP_DEBUG
1269  if( SCIPisGT(scip, proplbs[i], SCIPvarGetLbGlobal(vars[i])) )
1270  {
1271  SCIPdebugMsg(scip, " -> <%s>[%g,%g] >= %g\n", SCIPvarGetName(vars[i]),
1272  SCIPvarGetLbGlobal(vars[i]), SCIPvarGetUbGlobal(vars[i]), proplbs[i]);
1273  }
1274  if( SCIPisLT(scip, propubs[i], SCIPvarGetUbGlobal(vars[i])) )
1275  {
1276  SCIPdebugMsg(scip, " -> <%s>[%g,%g] <= %g\n", SCIPvarGetName(vars[i]),
1277  SCIPvarGetLbGlobal(vars[i]), SCIPvarGetUbGlobal(vars[i]), propubs[i]);
1278  }
1279 #endif
1280 #endif
1281  }
1282  }
1283 
1284  /* exit probing mode */
1285  SCIP_CALL( SCIPendProbing(scip) );
1286 
1287  return SCIP_OKAY;
1288 }
1289 
1290 /** analyses boundchanges resulting from probing on a variable and performs deduced fixations, aggregations, and domain tightenings
1291  * Given a variable probingvar with domain [l,u] and bound tightening results from reducing the domain
1292  * once to [l,leftub] and once to [rightlb,u], the method computes and applies resulting variable fixations, aggregations,
1293  * implications, and bound changes. Variable probingvar does not need to be binary.
1294  * The whole domain of probingvar need to be covered by the left and right branches, i.e.,
1295  * we assume leftub >= rightlb for continuous variables or floor(leftub) >= ceil(rightlb)-1 for discrete variables.
1296  * Bounds after applying implications and cliques do not need to be provided, but if they are omitted and probingvar is a binary variable,
1297  * then already existing implications may be added.
1298  */
1300  SCIP* scip, /**< SCIP data structure */
1301  SCIP_VAR* probingvar, /**< the probing variable */
1302  SCIP_Real leftub, /**< upper bound of probing variable in left branch */
1303  SCIP_Real rightlb, /**< lower bound of probing variable in right branch */
1304  int nvars, /**< number of variables which bound changes should be analyzed */
1305  SCIP_VAR** vars, /**< variables which bound changes should be analyzed */
1306  SCIP_Real* leftimpllbs, /**< lower bounds after applying implications and cliques in left branch, or NULL */
1307  SCIP_Real* leftimplubs, /**< upper bounds after applying implications and cliques in left branch, or NULL */
1308  SCIP_Real* leftproplbs, /**< lower bounds after applying domain propagation in left branch */
1309  SCIP_Real* leftpropubs, /**< upper bounds after applying domain propagation in left branch */
1310  SCIP_Real* rightimpllbs, /**< lower bounds after applying implications and cliques in right branch, or NULL */
1311  SCIP_Real* rightimplubs, /**< upper bounds after applying implications and cliques in right branch, or NULL */
1312  SCIP_Real* rightproplbs, /**< lower bounds after applying domain propagation in right branch */
1313  SCIP_Real* rightpropubs, /**< upper bounds after applying domain propagation in right branch */
1314  int* nfixedvars, /**< pointer to counter which is increased by the number of deduced variable fixations */
1315  int* naggrvars, /**< pointer to counter which is increased by the number of deduced variable aggregations */
1316  int* nimplications, /**< pointer to counter which is increased by the number of deduced implications */
1317  int* nchgbds, /**< pointer to counter which is increased by the number of deduced bound tightenings */
1318  SCIP_Bool* cutoff /**< buffer to store whether a cutoff is detected */
1319  )
1320 {
1321  SCIP_Bool fixedleft;
1322  SCIP_Bool fixedright;
1323  SCIP_Bool probingvarisbinary;
1324  SCIP_Bool probingvarisinteger;
1325  int j;
1326 
1327  assert(scip != NULL);
1328  assert(probingvar != NULL);
1329  assert(SCIPisGE(scip, leftub, SCIPvarGetLbLocal(probingvar))); /* left branch should not be empty by default */
1330  assert(SCIPisLE(scip, rightlb, SCIPvarGetUbLocal(probingvar))); /* right branch should not be empty by default */
1331  assert(vars != NULL || nvars == 0);
1332  assert(leftproplbs != NULL);
1333  assert(leftpropubs != NULL);
1334  assert(rightproplbs != NULL);
1335  assert(rightpropubs != NULL);
1336  assert(nfixedvars != NULL);
1337  assert(naggrvars != NULL);
1338  assert(nimplications != NULL);
1339  assert(nchgbds != NULL);
1340  assert(cutoff != NULL);
1341 
1342  /* @todo the asserts below could be relaxed by taking domain holes into account */
1343  if( SCIPvarGetType(probingvar) != SCIP_VARTYPE_CONTINUOUS )
1344  {
1345  /* adjust bounds to actually used ones */
1346  leftub = SCIPfloor(scip, leftub);
1347  rightlb = SCIPceil(scip, rightlb);
1348 
1349  probingvarisinteger = TRUE;
1350  probingvarisbinary = SCIPvarIsBinary(probingvar);
1351  }
1352  else
1353  {
1354  /* assert dichotomy in case of continuous var: leftub >= rightlb */
1355  assert(SCIPisGE(scip, leftub, rightlb));
1356  probingvarisbinary = FALSE;
1357  probingvarisinteger = FALSE;
1358  }
1359 
1360  /* check if probing variable was fixed in the branches */
1361  fixedleft = SCIPisEQ(scip, SCIPvarGetLbLocal(probingvar), leftub);
1362  fixedright = SCIPisEQ(scip, SCIPvarGetUbLocal(probingvar), rightlb);
1363 
1364  *cutoff = FALSE;
1365 
1366  for( j = 0; j < nvars && !*cutoff; ++j )
1367  {
1368  SCIP_VAR* var;
1369  SCIP_Bool varisinteger;
1370  SCIP_Real newlb;
1371  SCIP_Real newub;
1372 
1373  assert(vars != NULL); /* for flexelint */
1374 
1375  var = vars[j];
1376  assert(var != NULL);
1377 
1378  /* @todo: add holes, and even add holes if x was the probing variable and it followed a better bound on x itself */
1379  /* @todo: check if we probed on an integer variable, that this maybe led to aggregation on two other variables, i.e
1380  * probing on x <= 1 and x >= 2 led to y = 1, z = 1 and y = 0, z = 0 resp., which means y = Z
1381  */
1382 
1383  /* if probing variable is binary, then there is nothing we could deduce here (variable should be fixed in both branches)
1384  * if it is not binary, we want to see if we found bound tightenings, even though it seems quite unlikely */
1385  if( var == probingvar && probingvarisbinary )
1386  continue;
1387 
1388  /* new bounds of the variable is the union of the propagated bounds of the left and right case */
1389  newlb = MIN(leftproplbs[j], rightproplbs[j]);
1390  newub = MAX(leftpropubs[j], rightpropubs[j]);
1391  varisinteger = (SCIPvarGetType(var) < SCIP_VARTYPE_CONTINUOUS);
1392 
1393  /* check for fixed variables */
1394  if( SCIPisEQ(scip, newlb, newub) )
1395  {
1396  SCIP_Real fixval;
1397  SCIP_Bool fixed;
1398 
1399  if( !varisinteger )
1400  {
1401  /* in both probings, variable j is deduced to the same value: fix variable to this value */
1402  fixval = SCIPselectSimpleValue(newlb - 0.9 * SCIPepsilon(scip), newub + 0.9 * SCIPepsilon(scip), MAXDNOM);
1403  }
1404  else
1405  {
1406  fixval = newlb;
1407  }
1408 
1410  {
1411  SCIP_CALL( SCIPfixVar(scip, var, fixval, cutoff, &fixed) );
1412  }
1413  else
1414  {
1415  SCIP_CALL( SCIPtightenVarLb(scip, var, fixval, TRUE, cutoff, &fixed) );
1416  if( !*cutoff )
1417  {
1418  SCIP_Bool tightened;
1419 
1420  SCIP_CALL( SCIPtightenVarUb(scip, var, fixval, TRUE, cutoff, &tightened) );
1421  fixed &= tightened;
1422  }
1423  }
1424 
1425  if( fixed )
1426  {
1427  SCIPdebugMsg(scip, "fixed variable <%s> to %g due to probing on <%s> with nlocks=(%d/%d)\n",
1428  SCIPvarGetName(var), fixval,
1429  SCIPvarGetName(probingvar), SCIPvarGetNLocksDown(probingvar), SCIPvarGetNLocksUp(probingvar));
1430  (*nfixedvars)++;
1431  }
1432  else if( *cutoff )
1433  {
1434  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible fixing of variable <%s> to %g\n",
1435  SCIPvarGetName(probingvar), SCIPvarGetName(var), fixval);
1436  }
1437 
1438  continue;
1439  }
1440  else
1441  {
1442  /* check for bound tightenings */
1443  SCIP_Real oldlb;
1444  SCIP_Real oldub;
1445  SCIP_Bool tightened;
1446  SCIP_Bool tightenlb;
1447  SCIP_Bool tightenub;
1448  SCIP_Bool force;
1449 
1450  oldlb = SCIPvarGetLbLocal(var);
1451  oldub = SCIPvarGetUbLocal(var);
1452 
1453  if( varisinteger )
1454  {
1455  force = TRUE;
1456  tightenlb = (newlb > oldlb + 0.5);
1457  tightenub = (newub < oldub - 0.5);
1458  }
1459  else
1460  {
1461  force = TRUE;
1462  tightenlb = SCIPisLbBetter(scip, newlb, oldlb, oldub);
1463  tightenub = SCIPisUbBetter(scip, newub, oldlb, oldub);
1464  }
1465 
1466  if( tightenlb )
1467  {
1468  /* in both probings, variable j is deduced to be at least newlb: tighten lower bound */
1469  SCIP_CALL( SCIPtightenVarLb(scip, var, newlb, force, cutoff, &tightened) );
1470  if( tightened )
1471  {
1472  SCIPdebugMsg(scip, "tightened lower bound of variable <%s>[%g,%g] to %g due to probing on <%s> with nlocks=(%d/%d)\n",
1473  SCIPvarGetName(var), oldlb, oldub, newlb,
1474  SCIPvarGetName(probingvar), SCIPvarGetNLocksDown(probingvar), SCIPvarGetNLocksUp(probingvar));
1475  (*nchgbds)++;
1476  }
1477  else if( *cutoff )
1478  {
1479  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible new lower bound of variable <%s> to %g\n",
1480  SCIPvarGetName(probingvar), SCIPvarGetName(var), newlb);
1481  }
1482  }
1483 
1484  if( tightenub && !*cutoff )
1485  {
1486  /* in both probings, variable j is deduced to be at most newub: tighten upper bound */
1487  SCIP_CALL( SCIPtightenVarUb(scip, var, newub, force, cutoff, &tightened) );
1488  if( tightened )
1489  {
1490  SCIPdebugMsg(scip, "tightened upper bound of variable <%s>[%g,%g] to %g due to probing on <%s> with nlocks=(%d/%d)\n",
1491  SCIPvarGetName(var), oldlb, oldub, newub,
1492  SCIPvarGetName(probingvar), SCIPvarGetNLocksDown(probingvar), SCIPvarGetNLocksUp(probingvar));
1493  (*nchgbds)++;
1494  }
1495  else if( *cutoff )
1496  {
1497  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible new lower bound of variable <%s> to %g\n",
1498  SCIPvarGetName(probingvar), SCIPvarGetName(var), newub);
1499  }
1500  }
1501  if( *cutoff )
1502  break;
1503  }
1504 
1505  /* below we add aggregations and implications between probingvar and var,
1506  * we don't want this if both variables are the same
1507  */
1508  if( var == probingvar )
1509  continue;
1510 
1511  /* check for aggregations and implications */
1512  if( fixedleft && fixedright &&
1513  SCIPisEQ(scip, leftproplbs[j], leftpropubs[j]) && SCIPisEQ(scip, rightproplbs[j], rightpropubs[j]) )
1514  {
1515  /* var is fixed whenever probingvar is fixed, i.e.,
1516  * var = leftproplbs[j] + (rightproplbs[j] - leftproplbs[j]) / (rightlb - leftub) * (probingvar - leftub)
1517  * -> both variables can be aggregated:
1518  * (rightlb - leftub) * (var - leftproplbs[j]) = (rightproplbs[j] - leftproplbs[j]) * (probingvar - leftub)
1519  * -> (rightlb - leftub) * var - (rightproplbs[j] - leftproplbs[j]) * probingvar = leftproplbs[j] * rightlb - rightproplbs[j] * leftub
1520  *
1521  * check for case where both variables are binary: leftub = 1, rightlb = 0
1522  * case leftproplbs[j] = 0, rightproplbs[j] = 1, i.e., var and probingvar are fixed to same value
1523  * -> aggregation is 1 * var - 1 * probingvar = 0 * 1 - 1 * 0 = 0 -> correct
1524  * case leftproplbs[j] = 1, rightproblbs[j] = 0, i.e., var and probingvar are fixed to opposite values
1525  * -> aggregation is 1 * var + 1 * probingvar = 1 * 1 - 0 * 0 = 0 -> correct
1526  */
1527  if( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING )
1528  {
1529  SCIP_Bool aggregated;
1530  SCIP_Bool redundant;
1531 
1532  SCIP_CALL( SCIPaggregateVars(scip, var, probingvar,
1533  rightlb - leftub, -(rightproplbs[j] - leftproplbs[j]), leftproplbs[j] * rightlb - rightproplbs[j] * leftub,
1534  cutoff, &redundant, &aggregated) );
1535 
1536  if( aggregated )
1537  {
1538  SCIPdebugMsg(scip, "aggregated variables %g<%s> - %g<%s> == %g, nlocks=(%d/%d)\n",
1539  rightlb - leftub, SCIPvarGetName(var),
1540  rightproplbs[j] - leftproplbs[j], SCIPvarGetName(probingvar),
1541  leftproplbs[j] * rightlb - rightproplbs[j] * leftub,
1542  SCIPvarGetNLocksDown(var), SCIPvarGetNLocksUp(probingvar));
1543  (*naggrvars)++;
1544  }
1545  if( *cutoff )
1546  {
1547  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible aggregation: %g<%s> - %g<%s> == %g\n",
1548  SCIPvarGetName(probingvar), rightlb - leftub, SCIPvarGetName(var),
1549  rightproplbs[j] - leftproplbs[j], SCIPvarGetName(probingvar),
1550  leftproplbs[j] * rightlb - rightproplbs[j] * leftub);
1551  }
1552  }
1553  else if( probingvarisinteger && SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) == 0 )
1554  {
1555  /* if we are not in presolving, then we cannot do aggregations
1556  * but we can use variable bounds to code the same equality
1557  * var == ((leftproplbs[j] * rightlb - rightproplbs[j] * leftub) + (rightproplbs[j] - leftproplbs[j]) * probingvar) / (rightlb - leftub)
1558  */
1559  int nboundchanges;
1560 
1561  assert(!SCIPisEQ(scip, leftub, rightlb));
1562 
1563  SCIP_CALL( SCIPaddVarVlb(scip, var, probingvar, (rightproplbs[j] - leftproplbs[j]) / (rightlb - leftub), (leftproplbs[j] * rightlb - rightproplbs[j] * leftub) / (rightlb - leftub), cutoff, &nboundchanges) );
1564  (*nchgbds) += nboundchanges;
1565 
1566  if( *cutoff )
1567  {
1568  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible vlb: %g<%s> - %g<%s> == %g\n",
1569  SCIPvarGetName(probingvar), rightlb - leftub, SCIPvarGetName(var),
1570  rightproplbs[j] - leftproplbs[j], SCIPvarGetName(probingvar),
1571  leftproplbs[j] * rightlb - rightproplbs[j] * leftub);
1572  }
1573  else
1574  {
1575  SCIP_CALL( SCIPaddVarVub(scip, var, probingvar, (rightproplbs[j] - leftproplbs[j]) / (rightlb - leftub), (leftproplbs[j] * rightlb - rightproplbs[j] * leftub) / (rightlb - leftub), cutoff, &nboundchanges) );
1576  (*nchgbds) += nboundchanges;
1577 
1578  if( *cutoff )
1579  {
1580  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible vub: %g<%s> - %g<%s> == %g\n",
1581  SCIPvarGetName(probingvar), rightlb - leftub, SCIPvarGetName(var),
1582  rightproplbs[j] - leftproplbs[j], SCIPvarGetName(probingvar),
1583  leftproplbs[j] * rightlb - rightproplbs[j] * leftub);
1584  }
1585  }
1586  (*nimplications)++;
1587  }
1588  /* if probingvar is continuous and we are in solving stage, then we do nothing, but it's unlikely that we get
1589  * here (fixedleft && fixedright) with a continuous variable
1590  */
1591  }
1592  /* @todo: check if we can add variable lowerbounds/upperbounds on integer variables */
1593  /* can only add implications on binary variables which are globally valid */
1594  else if( probingvarisbinary && (SCIPgetStage(scip) != SCIP_STAGE_SOLVING || SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) == 0) )
1595  {
1596  /* implications can be added only for binary variables */
1597  int nboundchanges;
1598 
1599  /* since probing var is binary variable, probing should have fixed variable in both branches,
1600  * which is to 0.0 in the left branch and to 1.0 in the right branch */
1601  assert(fixedleft);
1602  assert(fixedright);
1603  assert(SCIPisZero(scip, leftub));
1604  assert(SCIPisEQ(scip, rightlb, 1.0));
1605 
1606  if( SCIPisEQ(scip, newlb, leftpropubs[j]) && (leftimplubs == NULL || leftimplubs[j] > leftpropubs[j]) )
1607  {
1608  /* var is fixed to lower bound whenever probingvar is fixed to 0.0
1609  * and implication is not already known
1610  * -> insert implication: probingvar == 0 => var <= leftpropubs[j]
1611  */
1612  /*SCIPdebugMsg(scip, "found implication <%s> == 0 => <%s> == %g\n",
1613  SCIPvarGetName(probingvar), SCIPvarGetName(var), leftpropubs[j]);*/
1614  SCIP_CALL( SCIPaddVarImplication(scip, probingvar, FALSE, var, SCIP_BOUNDTYPE_UPPER, leftpropubs[j],
1615  cutoff, &nboundchanges) );
1616  (*nimplications)++;
1617  (*nchgbds) += nboundchanges;
1618 
1619  if( *cutoff )
1620  {
1621  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 0 => <%s> == %g\n",
1622  SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), leftpropubs[j]);
1623  }
1624  }
1625  else if( SCIPisEQ(scip, newub, leftproplbs[j]) && (leftimpllbs == NULL || leftimpllbs[j] < leftproplbs[j]) )
1626  {
1627  /* var is fixed to upper bound whenever probingvar is fixed to 0.0
1628  * and implication is not already known
1629  * -> insert implication: probingvar == 0 => var >= leftproplbs[j]
1630  */
1631  /*SCIPdebugMsg(scip, "found implication <%s> == 0 => <%s> == %g\n",
1632  SCIPvarGetName(probingvar), SCIPvarGetName(var), leftproplbs[j]);*/
1633  SCIP_CALL( SCIPaddVarImplication(scip, probingvar, FALSE, var, SCIP_BOUNDTYPE_LOWER, leftproplbs[j],
1634  cutoff, &nboundchanges) );
1635  (*nimplications)++;
1636  (*nchgbds) += nboundchanges;
1637 
1638  if( *cutoff )
1639  {
1640  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 0 => <%s> == %g\n",
1641  SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), leftproplbs[j]);
1642  }
1643  }
1644  /* we can do an else here, since the case where var is fixed for both fixings of probingvar had been handled as aggregation */
1645  else if( SCIPisEQ(scip, newlb, rightpropubs[j]) && (rightimplubs == NULL || rightimplubs[j] > rightpropubs[j]) )
1646  {
1647  /* var is fixed to lower bound whenever probingvar is fixed to 1.0
1648  * and implication is not already known
1649  * -> insert implication: probingvar == 1 => var <= rightpropubs[j]
1650  */
1651  /*SCIPdebugMsg(scip, "found implication <%s> == 1 => <%s> == %g\n",
1652  SCIPvarGetName(probingvar), SCIPvarGetName(var), rightpropubs[j]);*/
1653  SCIP_CALL( SCIPaddVarImplication(scip, probingvar, TRUE, var, SCIP_BOUNDTYPE_UPPER, rightpropubs[j],
1654  cutoff, &nboundchanges) );
1655  (*nimplications)++;
1656  (*nchgbds) += nboundchanges;
1657 
1658  if( *cutoff )
1659  {
1660  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 1 => <%s> == %g\n",
1661  SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), rightpropubs[j]);
1662  }
1663  }
1664  else if( SCIPisEQ(scip, newub, rightproplbs[j]) && (rightimpllbs == NULL || rightimpllbs[j] < rightproplbs[j]) )
1665  {
1666  /* var is fixed to upper bound whenever probingvar is fixed to 1.0
1667  * and implication is not already known
1668  * -> insert implication: probingvar == 1 => var >= leftproplbs[j]
1669  */
1670  /*SCIPdebugMsg(scip, "found implication <%s> == 1 => <%s> == %g\n",
1671  SCIPvarGetName(probingvar), SCIPvarGetName(var), rightproplbs[j]);*/
1672  SCIP_CALL( SCIPaddVarImplication(scip, probingvar, TRUE, var, SCIP_BOUNDTYPE_LOWER, rightproplbs[j],
1673  cutoff, &nboundchanges) );
1674  (*nimplications)++;
1675  (*nchgbds) += nboundchanges;
1676 
1677  if( *cutoff )
1678  {
1679  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 1 => <%s> == %g\n",
1680  SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), rightproplbs[j]);
1681  }
1682  }
1683  else if( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY )
1684  {
1685  /* check for implications for lower or upper bounds (only store implications with bounds tightened at least by 0.5)
1686  * in case of binary variables, this should have been handled in the previous cases, since every boundchange also fixes the variable
1687  */
1688  if( leftpropubs[j] < newub - 0.5 && (leftimplubs == NULL || leftpropubs[j] < leftimplubs[j]) )
1689  {
1690  /* insert implication: probingvar == 0 => var <= leftpropubs[j] */
1691  /*SCIPdebugMsg(scip, "found implication <%s> == 0 => <%s>[%g,%g] <= %g\n",
1692  SCIPvarGetName(probingvar), SCIPvarGetName(var), newlb, newub, leftpropubs[j]);*/
1693  SCIP_CALL( SCIPaddVarImplication(scip, probingvar, FALSE, var, SCIP_BOUNDTYPE_UPPER, leftpropubs[j],
1694  cutoff, &nboundchanges) );
1695  (*nimplications)++;
1696  (*nchgbds) += nboundchanges;
1697 
1698  if( *cutoff )
1699  {
1700  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 0 => <%s> <= %g\n",
1701  SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), leftpropubs[j]);
1702  }
1703  }
1704  if( leftproplbs[j] > newlb + 0.5 && (leftimpllbs == NULL || leftproplbs[j] > leftimpllbs[j]) && !*cutoff )
1705  {
1706  /* insert implication: probingvar == 0 => var >= leftproplbs[j] */
1707  /*SCIPdebugMsg(scip, "found implication <%s> == 0 => <%s>[%g,%g] >= %g\n",
1708  SCIPvarGetName(probingvar), SCIPvarGetName(var), newlb, newub, leftproplbs[j]);*/
1709  SCIP_CALL( SCIPaddVarImplication(scip, probingvar, FALSE, var, SCIP_BOUNDTYPE_LOWER, leftproplbs[j],
1710  cutoff, &nboundchanges) );
1711  (*nimplications)++;
1712  (*nchgbds) += nboundchanges;
1713 
1714  if( *cutoff )
1715  {
1716  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 0 => <%s> >= %g\n",
1717  SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), leftproplbs[j]);
1718  }
1719  }
1720  if( rightpropubs[j] < newub - 0.5 && (rightimplubs == NULL || rightpropubs[j] < rightimplubs[j]) && !*cutoff )
1721  {
1722  /* insert implication: probingvar == 1 => var <= rightpropubs[j] */
1723  /*SCIPdebugMsg(scip, "found implication <%s> == 1 => <%s>[%g,%g] <= %g\n",
1724  SCIPvarGetName(probingvar), SCIPvarGetName(var), newlb, newub, rightpropubs[j]);*/
1725  SCIP_CALL( SCIPaddVarImplication(scip, probingvar, TRUE, var, SCIP_BOUNDTYPE_UPPER, rightpropubs[j],
1726  cutoff, &nboundchanges) );
1727  (*nimplications)++;
1728  (*nchgbds) += nboundchanges;
1729 
1730  if( *cutoff )
1731  {
1732  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 1 => <%s> <= %g\n",
1733  SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), rightpropubs[j]);
1734  }
1735  }
1736  if( rightproplbs[j] > newlb + 0.5 && (rightimpllbs == NULL || rightproplbs[j] > rightimpllbs[j]) && !*cutoff )
1737  {
1738  /* insert implication: probingvar == 1 => var >= rightproplbs[j] */
1739  /*SCIPdebugMsg(scip, "found implication <%s> == 1 => <%s>[%g,%g] >= %g\n",
1740  SCIPvarGetName(probingvar), SCIPvarGetName(var), newlb, newub, rightproplbs[j]);*/
1741  SCIP_CALL( SCIPaddVarImplication(scip, probingvar, TRUE, var, SCIP_BOUNDTYPE_LOWER, rightproplbs[j],
1742  cutoff, &nboundchanges) );
1743  (*nimplications)++;
1744  (*nchgbds) += nboundchanges;
1745 
1746  if( *cutoff )
1747  {
1748  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 1 => <%s> <= %g\n",
1749  SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), rightproplbs[j]);
1750  }
1751  }
1752  }
1753  }
1754  }
1755 
1756  return SCIP_OKAY;
1757 }
SCIP_RETCODE SCIPsetPropPresol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPPRESOL((*proppresol)), int presolpriority, int presolmaxrounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip.c:7823
static SCIP_RETCODE sortVariables(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR **vars, int nvars, int firstidx)
Definition: prop_probing.c:175
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip.c:36995
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip.c:48620
#define DEFAULT_MAXSUMUSELESS
Definition: prop_probing.c:69
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
int SCIPgetNIntVars(SCIP *scip)
Definition: scip.c:11896
static SCIP_DECL_PROPEXITPRE(propExitpreProbing)
Definition: prop_probing.c:803
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip.c:46300
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:22517
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip.c:41398
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:821
#define PROP_PRESOLTIMING
Definition: prop_probing.c:41
static SCIP_DECL_PROPCOPY(propCopyProbing)
Definition: prop_probing.c:712
SCIP_Bool SCIPisUbBetter(SCIP *scip, SCIP_Real newub, SCIP_Real oldlb, SCIP_Real oldub)
Definition: scip.c:47655
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17276
#define PROP_DESC
Definition: prop_probing.c:33
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed)
Definition: scip.c:48602
static long bound
static SCIP_DECL_PROPINITSOL(propInitsolProbing)
Definition: prop_probing.c:825
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17332
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47009
void SCIPsortDownRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip.c:18760
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16842
#define MAXDNOM
Definition: prop_probing.c:45
void SCIPswapPointers(void **pointer1, void **pointer2)
Definition: misc.c:9639
#define FALSE
Definition: def.h:64
#define DEFAULT_MAXUSELESS
Definition: prop_probing.c:63
SCIP_RETCODE SCIPpropagateProbingImplications(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip.c:36414
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47022
#define TRUE
Definition: def.h:63
#define SCIPdebug(x)
Definition: pub_message.h:74
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
enum SCIP_VerbLevel SCIP_VERBLEVEL
Definition: type_message.h:48
#define PROP_FREQ
Definition: prop_probing.c:36
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:22633
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
SCIP_Real SCIPselectSimpleValue(SCIP_Real lb, SCIP_Real ub, SCIP_Longint maxdnom)
Definition: misc.c:9126
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:36034
static SCIP_RETCODE applyProbing(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR **vars, int nvars, int nbinvars, int *startidx, int *nfixedvars, int *naggrvars, int *nchgbds, int oldnfixedvars, int oldnaggrvars, SCIP_Bool *delay, SCIP_Bool *cutoff)
Definition: prop_probing.c:322
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46957
SCIP_RETCODE SCIPaddVarVlb(SCIP *scip, SCIP_VAR *var, SCIP_VAR *vlbvar, SCIP_Real vlbcoef, SCIP_Real vlbconstant, SCIP_Bool *infeasible, int *nbdchgs)
Definition: scip.c:23969
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7350
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
SCIP_RETCODE SCIPaddVarVub(SCIP *scip, SCIP_VAR *var, SCIP_VAR *vubvar, SCIP_Real vubcoef, SCIP_Real vubconstant, SCIP_Bool *infeasible, int *nbdchgs)
Definition: scip.c:24028
static SCIP_RETCODE freeSortedvars(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_probing.c:146
#define SCIPdebugMsg
Definition: scip.h:455
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4265
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17628
SCIP_Real SCIPepsilon(SCIP *scip)
Definition: scip.c:46409
#define DEFAULT_MAXRUNS
Definition: prop_probing.c:58
const char * SCIPgetProbName(SCIP *scip)
Definition: scip.c:10885
#define DEFAULT_MAXDEPTH
Definition: prop_probing.c:72
SCIP_Bool SCIPisLbBetter(SCIP *scip, SCIP_Real newlb, SCIP_Real oldlb, SCIP_Real oldub)
Definition: scip.c:47640
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7340
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17286
SCIP_RETCODE SCIPsetPropExitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITPRE((*propexitpre)))
Definition: scip.c:7807
static SCIP_DECL_PROPINIT(propInitProbing)
Definition: prop_probing.c:748
#define DEFAULT_PROPROUNDS
Definition: prop_probing.c:59
static SCIP_DECL_PROPEXIT(propExitProbing)
Definition: prop_probing.c:768
static SCIP_RETCODE aggregation(SCIP *scip, AGGREGATIONDATA *aggrdata, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_Bool allowlocal, SCIP_Real *rowlhsscores, SCIP_Real *rowrhsscores, int startrow, int maxaggrs, SCIP_Bool *wastried, SCIP_Bool *cutoff, int *cutinds, SCIP_Real *cutcoefs, SCIP_Bool negate, int *ncuts)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46970
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip.c:36308
#define DEFAULT_RANDSEED
Definition: prop_probing.c:73
#define DEFAULT_MAXFIXINGS
Definition: prop_probing.c:60
SCIP_RETCODE SCIPaddVarImplication(SCIP *scip, SCIP_VAR *var, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_BOUNDTYPE impltype, SCIP_Real implbound, SCIP_Bool *infeasible, int *nbdchgs)
Definition: scip.c:24088
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip.c:35993
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
#define SCIP_CALL(x)
Definition: def.h:350
int SCIPgetNTotalVars(SCIP *scip)
Definition: scip.c:12383
static SCIP_RETCODE initPropdata(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_probing.c:117
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip.c:1360
static SCIP_DECL_PROPEXEC(propExecProbing)
Definition: prop_probing.c:978
static SCIP_DECL_PROPRESPROP(propRespropProbing)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
SCIP_RETCODE SCIPsetPropInit(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINIT((*propinit)))
Definition: scip.c:7727
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:29287
int SCIPgetNImplVars(SCIP *scip)
Definition: scip.c:11941
#define SCIPduplicateMemoryArray(scip, ptr, source, num)
Definition: scip.h:22565
#define PROP_PRESOL_MAXROUNDS
Definition: prop_probing.c:42
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:43039
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17554
int SCIPvarGetNLocksUp(SCIP_VAR *var)
Definition: var.c:3217
#define MAX(x, y)
Definition: tclique_def.h:75
void SCIPenableVarHistory(SCIP *scip)
Definition: scip.c:25952
SCIP_RETCODE SCIPanalyzeDeductionsProbing(SCIP *scip, SCIP_VAR *probingvar, SCIP_Real leftub, SCIP_Real rightlb, int nvars, SCIP_VAR **vars, SCIP_Real *leftimpllbs, SCIP_Real *leftimplubs, SCIP_Real *leftproplbs, SCIP_Real *leftpropubs, SCIP_Real *rightimpllbs, SCIP_Real *rightimplubs, SCIP_Real *rightproplbs, SCIP_Real *rightpropubs, int *nfixedvars, int *naggrvars, int *nimplications, int *nchgbds, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip.c:7695
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip.h:22569
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip.c:25569
#define SCIPreallocMemoryArray(scip, ptr, newnum)
Definition: scip.h:22559
int SCIPgetNRuns(SCIP *scip)
Definition: scip.c:42044
#define DEFAULT_MAXTOTALUSELESS
Definition: prop_probing.c:66
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11851
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:9388
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip.c:35830
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:887
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11806
#define PROP_PRESOL_PRIORITY
Definition: prop_probing.c:40
SCIP_RETCODE SCIPapplyProbingVar(SCIP *scip, SCIP_VAR **vars, int nvars, int probingpos, SCIP_BOUNDTYPE boundtype, SCIP_Real bound, int maxproprounds, SCIP_Real *impllbs, SCIP_Real *implubs, SCIP_Real *proplbs, SCIP_Real *propubs, SCIP_Bool *cutoff)
int SCIPvarGetNLocksDown(SCIP_VAR *var)
Definition: var.c:3162
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
Definition: scip.c:7856
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46996
static SCIP_DECL_PROPFREE(propFreeProbing)
Definition: prop_probing.c:727
probing propagator
#define PROP_NAME
Definition: prop_probing.c:32
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11761
SCIP_RETCODE SCIPsetPropInitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITSOL((*propinitsol)))
Definition: scip.c:7759
SCIP_RETCODE SCIPaggregateVars(SCIP *scip, SCIP_VAR *varx, SCIP_VAR *vary, SCIP_Real scalarx, SCIP_Real scalary, SCIP_Real rhs, SCIP_Bool *infeasible, SCIP_Bool *redundant, SCIP_Bool *aggregated)
Definition: scip.c:25678
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:18726
#define SCIP_Real
Definition: def.h:149
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:38
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1145
SCIP_RETCODE SCIPincludePropProbing(SCIP *scip)
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip.c:7711
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
Definition: prop.c:735
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
Definition: prop.c:745
#define SCIP_Longint
Definition: def.h:134
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:16959
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16827
#define PROP_TIMING
Definition: prop_probing.c:34
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:47070
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46983
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17342
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip.c:35852
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:112
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
Definition: scip.c:47155
SCIP_RETCODE SCIPsetPropInitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITPRE((*propinitpre)))
Definition: scip.c:7791
SCIP_RETCODE SCIPsetPropExit(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXIT((*propexit)))
Definition: scip.c:7743
#define SCIPfreeMemoryArrayNull(scip, ptr)
Definition: scip.h:22570
static SCIP_DECL_PROPPRESOL(propPresolProbing)
Definition: prop_probing.c:844
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:36078
#define PROP_DELAY
Definition: prop_probing.c:37
SCIP_Bool SCIPvarIsDeleted(SCIP_VAR *var)
Definition: var.c:16883
static SCIP_DECL_PROPINITPRE(propInitpreProbing)
Definition: prop_probing.c:788
SCIP_Real SCIPpropGetTime(SCIP_PROP *prop)
Definition: prop.c:1002
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:47143
#define PROP_PRIORITY
Definition: prop_probing.c:35
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:16949
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip.h:22624
SCIP_RETCODE SCIPincludePropBasic(SCIP *scip, SCIP_PROP **propptr, const char *name, const char *desc, int priority, int freq, SCIP_Bool delay, SCIP_PROPTIMING timingmask, SCIP_DECL_PROPEXEC((*propexec)), SCIP_PROPDATA *propdata)
Definition: scip.c:7658