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