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-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file prop_probing.c
17  * @ingroup DEFPLUGINS_PROP
18  * @brief probing propagator
19  * @author Tobias Achterberg
20  * @author Matthias Miltenberger
21  * @author Michael Winkler
22  */
23 
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
25 
26 #include "blockmemshell/memory.h"
27 #include "scip/prop_probing.h"
28 #include "scip/pub_message.h"
29 #include "scip/pub_misc.h"
30 #include "scip/pub_misc_sort.h"
31 #include "scip/pub_prop.h"
32 #include "scip/pub_tree.h"
33 #include "scip/pub_var.h"
34 #include "scip/scip_branch.h"
35 #include "scip/scip_general.h"
36 #include "scip/scip_lp.h"
37 #include "scip/scip_mem.h"
38 #include "scip/scip_message.h"
39 #include "scip/scip_numerics.h"
40 #include "scip/scip_param.h"
41 #include "scip/scip_prob.h"
42 #include "scip/scip_probing.h"
43 #include "scip/scip_prop.h"
44 #include "scip/scip_randnumgen.h"
45 #include "scip/scip_solvingstats.h"
46 #include "scip/scip_timing.h"
47 #include "scip/scip_tree.h"
48 #include "scip/scip_var.h"
49 #include <string.h>
50 
51 #define PROP_NAME "probing"
52 #define PROP_DESC "probing propagator on binary variables"
53 #define PROP_TIMING SCIP_PROPTIMING_AFTERLPLOOP
54 #define PROP_PRIORITY -100000 /**< propagation priority */
55 #define PROP_FREQ -1 /**< propagation frequency */
56 #define PROP_DELAY TRUE /**< should propagation method be delayed, if other propagators found
57  * reductions? */
58 #define PROP_PRESOL_PRIORITY -100000 /**< priority of the presolving method (>= 0: before, < 0: after constraint handlers); combined with presolvers */
59 #define PROP_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolving method (fast, medium, or exhaustive) */
60 #define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no
61  * limit) */
62 #define MAXDNOM 10000LL /**< maximal denominator for simple rational fixed values */
63 
64 
65 /* @todo check for restricting the maximal number of implications that can be added by probing */
66 
67 /* sorting of probing variables, two different variants are implemeneted */
68 /* #define VARIANT_B */
69 
70 
71 /*
72  * Default parameter settings
73  */
74 
75 #define DEFAULT_MAXRUNS 1 /**< maximal number of runs, probing participates in (-1: no limit) */
76 #define DEFAULT_PROPROUNDS -1 /**< maximal number of propagation rounds in probing subproblems */
77 #define DEFAULT_MAXFIXINGS 25 /**< maximal number of fixings found, until probing is interrupted
78  * (0: don't interrupt) */
79 #define DEFAULT_MAXUSELESS 1000 /**< maximal number of successive probings without fixings,
80  * until probing is aborted (0: don't abort) */
81 #define DEFAULT_MAXTOTALUSELESS 50 /**< maximal number of successive probings without fixings, bound changes,
82  * and implications, until probing is aborted (0: don't abort) */
83 #define DEFAULT_MAXSUMUSELESS 0 /**< maximal number of probings without fixings, until probing is aborted
84  * (0: don't abort) */
85 #define DEFAULT_MAXDEPTH -1 /**< maximal depth until propagation is executed(-1: no limit) */
86 #define DEFAULT_RANDSEED 59 /**< random initial seed */
87 
88 /*
89  * Data structures
90  */
91 
92 /** propagator data */
93 struct SCIP_PropData
94 {
95  SCIP_VAR** sortedvars; /**< problem variables sorted by number of rounding locks, used in presolving */
96  int* nprobed; /**< array of numbers how often we already probed on each variables */
97  int noldtotalvars; /**< number of total variables in problem */
98  int nsortedvars; /**< number of problem variables, used in presolving */
99  int nsortedbinvars; /**< number of binary problem variables, used in presolving */
100  int maxruns; /**< maximal number of runs, probing participates in (-1: no limit) */
101  int proprounds; /**< maximal number of propagation rounds in probing subproblems */
102  int maxfixings; /**< maximal number of fixings found, until probing is interrupted
103  * (0: don't interrupt) */
104  int maxuseless; /**< maximal number of successive probings without fixings,
105  * until probing is aborted (0: don't abort) */
106  int maxtotaluseless; /**< maximal number of successive probings without fixings, bound changes,
107  * and implications, until probing is aborted (0: don't abort) */
108  int maxsumuseless; /**< maximal number of probings without fixings, until probing is aborted
109  * (0: don't abort) */
110  int startidx; /**< starting variable index of next call, used in presolving */
111  int lastsortstartidx; /**< last starting variable index where the variables have been sorted, used in presolving */
112  int nfixings; /**< total number of fixings found in probing */
113  int naggregations; /**< total number of aggregations found in probing */
114  int nimplications; /**< total number of implications found in probing */
115  int nbdchgs; /**< total number of bound changes found in probing */
116  int nuseless; /**< current number of successive useless probings */
117  int ntotaluseless; /**< current number of successive totally useless probings */
118  int nsumuseless; /**< current number of useless probings */
119  int maxdepth; /**< maximal depth until propagation is executed */
120  SCIP_Longint lastnode; /**< last node where probing was applied, or -1 for presolving, and -2 for not applied yet */
121  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
122 };
123 
124 
125 /*
126  * Local methods
127  */
128 /** initializes the propagator data */
129 static
131  SCIP_PROPDATA* propdata /**< propagator data */
132  )
133 {
134  assert(propdata != NULL);
135 
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(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  SCIPdebug( 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  SCIPdebug( SCIPdebugMsg(scip, "probing propagation found %d fixings, %d aggregation, %d nchgbds, and %d implications\n",
1093  nfixedvars, naggrvars, nchgbds, (propdata->nimplications) - oldnimplications); )
1094 
1095  if( delay )
1096  {
1097  /* probing was interrupted because it reached the maximal fixings parameter, so we want to rerun it at the next call */
1098  propdata->lastnode = -2;
1099  }
1100 
1101  /* adjust result code */
1102  if( cutoff )
1103  *result = SCIP_CUTOFF;
1104  else if( nfixedvars > oldnfixedvars || naggrvars > oldnaggrvars || nchgbds > oldnchgbds )
1105  *result = SCIP_REDUCEDDOM;
1106 
1107  TERMINATE:
1108  SCIPfreeBufferArray(scip, &binvars);
1109 
1110  return SCIP_OKAY; /*lint !e438*/
1111 }
1112 
1113 
1114 /** propagation conflict resolving method of propagator */
1115 static
1116 SCIP_DECL_PROPRESPROP(propRespropProbing)
1117 { /*lint --e{715}*/
1118  *result = SCIP_DIDNOTRUN;
1119 
1120  return SCIP_OKAY;
1121 }
1123 
1124 /*
1125  * propagator specific interface methods
1126  */
1127 
1128 /** creates the probing propagator and includes it in SCIP */
1130  SCIP* scip /**< SCIP data structure */
1131  )
1132 {
1133  SCIP_PROPDATA* propdata;
1134  SCIP_PROP* prop;
1136  /* create probing propagator data */
1137  SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) );
1138  SCIP_CALL( initPropdata(propdata) );
1139 
1140  /* include propagator */
1142  propExecProbing, propdata) );
1143 
1144  assert(prop != NULL);
1145 
1146  /* set optional callbacks via setter functions */
1147  SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyProbing) );
1148  SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeProbing) );
1149  SCIP_CALL( SCIPsetPropInit(scip, prop, propInitProbing) );
1150  SCIP_CALL( SCIPsetPropExit(scip, prop, propExitProbing) );
1151  SCIP_CALL( SCIPsetPropInitsol(scip, prop, propInitsolProbing) );
1152  SCIP_CALL( SCIPsetPropInitpre(scip, prop, propInitpreProbing) );
1153  SCIP_CALL( SCIPsetPropExitpre(scip, prop, propExitpreProbing) );
1154  SCIP_CALL( SCIPsetPropPresol(scip, prop, propPresolProbing, PROP_PRESOL_PRIORITY, PROP_PRESOL_MAXROUNDS,
1155  PROP_PRESOLTIMING) );
1156  SCIP_CALL( SCIPsetPropResprop(scip, prop, propRespropProbing) );
1157 
1158  /* add probing propagator parameters */
1159  SCIP_CALL( SCIPaddIntParam(scip,
1160  "propagating/" PROP_NAME "/maxruns",
1161  "maximal number of runs, probing participates in (-1: no limit)",
1162  &propdata->maxruns, FALSE, DEFAULT_MAXRUNS, -1, INT_MAX, NULL, NULL) );
1163  SCIP_CALL( SCIPaddIntParam(scip,
1164  "propagating/" PROP_NAME "/proprounds",
1165  "maximal number of propagation rounds in probing subproblems (-1: no limit, 0: auto)",
1166  &propdata->proprounds, TRUE, DEFAULT_PROPROUNDS, -1, INT_MAX, NULL, NULL) );
1167  SCIP_CALL( SCIPaddIntParam(scip,
1168  "propagating/" PROP_NAME "/maxfixings",
1169  "maximal number of fixings found, until probing is interrupted (0: don't iterrupt)",
1170  &propdata->maxfixings, TRUE, DEFAULT_MAXFIXINGS, 0, INT_MAX, NULL, NULL) );
1171  SCIP_CALL( SCIPaddIntParam(scip,
1172  "propagating/" PROP_NAME "/maxuseless",
1173  "maximal number of successive probings without fixings, until probing is aborted (0: don't abort)",
1174  &propdata->maxuseless, TRUE, DEFAULT_MAXUSELESS, 0, INT_MAX, NULL, NULL) );
1175  SCIP_CALL( SCIPaddIntParam(scip,
1176  "propagating/" PROP_NAME "/maxtotaluseless",
1177  "maximal number of successive probings without fixings, bound changes, and implications, until probing is aborted (0: don't abort)",
1178  &propdata->maxtotaluseless, TRUE, DEFAULT_MAXTOTALUSELESS, 0, INT_MAX, NULL, NULL) );
1179  SCIP_CALL( SCIPaddIntParam(scip,
1180  "propagating/" PROP_NAME "/maxsumuseless",
1181  "maximal number of probings without fixings, until probing is aborted (0: don't abort)",
1182  &propdata->maxsumuseless, TRUE, DEFAULT_MAXSUMUSELESS, 0, INT_MAX, NULL, NULL) );
1183  SCIP_CALL( SCIPaddIntParam(scip,
1184  "propagating/" PROP_NAME "/maxdepth",
1185  "maximal depth until propagation is executed(-1: no limit)",
1186  &propdata->maxdepth, TRUE, DEFAULT_MAXDEPTH, -1, INT_MAX, NULL, NULL) );
1187 
1188  return SCIP_OKAY;
1189 }
1190 
1191 
1192 /** applies and evaluates probing of a single variable in the given direction and bound */
1194  SCIP* scip, /**< SCIP data structure */
1195  SCIP_VAR** vars, /**< problem variables */
1196  int nvars, /**< number of problem variables */
1197  int probingpos, /**< variable number to apply probing on */
1198  SCIP_BOUNDTYPE boundtype, /**< which bound should be changed */
1199  SCIP_Real bound, /**< which bound should be set */
1200  int maxproprounds, /**< maximal number of propagation rounds (-1: no limit, 0: parameter settings) */
1201  SCIP_Real* impllbs, /**< array to store lower bounds after applying implications and cliques */
1202  SCIP_Real* implubs, /**< array to store upper bounds after applying implications and cliques */
1203  SCIP_Real* proplbs, /**< array to store lower bounds after full propagation */
1204  SCIP_Real* propubs, /**< array to store upper bounds after full propagation */
1205  SCIP_Bool* cutoff /**< pointer to store whether the probing direction is infeasible */
1206  )
1207 {
1208  assert(impllbs != NULL);
1209  assert(implubs != NULL);
1210  assert(proplbs != NULL);
1211  assert(propubs != NULL);
1212  assert(cutoff != NULL);
1213  assert(0 <= probingpos && probingpos < nvars);
1214  assert(SCIPisGE(scip, bound, SCIPvarGetLbLocal(vars[probingpos])));
1215  assert(SCIPisLE(scip, bound, SCIPvarGetUbLocal(vars[probingpos])));
1216 
1217  SCIPdebugMsg(scip, "applying probing on variable <%s> %s %g (nlocks=%d/%d, impls=%d/%d, clqs=%d/%d)\n",
1218  SCIPvarGetName(vars[probingpos]), boundtype == SCIP_BOUNDTYPE_UPPER ? "<=" : ">=", bound,
1219  SCIPvarGetNLocksDownType(vars[probingpos], SCIP_LOCKTYPE_MODEL),
1220  SCIPvarGetNLocksUpType(vars[probingpos], SCIP_LOCKTYPE_MODEL),
1221  SCIPvarGetNImpls(vars[probingpos], FALSE), SCIPvarGetNImpls(vars[probingpos], TRUE),
1222  SCIPvarGetNCliques(vars[probingpos], FALSE), SCIPvarGetNCliques(vars[probingpos], TRUE));
1223 
1224  /* in debug mode we assert above that this trivial infeasibility does not occur (for performance reasons), but in
1225  * optimized mode we return safely
1226  */
1227  if( SCIPisLT(scip, bound, SCIPvarGetLbLocal(vars[probingpos]))
1228  || SCIPisGT(scip, bound, SCIPvarGetUbLocal(vars[probingpos])) )
1229  {
1230  SCIPdebugMsg(scip, " -> trivial infeasibility detected\n");
1231  *cutoff = TRUE;
1232  return SCIP_OKAY;
1233  }
1234 
1235  /* start probing mode */
1236  SCIP_CALL( SCIPstartProbing(scip) );
1237 
1238  /* enables collection of variable statistics during probing */
1239  SCIPenableVarHistory(scip);
1240 
1241  /* fix variable */
1242  if( boundtype == SCIP_BOUNDTYPE_UPPER )
1243  {
1244  SCIP_CALL( SCIPchgVarUbProbing(scip, vars[probingpos], bound) );
1245  }
1246  else
1247  {
1248  assert(boundtype == SCIP_BOUNDTYPE_LOWER);
1249  SCIP_CALL( SCIPchgVarLbProbing(scip, vars[probingpos], bound) );
1250  }
1251 
1252  /* @todo it might pay off to catch the bounds-tightened event on all variables and then only get the implied and
1253  * propagated bounds on those variables which where really changed on propagation
1254  */
1255 
1256  /* apply propagation of implication graph and clique table */
1258  if( !(*cutoff) )
1259  {
1260  int i;
1261 
1262  for( i = 0; i < nvars; ++i )
1263  {
1264  impllbs[i] = SCIPvarGetLbLocal(vars[i]);
1265  implubs[i] = SCIPvarGetUbLocal(vars[i]);
1266  }
1267 
1268  /* apply propagation */
1269  SCIP_CALL( SCIPpropagateProbing(scip, maxproprounds, cutoff, NULL) );
1270  }
1271  else
1272  {
1273  SCIPdebugMsg(scip, "propagating probing implications after <%s> to %g led to a cutoff\n",
1274  SCIPvarGetName(vars[probingpos]), bound);
1275  }
1276 
1277  /* evaluate propagation */
1278  if( !(*cutoff) )
1279  {
1280  int i;
1281 
1282  for( i = 0; i < nvars; ++i )
1283  {
1284  proplbs[i] = SCIPvarGetLbLocal(vars[i]);
1285  propubs[i] = SCIPvarGetUbLocal(vars[i]);
1286 #if 0
1287 #ifdef SCIP_DEBUG
1288  if( SCIPisGT(scip, proplbs[i], SCIPvarGetLbGlobal(vars[i])) )
1289  {
1290  SCIPdebugMsg(scip, " -> <%s>[%g,%g] >= %g\n", SCIPvarGetName(vars[i]),
1291  SCIPvarGetLbGlobal(vars[i]), SCIPvarGetUbGlobal(vars[i]), proplbs[i]);
1292  }
1293  if( SCIPisLT(scip, propubs[i], SCIPvarGetUbGlobal(vars[i])) )
1294  {
1295  SCIPdebugMsg(scip, " -> <%s>[%g,%g] <= %g\n", SCIPvarGetName(vars[i]),
1296  SCIPvarGetLbGlobal(vars[i]), SCIPvarGetUbGlobal(vars[i]), propubs[i]);
1297  }
1298 #endif
1299 #endif
1300  }
1301  }
1302 
1303  /* exit probing mode */
1304  SCIP_CALL( SCIPendProbing(scip) );
1305 
1306  return SCIP_OKAY;
1307 }
1308 
1309 /** analyses boundchanges resulting from probing on a variable and performs deduced fixations, aggregations, and domain tightenings
1310  * Given a variable probingvar with domain [l,u] and bound tightening results from reducing the domain
1311  * once to [l,leftub] and once to [rightlb,u], the method computes and applies resulting variable fixations, aggregations,
1312  * implications, and bound changes. Variable probingvar does not need to be binary.
1313  * The whole domain of probingvar need to be covered by the left and right branches, i.e.,
1314  * we assume leftub >= rightlb for continuous variables or floor(leftub) >= ceil(rightlb)-1 for discrete variables.
1315  * Bounds after applying implications and cliques do not need to be provided, but if they are omitted and probingvar is a binary variable,
1316  * then already existing implications may be added.
1317  */
1319  SCIP* scip, /**< SCIP data structure */
1320  SCIP_VAR* probingvar, /**< the probing variable */
1321  SCIP_Real leftub, /**< upper bound of probing variable in left branch */
1322  SCIP_Real rightlb, /**< lower bound of probing variable in right branch */
1323  int nvars, /**< number of variables which bound changes should be analyzed */
1324  SCIP_VAR** vars, /**< variables which bound changes should be analyzed */
1325  SCIP_Real* leftimpllbs, /**< lower bounds after applying implications and cliques in left branch, or NULL */
1326  SCIP_Real* leftimplubs, /**< upper bounds after applying implications and cliques in left branch, or NULL */
1327  SCIP_Real* leftproplbs, /**< lower bounds after applying domain propagation in left branch */
1328  SCIP_Real* leftpropubs, /**< upper bounds after applying domain propagation in left branch */
1329  SCIP_Real* rightimpllbs, /**< lower bounds after applying implications and cliques in right branch, or NULL */
1330  SCIP_Real* rightimplubs, /**< upper bounds after applying implications and cliques in right branch, or NULL */
1331  SCIP_Real* rightproplbs, /**< lower bounds after applying domain propagation in right branch */
1332  SCIP_Real* rightpropubs, /**< upper bounds after applying domain propagation in right branch */
1333  int* nfixedvars, /**< pointer to counter which is increased by the number of deduced variable fixations */
1334  int* naggrvars, /**< pointer to counter which is increased by the number of deduced variable aggregations */
1335  int* nimplications, /**< pointer to counter which is increased by the number of deduced implications */
1336  int* nchgbds, /**< pointer to counter which is increased by the number of deduced bound tightenings */
1337  SCIP_Bool* cutoff /**< buffer to store whether a cutoff is detected */
1338  )
1339 {
1340  SCIP_Bool fixedleft;
1341  SCIP_Bool fixedright;
1342  SCIP_Bool probingvarisbinary;
1343  SCIP_Bool probingvarisinteger;
1344  int j;
1345 
1346  assert(scip != NULL);
1347  assert(probingvar != NULL);
1348  assert(SCIPisGE(scip, leftub, SCIPvarGetLbLocal(probingvar))); /* left branch should not be empty by default */
1349  assert(SCIPisLE(scip, rightlb, SCIPvarGetUbLocal(probingvar))); /* right branch should not be empty by default */
1350  assert(vars != NULL || nvars == 0);
1351  assert(leftproplbs != NULL);
1352  assert(leftpropubs != NULL);
1353  assert(rightproplbs != NULL);
1354  assert(rightpropubs != NULL);
1355  assert(nfixedvars != NULL);
1356  assert(naggrvars != NULL);
1357  assert(nimplications != NULL);
1358  assert(nchgbds != NULL);
1359  assert(cutoff != NULL);
1360 
1361  /* @todo the asserts below could be relaxed by taking domain holes into account */
1362  if( SCIPvarGetType(probingvar) != SCIP_VARTYPE_CONTINUOUS )
1363  {
1364  /* adjust bounds to actually used ones */
1365  leftub = SCIPfloor(scip, leftub);
1366  rightlb = SCIPceil(scip, rightlb);
1367 
1368  probingvarisinteger = TRUE;
1369  probingvarisbinary = SCIPvarIsBinary(probingvar);
1370  }
1371  else
1372  {
1373  /* assert dichotomy in case of continuous var: leftub >= rightlb */
1374  assert(SCIPisGE(scip, leftub, rightlb));
1375  probingvarisbinary = FALSE;
1376  probingvarisinteger = FALSE;
1377  }
1378 
1379  /* check if probing variable was fixed in the branches */
1380  fixedleft = SCIPisEQ(scip, SCIPvarGetLbLocal(probingvar), leftub);
1381  fixedright = SCIPisEQ(scip, SCIPvarGetUbLocal(probingvar), rightlb);
1382 
1383  *cutoff = FALSE;
1384 
1385  for( j = 0; j < nvars && !*cutoff; ++j )
1386  {
1387  SCIP_VAR* var;
1388  SCIP_Bool varisinteger;
1389  SCIP_Real newlb;
1390  SCIP_Real newub;
1391 
1392  assert(vars != NULL); /* for flexelint */
1393 
1394  var = vars[j];
1395  assert(var != NULL);
1396 
1397  /* @todo: add holes, and even add holes if x was the probing variable and it followed a better bound on x itself */
1398  /* @todo: check if we probed on an integer variable, that this maybe led to aggregation on two other variables, i.e
1399  * probing on x <= 1 and x >= 2 led to y = 1, z = 1 and y = 0, z = 0 resp., which means y = Z
1400  */
1401 
1402  /* if probing variable is binary, then there is nothing we could deduce here (variable should be fixed in both branches)
1403  * if it is not binary, we want to see if we found bound tightenings, even though it seems quite unlikely */
1404  if( var == probingvar && probingvarisbinary )
1405  continue;
1406 
1407  /* new bounds of the variable is the union of the propagated bounds of the left and right case */
1408  newlb = MIN(leftproplbs[j], rightproplbs[j]);
1409  newub = MAX(leftpropubs[j], rightpropubs[j]);
1410  varisinteger = (SCIPvarGetType(var) < SCIP_VARTYPE_CONTINUOUS);
1411 
1412  /* check for fixed variables */
1413  if( SCIPisEQ(scip, newlb, newub) )
1414  {
1415  SCIP_Real fixval;
1416  SCIP_Bool fixed;
1417 
1418  if( !varisinteger )
1419  {
1420  /* in both probings, variable j is deduced to the same value: fix variable to this value */
1421  fixval = SCIPselectSimpleValue(newlb - 0.9 * SCIPepsilon(scip), newub + 0.9 * SCIPepsilon(scip), MAXDNOM);
1422  }
1423  else
1424  {
1425  fixval = newlb;
1426  }
1427 
1429  {
1430  SCIP_CALL( SCIPfixVar(scip, var, fixval, cutoff, &fixed) );
1431  }
1432  else
1433  {
1434  SCIP_CALL( SCIPtightenVarLb(scip, var, fixval, TRUE, cutoff, &fixed) );
1435  if( !*cutoff )
1436  {
1437  SCIP_Bool tightened;
1438 
1439  SCIP_CALL( SCIPtightenVarUb(scip, var, fixval, TRUE, cutoff, &tightened) );
1440  fixed &= tightened;
1441  }
1442  }
1443 
1444  if( fixed )
1445  {
1446  SCIPdebugMsg(scip, "fixed variable <%s> to %g due to probing on <%s> with nlocks=(%d/%d)\n",
1447  SCIPvarGetName(var), fixval,
1450  (*nfixedvars)++;
1451  }
1452  else if( *cutoff )
1453  {
1454  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible fixing of variable <%s> to %g\n",
1455  SCIPvarGetName(probingvar), SCIPvarGetName(var), fixval);
1456  }
1457 
1458  continue;
1459  }
1460  else
1461  {
1462  /* check for bound tightenings */
1463  SCIP_Real oldlb;
1464  SCIP_Real oldub;
1465  SCIP_Bool tightened;
1466  SCIP_Bool tightenlb;
1467  SCIP_Bool tightenub;
1468  SCIP_Bool force;
1469 
1470  oldlb = SCIPvarGetLbLocal(var);
1471  oldub = SCIPvarGetUbLocal(var);
1472 
1473  if( varisinteger )
1474  {
1475  force = TRUE;
1476  tightenlb = (newlb > oldlb + 0.5);
1477  tightenub = (newub < oldub - 0.5);
1478  }
1479  else
1480  {
1481  force = TRUE;
1482  tightenlb = SCIPisLbBetter(scip, newlb, oldlb, oldub);
1483  tightenub = SCIPisUbBetter(scip, newub, oldlb, oldub);
1484  }
1485 
1486  if( tightenlb )
1487  {
1488  /* in both probings, variable j is deduced to be at least newlb: tighten lower bound */
1489  SCIP_CALL( SCIPtightenVarLb(scip, var, newlb, force, cutoff, &tightened) );
1490  if( tightened )
1491  {
1492  SCIPdebugMsg(scip, "tightened lower bound of variable <%s>[%g,%g] to %g due to probing on <%s> with nlocks=(%d/%d)\n",
1493  SCIPvarGetName(var), oldlb, oldub, newlb,
1496  (*nchgbds)++;
1497  }
1498  else if( *cutoff )
1499  {
1500  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible new lower bound of variable <%s> to %g\n",
1501  SCIPvarGetName(probingvar), SCIPvarGetName(var), newlb);
1502  }
1503  }
1504 
1505  if( tightenub && !*cutoff )
1506  {
1507  /* in both probings, variable j is deduced to be at most newub: tighten upper bound */
1508  SCIP_CALL( SCIPtightenVarUb(scip, var, newub, force, cutoff, &tightened) );
1509  if( tightened )
1510  {
1511  SCIPdebugMsg(scip, "tightened upper bound of variable <%s>[%g,%g] to %g due to probing on <%s> with nlocks=(%d/%d)\n",
1512  SCIPvarGetName(var), oldlb, oldub, newub,
1515  (*nchgbds)++;
1516  }
1517  else if( *cutoff )
1518  {
1519  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible new lower bound of variable <%s> to %g\n",
1520  SCIPvarGetName(probingvar), SCIPvarGetName(var), newub);
1521  }
1522  }
1523  if( *cutoff )
1524  break;
1525  }
1526 
1527  /* below we add aggregations and implications between probingvar and var,
1528  * we don't want this if both variables are the same
1529  */
1530  if( var == probingvar )
1531  continue;
1532 
1533  /* check for aggregations and implications */
1534  if( fixedleft && fixedright &&
1535  SCIPisEQ(scip, leftproplbs[j], leftpropubs[j]) && SCIPisEQ(scip, rightproplbs[j], rightpropubs[j]) )
1536  {
1537  /* var is fixed whenever probingvar is fixed, i.e.,
1538  * var = leftproplbs[j] + (rightproplbs[j] - leftproplbs[j]) / (rightlb - leftub) * (probingvar - leftub)
1539  * -> both variables can be aggregated:
1540  * (rightlb - leftub) * (var - leftproplbs[j]) = (rightproplbs[j] - leftproplbs[j]) * (probingvar - leftub)
1541  * -> (rightlb - leftub) * var - (rightproplbs[j] - leftproplbs[j]) * probingvar = leftproplbs[j] * rightlb - rightproplbs[j] * leftub
1542  *
1543  * check for case where both variables are binary: leftub = 1, rightlb = 0
1544  * case leftproplbs[j] = 0, rightproplbs[j] = 1, i.e., var and probingvar are fixed to same value
1545  * -> aggregation is 1 * var - 1 * probingvar = 0 * 1 - 1 * 0 = 0 -> correct
1546  * case leftproplbs[j] = 1, rightproblbs[j] = 0, i.e., var and probingvar are fixed to opposite values
1547  * -> aggregation is 1 * var + 1 * probingvar = 1 * 1 - 0 * 0 = 0 -> correct
1548  */
1549  if( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING )
1550  {
1551  SCIP_Bool aggregated;
1552  SCIP_Bool redundant;
1553 
1554  SCIP_CALL( SCIPaggregateVars(scip, var, probingvar,
1555  rightlb - leftub, -(rightproplbs[j] - leftproplbs[j]), leftproplbs[j] * rightlb - rightproplbs[j] * leftub,
1556  cutoff, &redundant, &aggregated) );
1557 
1558  if( aggregated )
1559  {
1560  SCIPdebugMsg(scip, "aggregated variables %g<%s> - %g<%s> == %g, nlocks=(%d/%d)\n",
1561  rightlb - leftub, SCIPvarGetName(var),
1562  rightproplbs[j] - leftproplbs[j], SCIPvarGetName(probingvar),
1563  leftproplbs[j] * rightlb - rightproplbs[j] * leftub,
1566  (*naggrvars)++;
1567  }
1568  if( *cutoff )
1569  {
1570  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible aggregation: %g<%s> - %g<%s> == %g\n",
1571  SCIPvarGetName(probingvar), rightlb - leftub, SCIPvarGetName(var),
1572  rightproplbs[j] - leftproplbs[j], SCIPvarGetName(probingvar),
1573  leftproplbs[j] * rightlb - rightproplbs[j] * leftub);
1574  }
1575  }
1576  else if( probingvarisinteger && SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) == 0 )
1577  {
1578  /* if we are not in presolving, then we cannot do aggregations
1579  * but we can use variable bounds to code the same equality
1580  * var == ((leftproplbs[j] * rightlb - rightproplbs[j] * leftub) + (rightproplbs[j] - leftproplbs[j]) * probingvar) / (rightlb - leftub)
1581  */
1582  int nboundchanges;
1583 
1584  assert(!SCIPisEQ(scip, leftub, rightlb));
1585 
1586  SCIP_CALL( SCIPaddVarVlb(scip, var, probingvar, (rightproplbs[j] - leftproplbs[j]) / (rightlb - leftub), (leftproplbs[j] * rightlb - rightproplbs[j] * leftub) / (rightlb - leftub), cutoff, &nboundchanges) );
1587  (*nchgbds) += nboundchanges;
1588 
1589  if( *cutoff )
1590  {
1591  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible vlb: %g<%s> - %g<%s> == %g\n",
1592  SCIPvarGetName(probingvar), rightlb - leftub, SCIPvarGetName(var),
1593  rightproplbs[j] - leftproplbs[j], SCIPvarGetName(probingvar),
1594  leftproplbs[j] * rightlb - rightproplbs[j] * leftub);
1595  }
1596  else
1597  {
1598  SCIP_CALL( SCIPaddVarVub(scip, var, probingvar, (rightproplbs[j] - leftproplbs[j]) / (rightlb - leftub), (leftproplbs[j] * rightlb - rightproplbs[j] * leftub) / (rightlb - leftub), cutoff, &nboundchanges) );
1599  (*nchgbds) += nboundchanges;
1600 
1601  if( *cutoff )
1602  {
1603  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible vub: %g<%s> - %g<%s> == %g\n",
1604  SCIPvarGetName(probingvar), rightlb - leftub, SCIPvarGetName(var),
1605  rightproplbs[j] - leftproplbs[j], SCIPvarGetName(probingvar),
1606  leftproplbs[j] * rightlb - rightproplbs[j] * leftub);
1607  }
1608  }
1609  (*nimplications)++;
1610  }
1611  /* if probingvar is continuous and we are in solving stage, then we do nothing, but it's unlikely that we get
1612  * here (fixedleft && fixedright) with a continuous variable
1613  */
1614  }
1615  /* @todo: check if we can add variable lowerbounds/upperbounds on integer variables */
1616  /* can only add implications on binary variables which are globally valid */
1617  else if( probingvarisbinary && (SCIPgetStage(scip) != SCIP_STAGE_SOLVING || SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) == 0) )
1618  {
1619  /* implications can be added only for binary variables */
1620  int nboundchanges;
1621 
1622  /* since probing var is binary variable, probing should have fixed variable in both branches,
1623  * which is to 0.0 in the left branch and to 1.0 in the right branch */
1624  assert(fixedleft);
1625  assert(fixedright);
1626  assert(SCIPisZero(scip, leftub));
1627  assert(SCIPisEQ(scip, rightlb, 1.0));
1628 
1629  if( SCIPisEQ(scip, newlb, leftpropubs[j]) && (leftimplubs == NULL || leftimplubs[j] > leftpropubs[j]) )
1630  {
1631  /* var is fixed to lower bound whenever probingvar is fixed to 0.0
1632  * and implication is not already known
1633  * -> insert implication: probingvar == 0 => var <= leftpropubs[j]
1634  */
1635  /*SCIPdebugMsg(scip, "found implication <%s> == 0 => <%s> == %g\n",
1636  SCIPvarGetName(probingvar), SCIPvarGetName(var), leftpropubs[j]);*/
1637  SCIP_CALL( SCIPaddVarImplication(scip, probingvar, FALSE, var, SCIP_BOUNDTYPE_UPPER, leftpropubs[j],
1638  cutoff, &nboundchanges) );
1639  (*nimplications)++;
1640  (*nchgbds) += nboundchanges;
1641 
1642  if( *cutoff )
1643  {
1644  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 0 => <%s> == %g\n",
1645  SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), leftpropubs[j]);
1646  }
1647  }
1648  else if( SCIPisEQ(scip, newub, leftproplbs[j]) && (leftimpllbs == NULL || leftimpllbs[j] < leftproplbs[j]) )
1649  {
1650  /* var is fixed to upper bound whenever probingvar is fixed to 0.0
1651  * and implication is not already known
1652  * -> insert implication: probingvar == 0 => var >= leftproplbs[j]
1653  */
1654  /*SCIPdebugMsg(scip, "found implication <%s> == 0 => <%s> == %g\n",
1655  SCIPvarGetName(probingvar), SCIPvarGetName(var), leftproplbs[j]);*/
1656  SCIP_CALL( SCIPaddVarImplication(scip, probingvar, FALSE, var, SCIP_BOUNDTYPE_LOWER, leftproplbs[j],
1657  cutoff, &nboundchanges) );
1658  (*nimplications)++;
1659  (*nchgbds) += nboundchanges;
1660 
1661  if( *cutoff )
1662  {
1663  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 0 => <%s> == %g\n",
1664  SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), leftproplbs[j]);
1665  }
1666  }
1667  /* we can do an else here, since the case where var is fixed for both fixings of probingvar had been handled as aggregation */
1668  else if( SCIPisEQ(scip, newlb, rightpropubs[j]) && (rightimplubs == NULL || rightimplubs[j] > rightpropubs[j]) )
1669  {
1670  /* var is fixed to lower bound whenever probingvar is fixed to 1.0
1671  * and implication is not already known
1672  * -> insert implication: probingvar == 1 => var <= rightpropubs[j]
1673  */
1674  /*SCIPdebugMsg(scip, "found implication <%s> == 1 => <%s> == %g\n",
1675  SCIPvarGetName(probingvar), SCIPvarGetName(var), rightpropubs[j]);*/
1676  SCIP_CALL( SCIPaddVarImplication(scip, probingvar, TRUE, var, SCIP_BOUNDTYPE_UPPER, rightpropubs[j],
1677  cutoff, &nboundchanges) );
1678  (*nimplications)++;
1679  (*nchgbds) += nboundchanges;
1680 
1681  if( *cutoff )
1682  {
1683  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 1 => <%s> == %g\n",
1684  SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), rightpropubs[j]);
1685  }
1686  }
1687  else if( SCIPisEQ(scip, newub, rightproplbs[j]) && (rightimpllbs == NULL || rightimpllbs[j] < rightproplbs[j]) )
1688  {
1689  /* var is fixed to upper bound whenever probingvar is fixed to 1.0
1690  * and implication is not already known
1691  * -> insert implication: probingvar == 1 => var >= leftproplbs[j]
1692  */
1693  /*SCIPdebugMsg(scip, "found implication <%s> == 1 => <%s> == %g\n",
1694  SCIPvarGetName(probingvar), SCIPvarGetName(var), rightproplbs[j]);*/
1695  SCIP_CALL( SCIPaddVarImplication(scip, probingvar, TRUE, var, SCIP_BOUNDTYPE_LOWER, rightproplbs[j],
1696  cutoff, &nboundchanges) );
1697  (*nimplications)++;
1698  (*nchgbds) += nboundchanges;
1699 
1700  if( *cutoff )
1701  {
1702  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 1 => <%s> == %g\n",
1703  SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), rightproplbs[j]);
1704  }
1705  }
1706  else if( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY )
1707  {
1708  /* check for implications for lower or upper bounds (only store implications with bounds tightened at least by 0.5)
1709  * in case of binary variables, this should have been handled in the previous cases, since every boundchange also fixes the variable
1710  */
1711  if( leftpropubs[j] < newub - 0.5 && (leftimplubs == NULL || leftpropubs[j] < leftimplubs[j]) )
1712  {
1713  /* insert implication: probingvar == 0 => var <= leftpropubs[j] */
1714  /*SCIPdebugMsg(scip, "found implication <%s> == 0 => <%s>[%g,%g] <= %g\n",
1715  SCIPvarGetName(probingvar), SCIPvarGetName(var), newlb, newub, leftpropubs[j]);*/
1716  SCIP_CALL( SCIPaddVarImplication(scip, probingvar, FALSE, var, SCIP_BOUNDTYPE_UPPER, leftpropubs[j],
1717  cutoff, &nboundchanges) );
1718  (*nimplications)++;
1719  (*nchgbds) += nboundchanges;
1720 
1721  if( *cutoff )
1722  {
1723  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 0 => <%s> <= %g\n",
1724  SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), leftpropubs[j]);
1725  }
1726  }
1727  if( leftproplbs[j] > newlb + 0.5 && (leftimpllbs == NULL || leftproplbs[j] > leftimpllbs[j]) && !*cutoff )
1728  {
1729  /* insert implication: probingvar == 0 => var >= leftproplbs[j] */
1730  /*SCIPdebugMsg(scip, "found implication <%s> == 0 => <%s>[%g,%g] >= %g\n",
1731  SCIPvarGetName(probingvar), SCIPvarGetName(var), newlb, newub, leftproplbs[j]);*/
1732  SCIP_CALL( SCIPaddVarImplication(scip, probingvar, FALSE, var, SCIP_BOUNDTYPE_LOWER, leftproplbs[j],
1733  cutoff, &nboundchanges) );
1734  (*nimplications)++;
1735  (*nchgbds) += nboundchanges;
1736 
1737  if( *cutoff )
1738  {
1739  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 0 => <%s> >= %g\n",
1740  SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), leftproplbs[j]);
1741  }
1742  }
1743  if( rightpropubs[j] < newub - 0.5 && (rightimplubs == NULL || rightpropubs[j] < rightimplubs[j]) && !*cutoff )
1744  {
1745  /* insert implication: probingvar == 1 => var <= rightpropubs[j] */
1746  /*SCIPdebugMsg(scip, "found implication <%s> == 1 => <%s>[%g,%g] <= %g\n",
1747  SCIPvarGetName(probingvar), SCIPvarGetName(var), newlb, newub, rightpropubs[j]);*/
1748  SCIP_CALL( SCIPaddVarImplication(scip, probingvar, TRUE, var, SCIP_BOUNDTYPE_UPPER, rightpropubs[j],
1749  cutoff, &nboundchanges) );
1750  (*nimplications)++;
1751  (*nchgbds) += nboundchanges;
1752 
1753  if( *cutoff )
1754  {
1755  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 1 => <%s> <= %g\n",
1756  SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), rightpropubs[j]);
1757  }
1758  }
1759  if( rightproplbs[j] > newlb + 0.5 && (rightimpllbs == NULL || rightproplbs[j] > rightimpllbs[j]) && !*cutoff )
1760  {
1761  /* insert implication: probingvar == 1 => var >= rightproplbs[j] */
1762  /*SCIPdebugMsg(scip, "found implication <%s> == 1 => <%s>[%g,%g] >= %g\n",
1763  SCIPvarGetName(probingvar), SCIPvarGetName(var), newlb, newub, rightproplbs[j]);*/
1764  SCIP_CALL( SCIPaddVarImplication(scip, probingvar, TRUE, var, SCIP_BOUNDTYPE_LOWER, rightproplbs[j],
1765  cutoff, &nboundchanges) );
1766  (*nimplications)++;
1767  (*nchgbds) += nboundchanges;
1768 
1769  if( *cutoff )
1770  {
1771  SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 1 => <%s> <= %g\n",
1772  SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), rightproplbs[j]);
1773  }
1774  }
1775  }
1776  }
1777  }
1778 
1779  return SCIP_OKAY;
1780 }
SCIP_RETCODE SCIPsetPropPresol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPPRESOL((*proppresol)), int presolpriority, int presolmaxrounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_prop.c:270
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:386
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
#define DEFAULT_MAXSUMUSELESS
Definition: prop_probing.c:88
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2081
static SCIP_DECL_PROPEXITPRE(propExitpreProbing)
Definition: prop_probing.c:820
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:369
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5200
public methods for SCIP parameter handling
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3289
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:82
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
#define PROP_PRESOLTIMING
Definition: prop_probing.c:60
public methods for branch and bound tree
#define SCIPduplicateMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:67
#define SCIPfreeMemoryArrayNull(scip, ptr)
Definition: scip_mem.h:72
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:71
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17910
#define PROP_DESC
Definition: prop_probing.c:52
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3347
static long bound
static SCIP_DECL_PROPINITSOL(propInitsolProbing)
Definition: prop_probing.c:842
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17966
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:1245
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17431
#define MAXDNOM
Definition: prop_probing.c:64
void SCIPswapPointers(void **pointer1, void **pointer2)
Definition: misc.c:10291
#define FALSE
Definition: def.h:87
#define DEFAULT_MAXUSELESS
Definition: prop_probing.c:82
SCIP_RETCODE SCIPpropagateProbingImplications(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip_probing.c:677
SCIP_Real SCIPinfinity(SCIP *scip)
#define TRUE
Definition: def.h:86
#define SCIPdebug(x)
Definition: pub_message.h:84
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
enum SCIP_VerbLevel SCIP_VERBLEVEL
Definition: type_message.h:48
public methods for problem variables
#define PROP_FREQ
Definition: prop_probing.c:55
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5317
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
SCIP_Real SCIPselectSimpleValue(SCIP_Real lb, SCIP_Real ub, SCIP_Longint maxdnom)
Definition: misc.c:9719
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:292
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:6658
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7444
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
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:6717
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:69
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:74
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18262
SCIP_Real SCIPepsilon(SCIP *scip)
public methods for numerical tolerances
public methods for querying solving statistics
#define DEFAULT_MAXRUNS
Definition: prop_probing.c:77
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1066
public methods for the branch-and-bound tree
#define DEFAULT_MAXDEPTH
Definition: prop_probing.c:91
SCIP_Bool SCIPisLbBetter(SCIP *scip, SCIP_Real newlb, SCIP_Real oldlb, SCIP_Real oldub)
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7434
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17920
SCIP_RETCODE SCIPsetPropExitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITPRE((*propexitpre)))
Definition: scip_prop.c:254
static SCIP_DECL_PROPINIT(propInitProbing)
Definition: prop_probing.c:766
#define DEFAULT_PROPROUNDS
Definition: prop_probing.c:78
static SCIP_DECL_PROPEXIT(propExitProbing)
Definition: prop_probing.c:785
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:571
#define DEFAULT_RANDSEED
Definition: prop_probing.c:92
#define DEFAULT_MAXFIXINGS
Definition: prop_probing.c:79
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:6777
#define SCIPreallocMemoryArray(scip, ptr, newnum)
Definition: scip_mem.h:61
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:251
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17251
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:384
int SCIPgetNTotalVars(SCIP *scip)
Definition: scip_prob.c:2568
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
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:115
SCIP_RETCODE SCIPsetPropInit(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINIT((*propinit)))
Definition: scip_prop.c:174
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:84
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
int SCIPgetNImplVars(SCIP *scip)
Definition: scip_prob.c:2126
#define PROP_PRESOL_MAXROUNDS
Definition: prop_probing.c:61
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:661
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18188
#define MAX(x, y)
Definition: tclique_def.h:83
void SCIPenableVarHistory(SCIP *scip)
Definition: scip_var.c:8738
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:142
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8273
int SCIPgetNRuns(SCIP *scip)
#define DEFAULT_MAXTOTALUSELESS
Definition: prop_probing.c:85
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2036
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10025
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:88
public methods for the LP relaxation, rows and columns
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:932
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1991
#define PROP_PRESOL_PRIORITY
Definition: prop_probing.c:59
methods for sorting joint arrays of various types
public methods for branching rule plugins and branching
general public methods
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:303
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE aggregation(SCIP *scip, SCIP_MATRIX *matrix, SCIP_PRESOLDATA *presoldata, SCIP_VAR **vars, int colidx1, int colidx2, SCIP_Bool isimpliedfree, SCIP_Real weight1)
public methods for random numbers
static SCIP_DECL_PROPFREE(propFreeProbing)
Definition: prop_probing.c:746
public methods for the probing mode
probing propagator
static SCIP_RETCODE initPropdata(SCIP_PROPDATA *propdata)
Definition: prop_probing.c:136
public methods for message output
#define PROP_NAME
Definition: prop_probing.c:51
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1946
SCIP_RETCODE SCIPsetPropInitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITSOL((*propinitsol)))
Definition: scip_prop.c:206
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:8398
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1211
#define SCIP_Real
Definition: def.h:177
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:43
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:694
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:158
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
Definition: prop.c:780
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
Definition: prop.c:790
#define SCIP_Longint
Definition: def.h:162
public methods for propagator plugins
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17590
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17416
#define PROP_TIMING
Definition: prop_probing.c:53
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:17976
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:110
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:123
SCIPallocBlockMemory(scip, subsol))
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPsetPropInitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITPRE((*propinitpre)))
Definition: scip_prop.c:238
SCIP_RETCODE SCIPsetPropExit(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXIT((*propexit)))
Definition: scip_prop.c:190
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:336
#define PROP_DELAY
Definition: prop_probing.c:56
SCIP_Bool SCIPvarIsDeleted(SCIP_VAR *var)
Definition: var.c:17472
static SCIP_DECL_PROPINITPRE(propInitpreProbing)
Definition: prop_probing.c:805
SCIP_Real SCIPpropGetTime(SCIP_PROP *prop)
Definition: prop.c:1047
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
#define PROP_PRIORITY
Definition: prop_probing.c:54
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17580
public methods for propagators
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:119
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:105
memory allocation routines