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  continue; /* don't try downwards direction, because the variable is already fixed */
506  }
507 
508  /* ignore variables, that were fixed, aggregated, or deleted in prior probings
509  * (propagators in one-probe might have found global fixings but did not trigger the localcutoff)
510  */
511  if( !SCIPvarIsActive(vars[i]) || SCIPvarIsDeleted(vars[i])
512  || SCIPvarGetLbLocal(vars[i]) > 0.5 || SCIPvarGetUbLocal(vars[i]) < 0.5 )
513  continue;
514  }
515 
516  /* determine whether zero probing should happen */
517  probingzero = TRUE;
518  if( SCIPvarGetNLocksDown(vars[i]) == 0 )
519  probingzero = FALSE;
520 
521  if( probingzero )
522  {
523  /* apply probing for fixing the variable to zero */
524  SCIP_CALL( SCIPapplyProbingVar(scip, vars, nvars, i, SCIP_BOUNDTYPE_UPPER, 0.0, propdata->proprounds,
525  zeroimpllbs, zeroimplubs, zeroproplbs, zeropropubs, &localcutoff) );
526 
527  if( localcutoff )
528  {
529  SCIP_Bool fixed;
530 
531  if( SCIPgetStage(scip) != SCIP_STAGE_SOLVING || SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) == 0 )
532  {
533  /* the variable can be fixed to TRUE */
534  SCIP_CALL( SCIPfixVar(scip, vars[i], 1.0, cutoff, &fixed) );
535  }
536  else
537  {
538  SCIP_CALL( SCIPtightenVarLb(scip, vars[i], 1.0, TRUE, cutoff, &fixed) );
539  }
540 
541  if( fixed )
542  {
543  SCIPdebugMessage("fixed probing variable <%s> to 1.0, nlocks=(%d/%d)\n",
544  SCIPvarGetName(vars[i]), SCIPvarGetNLocksDown(vars[i]), SCIPvarGetNLocksUp(vars[i]));
545  (*nfixedvars)++;
546  propdata->nfixings++;
547  propdata->nuseless = 0;
548  propdata->ntotaluseless = 0;
549  }
550  continue; /* don't analyze probing deductions, because the variable is already fixed */
551  }
552  }
553 
554  /* not have to check deductions if only one probing direction has been checked */
555  if( !probingzero || !probingone )
556  continue;
557 
558  assert(propdata->noldtotalvars > SCIPvarGetIndex(vars[i]));
559 
560  /* count number of probings on each variable */
561  propdata->nprobed[SCIPvarGetIndex(vars[i])] += 1;
562 
563  /* analyze probing deductions */
564  localnfixedvars = 0;
565  localnaggrvars = 0;
566  localnimplications = 0;
567  localnchgbds = 0;
568  SCIP_CALL( SCIPanalyzeDeductionsProbing(scip, vars[i], 0.0, 1.0,
569  nvars, vars, zeroimpllbs, zeroimplubs, zeroproplbs, zeropropubs, oneimpllbs, oneimplubs, oneproplbs, onepropubs,
570  &localnfixedvars, &localnaggrvars, &localnimplications, &localnchgbds, cutoff) );
571 
572  *nfixedvars += localnfixedvars;
573  *naggrvars += localnaggrvars;
574  *nchgbds += localnchgbds;
575  propdata->nfixings += localnfixedvars;
576  propdata->naggregations += localnaggrvars;
577  propdata->nbdchgs += localnchgbds;
578  propdata->nimplications += localnimplications;
579 
580  if( localnfixedvars > 0 || localnaggrvars > 0 )
581  {
582  SCIPdebugMessage("probing on <%s> led to %d fixed and %d aggregated variables\n", SCIPvarGetName(vars[i]), localnfixedvars, localnaggrvars);
583  propdata->nuseless = 0;
584  propdata->ntotaluseless = 0;
585  }
586  if( localnimplications > 0 || localnchgbds > 0 )
587  propdata->ntotaluseless = 0;
588  }
589 
590  looped = TRUE;
591 
592  /* check if we reached the end of all binary variables but did not stop, so we start from the beginning */
593  if( i == nbinvars && !(*cutoff) && !(*delay) && !aborted )
594  {
595  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
596  " (%.1fs) probing cycle finished: starting next cycle\n", SCIPgetSolvingTime(scip));
597  i = 0;
598 
599  if( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING )
600  {
601  int nnewvars;
602  int nnewbinvars;
603  int nnewintvars;
604  int nnewimplvars;
605  int lastidx;
606  int v;
607 
608  assert(vars == propdata->sortedvars);
609  assert(nbinvars == propdata->nsortedbinvars);
610 
611  /* release old variables and free memory */
612  for( v = propdata->nsortedvars - 1; v >= 0; --v )
613  {
614  SCIP_CALL( SCIPreleaseVar(scip, &propdata->sortedvars[v]) );
615  }
616  SCIPfreeMemoryArray(scip, &propdata->sortedvars);
617  propdata->nsortedvars = 0;
618  propdata->nsortedbinvars = 0;
619 
620  /* get new variables */
621  nnewvars = SCIPgetNVars(scip);
622  SCIP_CALL( SCIPduplicateMemoryArray(scip, &(propdata->sortedvars), SCIPgetVars(scip), nnewvars) );
623  propdata->nsortedvars = nnewvars;
624 
625  nnewbinvars = SCIPgetNBinVars(scip);
626  nnewintvars = SCIPgetNIntVars(scip);
627  nnewimplvars = SCIPgetNImplVars(scip);
628 
629  /* determine implicit binary variables */
630  lastidx = nnewbinvars + nnewintvars + nnewimplvars;
631  for( v = nnewbinvars; v < lastidx; ++v )
632  {
633  if( SCIPvarIsBinary(propdata->sortedvars[v]) )
634  {
635  SCIPswapPointers((void**) &(propdata->sortedvars[nnewbinvars]), (void**) &(propdata->sortedvars[v]));
636  ++nnewbinvars;
637  }
638  }
639  propdata->nsortedbinvars = nnewbinvars;
640 
641  nbinvars = nnewbinvars;
642  vars = propdata->sortedvars;
643  nvars = propdata->nsortedvars;
644 
645  SCIP_CALL( SCIPreallocBufferArray(scip, &zeroimpllbs, nvars) );
646  SCIP_CALL( SCIPreallocBufferArray(scip, &zeroimplubs, nvars) );
647  SCIP_CALL( SCIPreallocBufferArray(scip, &zeroproplbs, nvars) );
648  SCIP_CALL( SCIPreallocBufferArray(scip, &zeropropubs, nvars) );
649  SCIP_CALL( SCIPreallocBufferArray(scip, &oneimpllbs, nvars) );
650  SCIP_CALL( SCIPreallocBufferArray(scip, &oneimplubs, nvars) );
651  SCIP_CALL( SCIPreallocBufferArray(scip, &oneproplbs, nvars) );
652  SCIP_CALL( SCIPreallocBufferArray(scip, &onepropubs, nvars) );
653 
654  /* correct oldstartidx which is used for early termination */
655  if( oldstartidx >= nbinvars )
656  oldstartidx = nbinvars - 1;
657 
658  /* capture variables to make sure, the variables are not deleted */
659  for( v = propdata->nsortedvars - 1; v >= 0; --v )
660  {
661  SCIP_CALL( SCIPcaptureVar(scip, propdata->sortedvars[v]) );
662  }
663 
664  if( nnewbinvars == 0 )
665  {
666  *startidx = 0;
667  propdata->lastsortstartidx = -1;
668  propdata->nuseless = 0;
669  propdata->ntotaluseless = 0;
670 
671  goto TERMINATE;
672  }
673 
674  /* resorting here might lead to probing a second time on the same variable */
675  SCIP_CALL( sortVariables(scip, propdata, propdata->sortedvars, propdata->nsortedbinvars, 0) );
676  propdata->lastsortstartidx = 0;
677  }
678  }
679 
680  }
681  while( i == 0 && !(*cutoff) && !(*delay) && !aborted );
682 
683  *startidx = i;
684 
685  TERMINATE:
686  /* free temporary memory */
687  SCIPfreeBufferArray(scip, &onepropubs);
688  SCIPfreeBufferArray(scip, &oneproplbs);
689  SCIPfreeBufferArray(scip, &oneimplubs);
690  SCIPfreeBufferArray(scip, &oneimpllbs);
691  SCIPfreeBufferArray(scip, &zeropropubs);
692  SCIPfreeBufferArray(scip, &zeroproplbs);
693  SCIPfreeBufferArray(scip, &zeroimplubs);
694  SCIPfreeBufferArray(scip, &zeroimpllbs);
695 
696  return SCIP_OKAY;
697 }
698 
699 
700 /*
701  * Callback methods of propagator
702  */
703 
704 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
705 static
706 SCIP_DECL_PROPCOPY(propCopyProbing)
707 { /*lint --e{715}*/
708  assert(scip != NULL);
709  assert(prop != NULL);
710  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
711 
712  /* call inclusion method for propagator */
713  SCIP_CALL( SCIPincludePropProbing(scip) );
714 
715  return SCIP_OKAY;
716 }
717 
718 
719 /** destructor of propagator to free user data (called when SCIP is exiting) */
720 static
721 SCIP_DECL_PROPFREE(propFreeProbing)
722 { /*lint --e{715}*/
723  SCIP_PROPDATA* propdata;
724 
725  /* free propagator data */
726  propdata = SCIPpropGetData(prop);
727  assert(propdata != NULL);
728  assert(propdata->sortedvars == NULL);
729  assert(propdata->nsortedvars == 0);
730  assert(propdata->nsortedbinvars == 0);
731 
732  SCIPfreeMemory(scip, &propdata);
733  SCIPpropSetData(prop, NULL);
734 
735  return SCIP_OKAY;
736 }
737 
738 
739 /** initialization method of propagator (called after problem was transformed) */
740 static
741 SCIP_DECL_PROPINIT(propInitProbing)
742 { /*lint --e{715}*/
743  SCIP_PROPDATA* propdata;
744 
745  propdata = SCIPpropGetData(prop);
746  assert(propdata != NULL);
747 
748  initPropdata(propdata);
749 
750  return SCIP_OKAY;
751 }
752 
753 
754 /** deinitialization method of propagator (called before transformed problem is freed) */
755 static
756 SCIP_DECL_PROPEXIT(propExitProbing)
757 { /*lint --e{715}*/
758  SCIP_PROPDATA* propdata;
759 
760  propdata = SCIPpropGetData(prop);
761  assert(propdata != NULL);
762 
763  SCIP_CALL( freeSortedvars(scip, propdata) );
764  assert(propdata->sortedvars == NULL);
765  assert(propdata->nsortedvars == 0);
766  assert(propdata->nsortedbinvars == 0);
767 
768 
769  return SCIP_OKAY;
770 }
771 
772 /** presolving initialization method of propagator (called when presolving is about to begin) */
773 static
774 SCIP_DECL_PROPINITPRE(propInitpreProbing)
775 { /*lint --e{715}*/
776  SCIP_PROPDATA* propdata;
777 
778  propdata = SCIPpropGetData(prop);
779  assert(propdata != NULL);
780 
781  propdata->lastnode = -2;
782 
783  return SCIP_OKAY;
784 }
785 
786 
787 /** presolving deinitialization method of propagator (called after presolving has been finished) */
788 static
789 SCIP_DECL_PROPEXITPRE(propExitpreProbing)
790 { /*lint --e{715}*/
791  SCIP_PROPDATA* propdata;
792 
793  propdata = SCIPpropGetData(prop);
794  assert(propdata != NULL);
795 
796  /* delete the vars array, if the maximal number of runs are exceeded */
797  if( propdata->maxruns >= 0 && SCIPgetNRuns(scip) >= propdata->maxruns )
798  {
799  SCIP_CALL( freeSortedvars(scip, propdata) );
800  assert(propdata->sortedvars == NULL);
801  assert(propdata->nsortedvars == 0);
802  assert(propdata->nsortedbinvars == 0);
803  }
804 
805  return SCIP_OKAY;
806 }
807 
808 
809 /** solving process initialization method of propagator (called when branch and bound process is about to begin) */
810 static
811 SCIP_DECL_PROPINITSOL(propInitsolProbing)
812 {
813  /*lint --e{715}*/
814  SCIP_PROPDATA* propdata;
815 
816  propdata = SCIPpropGetData(prop);
817  assert(propdata != NULL);
818 
819  /* reset all propdata elements for stopping propagation earlier */
820  propdata->nuseless = 0;
821  propdata->ntotaluseless = 0;
822  propdata->nsumuseless = 0;
823 #if 0
824  propdata->nfixings = 0;
825  propdata->naggregations = 0;
826  propdata->nimplications = 0;
827  propdata->nbdchgs = 0;
828 #endif
829 
830  return SCIP_OKAY;
831 }
832 
833 
834 /** presolve method of propagator */
835 static
836 SCIP_DECL_PROPPRESOL(propPresolProbing)
837 { /*lint --e{715}*/
838  SCIP_PROPDATA* propdata;
839  int nvars;
840  int nbinvars;
841  int nintvars;
842  int nimplvars;
843  int oldnfixedvars;
844  int oldnaggrvars;
845  int oldnchgbds;
846  int oldnimplications;
847  int ntotalvars;
848  SCIP_Bool delay;
849  SCIP_Bool cutoff;
850 
851  assert(result != NULL);
852 
853  *result = SCIP_DIDNOTRUN;
854 
855  nbinvars = SCIPgetNBinVars(scip);
856  nintvars = SCIPgetNIntVars(scip);
857  nimplvars = SCIPgetNImplVars(scip);
858 
859  /* if we have no binary variable anymore, we stop probing */
860  if( nbinvars + nintvars + nimplvars == 0 )
861  return SCIP_OKAY;
862 
863  /* get propagator data */
864  propdata = SCIPpropGetData(prop);
865  assert(propdata != NULL);
866 
867  /* check, if probing should be applied in the current run */
868  if( propdata->maxruns >= 0 && SCIPgetNRuns(scip) > propdata->maxruns )
869  return SCIP_OKAY;
870 
871  /* if no domains changed since the last call, we don't need to probe */
872  if( propdata->lastnode == -1 && nnewfixedvars == 0 && nnewaggrvars == 0 && nnewchgbds == 0 && nnewholes == 0 )
873  return SCIP_OKAY;
874 
875  SCIPdebugMessage("executing probing (used %.1f sec)\n", SCIPpropGetTime(prop));
876 
877  *result = SCIP_DIDNOTFIND;
878 
879  /* allow some additional probings */
880  propdata->nuseless -= propdata->nuseless/10;
881  propdata->ntotaluseless -= propdata->ntotaluseless/10;
882 
883  /* get variable data */
884  if( propdata->sortedvars == NULL )
885  {
886  int lastidx;
887  int v;
888 
889  assert(propdata->startidx == 0);
890 
891  nvars = SCIPgetNVars(scip);
892 
893  SCIP_CALL( SCIPduplicateMemoryArray(scip, &(propdata->sortedvars), SCIPgetVars(scip), nvars) );
894  propdata->nsortedvars = nvars;
895 
896  /* determine implicit binary variables */
897  lastidx = nbinvars + nintvars + nimplvars;
898  for( v = nbinvars; v < lastidx; ++v )
899  {
900  if( SCIPvarIsBinary(propdata->sortedvars[v]) )
901  {
902  SCIPswapPointers((void**) &(propdata->sortedvars[nbinvars]), (void**) &(propdata->sortedvars[v]));
903  ++nbinvars;
904  }
905  }
906  propdata->nsortedbinvars = nbinvars;
907 
908  /* capture variables to make sure, the variables are not deleted */
909  for( v = propdata->nsortedvars - 1; v >= 0 ; --v )
910  {
911  SCIP_CALL( SCIPcaptureVar(scip, propdata->sortedvars[v]) );
912  }
913  }
914 
915  if( propdata->nsortedbinvars == 0 )
916  return SCIP_OKAY;
917 
918  /* number of total variables is not decreasing, and we can identify every variable by their index, so allocate
919  * enough space
920  */
921  ntotalvars = SCIPgetNTotalVars(scip);
922  if( propdata->noldtotalvars < ntotalvars )
923  {
924  SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->nprobed, ntotalvars) );
925  BMSclearMemoryArray(&(propdata->nprobed[propdata->noldtotalvars]), ntotalvars - propdata->noldtotalvars); /*lint !e866*/
926  propdata->noldtotalvars = ntotalvars;
927  }
928 
929  propdata->lastnode = -1;
930 
931  /* sort the binary variables by number of rounding locks, if at least 100 variables were probed since last sort */
932  if( propdata->lastsortstartidx < 0 || propdata->startidx - propdata->lastsortstartidx >= 100 )
933  {
934  SCIP_CALL( sortVariables(scip, propdata, propdata->sortedvars, propdata->nsortedbinvars, propdata->startidx) );
935  propdata->lastsortstartidx = propdata->startidx;
936  }
937 
938  oldnfixedvars = *nfixedvars;
939  oldnaggrvars = *naggrvars;
940  oldnchgbds = *nchgbds;
941  oldnimplications = propdata->nimplications;
942 
943  /* start probing on variables */
944  SCIP_CALL( applyProbing(scip, propdata, propdata->sortedvars, propdata->nsortedvars, propdata->nsortedbinvars, &(propdata->startidx), nfixedvars, naggrvars, nchgbds, oldnfixedvars, oldnaggrvars, &delay, &cutoff) );
945 
946  /* adjust result code */
947  if( cutoff )
948  *result = SCIP_CUTOFF;
949  else if( delay )
950  {
951  *result = SCIP_DELAYED;
952  /* probing was interrupted because it reached the maximal fixings parameter, so we want to rerun it at the next call */
953  propdata->lastnode = -2;
954  }
955  else if( *nfixedvars > oldnfixedvars || *naggrvars > oldnaggrvars || *nchgbds > oldnchgbds
956  || propdata->nimplications > oldnimplications )
957  *result = SCIP_SUCCESS;
958 
959  return SCIP_OKAY;
960 }
961 
962 
963 /** execution method of propagator */
964 static
965 SCIP_DECL_PROPEXEC(propExecProbing)
966 { /*lint --e{715}*/
967  SCIP_PROPDATA* propdata;
968  SCIP_VAR** vars;
969  SCIP_VAR** binvars;
970  int nvars;
971  int nbinvars;
972  int i;
973  int nfixedvars;
974  int naggrvars;
975  int nchgbds;
976  int oldnfixedvars;
977  int oldnaggrvars;
978  int oldnchgbds;
979  int oldnimplications;
980  int startidx;
981  int ntotalvars;
982  SCIP_Bool delay;
983  SCIP_Bool cutoff;
984 
985  assert(result != NULL);
986 
987  *result = SCIP_DIDNOTRUN;
988 
989  /* avoid recursive infinity loop */
990  if( SCIPinProbing(scip) )
991  return SCIP_OKAY;
992 
993  /* only call propagation on branching candidates, if an optimal LP solution is at hand */
994  if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
995  return SCIP_OKAY;
996 
997  /* get propagator data */
998  propdata = SCIPpropGetData(prop);
999  assert(propdata != NULL);
1000 
1001  /* if already called stop */
1002  if( propdata->lastnode == SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) )
1003  return SCIP_OKAY;
1004 
1005  /* if maximal depth for propagation is reached, stop */
1006  if( propdata->maxdepth >= 0 && propdata->maxdepth < SCIPgetDepth(scip) )
1007  return SCIP_OKAY;
1008 
1009  propdata->lastnode = SCIPnodeGetNumber(SCIPgetCurrentNode(scip));
1010 
1011  /* get (number of) fractional variables that should be integral */
1012  /* todo check if integrating fractional implicit integer variables is beneficial for probing */
1013  SCIP_CALL( SCIPgetLPBranchCands(scip, &vars, NULL, NULL, &nvars, NULL, NULL) );
1014  nbinvars = 0;
1015 
1016  /* alloc array for fractional binary variables */
1017  SCIP_CALL( SCIPallocBufferArray(scip, &binvars, nvars) );
1018 
1019  /* copy binary variables to array binvars */
1020  for( i = 0; i < nvars; ++i )
1021  {
1022  SCIP_VAR* var;
1023  var = vars[i];
1024 
1025  assert(var != NULL);
1026  if( SCIPvarIsBinary(var) )
1027  {
1028  assert(SCIPvarGetLbLocal(var) < 0.5);
1029  assert(SCIPvarGetUbLocal(var) > 0.5);
1030 
1031  binvars[nbinvars] = var;
1032  ++nbinvars;
1033  }
1034  }
1035  SCIPdebugMessage("problem <%s> node %"SCIP_LONGINT_FORMAT" probing propagation found %d of %d possible probing candidates\n", SCIPgetProbName(scip), SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), nbinvars, nvars);
1036 
1037  if( nbinvars == 0 )
1038  {
1039  *result = SCIP_DIDNOTFIND;
1040  goto TERMINATE;
1041  }
1042 
1043  /* number of total variables is not decreasing, and we can identify every variable by their index, so allocate
1044  * enough space
1045  */
1046  ntotalvars = SCIPgetNTotalVars(scip);
1047  if( propdata->noldtotalvars < ntotalvars )
1048  {
1049  SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->nprobed, ntotalvars) );
1050  BMSclearMemoryArray(&(propdata->nprobed[propdata->noldtotalvars]), ntotalvars - propdata->noldtotalvars); /*lint !e866*/
1051  propdata->noldtotalvars = ntotalvars;
1052  }
1053 
1054  /* sort binary variables */
1055  SCIP_CALL( sortVariables(scip, propdata, binvars, nbinvars, 0) );
1056 
1057  oldnfixedvars = 0;
1058  oldnaggrvars = 0;
1059  oldnchgbds = 0;
1060  nfixedvars = 0;
1061  naggrvars = 0;
1062  nchgbds = 0;
1063  startidx = 0;
1064  oldnimplications = propdata->nimplications;
1065 
1066  /* start probing on found variables */
1067  SCIP_CALL( applyProbing(scip, propdata, binvars, nbinvars, nbinvars, &startidx, &nfixedvars, &naggrvars, &nchgbds, oldnfixedvars, oldnaggrvars, &delay, &cutoff) );
1068  SCIPdebugMessage("probing propagation found %d fixings, %d aggregation, %d nchgbds, and %d implications\n", nfixedvars, naggrvars, nchgbds, (propdata->nimplications) - oldnimplications);
1069 
1070  if( delay )
1071  {
1072  /* probing was interrupted because it reached the maximal fixings parameter, so we want to rerun it at the next call */
1073  propdata->lastnode = -2;
1074  }
1075 
1076  /* adjust result code */
1077  if( cutoff )
1078  *result = SCIP_CUTOFF;
1079  else if( nfixedvars > oldnfixedvars || naggrvars > oldnaggrvars || nchgbds > oldnchgbds )
1080  *result = SCIP_REDUCEDDOM;
1081 
1082  TERMINATE:
1083  SCIPfreeBufferArray(scip, &binvars);
1084 
1085  return SCIP_OKAY;
1086 }
1087 
1088 
1089 /** propagation conflict resolving method of propagator */
1090 static
1091 SCIP_DECL_PROPRESPROP(propRespropProbing)
1092 { /*lint --e{715}*/
1093  *result = SCIP_DIDNOTRUN;
1094 
1095  return SCIP_OKAY;
1096 }
1097 
1098 
1099 /*
1100  * propagator specific interface methods
1101  */
1102 
1103 /** creates the probing propagator and includes it in SCIP */
1104 SCIP_RETCODE SCIPincludePropProbing(
1105  SCIP* scip /**< SCIP data structure */
1106  )
1107 {
1108  SCIP_PROPDATA* propdata;
1109  SCIP_PROP* prop;
1110 
1111  /* create probing propagator data */
1112  SCIP_CALL( SCIPallocMemory(scip, &propdata) );
1113  initPropdata(propdata);
1114 
1115  /* include propagator */
1116  SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING,
1117  propExecProbing, propdata) );
1118 
1119  assert(prop != NULL);
1120 
1121  /* set optional callbacks via setter functions */
1122  SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyProbing) );
1123  SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeProbing) );
1124  SCIP_CALL( SCIPsetPropInit(scip, prop, propInitProbing) );
1125  SCIP_CALL( SCIPsetPropExit(scip, prop, propExitProbing) );
1126  SCIP_CALL( SCIPsetPropInitsol(scip, prop, propInitsolProbing) );
1127  SCIP_CALL( SCIPsetPropInitpre(scip, prop, propInitpreProbing) );
1128  SCIP_CALL( SCIPsetPropExitpre(scip, prop, propExitpreProbing) );
1129  SCIP_CALL( SCIPsetPropPresol(scip, prop, propPresolProbing, PROP_PRESOL_PRIORITY, PROP_PRESOL_MAXROUNDS,
1130  PROP_PRESOL_DELAY) );
1131  SCIP_CALL( SCIPsetPropResprop(scip, prop, propRespropProbing) );
1132 
1133  /* add probing propagator parameters */
1134  SCIP_CALL( SCIPaddIntParam(scip,
1135  "propagating/"PROP_NAME"/maxruns",
1136  "maximal number of runs, probing participates in (-1: no limit)",
1137  &propdata->maxruns, FALSE, DEFAULT_MAXRUNS, -1, INT_MAX, NULL, NULL) );
1138  SCIP_CALL( SCIPaddIntParam(scip,
1139  "propagating/"PROP_NAME"/proprounds",
1140  "maximal number of propagation rounds in probing subproblems (-1: no limit, 0: auto)",
1141  &propdata->proprounds, TRUE, DEFAULT_PROPROUNDS, -1, INT_MAX, NULL, NULL) );
1142  SCIP_CALL( SCIPaddIntParam(scip,
1143  "propagating/"PROP_NAME"/maxfixings",
1144  "maximal number of fixings found, until probing is interrupted (0: don't iterrupt)",
1145  &propdata->maxfixings, TRUE, DEFAULT_MAXFIXINGS, 0, INT_MAX, NULL, NULL) );
1146  SCIP_CALL( SCIPaddIntParam(scip,
1147  "propagating/"PROP_NAME"/maxuseless",
1148  "maximal number of successive probings without fixings, until probing is aborted (0: don't abort)",
1149  &propdata->maxuseless, TRUE, DEFAULT_MAXUSELESS, 0, INT_MAX, NULL, NULL) );
1150  SCIP_CALL( SCIPaddIntParam(scip,
1151  "propagating/"PROP_NAME"/maxtotaluseless",
1152  "maximal number of successive probings without fixings, bound changes, and implications, until probing is aborted (0: don't abort)",
1153  &propdata->maxtotaluseless, TRUE, DEFAULT_MAXTOTALUSELESS, 0, INT_MAX, NULL, NULL) );
1154  SCIP_CALL( SCIPaddIntParam(scip,
1155  "propagating/"PROP_NAME"/maxsumuseless",
1156  "maximal number of probings without fixings, until probing is aborted (0: don't abort)",
1157  &propdata->maxsumuseless, TRUE, DEFAULT_MAXSUMUSELESS, 0, INT_MAX, NULL, NULL) );
1158  SCIP_CALL( SCIPaddIntParam(scip,
1159  "propagating/"PROP_NAME"/maxdepth",
1160  "maximal depth until propagation is executed(-1: no limit)",
1161  &propdata->maxdepth, TRUE, DEFAULT_MAXDEPTH, -1, INT_MAX, NULL, NULL) );
1162 
1163  return SCIP_OKAY;
1164 }
1165 
1166 
1167 /** applies and evaluates probing of a single variable in the given direction and bound */
1168 SCIP_RETCODE SCIPapplyProbingVar(
1169  SCIP* scip, /**< SCIP data structure */
1170  SCIP_VAR** vars, /**< problem variables */
1171  int nvars, /**< number of problem variables */
1172  int probingpos, /**< variable number to apply probing on */
1173  SCIP_BOUNDTYPE boundtype, /**< which bound should be changed */
1174  SCIP_Real bound, /**< which bound should be set */
1175  int maxproprounds, /**< maximal number of propagation rounds (-1: no limit, 0: parameter settings) */
1176  SCIP_Real* impllbs, /**< array to store lower bounds after applying implications and cliques */
1177  SCIP_Real* implubs, /**< array to store upper bounds after applying implications and cliques */
1178  SCIP_Real* proplbs, /**< array to store lower bounds after full propagation */
1179  SCIP_Real* propubs, /**< array to store upper bounds after full propagation */
1180  SCIP_Bool* cutoff /**< pointer to store whether the probing direction is infeasible */
1181  )
1182 {
1183  assert(impllbs != NULL);
1184  assert(implubs != NULL);
1185  assert(proplbs != NULL);
1186  assert(propubs != NULL);
1187  assert(cutoff != NULL);
1188  assert(0 <= probingpos && probingpos < nvars);
1189  assert(SCIPisGE(scip, bound, SCIPvarGetLbLocal(vars[probingpos])));
1190  assert(SCIPisLE(scip, bound, SCIPvarGetUbLocal(vars[probingpos])));
1191 
1192  SCIPdebugMessage("applying probing on variable <%s> %s %g (nlocks=%d/%d, impls=%d/%d, clqs=%d/%d)\n",
1193  SCIPvarGetName(vars[probingpos]), boundtype == SCIP_BOUNDTYPE_UPPER ? "<=" : ">=", bound,
1194  SCIPvarGetNLocksDown(vars[probingpos]), SCIPvarGetNLocksUp(vars[probingpos]),
1195  SCIPvarGetNImpls(vars[probingpos], FALSE), SCIPvarGetNImpls(vars[probingpos], TRUE),
1196  SCIPvarGetNCliques(vars[probingpos], FALSE), SCIPvarGetNCliques(vars[probingpos], TRUE));
1197 
1198  /* in debug mode we assert above that this trivial infeasibility does not occur (for performance reasons), but in
1199  * optimized mode we return safely
1200  */
1201  if( SCIPisLT(scip, bound, SCIPvarGetLbLocal(vars[probingpos]))
1202  || SCIPisGT(scip, bound, SCIPvarGetUbLocal(vars[probingpos])) )
1203  {
1204  SCIPdebugMessage(" -> trivial infeasibility detected\n");
1205  *cutoff = TRUE;
1206  return SCIP_OKAY;
1207  }
1208 
1209  /* start probing mode */
1210  SCIP_CALL( SCIPstartProbing(scip) );
1211 
1212  /* enables collection of variable statistics during probing */
1213  SCIPenableVarHistory(scip);
1214 
1215  /* fix variable */
1216  if( boundtype == SCIP_BOUNDTYPE_UPPER )
1217  {
1218  SCIP_CALL( SCIPchgVarUbProbing(scip, vars[probingpos], bound) );
1219  }
1220  else
1221  {
1222  assert(boundtype == SCIP_BOUNDTYPE_LOWER);
1223  SCIP_CALL( SCIPchgVarLbProbing(scip, vars[probingpos], bound) );
1224  }
1225 
1226  /* @todo it might pay off to catch the bounds-tightened event on all variables and then only get the implied and
1227  * propagated bounds on those variables which where really changed on propagation
1228  */
1229 
1230  /* apply propagation of implication graph and clique table */
1231  SCIP_CALL( SCIPpropagateProbingImplications(scip, cutoff) );
1232  if( !(*cutoff) )
1233  {
1234  int i;
1235 
1236  for( i = 0; i < nvars; ++i )
1237  {
1238  impllbs[i] = SCIPvarGetLbLocal(vars[i]);
1239  implubs[i] = SCIPvarGetUbLocal(vars[i]);
1240  }
1241  }
1242 
1243  /* apply propagation */
1244  if( !(*cutoff) )
1245  {
1246  SCIP_CALL( SCIPpropagateProbing(scip, maxproprounds, cutoff, NULL) );
1247  }
1248 
1249  /* evaluate propagation */
1250  if( !(*cutoff) )
1251  {
1252  int i;
1253 
1254  for( i = 0; i < nvars; ++i )
1255  {
1256  proplbs[i] = SCIPvarGetLbLocal(vars[i]);
1257  propubs[i] = SCIPvarGetUbLocal(vars[i]);
1258 #if 0
1259 #ifdef SCIP_DEBUG
1260  if( SCIPisGT(scip, proplbs[i], SCIPvarGetLbGlobal(vars[i])) )
1261  {
1262  SCIPdebugMessage(" -> <%s>[%g,%g] >= %g\n", SCIPvarGetName(vars[i]),
1263  SCIPvarGetLbGlobal(vars[i]), SCIPvarGetUbGlobal(vars[i]), proplbs[i]);
1264  }
1265  if( SCIPisLT(scip, propubs[i], SCIPvarGetUbGlobal(vars[i])) )
1266  {
1267  SCIPdebugMessage(" -> <%s>[%g,%g] <= %g\n", SCIPvarGetName(vars[i]),
1268  SCIPvarGetLbGlobal(vars[i]), SCIPvarGetUbGlobal(vars[i]), propubs[i]);
1269  }
1270 #endif
1271 #endif
1272  }
1273  }
1274 
1275  /* exit probing mode */
1276  SCIP_CALL( SCIPendProbing(scip) );
1277 
1278  return SCIP_OKAY;
1279 }
1280 
1281 /** analyses boundchanges resulting from probing on a variable and performs deduced fixations, aggregations, and domain tightenings
1282  * Given a variable probingvar with domain [l,u] and bound tightening results from reducing the domain
1283  * once to [l,leftub] and once to [rightlb,u], the method computes and applies resulting variable fixations, aggregations,
1284  * implications, and bound changes. Variable probingvar does not need to be binary.
1285  * The whole domain of probingvar need to be covered by the left and right branches, i.e.,
1286  * we assume leftub >= rightlb for continuous variables or floor(leftub) >= ceil(rightlb)-1 for discrete variables.
1287  * Bounds after applying implications and cliques do not need to be provided, but if they are omitted and probingvar is a binary variable,
1288  * then already existing implications may be added.
1289  */
1290 SCIP_RETCODE SCIPanalyzeDeductionsProbing(
1291  SCIP* scip, /**< SCIP data structure */
1292  SCIP_VAR* probingvar, /**< the probing variable */
1293  SCIP_Real leftub, /**< upper bound of probing variable in left branch */
1294  SCIP_Real rightlb, /**< lower bound of probing variable in right branch */
1295  int nvars, /**< number of variables which bound changes should be analyzed */
1296  SCIP_VAR** vars, /**< variables which bound changes should be analyzed */
1297  SCIP_Real* leftimpllbs, /**< lower bounds after applying implications and cliques in left branch, or NULL */
1298  SCIP_Real* leftimplubs, /**< upper bounds after applying implications and cliques in left branch, or NULL */
1299  SCIP_Real* leftproplbs, /**< lower bounds after applying domain propagation in left branch */
1300  SCIP_Real* leftpropubs, /**< upper bounds after applying domain propagation in left branch */
1301  SCIP_Real* rightimpllbs, /**< lower bounds after applying implications and cliques in right branch, or NULL */
1302  SCIP_Real* rightimplubs, /**< upper bounds after applying implications and cliques in right branch, or NULL */
1303  SCIP_Real* rightproplbs, /**< lower bounds after applying domain propagation in right branch */
1304  SCIP_Real* rightpropubs, /**< upper bounds after applying domain propagation in right branch */
1305  int* nfixedvars, /**< pointer to counter which is increased by the number of deduced variable fixations */
1306  int* naggrvars, /**< pointer to counter which is increased by the number of deduced variable aggregations */
1307  int* nimplications, /**< pointer to counter which is increased by the number of deduced implications */
1308  int* nchgbds, /**< pointer to counter which is increased by the number of deduced bound tightenings */
1309  SCIP_Bool* cutoff /**< buffer to store whether a cutoff is detected */
1310  )
1311 {
1312  SCIP_Bool fixedleft;
1313  SCIP_Bool fixedright;
1314  SCIP_Bool probingvarisbinary;
1315  SCIP_Bool probingvarisinteger;
1316  int j;
1317 
1318  assert(scip != NULL);
1319  assert(probingvar != NULL);
1320  assert(SCIPisGE(scip, leftub, SCIPvarGetLbLocal(probingvar))); /* left branch should not be empty by default */
1321  assert(SCIPisLE(scip, rightlb, SCIPvarGetUbLocal(probingvar))); /* right branch should not be empty by default */
1322  assert(vars != NULL || nvars == 0);
1323  assert(leftproplbs != NULL);
1324  assert(leftpropubs != NULL);
1325  assert(rightproplbs != NULL);
1326  assert(rightpropubs != NULL);
1327  assert(nfixedvars != NULL);
1328  assert(naggrvars != NULL);
1329  assert(nimplications != NULL);
1330  assert(nchgbds != NULL);
1331  assert(cutoff != NULL);
1332 
1333  /* @todo the asserts below could be relaxed by taking domain holes into account */
1334  if( SCIPvarGetType(probingvar) != SCIP_VARTYPE_CONTINUOUS )
1335  {
1336  /* adjust bounds to actually used ones */
1337  leftub = SCIPfloor(scip, leftub);
1338  rightlb = SCIPceil(scip, rightlb);
1339 
1340  probingvarisinteger = TRUE;
1341  probingvarisbinary = SCIPvarIsBinary(probingvar);
1342  }
1343  else
1344  {
1345  /* assert dichotomy in case of continuous var: leftub >= rightlb */
1346  assert(SCIPisGE(scip, leftub, rightlb));
1347  probingvarisbinary = FALSE;
1348  probingvarisinteger = FALSE;
1349  }
1350 
1351  /* check if probing variable was fixed in the branches */
1352  fixedleft = SCIPisEQ(scip, SCIPvarGetLbLocal(probingvar), leftub);
1353  fixedright = SCIPisEQ(scip, SCIPvarGetUbLocal(probingvar), rightlb);
1354 
1355  *cutoff = FALSE;
1356 
1357  for( j = 0; j < nvars && !*cutoff; ++j )
1358  {
1359  SCIP_VAR* var;
1360  SCIP_Bool varisinteger;
1361  SCIP_Real newlb;
1362  SCIP_Real newub;
1363 
1364  assert(vars != NULL); /* for flexelint */
1365 
1366  var = vars[j];
1367  assert(var != NULL);
1368 
1369  /* @todo: add holes, and even add holes if x was the probing variable and it followed a better bound on x itself */
1370  /* @todo: check if we probed on an integer variable, that this maybe led to aggregation on two other variables, i.e
1371  * probing on x <= 1 and x >= 2 led to y = 1, z = 1 and y = 0, z = 0 resp., which means y = Z
1372  */
1373 
1374  /* if probing variable is binary, then there is nothing we could deduce here (variable should be fixed in both branches)
1375  * if it is not binary, we want to see if we found bound tightenings, even though it seems quite unlikely */
1376  if( var == probingvar && probingvarisbinary )
1377  continue;
1378 
1379  /* new bounds of the variable is the union of the propagated bounds of the left and right case */
1380  newlb = MIN(leftproplbs[j], rightproplbs[j]);
1381  newub = MAX(leftpropubs[j], rightpropubs[j]);
1382  varisinteger = (SCIPvarGetType(var) < SCIP_VARTYPE_CONTINUOUS);
1383 
1384  /* check for fixed variables */
1385  if( SCIPisEQ(scip, newlb, newub) )
1386  {
1387  SCIP_Real fixval;
1388  SCIP_Bool fixed;
1389 
1390  if( !varisinteger )
1391  {
1392  /* in both probings, variable j is deduced to the same value: fix variable to this value */
1393  fixval = SCIPselectSimpleValue(newlb - 0.9 * SCIPepsilon(scip), newub + 0.9 * SCIPepsilon(scip), MAXDNOM);
1394  }
1395  else
1396  {
1397  fixval = newlb;
1398  }
1399 
1400  if( SCIPgetStage(scip) != SCIP_STAGE_SOLVING || SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) == 0 )
1401  {
1402  SCIP_CALL( SCIPfixVar(scip, var, fixval, cutoff, &fixed) );
1403  }
1404  else
1405  {
1406  SCIP_CALL( SCIPtightenVarLb(scip, var, fixval, TRUE, cutoff, &fixed) );
1407  if( !*cutoff )
1408  {
1409  SCIP_Bool tightened;
1410 
1411  SCIP_CALL( SCIPtightenVarUb(scip, var, fixval, TRUE, cutoff, &tightened) );
1412  fixed &= tightened;
1413  }
1414  }
1415 
1416  if( fixed )
1417  {
1418  SCIPdebugMessage("fixed variable <%s> to %g due to probing on <%s> with nlocks=(%d/%d)\n",
1419  SCIPvarGetName(var), fixval,
1420  SCIPvarGetName(probingvar), SCIPvarGetNLocksDown(probingvar), SCIPvarGetNLocksUp(probingvar));
1421  (*nfixedvars)++;
1422  }
1423  continue;
1424  }
1425  else
1426  {
1427  /* check for bound tightenings */
1428  SCIP_Real oldlb;
1429  SCIP_Real oldub;
1430  SCIP_Bool tightened;
1431  SCIP_Bool tightenlb;
1432  SCIP_Bool tightenub;
1433  SCIP_Bool force;
1434 
1435  oldlb = SCIPvarGetLbLocal(var);
1436  oldub = SCIPvarGetUbLocal(var);
1437 
1438  if( varisinteger )
1439  {
1440  force = TRUE;
1441  tightenlb = (newlb > oldlb + 0.5);
1442  tightenub = (newub < oldub - 0.5);
1443  }
1444  else
1445  {
1446  force = TRUE;
1447  tightenlb = SCIPisLbBetter(scip, newlb, oldlb, oldub);
1448  tightenub = SCIPisUbBetter(scip, newub, oldlb, oldub);
1449  }
1450 
1451  if( tightenlb )
1452  {
1453  /* in both probings, variable j is deduced to be at least newlb: tighten lower bound */
1454  SCIP_CALL( SCIPtightenVarLb(scip, var, newlb, force, cutoff, &tightened) );
1455  if( tightened )
1456  {
1457  SCIPdebugMessage("tightened lower bound of variable <%s>[%g,%g] to %g due to probing on <%s> with nlocks=(%d/%d)\n",
1458  SCIPvarGetName(var), oldlb, oldub, newlb,
1459  SCIPvarGetName(probingvar), SCIPvarGetNLocksDown(probingvar), SCIPvarGetNLocksUp(probingvar));
1460  (*nchgbds)++;
1461  }
1462  }
1463 
1464  if( tightenub && !*cutoff )
1465  {
1466  /* in both probings, variable j is deduced to be at most newub: tighten upper bound */
1467  SCIP_CALL( SCIPtightenVarUb(scip, var, newub, force, cutoff, &tightened) );
1468  if( tightened )
1469  {
1470  SCIPdebugMessage("tightened upper bound of variable <%s>[%g,%g] to %g due to probing on <%s> with nlocks=(%d/%d)\n",
1471  SCIPvarGetName(var), oldlb, oldub, newub,
1472  SCIPvarGetName(probingvar), SCIPvarGetNLocksDown(probingvar), SCIPvarGetNLocksUp(probingvar));
1473  (*nchgbds)++;
1474  }
1475  }
1476  if( *cutoff )
1477  break;
1478  }
1479 
1480  /* below we add aggregations and implications between probingvar and var,
1481  * we don't want this if both variables are the same
1482  */
1483  if( var == probingvar )
1484  continue;
1485 
1486  /* check for aggregations and implications */
1487  if( fixedleft && fixedright &&
1488  SCIPisEQ(scip, leftproplbs[j], leftpropubs[j]) && SCIPisEQ(scip, rightproplbs[j], rightpropubs[j]) )
1489  {
1490  /* var is fixed whenever probingvar is fixed, i.e.,
1491  * var = leftproplbs[j] + (rightproplbs[j] - leftproplbs[j]) / (rightlb - leftub) * (probingvar - leftub)
1492  * -> both variables can be aggregated:
1493  * (rightlb - leftub) * (var - leftproplbs[j]) = (rightproplbs[j] - leftproplbs[j]) * (probingvar - leftub)
1494  * -> (rightlb - leftub) * var - (rightproplbs[j] - leftproplbs[j]) * probingvar = leftproplbs[j] * rightlb - rightproplbs[j] * leftub
1495  *
1496  * check for case where both variables are binary: leftub = 1, rightlb = 0
1497  * case leftproplbs[j] = 0, rightproplbs[j] = 1, i.e., var and probingvar are fixed to same value
1498  * -> aggregation is 1 * var - 1 * probingvar = 0 * 1 - 1 * 0 = 0 -> correct
1499  * case leftproplbs[j] = 1, rightproblbs[j] = 0, i.e., var and probingvar are fixed to opposite values
1500  * -> aggregation is 1 * var + 1 * probingvar = 1 * 1 - 0 * 0 = 0 -> correct
1501  */
1502  if( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING )
1503  {
1504  SCIP_Bool aggregated;
1505  SCIP_Bool redundant;
1506 
1507  SCIP_CALL( SCIPaggregateVars(scip, var, probingvar,
1508  rightlb - leftub, -(rightproplbs[j] - leftproplbs[j]), leftproplbs[j] * rightlb - rightproplbs[j] * leftub,
1509  cutoff, &redundant, &aggregated) );
1510 
1511  if( aggregated )
1512  {
1513  SCIPdebugMessage("aggregated variables %g<%s> - %g<%s> == %g, nlocks=(%d/%d)\n",
1514  rightlb - leftub, SCIPvarGetName(var),
1515  rightproplbs[j] - leftproplbs[j], SCIPvarGetName(probingvar),
1516  leftproplbs[j] * rightlb - rightproplbs[j] * leftub,
1517  SCIPvarGetNLocksDown(var), SCIPvarGetNLocksUp(probingvar));
1518  (*naggrvars)++;
1519  }
1520  }
1521  else if( probingvarisinteger && SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) == 0 )
1522  {
1523  /* if we are not in presolving, then we cannot do aggregations
1524  * but we can use variable bounds to code the same equality
1525  * var == ((leftproplbs[j] * rightlb - rightproplbs[j] * leftub) + (rightproplbs[j] - leftproplbs[j]) * probingvar) / (rightlb - leftub)
1526  */
1527  int nboundchanges;
1528 
1529  assert(!SCIPisEQ(scip, leftub, rightlb));
1530 
1531  SCIP_CALL( SCIPaddVarVlb(scip, var, probingvar, (rightproplbs[j] - leftproplbs[j]) / (rightlb - leftub), (leftproplbs[j] * rightlb - rightproplbs[j] * leftub) / (rightlb - leftub), cutoff, &nboundchanges) );
1532  (*nchgbds) += nboundchanges;
1533  if( !*cutoff )
1534  {
1535  SCIP_CALL( SCIPaddVarVub(scip, var, probingvar, (rightproplbs[j] - leftproplbs[j]) / (rightlb - leftub), (leftproplbs[j] * rightlb - rightproplbs[j] * leftub) / (rightlb - leftub), cutoff, &nboundchanges) );
1536  (*nchgbds) += nboundchanges;
1537  }
1538  (*nimplications)++;
1539  }
1540  /* if probingvar is continuous and we are in solving stage, then we do nothing, but it's unlikely that we get here (fixedleft && fixedright) with a continuous variable */
1541  }
1542  /* @todo: check if we can add variable lowerbounds/upperbounds on integer variables */
1543  /* can only add implications on binary variables which are globally valid */
1544  else if( probingvarisbinary && (SCIPgetStage(scip) != SCIP_STAGE_SOLVING || SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) == 0) )
1545  {
1546  /* implications can be added only for binary variables */
1547  int nboundchanges;
1548 
1549  /* since probing var is binary variable, probing should have fixed variable in both branches,
1550  * which is to 0.0 in the left branch and to 1.0 in the right branch */
1551  assert(fixedleft);
1552  assert(fixedright);
1553  assert(SCIPisZero(scip, leftub));
1554  assert(SCIPisEQ(scip, rightlb, 1.0));
1555 
1556  if( SCIPisEQ(scip, newlb, leftpropubs[j]) && (leftimplubs == NULL || leftimplubs[j] > leftpropubs[j]) )
1557  {
1558  /* var is fixed to lower bound whenever probingvar is fixed to 0.0
1559  * and implication is not already known
1560  * -> insert implication: probingvar == 0 => var <= leftpropubs[j]
1561  */
1562  /*SCIPdebugMessage("found implication <%s> == 0 => <%s> == %g\n",
1563  SCIPvarGetName(probingvar), SCIPvarGetName(var), leftpropubs[j]);*/
1564  SCIP_CALL( SCIPaddVarImplication(scip, probingvar, FALSE, var, SCIP_BOUNDTYPE_UPPER, leftpropubs[j],
1565  cutoff, &nboundchanges) );
1566  (*nimplications)++;
1567  (*nchgbds) += nboundchanges;
1568  }
1569  else if( SCIPisEQ(scip, newub, leftproplbs[j]) && (leftimpllbs == NULL || leftimpllbs[j] < leftproplbs[j]) )
1570  {
1571  /* var is fixed to upper bound whenever probingvar is fixed to 0.0
1572  * and implication is not already known
1573  * -> insert implication: probingvar == 0 => var >= leftproplbs[j]
1574  */
1575  /*SCIPdebugMessage("found implication <%s> == 0 => <%s> == %g\n",
1576  SCIPvarGetName(probingvar), SCIPvarGetName(var), leftproplbs[j]);*/
1577  SCIP_CALL( SCIPaddVarImplication(scip, probingvar, FALSE, var, SCIP_BOUNDTYPE_LOWER, leftproplbs[j],
1578  cutoff, &nboundchanges) );
1579  (*nimplications)++;
1580  (*nchgbds) += nboundchanges;
1581  }
1582  /* we can do an else here, since the case where var is fixed for both fixings of probingvar had been handled as aggregation */
1583  else if( SCIPisEQ(scip, newlb, rightpropubs[j]) && (rightimplubs == NULL || rightimplubs[j] > rightpropubs[j]) )
1584  {
1585  /* var is fixed to lower bound whenever probingvar is fixed to 1.0
1586  * and implication is not already known
1587  * -> insert implication: probingvar == 1 => var <= rightpropubs[j]
1588  */
1589  /*SCIPdebugMessage("found implication <%s> == 1 => <%s> == %g\n",
1590  SCIPvarGetName(probingvar), SCIPvarGetName(var), rightpropubs[j]);*/
1591  SCIP_CALL( SCIPaddVarImplication(scip, probingvar, TRUE, var, SCIP_BOUNDTYPE_UPPER, rightpropubs[j],
1592  cutoff, &nboundchanges) );
1593  (*nimplications)++;
1594  (*nchgbds) += nboundchanges;
1595  }
1596  else if( SCIPisEQ(scip, newub, rightproplbs[j]) && (rightimpllbs == NULL || rightimpllbs[j] < rightproplbs[j]) )
1597  {
1598  /* var is fixed to upper bound whenever probingvar is fixed to 1.0
1599  * and implication is not already known
1600  * -> insert implication: probingvar == 1 => var >= leftproplbs[j]
1601  */
1602  /*SCIPdebugMessage("found implication <%s> == 1 => <%s> == %g\n",
1603  SCIPvarGetName(probingvar), SCIPvarGetName(var), rightproplbs[j]);*/
1604  SCIP_CALL( SCIPaddVarImplication(scip, probingvar, TRUE, var, SCIP_BOUNDTYPE_LOWER, rightproplbs[j],
1605  cutoff, &nboundchanges) );
1606  (*nimplications)++;
1607  (*nchgbds) += nboundchanges;
1608  }
1609  else if( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY )
1610  {
1611  /* check for implications for lower or upper bounds (only store implications with bounds tightened at least by 0.5)
1612  * in case of binary variables, this should have been handled in the previous cases, since every boundchange also fixes the variable
1613  */
1614  if( leftpropubs[j] < newub - 0.5 && (leftimplubs == NULL || leftpropubs[j] < leftimplubs[j]) )
1615  {
1616  /* insert implication: probingvar == 0 => var <= leftpropubs[j] */
1617  /*SCIPdebugMessage("found implication <%s> == 0 => <%s>[%g,%g] <= %g\n",
1618  SCIPvarGetName(probingvar), SCIPvarGetName(var), newlb, newub, leftpropubs[j]);*/
1619  SCIP_CALL( SCIPaddVarImplication(scip, probingvar, FALSE, var, SCIP_BOUNDTYPE_UPPER, leftpropubs[j],
1620  cutoff, &nboundchanges) );
1621  (*nimplications)++;
1622  (*nchgbds) += nboundchanges;
1623  }
1624  if( leftproplbs[j] > newlb + 0.5 && (leftimpllbs == NULL || leftproplbs[j] > leftimpllbs[j]) && !*cutoff )
1625  {
1626  /* insert implication: probingvar == 0 => var >= leftproplbs[j] */
1627  /*SCIPdebugMessage("found implication <%s> == 0 => <%s>[%g,%g] >= %g\n",
1628  SCIPvarGetName(probingvar), SCIPvarGetName(var), newlb, newub, leftproplbs[j]);*/
1629  SCIP_CALL( SCIPaddVarImplication(scip, probingvar, FALSE, var, SCIP_BOUNDTYPE_LOWER, leftproplbs[j],
1630  cutoff, &nboundchanges) );
1631  (*nimplications)++;
1632  (*nchgbds) += nboundchanges;
1633  }
1634  if( rightpropubs[j] < newub - 0.5 && (rightimplubs == NULL || rightpropubs[j] < rightimplubs[j]) && !*cutoff )
1635  {
1636  /* insert implication: probingvar == 1 => var <= rightpropubs[j] */
1637  /*SCIPdebugMessage("found implication <%s> == 1 => <%s>[%g,%g] <= %g\n",
1638  SCIPvarGetName(probingvar), SCIPvarGetName(var), newlb, newub, rightpropubs[j]);*/
1639  SCIP_CALL( SCIPaddVarImplication(scip, probingvar, TRUE, var, SCIP_BOUNDTYPE_UPPER, rightpropubs[j],
1640  cutoff, &nboundchanges) );
1641  (*nimplications)++;
1642  (*nchgbds) += nboundchanges;
1643  }
1644  if( rightproplbs[j] > newlb + 0.5 && (rightimpllbs == NULL || rightproplbs[j] > rightimpllbs[j]) && !*cutoff )
1645  {
1646  /* insert implication: probingvar == 1 => var >= rightproplbs[j] */
1647  /*SCIPdebugMessage("found implication <%s> == 1 => <%s>[%g,%g] >= %g\n",
1648  SCIPvarGetName(probingvar), SCIPvarGetName(var), newlb, newub, rightproplbs[j]);*/
1649  SCIP_CALL( SCIPaddVarImplication(scip, probingvar, TRUE, var, SCIP_BOUNDTYPE_LOWER, rightproplbs[j],
1650  cutoff, &nboundchanges) );
1651  (*nimplications)++;
1652  (*nchgbds) += nboundchanges;
1653  }
1654  }
1655  }
1656  }
1657 
1658  return SCIP_OKAY;
1659 }
1660