Scippy

SCIP

Solving Constraint Integer Programs

conflict_general.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 conflict_general.c
26  * @ingroup OTHER_CFILES
27  * @brief methods and datastructures for conflict analysis
28  * @author Tobias Achterberg
29  * @author Timo Berthold
30  * @author Stefan Heinz
31  * @author Marc Pfetsch
32  * @author Michael Winkler
33  * @author Jakob Witzig
34  *
35  * SCIP contains two kinds of conflict analysis:
36  * - In graph based conflict analysis, the graph consisting of derived
37  * is analysed. Code and documentation is available in conflict_graphanalysis.h
38  * - In dual proof analysis, an infeasible LP relaxation is analysed.
39  * Using the dual solution, a valid constraint is derived that is violated
40  * by all values in the domain. This constraint is added to the problem
41  * and can then be used for domain propagation.
42  * Code is available in conflict_dualproofanalysis.h
43  * This file contains the methods that are shared by both kinds of conflict analysis.
44  */
45 
46 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
47 
48 #include "lpi/lpi.h"
49 #include "scip/clock.h"
50 #include "scip/conflict.h"
51 #include "scip/conflictstore.h"
52 #include "scip/cons.h"
53 #include "scip/cons_linear.h"
54 #include "scip/cuts.h"
55 #include "scip/history.h"
56 #include "scip/lp.h"
57 #include "scip/presolve.h"
58 #include "scip/prob.h"
59 #include "scip/prop.h"
60 #include "scip/pub_conflict.h"
61 #include "scip/pub_cons.h"
62 #include "scip/pub_lp.h"
63 #include "scip/pub_message.h"
64 #include "scip/pub_misc.h"
65 #include "scip/pub_misc_sort.h"
66 #include "scip/pub_paramset.h"
67 #include "scip/pub_prop.h"
68 #include "scip/pub_tree.h"
69 #include "scip/pub_var.h"
70 #include "scip/scip_conflict.h"
71 #include "scip/scip_cons.h"
72 #include "scip/scip_mem.h"
73 #include "scip/scip_sol.h"
74 #include "scip/scip_var.h"
75 #include "scip/set.h"
76 #include "scip/sol.h"
77 #include "scip/struct_conflict.h"
78 #include "scip/struct_lp.h"
79 #include "scip/struct_prob.h"
80 #include "scip/struct_set.h"
81 #include "scip/struct_stat.h"
82 #include "scip/struct_tree.h"
83 #include "scip/struct_var.h"
84 #include "scip/tree.h"
85 #include "scip/var.h"
86 #include "scip/visual.h"
87 #include <string.h>
88 #if defined(_WIN32) || defined(_WIN64)
89 #else
90 #include <strings.h> /*lint --e{766}*/
91 #endif
92 
93 /* because calculations might cancel out some values, we stop the infeasibility analysis if a value is bigger than
94  * 2^53 = 9007199254740992
95  */
96 #define NUMSTOP 9007199254740992.0
97 /* because row violations might be magnified, we stop the infeasibility analysis if a dual weight is bigger than
98  * 10^7 = 10000000
99  */
100 #define SOLSTOP 10000000.0
101 
102 /** returns the current number of conflict sets in the conflict set storage */
104  SCIP_CONFLICT* conflict /**< conflict analysis data */
105  )
106 {
107  assert(conflict != NULL);
108 
109  return conflict->nconflictsets;
110 }
111 
112 /** returns the total number of conflict constraints that were added to the problem */
114  SCIP_CONFLICT* conflict /**< conflict analysis data */
115  )
116 {
117  assert(conflict != NULL);
118 
119  return conflict->nappliedglbconss + conflict->nappliedlocconss;
120 }
121 
122 /** returns the total number of literals in conflict constraints that were added to the problem */
124  SCIP_CONFLICT* conflict /**< conflict analysis data */
125  )
126 {
127  assert(conflict != NULL);
128 
129  return conflict->nappliedglbliterals + conflict->nappliedlocliterals;
130 }
131 
132 /** returns the total number of global bound changes applied by the conflict analysis */
134  SCIP_CONFLICT* conflict /**< conflict analysis data */
135  )
136 {
137  assert(conflict != NULL);
138 
139  return conflict->nglbchgbds;
140 }
141 
142 /** returns the total number of conflict constraints that were added globally to the problem */
144  SCIP_CONFLICT* conflict /**< conflict analysis data */
145  )
146 {
147  assert(conflict != NULL);
148 
149  return conflict->nappliedglbconss;
150 }
151 
152 /** returns the total number of literals in conflict constraints that were added globally to the problem */
154  SCIP_CONFLICT* conflict /**< conflict analysis data */
155  )
156 {
157  assert(conflict != NULL);
158 
159  return conflict->nappliedglbliterals;
160 }
161 
162 /** returns the total number of local bound changes applied by the conflict analysis */
164  SCIP_CONFLICT* conflict /**< conflict analysis data */
165  )
166 {
167  assert(conflict != NULL);
168 
169  return conflict->nlocchgbds;
170 }
171 
172 /** returns the total number of conflict constraints that were added locally to the problem */
174  SCIP_CONFLICT* conflict /**< conflict analysis data */
175  )
176 {
177  assert(conflict != NULL);
178 
179  return conflict->nappliedlocconss;
180 }
181 
182 /** returns the total number of literals in conflict constraints that were added locally to the problem */
184  SCIP_CONFLICT* conflict /**< conflict analysis data */
185  )
186 {
187  assert(conflict != NULL);
188 
189  return conflict->nappliedlocliterals;
190 }
191 
192 /** compares two conflict set entries, such that bound changes inferred later are
193  * ordered prior to ones that were inferred earlier
194  */
195 static
196 SCIP_DECL_SORTPTRCOMP(conflictBdchginfoComp)
197 { /*lint --e{715}*/
198  SCIP_BDCHGINFO* bdchginfo1;
199  SCIP_BDCHGINFO* bdchginfo2;
200 
201  bdchginfo1 = (SCIP_BDCHGINFO*)elem1;
202  bdchginfo2 = (SCIP_BDCHGINFO*)elem2;
203  assert(bdchginfo1 != NULL);
204  assert(bdchginfo2 != NULL);
205  assert(!SCIPbdchginfoIsRedundant(bdchginfo1));
206  assert(!SCIPbdchginfoIsRedundant(bdchginfo2));
207 
208  if( bdchginfo1 == bdchginfo2 )
209  return 0;
210 
212  return -1;
213  else
214  return +1;
215 }
216 
217 /** enables or disables all clocks of \p conflict, depending on the value of the flag */
219  SCIP_CONFLICT* conflict, /**< the conflict analysis data for which all clocks should be enabled or disabled */
220  SCIP_Bool enable /**< should the clocks of the conflict analysis data be enabled? */
221  )
222 {
223  assert(conflict != NULL);
224 
225  SCIPclockEnableOrDisable(conflict->boundlpanalyzetime, enable);
226  SCIPclockEnableOrDisable(conflict->dIBclock, enable);
227  SCIPclockEnableOrDisable(conflict->inflpanalyzetime, enable);
228  SCIPclockEnableOrDisable(conflict->propanalyzetime, enable);
229  SCIPclockEnableOrDisable(conflict->pseudoanalyzetime, enable);
230  SCIPclockEnableOrDisable(conflict->sbanalyzetime, enable);
231 }
232 
233 /** creates conflict analysis data for propagation conflicts */
235  SCIP_CONFLICT** conflict, /**< pointer to conflict analysis data */
236  BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
237  SCIP_SET* set /**< global SCIP settings */
238  )
239 {
240  assert(conflict != NULL);
241 
242  SCIP_ALLOC( BMSallocMemory(conflict) );
243 
244  SCIP_CALL( SCIPclockCreate(&(*conflict)->dIBclock, SCIP_CLOCKTYPE_DEFAULT) );
245  SCIP_CALL( SCIPclockCreate(&(*conflict)->propanalyzetime, SCIP_CLOCKTYPE_DEFAULT) );
246  SCIP_CALL( SCIPclockCreate(&(*conflict)->inflpanalyzetime, SCIP_CLOCKTYPE_DEFAULT) );
247  SCIP_CALL( SCIPclockCreate(&(*conflict)->boundlpanalyzetime, SCIP_CLOCKTYPE_DEFAULT) );
248  SCIP_CALL( SCIPclockCreate(&(*conflict)->sbanalyzetime, SCIP_CLOCKTYPE_DEFAULT) );
249  SCIP_CALL( SCIPclockCreate(&(*conflict)->pseudoanalyzetime, SCIP_CLOCKTYPE_DEFAULT) );
250 
251  /* enable or disable timing depending on the parameter statistic timing */
252  SCIPconflictEnableOrDisableClocks((*conflict), set->time_statistictiming);
253 
254  SCIP_CALL( SCIPpqueueCreate(&(*conflict)->bdchgqueue, set->mem_arraygrowinit, set->mem_arraygrowfac,
255  conflictBdchginfoComp, NULL) );
256  SCIP_CALL( SCIPpqueueCreate(&(*conflict)->forcedbdchgqueue, set->mem_arraygrowinit, set->mem_arraygrowfac,
257  conflictBdchginfoComp, NULL) );
258  SCIP_CALL( SCIPconflictsetCreate(&(*conflict)->conflictset, blkmem) );
259  (*conflict)->conflictsets = NULL;
260  (*conflict)->conflictsetscores = NULL;
261  (*conflict)->tmpbdchginfos = NULL;
262  (*conflict)->conflictsetssize = 0;
263  (*conflict)->nconflictsets = 0;
264  (*conflict)->proofsets = NULL;
265  (*conflict)->proofsetssize = 0;
266  (*conflict)->nproofsets = 0;
267  (*conflict)->tmpbdchginfossize = 0;
268  (*conflict)->ntmpbdchginfos = 0;
269  (*conflict)->count = 0;
270  (*conflict)->nglbchgbds = 0;
271  (*conflict)->nappliedglbconss = 0;
272  (*conflict)->nappliedglbliterals = 0;
273  (*conflict)->nlocchgbds = 0;
274  (*conflict)->nappliedlocconss = 0;
275  (*conflict)->nappliedlocliterals = 0;
276  (*conflict)->npropcalls = 0;
277  (*conflict)->npropsuccess = 0;
278  (*conflict)->npropconfconss = 0;
279  (*conflict)->npropconfliterals = 0;
280  (*conflict)->npropreconvconss = 0;
281  (*conflict)->npropreconvliterals = 0;
282  (*conflict)->ninflpcalls = 0;
283  (*conflict)->ninflpsuccess = 0;
284  (*conflict)->ninflpconfconss = 0;
285  (*conflict)->ninflpconfliterals = 0;
286  (*conflict)->ninflpreconvconss = 0;
287  (*conflict)->ninflpreconvliterals = 0;
288  (*conflict)->ninflpiterations = 0;
289  (*conflict)->nboundlpcalls = 0;
290  (*conflict)->nboundlpsuccess = 0;
291  (*conflict)->nboundlpconfconss = 0;
292  (*conflict)->nboundlpconfliterals = 0;
293  (*conflict)->nboundlpreconvconss = 0;
294  (*conflict)->nboundlpreconvliterals = 0;
295  (*conflict)->nboundlpiterations = 0;
296  (*conflict)->nsbcalls = 0;
297  (*conflict)->nsbsuccess = 0;
298  (*conflict)->nsbconfconss = 0;
299  (*conflict)->nsbconfliterals = 0;
300  (*conflict)->nsbreconvconss = 0;
301  (*conflict)->nsbreconvliterals = 0;
302  (*conflict)->nsbiterations = 0;
303  (*conflict)->npseudocalls = 0;
304  (*conflict)->npseudosuccess = 0;
305  (*conflict)->npseudoconfconss = 0;
306  (*conflict)->npseudoconfliterals = 0;
307  (*conflict)->npseudoreconvconss = 0;
308  (*conflict)->npseudoreconvliterals = 0;
309  (*conflict)->ndualproofsinfglobal = 0;
310  (*conflict)->ndualproofsinflocal = 0;
311  (*conflict)->ndualproofsinfsuccess = 0;
312  (*conflict)->dualproofsinfnnonzeros = 0;
313  (*conflict)->ndualproofsbndglobal = 0;
314  (*conflict)->ndualproofsbndlocal = 0;
315  (*conflict)->ndualproofsbndsuccess = 0;
316  (*conflict)->dualproofsbndnnonzeros = 0;
317 
318  SCIP_CALL( SCIPconflictInitProofset((*conflict), blkmem) );
319 
320  return SCIP_OKAY;
321 }
322 
323 /** frees conflict analysis data for propagation conflicts */
325  SCIP_CONFLICT** conflict, /**< pointer to conflict analysis data */
326  BMS_BLKMEM* blkmem /**< block memory of transformed problem */
327  )
328 {
329  assert(conflict != NULL);
330  assert(*conflict != NULL);
331  assert((*conflict)->nconflictsets == 0);
332  assert((*conflict)->ntmpbdchginfos == 0);
333 
334 #if defined(SCIP_CONFGRAPH) || defined(SCIP_CONFGRAPH_DOT)
335  confgraphFree();
336 #endif
337 
338  SCIPclockFree(&(*conflict)->dIBclock);
339  SCIPclockFree(&(*conflict)->propanalyzetime);
340  SCIPclockFree(&(*conflict)->inflpanalyzetime);
341  SCIPclockFree(&(*conflict)->boundlpanalyzetime);
342  SCIPclockFree(&(*conflict)->sbanalyzetime);
343  SCIPclockFree(&(*conflict)->pseudoanalyzetime);
344  SCIPpqueueFree(&(*conflict)->bdchgqueue);
345  SCIPpqueueFree(&(*conflict)->forcedbdchgqueue);
346  SCIPconflictsetFree(&(*conflict)->conflictset, blkmem);
347  SCIPproofsetFree(&(*conflict)->proofset, blkmem);
348 
349  BMSfreeMemoryArrayNull(&(*conflict)->conflictsets);
350  BMSfreeMemoryArrayNull(&(*conflict)->conflictsetscores);
351  BMSfreeMemoryArrayNull(&(*conflict)->proofsets);
352  BMSfreeMemoryArrayNull(&(*conflict)->tmpbdchginfos);
353  BMSfreeMemory(conflict);
354 
355  return SCIP_OKAY;
356 }
357 
358 /** returns the conflict lower bound if the variable is present in the current conflict set; otherwise the global lower
359  * bound
360  */
362  SCIP_CONFLICT* conflict, /**< conflict analysis data */
363  SCIP_VAR* var /**< problem variable */
364  )
365 {
366  if( var->conflictlbcount == conflict->count )
367  {
368  assert(EPSGE(var->conflictlb, var->conflictrelaxedlb, 1e-09));
369  return var->conflictrelaxedlb;
370  }
371 
372  return SCIPvarGetLbGlobal(var);
373 }
374 
375 /** returns the conflict upper bound if the variable is present in the current conflict set; otherwise the global upper
376  * bound
377  */
379  SCIP_CONFLICT* conflict, /**< conflict analysis data */
380  SCIP_VAR* var /**< problem variable */
381  )
382 {
383  if( var->conflictubcount == conflict->count )
384  {
385  assert(EPSLE(var->conflictub, var->conflictrelaxedub, 1e-09));
386  return var->conflictrelaxedub;
387  }
388 
389  return SCIPvarGetUbGlobal(var);
390 }
391 
392 /** gets time in seconds used for preprocessing global conflict constraint before appliance */
394  SCIP_CONFLICT* conflict /**< conflict analysis data */
395  )
396 {
397  assert(conflict != NULL);
398 
399  return SCIPclockGetTime(conflict->dIBclock);
400 }
401 
402 /** gets time in seconds used for analyzing propagation conflicts */
404  SCIP_CONFLICT* conflict /**< conflict analysis data */
405  )
406 {
407  assert(conflict != NULL);
408 
409  return SCIPclockGetTime(conflict->propanalyzetime);
410 }
411 
412 /** gets number of calls to propagation conflict analysis */
414  SCIP_CONFLICT* conflict /**< conflict analysis data */
415  )
416 {
417  assert(conflict != NULL);
418 
419  return conflict->npropcalls;
420 }
421 
422 /** gets number of calls to propagation conflict analysis that yield at least one conflict constraint */
424  SCIP_CONFLICT* conflict /**< conflict analysis data */
425  )
426 {
427  assert(conflict != NULL);
428 
429  return conflict->npropsuccess;
430 }
431 
432 /** gets number of conflict constraints detected in propagation conflict analysis */
434  SCIP_CONFLICT* conflict /**< conflict analysis data */
435  )
436 {
437  assert(conflict != NULL);
438 
439  return conflict->npropconfconss;
440 }
441 
442 /** gets total number of literals in conflict constraints created in propagation conflict analysis */
444  SCIP_CONFLICT* conflict /**< conflict analysis data */
445  )
446 {
447  assert(conflict != NULL);
448 
449  return conflict->npropconfliterals;
450 }
451 
452 /** gets number of reconvergence constraints detected in propagation conflict analysis */
454  SCIP_CONFLICT* conflict /**< conflict analysis data */
455  )
456 {
457  assert(conflict != NULL);
458 
459  return conflict->npropreconvconss;
460 }
461 
462 /** gets total number of literals in reconvergence constraints created in propagation conflict analysis */
464  SCIP_CONFLICT* conflict /**< conflict analysis data */
465  )
466 {
467  assert(conflict != NULL);
468 
469  return conflict->npropreconvliterals;
470 }
471 
472 /** gets time in seconds used for analyzing infeasible LP conflicts */
474  SCIP_CONFLICT* conflict /**< conflict analysis data */
475  )
476 {
477  assert(conflict != NULL);
478 
479  return SCIPclockGetTime(conflict->inflpanalyzetime);
480 }
481 
482 /** gets number of calls to infeasible LP conflict analysis */
484  SCIP_CONFLICT* conflict /**< conflict analysis data */
485  )
486 {
487  assert(conflict != NULL);
488 
489  return conflict->ninflpcalls;
490 }
491 
492 /** gets number of calls to infeasible LP conflict analysis that yield at least one conflict constraint */
494  SCIP_CONFLICT* conflict /**< conflict analysis data */
495  )
496 {
497  assert(conflict != NULL);
498 
499  return conflict->ninflpsuccess;
500 }
501 
502 /** gets number of conflict constraints detected in infeasible LP conflict analysis */
504  SCIP_CONFLICT* conflict /**< conflict analysis data */
505  )
506 {
507  assert(conflict != NULL);
508 
509  return conflict->ninflpconfconss;
510 }
511 
512 /** gets total number of literals in conflict constraints created in infeasible LP conflict analysis */
514  SCIP_CONFLICT* conflict /**< conflict analysis data */
515  )
516 {
517  assert(conflict != NULL);
518 
519  return conflict->ninflpconfliterals;
520 }
521 
522 /** gets number of reconvergence constraints detected in infeasible LP conflict analysis */
524  SCIP_CONFLICT* conflict /**< conflict analysis data */
525  )
526 {
527  assert(conflict != NULL);
528 
529  return conflict->ninflpreconvconss;
530 }
531 
532 /** gets total number of literals in reconvergence constraints created in infeasible LP conflict analysis */
534  SCIP_CONFLICT* conflict /**< conflict analysis data */
535  )
536 {
537  assert(conflict != NULL);
538 
539  return conflict->ninflpreconvliterals;
540 }
541 
542 /** gets number of LP iterations in infeasible LP conflict analysis */
544  SCIP_CONFLICT* conflict /**< conflict analysis data */
545  )
546 {
547  assert(conflict != NULL);
548 
549  return conflict->ninflpiterations;
550 }
551 
552 /** gets time in seconds used for analyzing bound exceeding LP conflicts */
554  SCIP_CONFLICT* conflict /**< conflict analysis data */
555  )
556 {
557  assert(conflict != NULL);
558 
559  return SCIPclockGetTime(conflict->boundlpanalyzetime);
560 }
561 
562 /** gets number of calls to bound exceeding LP conflict analysis */
564  SCIP_CONFLICT* conflict /**< conflict analysis data */
565  )
566 {
567  assert(conflict != NULL);
568 
569  return conflict->nboundlpcalls;
570 }
571 
572 /** gets number of calls to bound exceeding LP conflict analysis that yield at least one conflict constraint */
574  SCIP_CONFLICT* conflict /**< conflict analysis data */
575  )
576 {
577  assert(conflict != NULL);
578 
579  return conflict->nboundlpsuccess;
580 }
581 
582 /** gets number of conflict constraints detected in bound exceeding LP conflict analysis */
584  SCIP_CONFLICT* conflict /**< conflict analysis data */
585  )
586 {
587  assert(conflict != NULL);
588 
589  return conflict->nboundlpconfconss;
590 }
591 
592 /** gets total number of literals in conflict constraints created in bound exceeding LP conflict analysis */
594  SCIP_CONFLICT* conflict /**< conflict analysis data */
595  )
596 {
597  assert(conflict != NULL);
598 
599  return conflict->nboundlpconfliterals;
600 }
601 
602 /** gets number of reconvergence constraints detected in bound exceeding LP conflict analysis */
604  SCIP_CONFLICT* conflict /**< conflict analysis data */
605  )
606 {
607  assert(conflict != NULL);
608 
609  return conflict->nboundlpreconvconss;
610 }
611 
612 /** gets total number of literals in reconvergence constraints created in bound exceeding LP conflict analysis */
614  SCIP_CONFLICT* conflict /**< conflict analysis data */
615  )
616 {
617  assert(conflict != NULL);
618 
619  return conflict->nboundlpreconvliterals;
620 }
621 
622 /** gets number of LP iterations in bound exceeding LP conflict analysis */
624  SCIP_CONFLICT* conflict /**< conflict analysis data */
625  )
626 {
627  assert(conflict != NULL);
628 
629  return conflict->nboundlpiterations;
630 }
631 
632 /** gets time in seconds used for analyzing infeasible strong branching conflicts */
634  SCIP_CONFLICT* conflict /**< conflict analysis data */
635  )
636 {
637  assert(conflict != NULL);
638 
639  return SCIPclockGetTime(conflict->sbanalyzetime);
640 }
641 
642 /** gets number of successful calls to dual proof analysis derived from infeasible LPs */
644  SCIP_CONFLICT* conflict /**< conflict analysis data */
645  )
646 {
647  assert(conflict != NULL);
648 
649  return conflict->ndualproofsinfsuccess;
650 }
651 
652 /** gets number of globally valid dual proof constraints derived from infeasible LPs */
654  SCIP_CONFLICT* conflict /**< conflict analysis data */
655  )
656 {
657  assert(conflict != NULL);
658 
659  return conflict->ndualproofsinfglobal;
660 }
661 
662 /** gets number of locally valid dual proof constraints derived from infeasible LPs */
664  SCIP_CONFLICT* conflict /**< conflict analysis data */
665  )
666 {
667  assert(conflict != NULL);
668 
669  return conflict->ndualproofsinflocal;
670 }
671 
672 /** gets average length of dual proof constraints derived from infeasible LPs */
674  SCIP_CONFLICT* conflict /**< conflict analysis data */
675  )
676 {
677  assert(conflict != NULL);
678 
679  return conflict->dualproofsinfnnonzeros;
680 }
681 
682 /** gets number of successfully analyzed dual proofs derived from bound exceeding LPs */
684  SCIP_CONFLICT* conflict /**< conflict analysis data */
685  )
686 {
687  assert(conflict != NULL);
688 
689  return conflict->ndualproofsbndsuccess;
690 }
691 
692 /** gets number of globally applied dual proofs derived from bound exceeding LPs */
694  SCIP_CONFLICT* conflict /**< conflict analysis data */
695  )
696 {
697  assert(conflict != NULL);
698 
699  return conflict->ndualproofsbndglobal;
700 }
701 
702 /** gets number of locally applied dual proofs derived from bound exceeding LPs */
704  SCIP_CONFLICT* conflict /**< conflict analysis data */
705  )
706 {
707  assert(conflict != NULL);
708 
709  return conflict->ndualproofsbndlocal;
710 }
711 
712 /** gets average length of dual proofs derived from bound exceeding LPs */
714  SCIP_CONFLICT* conflict /**< conflict analysis data */
715  )
716 {
717  assert(conflict != NULL);
718 
719  return conflict->dualproofsbndnnonzeros;
720 }
721 
722 /** gets number of calls to infeasible strong branching conflict analysis */
724  SCIP_CONFLICT* conflict /**< conflict analysis data */
725  )
726 {
727  assert(conflict != NULL);
728 
729  return conflict->nsbcalls;
730 }
731 
732 /** gets number of calls to infeasible strong branching conflict analysis that yield at least one conflict constraint */
734  SCIP_CONFLICT* conflict /**< conflict analysis data */
735  )
736 {
737  assert(conflict != NULL);
738 
739  return conflict->nsbsuccess;
740 }
741 
742 /** gets number of conflict constraints detected in infeasible strong branching conflict analysis */
744  SCIP_CONFLICT* conflict /**< conflict analysis data */
745  )
746 {
747  assert(conflict != NULL);
748 
749  return conflict->nsbconfconss;
750 }
751 
752 /** gets total number of literals in conflict constraints created in infeasible strong branching conflict analysis */
754  SCIP_CONFLICT* conflict /**< conflict analysis data */
755  )
756 {
757  assert(conflict != NULL);
758 
759  return conflict->nsbconfliterals;
760 }
761 
762 /** gets number of reconvergence constraints detected in infeasible strong branching conflict analysis */
764  SCIP_CONFLICT* conflict /**< conflict analysis data */
765  )
766 {
767  assert(conflict != NULL);
768 
769  return conflict->nsbreconvconss;
770 }
771 
772 /** gets total number of literals in reconvergence constraints created in infeasible strong branching conflict analysis */
774  SCIP_CONFLICT* conflict /**< conflict analysis data */
775  )
776 {
777  assert(conflict != NULL);
778 
779  return conflict->nsbreconvliterals;
780 }
781 
782 /** gets number of LP iterations in infeasible strong branching conflict analysis */
784  SCIP_CONFLICT* conflict /**< conflict analysis data */
785  )
786 {
787  assert(conflict != NULL);
788 
789  return conflict->nsbiterations;
790 }
791 
792 /** adds a weighted LP row to an aggregation row */
793 static
795  SCIP_SET* set, /**< global SCIP settings */
796  SCIP_ROW* row, /**< LP row */
797  SCIP_Real weight, /**< weight for scaling */
798  SCIP_AGGRROW* aggrrow /**< aggregation row */
799  )
800 {
801  assert(set != NULL);
802  assert(row != NULL);
803  assert(weight != 0.0);
804 
805  /* add minimal value to dual row's left hand side: y_i < 0 -> lhs, y_i > 0 -> rhs */
806  if( weight < 0.0 )
807  {
808  assert(!SCIPsetIsInfinity(set, -row->lhs));
809  SCIP_CALL( SCIPaggrRowAddRow(set->scip, aggrrow, row, weight, -1) );
810  }
811  else
812  {
813  assert(!SCIPsetIsInfinity(set, row->rhs));
814  SCIP_CALL( SCIPaggrRowAddRow(set->scip, aggrrow, row, weight, +1) );
815  }
816  SCIPsetDebugMsg(set, " -> add %s row <%s>[%g,%g](lp depth: %d): dual=%g -> dualrhs=%g\n",
817  row->local ? "local" : "global",
818  SCIProwGetName(row), row->lhs - row->constant, row->rhs - row->constant,
819  row->lpdepth, weight, SCIPaggrRowGetRhs(aggrrow));
820 
821  return SCIP_OKAY;
822 }
823 
824 /** checks validity of an LP row and a corresponding weight */
825 static
827  SCIP_SET* set, /**< global SCIP settings */
828  SCIP_ROW* row, /**< LP row */
829  SCIP_Real weight, /**< weight for scaling */
830  SCIP_Bool* zerocontribution /**< pointer to store whether every row entry is zero within tolerances */
831  )
832 {
833  SCIP_Bool valid = TRUE;
834 
835  *zerocontribution = TRUE;
836 
837  /* dual solution values of 0.0 are always valid */
838  if( REALABS(weight) > QUAD_EPSILON )
839  {
840  *zerocontribution = FALSE;
841 
842  /* check dual feasibility */
843  if( (SCIPsetIsInfinity(set, -row->lhs) && weight > 0.0) || (SCIPsetIsInfinity(set, row->rhs) && weight < 0.0) )
844  {
845  int i;
846 
847  /* ignore slight numerical violations if the contribution of every component of the row is close to zero */
848  if( weight > 0.0 )
849  *zerocontribution = SCIPsetIsDualfeasZero(set, row->rhs * weight);
850  else
851  *zerocontribution = SCIPsetIsDualfeasZero(set, row->lhs * weight);
852 
853  for( i = 0; i < row->len && *zerocontribution; i++ )
854  {
855  if( !SCIPsetIsDualfeasZero(set, weight * row->vals[i]) )
856  *zerocontribution = FALSE;
857  }
858 
859  if( !(*zerocontribution) )
860  {
861  SCIPsetDebugMsg(set, " -> invalid dual solution value %g for row <%s>: lhs=%g, rhs=%g\n",
862  weight, SCIProwGetName(row), row->lhs, row->rhs);
863 
864  valid = FALSE;
865  }
866  }
867  }
868 
869  return valid;
870 }
871 
872 /** calculates the minimal activity of a given aggregation row */
874  SCIP_SET* set, /**< global SCIP settings */
875  SCIP_PROB* transprob, /**< transformed problem data */
876  SCIP_AGGRROW* aggrrow, /**< aggregation row */
877  SCIP_Real* curvarlbs, /**< current lower bounds of active problem variables (or NULL for global bounds) */
878  SCIP_Real* curvarubs, /**< current upper bounds of active problem variables (or NULL for global bounds) */
879  SCIP_Bool* infdelta /**< pointer to store whether at least one variable contributes with an infinite value */
880  )
881 {
882  SCIP_VAR** vars;
883  SCIP_Real QUAD(minact);
884  int* inds;
885  int nnz;
886  int i;
887 
888  vars = SCIPprobGetVars(transprob);
889  assert(vars != NULL);
890 
891  nnz = SCIPaggrRowGetNNz(aggrrow);
892  inds = SCIPaggrRowGetInds(aggrrow);
893 
894  QUAD_ASSIGN(minact, 0.0);
895 
896  if( infdelta != NULL )
897  *infdelta = FALSE;
898 
899  for( i = 0; i < nnz; i++ )
900  {
901  SCIP_Real val;
902  SCIP_Real QUAD(delta);
903  int v = inds[i];
904 
905  assert(SCIPvarGetProbindex(vars[v]) == v);
906 
907  val = SCIPaggrRowGetProbvarValue(aggrrow, v);
908 
909  if( val > 0.0 )
910  {
911  SCIP_Real bnd = (curvarlbs == NULL ? SCIPvarGetLbGlobal(vars[v]) : curvarlbs[v]);
912 
913  if( SCIPsetIsInfinity(set, -bnd) )
914  {
915  if( infdelta != NULL )
916  *infdelta = TRUE;
917 
918  return -SCIPsetInfinity(set);
919  }
920 
921  SCIPquadprecProdDD(delta, val, bnd);
922  }
923  else
924  {
925  SCIP_Real bnd = (curvarubs == NULL ? SCIPvarGetUbGlobal(vars[v]) : curvarubs[v]);
926 
927  if( SCIPsetIsInfinity(set, bnd) )
928  {
929  if( infdelta != NULL )
930  *infdelta = TRUE;
931 
932  return -SCIPsetInfinity(set);
933  }
934 
935  SCIPquadprecProdDD(delta, val, bnd);
936  }
937 
938  /* update minimal activity */
939  SCIPquadprecSumQQ(minact, minact, delta);
940  }
941 
942  /* check whether the minimal activity is infinite */
943  if( SCIPsetIsInfinity(set, QUAD_TO_DBL(minact)) )
944  return SCIPsetInfinity(set);
945  if( SCIPsetIsInfinity(set, -QUAD_TO_DBL(minact)) )
946  return -SCIPsetInfinity(set);
947 
948  return QUAD_TO_DBL(minact);
949 }
950 
951 /** sort local rows by increasing depth and number of nonzeros as tie-breaker */
952 static
954  SCIP_SET* set, /**< global SCIP settings */
955  SCIP_AGGRROW* aggrrow, /**< aggregation row */
956  SCIP_ROW** rows, /**< array of local rows */
957  int* rowinds, /**< array of row indices */
958  int* rowdepth, /**< array of LP depths */
959  int nrows /**< number of local rows */
960  )
961 {
962  int* rownnz;
963  int i;
964 
965  assert(aggrrow != NULL);
966  assert(rows != NULL);
967  assert(nrows > 0);
968  assert(rowinds != NULL);
969  assert(rowdepth != NULL);
970 
971  /* sort row indices by increasing depth */
972  SCIPsortIntInt(rowdepth, rowinds, nrows);
973  assert(rowdepth[0] <= rowdepth[nrows-1]);
974 
975  SCIP_CALL( SCIPsetAllocBufferArray(set, &rownnz, nrows) );
976 
977  /* get number of nonzero entries for every row */
978  for( i = 0; i < nrows; i++ )
979  {
980  SCIP_ROW* row = rows[rowinds[i]];
981  assert(row != NULL);
982 
983  rownnz[i] = row->len;
984  }
985 
986  /* since SCIP has no stable sorting function we sort each bucket separately */
987  for( i = 0; i < nrows; i++ )
988  {
989  int j = i;
990  int d = rowdepth[i];
991 
992  /* search for the next row with a greater depth */
993  while( j+1 < nrows && rowdepth[j+1] == d )
994  j++;
995 
996  /* the bucket has size one */
997  if( j == i )
998  continue;
999 
1000  assert(j-i+1 <= nrows);
1001 
1002  /* sort row indices by increasing number of nonzero elements */
1003  SCIPsortIntIntInt(&rownnz[i], &rowdepth[i], &rowinds[i], j-i+1);
1004  assert(rownnz[i] <= rownnz[j]);
1005 
1006  i = j;
1007  } /*lint --e{850} i is modified in the body of the for loop */
1008 
1009 #ifndef NDEBUG
1010  for( i = 0; i < nrows-1; i++ )
1011  assert(rowdepth[i] < rowdepth[i+1] || (rowdepth[i] == rowdepth[i+1] && rownnz[i] <= rownnz[i+1]));
1012 #endif
1013 
1014  SCIPsetFreeBufferArray(set, &rownnz);
1015 
1016  return SCIP_OKAY;
1017 }
1018 
1019 /** adds locally valid rows to the proof constraint */
1020 static
1022  SCIP_SET* set, /**< global SCIP settings */
1023  SCIP_PROB* transprob, /**< transformed problem */
1024  SCIP_LP* lp, /**< LP data */
1025  SCIP_AGGRROW* proofrow, /**< aggregated row representing the proof */
1026  SCIP_ROW** rows, /**< array if locally valid rows */
1027  SCIP_Real* dualsols, /**< dual solution vector */
1028  int* localrowinds, /**< array of row indecies */
1029  int* localrowdepth, /**< array of row depths */
1030  int nlocalrows, /**< number of local rows stored in rows array */
1031  SCIP_Real* proofact, /**< pointer to store the activity of the proof constraint */
1032  int* validdepth, /**< pointer to store the depth where the proof constraint is valid */
1033  SCIP_Real* curvarlbs, /**< current lower bounds of active problem variables */
1034  SCIP_Real* curvarubs, /**< current upper bounds of active problem variables */
1035  SCIP_Bool* valid /**< pointer store whether the proof constraint is valid */
1036  )
1037 {
1038  SCIP_Bool infdelta;
1039  int i;
1040 
1041  assert(set != NULL);
1042  assert(lp != NULL);
1043 
1044  *validdepth = 0;
1045 
1046  if( !set->conf_uselocalrows )
1047  return SCIP_OKAY;
1048 
1049  SCIPsetDebugMsg(set, "add local rows to dual proof:\n");
1050 
1051  /* check whether the proof is already valid, e.g., violated within the local bounds */
1052  *proofact = SCIPaggrRowGetMinActivity(set, transprob, proofrow, curvarlbs, curvarubs, &infdelta);
1053 
1054  /* we stop if the minimal activity is infinite but all variables have a finite activity delta (bad numerics) */
1055  if( !infdelta && SCIPsetIsInfinity(set, REALABS(*proofact)) )
1056  {
1057  *valid = FALSE;
1058  return SCIP_OKAY;
1059  }
1060 
1061  /* break if the proof is valid w.r.t local bounds
1062  * note: it can happen that the proof contains a variable with an infinite activity delta.
1063  * here, we don't break immediately because we might be able to fix it by adding local rows
1064  */
1065  if( !infdelta && SCIPsetIsGT(set, *proofact, SCIPaggrRowGetRhs(proofrow)) )
1066  {
1067  *valid = TRUE;
1068  return SCIP_OKAY;
1069  }
1070 
1071  /* sort local rows by depth */
1072  SCIP_CALL( sortLocalRows(set, proofrow, rows, localrowinds, localrowdepth, nlocalrows) );
1073 
1074  /* add successively local rows */
1075  for( i = 0; i < nlocalrows; ++i )
1076  {
1077  SCIP_ROW* row;
1078  int r;
1079 
1080  r = localrowinds[i];
1081  row = rows[r];
1082 
1083  assert(row != NULL);
1084  assert(row->len == 0 || row->cols != NULL);
1085  assert(row->len == 0 || row->vals != NULL);
1086  assert(row == lp->lpirows[r]);
1087  assert(row->local);
1088  assert(row->lpdepth == localrowdepth[i]);
1089 
1090  /* ignore dual solution values of 0.0 (in this case: y_i == 0) */
1091  if( REALABS(dualsols[r]) > 0.0 )
1092  {
1093 #ifndef NDEBUG
1094  SCIP_Bool zerocontribution;
1095 
1096  /* check dual feasibility */
1097  *valid = checkDualFeasibility(set, row, dualsols[r], &zerocontribution);
1098  assert(*valid);
1099  assert(!zerocontribution);
1100 #endif
1101 
1102  if( SCIPsetIsDualfeasZero(set, dualsols[r]) )
1103  continue;
1104 
1105  /* add row to dual proof */
1106  SCIP_CALL( addRowToAggrRow(set, row, -dualsols[r], proofrow) );
1107 
1108  /* update depth where the proof is valid */
1109  if( *validdepth < localrowdepth[i] )
1110  *validdepth = localrowdepth[i];
1111 
1112  /* get the new minimal activity */
1113  *proofact = SCIPaggrRowGetMinActivity(set, transprob, proofrow, curvarlbs, curvarubs, &infdelta);
1114 
1115  /* we stop if the minimal activity is infinite but all variables have a finite activity delta (bad numerics) */
1116  if( !infdelta && SCIPsetIsInfinity(set, REALABS(*proofact)) )
1117  {
1118  *valid = FALSE;
1119  goto TERMINATE;
1120  }
1121 
1122  /* break if the proof is valid w.r.t local bounds */
1123  if( !infdelta && SCIPsetIsGT(set, *proofact, SCIPaggrRowGetRhs(proofrow)) )
1124  {
1125  *valid = TRUE;
1126  break;
1127  }
1128  }
1129  }
1130 
1131  /* remove all nearly zero coefficients */
1132  SCIPaggrRowRemoveZeros(set->scip, proofrow, TRUE, valid);
1133 
1134  TERMINATE:
1135  if( !(*valid) )
1136  {
1137  SCIPsetDebugMsg(set, " -> proof is not valid: %g <= %g\n", *proofact, SCIPaggrRowGetRhs(proofrow));
1138  SCIPsetDebugMsg(set, " -> stop due to numerical troubles\n");
1139  }
1140  else
1141  {
1142  *proofact = SCIPaggrRowGetMinActivity(set, transprob, proofrow, curvarlbs, curvarubs, &infdelta);
1143 
1144  /* we stop if the minimal activity is infinite but all variables have a finite activity delta (bad numerics) */
1145  if( !infdelta && SCIPsetIsInfinity(set, REALABS(*proofact)) )
1146  {
1147  *valid = FALSE;
1148  SCIPsetDebugMsg(set, " -> proof is not valid: %g <= %g [infdelta: %u]\n", *proofact, SCIPaggrRowGetRhs(proofrow), infdelta);
1149  }
1150  else if( infdelta || SCIPsetIsLE(set, *proofact, SCIPaggrRowGetRhs(proofrow)) )
1151  {
1152  *valid = FALSE;
1153  SCIPsetDebugMsg(set, " -> proof is not valid: %g <= %g [infdelta: %u]\n", *proofact, SCIPaggrRowGetRhs(proofrow), infdelta);
1154  }
1155  }
1156 
1157  return SCIP_OKAY;
1158 }
1159 
1160 /** calculates a Farkas proof from the current dual LP solution */
1162  SCIP_SET* set, /**< global SCIP settings */
1163  SCIP_PROB* prob, /**< transformed problem */
1164  SCIP_LP* lp, /**< LP data */
1165  SCIP_LPI* lpi, /**< LPI data */
1166  SCIP_TREE* tree, /**< tree data */
1167  SCIP_AGGRROW* farkasrow, /**< aggregated row representing the proof */
1168  SCIP_Real* farkasact, /**< maximal activity of the proof constraint */
1169  int* validdepth, /**< pointer to store the valid depth of the proof constraint */
1170  SCIP_Real* curvarlbs, /**< current lower bounds of active problem variables */
1171  SCIP_Real* curvarubs, /**< current upper bounds of active problem variables */
1172  SCIP_Bool* valid /**< pointer store whether the proof constraint is valid */
1173  )
1174 {
1175  SCIP_ROW** rows;
1176  SCIP_Real* dualfarkas;
1177  SCIP_ROW* row;
1178  int* localrowinds;
1179  int* localrowdepth;
1180  SCIP_Bool infdelta;
1181  int nlocalrows;
1182  int nrows;
1183  int r;
1184 
1185  assert(set != NULL);
1186  assert(prob != NULL);
1187  assert(lp != NULL);
1188  assert(lp->flushed);
1189  assert(lp->solved);
1190  assert(curvarlbs != NULL);
1191  assert(curvarubs != NULL);
1192  assert(valid != NULL);
1193 
1196 
1197  /* get LP rows and problem variables */
1198  rows = SCIPlpGetRows(lp);
1199  nrows = SCIPlpGetNRows(lp);
1200  assert(nrows == 0 || rows != NULL);
1201  assert(nrows == lp->nlpirows);
1202 
1203  /* it can happen that infeasibility is detetected within LP presolve. in that case, the LP solver may not be able to
1204  * to return the dual ray.
1205  */
1206  if( !SCIPlpiHasDualRay(lpi) )
1207  {
1208  *valid = FALSE;
1209  return SCIP_OKAY;
1210  }
1211 
1212  assert(farkasrow != NULL);
1213 
1214  /* allocate temporary memory */
1215  SCIP_CALL( SCIPsetAllocBufferArray(set, &dualfarkas, nrows) );
1216  BMSclearMemoryArray(dualfarkas, nrows);
1217  localrowinds = NULL;
1218  localrowdepth = NULL;
1219  nlocalrows = 0;
1220 
1221  /* get dual Farkas values of rows */
1222  SCIP_CALL( SCIPlpiGetDualfarkas(lpi, dualfarkas) );
1223 
1224  /* check whether the Farkas solution is numerically stable */
1225  for( r = 0; r < nrows; ++r )
1226  {
1227  if( REALABS(dualfarkas[r]) > SOLSTOP )
1228  {
1229  *valid = FALSE;
1230  goto TERMINATE;
1231  }
1232  }
1233 
1234  /* calculate the Farkas row */
1235  *valid = TRUE;
1236  *validdepth = 0;
1237 
1238  for( r = 0; r < nrows; ++r )
1239  {
1240  row = rows[r];
1241  assert(row != NULL);
1242  assert(row->len == 0 || row->cols != NULL);
1243  assert(row->len == 0 || row->vals != NULL);
1244  assert(row == lp->lpirows[r]);
1245 
1246  /* ignore dual ray values of 0.0 (in this case: y_i == z_i == 0) */
1247  if( REALABS(dualfarkas[r]) > 0.0 )
1248  {
1249  SCIP_Bool zerocontribution;
1250 
1251  /* check dual feasibility */
1252  *valid = checkDualFeasibility(set, row, dualfarkas[r], &zerocontribution);
1253 
1254  if( !(*valid) )
1255  goto TERMINATE;
1256 
1257  if( zerocontribution )
1258  continue;
1259 
1260  if( SCIPsetIsDualfeasZero(set, dualfarkas[r]) )
1261  continue;
1262 
1263  if( !row->local )
1264  {
1265  SCIP_CALL( addRowToAggrRow(set, row, -dualfarkas[r], farkasrow) );
1266 
1267  /* due to numerical reasons we want to stop */
1268  if( REALABS(SCIPaggrRowGetRhs(farkasrow)) > NUMSTOP )
1269  {
1270  *valid = FALSE;
1271  goto TERMINATE;
1272  }
1273  }
1274  else
1275  {
1276  int lpdepth = SCIProwGetLPDepth(row);
1277 
1278  if( nlocalrows == 0 && lpdepth < SCIPtreeGetFocusDepth(tree) )
1279  {
1280  SCIP_CALL( SCIPsetAllocBufferArray(set, &localrowinds, nrows-r) );
1281  SCIP_CALL( SCIPsetAllocBufferArray(set, &localrowdepth, nrows-r) );
1282  }
1283 
1284  if( lpdepth < SCIPtreeGetFocusDepth(tree) )
1285  {
1286  assert(localrowinds != NULL);
1287  assert(localrowdepth != NULL);
1288 
1289  localrowinds[nlocalrows] = r;
1290  localrowdepth[nlocalrows++] = lpdepth;
1291  }
1292  }
1293  }
1294  }
1295 
1296  /* remove all coefficients that are too close to zero */
1297  SCIPaggrRowRemoveZeros(set->scip, farkasrow, TRUE, valid);
1298 
1299  if( !(*valid) )
1300  goto TERMINATE;
1301 
1302  infdelta = FALSE;
1303 
1304  /* calculate the current Farkas activity, always using the best bound w.r.t. the Farkas coefficient */
1305  *farkasact = SCIPaggrRowGetMinActivity(set, prob, farkasrow, curvarlbs, curvarubs, &infdelta);
1306 
1307  SCIPsetDebugMsg(set, " -> farkasact=%g farkasrhs=%g [infdelta: %u], \n",
1308  (*farkasact), SCIPaggrRowGetRhs(farkasrow), infdelta);
1309 
1310  /* The constructed proof is not valid, this can happen due to numerical reasons,
1311  * e.g., we only consider rows r with !SCIPsetIsZero(set, dualfarkas[r]),
1312  * or because of local rows were ignored so far.
1313  * Due to the latter case, it might happen at least one variable contributes
1314  * with an infinite value to the activity (see: https://git.zib.de/integer/scip/issues/2743)
1315  */
1316  if( infdelta || SCIPsetIsFeasLE(set, *farkasact, SCIPaggrRowGetRhs(farkasrow)))
1317  {
1318  /* add contribution of local rows */
1319  if( nlocalrows > 0 && set->conf_uselocalrows > 0 )
1320  {
1321  SCIP_CALL( addLocalRows(set, prob, lp, farkasrow, rows, dualfarkas, localrowinds, localrowdepth,
1322  nlocalrows, farkasact, validdepth, curvarlbs, curvarubs, valid) );
1323  }
1324  else
1325  {
1326  *valid = FALSE;
1327  SCIPsetDebugMsg(set, " -> proof is not valid to due infinite activity delta\n");
1328  }
1329  }
1330 
1331  TERMINATE:
1332 
1333  SCIPfreeBufferArrayNull(set->scip, &localrowdepth);
1334  SCIPfreeBufferArrayNull(set->scip, &localrowinds);
1335  SCIPsetFreeBufferArray(set, &dualfarkas);
1336 
1337  return SCIP_OKAY;
1338 }
1339 
1340 /** calculates a dual proof from the current dual LP solution */
1342  SCIP_SET* set, /**< global SCIP settings */
1343  SCIP_PROB* transprob, /**< transformed problem */
1344  SCIP_LP* lp, /**< LP data */
1345  SCIP_LPI* lpi, /**< LPI data */
1346  SCIP_TREE* tree, /**< tree data */
1347  SCIP_AGGRROW* farkasrow, /**< aggregated row representing the proof */
1348  SCIP_Real* farkasact, /**< maximal activity of the proof constraint */
1349  int* validdepth, /**< pointer to store the valid depth of the proof constraint */
1350  SCIP_Real* curvarlbs, /**< current lower bounds of active problem variables */
1351  SCIP_Real* curvarubs, /**< current upper bounds of active problem variables */
1352  SCIP_Bool* valid /**< pointer store whether the proof constraint is valid */
1353  )
1354 {
1355  SCIP_RETCODE retcode;
1356  SCIP_ROW** rows;
1357  SCIP_ROW* row;
1358  SCIP_Real* primsols;
1359  SCIP_Real* dualsols;
1360  SCIP_Real* redcosts;
1361  int* localrowinds;
1362  int* localrowdepth;
1363  SCIP_Bool infdelta;
1364  int nlocalrows;
1365  int nrows;
1366  int ncols;
1367  int r;
1368 
1369  assert(set != NULL);
1370  assert(transprob != NULL);
1371  assert(lp != NULL);
1372  assert(lp->flushed);
1373  assert(lp->solved);
1374  assert(curvarlbs != NULL);
1375  assert(curvarubs != NULL);
1376  assert(valid != NULL);
1377 
1378  *validdepth = 0;
1379  *valid = TRUE;
1380 
1381  localrowinds = NULL;
1382  localrowdepth = NULL;
1383  nlocalrows = 0;
1384 
1385  /* get LP rows and problem variables */
1386  rows = SCIPlpGetRows(lp);
1387  nrows = SCIPlpGetNRows(lp);
1388  ncols = SCIPlpGetNCols(lp);
1389  assert(nrows == 0 || rows != NULL);
1390  assert(nrows == lp->nlpirows);
1391 
1392  /* get temporary memory */
1393  SCIP_CALL( SCIPsetAllocBufferArray(set, &primsols, ncols) );
1394  SCIP_CALL( SCIPsetAllocBufferArray(set, &dualsols, nrows) );
1395  SCIP_CALL( SCIPsetAllocBufferArray(set, &redcosts, ncols) );
1396 
1397  /* get solution from LPI */
1398  retcode = SCIPlpiGetSol(lpi, NULL, primsols, dualsols, NULL, redcosts);
1399  if( retcode == SCIP_LPERROR ) /* on an error in the LP solver, just abort the conflict analysis */
1400  {
1401  *valid = FALSE;
1402  goto TERMINATE;
1403  }
1404  SCIP_CALL( retcode );
1405 #ifdef SCIP_DEBUG
1406  {
1407  SCIP_Real objval;
1408  SCIP_CALL( SCIPlpiGetObjval(lpi, &objval) );
1409  SCIPsetDebugMsg(set, " -> LP objval: %g\n", objval);
1410  }
1411 #endif
1412 
1413  /* check whether the dual solution is numerically stable */
1414  for( r = 0; r < nrows; ++r )
1415  {
1416  if( REALABS(dualsols[r]) > SOLSTOP )
1417  {
1418  *valid = FALSE;
1419  goto TERMINATE;
1420  }
1421  }
1422 
1423  /* clear the proof */
1424  SCIPaggrRowClear(farkasrow);
1425 
1426  /* Let y be the dual solution and r be the reduced cost vector. Let z be defined as
1427  * z_i := y_i if i is a global row,
1428  * z_i := 0 if i is a local row.
1429  * Define the set X := {x | lhs <= Ax <= rhs, lb <= x <= ub, c^Tx <= c*}, with c* being the current primal bound.
1430  * Then the following inequalities are valid for all x \in X:
1431  * - c* <= -c^Tx
1432  * <=> z^TAx - c* <= (z^TA - c^T) x
1433  * <=> z^TAx - c* <= (y^TA - c^T - (y-z)^TA) x
1434  * <=> z^TAx - c* <= (-r^T - (y-z)^TA) x (dual feasibility of (y,r): y^TA + r^T == c^T)
1435  * Because lhs <= Ax <= rhs and lb <= x <= ub, the inequality can be relaxed to give
1436  * min{z^Tq | lhs <= q <= rhs} - c* <= max{(-r^T - (y-z)^TA) x | lb <= x <= ub}, or X = {}.
1437  *
1438  * The resulting dual row is: z^T{lhs,rhs} - c* <= (-r^T - (y-z)^TA){lb,ub},
1439  * where lhs, rhs, lb, and ub are selected in order to maximize the feasibility of the row.
1440  */
1441 
1442  /* add the objective function to the aggregation row with respect to the current cutoff bound
1443  *
1444  * for an integral objective the right-hand side is reduced by the cutoff bound delta to cut off up to the next
1445  * possible objective value below the cutoff bound
1446  */
1447  SCIP_CALL( SCIPaggrRowAddObjectiveFunction(set->scip, farkasrow, lp->cutoffbound - (SCIPprobIsObjIntegral(transprob) ? SCIPsetCutoffbounddelta(set) : 0.0), 1.0) );
1448 
1449  /* dual row: z^T{lhs,rhs} - c* <= (-r^T - (y-z)^TA){lb,ub}
1450  * process rows: add z^T{lhs,rhs} to the dual row's left hand side, and -(y-z)^TA to the dual row's coefficients
1451  */
1452  for( r = 0; r < nrows; ++r )
1453  {
1454  row = rows[r];
1455  assert(row != NULL);
1456  assert(row->len == 0 || row->cols != NULL);
1457  assert(row->len == 0 || row->vals != NULL);
1458  assert(row == lp->lpirows[r]);
1459 
1460  /* ignore dual solution values of 0.0 (in this case: y_i == z_i == 0) */
1461  if( REALABS(dualsols[r]) > 0.0 )
1462  {
1463  SCIP_Bool zerocontribution;
1464 
1465  /* check dual feasibility */
1466  *valid = checkDualFeasibility(set, row, dualsols[r], &zerocontribution);
1467 
1468  if( !(*valid) )
1469  goto TERMINATE;
1470 
1471  if( zerocontribution )
1472  continue;
1473 
1474  if( SCIPsetIsDualfeasZero(set, dualsols[r]) )
1475  continue;
1476 
1477  /* skip local row */
1478  if( !row->local )
1479  {
1480  SCIP_CALL( addRowToAggrRow(set, row, -dualsols[r], farkasrow) );
1481 
1482  /* due to numerical reasons we want to stop */
1483  if( REALABS(SCIPaggrRowGetRhs(farkasrow)) > NUMSTOP )
1484  {
1485  *valid = FALSE;
1486  goto TERMINATE;
1487  }
1488  }
1489  else
1490  {
1491  int lpdepth = SCIProwGetLPDepth(row);
1492 
1493  if( nlocalrows == 0 && lpdepth < SCIPtreeGetFocusDepth(tree) )
1494  {
1495  SCIP_CALL( SCIPsetAllocBufferArray(set, &localrowinds, nrows-r) );
1496  SCIP_CALL( SCIPsetAllocBufferArray(set, &localrowdepth, nrows-r) );
1497  }
1498 
1499  if( lpdepth < SCIPtreeGetFocusDepth(tree) )
1500  {
1501  assert(localrowinds != NULL);
1502  assert(localrowdepth != NULL);
1503 
1504  localrowinds[nlocalrows] = r;
1505  localrowdepth[nlocalrows++] = lpdepth;
1506  }
1507  }
1508  }
1509  }
1510 
1511  /* remove all nearly zero coefficients */
1512  SCIPaggrRowRemoveZeros(set->scip, farkasrow, TRUE, valid);
1513 
1514  if( !(*valid) )
1515  goto TERMINATE;
1516 
1517  infdelta = FALSE;
1518 
1519  /* check validity of the proof */
1520  *farkasact = SCIPaggrRowGetMinActivity(set, transprob, farkasrow, curvarlbs, curvarubs, &infdelta);
1521 
1522  SCIPsetDebugMsg(set, " -> farkasact=%g farkasrhs=%g [infdelta: %u], \n",
1523  (*farkasact), SCIPaggrRowGetRhs(farkasrow), infdelta);
1524 
1525  /* The constructed proof is not valid, this can happen due to numerical reasons,
1526  * e.g., we only consider rows r with !SCIPsetIsZero(set, dualsol[r]),
1527  * or because of local rows were ignored so far.
1528  * Due to the latter case, it might happen at least one variable contributes
1529  * with an infinite value to the activity (see: https://git.zib.de/integer/scip/issues/2743)
1530  */
1531  if( infdelta || SCIPsetIsFeasLE(set, *farkasact, SCIPaggrRowGetRhs(farkasrow)))
1532  {
1533  /* add contribution of local rows */
1534  if( nlocalrows > 0 && set->conf_uselocalrows > 0 )
1535  {
1536  SCIP_CALL( addLocalRows(set, transprob, lp, farkasrow, rows, dualsols, localrowinds, localrowdepth,
1537  nlocalrows, farkasact, validdepth, curvarlbs, curvarubs, valid) );
1538  }
1539  else
1540  {
1541  *valid = FALSE;
1542  SCIPsetDebugMsg(set, " -> proof is not valid to due infinite activity delta\n");
1543  }
1544  }
1545 
1546  TERMINATE:
1547 
1548  SCIPfreeBufferArrayNull(set->scip, &localrowdepth);
1549  SCIPfreeBufferArrayNull(set->scip, &localrowinds);
1550  SCIPsetFreeBufferArray(set, &redcosts);
1551  SCIPsetFreeBufferArray(set, &dualsols);
1552  SCIPsetFreeBufferArray(set, &primsols);
1553 
1554  return SCIP_OKAY;
1555 }
1556 
1557 
1558 /*
1559  * pseudo solution conflict analysis
1560  */
1561 
1562 /** analyzes a pseudo solution with objective value exceeding the current cutoff to find out the bound changes on
1563  * variables that were responsible for the objective value degradation;
1564  * on success, calls standard conflict analysis with the responsible variables as starting conflict set, thus creating
1565  * a conflict constraint out of the resulting conflict set;
1566  * updates statistics for pseudo solution conflict analysis
1567  */
1569  SCIP_CONFLICT* conflict, /**< conflict analysis data */
1570  BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
1571  SCIP_SET* set, /**< global SCIP settings */
1572  SCIP_STAT* stat, /**< problem statistics */
1573  SCIP_PROB* transprob, /**< transformed problem */
1574  SCIP_PROB* origprob, /**< original problem */
1575  SCIP_TREE* tree, /**< branch and bound tree */
1576  SCIP_REOPT* reopt, /**< reoptimization data structure */
1577  SCIP_LP* lp, /**< LP data */
1578  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1579  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1580  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1581  SCIP_Bool* success /**< pointer to store whether a conflict constraint was created, or NULL */
1582  )
1583 {
1584  SCIP_VAR** vars;
1585  SCIP_VAR* var;
1586  SCIP_Real* curvarlbs;
1587  SCIP_Real* curvarubs;
1588  int* lbchginfoposs;
1589  int* ubchginfoposs;
1590  SCIP_Real* pseudocoefs;
1591  SCIP_Real pseudolhs;
1592  SCIP_Real pseudoact;
1593  int nvars;
1594  int v;
1595 
1596  assert(conflict != NULL);
1597  assert(conflict->nconflictsets == 0);
1598  assert(set != NULL);
1599  assert(stat != NULL);
1600  assert(transprob != NULL);
1601  assert(lp != NULL);
1602  assert(!SCIPsetIsInfinity(set, -SCIPlpGetPseudoObjval(lp, set, transprob)));
1603  assert(!SCIPsetIsInfinity(set, lp->cutoffbound));
1604 
1605  if( success != NULL )
1606  *success = FALSE;
1607 
1608  /* check, if pseudo solution conflict analysis is enabled */
1609  if( !set->conf_enable || !set->conf_usepseudo )
1610  return SCIP_OKAY;
1611 
1612  /* check, if there are any conflict handlers to use a conflict set */
1613  if( set->nconflicthdlrs == 0 )
1614  return SCIP_OKAY;
1615 
1616  SCIPsetDebugMsg(set, "analyzing pseudo solution (obj: %g) that exceeds objective limit (%g)\n",
1617  SCIPlpGetPseudoObjval(lp, set, transprob), lp->cutoffbound);
1618 
1620  conflict->conflictset->usescutoffbound = TRUE;
1621 
1622  /* start timing */
1623  SCIPclockStart(conflict->pseudoanalyzetime, set);
1624  conflict->npseudocalls++;
1625 
1626  vars = transprob->vars;
1627  nvars = transprob->nvars;
1628  assert(nvars == 0 || vars != NULL);
1629 
1630  /* The current primal bound c* gives an upper bound for the current pseudo objective value:
1631  * min{c^T x | lb <= x <= ub} <= c*.
1632  * We have to transform this row into a >= inequality in order to use methods above:
1633  * -c* <= max{-c^T x | lb <= x <= ub}.
1634  * In the local subproblem, this row is violated. We want to undo bound changes while still keeping the
1635  * row violated.
1636  */
1637 
1638  /* get temporary memory for remembering variables' current bounds and corresponding bound change information
1639  * positions in variable's bound change information arrays
1640  */
1641  SCIP_CALL( SCIPsetAllocBufferArray(set, &curvarlbs, nvars) );
1642  SCIP_CALL( SCIPsetAllocBufferArray(set, &curvarubs, nvars) );
1643  SCIP_CALL( SCIPsetAllocBufferArray(set, &lbchginfoposs, nvars) );
1644  SCIP_CALL( SCIPsetAllocBufferArray(set, &ubchginfoposs, nvars) );
1645 
1646  /* get temporary memory for infeasibility proof coefficients */
1647  SCIP_CALL( SCIPsetAllocBufferArray(set, &pseudocoefs, nvars) );
1648 
1649  /* for an integral objective use the cutoff bound reduced by the cutoff bound delta to cut off up to the next better
1650  * objective value
1651  */
1652  pseudolhs = -(lp->cutoffbound - (SCIPprobIsObjIntegral(transprob) ? SCIPsetCutoffbounddelta(set) : 0.0));
1653 
1654  /* store the objective values as infeasibility proof coefficients, and recalculate the pseudo activity */
1655  pseudoact = 0.0;
1656  for( v = 0; v < nvars; ++v )
1657  {
1658  var = vars[v];
1659  pseudocoefs[v] = -SCIPvarGetObj(var);
1660  curvarlbs[v] = SCIPvarGetLbLocal(var);
1661  curvarubs[v] = SCIPvarGetUbLocal(var);
1662  lbchginfoposs[v] = var->nlbchginfos-1;
1663  ubchginfoposs[v] = var->nubchginfos-1;
1664 
1665  if( SCIPsetIsZero(set, pseudocoefs[v]) )
1666  {
1667  pseudocoefs[v] = 0.0;
1668  continue;
1669  }
1670 
1671  if( pseudocoefs[v] > 0.0 )
1672  pseudoact += pseudocoefs[v] * curvarubs[v];
1673  else
1674  pseudoact += pseudocoefs[v] * curvarlbs[v];
1675  }
1676  assert(SCIPsetIsFeasEQ(set, pseudoact, -SCIPlpGetPseudoObjval(lp, set, transprob)));
1677  SCIPsetDebugMsg(set, " -> recalculated pseudo infeasibility proof: %g <= %g\n", pseudolhs, pseudoact);
1678 
1679  /* check, if the pseudo row is still violated (after recalculation of pseudo activity) */
1680  if( SCIPsetIsFeasGT(set, pseudolhs, pseudoact) )
1681  {
1682  int nconss;
1683  int nliterals;
1684  int nreconvconss;
1685  int nreconvliterals;
1686 
1687  /* undo bound changes without destroying the infeasibility proof */
1688  SCIP_CALL( SCIPundoBdchgsProof(set, transprob, SCIPtreeGetCurrentDepth(tree), pseudocoefs, pseudolhs, &pseudoact,
1689  curvarlbs, curvarubs, lbchginfoposs, ubchginfoposs, NULL, NULL, NULL, lp->lpi) );
1690 
1691  /* analyze conflict on remaining bound changes */
1692  SCIP_CALL( SCIPconflictAnalyzeRemainingBdchgs(conflict, blkmem, set, stat, transprob, tree, FALSE, \
1693  lbchginfoposs, ubchginfoposs, &nconss, &nliterals, &nreconvconss, &nreconvliterals) );
1694  conflict->npseudosuccess += (nconss > 0 ? 1 : 0);
1695  conflict->npseudoconfconss += nconss;
1696  conflict->npseudoconfliterals += nliterals;
1697  conflict->npseudoreconvconss += nreconvconss;
1698  conflict->npseudoreconvliterals += nreconvliterals;
1699  if( success != NULL )
1700  *success = (nconss > 0);
1701  }
1702 
1703  /* free temporary memory */
1704  SCIPsetFreeBufferArray(set, &pseudocoefs);
1705  SCIPsetFreeBufferArray(set, &ubchginfoposs);
1706  SCIPsetFreeBufferArray(set, &lbchginfoposs);
1707  SCIPsetFreeBufferArray(set, &curvarubs);
1708  SCIPsetFreeBufferArray(set, &curvarlbs);
1709 
1710  /* flush conflict set storage */
1711  SCIP_CALL( SCIPconflictFlushConss(conflict, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cliquetable) );
1712 
1713  /* stop timing */
1714  SCIPclockStop(conflict->pseudoanalyzetime, set);
1715 
1716  return SCIP_OKAY;
1717 }
1718 
1719 /** gets time in seconds used for analyzing pseudo solution conflicts */
1721  SCIP_CONFLICT* conflict /**< conflict analysis data */
1722  )
1723 {
1724  assert(conflict != NULL);
1725 
1726  return SCIPclockGetTime(conflict->pseudoanalyzetime);
1727 }
1728 
1729 /** gets number of calls to pseudo solution conflict analysis */
1731  SCIP_CONFLICT* conflict /**< conflict analysis data */
1732  )
1733 {
1734  assert(conflict != NULL);
1735 
1736  return conflict->npseudocalls;
1737 }
1738 
1739 /** gets number of calls to pseudo solution conflict analysis that yield at least one conflict constraint */
1741  SCIP_CONFLICT* conflict /**< conflict analysis data */
1742  )
1743 {
1744  assert(conflict != NULL);
1745 
1746  return conflict->npseudosuccess;
1747 }
1748 
1749 /** gets number of conflict constraints detected in pseudo solution conflict analysis */
1751  SCIP_CONFLICT* conflict /**< conflict analysis data */
1752  )
1753 {
1754  assert(conflict != NULL);
1755 
1756  return conflict->npseudoconfconss;
1757 }
1758 
1759 /** gets total number of literals in conflict constraints created in pseudo solution conflict analysis */
1761  SCIP_CONFLICT* conflict /**< conflict analysis data */
1762  )
1763 {
1764  assert(conflict != NULL);
1765 
1766  return conflict->npseudoconfliterals;
1767 }
1768 
1769 /** gets number of reconvergence constraints detected in pseudo solution conflict analysis */
1771  SCIP_CONFLICT* conflict /**< conflict analysis data */
1772  )
1773 {
1774  assert(conflict != NULL);
1775 
1776  return conflict->npseudoreconvconss;
1777 }
1778 
1779 /** gets total number of literals in reconvergence constraints created in pseudo solution conflict analysis */
1781  SCIP_CONFLICT* conflict /**< conflict analysis data */
1782  )
1783 {
1784  assert(conflict != NULL);
1785 
1786  return conflict->npseudoreconvliterals;
1787 }
1788 
1789 /** actually performs analysis of infeasible LP */
1790 static
1792  SCIP_CONFLICT* conflict, /**< conflict analysis data */
1793  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
1794  BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
1795  SCIP_SET* set, /**< global SCIP settings */
1796  SCIP_STAT* stat, /**< problem statistics */
1797  SCIP_PROB* transprob, /**< transformed problem */
1798  SCIP_PROB* origprob, /**< original problem */
1799  SCIP_TREE* tree, /**< branch and bound tree */
1800  SCIP_REOPT* reopt, /**< reoptimization data structure */
1801  SCIP_LP* lp, /**< LP data */
1802  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1803  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1804  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1805  SCIP_Bool diving, /**< are we in strong branching or diving mode? */
1806  SCIP_Bool* dualproofsuccess, /**< pointer to store success result of dual proof analysis */
1807  int* iterations, /**< pointer to store the total number of LP iterations used */
1808  int* nconss, /**< pointer to store the number of generated conflict constraints */
1809  int* nliterals, /**< pointer to store the number of literals in generated conflict constraints */
1810  int* nreconvconss, /**< pointer to store the number of generated reconvergence constraints */
1811  int* nreconvliterals, /**< pointer to store the number of literals generated reconvergence constraints */
1812  SCIP_Bool marklpunsolved /**< whether LP should be marked unsolved after analysis (needed for strong branching) */
1813  )
1814 {
1815  SCIP_VAR** vars;
1816  SCIP_AGGRROW* farkasrow;
1817  SCIP_LPI* lpi;
1818  SCIP_Bool valid;
1819  SCIP_Bool globalinfeasible;
1820  int* lbchginfoposs;
1821  int* ubchginfoposs;
1822  int validdepth;
1823  int nvars;
1824  int v;
1825  SCIP_Real* curvarlbs;
1826  SCIP_Real* curvarubs;
1827  SCIP_Real farkasactivity;
1828 
1829  assert(conflict != NULL);
1830  assert(conflict->nconflictsets == 0);
1831  assert(set != NULL);
1832  assert(SCIPprobAllColsInLP(transprob, set, lp)); /* LP conflict analysis is only valid, if all variables are known */
1833  assert(stat != NULL);
1834  assert(transprob != NULL);
1835  assert(lp != NULL);
1836  assert(lp->flushed);
1837  assert(lp->solved);
1838  assert(iterations != NULL);
1839  assert(nconss != NULL);
1840  assert(nliterals != NULL);
1841  assert(nreconvconss != NULL);
1842  assert(nreconvliterals != NULL);
1843 
1844  *iterations = 0;
1845  *nconss = 0;
1846  *nliterals = 0;
1847  *nreconvconss = 0;
1848  *nreconvliterals = 0;
1849 
1850  vars = transprob->vars;
1851  nvars = transprob->nvars;
1852 
1853  valid = TRUE;
1854  validdepth = 0;
1855 
1856  /* get LP solver interface */
1857  lpi = SCIPlpGetLPI(lp);
1860 
1861  if( !SCIPlpiIsPrimalInfeasible(lpi) )
1862  {
1863  SCIP_Real objval;
1864 
1865  assert(!SCIPlpDivingObjChanged(lp));
1866 
1867  /* make sure, a dual feasible solution exists, that exceeds the objective limit;
1868  * With FASTMIP setting, CPLEX does not apply the final pivot to reach the dual solution exceeding the objective
1869  * limit. Therefore, we have to either turn off FASTMIP and resolve the problem or continue solving it without
1870  * objective limit for at least one iteration. It seems that the strategy to continue with FASTMIP for one
1871  * additional simplex iteration yields better results.
1872  */
1873  SCIP_CALL( SCIPlpiGetObjval(lpi, &objval) );
1874  if( objval < lp->lpiobjlim )
1875  {
1876  SCIP_RETCODE retcode;
1877 
1878  /* temporarily disable objective limit and install an iteration limit */
1881 
1882  /* start LP timer */
1883  SCIPclockStart(stat->conflictlptime, set);
1884 
1885  /* resolve LP */
1886  retcode = SCIPlpiSolveDual(lpi);
1887 
1888  /* stop LP timer */
1889  SCIPclockStop(stat->conflictlptime, set);
1890 
1891  /* check return code of LP solving call */
1892  valid = (retcode != SCIP_LPERROR);
1893  if( valid )
1894  {
1895  int iter;
1896 
1897  SCIP_CALL( retcode );
1898 
1899  /* count number of LP iterations */
1900  SCIP_CALL( SCIPlpiGetIterations(lpi, &iter) );
1901  (*iterations) += iter;
1902  stat->nconflictlps++;
1903  stat->nconflictlpiterations += iter;
1904  SCIPsetDebugMsg(set, " -> resolved objlim exceeding LP in %d iterations (total: %" SCIP_LONGINT_FORMAT ") (infeasible:%u, objlim: %u, optimal:%u)\n",
1907  }
1908 
1909  /* reinstall old objective and iteration limits in LP solver */
1912 
1913  /* abort, if the LP produced an error */
1914  if( !valid )
1915  return SCIP_OKAY;
1916  }
1917  }
1919 
1920  if( !SCIPlpiIsPrimalInfeasible(lpi) )
1921  {
1922  SCIP_Real objval;
1923 
1924  assert(!SCIPlpDivingObjChanged(lp));
1925 
1926  SCIP_CALL( SCIPlpiGetObjval(lpi, &objval) );
1927  if( objval < lp->lpiobjlim )
1928  {
1929  SCIPsetDebugMsg(set, " -> LP does not exceed the cutoff bound: obj=%g, cutoff=%g\n", objval, lp->lpiobjlim);
1930  return SCIP_OKAY;
1931  }
1932  else
1933  {
1934  SCIPsetDebugMsg(set, " -> LP exceeds the cutoff bound: obj=%g, cutoff=%g\n", objval, lp->lpiobjlim);
1935  }
1936  }
1937 
1938  assert(valid);
1939 
1940  SCIP_CALL( SCIPaggrRowCreate(set->scip, &farkasrow) );
1941  SCIP_CALL( SCIPsetAllocBufferArray(set, &lbchginfoposs, transprob->nvars) );
1942  SCIP_CALL( SCIPsetAllocBufferArray(set, &ubchginfoposs, transprob->nvars) );
1943 
1944  farkasactivity = 0.0;
1945 
1946  /* get temporary memory for remembering variables' current bounds and corresponding bound change information
1947  * positions in variable's bound change information arrays
1948  */
1949  SCIP_CALL( SCIPsetAllocBufferArray(set, &curvarlbs, nvars) );
1950  SCIP_CALL( SCIPsetAllocBufferArray(set, &curvarubs, nvars) );
1951 
1952  /* get current bounds and current positions in lb/ubchginfos arrays of variables */
1953  valid = TRUE;
1954  for( v = 0; v < nvars && valid; ++v )
1955  {
1956  SCIP_VAR* var;
1957 
1958  var = vars[v];
1959 
1960  curvarlbs[v] = SCIPvarGetLbLP(var, set);
1961  curvarubs[v] = SCIPvarGetUbLP(var, set);
1962  lbchginfoposs[v] = var->nlbchginfos-1;
1963  ubchginfoposs[v] = var->nubchginfos-1;
1964  assert(diving || SCIPsetIsEQ(set, curvarlbs[v], SCIPvarGetLbLocal(var)));
1965  assert(diving || SCIPsetIsEQ(set, curvarubs[v], SCIPvarGetUbLocal(var)));
1966 
1967  /* check, if last bound changes were due to strong branching or diving */
1968  if( diving )
1969  {
1970  SCIP_Real lb;
1971  SCIP_Real ub;
1972 
1973  lb = SCIPvarGetLbLocal(var);
1974  ub = SCIPvarGetUbLocal(var);
1975  if( SCIPsetIsGT(set, curvarlbs[v], lb) )
1976  lbchginfoposs[v] = var->nlbchginfos;
1977  else if( SCIPsetIsLT(set, curvarlbs[v], lb) )
1978  {
1979  /* the bound in the diving LP was relaxed -> the LP is not a subproblem of the current node -> abort! */
1980  /**@todo we could still analyze such a conflict, but we would have to take care with our data structures */
1981  valid = FALSE;
1982  }
1983  if( SCIPsetIsLT(set, curvarubs[v], ub) )
1984  ubchginfoposs[v] = var->nubchginfos;
1985  else if( SCIPsetIsGT(set, curvarubs[v], ub) )
1986  {
1987  /* the bound in the diving LP was relaxed -> the LP is not a subproblem of the current node -> abort! */
1988  /**@todo we could still analyze such a conflict, but we would have to take care with our data structures */
1989  valid = FALSE;
1990  }
1991  }
1992  }
1993 
1994  if( !valid )
1995  goto TERMINATE;
1996 
1997  /* the LP is prooven to be infeasible */
1998  if( SCIPlpiIsPrimalInfeasible(lpi) )
1999  {
2000  SCIP_CALL( SCIPgetFarkasProof(set, transprob, lp, lpi, tree, farkasrow, &farkasactivity, &validdepth,
2001  curvarlbs, curvarubs, &valid) );
2002  }
2003  /* the LP is dual feasible and/or exceeds the current incumbant solution */
2004  else
2005  {
2006  assert(SCIPlpiIsDualFeasible(lpi) || SCIPlpiIsObjlimExc(lpi));
2007  SCIP_CALL( SCIPgetDualProof(set, transprob, lp, lpi, tree, farkasrow, &farkasactivity, &validdepth,
2008  curvarlbs, curvarubs, &valid) );
2009  }
2010 
2011  if( !valid || validdepth >= SCIPtreeGetCurrentDepth(tree) )
2012  goto TERMINATE;
2013 
2014  globalinfeasible = FALSE;
2015 
2016  /* start dual proof analysis */
2017  if( ((set->conf_useinflp == 'b' || set->conf_useinflp == 'd') && conflict->conflictset->conflicttype == SCIP_CONFTYPE_INFEASLP)
2018  || ((set->conf_useboundlp == 'b' || set->conf_useboundlp == 'd') && conflict->conflictset->conflicttype == SCIP_CONFTYPE_BNDEXCEEDING) )
2019  {
2020  /* start dual proof analysis */
2021  SCIP_CALL( SCIPconflictAnalyzeDualProof(conflict, set, stat, blkmem, origprob, transprob, tree, reopt, lp, farkasrow, \
2022  validdepth, curvarlbs, curvarubs, TRUE, &globalinfeasible, dualproofsuccess) );
2023  }
2024 
2025  assert(valid);
2026 
2027  /* todo: in theory, we could apply conflict graph analysis for locally valid proofs, too, but this needs to be implemented */
2028  if( !globalinfeasible && validdepth <= SCIPtreeGetEffectiveRootDepth(tree)
2029  && (((set->conf_useinflp == 'b' || set->conf_useinflp == 'c') && conflict->conflictset->conflicttype == SCIP_CONFTYPE_INFEASLP)
2030  || ((set->conf_useboundlp == 'b' || set->conf_useboundlp == 'c') && conflict->conflictset->conflicttype == SCIP_CONFTYPE_BNDEXCEEDING)) )
2031  {
2032  SCIP_Real* farkascoefs;
2033  SCIP_Real farkaslhs;
2034  int* inds;
2035  int nnz;
2036 
2037 #ifdef SCIP_DEBUG
2038  {
2039  SCIP_Real objlim;
2040  SCIPsetDebugMsg(set, "analyzing conflict on infeasible LP (infeasible: %u, objlimexc: %u, optimal:%u) in depth %d (diving: %u)\n",
2042 
2043  SCIP_CALL( SCIPlpiGetRealpar(lpi, SCIP_LPPAR_OBJLIM, &objlim) );
2044  SCIPsetDebugMsg(set, " -> objective limit in LP solver: %g (in LP: %g)\n", objlim, lp->lpiobjlim);
2045  }
2046 #endif
2047 
2048  SCIP_CALL( SCIPsetAllocBufferArray(set, &farkascoefs, SCIPprobGetNVars(transprob)) );
2049  BMSclearMemoryArray(farkascoefs, SCIPprobGetNVars(transprob));
2050 
2051  farkaslhs = -SCIPaggrRowGetRhs(farkasrow);
2052  farkasactivity = -farkasactivity;
2053 
2054  inds = SCIPaggrRowGetInds(farkasrow);
2055  nnz = SCIPaggrRowGetNNz(farkasrow);
2056 
2057  for( v = 0; v < nnz; v++ )
2058  {
2059  int i = inds[v];
2060 
2061  assert(SCIPvarGetProbindex(vars[i]) == inds[v]);
2062 
2063  farkascoefs[i] = -SCIPaggrRowGetProbvarValue(farkasrow, i);
2064  }
2065 
2066  SCIP_CALL( SCIPrunBoundHeuristic(conflict, set, stat, origprob, transprob, tree, reopt, lp, lpi, blkmem, farkascoefs,
2067  &farkaslhs, &farkasactivity, curvarlbs, curvarubs, lbchginfoposs, ubchginfoposs, iterations, marklpunsolved,
2068  dualproofsuccess, &valid) );
2069 
2070  SCIPsetFreeBufferArray(set, &farkascoefs);
2071 
2072  if( !valid )
2073  goto FLUSHPROOFSETS;
2074 
2075  /* analyze the conflict starting with remaining bound changes */
2076  SCIP_CALL( SCIPconflictAnalyzeRemainingBdchgs(conflict, blkmem, set, stat, transprob, tree, diving, \
2077  lbchginfoposs, ubchginfoposs, nconss, nliterals, nreconvconss, nreconvliterals) );
2078 
2079  /* flush conflict set storage */
2080  SCIP_CALL( SCIPconflictFlushConss(conflict, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, \
2081  eventqueue, cliquetable) );
2082  }
2083 
2084  FLUSHPROOFSETS:
2085  /* flush proof set */
2086  if( SCIPproofsetGetNVars(conflict->proofset) > 0 || conflict->nproofsets > 0 )
2087  {
2088  SCIP_CALL( SCIPconflictFlushProofset(conflict, conflictstore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, \
2089  branchcand, eventqueue, cliquetable) );
2090  }
2091 
2092  TERMINATE:
2093  SCIPsetFreeBufferArray(set, &curvarubs);
2094  SCIPsetFreeBufferArray(set, &curvarlbs);
2095  SCIPsetFreeBufferArray(set, &ubchginfoposs);
2096  SCIPsetFreeBufferArray(set, &lbchginfoposs);
2097  SCIPaggrRowFree(set->scip, &farkasrow);
2098 
2099  return SCIP_OKAY;
2100 }
2101 
2102 
2103 /*
2104  * infeasible strong branching conflict analysis
2105  */
2106 
2107 /** analyses infeasible strong branching sub problems for conflicts */
2109  SCIP_CONFLICT* conflict, /**< conflict analysis data */
2110  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
2111  BMS_BLKMEM* blkmem, /**< block memory buffers */
2112  SCIP_SET* set, /**< global SCIP settings */
2113  SCIP_STAT* stat, /**< dynamic problem statistics */
2114  SCIP_PROB* transprob, /**< transformed problem */
2115  SCIP_PROB* origprob, /**< original problem */
2116  SCIP_TREE* tree, /**< branch and bound tree */
2117  SCIP_REOPT* reopt, /**< reoptimization data structure */
2118  SCIP_LP* lp, /**< LP data */
2119  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2120  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2121  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2122  SCIP_COL* col, /**< LP column with at least one infeasible strong branching subproblem */
2123  SCIP_Bool* downconflict, /**< pointer to store whether a conflict constraint was created for an
2124  * infeasible downwards branch, or NULL */
2125  SCIP_Bool* upconflict /**< pointer to store whether a conflict constraint was created for an
2126  * infeasible upwards branch, or NULL */
2127  )
2128 {
2129  int* cstat;
2130  int* rstat;
2131  SCIP_RETCODE retcode;
2132  SCIP_Bool resolve;
2133  SCIP_Real oldlb;
2134  SCIP_Real oldub;
2135  SCIP_Real newlb;
2136  SCIP_Real newub;
2137  SCIP_Bool dualraysuccess;
2138  int iter;
2139  int nconss;
2140  int nliterals;
2141  int nreconvconss;
2142  int nreconvliterals;
2143 
2144  assert(stat != NULL);
2145  assert(lp != NULL);
2146  assert(lp->flushed);
2147  assert(lp->solved);
2148  assert(SCIPprobAllColsInLP(transprob, set, lp)); /* LP conflict analysis is only valid, if all variables are known */
2149  assert(col != NULL);
2150  assert((col->sbdownvalid && SCIPsetIsGE(set, col->sbdown, lp->cutoffbound)
2151  && SCIPsetFeasCeil(set, col->primsol-1.0) >= col->lb - 0.5)
2152  || (col->sbupvalid && SCIPsetIsGE(set, col->sbup, lp->cutoffbound)
2153  && SCIPsetFeasFloor(set, col->primsol+1.0) <= col->ub + 0.5));
2154  assert(SCIPtreeGetCurrentDepth(tree) > 0);
2155 
2156  if( downconflict != NULL )
2157  *downconflict = FALSE;
2158  if( upconflict != NULL )
2159  *upconflict = FALSE;
2160 
2161  /* check, if infeasible LP conflict analysis is enabled */
2162  if( !set->conf_enable || !set->conf_usesb )
2163  return SCIP_OKAY;
2164 
2165  /* check, if there are any conflict handlers to use a conflict set */
2166  if( set->nconflicthdlrs == 0 )
2167  return SCIP_OKAY;
2168 
2169  /* inform the LPI that strong branch is (temporarily) finished */
2171 
2172  /* start timing */
2173  SCIPclockStart(conflict->sbanalyzetime, set);
2174 
2175  /* get temporary memory for storing current LP basis */
2176  SCIP_CALL( SCIPsetAllocBufferArray(set, &cstat, lp->nlpicols) );
2177  SCIP_CALL( SCIPsetAllocBufferArray(set, &rstat, lp->nlpirows) );
2178 
2179  /* get current LP basis */
2180  SCIP_CALL( SCIPlpiGetBase(lp->lpi, cstat, rstat) );
2181 
2182  /* remember old bounds */
2183  oldlb = col->lb;
2184  oldub = col->ub;
2185 
2186  resolve = FALSE;
2187 
2188  /* is down branch infeasible? */
2189  if( col->sbdownvalid && SCIPsetIsGE(set, col->sbdown, lp->cutoffbound) )
2190  {
2191  newub = SCIPsetFeasCeil(set, col->primsol-1.0);
2192  if( newub >= col->lb - 0.5 )
2193  {
2194  SCIPsetDebugMsg(set, "analyzing conflict on infeasible downwards strongbranch for variable <%s>[%g,%g] in depth %d\n",
2196  SCIPtreeGetCurrentDepth(tree));
2197 
2199  conflict->nsbcalls++;
2200 
2201  /* change the upper bound */
2202  col->ub = newub;
2203  SCIP_CALL( SCIPlpiChgBounds(lp->lpi, 1, &col->lpipos, &col->lb, &col->ub) );
2204 
2205  /* start LP timer */
2206  SCIPclockStart(stat->conflictlptime, set);
2207 
2208  /* resolve the LP */
2209  retcode = SCIPlpiSolveDual(lp->lpi);
2210 
2211  /* stop LP timer */
2212  SCIPclockStop(stat->conflictlptime, set);
2213 
2214  /* check return code of LP solving call */
2215  if( retcode != SCIP_LPERROR )
2216  {
2217  SCIP_CALL( retcode );
2218  }
2219 
2220  if( retcode != SCIP_LPERROR && SCIPlpiIsStable(lp->lpi) )
2221  {
2222  /* count number of LP iterations */
2223  SCIP_CALL( SCIPlpiGetIterations(lp->lpi, &iter) );
2224  stat->nconflictlps++;
2225  stat->nconflictlpiterations += iter;
2226  conflict->nsbiterations += iter;
2227  SCIPsetDebugMsg(set, " -> resolved downwards strong branching LP in %d iterations\n", iter);
2228 
2229  /* perform conflict analysis on infeasible LP; last parameter guarantees status 'solved' on return */
2230  SCIP_CALL( conflictAnalyzeLP(conflict, conflictstore, blkmem, set, stat, transprob, origprob, tree, reopt, \
2231  lp, branchcand, eventqueue, cliquetable, TRUE, &dualraysuccess, &iter, &nconss, &nliterals, \
2232  &nreconvconss, &nreconvliterals, FALSE) );
2233  conflict->nsbsuccess += ((nconss > 0 || dualraysuccess) ? 1 : 0);
2234  conflict->nsbiterations += iter;
2235  conflict->nsbconfconss += nconss;
2236  conflict->nsbconfliterals += nliterals;
2237  conflict->nsbreconvconss += nreconvconss;
2238  conflict->nsbreconvliterals += nreconvliterals;
2239  if( downconflict != NULL )
2240  *downconflict = (nconss > 0);
2241  }
2242 
2243  /* reset the upper bound */
2244  col->ub = oldub;
2245  SCIP_CALL( SCIPlpiChgBounds(lp->lpi, 1, &col->lpipos, &col->lb, &col->ub) );
2246 
2247  /* reset LP basis */
2248  SCIP_CALL( SCIPlpiSetBase(lp->lpi, cstat, rstat) );
2249 
2250  /* mark the LP to be resolved at the end */
2251  resolve = TRUE;
2252  }
2253  }
2254 
2255  /* is up branch infeasible? */
2256  if( col->sbupvalid && SCIPsetIsGE(set, col->sbup, lp->cutoffbound) )
2257  {
2258  newlb = SCIPsetFeasFloor(set, col->primsol+1.0);
2259  if( newlb <= col->ub + 0.5 )
2260  {
2261  SCIPsetDebugMsg(set, "analyzing conflict on infeasible upwards strongbranch for variable <%s>[%g,%g] in depth %d\n",
2263  SCIPtreeGetCurrentDepth(tree));
2264 
2266  conflict->nsbcalls++;
2267 
2268  /* change the lower bound */
2269  col->lb = newlb;
2270  SCIP_CALL( SCIPlpiChgBounds(lp->lpi, 1, &col->lpipos, &col->lb, &col->ub) );
2271 
2272  /* start LP timer */
2273  SCIPclockStart(stat->conflictlptime, set);
2274 
2275  /* resolve the LP */
2276  retcode = SCIPlpiSolveDual(lp->lpi);
2277 
2278  /* stop LP timer */
2279  SCIPclockStop(stat->conflictlptime, set);
2280 
2281  /* check return code of LP solving call */
2282  if( retcode != SCIP_LPERROR )
2283  {
2284  SCIP_CALL( retcode );
2285  }
2286 
2287  if( retcode != SCIP_LPERROR && SCIPlpiIsStable(lp->lpi) )
2288  {
2289  /* count number of LP iterations */
2290  SCIP_CALL( SCIPlpiGetIterations(lp->lpi, &iter) );
2291  stat->nconflictlps++;
2292  stat->nconflictlpiterations += iter;
2293  conflict->nsbiterations += iter;
2294  SCIPsetDebugMsg(set, " -> resolved upwards strong branching LP in %d iterations\n", iter);
2295 
2296  /* perform conflict analysis on infeasible LP; last parameter guarantees status 'solved' on return */
2297  SCIP_CALL( conflictAnalyzeLP(conflict, conflictstore, blkmem, set, stat, transprob, origprob, tree, reopt, \
2298  lp, branchcand, eventqueue, cliquetable, TRUE, &dualraysuccess, &iter, &nconss, &nliterals, \
2299  &nreconvconss, &nreconvliterals, FALSE) );
2300  conflict->nsbsuccess += ((nconss > 0 || dualraysuccess) ? 1 : 0);
2301  conflict->nsbiterations += iter;
2302  conflict->nsbconfconss += nconss;
2303  conflict->nsbconfliterals += nliterals;
2304  conflict->nsbreconvconss += nreconvconss;
2305  conflict->nsbreconvliterals += nreconvliterals;
2306  if( upconflict != NULL )
2307  *upconflict = (nconss > 0);
2308  }
2309 
2310  /* reset the lower bound */
2311  col->lb = oldlb;
2312  SCIP_CALL( SCIPlpiChgBounds(lp->lpi, 1, &col->lpipos, &col->lb, &col->ub) );
2313 
2314  /* reset LP basis */
2315  SCIP_CALL( SCIPlpiSetBase(lp->lpi, cstat, rstat) );
2316 
2317  /* mark the LP to be resolved at the end */
2318  resolve = TRUE;
2319  }
2320  }
2321 
2322  /* free temporary memory for storing current LP basis */
2323  SCIPsetFreeBufferArray(set, &rstat);
2324  SCIPsetFreeBufferArray(set, &cstat);
2325 
2326  assert(lp->flushed);
2327 
2328  /* resolve LP if something has changed in order to synchronize LPI and LP */
2329  if ( resolve )
2330  {
2331  /* start LP timer */
2332  SCIPclockStart(stat->conflictlptime, set);
2333 
2334  /* resolve the LP */
2335  SCIP_CALL( SCIPlpiSolveDual(lp->lpi) );
2336 
2337  /* stop LP timer */
2338  SCIPclockStop(stat->conflictlptime, set);
2339  }
2340 
2341  /* stop timing */
2342  SCIPclockStop(conflict->sbanalyzetime, set);
2343 
2344  /* inform the LPI that strong branch starts (again) */
2346 
2347  return SCIP_OKAY;
2348 }
2349 
2350 /** analyzes an infeasible LP to find out the bound changes on variables that were responsible for the infeasibility;
2351  * on success, calls standard conflict analysis with the responsible variables as starting conflict set, thus creating
2352  * a conflict constraint out of the resulting conflict set;
2353  * updates statistics for infeasible LP conflict analysis
2354  */
2355 static
2357  SCIP_CONFLICT* conflict, /**< conflict analysis data */
2358  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
2359  BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
2360  SCIP_SET* set, /**< global SCIP settings */
2361  SCIP_STAT* stat, /**< problem statistics */
2362  SCIP_PROB* transprob, /**< transformed problem */
2363  SCIP_PROB* origprob, /**< original problem */
2364  SCIP_TREE* tree, /**< branch and bound tree */
2365  SCIP_REOPT* reopt, /**< reoptimization data structure */
2366  SCIP_LP* lp, /**< LP data */
2367  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2368  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2369  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2370  SCIP_Bool* success /**< pointer to store whether a conflict constraint was created, or NULL */
2371  )
2372 {
2373  SCIP_Bool dualraysuccess = FALSE;
2374  SCIP_Longint olddualproofsuccess;
2375  int iterations;
2376  int nconss;
2377  int nliterals;
2378  int nreconvconss;
2379  int nreconvliterals;
2380 
2381  assert(conflict != NULL);
2382  assert(set != NULL);
2383  assert(lp != NULL);
2384  assert(SCIPprobAllColsInLP(transprob, set, lp)); /* LP conflict analysis is only valid, if all variables are known */
2385 
2386  assert(success == NULL || *success == FALSE);
2387 
2388  /* check, if infeasible LP conflict analysis is enabled */
2389  if( !set->conf_enable || set->conf_useinflp == 'o' )
2390  return SCIP_OKAY;
2391 
2392  /* check, if there are any conflict handlers to use a conflict set */
2393  if( set->nconflicthdlrs == 0 )
2394  return SCIP_OKAY;
2395 
2396  SCIPsetDebugMsg(set, "analyzing conflict on infeasible LP in depth %d (solstat: %d, objchanged: %u)\n",
2398 
2399  /* start timing */
2400  SCIPclockStart(conflict->inflpanalyzetime, set);
2401  conflict->ninflpcalls++;
2402 
2404 
2405  olddualproofsuccess = conflict->ndualproofsinfsuccess;
2406 
2407  /* perform conflict analysis */
2408  SCIP_CALL( conflictAnalyzeLP(conflict, conflictstore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, \
2409  cliquetable, SCIPlpDiving(lp), &dualraysuccess, &iterations, &nconss, &nliterals, &nreconvconss, &nreconvliterals, TRUE) );
2410  conflict->ninflpsuccess += ((nconss > 0 || conflict->ndualproofsinfsuccess > olddualproofsuccess) ? 1 : 0);
2411  conflict->ninflpiterations += iterations;
2412  conflict->ninflpconfconss += nconss;
2413  conflict->ninflpconfliterals += nliterals;
2414  conflict->ninflpreconvconss += nreconvconss;
2415  conflict->ninflpreconvliterals += nreconvliterals;
2416  if( success != NULL )
2417  *success = (nconss > 0 || conflict->ndualproofsinfsuccess > olddualproofsuccess);
2418 
2419  /* stop timing */
2420  SCIPclockStop(conflict->inflpanalyzetime, set);
2421 
2422  return SCIP_OKAY;
2423 }
2424 
2425 /** analyzes a bound exceeding LP to find out the bound changes on variables that were responsible for exceeding the
2426  * primal bound;
2427  * on success, calls standard conflict analysis with the responsible variables as starting conflict set, thus creating
2428  * a conflict constraint out of the resulting conflict set;
2429  * updates statistics for bound exceeding LP conflict analysis
2430  */
2431 static
2433  SCIP_CONFLICT* conflict, /**< conflict analysis data */
2434  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
2435  BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
2436  SCIP_SET* set, /**< global SCIP settings */
2437  SCIP_STAT* stat, /**< problem statistics */
2438  SCIP_PROB* transprob, /**< transformed problem */
2439  SCIP_PROB* origprob, /**< original problem */
2440  SCIP_TREE* tree, /**< branch and bound tree */
2441  SCIP_REOPT* reopt, /**< reoptimization data structure */
2442  SCIP_LP* lp, /**< LP data */
2443  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2444  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2445  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2446  SCIP_Bool* success /**< pointer to store whether a conflict constraint was created, or NULL */
2447  )
2448 {
2449  SCIP_Bool dualraysuccess;
2450  SCIP_Longint oldnsuccess;
2451  int iterations;
2452  int nconss;
2453  int nliterals;
2454  int nreconvconss;
2455  int nreconvliterals;
2456 
2457  assert(conflict != NULL);
2458  assert(set != NULL);
2459  assert(lp != NULL);
2460  assert(!SCIPlpDivingObjChanged(lp));
2461  assert(SCIPprobAllColsInLP(transprob, set, lp)); /* LP conflict analysis is only valid, if all variables are known */
2462 
2463  assert(success == NULL || *success == FALSE);
2464 
2465  /* check, if bound exceeding LP conflict analysis is enabled */
2466  if( !set->conf_enable || set->conf_useboundlp == 'o')
2467  return SCIP_OKAY;
2468 
2469  /* check, if there are any conflict handlers to use a conflict set */
2470  if( set->nconflicthdlrs == 0 )
2471  return SCIP_OKAY;
2472 
2473  SCIPsetDebugMsg(set, "analyzing conflict on bound exceeding LP in depth %d (solstat: %d)\n",
2475 
2476  /* start timing */
2477  SCIPclockStart(conflict->boundlpanalyzetime, set);
2478  conflict->nboundlpcalls++;
2479 
2480  /* mark the conflict to depend on the cutoff bound */
2482  conflict->conflictset->usescutoffbound = TRUE;
2483 
2484  oldnsuccess = conflict->ndualproofsbndsuccess + conflict->ndualproofsinfsuccess;
2485 
2486  /* perform conflict analysis */
2487  SCIP_CALL( conflictAnalyzeLP(conflict, conflictstore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, \
2488  cliquetable, SCIPlpDiving(lp), &dualraysuccess, &iterations, &nconss, &nliterals, &nreconvconss, &nreconvliterals, TRUE) );
2489  conflict->nboundlpsuccess += ((nconss > 0 || conflict->ndualproofsbndsuccess + conflict->ndualproofsinfsuccess > oldnsuccess) ? 1 : 0);
2490  conflict->nboundlpiterations += iterations;
2491  conflict->nboundlpconfconss += nconss;
2492  conflict->nboundlpconfliterals += nliterals;
2493  conflict->nboundlpreconvconss += nreconvconss;
2494  conflict->nboundlpreconvliterals += nreconvliterals;
2495  if( success != NULL )
2496  *success = (nconss > 0 || conflict->ndualproofsbndsuccess + conflict->ndualproofsinfsuccess > oldnsuccess);
2497 
2498  /* stop timing */
2499  SCIPclockStop(conflict->boundlpanalyzetime, set);
2500 
2501  return SCIP_OKAY;
2502 }
2503 
2504 /** analyzes an infeasible or bound exceeding LP to find out the bound changes on variables that were responsible for the
2505  * infeasibility or for exceeding the primal bound;
2506  * on success, calls standard conflict analysis with the responsible variables as starting conflict set, thus creating
2507  * a conflict constraint out of the resulting conflict set;
2508  * updates statistics for infeasible or bound exceeding LP conflict analysis;
2509  * may only be called if SCIPprobAllColsInLP()
2510  */
2512  SCIP_CONFLICT* conflict, /**< conflict analysis data */
2513  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
2514  BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
2515  SCIP_SET* set, /**< global SCIP settings */
2516  SCIP_STAT* stat, /**< problem statistics */
2517  SCIP_PROB* transprob, /**< transformed problem */
2518  SCIP_PROB* origprob, /**< original problem */
2519  SCIP_TREE* tree, /**< branch and bound tree */
2520  SCIP_REOPT* reopt, /**< reoptimization data structure */
2521  SCIP_LP* lp, /**< LP data */
2522  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2523  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2524  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2525  SCIP_Bool* success /**< pointer to store whether a conflict constraint was created, or NULL */
2526  )
2527 {
2528  SCIP_LPSOLVALS storedsolvals;
2529  SCIP_COLSOLVALS* storedcolsolvals;
2530  SCIP_ROWSOLVALS* storedrowsolvals;
2531  int c;
2532  int r;
2533 
2534  if( success != NULL )
2535  *success = FALSE;
2536 
2537  /* check if the conflict analysis is applicable */
2538  if( !set->conf_enable || (set->conf_useinflp == 'o' && set->conf_useboundlp == 'o') )
2539  return SCIP_OKAY;
2540 
2541  /* in rare cases, it might happen that the solution stati of the LP and the LPI are out of sync; in particular this
2542  * happens when a new incumbent which cuts off the current node is found during the LP solving loop; in this case the
2543  * LP has status objlimit, but if diving has been used, the LPI only has the basis information, but is not solved
2544  *
2545  * @todo: alternatively, solve the LPI
2546  */
2547  if( !SCIPlpiWasSolved(SCIPlpGetLPI(lp)) )
2548  return SCIP_OKAY;
2549 
2550  /* LP conflict analysis is only valid, if all variables are known */
2551  assert( SCIPprobAllColsInLP(transprob, set, lp) );
2553  || (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL && set->lp_disablecutoff == 1) );
2554 
2555  /* save status */
2556  storedsolvals.lpsolstat = lp->lpsolstat;
2557  storedsolvals.lpobjval = lp->lpobjval;
2558  storedsolvals.primalfeasible = lp->primalfeasible;
2559  storedsolvals.primalchecked = lp->primalchecked;
2560  storedsolvals.dualfeasible = lp->dualfeasible;
2561  storedsolvals.dualchecked = lp->dualchecked;
2562  storedsolvals.solisbasic = lp->solisbasic;
2563  storedsolvals.lpissolved = lp->solved;
2564 
2565  /* store solution values */
2566  SCIP_CALL( SCIPsetAllocBufferArray(set, &storedcolsolvals, lp->ncols) );
2567  SCIP_CALL( SCIPsetAllocBufferArray(set, &storedrowsolvals, lp->nrows) );
2568  for (c = 0; c < lp->ncols; ++c)
2569  {
2570  SCIP_COL* col;
2571 
2572  col = lp->cols[c];
2573  assert( col != NULL );
2574 
2575  storedcolsolvals[c].primsol = col->primsol;
2576  storedcolsolvals[c].redcost = col->redcost;
2577  storedcolsolvals[c].basisstatus = col->basisstatus; /*lint !e641 !e732*/
2578  }
2579  for (r = 0; r < lp->nrows; ++r)
2580  {
2581  SCIP_ROW* row;
2582 
2583  row = lp->rows[r];
2584  assert( row != NULL );
2585 
2586  if ( lp->lpsolstat == SCIP_LPSOLSTAT_INFEASIBLE )
2587  storedrowsolvals[r].dualsol = row->dualfarkas;
2588  else
2589  {
2590  assert( lp->lpsolstat == SCIP_LPSOLSTAT_OBJLIMIT ||
2591  (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL && set->lp_disablecutoff == 1) );
2592  storedrowsolvals[r].dualsol = row->dualsol;
2593  }
2594  storedrowsolvals[r].activity = row->activity;
2595  storedrowsolvals[r].basisstatus = row->basisstatus; /*lint !e641 !e732*/
2596  }
2597 
2598  /* check, if the LP was infeasible or bound exceeding */
2600  {
2601  SCIP_CALL( conflictAnalyzeInfeasibleLP(conflict, conflictstore, blkmem, set, stat, transprob, origprob, tree, \
2602  reopt, lp, branchcand, eventqueue, cliquetable, success) );
2603  }
2604  else
2605  {
2606  SCIP_CALL( conflictAnalyzeBoundexceedingLP(conflict, conflictstore, blkmem, set, stat, transprob, origprob, tree, \
2607  reopt, lp, branchcand, eventqueue, cliquetable, success) );
2608  }
2609 
2610  /* possibly restore solution values */
2612  {
2613  /* restore status */
2614  lp->lpsolstat = storedsolvals.lpsolstat;
2615  lp->lpobjval = storedsolvals.lpobjval;
2616  lp->primalfeasible = storedsolvals.primalfeasible;
2617  lp->primalchecked = storedsolvals.primalchecked;
2618  lp->dualfeasible = storedsolvals.dualfeasible;
2619  lp->dualchecked = storedsolvals.dualchecked;
2620  lp->solisbasic = storedsolvals.solisbasic;
2621  lp->solved = storedsolvals.lpissolved;
2622 
2623  for (c = 0; c < lp->ncols; ++c)
2624  {
2625  SCIP_COL* col;
2626 
2627  col = lp->cols[c];
2628  assert( col != NULL );
2629  col->primsol = storedcolsolvals[c].primsol;
2630  col->redcost = storedcolsolvals[c].redcost;
2631  col->basisstatus = storedcolsolvals[c].basisstatus; /*lint !e641 !e732*/
2632  }
2633  for (r = 0; r < lp->nrows; ++r)
2634  {
2635  SCIP_ROW* row;
2636 
2637  row = lp->rows[r];
2638  assert( row != NULL );
2639 
2640  if ( lp->lpsolstat == SCIP_LPSOLSTAT_INFEASIBLE )
2641  row->dualfarkas = storedrowsolvals[r].dualsol;
2642  else
2643  {
2644  assert( lp->lpsolstat == SCIP_LPSOLSTAT_OBJLIMIT );
2645  row->dualsol = storedrowsolvals[r].dualsol;
2646  }
2647  row->activity = storedrowsolvals[r].activity;
2648  row->basisstatus = storedrowsolvals[r].basisstatus; /*lint !e641 !e732*/
2649  }
2650  }
2651  SCIPsetFreeBufferArray(set, &storedrowsolvals);
2652  SCIPsetFreeBufferArray(set, &storedcolsolvals);
2653 
2654  return SCIP_OKAY;
2655 }
SCIP_Bool solisbasic
Definition: struct_lp.h:372
SCIP_CLOCK * propanalyzetime
SCIP_Bool lpissolved
Definition: struct_lp.h:125
SCIP_Real sbup
Definition: struct_lp.h:154
SCIP_Longint ninflpconfliterals
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)
SCIP_Bool primalchecked
Definition: struct_lp.h:121
void SCIPaggrRowFree(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition: cuts.c:1763
SCIP_Bool SCIPsetIsInfinity(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6281
SCIP_Real SCIPconflictGetVarUb(SCIP_CONFLICT *conflict, SCIP_VAR *var)
#define NULL
Definition: def.h:267
SCIP_Longint ninflpreconvconss
SCIP_Longint SCIPconflictGetNPseudoReconvergenceLiterals(SCIP_CONFLICT *conflict)
SCIP_Bool SCIPsetIsLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6339
internal methods for storing primal CIP solutions
SCIP_Real SCIPaggrRowGetMinActivity(SCIP_SET *set, SCIP_PROB *transprob, SCIP_AGGRROW *aggrrow, SCIP_Real *curvarlbs, SCIP_Real *curvarubs, SCIP_Bool *infdelta)
SCIP_RETCODE SCIPconflictCreate(SCIP_CONFLICT **conflict, BMS_BLKMEM *blkmem, SCIP_SET *set)
SCIP_Bool SCIPlpDiving(SCIP_LP *lp)
Definition: lp.c:17847
int nubchginfos
Definition: struct_var.h:269
#define BMSfreeMemoryArrayNull(ptr)
Definition: memory.h:148
SCIP_Longint ndualproofsinfsuccess
public methods for branch and bound tree
internal methods for branch and bound tree
SCIP_Longint SCIPconflictGetNBoundexceedingLPConflictConss(SCIP_CONFLICT *conflict)
SCIP_Real conflictlb
Definition: struct_var.h:219
SCIP_RETCODE SCIPaggrRowAddRow(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_ROW *row, SCIP_Real weight, int sidetype)
Definition: cuts.c:1867
SCIP_Longint SCIPconflictGetNBoundexceedingLPSuccess(SCIP_CONFLICT *conflict)
SCIP_Bool primalfeasible
Definition: struct_lp.h:368
SCIP_Longint dualproofsinfnnonzeros
SCIP_Longint SCIPconflictGetNPropReconvergenceLiterals(SCIP_CONFLICT *conflict)
public methods for memory management
SCIP_Longint nsbcalls
SCIP_RETCODE SCIPlpiGetDualfarkas(SCIP_LPI *lpi, SCIP_Real *dualfarkas)
Definition: lpi_clp.cpp:2857
int nlpicols
Definition: struct_lp.h:317
SCIP_Longint SCIPconflictGetNStrongbranchConflictLiterals(SCIP_CONFLICT *conflict)
SCIP_Bool SCIPsetIsFeasEQ(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6679
SCIP_RETCODE SCIPlpiStartStrongbranch(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:2006
SCIP_RETCODE SCIPlpiGetSol(SCIP_LPI *lpi, SCIP_Real *objval, SCIP_Real *primsol, SCIP_Real *dualsol, SCIP_Real *activity, SCIP_Real *redcost)
Definition: lpi_clp.cpp:2788
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18079
SCIP_CLOCK * conflictlptime
Definition: struct_stat.h:171
SCIP_RETCODE SCIPlpiSetIntpar(SCIP_LPI *lpi, SCIP_LPPARAM type, int ival)
Definition: lpi_clp.cpp:3692
public methods for conflict handler plugins and conflict analysis
internal methods for clocks and timing issues
SCIP_Longint SCIPconflictGetNBoundexceedingLPReconvergenceLiterals(SCIP_CONFLICT *conflict)
int lpdepth
Definition: struct_lp.h:241
SCIP_Longint SCIPconflictGetNPropConflictConss(SCIP_CONFLICT *conflict)
SCIP_Longint nappliedlocliterals
SCIP_Longint SCIPconflictGetNPropReconvergenceConss(SCIP_CONFLICT *conflict)
SCIP_CLOCK * inflpanalyzetime
SCIP_RETCODE SCIPlpiGetBase(SCIP_LPI *lpi, int *cstat, int *rstat)
Definition: lpi_clp.cpp:2967
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18135
SCIP_Real SCIPconflictGetStrongbranchTime(SCIP_CONFLICT *conflict)
static SCIP_RETCODE addRowToAggrRow(SCIP_SET *set, SCIP_ROW *row, SCIP_Real weight, SCIP_AGGRROW *aggrrow)
SCIP_Longint nappliedglbliterals
SCIP_Longint SCIPconflictGetNPseudoConflictConss(SCIP_CONFLICT *conflict)
SCIP_RETCODE SCIPconflictInitProofset(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem)
void SCIPsortIntIntInt(int *intarray1, int *intarray2, int *intarray3, int len)
SCIP_Longint npseudoreconvliterals
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17351
#define NUMSTOP
interface methods for specific LP solvers
SCIP_Longint npropconfliterals
SCIP_Real SCIPsetInfinity(SCIP_SET *set)
Definition: set.c:6146
SCIP_RETCODE SCIPlpiGetIterations(SCIP_LPI *lpi, int *iterations)
Definition: lpi_clp.cpp:2921
SCIP_RETCODE SCIPrunBoundHeuristic(SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *origprob, SCIP_PROB *transprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_Real *proofcoefs, SCIP_Real *prooflhs, SCIP_Real *proofactivity, SCIP_Real *curvarlbs, SCIP_Real *curvarubs, int *lbchginfoposs, int *ubchginfoposs, int *iterations, SCIP_Bool marklpunsolved, SCIP_Bool *dualproofsuccess, SCIP_Bool *valid)
int SCIPprobGetNVars(SCIP_PROB *prob)
Definition: prob.c:2393
SCIP_COL ** cols
Definition: struct_lp.h:301
int nlpirows
Definition: struct_lp.h:320
SCIP_Longint nappliedglbconss
SCIP_Real SCIPvarGetLbLP(SCIP_VAR *var, SCIP_SET *set)
Definition: var.c:12933
datastructures for conflict analysis
SCIP_Longint npseudoreconvconss
void SCIPclockStop(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:360
SCIP_Longint SCIPconflictGetNInfeasibleLPReconvergenceConss(SCIP_CONFLICT *conflict)
#define FALSE
Definition: def.h:94
methods for the aggregation rows
SCIP_Longint nlocchgbds
SCIP_Bool solved
Definition: struct_lp.h:367
void SCIPclockStart(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:290
SCIP_Longint SCIPconflictGetNBoundexceedingLPCalls(SCIP_CONFLICT *conflict)
SCIP_Bool dualchecked
Definition: struct_lp.h:371
void SCIPproofsetFree(SCIP_PROOFSET **proofset, BMS_BLKMEM *blkmem)
SCIP_Bool SCIPsetIsZero(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6393
#define TRUE
Definition: def.h:93
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
unsigned int basisstatus
Definition: struct_lp.h:250
void SCIPconflictsetFree(SCIP_CONFLICTSET **conflictset, BMS_BLKMEM *blkmem)
int nlbchginfos
Definition: struct_var.h:267
SCIP_RETCODE SCIPlpiSetRealpar(SCIP_LPI *lpi, SCIP_LPPARAM type, SCIP_Real dval)
Definition: lpi_clp.cpp:3833
SCIP_Real dualsol
Definition: struct_lp.h:107
SCIP_Real redcost
Definition: struct_lp.h:149
#define SCIPsetAllocBufferArray(set, ptr, num)
Definition: set.h:1748
int SCIPtreeGetCurrentDepth(SCIP_TREE *tree)
Definition: tree.c:8450
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17769
SCIP_Longint npropcalls
unsigned int sbdownvalid
Definition: struct_lp.h:188
SCIP_Real SCIPsetCutoffbounddelta(SCIP_SET *set)
Definition: set.c:6246
unsigned int basisstatus
Definition: struct_lp.h:179
SCIP_Longint nglbchgbds
public methods for problem variables
static SCIP_RETCODE conflictAnalyzeLP(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 diving, SCIP_Bool *dualproofsuccess, int *iterations, int *nconss, int *nliterals, int *nreconvconss, int *nreconvliterals, SCIP_Bool marklpunsolved)
SCIP_Longint npropsuccess
SCIP_Real dualfarkas
Definition: struct_lp.h:215
#define EPSGE(x, y, eps)
Definition: def.h:202
int SCIPaggrRowGetNNz(SCIP_AGGRROW *aggrrow)
Definition: cuts.c:2559
SCIP_RETCODE SCIPconflictFree(SCIP_CONFLICT **conflict, BMS_BLKMEM *blkmem)
SCIP_Real SCIPaggrRowGetRhs(SCIP_AGGRROW *aggrrow)
Definition: cuts.c:2589
void SCIPpqueueFree(SCIP_PQUEUE **pqueue)
Definition: misc.c:1322
SCIP_ROW ** SCIPlpGetRows(SCIP_LP *lp)
Definition: lp.c:17612
SCIP_Real SCIPlpGetPseudoObjval(SCIP_LP *lp, SCIP_SET *set, SCIP_PROB *prob)
Definition: lp.c:13302
SCIP_Longint SCIPconflictGetNAppliedLocalLiterals(SCIP_CONFLICT *conflict)
SCIP_Longint SCIPconflictGetNInfeasibleLPReconvergenceLiterals(SCIP_CONFLICT *conflict)
methods for creating output for visualization tools (VBC, BAK)
void SCIPclockEnableOrDisable(SCIP_CLOCK *clck, SCIP_Bool enable)
Definition: clock.c:260
#define QUAD_ASSIGN(a, constant)
Definition: dbldblarith.h:51
int SCIPconflictGetNConflicts(SCIP_CONFLICT *conflict)
#define SCIPsetFreeBufferArray(set, ptr)
Definition: set.h:1755
unsigned int basisstatus
Definition: struct_lp.h:109
#define BMSfreeMemory(ptr)
Definition: memory.h:145
SCIP_Longint SCIPconflictGetNPseudoReconvergenceConss(SCIP_CONFLICT *conflict)
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)
public methods for SCIP variables
SCIP_Longint SCIPconflictGetNPropCalls(SCIP_CONFLICT *conflict)
SCIP_RETCODE SCIPundoBdchgsProof(SCIP_SET *set, SCIP_PROB *prob, int currentdepth, SCIP_Real *proofcoefs, SCIP_Real prooflhs, SCIP_Real *proofact, SCIP_Real *curvarlbs, SCIP_Real *curvarubs, int *lbchginfoposs, int *ubchginfoposs, SCIP_LPBDCHGS *oldlpbdchgs, SCIP_LPBDCHGS *relaxedlpbdchgs, SCIP_Bool *resolve, SCIP_LPI *lpi)
SCIP_Longint SCIPconflictGetNDualproofsBndGlobal(SCIP_CONFLICT *conflict)
SCIP_Longint nappliedlocconss
SCIP_LPSOLSTAT SCIPlpGetSolstat(SCIP_LP *lp)
Definition: lp.c:13103
int conflictlbcount
Definition: struct_var.h:270
internal methods for LP management
SCIP_Longint npseudosuccess
Definition: heur_padm.c:134
SCIP_Real SCIPconflictGetVarLb(SCIP_CONFLICT *conflict, SCIP_VAR *var)
#define QUAD_TO_DBL(x)
Definition: dbldblarith.h:49
SCIP_Bool primalchecked
Definition: struct_lp.h:369
internal methods for branching and inference history
static SCIP_DECL_SORTPTRCOMP(conflictBdchginfoComp)
SCIP_Longint ninflpiterations
SCIP_RETCODE SCIPconflictAnalyzeRemainingBdchgs(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_TREE *tree, SCIP_Bool diving, int *lbchginfoposs, int *ubchginfoposs, int *nconss, int *nliterals, int *nreconvconss, int *nreconvliterals)
SCIP_Bool dualfeasible
Definition: struct_lp.h:122
int SCIPlpGetNCols(SCIP_LP *lp)
Definition: lp.c:17575
SCIP_Real SCIPvarGetUbLP(SCIP_VAR *var, SCIP_SET *set)
Definition: var.c:13003
SCIP_Bool SCIPsetIsGE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6375
internal methods for propagators
SCIP_Longint npropreconvliterals
SCIP_RETCODE SCIPaggrRowAddObjectiveFunction(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Real rhs, SCIP_Real scale)
Definition: cuts.c:2012
int SCIPtreeGetFocusDepth(SCIP_TREE *tree)
Definition: tree.c:8375
SCIP_Longint ndualproofsinflocal
SCIP_Longint npropconfconss
SCIP_Longint nboundlpcalls
SCIP_Real * vals
Definition: struct_lp.h:229
SCIP_Longint SCIPconflictGetNPropConflictLiterals(SCIP_CONFLICT *conflict)
SCIP_Real conflictrelaxedub
Definition: struct_var.h:222
SCIP_RETCODE SCIPlpiSolveDual(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:1880
SCIP_Bool SCIPlpiIsStable(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:2647
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18089
SCIP_Bool SCIPsetIsLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6321
SCIP_CLOCK * pseudoanalyzetime
public methods for handling parameter settings
public methods for managing constraints
SCIP_Real SCIPconflictGetPseudoTime(SCIP_CONFLICT *conflict)
int lpiitlim
Definition: struct_lp.h:345
SCIP_Real lb
Definition: struct_lp.h:138
SCIP_Real dualsol
Definition: struct_lp.h:213
SCIP_Real conflictrelaxedlb
Definition: struct_var.h:221
SCIP_Longint SCIPconflictGetNStrongbranchReconvergenceConss(SCIP_CONFLICT *conflict)
SCIP_RETCODE SCIPconflictAnalyzeDualProof(SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_PROB *origprob, SCIP_PROB *transprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_AGGRROW *proofrow, int validdepth, SCIP_Real *curvarlbs, SCIP_Real *curvarubs, SCIP_Bool initialproof, SCIP_Bool *globalinfeasible, SCIP_Bool *success)
SCIP_CLOCK * boundlpanalyzetime
SCIP_Longint SCIPconflictGetNBoundexceedingLPReconvergenceConss(SCIP_CONFLICT *conflict)
SCIP_Longint SCIPconflictGetNPseudoConflictLiterals(SCIP_CONFLICT *conflict)
SCIP_Real sbdown
Definition: struct_lp.h:153
SCIP_Longint ninflpreconvliterals
internal methods for storing and manipulating the main problem
#define QUAD_EPSILON
Definition: dbldblarith.h:42
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
SCIP_Bool SCIPbdchgidxIsEarlierNonNull(SCIP_BDCHGIDX *bdchgidx1, SCIP_BDCHGIDX *bdchgidx2)
Definition: var.c:18621
SCIP_Bool dualchecked
Definition: struct_lp.h:123
SCIP_COL ** cols
Definition: struct_lp.h:227
static SCIP_RETCODE conflictAnalyzeInfeasibleLP(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)
SCIP_Longint ndualproofsbndglobal
SCIP_Longint nconflictlpiterations
Definition: struct_stat.h:79
static SCIP_RETCODE addLocalRows(SCIP_SET *set, SCIP_PROB *transprob, SCIP_LP *lp, SCIP_AGGRROW *proofrow, SCIP_ROW **rows, SCIP_Real *dualsols, int *localrowinds, int *localrowdepth, int nlocalrows, SCIP_Real *proofact, int *validdepth, SCIP_Real *curvarlbs, SCIP_Real *curvarubs, SCIP_Bool *valid)
static SCIP_RETCODE conflictAnalyzeBoundexceedingLP(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)
SCIP_ROW ** lpirows
Definition: struct_lp.h:298
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:137
unsigned int sbupvalid
Definition: struct_lp.h:190
SCIP_Real SCIPconflictGetPropTime(SCIP_CONFLICT *conflict)
SCIP_Longint ndualproofsbndlocal
SCIP_Longint SCIPconflictGetNInfeasibleLPConflictLiterals(SCIP_CONFLICT *conflict)
SCIP_Longint SCIPconflictGetNInfeasibleLPSuccess(SCIP_CONFLICT *conflict)
#define QUAD(x)
Definition: dbldblarith.h:47
SCIP_Real lhs
Definition: struct_lp.h:204
SCIP_Bool SCIPlpiIsPrimalInfeasible(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:2502
SCIP_Longint npropreconvconss
SCIP_PROOFSET * proofset
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17420
SCIP_Real SCIPclockGetTime(SCIP_CLOCK *clck)
Definition: clock.c:438
SCIP_Real SCIPsetFeasCeil(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6857
SCIP_Longint SCIPconflictGetNDualproofsBndSuccess(SCIP_CONFLICT *conflict)
SCIP_Real cutoffbound
Definition: struct_lp.h:284
int * SCIPaggrRowGetInds(SCIP_AGGRROW *aggrrow)
Definition: cuts.c:2549
SCIP_RETCODE SCIPgetFarkasProof(SCIP_SET *set, SCIP_PROB *prob, SCIP_LP *lp, SCIP_LPI *lpi, SCIP_TREE *tree, SCIP_AGGRROW *farkasrow, SCIP_Real *farkasact, int *validdepth, SCIP_Real *curvarlbs, SCIP_Real *curvarubs, SCIP_Bool *valid)
data structures for branch and bound tree
#define REALABS(x)
Definition: def.h:197
SCIP_Longint ninflpcalls
SCIP_Longint nconflictlps
Definition: struct_stat.h:213
SCIP_Bool SCIPprobIsObjIntegral(SCIP_PROB *prob)
Definition: prob.c:2338
void SCIPaggrRowRemoveZeros(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Bool useglbbounds, SCIP_Bool *valid)
Definition: cuts.c:2479
internal methods for global SCIP settings
internal methods for storing conflicts
#define SCIP_CALL(x)
Definition: def.h:380
SCIP_Real activity
Definition: struct_lp.h:108
SCIP_Longint SCIPconflictGetNAppliedGlobalLiterals(SCIP_CONFLICT *conflict)
int SCIPlpGetNRows(SCIP_LP *lp)
Definition: lp.c:17622
SCIP_Longint SCIPconflictGetNInfeasibleLPIterations(SCIP_CONFLICT *conflict)
SCIP_Bool SCIPbdchginfoIsRedundant(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18809
SCIP_Bool SCIPsetIsEQ(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6303
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)
SCIP_LPI * SCIPlpGetLPI(SCIP_LP *lp)
Definition: lp.c:17774
SCIP_LPI * lpi
Definition: struct_lp.h:296
#define SCIPquadprecProdDD(r, a, b)
Definition: dbldblarith.h:58
SCIP_BDCHGIDX * SCIPbdchginfoGetIdx(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18731
SCIP_CLOCK * sbanalyzetime
SCIP_Longint dualproofsbndnnonzeros
SCIP_Bool SCIPsetIsFeasLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6723
public methods for constraint handler plugins and constraints
SCIP_RETCODE SCIPclockCreate(SCIP_CLOCK **clck, SCIP_CLOCKTYPE clocktype)
Definition: clock.c:170
methods commonly used for presolving
SCIP_Longint nboundlpsuccess
SCIP_Bool SCIPlpiWasSolved(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:2386
SCIP_CONFLICTSET * conflictset
SCIP_Longint nboundlpreconvconss
internal methods for problem variables
SCIP_RETCODE SCIPlpiGetObjval(SCIP_LPI *lpi, SCIP_Real *objval)
Definition: lpi_clp.cpp:2766
public data structures and miscellaneous methods
static SCIP_Bool checkDualFeasibility(SCIP_SET *set, SCIP_ROW *row, SCIP_Real weight, SCIP_Bool *zerocontribution)
int SCIPtreeGetEffectiveRootDepth(SCIP_TREE *tree)
Definition: tree.c:8489
#define SCIP_Bool
Definition: def.h:91
SCIP_Longint SCIPconflictGetNDualproofsInfSuccess(SCIP_CONFLICT *conflict)
SCIP_Real redcost
Definition: struct_lp.h:96
SCIP_Longint SCIPconflictGetNDualproofsInfGlobal(SCIP_CONFLICT *conflict)
SCIP_Longint SCIPconflictGetNStrongbranchReconvergenceLiterals(SCIP_CONFLICT *conflict)
SCIP_Real SCIPlpiInfinity(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:3919
SCIP_Bool SCIPlpiIsDualFeasible(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:2609
void SCIPclockFree(SCIP_CLOCK **clck)
Definition: clock.c:185
SCIP_Bool SCIPlpDivingObjChanged(SCIP_LP *lp)
Definition: lp.c:17857
SCIP_Longint ndualproofsinfglobal
unsigned int basisstatus
Definition: struct_lp.h:97
SCIP_Longint SCIPconflictGetNGlobalChgBds(SCIP_CONFLICT *conflict)
SCIP_Longint SCIPconflictGetNStrongbranchSuccess(SCIP_CONFLICT *conflict)
public methods for LP management
SCIP_CONFTYPE conflicttype
#define SCIPsetDebugMsg
Definition: set.h:1784
SCIP_Real conflictub
Definition: struct_var.h:220
SCIP_Bool SCIPprobAllColsInLP(SCIP_PROB *prob, SCIP_SET *set, SCIP_LP *lp)
Definition: prob.c:2350
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17927
#define EPSLE(x, y, eps)
Definition: def.h:200
SCIP_Longint SCIPconflictGetNAppliedLocalConss(SCIP_CONFLICT *conflict)
SCIP_RETCODE SCIPlpiSetBase(SCIP_LPI *lpi, const int *cstat, const int *rstat)
Definition: lpi_clp.cpp:3067
int SCIPproofsetGetNVars(SCIP_PROOFSET *proofset)
SCIP_Real SCIPconflictGetBoundexceedingLPTime(SCIP_CONFLICT *conflict)
SCIP_Longint SCIPconflictGetNInfeasibleLPConflictConss(SCIP_CONFLICT *conflict)
SCIP_Longint SCIPconflictGetNAppliedConss(SCIP_CONFLICT *conflict)
Constraint handler for linear constraints in their most general form, .
datastructures for problem statistics
SCIP_Longint nboundlpreconvliterals
SCIP_Real ub
Definition: struct_lp.h:139
SCIP_Longint nsbconfconss
SCIP_Longint nsbconfliterals
SCIP_Bool SCIPlpiIsOptimal(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:2623
SCIP_ROW ** rows
Definition: struct_lp.h:303
SCIP_Longint nboundlpiterations
SCIP_Longint SCIPconflictGetNAppliedGlobalConss(SCIP_CONFLICT *conflict)
#define SCIPquadprecSumQQ(r, a, b)
Definition: dbldblarith.h:67
int conflictubcount
Definition: struct_var.h:271
SCIP_Longint SCIPconflictGetNInfeasibleLPCalls(SCIP_CONFLICT *conflict)
SCIP_RETCODE SCIPlpiChgBounds(SCIP_LPI *lpi, int ncols, const int *ind, const SCIP_Real *lb, const SCIP_Real *ub)
Definition: lpi_clp.cpp:1084
SCIP_Longint npseudoconfliterals
SCIP_Longint ninflpconfconss
SCIP_Real rhs
Definition: struct_lp.h:205
SCIP_Real constant
Definition: struct_lp.h:203
SCIP_RETCODE SCIPpqueueCreate(SCIP_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos)))
Definition: misc.c:1295
SCIP_Longint SCIPconflictGetNDualproofsInfLocal(SCIP_CONFLICT *conflict)
datastructures for storing and manipulating the main problem
SCIP_Real * r
Definition: circlepacking.c:59
methods for sorting joint arrays of various types
SCIP_Longint SCIPconflictGetNLocalChgBds(SCIP_CONFLICT *conflict)
SCIP_Real SCIPsetFeasFloor(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6846
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
SCIP_RETCODE SCIPconflictsetCreate(SCIP_CONFLICTSET **conflictset, BMS_BLKMEM *blkmem)
SCIP_RETCODE SCIPconflictFlushProofset(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_Longint SCIPconflictGetNStrongbranchConflictConss(SCIP_CONFLICT *conflict)
SCIP_LPSOLSTAT lpsolstat
Definition: struct_lp.h:118
SCIP_Longint SCIPconflictGetNDualproofsBndNonzeros(SCIP_CONFLICT *conflict)
SCIP_RETCODE SCIPlpiEndStrongbranch(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:2018
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:17042
SCIP_Longint SCIPconflictGetNPropSuccess(SCIP_CONFLICT *conflict)
public methods for solutions
internal methods for conflict analysis
void SCIPconflictEnableOrDisableClocks(SCIP_CONFLICT *conflict, SCIP_Bool enable)
SCIP_Longint nsbsuccess
int lpipos
Definition: struct_lp.h:173
static SCIP_RETCODE sortLocalRows(SCIP_SET *set, SCIP_AGGRROW *aggrrow, SCIP_ROW **rows, int *rowinds, int *rowdepth, int nrows)
public methods for conflict analysis handlers
SCIP_Longint SCIPconflictGetNBoundexceedingLPIterations(SCIP_CONFLICT *conflict)
SCIP_Longint nsbreconvliterals
SCIP_Longint nboundlpconfliterals
SCIP_Bool flushed
Definition: struct_lp.h:366
SCIP_Longint SCIPconflictGetNDualproofsBndLocal(SCIP_CONFLICT *conflict)
SCIP_Bool SCIPlpiHasDualRay(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:2556
int nrows
Definition: struct_lp.h:334
public methods for message output
data structures for LP management
SCIP_Bool SCIPsetIsGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6357
datastructures for problem variables
SCIP_Bool SCIPlpiIsObjlimExc(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:2690
SCIP_Real lpobjval
Definition: struct_lp.h:271
SCIP_Real primsol
Definition: struct_lp.h:95
#define SCIP_Real
Definition: def.h:173
SCIP_Bool solisbasic
Definition: struct_lp.h:124
SCIP_VAR ** vars
Definition: struct_prob.h:64
SCIP_Longint npseudocalls
SCIP_Real lpiobjlim
Definition: struct_lp.h:286
SCIP_VAR ** SCIPprobGetVars(SCIP_PROB *prob)
Definition: prob.c:2438
#define BMSallocMemory(ptr)
Definition: memory.h:118
SCIP_CLOCK * dIBclock
internal methods for constraints and constraint handlers
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition: cuts.c:1731
SCIP_Real primsol
Definition: struct_lp.h:148
SCIP_Longint nsbiterations
SCIP_Longint nboundlpconfconss
#define SCIP_Longint
Definition: def.h:158
SCIP_Bool SCIPsetIsDualfeasZero(SCIP_SET *set, SCIP_Real val)
Definition: set.c:7000
int SCIProwGetLPDepth(SCIP_ROW *row)
Definition: lp.c:17512
SCIP_Bool SCIPsetIsFeasGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6745
SCIP_Longint npseudoconfconss
SCIP_Bool dualfeasible
Definition: struct_lp.h:370
SCIP_Real SCIPconflictGetGlobalApplTime(SCIP_CONFLICT *conflict)
SCIP_Longint SCIPconflictGetNBoundexceedingLPConflictLiterals(SCIP_CONFLICT *conflict)
#define SOLSTOP
static INLINE SCIP_Real SCIPaggrRowGetProbvarValue(SCIP_AGGRROW *aggrrow, int probindex)
Definition: cuts.h:251
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18145
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)
SCIP_Longint SCIPconflictGetNStrongbranchIterations(SCIP_CONFLICT *conflict)
unsigned int usescutoffbound
SCIP_Longint SCIPconflictGetNAppliedLiterals(SCIP_CONFLICT *conflict)
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
SCIP_RETCODE SCIPgetDualProof(SCIP_SET *set, SCIP_PROB *transprob, SCIP_LP *lp, SCIP_LPI *lpi, SCIP_TREE *tree, SCIP_AGGRROW *farkasrow, SCIP_Real *farkasact, int *validdepth, SCIP_Real *curvarlbs, SCIP_Real *curvarubs, SCIP_Bool *valid)
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:437
void SCIPaggrRowClear(SCIP_AGGRROW *aggrrow)
Definition: cuts.c:2141
SCIP_Longint SCIPconflictGetNPseudoSuccess(SCIP_CONFLICT *conflict)
SCIP_Bool primalfeasible
Definition: struct_lp.h:120
SCIP_Longint ndualproofsbndsuccess
#define SCIP_ALLOC(x)
Definition: def.h:391
SCIP_LPSOLSTAT lpsolstat
Definition: struct_lp.h:353
int ncols
Definition: struct_lp.h:328
datastructures for global SCIP settings
SCIP_Longint SCIPconflictGetNStrongbranchCalls(SCIP_CONFLICT *conflict)
SCIP_Real lpobjval
Definition: struct_lp.h:119
SCIP_Longint nsbreconvconss
unsigned int local
Definition: struct_lp.h:259
SCIP_Longint SCIPconflictGetNDualproofsInfNonzeros(SCIP_CONFLICT *conflict)
SCIP_Real activity
Definition: struct_lp.h:214
SCIP_RETCODE SCIPlpiGetRealpar(SCIP_LPI *lpi, SCIP_LPPARAM type, SCIP_Real *dval)
Definition: lpi_clp.cpp:3796
int len
Definition: struct_lp.h:235
public methods for propagators
SCIP_Real SCIPconflictGetInfeasibleLPTime(SCIP_CONFLICT *conflict)
SCIP_Longint ninflpsuccess
SCIP_Longint SCIPconflictGetNPseudoCalls(SCIP_CONFLICT *conflict)