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