Scippy

SCIP

Solving Constraint Integer Programs

conflict.h
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-2023 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file conflict.h
26  * @ingroup INTERNALAPI
27  * @brief internal methods for conflict analysis
28  * @author Tobias Achterberg
29  */
30 
31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32 
33 #ifndef __SCIP_CONFLICT_H__
34 #define __SCIP_CONFLICT_H__
35 
36 
37 #include "blockmemshell/memory.h"
38 #include "scip/def.h"
39 #include "scip/type_branch.h"
40 #include "scip/type_conflict.h"
42 #include "scip/type_event.h"
43 #include "scip/type_implics.h"
44 #include "scip/type_lp.h"
45 #include "scip/type_message.h"
46 #include "scip/type_prob.h"
47 #include "scip/type_reopt.h"
48 #include "scip/type_result.h"
49 #include "scip/type_retcode.h"
50 #include "scip/type_scip.h"
51 #include "scip/type_set.h"
52 #include "scip/type_stat.h"
53 #include "scip/type_tree.h"
54 #include "scip/type_var.h"
55 
56 #ifdef __cplusplus
57 extern "C" {
58 #endif
59 
60 /*
61  * Conflict Handler
62  */
63 
64 /** copies the given conflict handler to a new scip */
66  SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
67  SCIP_SET* set /**< SCIP_SET of SCIP to copy to */
68  );
69 
70 /** creates a conflict handler */
72  SCIP_CONFLICTHDLR** conflicthdlr, /**< pointer to conflict handler data structure */
73  SCIP_SET* set, /**< global SCIP settings */
74  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
75  BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
76  const char* name, /**< name of conflict handler */
77  const char* desc, /**< description of conflict handler */
78  int priority, /**< priority of the conflict handler */
79  SCIP_DECL_CONFLICTCOPY((*conflictcopy)), /**< copy method of conflict handler or NULL if you don't want to copy your plugin into sub-SCIPs */
80  SCIP_DECL_CONFLICTFREE((*conflictfree)), /**< destructor of conflict handler */
81  SCIP_DECL_CONFLICTINIT((*conflictinit)), /**< initialize conflict handler */
82  SCIP_DECL_CONFLICTEXIT((*conflictexit)), /**< deinitialize conflict handler */
83  SCIP_DECL_CONFLICTINITSOL((*conflictinitsol)),/**< solving process initialization method of conflict handler */
84  SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol)),/**< solving process deinitialization method of conflict handler */
85  SCIP_DECL_CONFLICTEXEC((*conflictexec)), /**< conflict processing method of conflict handler */
86  SCIP_CONFLICTHDLRDATA* conflicthdlrdata /**< conflict handler data */
87  );
88 
89 /** calls destructor and frees memory of conflict handler */
91  SCIP_CONFLICTHDLR** conflicthdlr, /**< pointer to conflict handler data structure */
92  SCIP_SET* set /**< global SCIP settings */
93  );
94 
95 /** calls init method of conflict handler */
97  SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
98  SCIP_SET* set /**< global SCIP settings */
99  );
100 
101 /** calls exit method of conflict handler */
103  SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
104  SCIP_SET* set /**< global SCIP settings */
105  );
106 
107 /** informs conflict handler that the branch and bound process is being started */
109  SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
110  SCIP_SET* set /**< global SCIP settings */
111  );
112 
113 /** informs conflict handler that the branch and bound process data is being freed */
115  SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
116  SCIP_SET* set /**< global SCIP settings */
117  );
118 
119 /** calls execution method of conflict handler */
121  SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
122  SCIP_SET* set, /**< global SCIP settings */
123  SCIP_NODE* node, /**< node to add conflict constraint to */
124  SCIP_NODE* validnode, /**< node at which the constraint is valid */
125  SCIP_BDCHGINFO** bdchginfos, /**< bound change resembling the conflict set */
126  SCIP_Real* relaxedbds, /**< array with relaxed bounds which are efficient to create a valid conflict */
127  int nbdchginfos, /**< number of bound changes in the conflict set */
128  SCIP_CONFTYPE conftype, /**< type of the conflict */
129  SCIP_Bool usescutoffbound, /**< depends the conflict on the cutoff bound? */
130  SCIP_Bool resolved, /**< was the conflict set already used to create a constraint? */
131  SCIP_RESULT* result /**< pointer to store the result of the callback method */
132  );
133 
134 /** sets priority of conflict handler */
136  SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
137  SCIP_SET* set, /**< global SCIP settings */
138  int priority /**< new priority of the conflict handler */
139  );
140 
141 /** set copy method of conflict handler */
143  SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
144  SCIP_DECL_CONFLICTCOPY((*conflictcopy)) /**< copy method of the conflict handler */
145  );
146 
147 /** set destructor of conflict handler */
149  SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
150  SCIP_DECL_CONFLICTFREE((*conflictfree)) /**< destructor of conflict handler */
151  );
152 
153 /** set initialization method of conflict handler */
155  SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
156  SCIP_DECL_CONFLICTINIT((*conflictinit)) /**< initialization method conflict handler */
157  );
158 
159 /** set deinitialization method of conflict handler */
161  SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
162  SCIP_DECL_CONFLICTEXIT((*conflictexit)) /**< deinitialization method conflict handler */
163  );
164 
165 /** set solving process initialization method of conflict handler */
167  SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
168  SCIP_DECL_CONFLICTINITSOL((*conflictinitsol))/**< solving process initialization method of conflict handler */
169  );
170 
171 /** set solving process deinitialization method of conflict handler */
173  SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
174  SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol))/**< solving process deinitialization method of conflict handler */
175  );
176 
177 /** enables or disables all clocks of \p conflicthdlr, depending on the value of the flag */
179  SCIP_CONFLICTHDLR* conflicthdlr, /**< the conflict handler for which all clocks should be enabled or disabled */
180  SCIP_Bool enable /**< should the clocks of the conflict handler be enabled? */
181  );
182 
183 /*
184  * Conflict Analysis
185  */
186 
187 /** return TRUE if conflict analysis is applicable; In case the function return FALSE there is no need to initialize the
188  * conflict analysis since it will not be applied
189  */
191  SCIP_SET* set /**< global SCIP settings */
192  );
193 
194 /** creates conflict analysis data for propagation conflicts */
196  SCIP_CONFLICT** conflict, /**< pointer to conflict analysis data */
197  BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
198  SCIP_SET* set /**< global SCIP settings */
199  );
200 
201 /** frees conflict analysis data for propagation conflicts */
203  SCIP_CONFLICT** conflict, /**< pointer to conflict analysis data */
204  BMS_BLKMEM* blkmem /**< block memory of transformed problem */
205  );
206 
207 /** initializes the propagation conflict analysis by clearing the conflict candidate queue */
209  SCIP_CONFLICT* conflict, /**< conflict analysis data */
210  SCIP_SET* set, /**< global SCIP settings */
211  SCIP_STAT* stat, /**< problem statistics */
212  SCIP_PROB* prob, /**< problem data */
213  SCIP_CONFTYPE conftype, /**< type of the conflict */
214  SCIP_Bool usescutoffbound /**< depends the conflict on a cutoff bound? */
215  );
216 
217 /** adds variable's bound to conflict candidate queue */
219  SCIP_CONFLICT* conflict, /**< conflict analysis data */
220  BMS_BLKMEM* blkmem, /**< block memory */
221  SCIP_SET* set, /**< global SCIP settings */
222  SCIP_STAT* stat, /**< dynamic problem statistics */
223  SCIP_VAR* var, /**< problem variable */
224  SCIP_BOUNDTYPE boundtype, /**< type of bound that was changed: lower or upper bound */
225  SCIP_BDCHGIDX* bdchgidx /**< bound change index (time stamp of bound change), or NULL for current time */
226  );
227 
228 /** adds variable's bound to conflict candidate queue with the additional information of a relaxed bound */
230  SCIP_CONFLICT* conflict, /**< conflict analysis data */
231  BMS_BLKMEM* blkmem, /**< block memory */
232  SCIP_SET* set, /**< global SCIP settings */
233  SCIP_STAT* stat, /**< dynamic problem statistics */
234  SCIP_VAR* var, /**< problem variable */
235  SCIP_BOUNDTYPE boundtype, /**< type of bound that was changed: lower or upper bound */
236  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
237  SCIP_Real relaxedbd /**< the relaxed bound */
238  );
239 
240 /** checks if the given variable is already part of the current conflict set or queued for resolving with the same or
241  * even stronger bound
242  */
244  SCIP_CONFLICT* conflict, /**< conflict analysis data */
245  SCIP_VAR* var, /**< problem variable */
246  SCIP_SET* set, /**< global SCIP settings */
247  SCIP_BOUNDTYPE boundtype, /**< type of bound for which the score should be increased */
248  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
249  SCIP_Bool* used /**< pointer to store if the variable is already used */
250  );
251 
252 /** returns the conflict lower bound if the variable is present in the current conflict set; otherwise the global lower
253  * bound
254  */
256  SCIP_CONFLICT* conflict, /**< conflict analysis data */
257  SCIP_VAR* var /**< problem variable */
258  );
259 
260 /** returns the conflict upper bound if the variable is present in the current conflict set; otherwise the global upper
261  * bound
262  */
264  SCIP_CONFLICT* conflict, /**< conflict analysis data */
265  SCIP_VAR* var /**< problem variable */
266  );
267 
268 /** analyzes conflicting bound changes that were added with calls to SCIPconflictAddBound() and
269  * SCIPconflictAddRelaxedBound(), and on success, calls the conflict handlers to create a conflict constraint out of
270  * the resulting conflict set; updates statistics for propagation conflict analysis
271  */
273  SCIP_CONFLICT* conflict, /**< conflict analysis data */
274  BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
275  SCIP_SET* set, /**< global SCIP settings */
276  SCIP_STAT* stat, /**< problem statistics */
277  SCIP_PROB* prob, /**< problem data */
278  SCIP_TREE* tree, /**< branch and bound tree */
279  int validdepth, /**< minimal depth level at which the initial conflict set is valid */
280  SCIP_Bool* success /**< pointer to store whether a conflict constraint was created, or NULL */
281  );
282 
283 /** adds the collected conflict constraints to the corresponding nodes; the best set->conf_maxconss conflict constraints
284  * are added to the node of their validdepth; additionally (if not yet added, and if repropagation is activated), the
285  * conflict constraint that triggers the earliest repropagation is added to the node of its validdepth
286  */
288  SCIP_CONFLICT* conflict, /**< conflict analysis data */
289  BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
290  SCIP_SET* set, /**< global SCIP settings */
291  SCIP_STAT* stat, /**< dynamic problem statistics */
292  SCIP_PROB* transprob, /**< transformed problem */
293  SCIP_PROB* origprob, /**< original problem */
294  SCIP_TREE* tree, /**< branch and bound tree */
295  SCIP_REOPT* reopt, /**< reoptimization data structure */
296  SCIP_LP* lp, /**< current LP data */
297  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
298  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
299  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
300  );
301 
302 /** returns the current number of conflict sets in the conflict set storage */
304  SCIP_CONFLICT* conflict /**< conflict analysis data */
305  );
306 
307 /** returns the total number of conflict constraints that were added to the problem */
309  SCIP_CONFLICT* conflict /**< conflict analysis data */
310  );
311 
312 /** returns the total number of literals in conflict constraints that were added to the problem */
314  SCIP_CONFLICT* conflict /**< conflict analysis data */
315  );
316 
317 /** returns the total number of global bound changes applied by the conflict analysis */
319  SCIP_CONFLICT* conflict /**< conflict analysis data */
320  );
321 
322 /** returns the total number of conflict constraints that were added globally to the problem */
324  SCIP_CONFLICT* conflict /**< conflict analysis data */
325  );
326 
327 /** returns the total number of literals in conflict constraints that were added globally to the problem */
329  SCIP_CONFLICT* conflict /**< conflict analysis data */
330  );
331 
332 /** returns the total number of local bound changes applied by the conflict analysis */
334  SCIP_CONFLICT* conflict /**< conflict analysis data */
335  );
336 
337 /** returns the total number of conflict constraints that were added locally to the problem */
339  SCIP_CONFLICT* conflict /**< conflict analysis data */
340  );
341 
342 /** returns the total number of literals in conflict constraints that were added locally to the problem */
344  SCIP_CONFLICT* conflict /**< conflict analysis data */
345  );
346 
347 /** gets time in seconds used for preprocessing global conflict constraint before appliance */
349  SCIP_CONFLICT* conflict /**< conflict analysis data */
350  );
351 
352 /** gets time in seconds used for analyzing propagation conflicts */
354  SCIP_CONFLICT* conflict /**< conflict analysis data */
355  );
356 
357 /** gets number of calls to propagation conflict analysis */
359  SCIP_CONFLICT* conflict /**< conflict analysis data */
360  );
361 
362 /** gets number of calls to propagation conflict analysis that yield at least one conflict constraint */
364  SCIP_CONFLICT* conflict /**< conflict analysis data */
365  );
366 
367 /** gets number of conflict constraints detected in propagation conflict analysis */
369  SCIP_CONFLICT* conflict /**< conflict analysis data */
370  );
371 
372 /** gets total number of literals in conflict constraints created in propagation conflict analysis */
374  SCIP_CONFLICT* conflict /**< conflict analysis data */
375  );
376 
377 /** gets number of reconvergence constraints detected in propagation conflict analysis */
379  SCIP_CONFLICT* conflict /**< conflict analysis data */
380  );
381 
382 /** gets total number of literals in reconvergence constraints created in propagation conflict analysis */
384  SCIP_CONFLICT* conflict /**< conflict analysis data */
385  );
386 
387 
388 
389 
390 /*
391  * Infeasible LP Conflict Analysis
392  */
393 
394 /** analyzes an infeasible or bound exceeding LP to find out the bound changes on variables that were responsible for the
395  * infeasibility or for exceeding the primal bound;
396  * on success, calls standard conflict analysis with the responsible variables as starting conflict set, thus creating
397  * a conflict constraint out of the resulting conflict set;
398  * updates statistics for infeasible or bound exceeding LP conflict analysis
399  */
401  SCIP_CONFLICT* conflict, /**< conflict analysis data */
402  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
403  BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
404  SCIP_SET* set, /**< global SCIP settings */
405  SCIP_STAT* stat, /**< problem statistics */
406  SCIP_PROB* transprob, /**< transformed problem */
407  SCIP_PROB* origprob, /**< original problem */
408  SCIP_TREE* tree, /**< branch and bound tree */
409  SCIP_REOPT* reopt, /**< reoptimization data structure */
410  SCIP_LP* lp, /**< LP data */
411  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
412  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
413  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
414  SCIP_Bool* success /**< pointer to store whether a conflict constraint was created, or NULL */
415  );
416 
417 /** gets time in seconds used for analyzing infeasible LP conflicts */
419  SCIP_CONFLICT* conflict /**< conflict analysis data */
420  );
421 
422 /** gets number of calls to infeasible LP conflict analysis */
424  SCIP_CONFLICT* conflict /**< conflict analysis data */
425  );
426 
427 /** gets number of calls to infeasible LP conflict analysis that yield at least one conflict constraint */
429  SCIP_CONFLICT* conflict /**< conflict analysis data */
430  );
431 
432 /** gets number of conflict constraints detected in infeasible LP conflict analysis */
434  SCIP_CONFLICT* conflict /**< conflict analysis data */
435  );
436 
437 /** gets total number of literals in conflict constraints created in infeasible LP conflict analysis */
439  SCIP_CONFLICT* conflict /**< conflict analysis data */
440  );
441 
442 /** gets number of reconvergence constraints detected in infeasible LP conflict analysis */
444  SCIP_CONFLICT* conflict /**< conflict analysis data */
445  );
446 
447 /** gets total number of literals in reconvergence constraints created in infeasible LP conflict analysis */
449  SCIP_CONFLICT* conflict /**< conflict analysis data */
450  );
451 
452 /** gets number of LP iterations in infeasible LP conflict analysis */
454  SCIP_CONFLICT* conflict /**< conflict analysis data */
455  );
456 
457 /** gets time in seconds used for analyzing bound exceeding LP conflicts */
459  SCIP_CONFLICT* conflict /**< conflict analysis data */
460  );
461 
462 /** gets number of calls to bound exceeding LP conflict analysis */
464  SCIP_CONFLICT* conflict /**< conflict analysis data */
465  );
466 
467 /** gets number of calls to bound exceeding LP conflict analysis that yield at least one conflict constraint */
469  SCIP_CONFLICT* conflict /**< conflict analysis data */
470  );
471 
472 /** gets number of conflict constraints detected in bound exceeding LP conflict analysis */
474  SCIP_CONFLICT* conflict /**< conflict analysis data */
475  );
476 
477 /** gets total number of literals in conflict constraints created in bound exceeding LP conflict analysis */
479  SCIP_CONFLICT* conflict /**< conflict analysis data */
480  );
481 
482 /** gets number of reconvergence constraints detected in bound exceeding LP conflict analysis */
484  SCIP_CONFLICT* conflict /**< conflict analysis data */
485  );
486 
487 /** gets total number of literals in reconvergence constraints created in bound exceeding LP conflict analysis */
489  SCIP_CONFLICT* conflict /**< conflict analysis data */
490  );
491 
492 /** gets number of LP iterations in bound exceeding LP conflict analysis */
494  SCIP_CONFLICT* conflict /**< conflict analysis data */
495  );
496 
497 
498 
499 
500 /*
501  * infeasible strong branching conflict analysis
502  */
503 
504 /** analyses infeasible strong branching sub problems for conflicts */
506  SCIP_CONFLICT* conflict, /**< conflict analysis data */
507  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
508  BMS_BLKMEM* blkmem, /**< block memory buffers */
509  SCIP_SET* set, /**< global SCIP settings */
510  SCIP_STAT* stat, /**< dynamic problem statistics */
511  SCIP_PROB* transprob, /**< transformed problem */
512  SCIP_PROB* origprob, /**< original problem */
513  SCIP_TREE* tree, /**< branch and bound tree */
514  SCIP_REOPT* reopt, /**< reoptimization data structure */
515  SCIP_LP* lp, /**< LP data */
516  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
517  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
518  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
519  SCIP_COL* col, /**< LP column with at least one infeasible strong branching subproblem */
520  SCIP_Bool* downconflict, /**< pointer to store whether a conflict constraint was created for an
521  * infeasible downwards branch, or NULL */
522  SCIP_Bool* upconflict /**< pointer to store whether a conflict constraint was created for an
523  * infeasible upwards branch, or NULL */
524  );
525 
526 /** gets time in seconds used for analyzing infeasible strong branching conflicts */
528  SCIP_CONFLICT* conflict /**< conflict analysis data */
529  );
530 
531 /** gets number of successful calls to dual proof analysis derived from infeasible LPs */
533  SCIP_CONFLICT* conflict /**< conflict analysis data */
534  );
535 
536 /** gets number of globally valid dual proof constraints derived from infeasible LPs */
538  SCIP_CONFLICT* conflict /**< conflict analysis data */
539  );
540 
541 /** gets number of locally valid dual proof constraints derived from infeasible LPs */
543  SCIP_CONFLICT* conflict /**< conflict analysis data */
544  );
545 
546 /** gets average length of dual proof constraints derived from infeasible LPs */
548  SCIP_CONFLICT* conflict /**< conflict analysis data */
549  );
550 
551 /** gets number of successfully analyzed dual proofs derived from bound exceeding LPs */
553  SCIP_CONFLICT* conflict /**< conflict analysis data */
554  );
555 
556 /** gets number of globally applied dual proofs derived from bound exceeding LPs */
558  SCIP_CONFLICT* conflict /**< conflict analysis data */
559  );
560 
561 /** gets number of locally applied dual proofs derived from bound exceeding LPs */
563  SCIP_CONFLICT* conflict /**< conflict analysis data */
564  );
565 
566 /** gets average length of dual proofs derived from bound exceeding LPs */
568  SCIP_CONFLICT* conflict /**< conflict analysis data */
569  );
570 
571 /** gets number of calls to infeasible strong branching conflict analysis */
573  SCIP_CONFLICT* conflict /**< conflict analysis data */
574  );
575 
576 /** gets number of calls to infeasible strong branching conflict analysis that yield at least one conflict constraint */
578  SCIP_CONFLICT* conflict /**< conflict analysis data */
579  );
580 
581 /** gets number of conflict constraints detected in infeasible strong branching conflict analysis */
583  SCIP_CONFLICT* conflict /**< conflict analysis data */
584  );
585 
586 /** gets total number of literals in conflict constraints created in infeasible strong branching conflict analysis */
588  SCIP_CONFLICT* conflict /**< conflict analysis data */
589  );
590 
591 /** gets number of reconvergence constraints detected in infeasible strong branching conflict analysis */
593  SCIP_CONFLICT* conflict /**< conflict analysis data */
594  );
595 
596 /** gets total number of literals in reconvergence constraints created in infeasible strong branching conflict analysis */
598  SCIP_CONFLICT* conflict /**< conflict analysis data */
599  );
600 
601 /** gets number of LP iterations in infeasible strong branching conflict analysis */
603  SCIP_CONFLICT* conflict /**< conflict analysis data */
604  );
605 
606 
607 
608 
609 /*
610  * pseudo solution conflict analysis
611  */
612 
613 /** analyzes a pseudo solution with objective value exceeding the current cutoff to find out the bound changes on
614  * variables that were responsible for the objective value degradation;
615  * on success, calls standard conflict analysis with the responsible variables as starting conflict set, thus creating
616  * a conflict constraint out of the resulting conflict set;
617  * updates statistics for pseudo solution conflict analysis
618  */
620  SCIP_CONFLICT* conflict, /**< conflict analysis data */
621  BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
622  SCIP_SET* set, /**< global SCIP settings */
623  SCIP_STAT* stat, /**< problem statistics */
624  SCIP_PROB* transprob, /**< transformed problem */
625  SCIP_PROB* origprob, /**< original problem */
626  SCIP_TREE* tree, /**< branch and bound tree */
627  SCIP_REOPT* reopt, /**< reoptimization data structure */
628  SCIP_LP* lp, /**< LP data */
629  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
630  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
631  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
632  SCIP_Bool* success /**< pointer to store whether a conflict constraint was created, or NULL */
633  );
634 
635 /** gets time in seconds used for analyzing pseudo solution conflicts */
637  SCIP_CONFLICT* conflict /**< conflict analysis data */
638  );
639 
640 /** gets number of calls to pseudo solution conflict analysis */
642  SCIP_CONFLICT* conflict /**< conflict analysis data */
643  );
644 
645 /** gets number of calls to pseudo solution conflict analysis that yield at least one conflict constraint */
647  SCIP_CONFLICT* conflict /**< conflict analysis data */
648  );
649 
650 /** gets number of conflict constraints detected in pseudo solution conflict analysis */
652  SCIP_CONFLICT* conflict /**< conflict analysis data */
653  );
654 
655 /** gets total number of literals in conflict constraints created in pseudo solution conflict analysis */
657  SCIP_CONFLICT* conflict /**< conflict analysis data */
658  );
659 
660 /** gets number of reconvergence constraints detected in pseudo solution conflict analysis */
662  SCIP_CONFLICT* conflict /**< conflict analysis data */
663  );
664 
665 /** gets total number of literals in reconvergence constraints created in pseudo solution conflict analysis */
667  SCIP_CONFLICT* conflict /**< conflict analysis data */
668  );
669 
670 /** enables or disables all clocks of \p conflict, depending on the value of the flag */
672  SCIP_CONFLICT* conflict, /**< the conflict analysis data for which all clocks should be enabled or disabled */
673  SCIP_Bool enable /**< should the clocks of the conflict analysis data be enabled? */
674  );
675 
676 #ifdef __cplusplus
677 }
678 #endif
679 
680 #endif
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
SCIP_Longint SCIPconflictGetNBoundexceedingLPCalls(SCIP_CONFLICT *conflict)
Definition: conflict.c:8921
SCIP_Longint SCIPconflictGetNPseudoConflictConss(SCIP_CONFLICT *conflict)
Definition: conflict.c:9589
SCIP_Longint SCIPconflictGetNPropReconvergenceLiterals(SCIP_CONFLICT *conflict)
Definition: conflict.c:5794
void SCIPconflicthdlrSetCopy(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_DECL_CONFLICTCOPY((*conflictcopy)))
Definition: conflict.c:706
SCIP_Longint SCIPconflictGetNDualproofsInfLocal(SCIP_CONFLICT *conflict)
Definition: conflict.c:9265
SCIP_RETCODE SCIPconflictFlushConss(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable)
Definition: conflict.c:3555
type definitions for implications, variable bounds, and cliques
SCIP_Longint SCIPconflictGetNDualproofsBndSuccess(SCIP_CONFLICT *conflict)
Definition: conflict.c:9285
SCIP_Longint SCIPconflictGetNBoundexceedingLPConflictConss(SCIP_CONFLICT *conflict)
Definition: conflict.c:8941
SCIP_Longint SCIPconflictGetNBoundexceedingLPIterations(SCIP_CONFLICT *conflict)
Definition: conflict.c:8981
type definitions for conflict store
SCIP_Real SCIPconflictGetGlobalApplTime(SCIP_CONFLICT *conflict)
Definition: conflict.c:5724
SCIP_Longint SCIPconflictGetNLocalChgBds(SCIP_CONFLICT *conflict)
Definition: conflict.c:3824
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)
Definition: conflict.c:4475
SCIP_Longint SCIPconflictGetNInfeasibleLPReconvergenceLiterals(SCIP_CONFLICT *conflict)
Definition: conflict.c:8891
int SCIPconflictGetNConflicts(SCIP_CONFLICT *conflict)
Definition: conflict.c:3764
SCIP_RETCODE SCIPconflicthdlrExitsol(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set)
Definition: conflict.c:614
SCIP_RETCODE SCIPconflicthdlrExec(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set, SCIP_NODE *node, SCIP_NODE *validnode, SCIP_BDCHGINFO **bdchginfos, SCIP_Real *relaxedbds, int nbdchginfos, SCIP_CONFTYPE conftype, SCIP_Bool usescutoffbound, SCIP_Bool resolved, SCIP_RESULT *result)
Definition: conflict.c:638
SCIP_Real SCIPconflictGetPseudoTime(SCIP_CONFLICT *conflict)
Definition: conflict.c:9559
SCIP_Longint SCIPconflictGetNPropReconvergenceConss(SCIP_CONFLICT *conflict)
Definition: conflict.c:5784
SCIP_RETCODE SCIPconflictInit(SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_CONFTYPE conftype, SCIP_Bool usescutoffbound)
Definition: conflict.c:4056
SCIP_Longint SCIPconflictGetNDualproofsInfGlobal(SCIP_CONFLICT *conflict)
Definition: conflict.c:9255
SCIP_Longint SCIPconflictGetNPropCalls(SCIP_CONFLICT *conflict)
Definition: conflict.c:5744
SCIP_Longint SCIPconflictGetNPseudoSuccess(SCIP_CONFLICT *conflict)
Definition: conflict.c:9579
SCIP_Longint SCIPconflictGetNDualproofsBndLocal(SCIP_CONFLICT *conflict)
Definition: conflict.c:9305
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
type definitions for global SCIP settings
SCIP_Longint SCIPconflictGetNAppliedLocalConss(SCIP_CONFLICT *conflict)
Definition: conflict.c:3834
SCIP_RETCODE SCIPconflicthdlrFree(SCIP_CONFLICTHDLR **conflicthdlr, SCIP_SET *set)
Definition: conflict.c:494
SCIP_Longint SCIPconflictGetNStrongbranchConflictLiterals(SCIP_CONFLICT *conflict)
Definition: conflict.c:9355
SCIP_Longint SCIPconflictGetNDualproofsBndNonzeros(SCIP_CONFLICT *conflict)
Definition: conflict.c:9315
void SCIPconflicthdlrSetFree(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_DECL_CONFLICTFREE((*conflictfree)))
Definition: conflict.c:717
SCIP_Longint SCIPconflictGetNBoundexceedingLPReconvergenceLiterals(SCIP_CONFLICT *conflict)
Definition: conflict.c:8971
SCIP_Longint SCIPconflictGetNBoundexceedingLPConflictLiterals(SCIP_CONFLICT *conflict)
Definition: conflict.c:8951
SCIP_RETCODE SCIPconflictFree(SCIP_CONFLICT **conflict, BMS_BLKMEM *blkmem)
Definition: conflict.c:4008
SCIP_Longint SCIPconflictGetNPropSuccess(SCIP_CONFLICT *conflict)
Definition: conflict.c:5754
type definitions for return codes for SCIP methods
SCIP_Real SCIPconflictGetPropTime(SCIP_CONFLICT *conflict)
Definition: conflict.c:5734
type definitions for collecting reoptimization information
#define SCIP_DECL_CONFLICTEXIT(x)
SCIP_Longint SCIPconflictGetNDualproofsBndGlobal(SCIP_CONFLICT *conflict)
Definition: conflict.c:9295
type definitions for branching rules
type definitions for problem statistics
void SCIPconflicthdlrSetInit(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_DECL_CONFLICTINIT((*conflictinit)))
Definition: conflict.c:728
SCIP_RETCODE SCIPconflicthdlrCopyInclude(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set)
Definition: conflict.c:389
void SCIPconflicthdlrSetExit(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_DECL_CONFLICTEXIT((*conflictexit)))
Definition: conflict.c:739
type definitions for LP management
SCIP_Longint SCIPconflictGetNAppliedLocalLiterals(SCIP_CONFLICT *conflict)
Definition: conflict.c:3844
SCIP_RETCODE SCIPconflicthdlrExit(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set)
Definition: conflict.c:559
#define SCIP_DECL_CONFLICTINITSOL(x)
SCIP_Longint SCIPconflictGetNPseudoReconvergenceLiterals(SCIP_CONFLICT *conflict)
Definition: conflict.c:9619
#define SCIP_DECL_CONFLICTEXEC(x)
SCIP_Longint SCIPconflictGetNPseudoCalls(SCIP_CONFLICT *conflict)
Definition: conflict.c:9569
SCIP_Longint SCIPconflictGetNAppliedGlobalConss(SCIP_CONFLICT *conflict)
Definition: conflict.c:3804
SCIP_Longint SCIPconflictGetNStrongbranchIterations(SCIP_CONFLICT *conflict)
Definition: conflict.c:9385
type definitions for SCIP&#39;s main datastructure
SCIP_Longint SCIPconflictGetNBoundexceedingLPReconvergenceConss(SCIP_CONFLICT *conflict)
Definition: conflict.c:8961
struct SCIP_ConflicthdlrData SCIP_CONFLICTHDLRDATA
Definition: type_conflict.h:49
type definitions for problem variables
#define SCIP_DECL_CONFLICTCOPY(x)
Definition: type_conflict.h:86
SCIP_Longint SCIPconflictGetNPseudoConflictLiterals(SCIP_CONFLICT *conflict)
Definition: conflict.c:9599
void SCIPconflicthdlrEnableOrDisableClocks(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_Bool enable)
Definition: conflict.c:826
type definitions for conflict analysis
type definitions for managing events
SCIP_Longint SCIPconflictGetNStrongbranchReconvergenceLiterals(SCIP_CONFLICT *conflict)
Definition: conflict.c:9375
SCIP_Longint SCIPconflictGetNInfeasibleLPConflictConss(SCIP_CONFLICT *conflict)
Definition: conflict.c:8861
#define SCIP_Bool
Definition: def.h:93
SCIP_Longint SCIPconflictGetNPseudoReconvergenceConss(SCIP_CONFLICT *conflict)
Definition: conflict.c:9609
SCIP_RETCODE SCIPconflictAnalyzeStrongbranch(SCIP_CONFLICT *conflict, SCIP_CONFLICTSTORE *conflictstore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_COL *col, SCIP_Bool *downconflict, SCIP_Bool *upconflict)
Definition: conflict.c:8998
SCIP_Real SCIPconflictGetVarLb(SCIP_CONFLICT *conflict, SCIP_VAR *var)
Definition: conflict.c:4699
SCIP_Real SCIPconflictGetBoundexceedingLPTime(SCIP_CONFLICT *conflict)
Definition: conflict.c:8911
SCIP_Longint SCIPconflictGetNBoundexceedingLPSuccess(SCIP_CONFLICT *conflict)
Definition: conflict.c:8931
type definitions for branch and bound tree
SCIP_Real SCIPconflictGetStrongbranchTime(SCIP_CONFLICT *conflict)
Definition: conflict.c:9235
SCIP_Longint SCIPconflictGetNDualproofsInfNonzeros(SCIP_CONFLICT *conflict)
Definition: conflict.c:9275
type definitions for storing and manipulating the main problem
SCIP_RETCODE SCIPconflictIsVarUsed(SCIP_CONFLICT *conflict, SCIP_VAR *var, SCIP_SET *set, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool *used)
Definition: conflict.c:4639
SCIP_RETCODE SCIPconflictAddBound(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx)
Definition: conflict.c:4414
SCIP_Longint SCIPconflictGetNAppliedLiterals(SCIP_CONFLICT *conflict)
Definition: conflict.c:3784
SCIP_RETCODE SCIPconflictAnalyzePseudo(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool *success)
Definition: conflict.c:9407
SCIP_Real SCIPconflictGetInfeasibleLPTime(SCIP_CONFLICT *conflict)
Definition: conflict.c:8831
void SCIPconflicthdlrSetInitsol(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_DECL_CONFLICTINITSOL((*conflictinitsol)))
Definition: conflict.c:750
SCIP_Longint SCIPconflictGetNInfeasibleLPIterations(SCIP_CONFLICT *conflict)
Definition: conflict.c:8901
void SCIPconflicthdlrSetExitsol(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol)))
Definition: conflict.c:761
#define SCIP_Real
Definition: def.h:186
result codes for SCIP callback methods
enum SCIP_ConflictType SCIP_CONFTYPE
Definition: type_conflict.h:65
SCIP_Longint SCIPconflictGetNAppliedConss(SCIP_CONFLICT *conflict)
Definition: conflict.c:3774
SCIP_RETCODE SCIPconflictAnalyzeLP(SCIP_CONFLICT *conflict, SCIP_CONFLICTSTORE *conflictstore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool *success)
Definition: conflict.c:8684
SCIP_Longint SCIPconflictGetNStrongbranchConflictConss(SCIP_CONFLICT *conflict)
Definition: conflict.c:9345
#define SCIP_DECL_CONFLICTINIT(x)
SCIP_RETCODE SCIPconflicthdlrInit(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set)
Definition: conflict.c:522
SCIP_Longint SCIPconflictGetNInfeasibleLPSuccess(SCIP_CONFLICT *conflict)
Definition: conflict.c:8851
#define SCIP_Longint
Definition: def.h:171
SCIP_Longint SCIPconflictGetNAppliedGlobalLiterals(SCIP_CONFLICT *conflict)
Definition: conflict.c:3814
SCIP_Longint SCIPconflictGetNStrongbranchSuccess(SCIP_CONFLICT *conflict)
Definition: conflict.c:9335
SCIP_Longint SCIPconflictGetNStrongbranchReconvergenceConss(SCIP_CONFLICT *conflict)
Definition: conflict.c:9365
SCIP_RETCODE SCIPconflictCreate(SCIP_CONFLICT **conflict, BMS_BLKMEM *blkmem, SCIP_SET *set)
Definition: conflict.c:3918
SCIP_Longint SCIPconflictGetNInfeasibleLPReconvergenceConss(SCIP_CONFLICT *conflict)
Definition: conflict.c:8881
type definitions for message output methods
SCIP_Longint SCIPconflictGetNStrongbranchCalls(SCIP_CONFLICT *conflict)
Definition: conflict.c:9325
SCIP_Longint SCIPconflictGetNPropConflictConss(SCIP_CONFLICT *conflict)
Definition: conflict.c:5764
SCIP_Real SCIPconflictGetVarUb(SCIP_CONFLICT *conflict, SCIP_VAR *var)
Definition: conflict.c:4716
common defines and data types used in all packages of SCIP
void SCIPconflicthdlrSetPriority(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set, int priority)
Definition: conflict.c:802
SCIP_Longint SCIPconflictGetNInfeasibleLPCalls(SCIP_CONFLICT *conflict)
Definition: conflict.c:8841
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:439
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)
Definition: conflict.c:5666
#define SCIP_DECL_CONFLICTFREE(x)
Definition: type_conflict.h:94
SCIP_Bool SCIPconflictApplicable(SCIP_SET *set)
Definition: conflict.c:3902
SCIP_Longint SCIPconflictGetNPropConflictLiterals(SCIP_CONFLICT *conflict)
Definition: conflict.c:5774
void SCIPconflictEnableOrDisableClocks(SCIP_CONFLICT *conflict, SCIP_Bool enable)
Definition: conflict.c:9630
SCIP_Longint SCIPconflictGetNGlobalChgBds(SCIP_CONFLICT *conflict)
Definition: conflict.c:3794
SCIP_Longint SCIPconflictGetNDualproofsInfSuccess(SCIP_CONFLICT *conflict)
Definition: conflict.c:9245
SCIP_RETCODE SCIPconflicthdlrInitsol(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set)
Definition: conflict.c:590
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)
Definition: conflict.c:463
#define SCIP_DECL_CONFLICTEXITSOL(x)
SCIP_Longint SCIPconflictGetNInfeasibleLPConflictLiterals(SCIP_CONFLICT *conflict)
Definition: conflict.c:8871
memory allocation routines