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