Scippy

SCIP

Solving Constraint Integer Programs

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