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_conflict.c
26   	 * @ingroup OTHER_CFILES
27   	 * @brief  public methods for conflict handler plugins and conflict analysis
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 "scip/conflict.h"
46   	#include "scip/debug.h"
47   	#include "scip/pub_cons.h"
48   	#include "scip/pub_message.h"
49   	#include "scip/pub_var.h"
50   	#include "scip/scip_conflict.h"
51   	#include "scip/scip_tree.h"
52   	#include "scip/set.h"
53   	#include "scip/struct_mem.h"
54   	#include "scip/struct_scip.h"
55   	#include "scip/struct_set.h"
56   	#include "scip/struct_var.h"
57   	
58   	/** creates a conflict handler and includes it in SCIP
59   	 *
60   	 *  @note method has all conflict handler callbacks as arguments and is thus changed every time a new
61   	 *        callback is added
62   	 *        in future releases; consider using SCIPincludeConflicthdlrBasic() and setter functions
63   	 *        if you seek for a method which is less likely to change in future releases
64   	 */
65   	SCIP_RETCODE SCIPincludeConflicthdlr(
66   	   SCIP*                 scip,               /**< SCIP data structure */
67   	   const char*           name,               /**< name of conflict handler */
68   	   const char*           desc,               /**< description of conflict handler */
69   	   int                   priority,           /**< priority of the conflict handler */
70   	   SCIP_DECL_CONFLICTCOPY((*conflictcopy)),  /**< copy method of conflict handler or NULL if you don't want to copy your plugin into sub-SCIPs */
71   	   SCIP_DECL_CONFLICTFREE((*conflictfree)),  /**< destructor of conflict handler */
72   	   SCIP_DECL_CONFLICTINIT((*conflictinit)),  /**< initialize conflict handler */
73   	   SCIP_DECL_CONFLICTEXIT((*conflictexit)),  /**< deinitialize conflict handler */
74   	   SCIP_DECL_CONFLICTINITSOL((*conflictinitsol)),/**< solving process initialization method of conflict handler */
75   	   SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol)),/**< solving process deinitialization method of conflict handler */
76   	   SCIP_DECL_CONFLICTEXEC((*conflictexec)),  /**< conflict processing method of conflict handler */
77   	   SCIP_CONFLICTHDLRDATA* conflicthdlrdata   /**< conflict handler data */
78   	   )
79   	{
80   	   SCIP_CONFLICTHDLR* conflicthdlr;
81   	
82   	   SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeConflicthdlr", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
83   	
84   	   /* check whether conflict handler is already present */
85   	   if( SCIPfindConflicthdlr(scip, name) != NULL )
86   	   {
87   	      SCIPerrorMessage("conflict handler <%s> already included.\n", name);
88   	      return SCIP_INVALIDDATA;
89   	   }
90   	
91   	   SCIP_CALL( SCIPconflicthdlrCreate(&conflicthdlr, scip->set, scip->messagehdlr, scip->mem->setmem, name, desc, priority,
92   	         conflictcopy,
93   	         conflictfree, conflictinit, conflictexit, conflictinitsol, conflictexitsol, conflictexec,
94   	         conflicthdlrdata) );
95   	   SCIP_CALL( SCIPsetIncludeConflicthdlr(scip->set, conflicthdlr) );
96   	
97   	   return SCIP_OKAY;
98   	}
99   	
100  	/** creates a conflict handler and includes it in SCIP with its most fundamental callbacks. All non-fundamental
101  	 *  (or optional) callbacks as, e.g., init and exit callbacks, will be set to NULL.
102  	 *  Optional callbacks can be set via specific setter functions SCIPsetConflicthdlrCopy(), SCIPsetConflicthdlrFree(),
103  	 *  SCIPsetConflicthdlrInit(), SCIPsetConflicthdlrExit(), SCIPsetConflicthdlrInitsol(),
104  	 *  and SCIPsetConflicthdlrExitsol()
105  	 *
106  	 *  @note if you want to set all callbacks with a single method call, consider using SCIPincludeConflicthdlr() instead
107  	 */
108  	SCIP_RETCODE SCIPincludeConflicthdlrBasic(
109  	   SCIP*                 scip,               /**< SCIP data structure */
110  	   SCIP_CONFLICTHDLR**   conflicthdlrptr,    /**< reference to a conflict handler pointer, or NULL */
111  	   const char*           name,               /**< name of conflict handler */
112  	   const char*           desc,               /**< description of conflict handler */
113  	   int                   priority,           /**< priority of the conflict handler */
114  	   SCIP_DECL_CONFLICTEXEC((*conflictexec)),  /**< conflict processing method of conflict handler */
115  	   SCIP_CONFLICTHDLRDATA* conflicthdlrdata   /**< conflict handler data */
116  	   )
117  	{
118  	   SCIP_CONFLICTHDLR* conflicthdlr;
119  	
120  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeConflicthdlrBasic", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
121  	
122  	   /* check whether conflict handler is already present */
123  	   if( SCIPfindConflicthdlr(scip, name) != NULL )
124  	   {
125  	      SCIPerrorMessage("conflict handler <%s> already included.\n", name);
126  	      return SCIP_INVALIDDATA;
127  	   }
128  	
129  	   SCIP_CALL( SCIPconflicthdlrCreate(&conflicthdlr, scip->set, scip->messagehdlr, scip->mem->setmem, name, desc, priority,
130  	         NULL, NULL, NULL, NULL, NULL, NULL, conflictexec, conflicthdlrdata) );
131  	   SCIP_CALL( SCIPsetIncludeConflicthdlr(scip->set, conflicthdlr) );
132  	
133  	   if( conflicthdlrptr != NULL )
134  	      *conflicthdlrptr = conflicthdlr;
135  	
136  	   return SCIP_OKAY;
137  	}
138  	
139  	/** set copy method of conflict handler */
140  	SCIP_RETCODE SCIPsetConflicthdlrCopy(
141  	   SCIP*                 scip,               /**< SCIP data structure */
142  	   SCIP_CONFLICTHDLR*    conflicthdlr,       /**< conflict handler */
143  	   SCIP_DECL_CONFLICTCOPY((*conflictcopy))   /**< copy method of conflict handler */
144  	   )
145  	{
146  	   assert(scip != NULL);
147  	
148  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPsetConflicthdlrCopy", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
149  	
150  	   SCIPconflicthdlrSetCopy(conflicthdlr, conflictcopy);
151  	
152  	   return SCIP_OKAY;
153  	}
154  	
155  	/** set destructor of conflict handler */
156  	SCIP_RETCODE SCIPsetConflicthdlrFree(
157  	   SCIP*                 scip,               /**< SCIP data structure */
158  	   SCIP_CONFLICTHDLR*    conflicthdlr,       /**< conflict handler */
159  	   SCIP_DECL_CONFLICTFREE((*conflictfree))   /**< destructor of conflict handler */
160  	   )
161  	{
162  	   assert(scip != NULL);
163  	
164  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPsetConflicthdlrFree", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
165  	
166  	   SCIPconflicthdlrSetFree(conflicthdlr, conflictfree);
167  	
168  	   return SCIP_OKAY;
169  	}
170  	
171  	/** set initialization method of conflict handler */
172  	SCIP_RETCODE SCIPsetConflicthdlrInit(
173  	   SCIP*                 scip,               /**< SCIP data structure */
174  	   SCIP_CONFLICTHDLR*    conflicthdlr,       /**< conflict handler */
175  	   SCIP_DECL_CONFLICTINIT((*conflictinit))   /**< initialize conflict handler */
176  	   )
177  	{
178  	   assert(scip != NULL);
179  	
180  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPsetConflicthdlrInit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
181  	
182  	   SCIPconflicthdlrSetInit(conflicthdlr, conflictinit);
183  	
184  	   return SCIP_OKAY;
185  	}
186  	
187  	/** set deinitialization method of conflict handler */
188  	SCIP_RETCODE SCIPsetConflicthdlrExit(
189  	   SCIP*                 scip,               /**< SCIP data structure */
190  	   SCIP_CONFLICTHDLR*    conflicthdlr,       /**< conflict handler */
191  	   SCIP_DECL_CONFLICTEXIT((*conflictexit))   /**< deinitialize conflict handler */
192  	   )
193  	{
194  	   assert(scip != NULL);
195  	
196  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPsetConflicthdlrExit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
197  	
198  	   SCIPconflicthdlrSetExit(conflicthdlr, conflictexit);
199  	
200  	   return SCIP_OKAY;
201  	}
202  	
203  	/** set solving process initialization method of conflict handler */
204  	SCIP_RETCODE SCIPsetConflicthdlrInitsol(
205  	   SCIP*                 scip,               /**< SCIP data structure */
206  	   SCIP_CONFLICTHDLR*    conflicthdlr,       /**< conflict handler */
207  	   SCIP_DECL_CONFLICTINITSOL((*conflictinitsol))/**< solving process initialization method of conflict handler */
208  	   )
209  	{
210  	   assert(scip != NULL);
211  	
212  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPsetConflicthdlrInitsol", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
213  	
214  	   SCIPconflicthdlrSetInitsol(conflicthdlr, conflictinitsol);
215  	
216  	   return SCIP_OKAY;
217  	}
218  	
219  	/** set solving process deinitialization method of conflict handler */
220  	SCIP_RETCODE SCIPsetConflicthdlrExitsol(
221  	   SCIP*                 scip,               /**< SCIP data structure */
222  	   SCIP_CONFLICTHDLR*    conflicthdlr,       /**< conflict handler */
223  	   SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol))/**< solving process deinitialization method of conflict handler */
224  	   )
225  	{
226  	   assert(scip != NULL);
227  	
228  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPsetConflicthdlrExitsol", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
229  	
230  	   SCIPconflicthdlrSetExitsol(conflicthdlr, conflictexitsol);
231  	
232  	   return SCIP_OKAY;
233  	}
234  	
235  	/** returns the conflict handler of the given name, or NULL if not existing */
236  	SCIP_CONFLICTHDLR* SCIPfindConflicthdlr(
237  	   SCIP*                 scip,               /**< SCIP data structure */
238  	   const char*           name                /**< name of conflict handler */
239  	   )
240  	{
241  	   assert(scip != NULL);
242  	   assert(scip->set != NULL);
243  	   assert(name != NULL);
244  	
245  	   return SCIPsetFindConflicthdlr(scip->set, name);
246  	}
247  	
248  	/** returns the array of currently available conflict handlers */
249  	SCIP_CONFLICTHDLR** SCIPgetConflicthdlrs(
250  	   SCIP*                 scip                /**< SCIP data structure */
251  	   )
252  	{
253  	   assert(scip != NULL);
254  	   assert(scip->set != NULL);
255  	
256  	   SCIPsetSortConflicthdlrs(scip->set);
257  	
258  	   return scip->set->conflicthdlrs;
259  	}
260  	
261  	/** returns the number of currently available conflict handlers */
262  	int SCIPgetNConflicthdlrs(
263  	   SCIP*                 scip                /**< SCIP data structure */
264  	   )
265  	{
266  	   assert(scip != NULL);
267  	   assert(scip->set != NULL);
268  	
269  	   return scip->set->nconflicthdlrs;
270  	}
271  	
272  	/** sets the priority of a conflict handler */
273  	SCIP_RETCODE SCIPsetConflicthdlrPriority(
274  	   SCIP*                 scip,               /**< SCIP data structure */
275  	   SCIP_CONFLICTHDLR*    conflicthdlr,       /**< conflict handler */
276  	   int                   priority            /**< new priority of the conflict handler */
277  	   )
278  	{
279  	   assert(scip != NULL);
280  	   assert(scip->set != NULL);
281  	
282  	   SCIPconflicthdlrSetPriority(conflicthdlr, scip->set, priority);
283  	
284  	   return SCIP_OKAY;
285  	}
286  	
287  	/** return TRUE if conflict analysis is applicable; In case the function return FALSE there is no need to initialize the
288  	 *  conflict analysis since it will not be applied
289  	 *
290  	 *  @return return TRUE if conflict analysis is applicable; In case the function return FALSE there is no need to initialize the
291  	 *          conflict analysis since it will not be applied
292  	 *
293  	 *  @pre This method can be called if SCIP is in one of the following stages:
294  	 *       - \ref SCIP_STAGE_INITPRESOLVE
295  	 *       - \ref SCIP_STAGE_PRESOLVING
296  	 *       - \ref SCIP_STAGE_EXITPRESOLVE
297  	 *       - \ref SCIP_STAGE_SOLVING
298  	 *
299  	 *  @note SCIP stage does not get changed
300  	 */
301  	SCIP_Bool SCIPisConflictAnalysisApplicable(
302  	   SCIP*                 scip                /**< SCIP data structure */
303  	   )
304  	{
305  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPisConflictAnalysisApplicable", FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
306  	
307  	   return (SCIPgetDepth(scip) > 0 && SCIPconflictApplicable(scip->set));
308  	}
309  	
310  	/** initializes the conflict analysis by clearing the conflict candidate queue; this method must be called before you
311  	 *  enter the conflict variables by calling SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPaddConflictBd(),
312  	 *  SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), SCIPaddConflictRelaxedBd(), or SCIPaddConflictBinvar();
313  	 *
314  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
315  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
316  	 *
317  	 *  @pre This method can be called if SCIP is in one of the following stages:
318  	 *       - \ref SCIP_STAGE_PRESOLVING
319  	 *       - \ref SCIP_STAGE_SOLVING
320  	 *
321  	 *  @note SCIP stage does not get changed
322  	 */
323  	SCIP_RETCODE SCIPinitConflictAnalysis(
324  	   SCIP*                 scip,               /**< SCIP data structure */
325  	   SCIP_CONFTYPE         conftype,           /**< type of conflict */
326  	   SCIP_Bool             iscutoffinvolved    /**< is the current cutoff bound involved? */
327  	   )
328  	{
329  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPinitConflictAnalysis", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
330  	
331  	   SCIP_CALL( SCIPconflictInit(scip->conflict, scip->set, scip->stat, scip->transprob, conftype, iscutoffinvolved) );
332  	
333  	   return SCIP_OKAY;
334  	}
335  	
336  	/** adds lower bound of variable at the time of the given bound change index to the conflict analysis' candidate storage;
337  	 *  this method should be called in one of the following two cases:
338  	 *   1. Before calling the SCIPanalyzeConflict() method, SCIPaddConflictLb() should be called for each lower bound
339  	 *      that led to the conflict (e.g. the infeasibility of globally or locally valid constraint).
340  	 *   2. In the propagation conflict resolving method of a constraint handler, SCIPaddConflictLb() should be called
341  	 *      for each lower bound, whose current assignment led to the deduction of the given conflict bound.
342  	 *
343  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
344  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
345  	 *
346  	 *  @pre This method can be called if SCIP is in one of the following stages:
347  	 *       - \ref SCIP_STAGE_PRESOLVING
348  	 *       - \ref SCIP_STAGE_SOLVING
349  	 *
350  	 *  @note SCIP stage does not get changed
351  	 */
352  	SCIP_RETCODE SCIPaddConflictLb(
353  	   SCIP*                 scip,               /**< SCIP data structure */
354  	   SCIP_VAR*             var,                /**< variable whose lower bound should be added to conflict candidate queue */
355  	   SCIP_BDCHGIDX*        bdchgidx            /**< bound change index representing time on path to current node, when the
356  	                                              *   conflicting bound was valid, NULL for current local bound */
357  	   )
358  	{
359  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPaddConflictLb", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
360  	
361  	   assert( var->scip == scip );
362  	
363  	   SCIP_CALL( SCIPconflictAddBound(scip->conflict, scip->mem->probmem, scip->set, scip->stat, var, SCIP_BOUNDTYPE_LOWER, bdchgidx) );
364  	
365  	   return SCIP_OKAY;
366  	}
367  	
368  	/** adds lower bound of variable at the time of the given bound change index to the conflict analysis' candidate storage
369  	 *  with the additional information of a relaxed lower bound; this relaxed lower bound is the one which would be enough
370  	 *  to explain a certain bound change;
371  	 *  this method should be called in one of the following two cases:
372  	 *   1. Before calling the SCIPanalyzeConflict() method, SCIPaddConflictRelaxedLb() should be called for each (relaxed) lower bound
373  	 *      that led to the conflict (e.g. the infeasibility of globally or locally valid constraint).
374  	 *   2. In the propagation conflict resolving method of a constraint handler, SCIPaddConflictRelexedLb() should be called
375  	 *      for each (relaxed) lower bound, whose current assignment led to the deduction of the given conflict bound.
376  	 *
377  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
378  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
379  	 *
380  	 *  @pre This method can be called if SCIP is in one of the following stages:
381  	 *       - \ref SCIP_STAGE_PRESOLVING
382  	 *       - \ref SCIP_STAGE_SOLVING
383  	 *
384  	 *  @note SCIP stage does not get changed
385  	 */
386  	SCIP_RETCODE SCIPaddConflictRelaxedLb(
387  	   SCIP*                 scip,               /**< SCIP data structure */
388  	   SCIP_VAR*             var,                /**< variable whose lower bound should be added to conflict candidate queue */
389  	   SCIP_BDCHGIDX*        bdchgidx,           /**< bound change index representing time on path to current node, when the
390  	                                              *   conflicting bound was valid, NULL for current local bound */
391  	   SCIP_Real             relaxedlb           /**< the relaxed lower bound */
392  	   )
393  	{
394  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPaddConflictRelaxedLb", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
395  	
396  	   assert( var->scip == scip );
397  	
398  	   SCIP_CALL( SCIPconflictAddRelaxedBound(scip->conflict, scip->mem->probmem, scip->set, scip->stat, var, SCIP_BOUNDTYPE_LOWER, bdchgidx, relaxedlb) );
399  	
400  	   return SCIP_OKAY;
401  	}
402  	
403  	/** adds upper bound of variable at the time of the given bound change index to the conflict analysis' candidate storage;
404  	 *  this method should be called in one of the following two cases:
405  	 *   1. Before calling the SCIPanalyzeConflict() method, SCIPaddConflictUb() should be called for each upper bound that
406  	 *      led to the conflict (e.g. the infeasibility of globally or locally valid constraint).
407  	 *   2. In the propagation conflict resolving method of a constraint handler, SCIPaddConflictUb() should be called for
408  	 *      each upper bound, whose current assignment led to the deduction of the given conflict bound.
409  	 *
410  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
411  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
412  	 *
413  	 *  @pre This method can be called if SCIP is in one of the following stages:
414  	 *       - \ref SCIP_STAGE_PRESOLVING
415  	 *       - \ref SCIP_STAGE_SOLVING
416  	 *
417  	 *  @note SCIP stage does not get changed
418  	 */
419  	SCIP_RETCODE SCIPaddConflictUb(
420  	   SCIP*                 scip,               /**< SCIP data structure */
421  	   SCIP_VAR*             var,                /**< variable whose upper bound should be added to conflict candidate queue */
422  	   SCIP_BDCHGIDX*        bdchgidx            /**< bound change index representing time on path to current node, when the
423  	                                              *   conflicting bound was valid, NULL for current local bound */
424  	   )
425  	{
426  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPaddConflictUb", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
427  	
428  	   assert( var->scip == scip );
429  	
430  	   SCIP_CALL( SCIPconflictAddBound(scip->conflict, scip->mem->probmem, scip->set, scip->stat, var, SCIP_BOUNDTYPE_UPPER, bdchgidx) );
431  	
432  	   return SCIP_OKAY;
433  	}
434  	
435  	/** adds upper bound of variable at the time of the given bound change index to the conflict analysis' candidate storage
436  	 *  with the additional information of a relaxed upper bound; this relaxed upper bound is the one which would be enough
437  	 *  to explain a certain bound change;
438  	 *  this method should be called in one of the following two cases:
439  	 *   1. Before calling the SCIPanalyzeConflict() method, SCIPaddConflictRelaxedUb() should be called for each (relaxed) upper
440  	 *      bound that led to the conflict (e.g. the infeasibility of globally or locally valid constraint).
441  	 *   2. In the propagation conflict resolving method of a constraint handler, SCIPaddConflictRelaxedUb() should be
442  	 *      called for each (relaxed) upper bound, whose current assignment led to the deduction of the given conflict
443  	 *      bound.
444  	 *
445  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
446  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
447  	 *
448  	 *  @pre This method can be called if SCIP is in one of the following stages:
449  	 *       - \ref SCIP_STAGE_PRESOLVING
450  	 *       - \ref SCIP_STAGE_SOLVING
451  	 *
452  	 *  @note SCIP stage does not get changed
453  	 */
454  	SCIP_RETCODE SCIPaddConflictRelaxedUb(
455  	   SCIP*                 scip,               /**< SCIP data structure */
456  	   SCIP_VAR*             var,                /**< variable whose upper bound should be added to conflict candidate queue */
457  	   SCIP_BDCHGIDX*        bdchgidx,           /**< bound change index representing time on path to current node, when the
458  	                                              *   conflicting bound was valid, NULL for current local bound */
459  	   SCIP_Real             relaxedub           /**< the relaxed upper bound */
460  	   )
461  	{
462  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPaddConflictRelaxedUb", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
463  	
464  	   assert( var->scip == scip );
465  	
466  	   SCIP_CALL( SCIPconflictAddRelaxedBound(scip->conflict, scip->mem->probmem, scip->set, scip->stat, var, SCIP_BOUNDTYPE_UPPER, bdchgidx, relaxedub) );
467  	
468  	   return SCIP_OKAY;
469  	}
470  	
471  	/** adds lower or upper bound of variable at the time of the given bound change index to the conflict analysis' candidate
472  	 *  storage; this method should be called in one of the following two cases:
473  	 *   1. Before calling the SCIPanalyzeConflict() method, SCIPaddConflictBd() should be called for each bound
474  	 *      that led to the conflict (e.g. the infeasibility of globally or locally valid constraint).
475  	 *   2. In the propagation conflict resolving method of a constraint handler, SCIPaddConflictBd() should be called
476  	 *      for each bound, whose current assignment led to the deduction of the given conflict bound.
477  	 *
478  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
479  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
480  	 *
481  	 *  @pre This method can be called if SCIP is in one of the following stages:
482  	 *       - \ref SCIP_STAGE_PRESOLVING
483  	 *       - \ref SCIP_STAGE_SOLVING
484  	 *
485  	 *  @note SCIP stage does not get changed
486  	 */
487  	SCIP_RETCODE SCIPaddConflictBd(
488  	   SCIP*                 scip,               /**< SCIP data structure */
489  	   SCIP_VAR*             var,                /**< variable whose upper bound should be added to conflict candidate queue */
490  	   SCIP_BOUNDTYPE        boundtype,          /**< the type of the conflicting bound (lower or upper bound) */
491  	   SCIP_BDCHGIDX*        bdchgidx            /**< bound change index representing time on path to current node, when the
492  	                                              *   conflicting bound was valid, NULL for current local bound */
493  	   )
494  	{
495  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPaddConflictBd", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
496  	
497  	   assert( var->scip == scip );
498  	
499  	   SCIP_CALL( SCIPconflictAddBound(scip->conflict, scip->mem->probmem, scip->set, scip->stat, var, boundtype, bdchgidx) );
500  	
501  	   return SCIP_OKAY;
502  	}
503  	
504  	/** adds lower or upper bound of variable at the time of the given bound change index to the conflict analysis'
505  	 *  candidate storage; with the additional information of a relaxed upper bound; this relaxed upper bound is the one
506  	 *  which would be enough to explain a certain bound change;
507  	 *  this method should be called in one of the following two cases:
508  	 *   1. Before calling the SCIPanalyzeConflict() method, SCIPaddConflictRelaxedBd() should be called for each (relaxed)
509  	 *      bound that led to the conflict (e.g. the infeasibility of globally or locally valid constraint).
510  	 *   2. In the propagation conflict resolving method of a constraint handler, SCIPaddConflictRelaxedBd() should be
511  	 *      called for each (relaxed) bound, whose current assignment led to the deduction of the given conflict bound.
512  	 *
513  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
514  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
515  	 *
516  	 *  @pre This method can be called if SCIP is in one of the following stages:
517  	 *       - \ref SCIP_STAGE_PRESOLVING
518  	 *       - \ref SCIP_STAGE_SOLVING
519  	 *
520  	 *  @note SCIP stage does not get changed
521  	 */
522  	SCIP_RETCODE SCIPaddConflictRelaxedBd(
523  	   SCIP*                 scip,               /**< SCIP data structure */
524  	   SCIP_VAR*             var,                /**< variable whose upper bound should be added to conflict candidate queue */
525  	   SCIP_BOUNDTYPE        boundtype,          /**< the type of the conflicting bound (lower or upper bound) */
526  	   SCIP_BDCHGIDX*        bdchgidx,           /**< bound change index representing time on path to current node, when the
527  	                                              *   conflicting bound was valid, NULL for current local bound */
528  	   SCIP_Real             relaxedbd           /**< the relaxed bound */
529  	   )
530  	{
531  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPaddConflictRelaxedBd", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
532  	
533  	   assert( var->scip == scip );
534  	
535  	   SCIP_CALL( SCIPconflictAddRelaxedBound(scip->conflict, scip->mem->probmem, scip->set, scip->stat, var, boundtype, bdchgidx, relaxedbd) );
536  	
537  	   return SCIP_OKAY;
538  	}
539  	
540  	/** adds changed bound of fixed binary variable to the conflict analysis' candidate storage;
541  	 *  this method should be called in one of the following two cases:
542  	 *   1. Before calling the SCIPanalyzeConflict() method, SCIPaddConflictBinvar() should be called for each fixed binary
543  	 *      variable that led to the conflict (e.g. the infeasibility of globally or locally valid constraint).
544  	 *   2. In the propagation conflict resolving method of a constraint handler, SCIPaddConflictBinvar() should be called
545  	 *      for each binary variable, whose current fixing led to the deduction of the given conflict bound.
546  	 *
547  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
548  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
549  	 *
550  	 *  @pre This method can be called if SCIP is in one of the following stages:
551  	 *       - \ref SCIP_STAGE_PRESOLVING
552  	 *       - \ref SCIP_STAGE_SOLVING
553  	 *
554  	 *  @note SCIP stage does not get changed
555  	 */
556  	SCIP_RETCODE SCIPaddConflictBinvar(
557  	   SCIP*                 scip,               /**< SCIP data structure */
558  	   SCIP_VAR*             var                 /**< binary variable whose changed bound should be added to conflict queue */
559  	   )
560  	{
561  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPaddConflictBinvar", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
562  	
563  	   assert(var->scip == scip);
564  	   assert(SCIPvarIsBinary(var));
565  	
566  	   if( SCIPvarGetLbLocal(var) > 0.5 )
567  	   {
568  	      SCIP_CALL( SCIPconflictAddBound(scip->conflict, scip->mem->probmem, scip->set, scip->stat, var, SCIP_BOUNDTYPE_LOWER, NULL) );
569  	   }
570  	   else if( SCIPvarGetUbLocal(var) < 0.5 )
571  	   {
572  	      SCIP_CALL( SCIPconflictAddBound(scip->conflict, scip->mem->probmem, scip->set, scip->stat, var, SCIP_BOUNDTYPE_UPPER, NULL) );
573  	   }
574  	
575  	   return SCIP_OKAY;
576  	}
577  	
578  	/** checks if the given variable is already part of the current conflict set or queued for resolving with the same or
579  	 *  even stronger bound
580  	 *
581  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
582  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
583  	 *
584  	 *  @pre This method can be called if SCIP is in one of the following stages:
585  	 *       - \ref SCIP_STAGE_PRESOLVING
586  	 *       - \ref SCIP_STAGE_SOLVING
587  	 *
588  	 *  @note SCIP stage does not get changed
589  	 */
590  	SCIP_RETCODE SCIPisConflictVarUsed(
591  	   SCIP*                 scip,               /**< SCIP data structure */
592  	   SCIP_VAR*             var,                /**< variable whose upper bound should be added to conflict candidate queue */
593  	   SCIP_BOUNDTYPE        boundtype,          /**< the type of the conflicting bound (lower or upper bound) */
594  	   SCIP_BDCHGIDX*        bdchgidx,           /**< bound change index representing time on path to current node, when the
595  	                                              *   conflicting bound was valid, NULL for current local bound */
596  	   SCIP_Bool*            used                /**< pointer to store if the variable is already used */
597  	   )
598  	{
599  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPisConflictVarUsed", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
600  	
601  	   assert( var->scip == scip );
602  	
603  	   return SCIPconflictIsVarUsed(scip->conflict, var, scip->set, boundtype, bdchgidx, used);
604  	}
605  	
606  	/** returns the conflict lower bound if the variable is present in the current conflict set; otherwise the global lower
607  	 *  bound
608  	 *
609  	 *  @return returns the conflict lower bound if the variable is present in the current conflict set; otherwise the global lower
610  	 *          bound
611  	 *
612  	 *  @pre This method can be called if SCIP is in one of the following stages:
613  	 *       - \ref SCIP_STAGE_PRESOLVING
614  	 *       - \ref SCIP_STAGE_SOLVING
615  	 *
616  	 *  @note SCIP stage does not get changed
617  	 */
618  	SCIP_Real SCIPgetConflictVarLb(
619  	   SCIP*                 scip,               /**< SCIP data structure */
620  	   SCIP_VAR*             var                 /**< problem variable */
621  	   )
622  	{
623  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetConflictVarLb", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
624  	
625  	   assert( var->scip == scip );
626  	
627  	   return SCIPconflictGetVarLb(scip->conflict, var);
628  	}
629  	
630  	/** returns the conflict upper bound if the variable is present in the current conflict set; otherwise minus global
631  	 *  upper bound
632  	 *
633  	 *  @return returns the conflict upper bound if the variable is present in the current conflict set; otherwise minus global
634  	 *          upper bound
635  	 *
636  	 *  @pre This method can be called if SCIP is in one of the following stages:
637  	 *       - \ref SCIP_STAGE_PRESOLVING
638  	 *       - \ref SCIP_STAGE_SOLVING
639  	 *
640  	 *  @note SCIP stage does not get changed
641  	 */
642  	SCIP_Real SCIPgetConflictVarUb(
643  	   SCIP*                 scip,               /**< SCIP data structure */
644  	   SCIP_VAR*             var                 /**< problem variable */
645  	   )
646  	{
647  	   SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetConflictVarUb", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
648  	
649  	   assert( var->scip == scip );
650  	
651  	   return SCIPconflictGetVarUb(scip->conflict, var);
652  	}
653  	
654  	/** analyzes conflict bounds that were added after a call to SCIPinitConflictAnalysis() with calls to
655  	 *  SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPaddConflictBd(), SCIPaddConflictRelaxedLb(),
656  	 *  SCIPaddConflictRelaxedUb(), SCIPaddConflictRelaxedBd(), or SCIPaddConflictBinvar(); on success, calls the conflict
657  	 *  handlers to create a conflict constraint out of the resulting conflict set; the given valid depth must be a depth
658  	 *  level, at which the conflict set defined by calls to SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPaddConflictBd(),
659  	 *  SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), SCIPaddConflictRelaxedBd(), and SCIPaddConflictBinvar() is
660  	 *  valid for the whole subtree; if the conflict was found by a violated constraint, use SCIPanalyzeConflictCons()
661  	 *  instead of SCIPanalyzeConflict() to make sure, that the correct valid depth is used
662  	 *
663  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
664  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
665  	 *
666  	 *  @pre This method can be called if SCIP is in one of the following stages:
667  	 *       - \ref SCIP_STAGE_PRESOLVING
668  	 *       - \ref SCIP_STAGE_SOLVING
669  	 *
670  	 *  @note SCIP stage does not get changed
671  	 */
672  	SCIP_RETCODE SCIPanalyzeConflict(
673  	   SCIP*                 scip,               /**< SCIP data structure */
674  	   int                   validdepth,         /**< minimal depth level at which the initial conflict set is valid */
675  	   SCIP_Bool*            success             /**< pointer to store whether a conflict constraint was created, or NULL */
676  	   )
677  	{
678  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPanalyzeConflict", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
679  	
680  	   SCIP_CALL( SCIPconflictAnalyze(scip->conflict, scip->mem->probmem, scip->set, scip->stat,
681  	         scip->transprob, scip->tree, validdepth, success) );
682  	
683  	   return SCIP_OKAY;
684  	}
685  	
686  	/** analyzes conflict bounds that were added with calls to SCIPaddConflictLb(), SCIPaddConflictUb(),
687  	 *  SCIPaddConflictBd(), SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), SCIPaddConflictRelaxedBd(), or
688  	 *  SCIPaddConflictBinvar(); on success, calls the conflict handlers to create a conflict constraint out of the
689  	 *  resulting conflict set; the given constraint must be the constraint that detected the conflict, i.e. the constraint
690  	 *  that is infeasible in the local bounds of the initial conflict set (defined by calls to SCIPaddConflictLb(),
691  	 *  SCIPaddConflictUb(), SCIPaddConflictBd(), SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(),
692  	 *  SCIPaddConflictRelaxedBd(), and SCIPaddConflictBinvar())
693  	 *
694  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
695  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
696  	 *
697  	 *  @pre This method can be called if SCIP is in one of the following stages:
698  	 *       - \ref SCIP_STAGE_PRESOLVING
699  	 *       - \ref SCIP_STAGE_SOLVING
700  	 *
701  	 *  @note SCIP stage does not get changed
702  	 */
703  	SCIP_RETCODE SCIPanalyzeConflictCons(
704  	   SCIP*                 scip,               /**< SCIP data structure */
705  	   SCIP_CONS*            cons,               /**< constraint that detected the conflict */
706  	   SCIP_Bool*            success             /**< pointer to store whether a conflict constraint was created, or NULL */
707  	   )
708  	{
709  	   SCIP_CALL( SCIPcheckStage(scip, "SCIPanalyzeConflictCons", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
710  	
711  	   if( SCIPconsIsGlobal(cons) )
712  	   {
713  	      SCIP_CALL( SCIPconflictAnalyze(scip->conflict, scip->mem->probmem, scip->set, scip->stat,
714  	            scip->transprob, scip->tree, 0, success) );
715  	   }
716  	   else if( SCIPconsIsActive(cons) )
717  	   {
718  	      SCIP_CALL( SCIPconflictAnalyze(scip->conflict, scip->mem->probmem, scip->set, scip->stat,
719  	            scip->transprob, scip->tree, SCIPconsGetValidDepth(cons), success) );
720  	   }
721  	
722  	   return SCIP_OKAY;
723  	}
724