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