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-2024 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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
250 SCIP* scip /**< SCIP data structure */
251 )
252{
253 assert(scip != NULL);
254 assert(scip->set != NULL);
255
257
258 return scip->set->conflicthdlrs;
259}
260
261/** returns the number of currently available conflict handlers */
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 */
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 */
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 */
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 */
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{
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 */
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 */
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{
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 */
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 */
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{
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 */
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 */
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 */
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{
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 */
619 SCIP* scip, /**< SCIP data structure */
620 SCIP_VAR* var /**< problem variable */
621 )
622{
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 */
643 SCIP* scip, /**< SCIP data structure */
644 SCIP_VAR* var /**< problem variable */
645 )
646{
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 */
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{
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 */
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}
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:2208
methods for debugging
#define NULL
Definition: def.h:267
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_CALL_ABORT(x)
Definition: def.h:353
#define SCIP_CALL(x)
Definition: def.h:374
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:65
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:670
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17599
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
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