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   scip_probing.c
26   	 * @ingroup OTHER_CFILES
27   	 * @brief  public methods for the probing mode
28   	 * @author Tobias Achterberg
29   	 * @author Timo Berthold
30   	 * @author Gerald Gamrath
31   	 * @author Leona Gottwald
32   	 * @author Stefan Heinz
33   	 * @author Gregor Hendel
34   	 * @author Thorsten Koch
35   	 * @author Alexander Martin
36   	 * @author Marc Pfetsch
37   	 * @author Michael Winkler
38   	 * @author Kati Wolter
39   	 *
40   	 * @todo check all SCIP_STAGE_* switches, and include the new stages TRANSFORMED and INITSOLVE
41   	 */
42   	
43   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
44   	
45   	#include "blockmemshell/memory.h"
46   	#include "scip/conflict.h"
47   	#include "scip/cons.h"
48   	#include "scip/debug.h"
49   	#include "scip/heur.h"
50   	#include "scip/lp.h"
51   	#include "scip/prob.h"
52   	#include "scip/pub_message.h"
53   	#include "scip/pub_misc.h"
54   	#include "scip/pub_relax.h"
55   	#include "scip/pub_tree.h"
56   	#include "scip/pub_var.h"
57   	#include "scip/relax.h"
58   	#include "scip/scip_general.h"
59   	#include "scip/scip_lp.h"
60   	#include "scip/scip_mem.h"
61   	#include "scip/scip_message.h"
62   	#include "scip/scip_numerics.h"
63   	#include "scip/scip_prob.h"
64   	#include "scip/scip_probing.h"
65   	#include "scip/scip_solvingstats.h"
66   	#include "scip/scip_tree.h"
67   	#include "scip/sepastore.h"
68   	#include "scip/set.h"
69   	#include "scip/solve.h"
70   	#include "scip/stat.h"
71   	#include "scip/struct_lp.h"
72   	#include "scip/struct_mem.h"
73   	#include "scip/struct_scip.h"
74   	#include "scip/struct_set.h"
75   	#include "scip/struct_stat.h"
76   	#include "scip/struct_tree.h"
77   	#include "scip/struct_var.h"
78   	#include "scip/tree.h"
79   	#include "scip/var.h"
80   	
81   	/** returns whether we are in probing mode; probing mode is activated via SCIPstartProbing() and stopped
82   	 *  via SCIPendProbing()
83   	 *
84   	 *  @return TRUE, if SCIP is currently in probing mode, otherwise FALSE
85   	 *
86   	 *  @pre This method can be called if @p scip is in one of the following stages:
87   	 *       - \ref SCIP_STAGE_TRANSFORMED
88   	 *       - \ref SCIP_STAGE_INITPRESOLVE
89   	 *       - \ref SCIP_STAGE_PRESOLVING
90   	 *       - \ref SCIP_STAGE_EXITPRESOLVE
91   	 *       - \ref SCIP_STAGE_PRESOLVED
92   	 *       - \ref SCIP_STAGE_INITSOLVE
93   	 *       - \ref SCIP_STAGE_SOLVING
94   	 *       - \ref SCIP_STAGE_SOLVED
95   	 *       - \ref SCIP_STAGE_EXITSOLVE
96   	 */
97   	SCIP_Bool SCIPinProbing(
98   	   SCIP*                 scip                /**< SCIP data structure */
99   	   )
100  	{
101  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPinProbing", FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE) );
102  	
103  	   return SCIPtreeProbing(scip->tree);
104  	}
105  	
106  	/** initiates probing, making methods SCIPnewProbingNode(), SCIPbacktrackProbing(), SCIPchgVarLbProbing(),
107  	 *  SCIPchgVarUbProbing(), SCIPfixVarProbing(), SCIPpropagateProbing(), and SCIPsolveProbingLP() available
108  	 *
109  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
110  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
111  	 *
112  	 *  @pre This method can be called if @p scip is in one of the following stages:
113  	 *       - \ref SCIP_STAGE_PRESOLVING
114  	 *       - \ref SCIP_STAGE_SOLVING
115  	 *
116  	 *  @note The collection of variable statistics is turned off during probing. If these statistics should be collected
117  	 *        during probing use the method SCIPenableVarHistory() to turn the collection explicitly on.
118  	 */
119  	SCIP_RETCODE SCIPstartProbing(
120  	   SCIP*                 scip                /**< SCIP data structure */
121  	   )
122  	{
123  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPstartProbing", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
124  	
125  	   if( SCIPtreeProbing(scip->tree) )
126  	   {
127  	      SCIPerrorMessage("already in probing mode\n");
128  	      return SCIP_INVALIDCALL;
129  	   }
130  	
131  	   if( scip->lp != NULL && SCIPlpDiving(scip->lp) )
132  	   {
133  	      SCIPerrorMessage("cannot start probing while in diving mode\n");
134  	      return SCIP_INVALIDCALL;
135  	   }
136  	
137  	   /* use a different separation storage for probing mode; otherwise SCIP will remove the cuts that are currently in the
138  	    * separation storage after solving an LP in probing mode
139  	    */
140  	   if( scip->sepastore != NULL )
141  	   {
142  	      assert(scip->sepastoreprobing != NULL);
143  	      SCIPswapPointers((void**)&scip->sepastore, (void**)&scip->sepastoreprobing);
144  	   }
145  	
146  	   SCIP_CALL( SCIPtreeStartProbing(scip->tree, scip->mem->probmem, scip->set, scip->lp, scip->relaxation, scip->transprob, FALSE) );
147  	
148  	   /* disables the collection of any statistic for a variable */
149  	   SCIPstatDisableVarHistory(scip->stat);
150  	
151  	   return SCIP_OKAY;
152  	}
153  	
154  	/** creates a new probing sub node, whose changes can be undone by backtracking to a higher node in the probing path
155  	 *  with a call to SCIPbacktrackProbing();
156  	 *  using a sub node for each set of probing bound changes can improve conflict analysis
157  	 *
158  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
159  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
160  	 *
161  	 *  @pre This method can be called if @p scip is in one of the following stages:
162  	 *       - \ref SCIP_STAGE_PRESOLVING
163  	 *       - \ref SCIP_STAGE_SOLVING
164  	 */
165  	SCIP_RETCODE SCIPnewProbingNode(
166  	   SCIP*                 scip                /**< SCIP data structure */
167  	   )
168  	{
169  	   SCIP_RETCODE retcode;
170  	
171  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPnewProbingNode", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
172  	
173  	   if( !SCIPtreeProbing(scip->tree) )
174  	   {
175  	      SCIPerrorMessage("not in probing mode\n");
176  	      return SCIP_INVALIDCALL;
177  	   }
178  	
179  	   retcode = SCIPtreeCreateProbingNode(scip->tree, scip->mem->probmem, scip->set, scip->lp);
180  	
181  	   if( retcode == SCIP_MAXDEPTHLEVEL )
182  	   {
183  	      SCIPwarningMessage(scip, "probing reached maximal depth; it should be stopped\n");
184  	   }
185  	   SCIP_CALL( retcode );
186  	
187  	   return SCIP_OKAY;
188  	}
189  	
190  	/** returns the current probing depth
191  	 *
192  	 *  @return the probing depth, i.e. the number of probing sub nodes existing in the probing path
193  	 *
194  	 *  @pre This method can be called if @p scip is in one of the following stages:
195  	 *       - \ref SCIP_STAGE_PRESOLVING
196  	 *       - \ref SCIP_STAGE_SOLVING
197  	 */
198  	int SCIPgetProbingDepth(
199  	   SCIP*                 scip                /**< SCIP data structure */
200  	   )
201  	{
202  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetProbingDepth", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
203  	
204  	   if( !SCIPtreeProbing(scip->tree) )
205  	   {
206  	      SCIPerrorMessage("not in probing mode\n");
207  	      SCIPABORT();
208  	      return -1; /*lint !e527*/
209  	   }
210  	
211  	   return SCIPtreeGetProbingDepth(scip->tree);
212  	}
213  	
214  	/** undoes all changes to the problem applied in probing up to the given probing depth;
215  	 *  the changes of the probing node of the given probing depth are the last ones that remain active;
216  	 *  changes that were applied before calling SCIPnewProbingNode() cannot be undone
217  	 *
218  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
219  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
220  	 *
221  	 *  @pre This method can be called if @p scip is in one of the following stages:
222  	 *       - \ref SCIP_STAGE_PRESOLVING
223  	 *       - \ref SCIP_STAGE_SOLVING
224  	 */
225  	SCIP_RETCODE SCIPbacktrackProbing(
226  	   SCIP*                 scip,               /**< SCIP data structure */
227  	   int                   probingdepth        /**< probing depth of the node in the probing path that should be reactivated */
228  	   )
229  	{
230  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPbacktrackProbing", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
231  	
232  	   if( !SCIPtreeProbing(scip->tree) )
233  	   {
234  	      SCIPerrorMessage("not in probing mode\n");
235  	      return SCIP_INVALIDCALL;
236  	   }
237  	   if( probingdepth < 0 || probingdepth > SCIPtreeGetProbingDepth(scip->tree) )
238  	   {
239  	      SCIPerrorMessage("backtracking probing depth %d out of current probing range [0,%d]\n",
240  	         probingdepth, SCIPtreeGetProbingDepth(scip->tree));
241  	      return SCIP_INVALIDDATA;
242  	   }
243  	
244  	   SCIP_CALL( SCIPtreeBacktrackProbing(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->transprob,
245  	         scip->origprob, scip->lp, scip->primal, scip->branchcand, scip->eventqueue, scip->eventfilter,
246  	         scip->cliquetable, probingdepth) );
247  	
248  	   return SCIP_OKAY;
249  	}
250  	
251  	/** quits probing and resets bounds and constraints to the focus node's environment
252  	 *
253  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
254  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
255  	 *
256  	 *  @pre This method can be called if @p scip is in one of the following stages:
257  	 *       - \ref SCIP_STAGE_PRESOLVING
258  	 *       - \ref SCIP_STAGE_SOLVING
259  	 */
260  	SCIP_RETCODE SCIPendProbing(
261  	   SCIP*                 scip                /**< SCIP data structure */
262  	   )
263  	{
264  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPendProbing", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
265  	
266  	   if( !SCIPtreeProbing(scip->tree) )
267  	   {
268  	      SCIPerrorMessage("not in probing mode\n");
269  	      return SCIP_INVALIDCALL;
270  	   }
271  	
272  	   /* switch back from probing to normal operation mode and restore variables and constraints to focus node */
273  	   SCIP_CALL( SCIPtreeEndProbing(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->messagehdlr, scip->stat,
274  	         scip->transprob, scip->origprob, scip->lp, scip->relaxation, scip->primal,
275  	         scip->branchcand, scip->eventqueue, scip->eventfilter, scip->cliquetable) );
276  	
277  	   /* enables the collection of statistics for a variable */
278  	   SCIPstatEnableVarHistory(scip->stat);
279  	
280  	   /* switch to the original separation storage */
281  	   if( scip->sepastore != NULL )
282  	   {
283  	      assert(scip->sepastoreprobing != NULL);
284  	      SCIPswapPointers((void**)&scip->sepastore, (void**)&scip->sepastoreprobing);
285  	      assert(SCIPsepastoreGetNCuts(scip->sepastoreprobing) == 0);
286  	   }
287  	
288  	   return SCIP_OKAY;
289  	}
290  	
291  	/** injects a change of variable's lower bound into current probing node; the same can also be achieved with a call to
292  	 *  SCIPchgVarLb(), but in this case, the bound change would be treated like a deduction instead of a branching decision
293  	 *
294  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
295  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
296  	 *
297  	 *  @pre This method can be called if @p scip is in one of the following stages:
298  	 *       - \ref SCIP_STAGE_PRESOLVING
299  	 *       - \ref SCIP_STAGE_SOLVING
300  	 */
301  	SCIP_RETCODE SCIPchgVarLbProbing(
302  	   SCIP*                 scip,               /**< SCIP data structure */
303  	   SCIP_VAR*             var,                /**< variable to change the bound for */
304  	   SCIP_Real             newbound            /**< new value for bound */
305  	   )
306  	{
307  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPchgVarLbProbing", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
308  	
309  	   if( !SCIPtreeProbing(scip->tree) )
310  	   {
311  	      SCIPerrorMessage("not in probing mode\n");
312  	      return SCIP_INVALIDCALL;
313  	   }
314  	   assert(SCIPnodeGetType(SCIPtreeGetCurrentNode(scip->tree)) == SCIP_NODETYPE_PROBINGNODE);
315  	
316  	   SCIPvarAdjustLb(var, scip->set, &newbound);
317  	
318  	   /* ignore tightenings of lower bounds to +infinity during solving process */
319  	   if( SCIPisInfinity(scip, newbound) && SCIPgetStage(scip) == SCIP_STAGE_SOLVING )
320  	   {
321  	#ifndef NDEBUG
322  	      SCIPwarningMessage(scip, "ignore lower bound tightening for %s from %e to +infinity\n", SCIPvarGetName(var),
323  	         SCIPvarGetLbLocal(var));
324  	#endif
325  	      return SCIP_OKAY;
326  	   }
327  	
328  	   SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(scip->tree), scip->mem->probmem, scip->set, scip->stat,
329  	         scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->cliquetable,
330  	         var, newbound, SCIP_BOUNDTYPE_LOWER, TRUE) );
331  	
332  	   return SCIP_OKAY;
333  	}
334  	
335  	/** injects a change of variable's upper bound into current probing node; the same can also be achieved with a call to
336  	 *  SCIPchgVarUb(), but in this case, the bound change would be treated like a deduction instead of a branching decision
337  	 *
338  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
339  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
340  	 *
341  	 *  @pre This method can be called if @p scip is in one of the following stages:
342  	 *       - \ref SCIP_STAGE_PRESOLVING
343  	 *       - \ref SCIP_STAGE_SOLVING
344  	 */
345  	SCIP_RETCODE SCIPchgVarUbProbing(
346  	   SCIP*                 scip,               /**< SCIP data structure */
347  	   SCIP_VAR*             var,                /**< variable to change the bound for */
348  	   SCIP_Real             newbound            /**< new value for bound */
349  	   )
350  	{
351  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPchgVarUbProbing", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
352  	
353  	   if( !SCIPtreeProbing(scip->tree) )
354  	   {
355  	      SCIPerrorMessage("not in probing mode\n");
356  	      return SCIP_INVALIDCALL;
357  	   }
358  	   assert(SCIPnodeGetType(SCIPtreeGetCurrentNode(scip->tree)) == SCIP_NODETYPE_PROBINGNODE);
359  	
360  	   SCIPvarAdjustUb(var, scip->set, &newbound);
361  	
362  	   /* ignore tightenings of upper bounds to -infinity during solving process */
363  	   if( SCIPisInfinity(scip, -newbound) && SCIPgetStage(scip) == SCIP_STAGE_SOLVING )
364  	   {
365  	#ifndef NDEBUG
366  	      SCIPwarningMessage(scip, "ignore upper bound tightening for %s from %e to -infinity\n", SCIPvarGetName(var),
367  	         SCIPvarGetUbLocal(var));
368  	#endif
369  	      return SCIP_OKAY;
370  	   }
371  	
372  	   SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(scip->tree), scip->mem->probmem, scip->set, scip->stat,
373  	         scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->cliquetable,
374  	         var, newbound, SCIP_BOUNDTYPE_UPPER, TRUE) );
375  	
376  	   return SCIP_OKAY;
377  	}
378  	
379  	/** gets variable's objective value in current probing
380  	 *
381  	 *  @return the variable's objective value in current probing.
382  	 *
383  	 *  @pre This method can be called if @p scip is in one of the following stages:
384  	 *       - \ref SCIP_STAGE_SOLVING
385  	 *
386  	 *  See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
387  	 */
388  	SCIP_Real SCIPgetVarObjProbing(
389  	   SCIP*                 scip,               /**< SCIP data structure */
390  	   SCIP_VAR*             var                 /**< variable to get the bound for */
391  	   )
392  	{
393  	   assert(scip != NULL);
394  	   assert(var != NULL);
395  	
396  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetVarObjProbing", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
397  	
398  	   if( !SCIPtreeProbing(scip->tree) )
399  	   {
400  	      SCIPerrorMessage("not in probing mode\n");
401  	      return SCIP_INVALID;
402  	   }
403  	
404  	   return SCIPvarGetObjLP(var);
405  	}
406  	
407  	/** injects a change of variable's bounds into current probing node to fix the variable to the specified value;
408  	 *  the same can also be achieved with a call to SCIPfixVar(), but in this case, the bound changes would be treated
409  	 *  like deductions instead of branching decisions
410  	 *
411  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
412  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
413  	 *
414  	 *  @pre This method can be called if @p scip is in one of the following stages:
415  	 *       - \ref SCIP_STAGE_PRESOLVING
416  	 *       - \ref SCIP_STAGE_SOLVING
417  	 */
418  	SCIP_RETCODE SCIPfixVarProbing(
419  	   SCIP*                 scip,               /**< SCIP data structure */
420  	   SCIP_VAR*             var,                /**< variable to change the bound for */
421  	   SCIP_Real             fixedval            /**< value to fix variable to */
422  	   )
423  	{
424  	   SCIP_Real fixlb;
425  	   SCIP_Real fixub;
426  	
427  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPfixVarProbing", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
428  	
429  	   if( !SCIPtreeProbing(scip->tree) )
430  	   {
431  	      SCIPerrorMessage("not in probing mode\n");
432  	      return SCIP_INVALIDCALL;
433  	   }
434  	   assert(SCIPnodeGetType(SCIPtreeGetCurrentNode(scip->tree)) == SCIP_NODETYPE_PROBINGNODE);
435  	
436  	   /* we adjust the fixing value here and compare the old bound with the adjusted values because otherwise,
437  	    * it might happen that the unadjusted value is better and we add the boundchange,
438  	    * but within SCIPnodeAddBoundchg() the bounds are adjusted - using the feasibility epsilon for integer variables -
439  	    * and it is asserted, that the bound is still better than the old one which might then be incorrect.
440  	    */
441  	   fixlb = fixedval;
442  	   fixub = fixedval;
443  	   SCIPvarAdjustLb(var, scip->set, &fixlb);
444  	   SCIPvarAdjustUb(var, scip->set, &fixub);
445  	   assert(SCIPsetIsEQ(scip->set, fixlb, fixub));
446  	
447  	   if( SCIPsetIsGT(scip->set, fixlb, SCIPvarGetLbLocal(var)) )
448  	   {
449  	      SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(scip->tree), scip->mem->probmem, scip->set, scip->stat,
450  	            scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue,
451  	            scip->cliquetable, var, fixlb, SCIP_BOUNDTYPE_LOWER, TRUE) );
452  	   }
453  	   if( SCIPsetIsLT(scip->set, fixub, SCIPvarGetUbLocal(var)) )
454  	   {
455  	      SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(scip->tree), scip->mem->probmem, scip->set, scip->stat,
456  	            scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->cliquetable,
457  	            var, fixub, SCIP_BOUNDTYPE_UPPER, TRUE) );
458  	   }
459  	
460  	   return SCIP_OKAY;
461  	}
462  	
463  	/** changes (column) variable's objective value during probing mode
464  	 *
465  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
466  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
467  	 *
468  	 *  @pre This method can be called if @p scip is in one of the following stages:
469  	 *       - \ref SCIP_STAGE_PRESOLVING
470  	 *       - \ref SCIP_STAGE_SOLVING
471  	 *
472  	 *  @pre The variable needs to be a column variable.
473  	 */
474  	SCIP_RETCODE SCIPchgVarObjProbing(
475  	   SCIP*                 scip,               /**< SCIP data structure */
476  	   SCIP_VAR*             var,                /**< variable to change the objective for */
477  	   SCIP_Real             newobj              /**< new objective function value */
478  	   )
479  	{
480  	   SCIP_NODE* node;
481  	   SCIP_Real oldobj;
482  	
483  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPchgVarObjProbing", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
484  	
485  	   if( !SCIPtreeProbing(scip->tree) )
486  	   {
487  	      SCIPerrorMessage("not in probing mode\n");
488  	      return SCIP_INVALIDCALL;
489  	   }
490  	
491  	   /* get current probing node */
492  	   node = SCIPtreeGetCurrentNode(scip->tree);
493  	   assert(SCIPnodeGetType(node) == SCIP_NODETYPE_PROBINGNODE);
494  	
495  	   /* get old objective function value */
496  	   oldobj = SCIPvarGetObj(var);
497  	
498  	   if( SCIPisEQ(scip, oldobj, newobj) )
499  	      return SCIP_OKAY;
500  	
501  	   if( node->data.probingnode->nchgdobjs == 0 )
502  	   {
503  	      SCIP_CALL( SCIPallocMemoryArray(scip, &node->data.probingnode->origobjvars, 1) ); /*lint !e506*/
504  	      SCIP_CALL( SCIPallocMemoryArray(scip, &node->data.probingnode->origobjvals, 1) ); /*lint !e506*/
505  	   }
506  	   else
507  	   {
508  	      SCIP_CALL( SCIPreallocMemoryArray(scip, &node->data.probingnode->origobjvars, node->data.probingnode->nchgdobjs + 1) ); /*lint !e776*/
509  	      SCIP_CALL( SCIPreallocMemoryArray(scip, &node->data.probingnode->origobjvals, node->data.probingnode->nchgdobjs + 1) ); /*lint !e776*/
510  	   }
511  	
512  	   node->data.probingnode->origobjvars[node->data.probingnode->nchgdobjs] = var;
513  	   node->data.probingnode->origobjvals[node->data.probingnode->nchgdobjs] = oldobj;
514  	   ++node->data.probingnode->nchgdobjs;
515  	   ++scip->tree->probingsumchgdobjs;
516  	
517  	   assert(SCIPtreeProbingObjChanged(scip->tree) == SCIPlpDivingObjChanged(scip->lp));
518  	
519  	   /* inform tree and LP that the objective was changed and invalidate the LP's cutoff bound, since this has nothing to
520  	    * do with the current objective value anymore; the cutoff bound is reset in SCIPendProbing()
521  	    */
522  	   if( !SCIPtreeProbingObjChanged(scip->tree) )
523  	   {
524  	      SCIP_CALL( SCIPlpSetCutoffbound(scip->lp, scip->set, scip->transprob, SCIPsetInfinity(scip->set)) );
525  	
526  	      SCIPtreeMarkProbingObjChanged(scip->tree);
527  	      SCIPlpMarkDivingObjChanged(scip->lp);
528  	   }
529  	   assert(SCIPisInfinity(scip, scip->lp->cutoffbound));
530  	
531  	   /* perform the objective change */
532  	   SCIP_CALL( SCIPvarChgObj(var, scip->mem->probmem, scip->set,  scip->transprob, scip->primal, scip->lp, scip->eventqueue, newobj) );
533  	
534  	   return SCIP_OKAY;
535  	}
536  	
537  	/** returns whether the objective function has changed during probing mode
538  	 *
539  	 *  @return \ref TRUE if objective has changed, \ref FALSE otherwise
540  	 *
541  	 *  @pre This method can be called if @p scip is in one of the following stages:
542  	 *       - \ref SCIP_STAGE_TRANSFORMED
543  	 *       - \ref SCIP_STAGE_INITPRESOLVE
544  	 *       - \ref SCIP_STAGE_PRESOLVING
545  	 *       - \ref SCIP_STAGE_EXITPRESOLVE
546  	 *       - \ref SCIP_STAGE_PRESOLVED
547  	 *       - \ref SCIP_STAGE_INITSOLVE
548  	 *       - \ref SCIP_STAGE_SOLVING
549  	 *       - \ref SCIP_STAGE_SOLVED
550  	 *       - \ref SCIP_STAGE_EXITSOLVE
551  	 */
552  	SCIP_Bool SCIPisObjChangedProbing(
553  	   SCIP*                 scip                /**< SCIP data structure */
554  	   )
555  	{
556  	   assert(scip != NULL);
557  	
558  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPisObjChangedProbing", FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE) );
559  	
560  	   return scip->tree != NULL && SCIPinProbing(scip) && SCIPtreeProbingObjChanged(scip->tree);
561  	}
562  	
563  	/** applies domain propagation on the probing sub problem, that was changed after SCIPstartProbing() was called;
564  	 *  the propagated domains of the variables can be accessed with the usual bound accessing calls SCIPvarGetLbLocal()
565  	 *  and SCIPvarGetUbLocal(); the propagation is only valid locally, i.e. the local bounds as well as the changed
566  	 *  bounds due to SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), and SCIPfixVarProbing() are used for propagation
567  	 *
568  	 *  @note Conflict analysis can run if the propagation finds infeasibilities. SCIPpropagateProbing can even find
569  	 *  globally valid bound changes. For this reason, the function restores the original objective (i.e. undoes the changes
570  	 *  done by SCIPchgVarObjProbing before performing the propagation, as the propagators don't know that the objective
571  	 *  might have changed. Thus, SCIPpropagateProbing can have an effect on the problem after probing ends.
572  	 *
573  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
574  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
575  	 *
576  	 *  @pre This method can be called if @p scip is in one of the following stages:
577  	 *       - \ref SCIP_STAGE_PRESOLVING
578  	 *       - \ref SCIP_STAGE_SOLVING
579  	 */
580  	SCIP_RETCODE SCIPpropagateProbing(
581  	   SCIP*                 scip,               /**< SCIP data structure */
582  	   int                   maxproprounds,      /**< maximal number of propagation rounds (-1: no limit, 0: parameter settings) */
583  	   SCIP_Bool*            cutoff,             /**< pointer to store whether the probing node can be cut off */
584  	   SCIP_Longint*         ndomredsfound       /**< pointer to store the number of domain reductions found, or NULL */
585  	   )
586  	{
587  	   SCIP_VAR** objchgvars;
588  	   SCIP_Real* objchgvals;
589  	   SCIP_Bool changedobj;
590  	   int nobjchg;
591  	
592  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPpropagateProbing", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
593  	
594  	   if( !SCIPtreeProbing(scip->tree) )
595  	   {
596  	      SCIPerrorMessage("not in probing mode\n");
597  	      return SCIP_INVALIDCALL;
598  	   }
599  	
600  	   objchgvars = NULL;
601  	   objchgvals = NULL;
602  	   changedobj = FALSE;
603  	   nobjchg = 0;
604  	
605  	   /* undo objective changes if we want to propagate during probing */
606  	   if( scip->tree->probingobjchanged )
607  	   {
608  	      SCIP_VAR** vars;
609  	      int nvars;
610  	      int i;
611  	
612  	      vars = SCIPgetVars(scip);
613  	      nvars = SCIPgetNVars(scip);
614  	
615  	      SCIP_CALL( SCIPallocBufferArray(scip, &objchgvals, MIN(nvars, scip->tree->probingsumchgdobjs)) );
616  	      SCIP_CALL( SCIPallocBufferArray(scip, &objchgvars, MIN(nvars, scip->tree->probingsumchgdobjs)) );
617  	      nobjchg = 0;
618  	
619  	      for( i = 0; i < nvars; ++i )
620  	      {
621  	         if( !SCIPisEQ(scip, vars[i]->unchangedobj, SCIPgetVarObjProbing(scip, vars[i])) )
622  	         {
623  	            objchgvars[nobjchg] = vars[i];
624  	            objchgvals[nobjchg] = SCIPgetVarObjProbing(scip, vars[i]);
625  	            ++nobjchg;
626  	
627  	            SCIP_CALL( SCIPvarChgObj(vars[i], scip->mem->probmem, scip->set, scip->transprob, scip->primal, scip->lp,
628  	                  scip->eventqueue, vars[i]->unchangedobj) );
629  	         }
630  	      }
631  	      assert(nobjchg <= scip->tree->probingsumchgdobjs);
632  	
633  	      SCIPlpUnmarkDivingObjChanged(scip->lp);
634  	      scip->tree->probingobjchanged = FALSE;
635  	      changedobj = TRUE;
636  	   }
637  	
638  	   if( ndomredsfound != NULL )
639  	      *ndomredsfound = -(scip->stat->nprobboundchgs + scip->stat->nprobholechgs);
640  	
641  	   SCIP_CALL( SCIPpropagateDomains(scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob,
642  	         scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->conflict, scip->cliquetable,
643  	         SCIPgetDepth(scip), maxproprounds, SCIP_PROPTIMING_ALWAYS, cutoff) );
644  	
645  	   if( ndomredsfound != NULL )
646  	      *ndomredsfound += scip->stat->nprobboundchgs + scip->stat->nprobholechgs;
647  	
648  	   /* restore old objective function */
649  	   if( changedobj )
650  	   {
651  	      int i;
652  	
653  	      assert(objchgvars != NULL);
654  	      assert(objchgvals != NULL);
655  	
656  	      SCIPlpMarkDivingObjChanged(scip->lp);
657  	      scip->tree->probingobjchanged = TRUE;
658  	
659  	      for( i = 0; i < nobjchg; ++i )
660  	      {
661  	         SCIP_CALL( SCIPvarChgObj(objchgvars[i], scip->mem->probmem, scip->set,  scip->transprob, scip->primal,
662  	               scip->lp, scip->eventqueue, objchgvals[i]) );
663  	      }
664  	
665  	      SCIPfreeBufferArray(scip, &objchgvars);
666  	      SCIPfreeBufferArray(scip, &objchgvals);
667  	   }
668  	
669  	   return SCIP_OKAY;
670  	}
671  	
672  	/** applies domain propagation on the probing sub problem, that was changed after SCIPstartProbing() was called;
673  	 *  only propagations of the binary variables fixed at the current probing node that are triggered by the implication
674  	 *  graph and the clique table are applied;
675  	 *  the propagated domains of the variables can be accessed with the usual bound accessing calls SCIPvarGetLbLocal()
676  	 *  and SCIPvarGetUbLocal(); the propagation is only valid locally, i.e. the local bounds as well as the changed
677  	 *  bounds due to SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), and SCIPfixVarProbing() are used for propagation
678  	 *
679  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
680  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
681  	 *
682  	 *  @pre This method can be called if @p scip is in one of the following stages:
683  	 *       - \ref SCIP_STAGE_PRESOLVING
684  	 *       - \ref SCIP_STAGE_SOLVING
685  	 */
686  	SCIP_RETCODE SCIPpropagateProbingImplications(
687  	   SCIP*                 scip,               /**< SCIP data structure */
688  	   SCIP_Bool*            cutoff              /**< pointer to store whether the probing node can be cut off */
689  	   )
690  	{
691  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPpropagateProbingImplications", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
692  	
693  	   if( !SCIPtreeProbing(scip->tree) )
694  	   {
695  	      SCIPerrorMessage("not in probing mode\n");
696  	      return SCIP_INVALIDCALL;
697  	   }
698  	
699  	   SCIP_CALL( SCIPnodePropagateImplics(SCIPtreeGetCurrentNode(scip->tree), scip->mem->probmem, scip->set, scip->stat,
700  	         scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->cliquetable, cutoff) );
701  	
702  	   return SCIP_OKAY;
703  	}
704  	
705  	/** solves the LP at the current probing node (cannot be applied at preprocessing stage) with or without pricing */
706  	static
707  	SCIP_RETCODE solveProbingLP(
708  	   SCIP*                 scip,               /**< SCIP data structure */
709  	   int                   itlim,              /**< maximal number of LP iterations to perform, or -1 for no limit */
710  	   SCIP_Bool             pricing,            /**< should pricing be applied? */
711  	   SCIP_Bool             pretendroot,        /**< should the pricers be called as if we are at the root node? */
712  	   SCIP_Bool             displayinfo,        /**< should info lines be displayed after each pricing round? */
713  	   int                   maxpricerounds,     /**< maximal number of pricing rounds (-1: no limit) */
714  	   SCIP_Bool*            lperror,            /**< pointer to store whether an unresolved LP error occurred */
715  	   SCIP_Bool*            cutoff              /**< pointer to store whether the probing LP was infeasible or the objective
716  	                                              *   limit was reached (or NULL, if not needed) */
717  	   )
718  	{
719  	   SCIP_Bool initcutoff;
720  	
721  	   assert(lperror != NULL);
722  	   assert(SCIPtreeIsFocusNodeLPConstructed(scip->tree));
723  	
724  	   if( !SCIPtreeProbing(scip->tree) )
725  	   {
726  	      SCIPerrorMessage("not in probing mode\n");
727  	      return SCIP_INVALIDCALL;
728  	   }
729  	   assert(SCIPtreeGetCurrentDepth(scip->tree) > 0);
730  	
731  	   SCIP_CALL( SCIPinitConssLP(scip->mem->probmem, scip->set, scip->sepastore, scip->cutpool, scip->stat, scip->transprob,
732  	         scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->eventfilter,
733  	         scip->cliquetable, FALSE, FALSE, &initcutoff) );
734  	
735  	   if( initcutoff )
736  	   {
737  	      if( cutoff != NULL )
738  	         *cutoff = TRUE;
739  	
740  	      return SCIP_OKAY;
741  	   }
742  	   else if( cutoff != NULL )
743  	      *cutoff = FALSE;
744  	
745  	   /* load the LP state (if necessary) */
746  	   SCIP_CALL( SCIPtreeLoadProbingLPState(scip->tree, scip->mem->probmem, scip->set, scip->transprob, scip->eventqueue, scip->lp) );
747  	
748  	   SCIPlpSetIsRelax(scip->lp, TRUE);
749  	
750  	   /* solve probing LP */
751  	   SCIP_CALL( SCIPlpSolveAndEval(scip->lp, scip->set, scip->messagehdlr, scip->mem->probmem, scip->stat,
752  	         scip->eventqueue, scip->eventfilter, scip->transprob, (SCIP_Longint)itlim, FALSE, FALSE, FALSE, lperror) );
753  	
754  	   assert((*lperror) || SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_NOTSOLVED);
755  	
756  	   /* mark the probing node to have a solved LP */
757  	   if( !(*lperror) )
758  	   {
759  	      SCIP_CALL( SCIPtreeMarkProbingNodeHasLP(scip->tree, scip->mem->probmem, scip->lp) );
760  	
761  	      /* call pricing */
762  	      if( pricing )
763  	      {
764  	         SCIP_Bool mustsepa;
765  	         int npricedcolvars;
766  	         SCIP_Bool result;
767  	
768  	            mustsepa = FALSE;
769  	            SCIP_CALL( SCIPpriceLoop(scip->mem->probmem, scip->set, scip->messagehdlr, scip->stat, scip->transprob,
770  	                  scip->origprob, scip->primal, scip->tree, scip->reopt, scip->lp, scip->pricestore, scip->sepastore, scip->cutpool,
771  	                  scip->branchcand, scip->eventqueue, scip->eventfilter, scip->cliquetable, pretendroot, displayinfo,
772  	                  maxpricerounds, &npricedcolvars, &mustsepa, lperror, &result) );
773  	
774  	         /* mark the probing node again to update the LP size in the node and the tree path */
775  	         if( !(*lperror) )
776  	         {
777  	            SCIP_CALL( SCIPtreeMarkProbingNodeHasLP(scip->tree, scip->mem->probmem, scip->lp) );
778  	         }
779  	      }
780  	   }
781  	
782  	   /* remember that probing might have changed the LPi state; this holds even if solving returned with an LP error */
783  	   scip->tree->probingsolvedlp = TRUE;
784  	
785  	   /* the LP is infeasible or the objective limit was reached */
786  	   if( !(*lperror) && (SCIPlpGetSolstat(scip->lp) == SCIP_LPSOLSTAT_INFEASIBLE
787  	         || SCIPlpGetSolstat(scip->lp) == SCIP_LPSOLSTAT_OBJLIMIT ||
788  	         (SCIPlpGetSolstat(scip->lp) == SCIP_LPSOLSTAT_OPTIMAL
789  	            && SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)))) )
790  	   {
791  	      /* analyze the infeasible LP (only if all columns are in the LP and no external pricers exist) */
792  	      if( !scip->set->misc_exactsolve && SCIPprobAllColsInLP(scip->transprob, scip->set, scip->lp) && !scip->tree->probingobjchanged )
793  	      {
794  	         SCIP_CALL( SCIPconflictAnalyzeLP(scip->conflict, scip->conflictstore, scip->mem->probmem, scip->set, scip->stat, scip->transprob,
795  	               scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->cliquetable, NULL) );
796  	      }
797  	
798  	      if( cutoff != NULL )
799  	         *cutoff = TRUE;
800  	   }
801  	
802  	   return SCIP_OKAY;
803  	}
804  	
805  	/** solves the LP at the current probing node (cannot be applied at preprocessing stage);
806  	 *  no separation or pricing is applied
807  	 *
808  	 *  The LP has to be constructed before (you can use SCIPisLPConstructed() or SCIPconstructLP()).
809  	 *
810  	 *  @note if the LP is infeasible or the objective limit is reached, and if all columns are in the LP and no external
811  	 *  pricers exist then conflict analysis will be run. This can have an effect on the problem after probing ends.
812  	 *
813  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
814  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
815  	 *
816  	 *  @pre This method can be called if @p scip is in one of the following stages:
817  	 *       - \ref SCIP_STAGE_SOLVING
818  	 */
819  	SCIP_RETCODE SCIPsolveProbingLP(
820  	   SCIP*                 scip,               /**< SCIP data structure */
821  	   int                   itlim,              /**< maximal number of LP iterations to perform, or -1 for no limit */
822  	   SCIP_Bool*            lperror,            /**< pointer to store whether an unresolved LP error occurred */
823  	   SCIP_Bool*            cutoff              /**< pointer to store whether the probing LP was infeasible or the objective
824  	                                              *   limit was reached (or NULL, if not needed) */
825  	   )
826  	{
827  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPsolveProbingLP", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
828  	
829  	   SCIP_CALL( solveProbingLP(scip, itlim, FALSE, FALSE, FALSE, -1, lperror, cutoff) );
830  	
831  	   return SCIP_OKAY;
832  	}
833  	
834  	/** solves the LP at the current probing node (cannot be applied at preprocessing stage) and applies pricing
835  	 *  until the LP is solved to optimality; no separation is applied
836  	 *
837  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
838  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
839  	 *
840  	 *  @pre This method can be called if @p scip is in one of the following stages:
841  	 *       - \ref SCIP_STAGE_SOLVING
842  	 */
843  	SCIP_RETCODE SCIPsolveProbingLPWithPricing(
844  	   SCIP*                 scip,               /**< SCIP data structure */
845  	   SCIP_Bool             pretendroot,        /**< should the pricers be called as if we were at the root node? */
846  	   SCIP_Bool             displayinfo,        /**< should info lines be displayed after each pricing round? */
847  	   int                   maxpricerounds,     /**< maximal number of pricing rounds (-1: no limit);
848  	                                              *   a finite limit means that the LP might not be solved to optimality! */
849  	   SCIP_Bool*            lperror,            /**< pointer to store whether an unresolved LP error occurred */
850  	   SCIP_Bool*            cutoff              /**< pointer to store whether the probing LP was infeasible or the objective
851  	                                              *   limit was reached (or NULL, if not needed) */
852  	   )
853  	{
854  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPsolveProbingLPWithPricing", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
855  	
856  	   SCIP_CALL( solveProbingLP(scip, -1, TRUE, pretendroot, displayinfo, maxpricerounds, lperror, cutoff) );
857  	
858  	   return SCIP_OKAY;
859  	}
860  	
861  	/** sets the LP state for the current probing node
862  	 *
863  	 *  @note state and norms are stored at the node and later released by SCIP; therefore, the pointers are set
864  	 *        to NULL by the method
865  	 *
866  	 *  @note the pointers to state and norms must not be NULL; however, they may point to a NULL pointer if the
867  	 *        respective information should not be set
868  	 *
869  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
870  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
871  	 *
872  	 *  @pre This method can be called if @p scip is in one of the following stages:
873  	 *       - \ref SCIP_STAGE_PRESOLVING
874  	 *       - \ref SCIP_STAGE_SOLVING
875  	 */
876  	SCIP_RETCODE SCIPsetProbingLPState(
877  	   SCIP*                 scip,               /**< SCIP data structure */
878  	   SCIP_LPISTATE**       lpistate,           /**< pointer to LP state information (like basis information) */
879  	   SCIP_LPINORMS**       lpinorms,           /**< pointer to LP pricing norms information */
880  	   SCIP_Bool             primalfeas,         /**< primal feasibility when LP state information was stored */
881  	   SCIP_Bool             dualfeas            /**< dual feasibility when LP state information was stored */
882  	   )
883  	{
884  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPsetProbingLPState", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
885  	
886  	   if( !SCIPtreeProbing(scip->tree) )
887  	   {
888  	      SCIPerrorMessage("not in probing mode\n");
889  	      return SCIP_INVALIDCALL;
890  	   }
891  	
892  	   SCIP_CALL( SCIPtreeSetProbingLPState(scip->tree, scip->mem->probmem, scip->lp, lpistate, lpinorms, primalfeas, dualfeas) );
893  	
894  	   return SCIP_OKAY;
895  	}
896  	
897  	/** adds a row to the LP in the current probing node
898  	 *
899  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
900  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
901  	 *
902  	 *  @pre This method can be called if @p scip is in one of the following stages:
903  	 *       - \ref SCIP_STAGE_SOLVING
904  	 *
905  	 *  See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
906  	 */
907  	SCIP_RETCODE SCIPaddRowProbing(
908  	   SCIP*                 scip,               /**< SCIP data structure */
909  	   SCIP_ROW*             row                 /**< row to be added */
910  	   )
911  	{
912  	   SCIP_NODE* node;
913  	   int depth;
914  	
915  	   assert(scip != NULL);
916  	   assert(row != NULL);
917  	
918  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPaddRowProbing", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
919  	
920  	   if( !SCIPtreeProbing(scip->tree) )
921  	   {
922  	      SCIPerrorMessage("not in probing mode\n");
923  	      return SCIP_INVALIDCALL;
924  	   }
925  	
926  	   /* get depth of current node */
927  	   node = SCIPtreeGetCurrentNode(scip->tree);
928  	   assert(node != NULL);
929  	   depth = SCIPnodeGetDepth(node);
930  	
931  	   SCIP_CALL( SCIPlpAddRow(scip->lp, scip->mem->probmem, scip->set, scip->eventqueue, scip->eventfilter, row, depth) );
932  	
933  	   return SCIP_OKAY;
934  	}
935  	
936  	
937  	/** applies the cuts in the separation storage to the LP and clears the storage afterwards;
938  	 *  this method can only be applied during probing; the user should resolve the probing LP afterwards
939  	 *  in order to get a new solution
940  	 *
941  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
942  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
943  	 *
944  	 *  @pre This method can be called if @p scip is in one of the following stages:
945  	 *       - \ref SCIP_STAGE_SOLVING
946  	 */
947  	SCIP_RETCODE SCIPapplyCutsProbing(
948  	   SCIP*                 scip,               /**< SCIP data structure */
949  	   SCIP_Bool*            cutoff              /**< pointer to store whether an empty domain was created */
950  	   )
951  	{
952  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPapplyCutsProbing", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
953  	
954  	   if( !SCIPtreeProbing(scip->tree) )
955  	   {
956  	      SCIPerrorMessage("not in probing mode\n");
957  	      return SCIP_INVALIDCALL;
958  	   }
959  	
960  	   SCIP_CALL( SCIPsepastoreApplyCuts(scip->sepastore, scip->mem->probmem, scip->set, scip->stat, scip->transprob,
961  	         scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->eventfilter,
962  	         scip->cliquetable, FALSE, SCIP_EFFICIACYCHOICE_LP, cutoff) );
963  	
964  	   return SCIP_OKAY;
965  	}
966  	
967  	/** solves relaxation(s) at the current probing node (cannot be applied at preprocessing stage);
968  	 *  no separation or pricing is applied
969  	 *
970  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
971  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
972  	 *
973  	 *  @pre This method can be called if @p scip is in one of the following stages:
974  	 *       - \ref SCIP_STAGE_SOLVING
975  	 */
976  	SCIP_RETCODE SCIPsolveProbingRelax(
977  	   SCIP*                 scip,               /**< SCIP data structure */
978  	   SCIP_Bool*            cutoff              /**< pointer to store whether a relaxation was infeasible or the objective
979  	                                              *   limit was reached (or NULL, if not needed) */
980  	   )
981  	{
982  	   SCIP_SET* set;
983  	   int r;
984  	
985  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPsolveProbingRelax", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
986  	
987  	   if ( ! SCIPtreeProbing(scip->tree) )
988  	   {
989  	      SCIPerrorMessage("not in probing mode\n");
990  	      return SCIP_INVALIDCALL;
991  	   }
992  	   assert( SCIPtreeGetCurrentDepth(scip->tree) > 0 );
993  	
994  	   assert( cutoff != NULL );
995  	   *cutoff = FALSE;
996  	
997  	   set = scip->set;
998  	
999  	   /* sort relaxators by priority */
1000 	   SCIPsetSortRelaxs(set);
1001 	
1002 	   /* solve relaxations */
1003 	   for (r = 0; r < set->nrelaxs && !(*cutoff); ++r)
1004 	   {
1005 	      SCIP_RELAX* relax;
1006 	      SCIP_Real lowerbound;
1007 	      SCIP_RESULT result;
1008 	
1009 	      lowerbound = -SCIPinfinity(scip);
1010 	
1011 	      relax = set->relaxs[r];
1012 	      assert( relax != NULL );
1013 	
1014 	      SCIP_CALL( SCIPrelaxExec(relax, set, scip->tree, scip->stat, SCIPtreeGetCurrentDepth(scip->tree), &lowerbound, &result) );
1015 	
1016 	      switch( result )
1017 	      {
1018 	      case SCIP_CUTOFF:
1019 	         *cutoff = TRUE;
1020 	         SCIPdebugMsg(scip, " -> relaxator <%s> detected cutoff\n", SCIPrelaxGetName(relax));
1021 	         break;
1022 	
1023 	      case SCIP_CONSADDED:
1024 	      case SCIP_REDUCEDDOM:
1025 	      case SCIP_SEPARATED:
1026 	      case SCIP_SUSPENDED:
1027 	         SCIPerrorMessage("The relaxator should not return <%d> within probing mode.\n", result);
1028 	         break;
1029 	
1030 	      case SCIP_SUCCESS:
1031 	      case SCIP_DIDNOTRUN:
1032 	         break;
1033 	
1034 	      default:
1035 	         SCIPerrorMessage("Invalid result code <%d> of relaxator <%s>\n", result, SCIPrelaxGetName(relax));
1036 	         return SCIP_INVALIDRESULT;
1037 	      }  /*lint !e788*/
1038 	   }
1039 	
1040 	   return SCIP_OKAY;
1041 	}
1042 	
1043 	/** print statistics of probing */
1044 	char* SCIPsnprintfProbingStats(
1045 	   SCIP*                 scip,               /**< SCIP data structure */
1046 	   char*                 strbuf,             /**< string buffer */
1047 	   int                   len                 /**< length of string buffer */
1048 	   )
1049 	{
1050 	   char* ptr = strbuf;
1051 	   const int nvartypes = 4;
1052 	
1053 	   assert(scip != NULL);
1054 	   assert(strbuf != NULL);
1055 	
1056 	   if( SCIPinProbing(scip) )
1057 	   {
1058 	      SCIP_VAR** vars;
1059 	      int nbinvars = SCIPgetNBinVars(scip);
1060 	      int nintvars = SCIPgetNIntVars(scip);
1061 	      int nimplvars = SCIPgetNImplVars(scip);
1062 	      int nvars = SCIPgetNVars(scip);
1063 	      int vartypeend[] = {
1064 	            nbinvars,
1065 	            nbinvars + nintvars,
1066 	            nbinvars + nintvars + nimplvars,
1067 	            nvars
1068 	      };
1069 	      const char* vartypenames[] = {
1070 	            "binary",
1071 	            "integer",
1072 	            "implicit integer",
1073 	            "continuous"
1074 	      };
1075 	      int nvartypefixed[4];
1076 	      int nvarsfixed = 0;
1077 	      int depth;
1078 	      int probingdepth;
1079 	      int vartypestart = 0;
1080 	      int v;
1081 	      int p;
1082 	
1083 	      vars = SCIPgetVars(scip);
1084 	      BMSclearMemoryArray(nvartypefixed, nvartypes);
1085 	
1086 	      /* loop over vartypes and count fixings */
1087 	      for( p = 0; p < nvartypes; ++p )
1088 	      {
1089 	         for( v = vartypestart; v < vartypeend[p]; ++v )
1090 	         {
1091 	            if( SCIPisEQ(scip, SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v])) )
1092 	               ++nvartypefixed[p];
1093 	         }
1094 	         nvarsfixed += nvartypefixed[p];
1095 	         vartypestart = vartypeend[p];
1096 	      }
1097 	
1098 	      depth = SCIPgetDepth(scip);
1099 	      probingdepth = SCIPgetProbingDepth(scip);
1100 	
1101 	      ptr += SCIPsnprintf(ptr, len, "Depth: (%d total, %d probing) ", depth, probingdepth);
1102 	      ptr += SCIPsnprintf(ptr, len, "Fixed/Variables: %d / %d (", nvarsfixed, vartypeend[nvartypes - 1]);
1103 	
1104 	      for( p = 0; p < nvartypes; ++p )
1105 	      {
1106 	         int ntypevars = vartypeend[p] - (p == 0 ? 0 : vartypeend[p - 1]);
1107 	         ptr += SCIPsnprintf(ptr, len, "%d / %d %s%s", nvartypefixed[p], ntypevars, vartypenames[p], p < (nvartypes - 1) ? ", " : ")");
1108 	      }
1109 	   }
1110 	   else
1111 	   {
1112 	      (void) SCIPsnprintf(strbuf, len, "Not in probing");
1113 	   }
1114 	
1115 	   return strbuf;
1116 	}
1117 	
1118 	/** gets the candidate score and preferred rounding direction for a candidate variable */
1119 	SCIP_RETCODE SCIPgetDivesetScore(
1120 	   SCIP*                 scip,               /**< SCIP data structure */
1121 	   SCIP_DIVESET*         diveset,            /**< general diving settings */
1122 	   SCIP_DIVETYPE         divetype,           /**< represents different methods for a dive set to explore the next children */
1123 	   SCIP_VAR*             divecand,           /**< the candidate for which the branching direction is requested */
1124 	   SCIP_Real             divecandsol,        /**< LP solution value of the candidate */
1125 	   SCIP_Real             divecandfrac,       /**< fractionality of the candidate */
1126 	   SCIP_Real*            candscore,          /**< pointer to store the candidate score */
1127 	   SCIP_Bool*            roundup             /**< pointer to store whether preferred direction for diving is upwards */
1128 	   )
1129 	{
1130 	   assert(scip != NULL);
1131 	   assert(candscore != NULL);
1132 	   assert(roundup != NULL);
1133 	   assert(divecand != NULL);
1134 	
1135 	   SCIP_CALL( SCIPcheckStage(scip, "SCIPgetDivesetScore", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1136 	
1137 	   SCIP_CALL( SCIPdivesetGetScore(diveset, scip->set, divetype, divecand, divecandsol, divecandfrac, candscore,
1138 	         roundup) );
1139 	
1140 	   return SCIP_OKAY;
1141 	}
1142 	
1143 	/** update diveset LP statistics, should be called after every LP solved by this diving heuristic */
1144 	void SCIPupdateDivesetLPStats(
1145 	   SCIP*                 scip,               /**< SCIP data structure */
1146 	   SCIP_DIVESET*         diveset,            /**< diving settings */
1147 	   SCIP_Longint          niterstoadd,        /**< additional number of LP iterations to be added */
1148 	   SCIP_DIVECONTEXT      divecontext         /**< context for diving statistics */
1149 	   )
1150 	{
1151 	   assert(scip != NULL);
1152 	   assert(diveset != NULL);
1153 	
1154 	   SCIPdivesetUpdateLPStats(diveset, scip->stat, niterstoadd, divecontext);
1155 	}
1156 	
1157 	/** update diveset statistics and global diveset statistics */
1158 	void SCIPupdateDivesetStats(
1159 	   SCIP*                 scip,               /**< SCIP data structure */
1160 	   SCIP_DIVESET*         diveset,            /**< diveset to be reset */
1161 	   int                   nprobingnodes,      /**< the number of probing nodes explored this time */
1162 	   int                   nbacktracks,        /**< the number of backtracks during probing this time */
1163 	   SCIP_Longint          nsolsfound,         /**< the number of solutions found */
1164 	   SCIP_Longint          nbestsolsfound,     /**< the number of best solutions found */
1165 	   SCIP_Longint          nconflictsfound,    /**< number of new conflicts found this time */
1166 	   SCIP_Bool             leavewassol,        /**< was a solution found at the leaf? */
1167 	   SCIP_DIVECONTEXT      divecontext         /**< context for diving statistics */
1168 	   )
1169 	{
1170 	   assert(scip != NULL);
1171 	   assert(diveset != NULL);
1172 	   assert(SCIPinProbing(scip));
1173 	
1174 	   SCIPdivesetUpdateStats(diveset, scip->stat, SCIPgetDepth(scip), nprobingnodes, nbacktracks, nsolsfound,
1175 	         nbestsolsfound, nconflictsfound, leavewassol, divecontext);
1176 	}
1177 	
1178 	/** enforces a probing/diving solution by suggesting bound changes that maximize the score w.r.t. the current diving settings
1179 	 *
1180 	 *  the process is guided by the enforcement priorities of the constraint handlers and the scoring mechanism provided by
1181 	 *  the dive set.
1182 	 *  Constraint handlers may suggest diving bound changes in decreasing order of their enforcement priority, based on the
1183 	 *  solution values in the solution @p sol and the current local bounds of the variables. A diving bound change
1184 	 *  is a triple (variable,branching direction,value) and is used inside SCIPperformGenericDivingAlgorithm().
1185 	 *
1186 	 *  After a successful call, SCIP holds two arrays of suggested dive bound changes, one for the preferred child
1187 	 *  and one for the alternative.
1188 	 *
1189 	 *  @see SCIPgetDiveBoundChangeData() for retrieving the dive bound change suggestions.
1190 	 *
1191 	 *  The method stops after the first constraint handler was successful
1192 	 *
1193 	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1194 	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
1195 	 *
1196 	 *  @pre This method can be called if @p scip is in one of the following stages:
1197 	 *       - \ref SCIP_STAGE_SOLVING
1198 	 *
1199 	 *  See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1200 	 */
1201 	SCIP_RETCODE SCIPgetDiveBoundChanges(
1202 	   SCIP*                 scip,               /**< SCIP data structure */
1203 	   SCIP_DIVESET*         diveset,            /**< diving settings to control scoring */
1204 	   SCIP_SOL*             sol,                /**< current solution of diving mode */
1205 	   SCIP_Bool*            success,            /**< pointer to store whether constraint handler successfully found a variable */
1206 	   SCIP_Bool*            infeasible          /**< pointer to store whether the current node was detected to be infeasible */
1207 	   )
1208 	{
1209 	   int i;
1210 	
1211 	   assert(scip != NULL);
1212 	   assert(diveset != NULL);
1213 	   assert(SCIPinProbing(scip));
1214 	   assert(infeasible != NULL);
1215 	   assert(success != NULL);
1216 	
1217 	   SCIP_CALL( SCIPcheckStage(scip, "SCIPgetDiveBoundChanges", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1218 	
1219 	   *success = FALSE;
1220 	   *infeasible = FALSE;
1221 	
1222 	   /* we invalidate the previously stored bound changes */
1223 	   SCIPclearDiveBoundChanges(scip);
1224 	
1225 	   /* loop over constraint handlers until a constraint handler successfully found a variable/value assignment for proceeding
1226 	    * or a constraint handler detected the infeasibility of the local node
1227 	    */
1228 	   for( i = 0; i < scip->set->nconshdlrs && !(*success || *infeasible); ++i )
1229 	   {
1230 	      SCIP_CALL( SCIPconshdlrGetDiveBoundChanges(scip->set->conshdlrs_enfo[i], scip->set, diveset, sol,
1231 	            success, infeasible) );
1232 	   }
1233 	
1234 	#ifndef NDEBUG
1235 	   /* check if the constraint handler correctly assigned values to the dive set */
1236 	   if( *success )
1237 	   {
1238 	      SCIP_VAR** bdchgvars;
1239 	      SCIP_BRANCHDIR* bdchgdirs;
1240 	      SCIP_Real* values;
1241 	      int nbdchanges;
1242 	      SCIPtreeGetDiveBoundChangeData(scip->tree, &bdchgvars, &bdchgdirs, &values, &nbdchanges, TRUE);
1243 	      assert(nbdchanges > 0);
1244 	      SCIPtreeGetDiveBoundChangeData(scip->tree, &bdchgvars, &bdchgdirs, &values, &nbdchanges, FALSE);
1245 	      assert(nbdchanges > 0);
1246 	   }
1247 	#endif
1248 	
1249 	   return SCIP_OKAY;
1250 	}
1251 	
1252 	/** adds a diving bound change to the diving bound change storage of SCIP together with the information if this is a
1253 	 *  bound change for the preferred direction or not
1254 	 *
1255 	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1256 	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
1257 	 *
1258 	 *  @pre This method can be called if @p scip is in one of the following stages:
1259 	 *       - \ref SCIP_STAGE_SOLVING
1260 	 *
1261 	 *  See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1262 	 */
1263 	SCIP_RETCODE SCIPaddDiveBoundChange(
1264 	   SCIP*                 scip,               /**< SCIP data structure */
1265 	   SCIP_VAR*             var,                /**< variable to apply the bound change to */
1266 	   SCIP_BRANCHDIR        dir,                /**< direction of the bound change */
1267 	   SCIP_Real             value,              /**< value to adjust this variable bound to */
1268 	   SCIP_Bool             preferred           /**< is this a bound change for the preferred child? */
1269 	   )
1270 	{
1271 	   assert(scip->tree != NULL);
1272 	   assert(scip->mem->probmem != NULL);
1273 	   assert(SCIPinProbing(scip));
1274 	
1275 	   SCIP_CALL( SCIPcheckStage(scip, "SCIPaddDiveBoundChange", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1276 	
1277 	   SCIP_CALL( SCIPtreeAddDiveBoundChange(scip->tree, scip->mem->probmem, var, dir, value, preferred) );
1278 	
1279 	   return SCIP_OKAY;
1280 	}
1281 	
1282 	/** get the dive bound change data for the preferred or the alternative direction
1283 	 *
1284 	 *   @pre This method can be called if @p scip is in one of the following stages:
1285 	 *       - \ref SCIP_STAGE_SOLVING
1286 	 *
1287 	 *  See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1288 	 */
1289 	void SCIPgetDiveBoundChangeData(
1290 	   SCIP*                 scip,               /**< SCIP data structure */
1291 	   SCIP_VAR***           variables,          /**< pointer to store variables for the specified direction */
1292 	   SCIP_BRANCHDIR**      directions,         /**< pointer to store the branching directions */
1293 	   SCIP_Real**           values,             /**< pointer to store bound change values */
1294 	   int*                  ndivebdchgs,        /**< pointer to store the number of dive bound changes */
1295 	   SCIP_Bool             preferred           /**< should the dive bound changes for the preferred child be output? */
1296 	   )
1297 	{
1298 	   assert(variables != NULL);
1299 	   assert(directions != NULL);
1300 	   assert(values != NULL);
1301 	   assert(ndivebdchgs != NULL);
1302 	   assert(SCIPinProbing(scip));
1303 	
1304 	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetDiveBoundChangeData", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1305 	
1306 	   SCIPtreeGetDiveBoundChangeData(scip->tree, variables, directions, values, ndivebdchgs, preferred);
1307 	}
1308 	
1309 	/** clear the dive bound change data structures
1310 	 *
1311 	 *  @pre This method can be called if @p scip is in one of the following stages:
1312 	 *       - \ref SCIP_STAGE_SOLVING
1313 	 *
1314 	 *  See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1315 	 */
1316 	void SCIPclearDiveBoundChanges(
1317 	   SCIP*                 scip                /**< SCIP data structure */
1318 	   )
1319 	{
1320 	   assert(scip->tree != NULL);
1321 	
1322 	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPclearDiveBoundChanges", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1323 	
1324 	   SCIPtreeClearDiveBoundChanges(scip->tree);
1325 	}
1326