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