Scippy

SCIP

Solving Constraint Integer Programs

conflict_graphanalysis.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_graphanalysis.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 * This file implements a conflict analysis method like the one used in modern
36 * SAT solvers like zchaff. The algorithm works as follows:
37 *
38 * Given is a set of bound changes that are not allowed being applied simultaneously, because they
39 * render the current node infeasible (e.g. because a single constraint is infeasible in the these
40 * bounds, or because the LP relaxation is infeasible). The goal is to deduce a clause on variables
41 * -- a conflict clause -- representing the "reason" for this conflict, i.e., the branching decisions
42 * or the deductions (applied e.g. in domain propagation) that lead to the conflict. This clause can
43 * then be added to the constraint set to help cutting off similar parts of the branch and bound
44 * tree, that would lead to the same conflict. A conflict clause can also be generated, if the
45 * conflict was detected by a locally valid constraint. In this case, the resulting conflict clause
46 * is also locally valid in the same depth as the conflict detecting constraint. If all involved
47 * variables are binary, a linear (set covering) constraint can be generated, otherwise a bound
48 * disjunction constraint is generated. Details are given in
49 *
50 * Tobias Achterberg, Conflict Analysis in Mixed Integer Programming@n
51 * Discrete Optimization, 4, 4-20 (2007)
52 *
53 * See also @ref CONF. Here is an outline of the algorithm:
54 *
55 * -# Put all the given bound changes to a priority queue, which is ordered,
56 * such that the bound change that was applied last due to branching or deduction
57 * is at the top of the queue. The variables in the queue are always active
58 * problem variables. Because binary variables are preferred over general integer
59 * variables, integer variables are put on the priority queue prior to the binary
60 * variables. Create an empty conflict set.
61 * -# Remove the top bound change b from the priority queue.
62 * -# Perform the following case distinction:
63 * -# If the remaining queue is non-empty, and bound change b' (the one that is now
64 * on the top of the queue) was applied at the same depth level as b, and if
65 * b was a deduction with known inference reason, and if the inference constraint's
66 * valid depth is smaller or equal to the conflict detecting constraint's valid
67 * depth:
68 * - Resolve bound change b by asking the constraint that inferred the
69 * bound change to put all the bound changes on the priority queue, that
70 * lead to the deduction of b.
71 * Note that these bound changes have at most the same inference depth
72 * level as b, and were deduced earlier than b.
73 * -# Otherwise, the bound change b was a branching decision or a deduction with
74 * missing inference reason, or the inference constraint's validity is more local
75 * than the one of the conflict detecting constraint.
76 * - If a the bound changed corresponds to a binary variable, add it or its
77 * negation to the conflict set, depending on which of them is currently fixed to
78 * FALSE (i.e., the conflict set consists of literals that cannot be FALSE
79 * altogether at the same time).
80 * - Otherwise put the bound change into the conflict set.
81 * Note that if the bound change was a branching, all deduced bound changes
82 * remaining in the priority queue have smaller inference depth level than b,
83 * since deductions are always applied after the branching decisions. However,
84 * there is the possibility, that b was a deduction, where the inference
85 * reason was not given or the inference constraint was too local.
86 * With this lack of information, we must treat the deduced bound change like
87 * a branching, and there may exist other deduced bound changes of the same
88 * inference depth level in the priority queue.
89 * -# If priority queue is non-empty, goto step 2.
90 * -# The conflict set represents the conflict clause saying that at least one
91 * of the conflict variables must take a different value. The conflict set is then passed
92 * to the conflict handlers, that may create a corresponding constraint (e.g. a logicor
93 * constraint or bound disjunction constraint) out of these conflict variables and
94 * add it to the problem.
95 *
96 * If all deduced bound changes come with (global) inference information, depending on
97 * the conflict analyzing strategy, the resulting conflict set has the following property:
98 * - 1-FirstUIP: In the depth level where the conflict was found, at most one variable
99 * assigned at that level is member of the conflict set. This conflict variable is the
100 * first unique implication point of its depth level (FUIP).
101 * - All-FirstUIP: For each depth level, at most one variable assigned at that level is
102 * member of the conflict set. This conflict variable is the first unique implication
103 * point of its depth level (FUIP).
104 *
105 * The user has to do the following to get the conflict analysis running in its
106 * current implementation:
107 * - A constraint handler or propagator supporting the conflict analysis must implement
108 * the CONSRESPROP/PROPRESPROP call, that processes a bound change inference b and puts all
109 * the reason bounds leading to the application of b with calls to
110 * SCIPaddConflictBound() on the conflict queue (algorithm step 3.(a)).
111 * - If the current bounds lead to a deduction of a bound change (e.g. in domain
112 * propagation), a constraint handler should call SCIPinferVarLbCons() or
113 * SCIPinferVarUbCons(), thus providing the constraint that inferred the bound change.
114 * A propagator should call SCIPinferVarLbProp() or SCIPinferVarUbProp() instead,
115 * thus providing a pointer to itself.
116 * - If (in the current bounds) an infeasibility is detected, the constraint handler or
117 * propagator should
118 * 1. call SCIPinitConflictAnalysis() to initialize the conflict queue,
119 * 2. call SCIPaddConflictBound() for each bound that lead to the conflict,
120 * 3. call SCIPanalyzeConflictCons() or SCIPanalyzeConflict() to analyze the conflict
121 * and add an appropriate conflict constraint.
122 */
123
124/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
125
126#include "lpi/lpi.h"
129#include "scip/clock.h"
130#include "scip/conflict.h"
131#include "scip/cons.h"
132#include "scip/cons_linear.h"
133#include "scip/cuts.h"
134#include "scip/history.h"
135#include "scip/lp.h"
136#include "scip/presolve.h"
137#include "scip/prob.h"
138#include "scip/prop.h"
139#include "scip/pub_conflict.h"
140#include "scip/pub_cons.h"
141#include "scip/pub_lp.h"
142#include "scip/pub_message.h"
143#include "scip/pub_misc.h"
144#include "scip/pub_misc_sort.h"
145#include "scip/pub_paramset.h"
146#include "scip/pub_prop.h"
147#include "scip/pub_tree.h"
148#include "scip/pub_var.h"
149#include "scip/scip_conflict.h"
150#include "scip/scip_cons.h"
151#include "scip/scip_mem.h"
152#include "scip/scip_sol.h"
153#include "scip/scip_var.h"
154#include "scip/set.h"
155#include "scip/sol.h"
156#include "scip/struct_conflict.h"
157#include "scip/struct_lp.h"
158#include "scip/struct_prob.h"
159#include "scip/struct_set.h"
160#include "scip/struct_stat.h"
161#include "scip/struct_tree.h"
162#include "scip/struct_var.h"
163#include "scip/tree.h"
164#include "scip/var.h"
165#include "scip/visual.h"
166#include <string.h>
167#if defined(_WIN32) || defined(_WIN64)
168#else
169#include <strings.h> /*lint --e{766}*/
170#endif
171
172/* #define SCIP_CONFGRAPH */
173/* #define SCIP_CONFGRAPH_DOT */
174
175
176#if defined(SCIP_CONFGRAPH) || defined(SCIP_CONFGRAPH_DOT)
177/*
178 * Output of Conflict Graph
179 */
180
181#include <stdio.h>
182#include "scip/scip_message.h"
183
184static FILE* confgraphfile = NULL; /**< output file for current conflict graph */
185static SCIP_BDCHGINFO* confgraphcurrentbdchginfo = NULL; /**< currently resolved bound change */
186static int confgraphnconflictsets = 0; /**< number of conflict sets marked in the graph */
187
188/** writes a node section to the conflict graph file */
189static
190void confgraphWriteNode(
191 void* idptr, /**< id of the node */
192 const char* label, /**< label of the node */
193 const char* nodetype, /**< type of the node */
194 const char* fillcolor, /**< color of the node's interior */
195 const char* bordercolor /**< color of the node's border */
196 )
197{
198 assert(confgraphfile != NULL);
199
200#ifdef SCIP_CONFGRAPH_DOT
201 SCIPdotWriteNode(confgraphfile, (int)(size_t) idptr, label, nodetype, fillcolor, bordercolor); /*lint !e571*/
202
203#else
204 SCIPgmlWriteNode(confgraphfile, (unsigned int)(size_t)idptr, label, nodetype, fillcolor, bordercolor); /*lint !e571*/
205
206#endif
207}
208
209/** writes an edge section to the conflict graph file */
210static
211void confgraphWriteEdge(
212 void* source, /**< source node of the edge */
213 void* target, /**< target node of the edge */
214 const char* color /**< color of the edge */
215 )
216{
217 assert(confgraphfile != NULL);
218
219#ifdef SCIP_CONFGRAPH_DOT
220 SCIPdotWriteArc(confgraphfile, (int)(size_t)source, (int)(size_t)target, color); /*lint !e571*/
221
222#else
223#ifndef SCIP_CONFGRAPH_EDGE
224 SCIPgmlWriteArc(confgraphfile, (unsigned int)(size_t)source, (unsigned int)(size_t)target, NULL, color); /*lint !e571*/
225
226#else
227 SCIPgmlWriteEdge(confgraphfile, (unsigned int)(size_t)source, (unsigned int)(size_t)target, NULL, color); /*lint !e571*/
228#endif
229#endif
230}
231
232/** creates a file to output the current conflict graph into; adds the conflict vertex to the graph */
233static
234SCIP_RETCODE confgraphCreate(
235 SCIP_SET* set, /**< global SCIP settings */
236 SCIP_CONFLICT* conflict /**< conflict analysis data */
237 )
238{
239 char fname[SCIP_MAXSTRLEN];
240
241 assert(conflict != NULL);
242 assert(confgraphfile == NULL);
243
244#ifdef SCIP_CONFGRAPH_DOT
245 (void) SCIPsnprintf(fname, SCIP_MAXSTRLEN, "conf%p%d.dot", conflict, conflict->count);
246#else
247 (void) SCIPsnprintf(fname, SCIP_MAXSTRLEN, "conf%p%d.gml", conflict, conflict->count);
248#endif
249 SCIPinfoMessage(set->scip, NULL, "storing conflict graph in file <%s>\n", fname);
250
251 confgraphfile = fopen(fname, "w");
252
253 if( confgraphfile == NULL )
254 {
255 SCIPerrorMessage("cannot open graph file <%s>\n", fname);
256 SCIPABORT(); /*lint !e527*/
257 return SCIP_WRITEERROR;
258 }
259
260#ifdef SCIP_CONFGRAPH_DOT
261 SCIPdotWriteOpening(confgraphfile);
262#else
263 SCIPgmlWriteOpening(confgraphfile, TRUE);
264#endif
265 confgraphWriteNode(NULL, "conflict", "ellipse", "#ff0000", "#000000");
266
267 confgraphcurrentbdchginfo = NULL;
268
269 return SCIP_OKAY;
270}
271
272/** closes conflict graph file */
273static
274void confgraphFree(
275 void
276 )
277{
278 if( confgraphfile != NULL )
279 {
280#ifdef SCIP_CONFGRAPH_DOT
281 SCIPdotWriteClosing(confgraphfile);
282#else
283 SCIPgmlWriteClosing(confgraphfile);
284#endif
285 fclose(confgraphfile);
286
287 confgraphfile = NULL;
288 confgraphnconflictsets = 0;
289 }
290}
291
292/** adds a bound change node to the conflict graph and links it to the currently resolved bound change */
293static
294void confgraphAddBdchg(
295 SCIP_BDCHGINFO* bdchginfo /**< bound change to add to the conflict graph */
296 )
297{
298 const char* colors[] = {
299 "#8888ff", /* blue for constraint resolving */
300 "#ffff00", /* yellow for propagator resolving */
301 "#55ff55" /* green branching decision */
302 };
303 char label[SCIP_MAXSTRLEN];
304 char depth[SCIP_MAXSTRLEN];
305 int col;
306
307 switch( SCIPbdchginfoGetChgtype(bdchginfo) )
308 {
310 col = 2;
311 break;
313 col = 0;
314 break;
316 col = (SCIPbdchginfoGetInferProp(bdchginfo) == NULL ? 1 : 0);
317 break;
318 default:
319 SCIPerrorMessage("invalid bound change type\n");
320 col = 0;
321 SCIPABORT();
322 break;
323 }
324
325 if( SCIPbdchginfoGetDepth(bdchginfo) == INT_MAX )
326 (void) SCIPsnprintf(depth, SCIP_MAXSTRLEN, "dive");
327 else
328 (void) SCIPsnprintf(depth, SCIP_MAXSTRLEN, "%d", SCIPbdchginfoGetDepth(bdchginfo));
329 (void) SCIPsnprintf(label, SCIP_MAXSTRLEN, "%s %s %g\n[%s:%d]", SCIPvarGetName(SCIPbdchginfoGetVar(bdchginfo)),
330 SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
331 SCIPbdchginfoGetNewbound(bdchginfo), depth, SCIPbdchginfoGetPos(bdchginfo));
332 confgraphWriteNode(bdchginfo, label, "ellipse", colors[col], "#000000");
333 confgraphWriteEdge(bdchginfo, confgraphcurrentbdchginfo, "#000000");
334}
335
336/** links the already existing bound change node to the currently resolved bound change */
337static
338void confgraphLinkBdchg(
339 SCIP_BDCHGINFO* bdchginfo /**< bound change to add to the conflict graph */
340 )
341{
342 confgraphWriteEdge(bdchginfo, confgraphcurrentbdchginfo, "#000000");
343}
344
345/** marks the given bound change to be the currently resolved bound change */
346static
347void confgraphSetCurrentBdchg(
348 SCIP_BDCHGINFO* bdchginfo /**< bound change to add to the conflict graph */
349 )
350{
351 confgraphcurrentbdchginfo = bdchginfo;
352}
353
354/** marks given conflict set in the conflict graph */
355static
356void confgraphMarkConflictset(
357 SCIP_CONFLICTSET* conflictset /**< conflict set */
358 )
359{
360 char label[SCIP_MAXSTRLEN];
361 int i;
362
363 assert(conflictset != NULL);
364
365 confgraphnconflictsets++;
366 (void) SCIPsnprintf(label, SCIP_MAXSTRLEN, "conf %d (%d)", confgraphnconflictsets, conflictset->validdepth);
367 confgraphWriteNode((void*)(size_t)confgraphnconflictsets, label, "rectangle", "#ff00ff", "#000000"); /*lint !e571*/
368 for( i = 0; i < conflictset->nbdchginfos; ++i )
369 confgraphWriteEdge((void*)(size_t)confgraphnconflictsets, conflictset->bdchginfos[i], "#ff00ff"); /*lint !e571*/
370}
371
372#endif
373
374/** Conflict sets */
375
376/** resizes the arrays of the conflict set to be able to store at least num bound change entries */
377static
379 SCIP_CONFLICTSET* conflictset, /**< conflict set */
380 BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
381 SCIP_SET* set, /**< global SCIP settings */
382 int num /**< minimal number of slots in arrays */
383 )
384{
385 assert(conflictset != NULL);
386 assert(set != NULL);
387
388 if( num > conflictset->bdchginfossize )
389 {
390 int newsize;
391
392 newsize = SCIPsetCalcMemGrowSize(set, num);
393 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &conflictset->bdchginfos, conflictset->bdchginfossize, newsize) );
394 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &conflictset->relaxedbds, conflictset->bdchginfossize, newsize) );
395 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &conflictset->sortvals, conflictset->bdchginfossize, newsize) );
396 conflictset->bdchginfossize = newsize;
397 }
398 assert(num <= conflictset->bdchginfossize);
399
400 return SCIP_OKAY;
401}
402
403/** adds a bound change to a conflict set */
404static
406 SCIP_CONFLICTSET* conflictset, /**< conflict set */
407 BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
408 SCIP_SET* set, /**< global SCIP settings */
409 SCIP_BDCHGINFO* bdchginfo, /**< bound change to add to the conflict set */
410 SCIP_Real relaxedbd /**< relaxed bound */
411 )
412{
413 SCIP_BDCHGINFO** bdchginfos;
414 SCIP_Real* relaxedbds;
415 int* sortvals;
416 SCIP_VAR* var;
417 SCIP_BOUNDTYPE boundtype;
418 int idx;
419 int sortval;
420 int pos;
421
422 assert(conflictset != NULL);
423 assert(bdchginfo != NULL);
424
425 /* allocate memory for additional element */
426 SCIP_CALL( conflictsetEnsureBdchginfosMem(conflictset, blkmem, set, conflictset->nbdchginfos+1) );
427
428 /* insert the new bound change in the arrays sorted by increasing variable index and by bound type */
429 bdchginfos = conflictset->bdchginfos;
430 relaxedbds = conflictset->relaxedbds;
431 sortvals = conflictset->sortvals;
432 var = SCIPbdchginfoGetVar(bdchginfo);
433 boundtype = SCIPbdchginfoGetBoundtype(bdchginfo);
434 idx = SCIPvarGetIndex(var);
435 assert(idx < INT_MAX/2);
436 assert((int)boundtype == 0 || (int)boundtype == 1);
437 sortval = 2*idx + (int)boundtype; /* first sorting criteria: variable index, second criteria: boundtype */
438
439 /* insert new element into the sorted arrays; if an element exits with the same value insert the new element afterwards
440 *
441 * @todo check if it better (faster) to first search for the position O(log n) and compare the sort values and if
442 * they are equal just replace the element and if not run the insert method O(n)
443 */
444
445 SCIPsortedvecInsertIntPtrReal(sortvals, (void**)bdchginfos, relaxedbds, sortval, (void*)bdchginfo, relaxedbd, &conflictset->nbdchginfos, &pos);
446 assert(pos == conflictset->nbdchginfos - 1 || sortval < sortvals[pos+1]);
447
448 /* merge multiple bound changes */
449 if( pos > 0 && sortval == sortvals[pos-1] )
450 {
451 /* this is a multiple bound change */
452 if( SCIPbdchginfoIsTighter(bdchginfo, bdchginfos[pos-1]) )
453 {
454 /* remove the "old" bound change since the "new" one in tighter */
455 SCIPsortedvecDelPosIntPtrReal(sortvals, (void**)bdchginfos, relaxedbds, pos-1, &conflictset->nbdchginfos);
456 }
457 else if( SCIPbdchginfoIsTighter(bdchginfos[pos-1], bdchginfo) )
458 {
459 /* remove the "new" bound change since the "old" one is tighter */
460 SCIPsortedvecDelPosIntPtrReal(sortvals, (void**)bdchginfos, relaxedbds, pos, &conflictset->nbdchginfos);
461 }
462 else
463 {
464 /* both bound change are equivalent; hence, keep the worse relaxed bound and remove one of them */
465 relaxedbds[pos-1] = boundtype == SCIP_BOUNDTYPE_LOWER ? MAX(relaxedbds[pos-1], relaxedbd) : MIN(relaxedbds[pos-1], relaxedbd);
466 SCIPsortedvecDelPosIntPtrReal(sortvals, (void**)bdchginfos, relaxedbds, pos, &conflictset->nbdchginfos);
467 }
468 }
469
470 if( SCIPvarIsRelaxationOnly(var) )
471 conflictset->hasrelaxonlyvar = TRUE;
472
473 return SCIP_OKAY;
474}
475
476/** calculates the conflict and the repropagation depths of the conflict set */
477static
479 SCIP_CONFLICTSET* conflictset /**< conflict set */
480 )
481{
482 int maxdepth[2];
483 int i;
484
485 assert(conflictset != NULL);
486 assert(conflictset->validdepth <= conflictset->insertdepth);
487
488 /* get the depth of the last and last but one bound change */
489 maxdepth[0] = conflictset->validdepth;
490 maxdepth[1] = conflictset->validdepth;
491 for( i = 0; i < conflictset->nbdchginfos; ++i )
492 {
493 int depth;
494
495 depth = SCIPbdchginfoGetDepth(conflictset->bdchginfos[i]);
496 assert(depth >= 0);
497 if( depth > maxdepth[0] )
498 {
499 maxdepth[1] = maxdepth[0];
500 maxdepth[0] = depth;
501 }
502 else if( depth > maxdepth[1] )
503 maxdepth[1] = depth;
504 }
505 assert(maxdepth[0] >= maxdepth[1]);
506
507 conflictset->conflictdepth = maxdepth[0];
508 conflictset->repropdepth = maxdepth[1];
509}
510
511/** identifies the depth, at which the conflict set should be added:
512 * - if the branching rule operates on variables only, and if all branching variables up to a certain
513 * depth level are member of the conflict, the conflict constraint can only be violated in the subtree
514 * of the node at that depth, because in all other nodes, at least one of these branching variables
515 * violates its conflicting bound, such that the conflict constraint is feasible
516 * - if there is at least one branching variable in a node, we assume, that this branching was performed
517 * on variables, and that the siblings of this node are disjunct w.r.t. the branching variables' fixings
518 * - we have to add the conflict set at least in the valid depth of the initial conflict set,
519 * so we start searching at the first branching after this depth level, i.e. validdepth+1
520 */
521static
523 SCIP_CONFLICTSET* conflictset, /**< conflict set */
524 SCIP_SET* set, /**< global SCIP settings */
525 SCIP_TREE* tree /**< branch and bound tree */
526 )
527{
528 SCIP_Bool* branchingincluded;
529 int currentdepth;
530 int i;
531
532 assert(conflictset != NULL);
533 assert(set != NULL);
534 assert(tree != NULL);
535
536 /* the conflict set must not be inserted prior to its valid depth */
537 conflictset->insertdepth = conflictset->validdepth;
538 assert(conflictset->insertdepth >= 0);
539
540 currentdepth = SCIPtreeGetCurrentDepth(tree);
541 assert(currentdepth == tree->pathlen-1);
542
543 /* mark the levels for which a branching variable is included in the conflict set */
544 SCIP_CALL( SCIPsetAllocBufferArray(set, &branchingincluded, currentdepth+2) );
545 BMSclearMemoryArray(branchingincluded, currentdepth+2);
546 for( i = 0; i < conflictset->nbdchginfos; ++i )
547 {
548 int depth;
549
550 depth = SCIPbdchginfoGetDepth(conflictset->bdchginfos[i]);
551 depth = MIN(depth, currentdepth+1); /* put diving/probing/strong branching changes in this depth level */
552 branchingincluded[depth] = TRUE;
553 }
554
555 /* skip additional depth levels where branching on the conflict variables was applied */
556 while( conflictset->insertdepth < currentdepth && branchingincluded[conflictset->insertdepth+1] )
557 conflictset->insertdepth++;
558
559 /* free temporary memory */
560 SCIPsetFreeBufferArray(set, &branchingincluded);
561
562 assert(conflictset->validdepth <= conflictset->insertdepth && conflictset->insertdepth <= currentdepth);
563
564 return SCIP_OKAY;
565}
566
567/** checks whether the first conflict set is redundant to the second one */
568static
570 SCIP_CONFLICTSET* conflictset1, /**< first conflict conflict set */
571 SCIP_CONFLICTSET* conflictset2 /**< second conflict conflict set */
572 )
573{
574 int i1;
575 int i2;
576
577 assert(conflictset1 != NULL);
578 assert(conflictset2 != NULL);
579
580 /* if conflictset1 has smaller validdepth, it is definitely not redundant to conflictset2 */
581 if( conflictset1->validdepth < conflictset2->validdepth )
582 return FALSE;
583
584 /* check, if all bound changes in conflictset2 are also present at least as tight in conflictset1;
585 * we can stop immediately, if more bound changes are remaining in conflictset2 than in conflictset1
586 */
587 for( i1 = 0, i2 = 0; i2 < conflictset2->nbdchginfos && conflictset1->nbdchginfos - i1 >= conflictset2->nbdchginfos - i2;
588 ++i1, ++i2 )
589 {
590 int sortval;
591
592 assert(i2 == 0 || conflictset2->sortvals[i2-1] < conflictset2->sortvals[i2]);
593
594 sortval = conflictset2->sortvals[i2];
595 for( ; i1 < conflictset1->nbdchginfos && conflictset1->sortvals[i1] < sortval; ++i1 ) /*lint !e445*/
596 {
597 /* while scanning conflictset1, check consistency */
598 assert(i1 == 0 || conflictset1->sortvals[i1-1] < conflictset1->sortvals[i1]);
599 }
600 if( i1 >= conflictset1->nbdchginfos || conflictset1->sortvals[i1] > sortval
601 || SCIPbdchginfoIsTighter(conflictset2->bdchginfos[i2], conflictset1->bdchginfos[i1]) )
602 return FALSE;
603 }
604
605 return (i2 == conflictset2->nbdchginfos);
606}
607
608#ifdef SCIP_DEBUG
609/** prints a conflict set to the screen */
610void conflictsetPrint(
611 SCIP_CONFLICTSET* conflictset /**< conflict set */
612 )
613{
614 int i;
615
616 assert(conflictset != NULL);
617 for( i = 0; i < conflictset->nbdchginfos; ++i )
618 {
619 SCIPdebugPrintf(" [%d:<%s> %s %g(%g)]", SCIPbdchginfoGetDepth(conflictset->bdchginfos[i]),
621 SCIPbdchginfoGetBoundtype(conflictset->bdchginfos[i]) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
622 SCIPbdchginfoGetNewbound(conflictset->bdchginfos[i]), conflictset->relaxedbds[i]);
623 }
624 SCIPdebugPrintf("\n");
625}
626#endif
627
628
629/** check conflict set for redundancy, other conflicts in the same conflict analysis could have led to global reductions
630 * an made this conflict set redundant
631 */
632static
634 SCIP_SET* set, /**< global SCIP settings */
635 SCIP_CONFLICTSET* conflictset /**< conflict set */
636 )
637{
638 SCIP_BDCHGINFO** bdchginfos;
639 SCIP_VAR* var;
640 SCIP_Real* relaxedbds;
642 int v;
643
644 assert(set != NULL);
645 assert(conflictset != NULL);
646
647 bdchginfos = conflictset->bdchginfos;
648 relaxedbds = conflictset->relaxedbds;
649 assert(bdchginfos != NULL);
650 assert(relaxedbds != NULL);
651
652 /* check all boundtypes and bounds for redundancy */
653 for( v = conflictset->nbdchginfos - 1; v >= 0; --v )
654 {
655 var = SCIPbdchginfoGetVar(bdchginfos[v]);
656 assert(var != NULL);
657 assert(SCIPvarGetProbindex(var) >= 0);
658
659 /* check if the relaxed bound is really a relaxed bound */
660 assert(SCIPbdchginfoGetBoundtype(bdchginfos[v]) == SCIP_BOUNDTYPE_LOWER || SCIPsetIsGE(set, relaxedbds[v], SCIPbdchginfoGetNewbound(bdchginfos[v])));
661 assert(SCIPbdchginfoGetBoundtype(bdchginfos[v]) == SCIP_BOUNDTYPE_UPPER || SCIPsetIsLE(set, relaxedbds[v], SCIPbdchginfoGetNewbound(bdchginfos[v])));
662
663 bound = relaxedbds[v];
664
665 if( SCIPbdchginfoGetBoundtype(bdchginfos[v]) == SCIP_BOUNDTYPE_UPPER )
666 {
668 {
669 assert(SCIPsetIsIntegral(set, bound));
670 bound += 1.0;
671 }
672
673 /* check if the bound is already fulfilled globally */
675 return TRUE;
676 }
677 else
678 {
679 assert(SCIPbdchginfoGetBoundtype(bdchginfos[v]) == SCIP_BOUNDTYPE_LOWER);
680
682 {
683 assert(SCIPsetIsIntegral(set, bound));
684 bound -= 1.0;
685 }
686
687 /* check if the bound is already fulfilled globally */
689 return TRUE;
690 }
691 }
692
693 return FALSE;
694}
695
696/** find global fixings which can be derived from the new conflict set */
697static
699 SCIP_SET* set, /**< global SCIP settings */
700 SCIP_PROB* prob, /**< transformed problem after presolve */
701 SCIP_STAT* stat, /**< dynamic SCIP statistics */
702 SCIP_TREE* tree, /**< tree data */
703 BMS_BLKMEM* blkmem, /**< block memory */
704 SCIP_PROB* origprob, /**< original problem */
705 SCIP_REOPT* reopt, /**< reoptimization data */
706 SCIP_LP* lp, /**< LP data */
707 SCIP_CONFLICTSET* conflictset, /**< conflict set to add to the tree */
708 int* nbdchgs, /**< number of global deducted bound changes due to the conflict set */
709 int* nredvars, /**< number of redundant and removed variables from conflict set */
710 SCIP_Bool* redundant /**< did we found a global reduction on a conflict set variable, which makes this conflict redundant */
711 )
712{
713 SCIP_BDCHGINFO** bdchginfos;
714 SCIP_Real* relaxedbds;
715 SCIP_VAR* var;
716 SCIP_Bool* boundtypes;
717 SCIP_Real* bounds;
718 SCIP_Longint* nbinimpls;
719 int* sortvals;
721 SCIP_Bool isupper;
722 int ntrivialredvars;
723 int nbdchginfos;
724 int nzeroimpls;
725 int v;
726
727 assert(set != NULL);
728 assert(prob != NULL);
729 assert(SCIPprobIsTransformed(prob));
730 assert(conflictset != NULL);
731 assert(nbdchgs != NULL);
732 assert(nredvars != NULL);
733 /* only check conflict sets with more than one variable */
734 assert(conflictset->nbdchginfos > 1);
735
736 *nbdchgs = 0;
737 *nredvars = 0;
738
739 /* due to other conflict in the same conflict analysis, this conflict set might have become redundant */
740 *redundant = checkRedundancy(set, conflictset);
741
742 if( *redundant )
743 return SCIP_OKAY;
744
745 bdchginfos = conflictset->bdchginfos;
746 relaxedbds = conflictset->relaxedbds;
747 nbdchginfos = conflictset->nbdchginfos;
748 sortvals = conflictset->sortvals;
749
750 assert(bdchginfos != NULL);
751 assert(relaxedbds != NULL);
752 assert(sortvals != NULL);
753
754 /* check if the boolean representation of boundtypes matches the 'standard' definition */
755 assert(SCIP_BOUNDTYPE_LOWER == FALSE); /*lint !e641 !e506*/
756 assert(SCIP_BOUNDTYPE_UPPER == TRUE); /*lint !e641 !e506*/
757
758 ntrivialredvars = 0;
759
760 /* due to multiple conflict sets for one conflict, it can happen, that we already have redundant information in the
761 * conflict set
762 */
763 for( v = nbdchginfos - 1; v >= 0; --v )
764 {
765 var = SCIPbdchginfoGetVar(bdchginfos[v]);
766 bound = relaxedbds[v];
768
769 /* for integral variable we can increase/decrease the conflicting bound */
770 if( SCIPvarIsIntegral(var) )
771 bound += (isupper ? -1.0 : +1.0);
772
773 /* if conflict variable cannot fulfill the conflict we can remove it */
774 if( (isupper && SCIPsetIsFeasLT(set, bound, SCIPvarGetLbGlobal(var))) ||
775 (!isupper && SCIPsetIsFeasGT(set, bound, SCIPvarGetUbGlobal(var))) )
776 {
777 SCIPsetDebugMsg(set, "remove redundant variable <%s> from conflict set\n", SCIPvarGetName(var));
778
779 bdchginfos[v] = bdchginfos[nbdchginfos - 1];
780 relaxedbds[v] = relaxedbds[nbdchginfos - 1];
781 sortvals[v] = sortvals[nbdchginfos - 1];
782
783 --nbdchginfos;
784 ++ntrivialredvars;
785 }
786 }
787 assert(ntrivialredvars + nbdchginfos == conflictset->nbdchginfos);
788
789 SCIPsetDebugMsg(set, "trivially removed %d redundant of %d variables from conflictset (%p)\n", ntrivialredvars, conflictset->nbdchginfos, (void*)conflictset);
790 conflictset->nbdchginfos = nbdchginfos;
791
792 /* all variables where removed, the conflict cannot be fulfilled, i.e., we have an infeasibility proof */
793 if( conflictset->nbdchginfos == 0 )
794 return SCIP_OKAY;
795
796 /* do not check to big or trivial conflicts */
797 if( conflictset->nbdchginfos > set->conf_maxvarsdetectimpliedbounds || conflictset->nbdchginfos == 1 )
798 {
799 *nredvars = ntrivialredvars;
800 return SCIP_OKAY;
801 }
802
803 /* create array of boundtypes, and bound values in conflict set */
804 SCIP_CALL( SCIPsetAllocBufferArray(set, &boundtypes, nbdchginfos) );
805 SCIP_CALL( SCIPsetAllocBufferArray(set, &bounds, nbdchginfos) );
806 /* memory for the estimates for binary implications used for sorting */
807 SCIP_CALL( SCIPsetAllocBufferArray(set, &nbinimpls, nbdchginfos) );
808
809 nzeroimpls = 0;
810
811 /* collect estimates and initialize variables, boundtypes, and bounds array */
812 for( v = 0; v < nbdchginfos; ++v )
813 {
814 var = SCIPbdchginfoGetVar(bdchginfos[v]);
815 boundtypes[v] = (SCIP_Bool) SCIPboundtypeOpposite(SCIPbdchginfoGetBoundtype(bdchginfos[v]));
816 bounds[v] = relaxedbds[v];
817
818 assert(SCIPvarGetProbindex(var) >= 0);
819
820 /* check if the relaxed bound is really a relaxed bound */
821 assert(SCIPbdchginfoGetBoundtype(bdchginfos[v]) == SCIP_BOUNDTYPE_LOWER || SCIPsetIsGE(set, relaxedbds[v], SCIPbdchginfoGetNewbound(bdchginfos[v])));
822 assert(SCIPbdchginfoGetBoundtype(bdchginfos[v]) == SCIP_BOUNDTYPE_UPPER || SCIPsetIsLE(set, relaxedbds[v], SCIPbdchginfoGetNewbound(bdchginfos[v])));
823
824 /* for continuous variables, we can only use the relaxed version of the bounds negation: !(x <= u) -> x >= u */
825 if( SCIPvarIsBinary(var) )
826 {
827 if( !boundtypes[v] )
828 {
829 assert(SCIPsetIsZero(set, bounds[v]));
830 bounds[v] = 1.0;
831 nbinimpls[v] = (SCIP_Longint)SCIPvarGetNCliques(var, TRUE) * 2;
832 }
833 else
834 {
835 assert(SCIPsetIsEQ(set, bounds[v], 1.0));
836 bounds[v] = 0.0;
837 nbinimpls[v] = (SCIP_Longint)SCIPvarGetNCliques(var, FALSE) * 2;
838 }
839 }
840 else if( SCIPvarIsIntegral(var) )
841 {
842 assert(SCIPsetIsIntegral(set, bounds[v]));
843
844 bounds[v] += ((!boundtypes[v]) ? +1.0 : -1.0);
845 nbinimpls[v] = (boundtypes[v] ? SCIPvarGetNVlbs(var) : SCIPvarGetNVubs(var));
846 }
847 else if( ((!boundtypes[v]) && SCIPsetIsFeasEQ(set, SCIPvarGetLbGlobal(var), bounds[v]))
848 || ((boundtypes[v]) && SCIPsetIsFeasEQ(set, SCIPvarGetUbGlobal(var), bounds[v])) )
849 {
850 /* the literal is satisfied in global bounds (may happen due to weak "negation" of continuous variables)
851 * -> discard the conflict constraint
852 */
853 break;
854 }
855 else
856 {
857 nbinimpls[v] = (boundtypes[v] ? SCIPvarGetNVlbs(var) : SCIPvarGetNVubs(var));
858 }
859
860 if( nbinimpls[v] == 0 )
861 ++nzeroimpls;
862 }
863
864 /* starting to derive global bound changes */
865 if( v == nbdchginfos && ((!set->conf_fullshortenconflict && nzeroimpls < 2) || (set->conf_fullshortenconflict && nzeroimpls < nbdchginfos)) )
866 {
867 SCIP_VAR** vars;
868 SCIP_Bool* redundants;
869 SCIP_Bool glbinfeas;
870
871 /* sort variables in increasing order of binary implications to gain speed later on */
872 SCIPsortLongPtrRealRealBool(nbinimpls, (void**)bdchginfos, relaxedbds, bounds, boundtypes, v);
873
874 SCIPsetDebugMsg(set, "checking for global reductions and redundant conflict variables(in %s) on conflict:\n", SCIPprobGetName(prob));
875 SCIPsetDebugMsg(set, "[");
876 for( v = 0; v < nbdchginfos; ++v )
877 {
878 SCIPsetDebugMsgPrint(set, "%s %s %g", SCIPvarGetName(SCIPbdchginfoGetVar(bdchginfos[v])), (!boundtypes[v]) ? ">=" : "<=", bounds[v]);
879 if( v < nbdchginfos - 1 )
881 }
883
885 SCIP_CALL( SCIPsetAllocCleanBufferArray(set, &redundants, v) );
886
887 /* initialize conflict variable data */
888 for( v = 0; v < nbdchginfos; ++v )
889 vars[v] = SCIPbdchginfoGetVar(bdchginfos[v]);
890
891 SCIP_CALL( SCIPshrinkDisjunctiveVarSet(set->scip, vars, bounds, boundtypes, redundants, nbdchginfos, nredvars, \
892 nbdchgs, redundant, &glbinfeas, set->conf_fullshortenconflict) );
893
894 if( glbinfeas )
895 {
896 SCIPsetDebugMsg(set, "conflict set (%p) led to global infeasibility\n", (void*) conflictset);
897
898 SCIP_CALL( SCIPnodeCutoff(SCIPtreeGetRootNode(tree), set, stat, tree, prob, origprob, reopt, lp, blkmem) );
899
900 /* clear the memory array before freeing it */
901 BMSclearMemoryArray(redundants, nbdchginfos);
902 goto TERMINATE;
903 }
904
905#ifdef SCIP_DEBUG
906 if( *nbdchgs > 0 )
907 {
908 SCIPsetDebugMsg(set, "conflict set (%p) led to %d global bound reductions\n", (void*) conflictset, *nbdchgs);
909 }
910#endif
911
912 /* remove as redundant marked variables */
913 if( *redundant )
914 {
915 SCIPsetDebugMsg(set, "conflict set (%p) is redundant because at least one global reduction, fulfills the conflict constraint\n", (void*)conflictset);
916
917 /* clear the memory array before freeing it */
918 BMSclearMemoryArray(redundants, nbdchginfos);
919 }
920 else if( *nredvars > 0 )
921 {
922 assert(bdchginfos == conflictset->bdchginfos);
923 assert(relaxedbds == conflictset->relaxedbds);
924 assert(sortvals == conflictset->sortvals);
925
926 for( v = nbdchginfos - 1; v >= 0; --v )
927 {
928 /* if conflict variable was marked to be redundant remove it */
929 if( redundants[v] )
930 {
931 SCIPsetDebugMsg(set, "remove redundant variable <%s> from conflict set\n", SCIPvarGetName(SCIPbdchginfoGetVar(bdchginfos[v])));
932
933 bdchginfos[v] = bdchginfos[nbdchginfos - 1];
934 relaxedbds[v] = relaxedbds[nbdchginfos - 1];
935 sortvals[v] = sortvals[nbdchginfos - 1];
936
937 /* reset redundants[v] to 0 */
938 redundants[v] = 0;
939
940 --nbdchginfos;
941 }
942 }
943 assert((*nredvars) + nbdchginfos == conflictset->nbdchginfos);
944
945 SCIPsetDebugMsg(set, "removed %d redundant of %d variables from conflictset (%p)\n", (*nredvars), conflictset->nbdchginfos, (void*)conflictset);
946 conflictset->nbdchginfos = nbdchginfos;
947 }
948 else
949 {
950 /* clear the memory array before freeing it */
951 BMSclearMemoryArray(redundants, nbdchginfos);
952 }
953
954 TERMINATE:
955 SCIPsetFreeCleanBufferArray(set, &redundants);
957 }
958
959 /* free temporary memory */
960 SCIPsetFreeBufferArray(set, &nbinimpls);
961 SCIPsetFreeBufferArray(set, &bounds);
962 SCIPsetFreeBufferArray(set, &boundtypes);
963
964 *nredvars += ntrivialredvars;
965
966 return SCIP_OKAY;
967}
968
969/** clears the given conflict set */
970static
972 SCIP_CONFLICTSET* conflictset /**< conflict set */
973 )
974{
975 assert(conflictset != NULL);
976
977 conflictset->nbdchginfos = 0;
978 conflictset->validdepth = 0;
979 conflictset->insertdepth = 0;
980 conflictset->conflictdepth = 0;
981 conflictset->repropdepth = 0;
982 conflictset->repropagate = TRUE;
983 conflictset->usescutoffbound = FALSE;
984 conflictset->hasrelaxonlyvar = FALSE;
985 conflictset->conflicttype = SCIP_CONFTYPE_UNKNOWN;
986}
987
988/** creates an empty conflict set */
990 SCIP_CONFLICTSET** conflictset, /**< pointer to store the conflict set */
991 BMS_BLKMEM* blkmem /**< block memory of transformed problem */
992 )
993{
994 assert(conflictset != NULL);
995
996 SCIP_ALLOC( BMSallocBlockMemory(blkmem, conflictset) );
997 (*conflictset)->bdchginfos = NULL;
998 (*conflictset)->relaxedbds = NULL;
999 (*conflictset)->sortvals = NULL;
1000 (*conflictset)->bdchginfossize = 0;
1001
1002 conflictsetClear(*conflictset);
1003
1004 return SCIP_OKAY;
1005}
1006
1007/** creates a copy of the given conflict set, allocating an additional amount of memory */
1008static
1010 SCIP_CONFLICTSET** targetconflictset, /**< pointer to store the conflict set */
1011 BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
1012 SCIP_CONFLICTSET* sourceconflictset, /**< source conflict set */
1013 int nadditionalelems /**< number of additional elements to allocate memory for */
1014 )
1015{
1016 int targetsize;
1017
1018 assert(targetconflictset != NULL);
1019 assert(sourceconflictset != NULL);
1020
1021 targetsize = sourceconflictset->nbdchginfos + nadditionalelems;
1022 SCIP_ALLOC( BMSallocBlockMemory(blkmem, targetconflictset) );
1023 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*targetconflictset)->bdchginfos, targetsize) );
1024 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*targetconflictset)->relaxedbds, targetsize) );
1025 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*targetconflictset)->sortvals, targetsize) );
1026 (*targetconflictset)->bdchginfossize = targetsize;
1027
1028 BMScopyMemoryArray((*targetconflictset)->bdchginfos, sourceconflictset->bdchginfos, sourceconflictset->nbdchginfos);
1029 BMScopyMemoryArray((*targetconflictset)->relaxedbds, sourceconflictset->relaxedbds, sourceconflictset->nbdchginfos);
1030 BMScopyMemoryArray((*targetconflictset)->sortvals, sourceconflictset->sortvals, sourceconflictset->nbdchginfos);
1031
1032 (*targetconflictset)->nbdchginfos = sourceconflictset->nbdchginfos;
1033 (*targetconflictset)->validdepth = sourceconflictset->validdepth;
1034 (*targetconflictset)->insertdepth = sourceconflictset->insertdepth;
1035 (*targetconflictset)->conflictdepth = sourceconflictset->conflictdepth;
1036 (*targetconflictset)->repropdepth = sourceconflictset->repropdepth;
1037 (*targetconflictset)->usescutoffbound = sourceconflictset->usescutoffbound;
1038 (*targetconflictset)->hasrelaxonlyvar = sourceconflictset->hasrelaxonlyvar;
1039 (*targetconflictset)->conflicttype = sourceconflictset->conflicttype;
1040
1041 return SCIP_OKAY;
1042}
1043
1044/** frees a conflict set */
1046 SCIP_CONFLICTSET** conflictset, /**< pointer to the conflict set */
1047 BMS_BLKMEM* blkmem /**< block memory of transformed problem */
1048 )
1049{
1050 assert(conflictset != NULL);
1051 assert(*conflictset != NULL);
1052
1053 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictset)->bdchginfos, (*conflictset)->bdchginfossize);
1054 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictset)->relaxedbds, (*conflictset)->bdchginfossize);
1055 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictset)->sortvals, (*conflictset)->bdchginfossize);
1056 BMSfreeBlockMemory(blkmem, conflictset);
1057}
1058
1059/** calculates the score of the conflict set
1060 *
1061 * the score is weighted sum of number of bound changes, repropagation depth, and valid depth
1062 */
1063static
1065 SCIP_CONFLICTSET* conflictset, /**< conflict set */
1066 SCIP_SET* set /**< global SCIP settings */
1067 )
1068{
1069 assert(conflictset != NULL);
1070
1071 return -(set->conf_weightsize * conflictset->nbdchginfos
1072 + set->conf_weightrepropdepth * conflictset->repropdepth
1073 + set->conf_weightvaliddepth * conflictset->validdepth);
1074}
1075
1076
1077/*
1078 * Conflict Handler
1079 */
1080
1081/** compares two conflict handlers w. r. to their priority */
1082SCIP_DECL_SORTPTRCOMP(SCIPconflicthdlrComp)
1083{ /*lint --e{715}*/
1084 return ((SCIP_CONFLICTHDLR*)elem2)->priority - ((SCIP_CONFLICTHDLR*)elem1)->priority;
1085}
1086
1087/** comparison method for sorting conflict handler w.r.t. to their name */
1088SCIP_DECL_SORTPTRCOMP(SCIPconflicthdlrCompName)
1089{
1091}
1092
1093/** method to call, when the priority of a conflict handler was changed */
1094static
1095SCIP_DECL_PARAMCHGD(paramChgdConflicthdlrPriority)
1096{ /*lint --e{715}*/
1097 SCIP_PARAMDATA* paramdata;
1098
1099 paramdata = SCIPparamGetData(param);
1100 assert(paramdata != NULL);
1101
1102 /* use SCIPsetConflicthdlrPriority() to mark the conflicthdlrs unsorted */
1103 SCIP_CALL( SCIPsetConflicthdlrPriority(scip, (SCIP_CONFLICTHDLR*)paramdata, SCIPparamGetInt(param)) ); /*lint !e740*/
1104
1105 return SCIP_OKAY;
1106}
1107
1108/** copies the given conflict handler to a new scip */
1110 SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
1111 SCIP_SET* set /**< SCIP_SET of SCIP to copy to */
1112 )
1113{
1114 assert(conflicthdlr != NULL);
1115 assert(set != NULL);
1116 assert(set->scip != NULL);
1117
1118 if( conflicthdlr->conflictcopy != NULL )
1119 {
1120 SCIPsetDebugMsg(set, "including conflict handler %s in subscip %p\n", SCIPconflicthdlrGetName(conflicthdlr), (void*)set->scip);
1121 SCIP_CALL( conflicthdlr->conflictcopy(set->scip, conflicthdlr) );
1122 }
1123
1124 return SCIP_OKAY;
1125}
1126
1127/** internal method for creating a conflict handler */
1128static
1130 SCIP_CONFLICTHDLR** conflicthdlr, /**< pointer to conflict handler data structure */
1131 SCIP_SET* set, /**< global SCIP settings */
1132 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1133 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
1134 const char* name, /**< name of conflict handler */
1135 const char* desc, /**< description of conflict handler */
1136 int priority, /**< priority of the conflict handler */
1137 SCIP_DECL_CONFLICTCOPY((*conflictcopy)), /**< copy method of conflict handler or NULL if you don't want to copy your plugin into sub-SCIPs */
1138 SCIP_DECL_CONFLICTFREE((*conflictfree)), /**< destructor of conflict handler */
1139 SCIP_DECL_CONFLICTINIT((*conflictinit)), /**< initialize conflict handler */
1140 SCIP_DECL_CONFLICTEXIT((*conflictexit)), /**< deinitialize conflict handler */
1141 SCIP_DECL_CONFLICTINITSOL((*conflictinitsol)),/**< solving process initialization method of conflict handler */
1142 SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol)),/**< solving process deinitialization method of conflict handler */
1143 SCIP_DECL_CONFLICTEXEC((*conflictexec)), /**< conflict processing method of conflict handler */
1144 SCIP_CONFLICTHDLRDATA* conflicthdlrdata /**< conflict handler data */
1145 )
1146{
1148 char paramdesc[SCIP_MAXSTRLEN];
1149
1150 assert(conflicthdlr != NULL);
1151 assert(name != NULL);
1152 assert(desc != NULL);
1153
1154 SCIP_ALLOC( BMSallocMemory(conflicthdlr) );
1155 BMSclearMemory(*conflicthdlr);
1156
1157 SCIP_ALLOC( BMSduplicateMemoryArray(&(*conflicthdlr)->name, name, strlen(name)+1) );
1158 SCIP_ALLOC( BMSduplicateMemoryArray(&(*conflicthdlr)->desc, desc, strlen(desc)+1) );
1159 (*conflicthdlr)->priority = priority;
1160 (*conflicthdlr)->conflictcopy = conflictcopy;
1161 (*conflicthdlr)->conflictfree = conflictfree;
1162 (*conflicthdlr)->conflictinit = conflictinit;
1163 (*conflicthdlr)->conflictexit = conflictexit;
1164 (*conflicthdlr)->conflictinitsol = conflictinitsol;
1165 (*conflicthdlr)->conflictexitsol = conflictexitsol;
1166 (*conflicthdlr)->conflictexec = conflictexec;
1167 (*conflicthdlr)->conflicthdlrdata = conflicthdlrdata;
1168 (*conflicthdlr)->initialized = FALSE;
1169
1170 SCIP_CALL( SCIPclockCreate(&(*conflicthdlr)->setuptime, SCIP_CLOCKTYPE_DEFAULT) );
1171 SCIP_CALL( SCIPclockCreate(&(*conflicthdlr)->conflicttime, SCIP_CLOCKTYPE_DEFAULT) );
1172
1173 /* add parameters */
1174 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "conflict/%s/priority", name);
1175 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "priority of conflict handler <%s>", name);
1176 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc, &(*conflicthdlr)->priority, TRUE, \
1177 priority, INT_MIN, INT_MAX, paramChgdConflicthdlrPriority, (SCIP_PARAMDATA*)(*conflicthdlr)) ); /*lint !e740*/
1178
1179 return SCIP_OKAY;
1180}
1181
1182/** creates a conflict handler */
1184 SCIP_CONFLICTHDLR** conflicthdlr, /**< pointer to conflict handler data structure */
1185 SCIP_SET* set, /**< global SCIP settings */
1186 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1187 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
1188 const char* name, /**< name of conflict handler */
1189 const char* desc, /**< description of conflict handler */
1190 int priority, /**< priority of the conflict handler */
1191 SCIP_DECL_CONFLICTCOPY((*conflictcopy)), /**< copy method of conflict handler or NULL if you don't want to
1192 * copy your plugin into sub-SCIPs */
1193 SCIP_DECL_CONFLICTFREE((*conflictfree)), /**< destructor of conflict handler */
1194 SCIP_DECL_CONFLICTINIT((*conflictinit)), /**< initialize conflict handler */
1195 SCIP_DECL_CONFLICTEXIT((*conflictexit)), /**< deinitialize conflict handler */
1196 SCIP_DECL_CONFLICTINITSOL((*conflictinitsol)),/**< solving process initialization method of conflict handler */
1197 SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol)),/**< solving process deinitialization method of conflict handler */
1198 SCIP_DECL_CONFLICTEXEC((*conflictexec)), /**< conflict processing method of conflict handler */
1199 SCIP_CONFLICTHDLRDATA* conflicthdlrdata /**< conflict handler data */
1200 )
1201{
1202 assert(conflicthdlr != NULL);
1203 assert(name != NULL);
1204 assert(desc != NULL);
1205
1206 SCIP_CALL_FINALLY( doConflicthdlrCreate(conflicthdlr, set, messagehdlr, blkmem, name, desc, priority,
1207 conflictcopy, conflictfree, conflictinit, conflictexit, conflictinitsol, conflictexitsol, conflictexec,
1208 conflicthdlrdata), (void) SCIPconflicthdlrFree(conflicthdlr, set) );
1209
1210 return SCIP_OKAY;
1211}
1212
1213/** calls destructor and frees memory of conflict handler */
1215 SCIP_CONFLICTHDLR** conflicthdlr, /**< pointer to conflict handler data structure */
1216 SCIP_SET* set /**< global SCIP settings */
1217 )
1218{
1219 assert(conflicthdlr != NULL);
1220 if( *conflicthdlr == NULL )
1221 return SCIP_OKAY;
1222 assert(!(*conflicthdlr)->initialized);
1223 assert(set != NULL);
1224
1225 /* call destructor of conflict handler */
1226 if( (*conflicthdlr)->conflictfree != NULL )
1227 {
1228 SCIP_CALL( (*conflicthdlr)->conflictfree(set->scip, *conflicthdlr) );
1229 }
1230
1231 SCIPclockFree(&(*conflicthdlr)->conflicttime);
1232 SCIPclockFree(&(*conflicthdlr)->setuptime);
1233
1234 BMSfreeMemoryArrayNull(&(*conflicthdlr)->name);
1235 BMSfreeMemoryArrayNull(&(*conflicthdlr)->desc);
1236 BMSfreeMemory(conflicthdlr);
1237
1238 return SCIP_OKAY;
1239}
1240
1241/** calls initialization method of conflict handler */
1243 SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
1244 SCIP_SET* set /**< global SCIP settings */
1245 )
1246{
1247 assert(conflicthdlr != NULL);
1248 assert(set != NULL);
1249
1250 if( conflicthdlr->initialized )
1251 {
1252 SCIPerrorMessage("conflict handler <%s> already initialized\n", conflicthdlr->name);
1253 return SCIP_INVALIDCALL;
1254 }
1255
1256 if( set->misc_resetstat )
1257 {
1258 SCIPclockReset(conflicthdlr->setuptime);
1259 SCIPclockReset(conflicthdlr->conflicttime);
1260 }
1261
1262 /* call initialization method of conflict handler */
1263 if( conflicthdlr->conflictinit != NULL )
1264 {
1265 /* start timing */
1266 SCIPclockStart(conflicthdlr->setuptime, set);
1267
1268 SCIP_CALL( conflicthdlr->conflictinit(set->scip, conflicthdlr) );
1269
1270 /* stop timing */
1271 SCIPclockStop(conflicthdlr->setuptime, set);
1272 }
1273 conflicthdlr->initialized = TRUE;
1274
1275 return SCIP_OKAY;
1276}
1277
1278/** calls exit method of conflict handler */
1280 SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
1281 SCIP_SET* set /**< global SCIP settings */
1282 )
1283{
1284 assert(conflicthdlr != NULL);
1285 assert(set != NULL);
1286
1287 if( !conflicthdlr->initialized )
1288 {
1289 SCIPerrorMessage("conflict handler <%s> not initialized\n", conflicthdlr->name);
1290 return SCIP_INVALIDCALL;
1291 }
1292
1293 /* call deinitialization method of conflict handler */
1294 if( conflicthdlr->conflictexit != NULL )
1295 {
1296 /* start timing */
1297 SCIPclockStart(conflicthdlr->setuptime, set);
1298
1299 SCIP_CALL( conflicthdlr->conflictexit(set->scip, conflicthdlr) );
1300
1301 /* stop timing */
1302 SCIPclockStop(conflicthdlr->setuptime, set);
1303 }
1304 conflicthdlr->initialized = FALSE;
1305
1306 return SCIP_OKAY;
1307}
1308
1309/** informs conflict handler that the branch and bound process is being started */
1311 SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
1312 SCIP_SET* set /**< global SCIP settings */
1313 )
1314{
1315 assert(conflicthdlr != NULL);
1316 assert(set != NULL);
1317
1318 /* call solving process initialization method of conflict handler */
1319 if( conflicthdlr->conflictinitsol != NULL )
1320 {
1321 /* start timing */
1322 SCIPclockStart(conflicthdlr->setuptime, set);
1323
1324 SCIP_CALL( conflicthdlr->conflictinitsol(set->scip, conflicthdlr) );
1325
1326 /* stop timing */
1327 SCIPclockStop(conflicthdlr->setuptime, set);
1328 }
1329
1330 return SCIP_OKAY;
1331}
1332
1333/** informs conflict handler that the branch and bound process data is being freed */
1335 SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
1336 SCIP_SET* set /**< global SCIP settings */
1337 )
1338{
1339 assert(conflicthdlr != NULL);
1340 assert(set != NULL);
1341
1342 /* call solving process deinitialization method of conflict handler */
1343 if( conflicthdlr->conflictexitsol != NULL )
1344 {
1345 /* start timing */
1346 SCIPclockStart(conflicthdlr->setuptime, set);
1347
1348 SCIP_CALL( conflicthdlr->conflictexitsol(set->scip, conflicthdlr) );
1349
1350 /* stop timing */
1351 SCIPclockStop(conflicthdlr->setuptime, set);
1352 }
1353
1354 return SCIP_OKAY;
1355}
1356
1357/** calls execution method of conflict handler */
1359 SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
1360 SCIP_SET* set, /**< global SCIP settings */
1361 SCIP_NODE* node, /**< node to add conflict constraint to */
1362 SCIP_NODE* validnode, /**< node at which the constraint is valid */
1363 SCIP_BDCHGINFO** bdchginfos, /**< bound change resembling the conflict set */
1364 SCIP_Real* relaxedbds, /**< array with relaxed bounds which are efficient to create a valid conflict */
1365 int nbdchginfos, /**< number of bound changes in the conflict set */
1366 SCIP_CONFTYPE conftype, /**< type of the conflict */
1367 SCIP_Bool usescutoffbound, /**< depends the conflict on the cutoff bound? */
1368 SCIP_Bool resolved, /**< was the conflict set already used to create a constraint? */
1369 SCIP_RESULT* result /**< pointer to store the result of the callback method */
1370 )
1371{
1372 assert(conflicthdlr != NULL);
1373 assert(set != NULL);
1374 assert(bdchginfos != NULL || nbdchginfos == 0);
1375 assert(result != NULL);
1376
1377 /* call solution start method of conflict handler */
1378 *result = SCIP_DIDNOTRUN;
1379 if( conflicthdlr->conflictexec != NULL )
1380 {
1381 /* start timing */
1382 SCIPclockStart(conflicthdlr->conflicttime, set);
1383
1384 SCIP_CALL( conflicthdlr->conflictexec(set->scip, conflicthdlr, node, validnode, bdchginfos, relaxedbds, nbdchginfos,
1385 conftype, usescutoffbound, set->conf_separate, (SCIPnodeGetDepth(validnode) > 0), set->conf_dynamic,
1386 set->conf_removable, resolved, result) );
1387
1388 /* stop timing */
1389 SCIPclockStop(conflicthdlr->conflicttime, set);
1390
1391 if( *result != SCIP_CONSADDED
1392 && *result != SCIP_DIDNOTFIND
1393 && *result != SCIP_DIDNOTRUN )
1394 {
1395 SCIPerrorMessage("execution method of conflict handler <%s> returned invalid result <%d>\n",
1396 conflicthdlr->name, *result);
1397 return SCIP_INVALIDRESULT;
1398 }
1399 }
1400
1401 return SCIP_OKAY;
1402}
1403
1404/** gets user data of conflict handler */
1406 SCIP_CONFLICTHDLR* conflicthdlr /**< conflict handler */
1407 )
1408{
1409 assert(conflicthdlr != NULL);
1410
1411 return conflicthdlr->conflicthdlrdata;
1412}
1413
1414/** sets user data of conflict handler; user has to free old data in advance! */
1416 SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
1417 SCIP_CONFLICTHDLRDATA* conflicthdlrdata /**< new conflict handler user data */
1418 )
1419{
1420 assert(conflicthdlr != NULL);
1421
1422 conflicthdlr->conflicthdlrdata = conflicthdlrdata;
1423}
1424
1425/** set copy method of conflict handler */
1427 SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
1428 SCIP_DECL_CONFLICTCOPY((*conflictcopy)) /**< copy method of the conflict handler */
1429 )
1430{
1431 assert(conflicthdlr != NULL);
1432
1433 conflicthdlr->conflictcopy = conflictcopy;
1434}
1435
1436/** set destructor of conflict handler */
1438 SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
1439 SCIP_DECL_CONFLICTFREE((*conflictfree)) /**< destructor of conflict handler */
1440 )
1441{
1442 assert(conflicthdlr != NULL);
1443
1444 conflicthdlr->conflictfree = conflictfree;
1445}
1446
1447/** set initialization method of conflict handler */
1448
1450 SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
1451 SCIP_DECL_CONFLICTINIT((*conflictinit)) /**< initialization method conflict handler */
1452 )
1453{
1454 assert(conflicthdlr != NULL);
1455
1456 conflicthdlr->conflictinit = conflictinit;
1457}
1458
1459/** set deinitialization method of conflict handler */
1461 SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
1462 SCIP_DECL_CONFLICTEXIT((*conflictexit)) /**< deinitialization method conflict handler */
1463 )
1464{
1465 assert(conflicthdlr != NULL);
1466
1467 conflicthdlr->conflictexit = conflictexit;
1468}
1469
1470/** set solving process initialization method of conflict handler */
1472 SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
1473 SCIP_DECL_CONFLICTINITSOL((*conflictinitsol))/**< solving process initialization method of conflict handler */
1474 )
1475{
1476 assert(conflicthdlr != NULL);
1477
1478 conflicthdlr->conflictinitsol = conflictinitsol;
1479}
1480
1481/** set solving process deinitialization method of conflict handler */
1483 SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
1484 SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol))/**< solving process deinitialization method of conflict handler */
1485 )
1486{
1487 assert(conflicthdlr != NULL);
1488
1489 conflicthdlr->conflictexitsol = conflictexitsol;
1490}
1491
1492/** gets name of conflict handler */
1494 SCIP_CONFLICTHDLR* conflicthdlr /**< conflict handler */
1495 )
1496{
1497 assert(conflicthdlr != NULL);
1498
1499 return conflicthdlr->name;
1500}
1501
1502/** gets description of conflict handler */
1504 SCIP_CONFLICTHDLR* conflicthdlr /**< conflict handler */
1505 )
1506{
1507 assert(conflicthdlr != NULL);
1508
1509 return conflicthdlr->desc;
1510}
1511
1512/** gets priority of conflict handler */
1514 SCIP_CONFLICTHDLR* conflicthdlr /**< conflict handler */
1515 )
1516{
1517 assert(conflicthdlr != NULL);
1518
1519 return conflicthdlr->priority;
1520}
1521
1522/** sets priority of conflict handler */
1524 SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */
1525 SCIP_SET* set, /**< global SCIP settings */
1526 int priority /**< new priority of the conflict handler */
1527 )
1528{
1529 assert(conflicthdlr != NULL);
1530 assert(set != NULL);
1531
1532 conflicthdlr->priority = priority;
1533 set->conflicthdlrssorted = FALSE;
1534}
1535
1536/** is conflict handler initialized? */
1538 SCIP_CONFLICTHDLR* conflicthdlr /**< conflict handler */
1539 )
1540{
1541 assert(conflicthdlr != NULL);
1542
1543 return conflicthdlr->initialized;
1544}
1545
1546/** enables or disables all clocks of \p conflicthdlr, depending on the value of the flag */
1548 SCIP_CONFLICTHDLR* conflicthdlr, /**< the conflict handler for which all clocks should be enabled or disabled */
1549 SCIP_Bool enable /**< should the clocks of the conflict handler be enabled? */
1550 )
1551{
1552 assert(conflicthdlr != NULL);
1553
1554 SCIPclockEnableOrDisable(conflicthdlr->setuptime, enable);
1555 SCIPclockEnableOrDisable(conflicthdlr->conflicttime, enable);
1556}
1557
1558/** gets time in seconds used in this conflict handler for setting up for next stages */
1560 SCIP_CONFLICTHDLR* conflicthdlr /**< conflict handler */
1561 )
1562{
1563 assert(conflicthdlr != NULL);
1564
1565 return SCIPclockGetTime(conflicthdlr->setuptime);
1566}
1567
1568/** gets time in seconds used in this conflict handler */
1570 SCIP_CONFLICTHDLR* conflicthdlr /**< conflict handler */
1571 )
1572{
1573 assert(conflicthdlr != NULL);
1574
1575 return SCIPclockGetTime(conflicthdlr->conflicttime);
1576}
1577
1578/** return TRUE if conflict analysis is applicable; In case the function return FALSE there is no need to initialize the
1579 * conflict analysis since it will not be applied
1580 */
1582 SCIP_SET* set /**< global SCIP settings */
1583 )
1584{
1585 /* check, if propagation conflict analysis is enabled */
1586 if( !set->conf_enable || !set->conf_useprop )
1587 return FALSE;
1588
1589 /* check, if there are any conflict handlers to use a conflict set */
1590 if( set->nconflicthdlrs == 0 )
1591 return FALSE;
1592
1593 return TRUE;
1594}
1595
1596/** resizes the array of the temporary bound change informations to be able to store at least num bound change entries */
1597static
1599 SCIP_CONFLICT* conflict, /**< conflict analysis data */
1600 SCIP_SET* set, /**< global SCIP settings */
1601 int num /**< minimal number of slots in arrays */
1602 )
1603{
1604 assert(conflict != NULL);
1605 assert(set != NULL);
1606
1607 if( num > conflict->tmpbdchginfossize )
1608 {
1609 int newsize;
1610
1611 newsize = SCIPsetCalcMemGrowSize(set, num);
1612 SCIP_ALLOC( BMSreallocMemoryArray(&conflict->tmpbdchginfos, newsize) );
1613 conflict->tmpbdchginfossize = newsize;
1614 }
1615 assert(num <= conflict->tmpbdchginfossize);
1616
1617 return SCIP_OKAY;
1618}
1619
1620/** creates a temporary bound change information object that is destroyed after the conflict sets are flushed */
1622 SCIP_CONFLICT* conflict, /**< conflict analysis data */
1623 BMS_BLKMEM* blkmem, /**< block memory */
1624 SCIP_SET* set, /**< global SCIP settings */
1625 SCIP_VAR* var, /**< active variable that changed the bounds */
1626 SCIP_BOUNDTYPE boundtype, /**< type of bound for var: lower or upper bound */
1627 SCIP_Real oldbound, /**< old value for bound */
1628 SCIP_Real newbound, /**< new value for bound */
1629 SCIP_BDCHGINFO** bdchginfo /**< pointer to store bound change information */
1630 )
1631{
1632 assert(conflict != NULL);
1633
1635 SCIP_CALL( SCIPbdchginfoCreate(&conflict->tmpbdchginfos[conflict->ntmpbdchginfos], blkmem,
1636 var, boundtype, oldbound, newbound) );
1637 *bdchginfo = conflict->tmpbdchginfos[conflict->ntmpbdchginfos];
1638 conflict->ntmpbdchginfos++;
1639
1640 return SCIP_OKAY;
1641}
1642
1643/** frees all temporarily created bound change information data */
1644static
1646 SCIP_CONFLICT* conflict, /**< conflict analysis data */
1647 BMS_BLKMEM* blkmem /**< block memory */
1648 )
1649{
1650 int i;
1651
1652 assert(conflict != NULL);
1653
1654 for( i = 0; i < conflict->ntmpbdchginfos; ++i )
1655 SCIPbdchginfoFree(&conflict->tmpbdchginfos[i], blkmem);
1656 conflict->ntmpbdchginfos = 0;
1657}
1658
1659/** increases the conflict score of the variable in the given direction */
1660static
1662 SCIP_VAR* var, /**< problem variable */
1663 BMS_BLKMEM* blkmem, /**< block memory */
1664 SCIP_SET* set, /**< global SCIP settings */
1665 SCIP_STAT* stat, /**< dynamic problem statistics */
1666 SCIP_BOUNDTYPE boundtype, /**< type of bound for which the score should be increased */
1667 SCIP_Real value, /**< value of the bound */
1668 SCIP_Real weight /**< weight of this VSIDS updates */
1669 )
1670{
1671 SCIP_BRANCHDIR branchdir;
1672
1673 assert(var != NULL);
1674 assert(stat != NULL);
1675
1676 /* weight the VSIDS by the given weight */
1677 weight *= stat->vsidsweight;
1678
1679 if( SCIPsetIsZero(set, weight) )
1680 return SCIP_OKAY;
1681
1682 branchdir = (boundtype == SCIP_BOUNDTYPE_LOWER ? SCIP_BRANCHDIR_UPWARDS : SCIP_BRANCHDIR_DOWNWARDS); /*lint !e641*/
1683 SCIP_CALL( SCIPvarIncVSIDS(var, blkmem, set, stat, branchdir, value, weight) );
1684 SCIPhistoryIncVSIDS(stat->glbhistory, branchdir, weight);
1685 SCIPhistoryIncVSIDS(stat->glbhistorycrun, branchdir, weight);
1686
1687 return SCIP_OKAY;
1688}
1689
1690/** update conflict statistics */
1691static
1693 SCIP_CONFLICT* conflict, /**< conflict analysis data */
1694 BMS_BLKMEM* blkmem, /**< block memory */
1695 SCIP_SET* set, /**< global SCIP settings */
1696 SCIP_STAT* stat, /**< dynamic problem statistics */
1697 SCIP_CONFLICTSET* conflictset, /**< conflict set to add to the tree */
1698 int insertdepth /**< depth level at which the conflict set should be added */
1699 )
1700{
1701 if( insertdepth > 0 )
1702 {
1703 conflict->nappliedlocconss++;
1704 conflict->nappliedlocliterals += conflictset->nbdchginfos;
1705 }
1706 else
1707 {
1708 int i;
1709 int conflictlength;
1710 conflictlength = conflictset->nbdchginfos;
1711
1712 for( i = 0; i < conflictlength; i++ )
1713 {
1714 SCIP_VAR* var;
1715 SCIP_BRANCHDIR branchdir;
1716 SCIP_BOUNDTYPE boundtype;
1718
1719 assert(stat != NULL);
1720
1721 var = conflictset->bdchginfos[i]->var;
1722 boundtype = SCIPbdchginfoGetBoundtype(conflictset->bdchginfos[i]);
1723 bound = conflictset->relaxedbds[i];
1724
1725 branchdir = (boundtype == SCIP_BOUNDTYPE_LOWER ? SCIP_BRANCHDIR_UPWARDS : SCIP_BRANCHDIR_DOWNWARDS); /*lint !e641*/
1726
1727 SCIP_CALL( SCIPvarIncNActiveConflicts(var, blkmem, set, stat, branchdir, bound, (SCIP_Real)conflictlength) );
1728 SCIPhistoryIncNActiveConflicts(stat->glbhistory, branchdir, (SCIP_Real)conflictlength);
1729 SCIPhistoryIncNActiveConflicts(stat->glbhistorycrun, branchdir, (SCIP_Real)conflictlength);
1730
1731 /* each variable which is part of the conflict gets an increase in the VSIDS */
1732 SCIP_CALL( incVSIDS(var, blkmem, set, stat, boundtype, bound, set->conf_conflictweight) );
1733 }
1734 conflict->nappliedglbconss++;
1735 conflict->nappliedglbliterals += conflictset->nbdchginfos;
1736 }
1737
1738 return SCIP_OKAY;
1739}
1740
1741/** adds the given conflict set as conflict constraint to the problem */
1742static
1744 SCIP_CONFLICT* conflict, /**< conflict analysis data */
1745 BMS_BLKMEM* blkmem, /**< block memory */
1746 SCIP_SET* set, /**< global SCIP settings */
1747 SCIP_STAT* stat, /**< dynamic problem statistics */
1748 SCIP_PROB* transprob, /**< transformed problem after presolve */
1749 SCIP_PROB* origprob, /**< original problem */
1750 SCIP_TREE* tree, /**< branch and bound tree */
1751 SCIP_REOPT* reopt, /**< reoptimization data structure */
1752 SCIP_LP* lp, /**< current LP data */
1753 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1754 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1755 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1756 SCIP_CONFLICTSET* conflictset, /**< conflict set to add to the tree */
1757 int insertdepth, /**< depth level at which the conflict set should be added */
1758 SCIP_Bool* success /**< pointer to store whether the addition was successful */
1759 )
1760{
1761 SCIP_Bool redundant;
1762 int h;
1763
1764 assert(conflict != NULL);
1765 assert(tree != NULL);
1766 assert(tree->path != NULL);
1767 assert(conflictset != NULL);
1768 assert(conflictset->validdepth <= insertdepth);
1769 assert(success != NULL);
1770
1771 *success = FALSE;
1772 redundant = FALSE;
1773
1774 /* try to derive global bound changes and shorten the conflictset by using implication and clique and variable bound
1775 * information
1776 */
1777 if( conflictset->nbdchginfos > 1 && insertdepth == 0 && !lp->strongbranching )
1778 {
1779 int nbdchgs;
1780 int nredvars;
1781#ifdef SCIP_DEBUG
1782 int oldnbdchginfos = conflictset->nbdchginfos;
1783#endif
1784 assert(conflictset->validdepth == 0);
1785
1786 /* check conflict set on debugging solution */
1787 SCIP_CALL( SCIPdebugCheckConflict(blkmem, set, tree->root, conflictset->bdchginfos, conflictset->relaxedbds, conflictset->nbdchginfos) );
1788
1789 SCIPclockStart(conflict->dIBclock, set);
1790
1791 /* find global bound changes which can be derived from the new conflict set */
1792 SCIP_CALL( detectImpliedBounds(set, transprob, stat, tree, blkmem, origprob, reopt, lp, conflictset, &nbdchgs, &nredvars, &redundant) );
1793
1794 /* all variables where removed, we have an infeasibility proof */
1795 if( conflictset->nbdchginfos == 0 )
1796 return SCIP_OKAY;
1797
1798 /* debug check for reduced conflict set */
1799 if( nredvars > 0 )
1800 {
1801 /* check conflict set on debugging solution */
1802 SCIP_CALL( SCIPdebugCheckConflict(blkmem, set, tree->root, conflictset->bdchginfos, conflictset->relaxedbds, conflictset->nbdchginfos) ); /*lint !e506 !e774*/
1803 }
1804
1805#ifdef SCIP_DEBUG
1806 SCIPsetDebugMsg(set, " -> conflict set removed %d redundant variables (old nvars %d, new nvars = %d)\n", nredvars, oldnbdchginfos, conflictset->nbdchginfos);
1807 SCIPsetDebugMsg(set, " -> conflict set led to %d global bound changes %s(cdpt:%d, fdpt:%d, confdpt:%d, len:%d):\n",
1808 nbdchgs, redundant ? "(conflict became redundant) " : "", SCIPtreeGetCurrentDepth(tree), SCIPtreeGetFocusDepth(tree),
1809 conflictset->conflictdepth, conflictset->nbdchginfos);
1810 conflictsetPrint(conflictset);
1811#endif
1812
1813 SCIPclockStop(conflict->dIBclock, set);
1814
1815 if( redundant )
1816 {
1817 if( nbdchgs > 0 )
1818 *success = TRUE;
1819
1820 return SCIP_OKAY;
1821 }
1822 }
1823
1824 /* in case the conflict set contains only one bound change which is globally valid we apply that bound change
1825 * directly (except if we are in strong branching or diving - in this case a bound change would yield an unflushed LP
1826 * and is not handled when restoring the information)
1827 *
1828 * @note A bound change can only be applied if it is are related to the active node or if is a global bound
1829 * change. Bound changes which are related to any other node cannot be handled at point due to the internal
1830 * data structure
1831 */
1832 if( conflictset->nbdchginfos == 1 && insertdepth == 0 && !lp->strongbranching && !lp->diving )
1833 {
1834 SCIP_VAR* var;
1836 SCIP_BOUNDTYPE boundtype;
1837
1838 var = conflictset->bdchginfos[0]->var;
1839 assert(var != NULL);
1840
1841 boundtype = SCIPboundtypeOpposite((SCIP_BOUNDTYPE) conflictset->bdchginfos[0]->boundtype);
1842 bound = conflictset->relaxedbds[0];
1843
1844 /* for continuous variables, we can only use the relaxed version of the bounds negation: !(x <= u) -> x >= u */
1845 if( SCIPvarIsIntegral(var) )
1846 {
1847 assert(SCIPsetIsIntegral(set, bound));
1848 bound += (boundtype == SCIP_BOUNDTYPE_LOWER ? +1.0 : -1.0);
1849 }
1850
1851 SCIPsetDebugMsg(set, " -> apply global bound change: <%s> %s %g\n",
1852 SCIPvarGetName(var), boundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", bound);
1853
1854 SCIP_CALL( SCIPnodeAddBoundchg(tree->path[conflictset->validdepth], blkmem, set, stat, transprob, origprob, tree,
1855 reopt, lp, branchcand, eventqueue, cliquetable, var, bound, boundtype, FALSE) );
1856
1857 *success = TRUE;
1858 SCIP_CALL( updateStatistics(conflict, blkmem, set, stat, conflictset, insertdepth) );
1859 }
1860 else if( !conflictset->hasrelaxonlyvar )
1861 {
1862 /* sort conflict handlers by priority */
1864
1865 /* call conflict handlers to create a conflict constraint */
1866 for( h = 0; h < set->nconflicthdlrs; ++h )
1867 {
1868 SCIP_RESULT result;
1869
1870 assert(conflictset->conflicttype != SCIP_CONFTYPE_UNKNOWN);
1871
1872 SCIP_CALL( SCIPconflicthdlrExec(set->conflicthdlrs[h], set, tree->path[insertdepth],
1873 tree->path[conflictset->validdepth], conflictset->bdchginfos, conflictset->relaxedbds,
1874 conflictset->nbdchginfos, conflictset->conflicttype, conflictset->usescutoffbound, *success, &result) );
1875 if( result == SCIP_CONSADDED )
1876 {
1877 *success = TRUE;
1878 SCIP_CALL( updateStatistics(conflict, blkmem, set, stat, conflictset, insertdepth) );
1879 }
1880
1881 SCIPsetDebugMsg(set, " -> call conflict handler <%s> (prio=%d) to create conflict set with %d bounds returned result %d\n",
1882 SCIPconflicthdlrGetName(set->conflicthdlrs[h]), SCIPconflicthdlrGetPriority(set->conflicthdlrs[h]),
1883 conflictset->nbdchginfos, result);
1884 }
1885 }
1886 else
1887 {
1888 SCIPsetDebugMsg(set, " -> skip conflict set with relaxation-only variable\n");
1889 /* TODO would be nice to still create a constraint?, if we can make sure that we the constraint does not survive a restart */
1890 }
1891
1892 return SCIP_OKAY;
1893}
1894
1895/** calculates the maximal size of conflict sets to be used */
1897 SCIP_SET* set, /**< global SCIP settings */
1898 SCIP_PROB* prob /**< problem data */
1899 )
1900{
1901 int maxsize;
1902
1903 assert(set != NULL);
1904 assert(prob != NULL);
1905
1906 maxsize = (int)(set->conf_maxvarsfac * (prob->nvars - prob->ncontvars));
1907 maxsize = MAX(maxsize, set->conf_minmaxvars);
1908
1909 return maxsize;
1910}
1911
1912/** adds the collected conflict constraints to the corresponding nodes; the best set->conf_maxconss conflict constraints
1913 * are added to the node of their validdepth; additionally (if not yet added, and if repropagation is activated), the
1914 * conflict constraint that triggers the earliest repropagation is added to the node of its validdepth
1915 */
1917 SCIP_CONFLICT* conflict, /**< conflict analysis data */
1918 BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
1919 SCIP_SET* set, /**< global SCIP settings */
1920 SCIP_STAT* stat, /**< dynamic problem statistics */
1921 SCIP_PROB* transprob, /**< transformed problem */
1922 SCIP_PROB* origprob, /**< original problem */
1923 SCIP_TREE* tree, /**< branch and bound tree */
1924 SCIP_REOPT* reopt, /**< reoptimization data structure */
1925 SCIP_LP* lp, /**< current LP data */
1926 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1927 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1928 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
1929 )
1930{
1931 assert(conflict != NULL);
1932 assert(set != NULL);
1933 assert(stat != NULL);
1934 assert(transprob != NULL);
1935 assert(tree != NULL);
1936
1937 /* is there anything to do? */
1938 if( conflict->nconflictsets > 0 )
1939 {
1940 SCIP_CONFLICTSET* repropconflictset;
1941 int nconflictsetsused;
1942 int focusdepth;
1943#ifndef NDEBUG
1944 int currentdepth;
1945#endif
1946 int cutoffdepth;
1947 int repropdepth;
1948 int maxconflictsets;
1949 int maxsize;
1950 int i;
1951
1952 /* calculate the maximal number of conflict sets to accept, and the maximal size of each accepted conflict set */
1953 maxconflictsets = (set->conf_maxconss == -1 ? INT_MAX : set->conf_maxconss);
1954 maxsize = conflictCalcMaxsize(set, transprob);
1955
1956 focusdepth = SCIPtreeGetFocusDepth(tree);
1957#ifndef NDEBUG
1958 currentdepth = SCIPtreeGetCurrentDepth(tree);
1959 assert(focusdepth <= currentdepth);
1960 assert(currentdepth == tree->pathlen-1);
1961#endif
1962
1963 SCIPsetDebugMsg(set, "flushing %d conflict sets at focus depth %d (maxconflictsets: %d, maxsize: %d)\n",
1964 conflict->nconflictsets, focusdepth, maxconflictsets, maxsize);
1965
1966 /* mark the focus node to have produced conflict sets in the visualization output */
1967 SCIPvisualFoundConflict(stat->visual, stat, tree->path[focusdepth]);
1968
1969 /* insert the conflict sets at the corresponding nodes */
1970 nconflictsetsused = 0;
1971 cutoffdepth = INT_MAX;
1972 repropdepth = INT_MAX;
1973 repropconflictset = NULL;
1974 for( i = 0; i < conflict->nconflictsets && nconflictsetsused < maxconflictsets; ++i )
1975 {
1976 SCIP_CONFLICTSET* conflictset;
1977
1978 conflictset = conflict->conflictsets[i];
1979 assert(conflictset != NULL);
1980 assert(0 <= conflictset->validdepth);
1981 assert(conflictset->validdepth <= conflictset->insertdepth);
1982 assert(conflictset->insertdepth <= focusdepth);
1983 assert(conflictset->insertdepth <= conflictset->repropdepth);
1984 assert(conflictset->repropdepth <= currentdepth || conflictset->repropdepth == INT_MAX); /* INT_MAX for dive/probing/strong */
1985 assert(conflictset->conflictdepth <= currentdepth || conflictset->conflictdepth == INT_MAX); /* INT_MAX for dive/probing/strong */
1986
1987 /* ignore conflict sets that are only valid at a node that was already cut off */
1988 if( conflictset->insertdepth >= cutoffdepth )
1989 {
1990 SCIPsetDebugMsg(set, " -> ignoring conflict set with insertdepth %d >= cutoffdepth %d\n",
1991 conflictset->validdepth, cutoffdepth);
1992 continue;
1993 }
1994
1995 /* if no conflict bounds exist, the node and its sub tree in the conflict set's valid depth can be
1996 * cut off completely
1997 */
1998 if( conflictset->nbdchginfos == 0 )
1999 {
2000 SCIPsetDebugMsg(set, " -> empty conflict set in depth %d cuts off sub tree at depth %d\n",
2001 focusdepth, conflictset->validdepth);
2002
2003 SCIP_CALL( SCIPnodeCutoff(tree->path[conflictset->validdepth], set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
2004 cutoffdepth = conflictset->validdepth;
2005 continue;
2006 }
2007
2008 /* if the conflict set is too long, use the conflict set only if it decreases the repropagation depth */
2009 if( conflictset->nbdchginfos > maxsize )
2010 {
2011 SCIPsetDebugMsg(set, " -> conflict set is too long: %d > %d literals\n", conflictset->nbdchginfos, maxsize);
2012 if( set->conf_keepreprop && conflictset->repropagate && conflictset->repropdepth < repropdepth )
2013 {
2014 repropdepth = conflictset->repropdepth;
2015 repropconflictset = conflictset;
2016 }
2017 }
2018 else
2019 {
2020 SCIP_Bool success;
2021
2022 /* call conflict handlers to create a conflict constraint */
2023 SCIP_CALL( conflictAddConflictCons(conflict, blkmem, set, stat, transprob, origprob, tree, reopt, lp, \
2024 branchcand, eventqueue, cliquetable, conflictset, conflictset->insertdepth, &success) );
2025
2026 /* if no conflict bounds exist, the node and its sub tree in the conflict set's valid depth can be
2027 * cut off completely
2028 */
2029 if( conflictset->nbdchginfos == 0 )
2030 {
2031 assert(!success);
2032
2033 SCIPsetDebugMsg(set, " -> empty conflict set in depth %d cuts off sub tree at depth %d\n",
2034 focusdepth, conflictset->validdepth);
2035
2036 SCIP_CALL( SCIPnodeCutoff(tree->path[conflictset->validdepth], set, stat, tree, transprob, origprob, \
2037 reopt, lp, blkmem) );
2038 cutoffdepth = conflictset->validdepth;
2039 continue;
2040 }
2041
2042 if( success )
2043 {
2044 SCIPsetDebugMsg(set, " -> conflict set %d/%d added (cdpt:%d, fdpt:%d, insert:%d, valid:%d, conf:%d, reprop:%d, len:%d):\n",
2045 nconflictsetsused+1, maxconflictsets, SCIPtreeGetCurrentDepth(tree), SCIPtreeGetFocusDepth(tree),
2046 conflictset->insertdepth, conflictset->validdepth, conflictset->conflictdepth, conflictset->repropdepth,
2047 conflictset->nbdchginfos);
2048 SCIPdebug(conflictsetPrint(conflictset));
2049
2050 if( conflictset->repropagate && conflictset->repropdepth <= repropdepth )
2051 {
2052 repropdepth = conflictset->repropdepth;
2053 repropconflictset = NULL;
2054 }
2055 nconflictsetsused++;
2056 }
2057 }
2058 }
2059
2060 /* reactivate propagation on the first node where one of the new conflict sets trigger a deduction */
2061 if( set->conf_repropagate && repropdepth < cutoffdepth && repropdepth < tree->pathlen )
2062 {
2063 assert(0 <= repropdepth && repropdepth < tree->pathlen);
2064 assert((int) tree->path[repropdepth]->depth == repropdepth);
2065
2066 /* if the conflict constraint of smallest repropagation depth was not yet added, insert it now */
2067 if( repropconflictset != NULL )
2068 {
2069 SCIP_Bool success;
2070
2071 assert(repropconflictset->repropagate);
2072 assert(repropconflictset->repropdepth == repropdepth);
2073
2074 SCIP_CALL( conflictAddConflictCons(conflict, blkmem, set, stat, transprob, origprob, tree, reopt, lp, \
2075 branchcand, eventqueue, cliquetable, repropconflictset, repropdepth, &success) );
2076
2077 /* if no conflict bounds exist, the node and its sub tree in the conflict set's valid depth can be
2078 * cut off completely
2079 */
2080 if( repropconflictset->nbdchginfos == 0 )
2081 {
2082 assert(!success);
2083
2084 SCIPsetDebugMsg(set, " -> empty reprop conflict set in depth %d cuts off sub tree at depth %d\n",
2085 focusdepth, repropconflictset->validdepth);
2086
2087 SCIP_CALL( SCIPnodeCutoff(tree->path[repropconflictset->validdepth], set, stat, tree, transprob, \
2088 origprob, reopt, lp, blkmem) );
2089 }
2090
2091#ifdef SCIP_DEBUG
2092 if( success )
2093 {
2094 SCIPsetDebugMsg(set, " -> additional reprop conflict set added (cdpt:%d, fdpt:%d, insert:%d, valid:%d, conf:%d, reprop:%d, len:%d):\n",
2096 repropconflictset->insertdepth, repropconflictset->validdepth, repropconflictset->conflictdepth,
2097 repropconflictset->repropdepth, repropconflictset->nbdchginfos);
2098 SCIPdebug(conflictsetPrint(repropconflictset));
2099 }
2100#endif
2101 }
2102
2103 /* mark the node in the repropdepth to be propagated again */
2104 SCIPnodePropagateAgain(tree->path[repropdepth], set, stat, tree);
2105
2106 SCIPsetDebugMsg(set, "marked node %p in depth %d to be repropagated due to conflicts found in depth %d\n",
2107 (void*)tree->path[repropdepth], repropdepth, focusdepth);
2108 }
2109
2110 /* free the conflict store */
2111 for( i = 0; i < conflict->nconflictsets; ++i )
2112 {
2113 SCIPconflictsetFree(&conflict->conflictsets[i], blkmem);
2114 }
2115 conflict->nconflictsets = 0;
2116 }
2117
2118 /* free all temporarily created bound change information data */
2119 conflictFreeTmpBdchginfos(conflict, blkmem);
2120
2121 return SCIP_OKAY;
2122}
2123
2124/** resizes conflictsets array to be able to store at least num entries */
2125static
2127 SCIP_CONFLICT* conflict, /**< conflict analysis data */
2128 SCIP_SET* set, /**< global SCIP settings */
2129 int num /**< minimal number of slots in array */
2130 )
2131{
2132 assert(conflict != NULL);
2133 assert(set != NULL);
2134
2135 if( num > conflict->conflictsetssize )
2136 {
2137 int newsize;
2138
2139 newsize = SCIPsetCalcMemGrowSize(set, num);
2140 SCIP_ALLOC( BMSreallocMemoryArray(&conflict->conflictsets, newsize) );
2141 SCIP_ALLOC( BMSreallocMemoryArray(&conflict->conflictsetscores, newsize) );
2142 conflict->conflictsetssize = newsize;
2143 }
2144 assert(num <= conflict->conflictsetssize);
2145
2146 return SCIP_OKAY;
2147}
2148
2149/** inserts conflict set into sorted conflictsets array and deletes the conflict set pointer */
2150static
2152 SCIP_CONFLICT* conflict, /**< conflict analysis data */
2153 BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
2154 SCIP_SET* set, /**< global SCIP settings */
2155 SCIP_CONFLICTSET** conflictset /**< pointer to conflict set to insert */
2156 )
2157{
2158 SCIP_Real score;
2159 int pos;
2160 int i;
2161 int j;
2162
2163 assert(conflict != NULL);
2164 assert(set != NULL);
2165 assert(conflictset != NULL);
2166 assert(*conflictset != NULL);
2167 assert((*conflictset)->validdepth <= (*conflictset)->insertdepth);
2168 assert(set->conf_allowlocal || (*conflictset)->validdepth == 0);
2169
2170 /* calculate conflict and repropagation depth */
2171 conflictsetCalcConflictDepth(*conflictset);
2172
2173 /* if we apply repropagations, the conflict set should be inserted at most at its repropdepth */
2174 if( set->conf_repropagate )
2175 (*conflictset)->insertdepth = MIN((*conflictset)->insertdepth, (*conflictset)->repropdepth);
2176 else
2177 (*conflictset)->repropdepth = INT_MAX;
2178 assert((*conflictset)->insertdepth <= (*conflictset)->repropdepth);
2179
2180 SCIPsetDebugMsg(set, "inserting conflict set (valid: %d, insert: %d, conf: %d, reprop: %d):\n",
2181 (*conflictset)->validdepth, (*conflictset)->insertdepth, (*conflictset)->conflictdepth, (*conflictset)->repropdepth);
2182 SCIPdebug(conflictsetPrint(*conflictset));
2183
2184 /* get the score of the conflict set */
2185 score = conflictsetCalcScore(*conflictset, set);
2186
2187 /* check, if conflict set is redundant to a better conflict set */
2188 for( pos = 0; pos < conflict->nconflictsets && score < conflict->conflictsetscores[pos]; ++pos )
2189 {
2190 /* check if conflict set is redundant with respect to conflictsets[pos] */
2191 if( conflictsetIsRedundant(*conflictset, conflict->conflictsets[pos]) )
2192 {
2193 SCIPsetDebugMsg(set, " -> conflict set is redundant to: ");
2194 SCIPdebug(conflictsetPrint(conflict->conflictsets[pos]));
2195 SCIPconflictsetFree(conflictset, blkmem);
2196 return SCIP_OKAY;
2197 }
2198
2199 /**@todo like in sepastore.c: calculate overlap between conflictsets -> large overlap reduces score */
2200 }
2201
2202 /* insert conflictset into the sorted conflictsets array */
2203 SCIP_CALL( conflictEnsureConflictsetsMem(conflict, set, conflict->nconflictsets + 1) );
2204 for( i = conflict->nconflictsets; i > pos; --i )
2205 {
2206 assert(score >= conflict->conflictsetscores[i-1]);
2207 conflict->conflictsets[i] = conflict->conflictsets[i-1];
2208 conflict->conflictsetscores[i] = conflict->conflictsetscores[i-1];
2209 }
2210 conflict->conflictsets[pos] = *conflictset;
2211 conflict->conflictsetscores[pos] = score;
2212 conflict->nconflictsets++;
2213
2214 /* remove worse conflictsets that are redundant to the new conflictset */
2215 for( i = pos+1, j = pos+1; i < conflict->nconflictsets; ++i )
2216 {
2217 if( conflictsetIsRedundant(conflict->conflictsets[i], *conflictset) )
2218 {
2219 SCIPsetDebugMsg(set, " -> conflict set dominates: ");
2220 SCIPdebug(conflictsetPrint(conflict->conflictsets[i]));
2221 SCIPconflictsetFree(&conflict->conflictsets[i], blkmem);
2222 }
2223 else
2224 {
2225 assert(j <= i);
2226 conflict->conflictsets[j] = conflict->conflictsets[i];
2227 conflict->conflictsetscores[j] = conflict->conflictsetscores[i];
2228 j++;
2229 }
2230 }
2231 assert(j <= conflict->nconflictsets);
2232 conflict->nconflictsets = j;
2233
2234#if defined(SCIP_CONFGRAPH) || defined(SCIP_CONFGRAPH_DOT)
2235 confgraphMarkConflictset(*conflictset);
2236#endif
2237
2238 *conflictset = NULL; /* ownership of pointer is now in the conflictsets array */
2239
2240 return SCIP_OKAY;
2241}
2242
2243/** marks bound to be present in the current conflict and returns whether a bound which is at least as tight was already
2244 * member of the current conflict (i.e., the given bound change does not need to be added)
2245 */
2246static
2248 SCIP_CONFLICT* conflict, /**< conflict analysis data */
2249 SCIP_SET* set, /**< global SCIP settings */
2250 SCIP_BDCHGINFO* bdchginfo, /**< bound change to add to the conflict set */
2251 SCIP_Real relaxedbd /**< relaxed bound */
2252 )
2253{
2254 SCIP_VAR* var;
2255 SCIP_Real newbound;
2256
2257 assert(conflict != NULL);
2258
2259 var = SCIPbdchginfoGetVar(bdchginfo);
2260 newbound = SCIPbdchginfoGetNewbound(bdchginfo);
2261 assert(var != NULL);
2262
2263 switch( SCIPbdchginfoGetBoundtype(bdchginfo) )
2264 {
2266 /* check if the variables lower bound is already member of the conflict */
2267 if( var->conflictlbcount == conflict->count )
2268 {
2269 /* the variable is already member of the conflict; hence check if the new bound is redundant */
2270 if( var->conflictlb > newbound )
2271 {
2272 SCIPsetDebugMsg(set, "ignoring redundant bound change <%s> >= %g since a stronger lower bound exist <%s> >= %g\n",
2273 SCIPvarGetName(var), newbound, SCIPvarGetName(var), var->conflictlb);
2274 return TRUE;
2275 }
2276 else if( var->conflictlb == newbound ) /*lint !e777*/
2277 {
2278 SCIPsetDebugMsg(set, "ignoring redundant bound change <%s> >= %g since this lower bound is already present\n", SCIPvarGetName(var), newbound);
2279 SCIPsetDebugMsg(set, "adjust relaxed lower bound <%g> -> <%g>\n", var->conflictlb, relaxedbd);
2280 var->conflictrelaxedlb = MAX(var->conflictrelaxedlb, relaxedbd);
2281 return TRUE;
2282 }
2283 }
2284
2285 /* add the variable lower bound to the current conflict */
2286 var->conflictlbcount = conflict->count;
2287
2288 /* remember the lower bound and relaxed bound to allow only better/tighter lower bounds for that variables
2289 * w.r.t. this conflict
2290 */
2291 var->conflictlb = newbound;
2292 var->conflictrelaxedlb = relaxedbd;
2293
2294 return FALSE;
2295
2297 /* check if the variables upper bound is already member of the conflict */
2298 if( var->conflictubcount == conflict->count )
2299 {
2300 /* the variable is already member of the conflict; hence check if the new bound is redundant */
2301 if( var->conflictub < newbound )
2302 {
2303 SCIPsetDebugMsg(set, "ignoring redundant bound change <%s> <= %g since a stronger upper bound exist <%s> <= %g\n",
2304 SCIPvarGetName(var), newbound, SCIPvarGetName(var), var->conflictub);
2305 return TRUE;
2306 }
2307 else if( var->conflictub == newbound ) /*lint !e777*/
2308 {
2309 SCIPsetDebugMsg(set, "ignoring redundant bound change <%s> <= %g since this upper bound is already present\n", SCIPvarGetName(var), newbound);
2310 SCIPsetDebugMsg(set, "adjust relaxed upper bound <%g> -> <%g>\n", var->conflictub, relaxedbd);
2311 var->conflictrelaxedub = MIN(var->conflictrelaxedub, relaxedbd);
2312 return TRUE;
2313 }
2314 }
2315
2316 /* add the variable upper bound to the current conflict */
2317 var->conflictubcount = conflict->count;
2318
2319 /* remember the upper bound and relaxed bound to allow only better/tighter upper bounds for that variables
2320 * w.r.t. this conflict
2321 */
2322 var->conflictub = newbound;
2323 var->conflictrelaxedub = relaxedbd;
2324
2325 return FALSE;
2326
2327 default:
2328 SCIPerrorMessage("invalid bound type %d\n", SCIPbdchginfoGetBoundtype(bdchginfo));
2329 SCIPABORT();
2330 return FALSE; /*lint !e527*/
2331 }
2332}
2333
2334/** puts bound change into the current conflict set */
2335static
2337 SCIP_CONFLICT* conflict, /**< conflict analysis data */
2338 BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
2339 SCIP_SET* set, /**< global SCIP settings */
2340 SCIP_BDCHGINFO* bdchginfo, /**< bound change to add to the conflict set */
2341 SCIP_Real relaxedbd /**< relaxed bound */
2342 )
2343{
2344 assert(conflict != NULL);
2345 assert(!SCIPbdchginfoIsRedundant(bdchginfo));
2346
2347 /* check if the relaxed bound is really a relaxed bound */
2348 assert(SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_LOWER || SCIPsetIsGE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)));
2349 assert(SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_UPPER || SCIPsetIsLE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)));
2350
2351 SCIPsetDebugMsg(set, "putting bound change <%s> %s %g(%g) at depth %d to current conflict set\n",
2353 SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", SCIPbdchginfoGetNewbound(bdchginfo),
2354 relaxedbd, SCIPbdchginfoGetDepth(bdchginfo));
2355
2356 /* mark the bound to be member of the conflict and check if a bound which is at least as tight is already member of
2357 * the conflict
2358 */
2359 if( !conflictMarkBoundCheckPresence(conflict, set, bdchginfo, relaxedbd) )
2360 {
2361 /* add the bound change to the current conflict set */
2362 SCIP_CALL( conflictsetAddBound(conflict->conflictset, blkmem, set, bdchginfo, relaxedbd) );
2363
2364#if defined(SCIP_CONFGRAPH) || defined(SCIP_CONFGRAPH_DOT)
2365 if( bdchginfo != confgraphcurrentbdchginfo )
2366 confgraphAddBdchg(bdchginfo);
2367#endif
2368 }
2369#if defined(SCIP_CONFGRAPH) || defined(SCIP_CONFGRAPH_DOT)
2370 else
2371 confgraphLinkBdchg(bdchginfo);
2372#endif
2373
2374 return SCIP_OKAY;
2375}
2376
2377/** returns whether the negation of the given bound change would lead to a globally valid literal */
2378static
2380 SCIP_SET* set, /**< global SCIP settings */
2381 SCIP_BDCHGINFO* bdchginfo /**< bound change information */
2382 )
2383{
2384 SCIP_VAR* var;
2385 SCIP_BOUNDTYPE boundtype;
2387
2388 var = SCIPbdchginfoGetVar(bdchginfo);
2389 boundtype = SCIPbdchginfoGetBoundtype(bdchginfo);
2390 bound = SCIPbdchginfoGetNewbound(bdchginfo);
2391
2394 || (boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsFeasLE(set, bound, SCIPvarGetLbGlobal(var)))));
2395}
2396
2397/** adds given bound change information to the conflict candidate queue */
2398static
2400 SCIP_CONFLICT* conflict, /**< conflict analysis data */
2401 SCIP_SET* set, /**< global SCIP settings */
2402 SCIP_BDCHGINFO* bdchginfo, /**< bound change information */
2403 SCIP_Real relaxedbd /**< relaxed bound */
2404 )
2405{
2406 assert(conflict != NULL);
2407 assert(set != NULL);
2408 assert(bdchginfo != NULL);
2409 assert(!SCIPbdchginfoIsRedundant(bdchginfo));
2410
2411 /* check if the relaxed bound is really a relaxed bound */
2412 assert(SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_LOWER || SCIPsetIsGE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)));
2413 assert(SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_UPPER || SCIPsetIsLE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)));
2414
2415 /* mark the bound to be member of the conflict and check if a bound which is at least as tight is already member of
2416 * the conflict
2417 */
2418 if( !conflictMarkBoundCheckPresence(conflict, set, bdchginfo, relaxedbd) )
2419 {
2420 /* insert the bound change into the conflict queue */
2421 if( (!set->conf_preferbinary || SCIPvarIsBinary(SCIPbdchginfoGetVar(bdchginfo)))
2422 && !isBoundchgUseless(set, bdchginfo) )
2423 {
2424 SCIP_CALL( SCIPpqueueInsert(conflict->bdchgqueue, (void*)bdchginfo) );
2425 }
2426 else
2427 {
2428 SCIP_CALL( SCIPpqueueInsert(conflict->forcedbdchgqueue, (void*)bdchginfo) );
2429 }
2430
2431#if defined(SCIP_CONFGRAPH) || defined(SCIP_CONFGRAPH_DOT)
2432 confgraphAddBdchg(bdchginfo);
2433#endif
2434 }
2435#if defined(SCIP_CONFGRAPH) || defined(SCIP_CONFGRAPH_DOT)
2436 else
2437 confgraphLinkBdchg(bdchginfo);
2438#endif
2439
2440 return SCIP_OKAY;
2441}
2442
2443/** adds variable's bound to conflict candidate queue */
2444static
2446 SCIP_CONFLICT* conflict, /**< conflict analysis data */
2447 BMS_BLKMEM* blkmem, /**< block memory */
2448 SCIP_SET* set, /**< global SCIP settings */
2449 SCIP_STAT* stat, /**< dynamic problem statistics */
2450 SCIP_VAR* var, /**< problem variable */
2451 SCIP_BOUNDTYPE boundtype, /**< type of bound that was changed: lower or upper bound */
2452 SCIP_BDCHGINFO* bdchginfo, /**< bound change info, or NULL */
2453 SCIP_Real relaxedbd /**< relaxed bound */
2454 )
2455{
2456 assert(SCIPvarIsActive(var));
2457 assert(bdchginfo != NULL);
2458 assert(!SCIPbdchginfoIsRedundant(bdchginfo));
2459
2460 SCIPsetDebugMsg(set, " -> adding bound <%s> %s %.15g(%.15g) [status:%d, type:%d, depth:%d, pos:%d, reason:<%s>, info:%d] to candidates\n",
2461 SCIPvarGetName(var),
2462 boundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
2463 SCIPbdchginfoGetNewbound(bdchginfo), relaxedbd,
2465 SCIPbdchginfoGetDepth(bdchginfo), SCIPbdchginfoGetPos(bdchginfo),
2470 : "none")),
2472
2473 /* the local bound change may be resolved and has to be put on the candidate queue;
2474 * we even put bound changes without inference information on the queue in order to automatically
2475 * eliminate multiple insertions of the same bound change
2476 */
2477 assert(SCIPbdchginfoGetVar(bdchginfo) == var);
2478 assert(SCIPbdchginfoGetBoundtype(bdchginfo) == boundtype);
2479 assert(SCIPbdchginfoGetDepth(bdchginfo) >= 0);
2480 assert(SCIPbdchginfoGetPos(bdchginfo) >= 0);
2481
2482 /* the relaxed bound should be a relaxation */
2483 assert(boundtype == SCIP_BOUNDTYPE_LOWER ? SCIPsetIsLE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)) : SCIPsetIsGE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)));
2484
2485 /* the relaxed bound should be worse then the old bound of the bound change info */
2486 assert(boundtype == SCIP_BOUNDTYPE_LOWER ? SCIPsetIsGT(set, relaxedbd, SCIPbdchginfoGetOldbound(bdchginfo)) : SCIPsetIsLT(set, relaxedbd, SCIPbdchginfoGetOldbound(bdchginfo)));
2487
2488 /* put bound change information into priority queue */
2489 SCIP_CALL( conflictQueueBound(conflict, set, bdchginfo, relaxedbd) );
2490
2491 /* each variable which is add to the conflict graph gets an increase in the VSIDS
2492 *
2493 * @note That is different to the VSIDS preseted in the literature
2494 */
2495 SCIP_CALL( incVSIDS(var, blkmem, set, stat, boundtype, relaxedbd, set->conf_conflictgraphweight) );
2496
2497 return SCIP_OKAY;
2498}
2499
2500/** applies conflict analysis starting with given bound changes, that could not be undone during previous
2501 * infeasibility analysis
2502 */
2504 SCIP_CONFLICT* conflict, /**< conflict analysis data */
2505 BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
2506 SCIP_SET* set, /**< global SCIP settings */
2507 SCIP_STAT* stat, /**< problem statistics */
2508 SCIP_PROB* prob, /**< problem data */
2509 SCIP_TREE* tree, /**< branch and bound tree */
2510 SCIP_Bool diving, /**< are we in strong branching or diving mode? */
2511 int* lbchginfoposs, /**< positions of currently active lower bound change information in variables' arrays */
2512 int* ubchginfoposs, /**< positions of currently active upper bound change information in variables' arrays */
2513 int* nconss, /**< pointer to store the number of generated conflict constraints */
2514 int* nliterals, /**< pointer to store the number of literals in generated conflict constraints */
2515 int* nreconvconss, /**< pointer to store the number of generated reconvergence constraints */
2516 int* nreconvliterals /**< pointer to store the number of literals generated reconvergence constraints */
2517 )
2518{
2519 SCIP_VAR** vars;
2520 SCIP_VAR* var;
2521 SCIP_CONFTYPE conftype;
2522 SCIP_Bool usescutoffbound;
2523 int nvars;
2524 int v;
2525 int nbdchgs;
2526 int maxsize;
2527
2528 assert(prob != NULL);
2529 assert(lbchginfoposs != NULL);
2530 assert(ubchginfoposs != NULL);
2531 assert(nconss != NULL);
2532 assert(nliterals != NULL);
2533 assert(nreconvconss != NULL);
2534 assert(nreconvliterals != NULL);
2535
2536 *nconss = 0;
2537 *nliterals = 0;
2538 *nreconvconss = 0;
2539 *nreconvliterals = 0;
2540
2541 vars = prob->vars;
2542 nvars = prob->nvars;
2543 assert(nvars == 0 || vars != NULL);
2544
2545 maxsize = 2*conflictCalcMaxsize(set, prob);
2546
2547 /* initialize conflict data */
2548 conftype = conflict->conflictset->conflicttype;
2549 usescutoffbound = conflict->conflictset->usescutoffbound;
2550
2551 SCIP_CALL( SCIPconflictInit(conflict, set, stat, prob, conftype, usescutoffbound) );
2552
2553 conflict->conflictset->conflicttype = conftype;
2554 conflict->conflictset->usescutoffbound = usescutoffbound;
2555
2556 /* add remaining bound changes to conflict queue */
2557 SCIPsetDebugMsg(set, "initial conflict set after undoing bound changes:\n");
2558
2559 nbdchgs = 0;
2560 for( v = 0; v < nvars && nbdchgs < maxsize; ++v )
2561 {
2562 var = vars[v];
2563 assert(var != NULL);
2564 assert(var->nlbchginfos >= 0);
2565 assert(var->nubchginfos >= 0);
2566 assert(-1 <= lbchginfoposs[v] && lbchginfoposs[v] <= var->nlbchginfos);
2567 assert(-1 <= ubchginfoposs[v] && ubchginfoposs[v] <= var->nubchginfos);
2568
2569 if( lbchginfoposs[v] == var->nlbchginfos || ubchginfoposs[v] == var->nubchginfos )
2570 {
2571 SCIP_BDCHGINFO* bdchginfo;
2572 SCIP_Real relaxedbd;
2573
2574 /* the strong branching or diving bound stored in the column is responsible for the conflict:
2575 * it cannot be resolved and therefore has to be directly put into the conflict set
2576 */
2577 assert((lbchginfoposs[v] == var->nlbchginfos) != (ubchginfoposs[v] == var->nubchginfos)); /* only one can be tight in the dual! */
2578 assert(lbchginfoposs[v] < var->nlbchginfos || SCIPvarGetLbLP(var, set) > SCIPvarGetLbLocal(var));
2579 assert(ubchginfoposs[v] < var->nubchginfos || SCIPvarGetUbLP(var, set) < SCIPvarGetUbLocal(var));
2580
2581 /* create an artificial bound change information for the diving/strong branching bound change;
2582 * they are freed in the SCIPconflictFlushConss() call
2583 */
2584 if( lbchginfoposs[v] == var->nlbchginfos )
2585 {
2587 SCIPvarGetLbLocal(var), SCIPvarGetLbLP(var, set), &bdchginfo) );
2588 relaxedbd = SCIPvarGetLbLP(var, set);
2589 }
2590 else
2591 {
2593 SCIPvarGetUbLocal(var), SCIPvarGetUbLP(var, set), &bdchginfo) );
2594 relaxedbd = SCIPvarGetUbLP(var, set);
2595 }
2596
2597 /* put variable into the conflict set */
2598 SCIPsetDebugMsg(set, " force: <%s> %s %g [status: %d, type: %d, dive/strong]\n",
2599 SCIPvarGetName(var), lbchginfoposs[v] == var->nlbchginfos ? ">=" : "<=",
2600 lbchginfoposs[v] == var->nlbchginfos ? SCIPvarGetLbLP(var, set) : SCIPvarGetUbLP(var, set),
2601 SCIPvarGetStatus(var), SCIPvarGetType(var));
2602 SCIP_CALL( conflictAddConflictBound(conflict, blkmem, set, bdchginfo, relaxedbd) );
2603
2604 /* each variable which is add to the conflict graph gets an increase in the VSIDS
2605 *
2606 * @note That is different to the VSIDS preseted in the literature
2607 */
2608 SCIP_CALL( incVSIDS(var, blkmem, set, stat, SCIPbdchginfoGetBoundtype(bdchginfo), relaxedbd, set->conf_conflictgraphweight) );
2609 nbdchgs++;
2610 }
2611 else
2612 {
2613 /* put remaining bound changes into conflict candidate queue */
2614 if( lbchginfoposs[v] >= 0 )
2615 {
2616 SCIP_CALL( conflictAddBound(conflict, blkmem, set, stat, var, SCIP_BOUNDTYPE_LOWER, \
2617 &var->lbchginfos[lbchginfoposs[v]], SCIPbdchginfoGetNewbound(&var->lbchginfos[lbchginfoposs[v]])) );
2618 nbdchgs++;
2619 }
2620 if( ubchginfoposs[v] >= 0 )
2621 {
2622 assert(!SCIPbdchginfoIsRedundant(&var->ubchginfos[ubchginfoposs[v]]));
2623 SCIP_CALL( conflictAddBound(conflict, blkmem, set, stat, var, SCIP_BOUNDTYPE_UPPER, \
2624 &var->ubchginfos[ubchginfoposs[v]], SCIPbdchginfoGetNewbound(&var->ubchginfos[ubchginfoposs[v]])) );
2625 nbdchgs++;
2626 }
2627 }
2628 }
2629
2630 if( v == nvars )
2631 {
2632 /* analyze the conflict set, and create conflict constraints on success */
2633 SCIP_CALL( conflictAnalyze(conflict, blkmem, set, stat, prob, tree, diving, 0, FALSE, nconss, nliterals, \
2634 nreconvconss, nreconvliterals) );
2635 }
2636
2637 return SCIP_OKAY;
2638}
2639
2640/** check if the bound change info (which is the potential next candidate which is queued) is valid for the current
2641 * conflict analysis; a bound change info can get invalid if after this one was added to the queue, a weaker bound
2642 * change was added to the queue (due the bound widening idea) which immediately makes this bound change redundant; due
2643 * to the priority we did not removed that bound change info since that cost O(log(n)); hence we have to skip/ignore it
2644 * now
2645 *
2646 * The following situations can occur before for example the bound change info (x >= 3) is potentially popped from the
2647 * queue.
2648 *
2649 * Postcondition: the reason why (x >= 3) was queued is that at this time point no lower bound of x was involved yet in
2650 * the current conflict or the lower bound which was involved until then was stronger, e.g., (x >= 2).
2651 *
2652 * 1) during the time until (x >= 3) gets potentially popped no weaker lower bound was added to the queue, in that case
2653 * the conflictlbcount is valid and conflictlb is 3; that is (var->conflictlbcount == conflict->count &&
2654 * var->conflictlb == 3)
2655 *
2656 * 2) a weaker bound change info gets queued (e.g., x >= 4); this bound change is popped before (x >= 3) since it has
2657 * higher priority (which is the time stamp of the bound change info and (x >= 4) has to be done after (x >= 3)
2658 * during propagation or branching)
2659 *
2660 * a) if (x >= 4) is popped and added to the conflict set the conflictlbcount is still valid and conflictlb is at
2661 * most 4; that is (var->conflictlbcount == conflict->count && var->conflictlb >= 4); it follows that any bound
2662 * change info which is stronger than (x >= 4) gets ignored (for example x >= 2)
2663 *
2664 * b) if (x >= 4) is popped and resolved without introducing a new lower bound on x until (x >= 3) is a potentially
2665 * candidate the conflictlbcount indicates that bound change is currently not present; that is
2666 * (var->conflictlbcount != conflict->count)
2667 *
2668 * c) if (x >= 4) is popped and resolved and a new lower bound on x (e.g., x >= 2) is introduced until (x >= 3) is
2669 * pooped, the conflictlbcount indicates that bound change is currently present; that is (var->conflictlbcount ==
2670 * conflict->count); however the (x >= 3) only has be explained if conflictlb matches that one; that is
2671 * (var->conflictlb == bdchginfo->newbound); otherwise it redundant/invalid.
2672 */
2673static
2675 SCIP_CONFLICT* conflict, /**< conflict analysis data */
2676 SCIP_BDCHGINFO* bdchginfo /**< bound change information */
2677 )
2678{
2679 SCIP_VAR* var;
2680
2681 assert(bdchginfo != NULL);
2682
2683 var = SCIPbdchginfoGetVar(bdchginfo);
2684 assert(var != NULL);
2685
2686 /* the bound change info of a binary (domained) variable can never be invalid since the concepts of relaxed bounds
2687 * and bound widening do not make sense for these type of variables
2688 */
2689 if( SCIPvarIsBinary(var) )
2690 return FALSE;
2691
2692 /* check if the bdchginfo is invalid since a tight/weaker bound change was already explained */
2694 {
2695 if( var->conflictlbcount != conflict->count || var->conflictlb != SCIPbdchginfoGetNewbound(bdchginfo) ) /*lint !e777*/
2696 {
2697 assert(!SCIPvarIsBinary(var));
2698 return TRUE;
2699 }
2700 }
2701 else
2702 {
2703 assert(SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_UPPER);
2704
2705 if( var->conflictubcount != conflict->count || var->conflictub != SCIPbdchginfoGetNewbound(bdchginfo) ) /*lint !e777*/
2706 {
2707 assert(!SCIPvarIsBinary(var));
2708 return TRUE;
2709 }
2710 }
2711
2712 return FALSE;
2713}
2714
2715/** adds given bound changes to a conflict set */
2716static
2718 SCIP_CONFLICT* conflict, /**< conflict analysis data */
2719 SCIP_CONFLICTSET* conflictset, /**< conflict set */
2720 BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
2721 SCIP_SET* set, /**< global SCIP settings */
2722 SCIP_BDCHGINFO** bdchginfos, /**< bound changes to add to the conflict set */
2723 int nbdchginfos /**< number of bound changes to add */
2724 )
2725{
2726 SCIP_BDCHGINFO** confbdchginfos;
2727 SCIP_BDCHGINFO* bdchginfo;
2728 SCIP_Real* confrelaxedbds;
2729 int* confsortvals;
2730 int confnbdchginfos;
2731 int idx;
2732 int sortval;
2733 int i;
2734 SCIP_BOUNDTYPE boundtype;
2735
2736 assert(conflict != NULL);
2737 assert(conflictset != NULL);
2738 assert(blkmem != NULL);
2739 assert(set != NULL);
2740 assert(bdchginfos != NULL || nbdchginfos == 0);
2741
2742 /* nothing to add */
2743 if( nbdchginfos == 0 )
2744 return SCIP_OKAY;
2745
2746 assert(bdchginfos != NULL);
2747
2748 /* only one element to add, use the single insertion method */
2749 if( nbdchginfos == 1 )
2750 {
2751 bdchginfo = bdchginfos[0];
2752 assert(bdchginfo != NULL);
2753
2754 if( !bdchginfoIsInvalid(conflict, bdchginfo) )
2755 {
2756 SCIP_CALL( conflictsetAddBound(conflictset, blkmem, set, bdchginfo, SCIPbdchginfoGetRelaxedBound(bdchginfo)) );
2757 }
2758 else
2759 {
2760 SCIPsetDebugMsg(set, "-> bound change info [%d:<%s> %s %g] is invalid -> ignore it\n", SCIPbdchginfoGetDepth(bdchginfo),
2762 SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
2763 SCIPbdchginfoGetNewbound(bdchginfo));
2764 }
2765
2766 return SCIP_OKAY;
2767 }
2768
2769 confnbdchginfos = conflictset->nbdchginfos;
2770
2771 /* allocate memory for additional element */
2772 SCIP_CALL( conflictsetEnsureBdchginfosMem(conflictset, blkmem, set, confnbdchginfos + nbdchginfos) );
2773
2774 confbdchginfos = conflictset->bdchginfos;
2775 confrelaxedbds = conflictset->relaxedbds;
2776 confsortvals = conflictset->sortvals;
2777
2778 assert(SCIP_BOUNDTYPE_LOWER == FALSE); /*lint !e641 !e506*/
2779 assert(SCIP_BOUNDTYPE_UPPER == TRUE); /*lint !e641 !e506*/
2780
2781 for( i = 0; i < nbdchginfos; ++i )
2782 {
2783 bdchginfo = bdchginfos[i];
2784 assert(bdchginfo != NULL);
2785
2786 /* add only valid bound change infos */
2787 if( !bdchginfoIsInvalid(conflict, bdchginfo) )
2788 {
2789 /* calculate sorting value */
2790 boundtype = SCIPbdchginfoGetBoundtype(bdchginfo);
2791 assert(SCIPbdchginfoGetVar(bdchginfo) != NULL);
2792
2793 idx = SCIPvarGetIndex(SCIPbdchginfoGetVar(bdchginfo));
2794 assert(idx < INT_MAX/2);
2795
2796 assert((int)boundtype == 0 || (int)boundtype == 1);
2797 sortval = 2*idx + (int)boundtype; /* first sorting criteria: variable index, second criteria: boundtype */
2798
2799 /* add new element */
2800 confbdchginfos[confnbdchginfos] = bdchginfo;
2801 confrelaxedbds[confnbdchginfos] = SCIPbdchginfoGetRelaxedBound(bdchginfo);
2802 confsortvals[confnbdchginfos] = sortval;
2803 ++confnbdchginfos;
2804
2806 conflictset->hasrelaxonlyvar = TRUE;
2807 }
2808 else
2809 {
2810 SCIPsetDebugMsg(set, "-> bound change info [%d:<%s> %s %g] is invalid -> ignore it\n", SCIPbdchginfoGetDepth(bdchginfo),
2812 SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
2813 SCIPbdchginfoGetNewbound(bdchginfo));
2814 }
2815 }
2816 assert(confnbdchginfos <= conflictset->nbdchginfos + nbdchginfos);
2817
2818 /* sort and merge the new conflict set */
2819 if( confnbdchginfos > conflictset->nbdchginfos )
2820 {
2821 int k = 0;
2822
2823 /* sort array */
2824 SCIPsortIntPtrReal(confsortvals, (void**)confbdchginfos, confrelaxedbds, confnbdchginfos);
2825
2826 i = 1;
2827 /* merge multiple bound changes */
2828 while( i < confnbdchginfos )
2829 {
2830 assert(i > k);
2831
2832 /* is this a multiple bound change */
2833 if( confsortvals[k] == confsortvals[i] )
2834 {
2835 if( SCIPbdchginfoIsTighter(confbdchginfos[k], confbdchginfos[i]) )
2836 ++i;
2837 else if( SCIPbdchginfoIsTighter(confbdchginfos[i], confbdchginfos[k]) )
2838 {
2839 /* replace worse bound change info by tighter bound change info */
2840 confbdchginfos[k] = confbdchginfos[i];
2841 confrelaxedbds[k] = confrelaxedbds[i];
2842 confsortvals[k] = confsortvals[i];
2843 ++i;
2844 }
2845 else
2846 {
2847 assert(confsortvals[k] == confsortvals[i]);
2848
2849 /* both bound change are equivalent; hence, keep the worse relaxed bound and remove one of them */
2850 confrelaxedbds[k] = (confsortvals[k] % 2 == 0) ? MAX(confrelaxedbds[k], confrelaxedbds[i]) : MIN(confrelaxedbds[k], confrelaxedbds[i]);
2851 ++i;
2852 }
2853 }
2854 else
2855 {
2856 /* all bound change infos must be valid */
2857 assert(!bdchginfoIsInvalid(conflict, confbdchginfos[k]));
2858
2859 ++k;
2860 /* move next comparison element to the correct position */
2861 if( k != i )
2862 {
2863 confbdchginfos[k] = confbdchginfos[i];
2864 confrelaxedbds[k] = confrelaxedbds[i];
2865 confsortvals[k] = confsortvals[i];
2866 }
2867 ++i;
2868 }
2869 }
2870 /* last bound change infos must also be valid */
2871 assert(!bdchginfoIsInvalid(conflict, confbdchginfos[k]));
2872 /* the number of bound change infos cannot be decreased, it would mean that the conflict set was not merged
2873 * before
2874 */
2875 assert(conflictset->nbdchginfos <= k + 1 );
2876 assert(k + 1 <= confnbdchginfos);
2877
2878 conflictset->nbdchginfos = k + 1;
2879 }
2880
2881 return SCIP_OKAY;
2882}
2883
2884/** removes and returns next conflict analysis candidate from the candidate queue */
2885static
2887 SCIP_CONFLICT* conflict /**< conflict analysis data */
2888 )
2889{
2890 SCIP_BDCHGINFO* bdchginfo;
2891 SCIP_VAR* var;
2892
2893 assert(conflict != NULL);
2894
2895 if( SCIPpqueueNElems(conflict->forcedbdchgqueue) > 0 )
2896 bdchginfo = (SCIP_BDCHGINFO*)(SCIPpqueueRemove(conflict->forcedbdchgqueue));
2897 else
2898 bdchginfo = (SCIP_BDCHGINFO*)(SCIPpqueueRemove(conflict->bdchgqueue));
2899
2900 assert(!SCIPbdchginfoIsRedundant(bdchginfo));
2901
2902 /* if we have a candidate this one should be valid for the current conflict analysis */
2903 assert(!bdchginfoIsInvalid(conflict, bdchginfo));
2904
2905 /* mark the bound change to be no longer in the conflict (it will be either added again to the conflict set or
2906 * replaced by resolving, which might add a weaker change on the same bound to the queue)
2907 */
2908 var = SCIPbdchginfoGetVar(bdchginfo);
2910 {
2911 var->conflictlbcount = 0;
2913 }
2914 else
2915 {
2916 assert(SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_UPPER);
2917 var->conflictubcount = 0;
2919 }
2920
2921#if defined(SCIP_CONFGRAPH) || defined(SCIP_CONFGRAPH_DOT)
2922 confgraphSetCurrentBdchg(bdchginfo);
2923#endif
2924
2925 return bdchginfo;
2926}
2927
2928/** returns next conflict analysis candidate from the candidate queue without removing it */
2929static
2931 SCIP_CONFLICT* conflict /**< conflict analysis data */
2932 )
2933{
2934 SCIP_BDCHGINFO* bdchginfo;
2935
2936 assert(conflict != NULL);
2937
2938 if( SCIPpqueueNElems(conflict->forcedbdchgqueue) > 0 )
2939 {
2940 /* get next potential candidate */
2941 bdchginfo = (SCIP_BDCHGINFO*)(SCIPpqueueFirst(conflict->forcedbdchgqueue));
2942
2943 /* check if this candidate is valid */
2944 if( bdchginfoIsInvalid(conflict, bdchginfo) )
2945 {
2946 SCIPdebugMessage("bound change info [%d:<%s> %s %g] is invalid -> pop it from the force queue\n", SCIPbdchginfoGetDepth(bdchginfo),
2948 SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
2949 SCIPbdchginfoGetNewbound(bdchginfo));
2950
2951 /* pop the invalid bound change info from the queue */
2952 (void)(SCIPpqueueRemove(conflict->forcedbdchgqueue));
2953
2954 /* call method recursively to get next conflict analysis candidate */
2955 bdchginfo = conflictFirstCand(conflict);
2956 }
2957 }
2958 else
2959 {
2960 bdchginfo = (SCIP_BDCHGINFO*)(SCIPpqueueFirst(conflict->bdchgqueue));
2961
2962 /* check if this candidate is valid */
2963 if( bdchginfo != NULL && bdchginfoIsInvalid(conflict, bdchginfo) )
2964 {
2965 SCIPdebugMessage("bound change info [%d:<%s> %s %g] is invalid -> pop it from the queue\n", SCIPbdchginfoGetDepth(bdchginfo),
2967 SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
2968 SCIPbdchginfoGetNewbound(bdchginfo));
2969
2970 /* pop the invalid bound change info from the queue */
2971 (void)(SCIPpqueueRemove(conflict->bdchgqueue));
2972
2973 /* call method recursively to get next conflict analysis candidate */
2974 bdchginfo = conflictFirstCand(conflict);
2975 }
2976 }
2977 assert(bdchginfo == NULL || !SCIPbdchginfoIsRedundant(bdchginfo));
2978
2979 return bdchginfo;
2980}
2981
2982/** adds the current conflict set (extended by all remaining bound changes in the queue) to the pool of conflict sets */
2983static
2985 SCIP_CONFLICT* conflict, /**< conflict analysis data */
2986 BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
2987 SCIP_SET* set, /**< global SCIP settings */
2988 SCIP_STAT* stat, /**< dynamic problem statistics */
2989 SCIP_TREE* tree, /**< branch and bound tree */
2990 int validdepth, /**< minimal depth level at which the conflict set is valid */
2991 SCIP_Bool diving, /**< are we in strong branching or diving mode? */
2992 SCIP_Bool repropagate, /**< should the constraint trigger a repropagation? */
2993 SCIP_Bool* success, /**< pointer to store whether the conflict set is valid */
2994 int* nliterals /**< pointer to store the number of literals in the generated conflictset */
2995 )
2996{
2997 SCIP_CONFLICTSET* conflictset;
2998 SCIP_BDCHGINFO** bdchginfos;
2999 int nbdchginfos;
3000 int currentdepth;
3001 int focusdepth;
3002
3003 assert(conflict != NULL);
3004 assert(conflict->conflictset != NULL);
3005 assert(set != NULL);
3006 assert(stat != NULL);
3007 assert(tree != NULL);
3008 assert(success != NULL);
3009 assert(nliterals != NULL);
3010 assert(SCIPpqueueNElems(conflict->forcedbdchgqueue) == 0);
3011
3012 *success = FALSE;
3013 *nliterals = 0;
3014
3015 /* check, whether local conflicts are allowed */
3016 validdepth = MAX(validdepth, conflict->conflictset->validdepth);
3017 if( !set->conf_allowlocal && validdepth > 0 )
3018 return SCIP_OKAY;
3019
3020 focusdepth = SCIPtreeGetFocusDepth(tree);
3021 currentdepth = SCIPtreeGetCurrentDepth(tree);
3022 assert(currentdepth == tree->pathlen-1);
3023 assert(focusdepth <= currentdepth);
3024 assert(0 <= conflict->conflictset->validdepth && conflict->conflictset->validdepth <= currentdepth);
3025 assert(0 <= validdepth && validdepth <= currentdepth);
3026
3027 /* get the elements of the bound change queue */
3028 bdchginfos = (SCIP_BDCHGINFO**)SCIPpqueueElems(conflict->bdchgqueue);
3029 nbdchginfos = SCIPpqueueNElems(conflict->bdchgqueue);
3030
3031 /* create a copy of the current conflict set, allocating memory for the additional elements of the queue */
3032 SCIP_CALL( conflictsetCopy(&conflictset, blkmem, conflict->conflictset, nbdchginfos) );
3033 conflictset->validdepth = validdepth;
3034 conflictset->repropagate = repropagate;
3035
3036 /* add the valid queue elements to the conflict set */
3037 SCIPsetDebugMsg(set, "adding %d variables from the queue as temporary conflict variables\n", nbdchginfos);
3038 SCIP_CALL( conflictsetAddBounds(conflict, conflictset, blkmem, set, bdchginfos, nbdchginfos) );
3039
3040 /* calculate the depth, at which the conflictset should be inserted */
3041 SCIP_CALL( conflictsetCalcInsertDepth(conflictset, set, tree) );
3042 assert(conflictset->validdepth <= conflictset->insertdepth && conflictset->insertdepth <= currentdepth);
3043 SCIPsetDebugMsg(set, " -> conflict with %d literals found at depth %d is active in depth %d and valid in depth %d\n",
3044 conflictset->nbdchginfos, currentdepth, conflictset->insertdepth, conflictset->validdepth);
3045
3046 /* if all branching variables are in the conflict set, the conflict set is of no use;
3047 * don't use conflict sets that are only valid in the probing path but not in the problem tree
3048 */
3049 if( (diving || conflictset->insertdepth < currentdepth) && conflictset->insertdepth <= focusdepth )
3050 {
3051 /* if the conflict should not be located only in the subtree where it is useful, put it to its valid depth level */
3052 if( !set->conf_settlelocal )
3053 conflictset->insertdepth = conflictset->validdepth;
3054
3055 *nliterals = conflictset->nbdchginfos;
3056 SCIPsetDebugMsg(set, " -> final conflict set has %d literals\n", *nliterals);
3057
3058 /* check conflict set on debugging solution */
3059 SCIP_CALL( SCIPdebugCheckConflict(blkmem, set, tree->path[validdepth], \
3060 conflictset->bdchginfos, conflictset->relaxedbds, conflictset->nbdchginfos) ); /*lint !e506 !e774*/
3061
3062 /* move conflictset to the conflictset storage */
3063 SCIP_CALL( conflictInsertConflictset(conflict, blkmem, set, &conflictset) );
3064 *success = TRUE;
3065 }
3066 else
3067 {
3068 /* free the temporary conflict set */
3069 SCIPconflictsetFree(&conflictset, blkmem);
3070 }
3071
3072 return SCIP_OKAY;
3073}
3074
3075/** tries to resolve given bound change
3076 * - resolutions on local constraints are only applied, if the constraint is valid at the
3077 * current minimal valid depth level, because this depth level is the topmost level to add the conflict
3078 * constraint to anyways
3079 *
3080 * @note it is sufficient to explain the relaxed bound change
3081 */
3082static
3084 SCIP_CONFLICT* conflict, /**< conflict analysis data */
3085 SCIP_SET* set, /**< global SCIP settings */
3086 SCIP_BDCHGINFO* bdchginfo, /**< bound change to resolve */
3087 SCIP_Real relaxedbd, /**< the relaxed bound */
3088 int validdepth, /**< minimal depth level at which the conflict is valid */
3089 SCIP_Bool* resolved /**< pointer to store whether the bound change was resolved */
3090 )
3091{
3092 SCIP_VAR* actvar;
3093 SCIP_CONS* infercons;
3094 SCIP_PROP* inferprop;
3095 SCIP_RESULT result;
3096
3097#ifndef NDEBUG
3098 int nforcedbdchgqueue;
3099 int nbdchgqueue;
3100
3101 /* store the current size of the conflict queues */
3102 assert(conflict != NULL);
3103 nforcedbdchgqueue = SCIPpqueueNElems(conflict->forcedbdchgqueue);
3104 nbdchgqueue = SCIPpqueueNElems(conflict->bdchgqueue);
3105#else
3106 assert(conflict != NULL);
3107#endif
3108
3109 assert(resolved != NULL);
3110 assert(!SCIPbdchginfoIsRedundant(bdchginfo));
3111
3112 *resolved = FALSE;
3113
3114 actvar = SCIPbdchginfoGetVar(bdchginfo);
3115 assert(actvar != NULL);
3116 assert(SCIPvarIsActive(actvar));
3117
3118#ifdef SCIP_DEBUG
3119 {
3120 int i;
3121 SCIPsetDebugMsg(set, "processing next conflicting bound (depth: %d, valid depth: %d, bdchgtype: %s [%s], vartype: %d): [<%s> %s %g(%g)]\n",
3122 SCIPbdchginfoGetDepth(bdchginfo), validdepth,
3124 : SCIPbdchginfoGetChgtype(bdchginfo) == SCIP_BOUNDCHGTYPE_CONSINFER ? "cons" : "prop",
3128 : SCIPbdchginfoGetInferProp(bdchginfo) == NULL ? "-"
3130 SCIPvarGetType(actvar), SCIPvarGetName(actvar),
3131 SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
3132 SCIPbdchginfoGetNewbound(bdchginfo), relaxedbd);
3133 SCIPsetDebugMsg(set, " - conflict set :");
3134
3135 for( i = 0; i < conflict->conflictset->nbdchginfos; ++i )
3136 {
3137 SCIPsetDebugMsgPrint(set, " [%d:<%s> %s %g(%g)]", SCIPbdchginfoGetDepth(conflict->conflictset->bdchginfos[i]),
3141 }
3143 SCIPsetDebugMsg(set, " - forced candidates :");
3144
3145 for( i = 0; i < SCIPpqueueNElems(conflict->forcedbdchgqueue); ++i )
3146 {
3149 bdchginfoIsInvalid(conflict, info) ? "<!>" : SCIPbdchginfoGetBoundtype(info) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
3151 }
3153 SCIPsetDebugMsg(set, " - optional candidates:");
3154
3155 for( i = 0; i < SCIPpqueueNElems(conflict->bdchgqueue); ++i )
3156 {
3157 SCIP_BDCHGINFO* info = (SCIP_BDCHGINFO*)(SCIPpqueueElems(conflict->bdchgqueue)[i]);
3159 bdchginfoIsInvalid(conflict, info) ? "<!>" : SCIPbdchginfoGetBoundtype(info) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
3161 }
3163 }
3164#endif
3165
3166 /* check, if the bound change can and should be resolved:
3167 * - resolutions on local constraints should only be applied, if the constraint is valid at the
3168 * current minimal valid depth level (which is initialized with the valid depth level of the initial
3169 * conflict set), because this depth level is the topmost level to add the conflict constraint to anyways
3170 */
3171 switch( SCIPbdchginfoGetChgtype(bdchginfo) )
3172 {
3174 infercons = SCIPbdchginfoGetInferCons(bdchginfo);
3175 assert(infercons != NULL);
3176
3177 if( SCIPconsIsGlobal(infercons) || SCIPconsGetValidDepth(infercons) <= validdepth )
3178 {
3179 SCIP_VAR* infervar;
3180 int inferinfo;
3181 SCIP_BOUNDTYPE inferboundtype;
3182 SCIP_BDCHGIDX* bdchgidx;
3183
3184 /* resolve bound change by asking the constraint that inferred the bound to put all bounds that were
3185 * the reasons for the conflicting bound change on the priority queue
3186 */
3187 infervar = SCIPbdchginfoGetInferVar(bdchginfo);
3188 inferinfo = SCIPbdchginfoGetInferInfo(bdchginfo);
3189 inferboundtype = SCIPbdchginfoGetInferBoundtype(bdchginfo);
3190 bdchgidx = SCIPbdchginfoGetIdx(bdchginfo);
3191 assert(infervar != NULL);
3192
3193 SCIPsetDebugMsg(set, "resolving bound <%s> %s %g(%g) [status:%d, type:%d, depth:%d, pos:%d]: <%s> %s %g [cons:<%s>(%s), info:%d]\n",
3194 SCIPvarGetName(actvar),
3195 SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
3196 SCIPbdchginfoGetNewbound(bdchginfo), relaxedbd,
3197 SCIPvarGetStatus(actvar), SCIPvarGetType(actvar),
3198 SCIPbdchginfoGetDepth(bdchginfo), SCIPbdchginfoGetPos(bdchginfo),
3199 SCIPvarGetName(infervar),
3200 inferboundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
3201 SCIPgetVarBdAtIndex(set->scip, infervar, inferboundtype, bdchgidx, TRUE),
3202 SCIPconsGetName(infercons),
3203 SCIPconsIsGlobal(infercons) ? "global" : "local",
3204 inferinfo);
3205
3206 /* in case the inference variables is not an active variables, we need to transform the relaxed bound */
3207 if( actvar != infervar )
3208 {
3209 SCIP_VAR* var;
3210 SCIP_Real scalar;
3211 SCIP_Real constant;
3212
3215 || (SCIPvarGetStatus(infervar) == SCIP_VARSTATUS_MULTAGGR && SCIPvarGetMultaggrNVars(infervar) == 1));
3216
3217 scalar = 1.0;
3218 constant = 0.0;
3219
3220 var = infervar;
3221
3222 /* transform given variable to active variable */
3223 SCIP_CALL( SCIPvarGetProbvarSum(&var, set, &scalar, &constant) );
3224 assert(var == actvar);
3225
3226 relaxedbd *= scalar;
3227 relaxedbd += constant;
3228 }
3229
3230 SCIP_CALL( SCIPconsResolvePropagation(infercons, set, infervar, inferinfo, inferboundtype, bdchgidx, relaxedbd, &result) );
3231 *resolved = (result == SCIP_SUCCESS);
3232 }
3233 break;
3234
3236 inferprop = SCIPbdchginfoGetInferProp(bdchginfo);
3237 if( inferprop != NULL )
3238 {
3239 SCIP_VAR* infervar;
3240 int inferinfo;
3241 SCIP_BOUNDTYPE inferboundtype;
3242 SCIP_BDCHGIDX* bdchgidx;
3243
3244 /* resolve bound change by asking the propagator that inferred the bound to put all bounds that were
3245 * the reasons for the conflicting bound change on the priority queue
3246 */
3247 infervar = SCIPbdchginfoGetInferVar(bdchginfo);
3248 inferinfo = SCIPbdchginfoGetInferInfo(bdchginfo);
3249 inferboundtype = SCIPbdchginfoGetInferBoundtype(bdchginfo);
3250 bdchgidx = SCIPbdchginfoGetIdx(bdchginfo);
3251 assert(infervar != NULL);
3252
3253 SCIPsetDebugMsg(set, "resolving bound <%s> %s %g(%g) [status:%d, depth:%d, pos:%d]: <%s> %s %g [prop:<%s>, info:%d]\n",
3254 SCIPvarGetName(actvar),
3255 SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
3256 SCIPbdchginfoGetNewbound(bdchginfo), relaxedbd,
3257 SCIPvarGetStatus(actvar), SCIPbdchginfoGetDepth(bdchginfo), SCIPbdchginfoGetPos(bdchginfo),
3258 SCIPvarGetName(infervar),
3259 inferboundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
3260 SCIPgetVarBdAtIndex(set->scip, infervar, inferboundtype, bdchgidx, TRUE),
3261 SCIPpropGetName(inferprop), inferinfo);
3262
3263 SCIP_CALL( SCIPpropResolvePropagation(inferprop, set, infervar, inferinfo, inferboundtype, bdchgidx, relaxedbd, &result) );
3264 *resolved = (result == SCIP_SUCCESS);
3265 }
3266 break;
3267
3269 assert(!(*resolved));
3270 break;
3271
3272 default:
3273 SCIPerrorMessage("invalid bound change type <%d>\n", SCIPbdchginfoGetChgtype(bdchginfo));
3274 return SCIP_INVALIDDATA;
3275 }
3276
3277 SCIPsetDebugMsg(set, "resolving status: %u\n", *resolved);
3278
3279#ifndef NDEBUG
3280 /* subtract the size of the conflicq queues */
3281 nforcedbdchgqueue -= SCIPpqueueNElems(conflict->forcedbdchgqueue);
3282 nbdchgqueue -= SCIPpqueueNElems(conflict->bdchgqueue);
3283
3284 /* in case the bound change was not resolved, the conflict queues should have the same size (contents) */
3285 assert((*resolved) || (nforcedbdchgqueue == 0 && nbdchgqueue == 0));
3286#endif
3287
3288 return SCIP_OKAY;
3289}
3290
3291/** clears the conflict queue and the current conflict set */
3292static
3294 SCIP_CONFLICT* conflict /**< conflict analysis data */
3295 )
3296{
3297 assert(conflict != NULL);
3298
3299 SCIPpqueueClear(conflict->bdchgqueue);
3301 conflictsetClear(conflict->conflictset);
3302}
3303
3304/** initializes the propagation conflict analysis by clearing the conflict candidate queue */
3306 SCIP_CONFLICT* conflict, /**< conflict analysis data */
3307 SCIP_SET* set, /**< global SCIP settings */
3308 SCIP_STAT* stat, /**< problem statistics */
3309 SCIP_PROB* prob, /**< problem data */
3310 SCIP_CONFTYPE conftype, /**< type of the conflict */
3311 SCIP_Bool usescutoffbound /**< depends the conflict on a cutoff bound? */
3312 )
3313{
3314 assert(conflict != NULL);
3315 assert(set != NULL);
3316 assert(stat != NULL);
3317 assert(prob != NULL);
3318
3319 SCIPsetDebugMsg(set, "initializing conflict analysis\n");
3320
3321 /* clear the conflict candidate queue and the conflict set */
3322 conflictClear(conflict);
3323
3324 /* set conflict type */
3325 assert(conftype == SCIP_CONFTYPE_BNDEXCEEDING || conftype == SCIP_CONFTYPE_INFEASLP
3326 || conftype == SCIP_CONFTYPE_PROPAGATION);
3327 conflict->conflictset->conflicttype = conftype;
3328
3329 /* set whether a cutoff bound is involved */
3330 conflict->conflictset->usescutoffbound = usescutoffbound;
3331
3332 /* increase the conflict counter, such that binary variables of new conflict set and new conflict queue are labeled
3333 * with this new counter
3334 */
3335 conflict->count++;
3336 if( conflict->count == 0 ) /* make sure, 0 is not a valid conflict counter (may happen due to integer overflow) */
3337 conflict->count = 1;
3338
3339 /* increase the conflict score weight for history updates of future conflict reasons */
3340 if( stat->nnodes > stat->lastconflictnode )
3341 {
3342 assert(0.0 < set->conf_scorefac && set->conf_scorefac <= 1.0);
3343 stat->vsidsweight /= set->conf_scorefac;
3344 assert(stat->vsidsweight > 0.0);
3345
3346 /* if the conflict score for the next conflict exceeds 1000.0, rescale all history conflict scores */
3347 if( stat->vsidsweight >= 1000.0 )
3348 {
3349 int v;
3350
3351 for( v = 0; v < prob->nvars; ++v )
3352 {
3353 SCIP_CALL( SCIPvarScaleVSIDS(prob->vars[v], 1.0/stat->vsidsweight) );
3354 }
3357 stat->vsidsweight = 1.0;
3358 }
3359 stat->lastconflictnode = stat->nnodes;
3360 }
3361
3362#if defined(SCIP_CONFGRAPH) || defined(SCIP_CONFGRAPH_DOT)
3363 confgraphFree();
3364 SCIP_CALL( confgraphCreate(set, conflict) );
3365#endif
3366
3367 return SCIP_OKAY;
3368}
3369
3370/** convert variable and bound change to active variable */
3371static
3373 SCIP_VAR** var, /**< pointer to variable */
3374 SCIP_SET* set, /**< global SCIP settings */
3375 SCIP_BOUNDTYPE* boundtype, /**< pointer to type of bound that was changed: lower or upper bound */
3376 SCIP_Real* bound /**< pointer to bound to convert, or NULL */
3377 )
3378{
3379 SCIP_Real scalar;
3380 SCIP_Real constant;
3381
3382 scalar = 1.0;
3383 constant = 0.0;
3384
3385 /* transform given variable to active variable */
3386 SCIP_CALL( SCIPvarGetProbvarSum(var, set, &scalar, &constant) );
3387 assert(SCIPvarGetStatus(*var) == SCIP_VARSTATUS_FIXED || scalar != 0.0); /*lint !e777*/
3388
3390 return SCIP_OKAY;
3391
3392 /* if the scalar of the aggregation is negative, we have to switch the bound type */
3393 if( scalar < 0.0 )
3394 (*boundtype) = SCIPboundtypeOpposite(*boundtype);
3395
3396 if( bound != NULL )
3397 {
3398 (*bound) -= constant;
3399 (*bound) /= scalar;
3400 }
3401
3402 return SCIP_OKAY;
3403}
3404
3405/** returns whether bound change has a valid reason that can be resolved in conflict analysis */
3406static
3408 SCIP_BDCHGINFO* bdchginfo /**< bound change information */
3409 )
3410{
3411 assert(bdchginfo != NULL);
3412 assert(!SCIPbdchginfoIsRedundant(bdchginfo));
3413
3416 && SCIPbdchginfoGetInferProp(bdchginfo) != NULL));
3417}
3418
3419
3420/** if only one conflicting bound change of the last depth level was used, and if this can be resolved,
3421 * creates GRASP-like reconvergence conflict constraints in the conflict graph up to the branching variable of this
3422 * depth level
3423 */
3424static
3426 SCIP_CONFLICT* conflict, /**< conflict analysis data */
3427 BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
3428 SCIP_SET* set, /**< global SCIP settings */
3429 SCIP_STAT* stat, /**< problem statistics */
3430 SCIP_PROB* prob, /**< problem data */
3431 SCIP_TREE* tree, /**< branch and bound tree */
3432 SCIP_Bool diving, /**< are we in strong branching or diving mode? */
3433 int validdepth, /**< minimal depth level at which the initial conflict set is valid */
3434 SCIP_BDCHGINFO* firstuip, /**< first UIP of conflict graph */
3435 int* nreconvconss, /**< pointer to store the number of generated reconvergence constraints */
3436 int* nreconvliterals /**< pointer to store the number of literals generated reconvergence constraints */
3437 )
3438{
3439 SCIP_BDCHGINFO* uip;
3440 SCIP_CONFTYPE conftype;
3441 SCIP_Bool usescutoffbound;
3442 int firstuipdepth;
3443 int focusdepth;
3444 int currentdepth;
3445 int maxvaliddepth;
3446
3447 assert(conflict != NULL);
3448 assert(firstuip != NULL);
3449 assert(nreconvconss != NULL);
3450 assert(nreconvliterals != NULL);
3451 assert(!SCIPbdchginfoIsRedundant(firstuip));
3452
3453 focusdepth = SCIPtreeGetFocusDepth(tree);
3454 currentdepth = SCIPtreeGetCurrentDepth(tree);
3455 assert(currentdepth == tree->pathlen-1);
3456 assert(focusdepth <= currentdepth);
3457
3458 /* check, whether local constraints are allowed; however, don't generate reconvergence constraints that are only valid
3459 * in the probing path and not in the problem tree (i.e. that exceed the focusdepth)
3460 */
3461 maxvaliddepth = (set->conf_allowlocal ? MIN(currentdepth-1, focusdepth) : 0);
3462 if( validdepth > maxvaliddepth )
3463 return SCIP_OKAY;
3464
3465 firstuipdepth = SCIPbdchginfoGetDepth(firstuip);
3466
3467 conftype = conflict->conflictset->conflicttype;
3468 usescutoffbound = conflict->conflictset->usescutoffbound;
3469
3470 /* for each succeeding UIP pair of the last depth level, create one reconvergence constraint */
3471 uip = firstuip;
3472 while( uip != NULL && SCIPbdchginfoGetDepth(uip) == SCIPbdchginfoGetDepth(firstuip) && bdchginfoIsResolvable(uip) )
3473 {
3474 SCIP_BDCHGINFO* oppositeuip;
3475 SCIP_BDCHGINFO* bdchginfo;
3476 SCIP_BDCHGINFO* nextuip;
3477 SCIP_VAR* uipvar;
3478 SCIP_Real oppositeuipbound;
3479 SCIP_BOUNDTYPE oppositeuipboundtype;
3480 int nresolutions;
3481
3482 assert(!SCIPbdchginfoIsRedundant(uip));
3483
3484 SCIPsetDebugMsg(set, "creating reconvergence constraint for UIP <%s> %s %g in depth %d pos %d\n",
3487
3488 /* initialize conflict data */
3489 SCIP_CALL( SCIPconflictInit(conflict, set, stat, prob, conftype, usescutoffbound) );
3490
3491 conflict->conflictset->conflicttype = conftype;
3492 conflict->conflictset->usescutoffbound = usescutoffbound;
3493
3494 /* create a temporary bound change information for the negation of the UIP's bound change;
3495 * this bound change information is freed in the SCIPconflictFlushConss() call;
3496 * for reconvergence constraints for continuous variables we can only use the "negation" !(x <= u) == (x >= u);
3497 * during conflict analysis, we treat a continuous bound "x >= u" in the conflict set as "x > u", and in the
3498 * generated constraint this is negated again to "x <= u" which is correct.
3499 */
3500 uipvar = SCIPbdchginfoGetVar(uip);
3501 oppositeuipboundtype = SCIPboundtypeOpposite(SCIPbdchginfoGetBoundtype(uip));
3502 oppositeuipbound = SCIPbdchginfoGetNewbound(uip);
3503 if( SCIPvarIsIntegral(uipvar) )
3504 {
3505 assert(SCIPsetIsIntegral(set, oppositeuipbound));
3506 oppositeuipbound += (oppositeuipboundtype == SCIP_BOUNDTYPE_LOWER ? +1.0 : -1.0);
3507 }
3508 SCIP_CALL( conflictCreateTmpBdchginfo(conflict, blkmem, set, uipvar, oppositeuipboundtype, \
3509 oppositeuipboundtype == SCIP_BOUNDTYPE_LOWER ? SCIP_REAL_MIN : SCIP_REAL_MAX, oppositeuipbound, &oppositeuip) );
3510
3511 /* put the negated UIP into the conflict set */
3512 SCIP_CALL( conflictAddConflictBound(conflict, blkmem, set, oppositeuip, oppositeuipbound) );
3513
3514 /* put positive UIP into priority queue */
3515 SCIP_CALL( conflictQueueBound(conflict, set, uip, SCIPbdchginfoGetNewbound(uip) ) );
3516
3517 /* resolve the queue until the next UIP is reached */
3518 bdchginfo = conflictFirstCand(conflict);
3519 nextuip = NULL;
3520 nresolutions = 0;
3521 while( bdchginfo != NULL && validdepth <= maxvaliddepth )
3522 {
3523 SCIP_BDCHGINFO* nextbdchginfo;
3524 SCIP_Real relaxedbd;
3525 SCIP_Bool forceresolve;
3526 int bdchgdepth;
3527
3528 /* check if the next bound change must be resolved in every case */
3529 forceresolve = (SCIPpqueueNElems(conflict->forcedbdchgqueue) > 0);
3530
3531 /* remove currently processed candidate and get next conflicting bound from the conflict candidate queue before
3532 * we remove the candidate we have to collect the relaxed bound since removing the candidate from the queue
3533 * invalidates the relaxed bound
3534 */
3535 assert(bdchginfo == conflictFirstCand(conflict));
3536 relaxedbd = SCIPbdchginfoGetRelaxedBound(bdchginfo);
3537 bdchginfo = conflictRemoveCand(conflict);
3538 nextbdchginfo = conflictFirstCand(conflict);
3539 bdchgdepth = SCIPbdchginfoGetDepth(bdchginfo);
3540 assert(bdchginfo != NULL);
3541 assert(!SCIPbdchginfoIsRedundant(bdchginfo));
3542 assert(nextbdchginfo == NULL || SCIPbdchginfoGetDepth(bdchginfo) >= SCIPbdchginfoGetDepth(nextbdchginfo)
3543 || forceresolve);
3544 assert(bdchgdepth <= firstuipdepth);
3545
3546 /* bound changes that are higher in the tree than the valid depth of the conflict can be ignored;
3547 * multiple insertions of the same bound change can be ignored
3548 */
3549 if( bdchgdepth > validdepth && bdchginfo != nextbdchginfo )
3550 {
3551 SCIP_VAR* actvar;
3552 SCIP_Bool resolved;
3553
3554 actvar = SCIPbdchginfoGetVar(bdchginfo);
3555 assert(actvar != NULL);
3556 assert(SCIPvarIsActive(actvar));
3557
3558 /* check if we have to resolve the bound change in this depth level
3559 * - the starting uip has to be resolved
3560 * - a bound change should be resolved, if it is in the fuip's depth level and not the
3561 * next uip (i.e., if it is not the last bound change in the fuip's depth level)
3562 * - a forced bound change must be resolved in any case
3563 */
3564 resolved = FALSE;
3565 if( bdchginfo == uip
3566 || (bdchgdepth == firstuipdepth
3567 && nextbdchginfo != NULL
3568 && SCIPbdchginfoGetDepth(nextbdchginfo) == bdchgdepth)
3569 || forceresolve )
3570 {
3571 SCIP_CALL( conflictResolveBound(conflict, set, bdchginfo, relaxedbd, validdepth, &resolved) );
3572 }
3573
3574 if( resolved )
3575 nresolutions++;
3576 else if( forceresolve )
3577 {
3578 /* variable cannot enter the conflict clause: we have to make the conflict clause local, s.t.
3579 * the unresolved bound change is active in the whole sub tree of the conflict clause
3580 */
3581 assert(bdchgdepth >= validdepth);
3582 validdepth = bdchgdepth;
3583
3584 SCIPsetDebugMsg(set, "couldn't resolve forced bound change on <%s> -> new valid depth: %d\n",
3585 SCIPvarGetName(actvar), validdepth);
3586 }
3587 else if( bdchginfo != uip )
3588 {
3589 assert(conflict->conflictset != NULL);
3590 assert(conflict->conflictset->nbdchginfos >= 1); /* starting UIP is already member of the conflict set */
3591
3592 /* if this is the first variable of the conflict set besides the current starting UIP, it is the next
3593 * UIP (or the first unresolvable bound change)
3594 */
3595 if( bdchgdepth == firstuipdepth && conflict->conflictset->nbdchginfos == 1 )
3596 {
3597 assert(nextuip == NULL);
3598 nextuip = bdchginfo;
3599 }
3600
3601 /* put bound change into the conflict set */
3602 SCIP_CALL( conflictAddConflictBound(conflict, blkmem, set, bdchginfo, relaxedbd) );
3603 assert(conflict->conflictset->nbdchginfos >= 2);
3604 }
3605 else
3606 assert(conflictFirstCand(conflict) == NULL); /* the starting UIP was not resolved */
3607 }
3608
3609 /* get next conflicting bound from the conflict candidate queue (this does not need to be nextbdchginfo, because
3610 * due to resolving the bound changes, a variable could be added to the queue which must be
3611 * resolved before nextbdchginfo)
3612 */
3613 bdchginfo = conflictFirstCand(conflict);
3614 }
3615 assert(nextuip != uip);
3616
3617 /* if only one propagation was resolved, the reconvergence constraint is already member of the constraint set
3618 * (it is exactly the constraint that produced the propagation)
3619 */
3620 if( nextuip != NULL && nresolutions >= 2 && bdchginfo == NULL && validdepth <= maxvaliddepth )
3621 {
3622 int nlits;
3623 SCIP_Bool success;
3624
3625 assert(SCIPbdchginfoGetDepth(nextuip) == SCIPbdchginfoGetDepth(uip));
3626
3627 /* check conflict graph frontier on debugging solution */
3628 SCIP_CALL( SCIPdebugCheckConflictFrontier(blkmem, set, tree->path[validdepth], \
3629 bdchginfo, conflict->conflictset->bdchginfos, conflict->conflictset->relaxedbds, \
3630 conflict->conflictset->nbdchginfos, conflict->bdchgqueue, conflict->forcedbdchgqueue) ); /*lint !e506 !e774*/
3631
3632 SCIPsetDebugMsg(set, "creating reconvergence constraint from UIP <%s> to UIP <%s> in depth %d with %d literals after %d resolutions\n",
3634 SCIPbdchginfoGetDepth(uip), conflict->conflictset->nbdchginfos, nresolutions);
3635
3636 /* call the conflict handlers to create a conflict set */
3637 SCIP_CALL( conflictAddConflictset(conflict, blkmem, set, stat, tree, validdepth, diving, FALSE, &success, &nlits) );
3638 if( success )
3639 {
3640 (*nreconvconss)++;
3641 (*nreconvliterals) += nlits;
3642 }
3643 }
3644
3645 /* clear the conflict candidate queue and the conflict set (to make sure, oppositeuip is not referenced anymore) */
3646 conflictClear(conflict);
3647
3648 uip = nextuip;
3649 }
3650
3651 conflict->conflictset->conflicttype = conftype;
3652 conflict->conflictset->usescutoffbound = usescutoffbound;
3653
3654 return SCIP_OKAY;
3655}
3656
3657/** analyzes conflicting bound changes that were added with calls to SCIPconflictAddBound() and
3658 * SCIPconflictAddRelaxedBound(), and on success, calls the conflict handlers to create a conflict constraint out of
3659 * the resulting conflict set; afterwards the conflict queue and the conflict set is cleared
3660 */
3662 SCIP_CONFLICT* conflict, /**< conflict analysis data */
3663 BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
3664 SCIP_SET* set, /**< global SCIP settings */
3665 SCIP_STAT* stat, /**< problem statistics */
3666 SCIP_PROB* prob, /**< problem data */
3667 SCIP_TREE* tree, /**< branch and bound tree */
3668 SCIP_Bool diving, /**< are we in strong branching or diving mode? */
3669 int validdepth, /**< minimal depth level at which the initial conflict set is valid */
3670 SCIP_Bool mustresolve, /**< should the conflict set only be used, if a resolution was applied? */
3671 int* nconss, /**< pointer to store the number of generated conflict constraints */
3672 int* nliterals, /**< pointer to store the number of literals in generated conflict constraints */
3673 int* nreconvconss, /**< pointer to store the number of generated reconvergence constraints */
3674 int* nreconvliterals /**< pointer to store the number of literals generated reconvergence constraints */
3675 )
3676{
3677 SCIP_BDCHGINFO* bdchginfo;
3678 SCIP_BDCHGINFO** firstuips;
3679 SCIP_CONFTYPE conftype;
3680 int nfirstuips;
3681 int focusdepth;
3682 int currentdepth;
3683 int maxvaliddepth;
3684 int resolvedepth;
3685 int nresolutions;
3686 int lastconsnresolutions;
3687 int lastconsresoldepth;
3688
3689 assert(conflict != NULL);
3690 assert(conflict->conflictset != NULL);
3691 assert(conflict->conflictset->nbdchginfos >= 0);
3692 assert(set != NULL);
3693 assert(stat != NULL);
3694 assert(0 <= validdepth && validdepth <= SCIPtreeGetCurrentDepth(tree));
3695 assert(nconss != NULL);
3696 assert(nliterals != NULL);
3697 assert(nreconvconss != NULL);
3698 assert(nreconvliterals != NULL);
3699
3700 focusdepth = SCIPtreeGetFocusDepth(tree);
3701 currentdepth = SCIPtreeGetCurrentDepth(tree);
3702 assert(currentdepth == tree->pathlen-1);
3703 assert(focusdepth <= currentdepth);
3704
3705 resolvedepth = ((set->conf_fuiplevels >= 0 && set->conf_fuiplevels <= currentdepth)
3706 ? currentdepth - set->conf_fuiplevels + 1 : 0);
3707 assert(0 <= resolvedepth && resolvedepth <= currentdepth + 1);
3708
3709 /* if we must resolve at least one bound change, find the first UIP at least in the last depth level */
3710 if( mustresolve )
3711 resolvedepth = MIN(resolvedepth, currentdepth);
3712
3713 SCIPsetDebugMsg(set, "analyzing conflict with %d+%d conflict candidates and starting conflict set of size %d in depth %d (resolvedepth=%d)\n",
3715 conflict->conflictset->nbdchginfos, currentdepth, resolvedepth);
3716
3717 *nconss = 0;
3718 *nliterals = 0;
3719 *nreconvconss = 0;
3720 *nreconvliterals = 0;
3721
3722 /* check, whether local conflicts are allowed; however, don't generate conflict constraints that are only valid in the
3723 * probing path and not in the problem tree (i.e. that exceed the focusdepth)
3724 */
3725 maxvaliddepth = (set->conf_allowlocal ? MIN(currentdepth-1, focusdepth) : 0);
3726 if( validdepth > maxvaliddepth )
3727 return SCIP_OKAY;
3728
3729 /* allocate temporary memory for storing first UIPs (in each depth level, at most two bound changes can be flagged
3730 * as UIP, namely a binary and a non-binary bound change)
3731 */
3732 SCIP_CALL( SCIPsetAllocBufferArray(set, &firstuips, 2*(currentdepth+1)) ); /*lint !e647*/
3733
3734 /* process all bound changes in the conflict candidate queue */
3735 nresolutions = 0;
3736 lastconsnresolutions = (mustresolve ? 0 : -1);
3737 lastconsresoldepth = (mustresolve ? currentdepth : INT_MAX);
3738 bdchginfo = conflictFirstCand(conflict);
3739 nfirstuips = 0;
3740
3741 /* check if the initial reason on debugging solution */
3742 SCIP_CALL( SCIPdebugCheckConflictFrontier(blkmem, set, tree->path[validdepth], \
3743 NULL, conflict->conflictset->bdchginfos, conflict->conflictset->relaxedbds, conflict->conflictset->nbdchginfos, \
3744 conflict->bdchgqueue, conflict->forcedbdchgqueue) ); /*lint !e506 !e774*/
3745
3746 while( bdchginfo != NULL && validdepth <= maxvaliddepth )
3747 {
3748 SCIP_BDCHGINFO* nextbdchginfo;
3749 SCIP_Real relaxedbd;
3750 SCIP_Bool forceresolve;
3751 int bdchgdepth;
3752
3753 assert(!SCIPbdchginfoIsRedundant(bdchginfo));
3754
3755 /* check if the next bound change must be resolved in every case */
3756 forceresolve = (SCIPpqueueNElems(conflict->forcedbdchgqueue) > 0);
3757
3758 /* resolve next bound change in queue */
3759 bdchgdepth = SCIPbdchginfoGetDepth(bdchginfo);
3760 assert(0 <= bdchgdepth && bdchgdepth <= currentdepth);
3761 assert(SCIPvarIsActive(SCIPbdchginfoGetVar(bdchginfo)));
3762 assert(bdchgdepth < tree->pathlen);
3763 assert(tree->path[bdchgdepth] != NULL);
3764 assert(tree->path[bdchgdepth]->domchg != NULL);
3765 assert(SCIPbdchginfoGetPos(bdchginfo) < (int)tree->path[bdchgdepth]->domchg->domchgbound.nboundchgs);
3766 assert(tree->path[bdchgdepth]->domchg->domchgbound.boundchgs[SCIPbdchginfoGetPos(bdchginfo)].var
3767 == SCIPbdchginfoGetVar(bdchginfo));
3768 assert(tree->path[bdchgdepth]->domchg->domchgbound.boundchgs[SCIPbdchginfoGetPos(bdchginfo)].newbound
3769 == SCIPbdchginfoGetNewbound(bdchginfo)
3772 == SCIPbdchginfoGetNewbound(bdchginfo)); /*lint !e777*/
3773 assert((SCIP_BOUNDTYPE)tree->path[bdchgdepth]->domchg->domchgbound.boundchgs[SCIPbdchginfoGetPos(bdchginfo)].boundtype
3774 == SCIPbdchginfoGetBoundtype(bdchginfo));
3775
3776 /* create intermediate conflict constraint */
3777 assert(nresolutions >= lastconsnresolutions);
3778 if( !forceresolve )
3779 {
3780 if( nresolutions == lastconsnresolutions )
3781 lastconsresoldepth = bdchgdepth; /* all intermediate depth levels consisted of only unresolved bound changes */
3782 else if( bdchgdepth < lastconsresoldepth && (set->conf_interconss == -1 || *nconss < set->conf_interconss) )
3783 {
3784 int nlits;
3785 SCIP_Bool success;
3786
3787 /* call the conflict handlers to create a conflict set */
3788 SCIPsetDebugMsg(set, "creating intermediate conflictset after %d resolutions up to depth %d (valid at depth %d): %d conflict bounds, %d bounds in queue\n",
3789 nresolutions, bdchgdepth, validdepth, conflict->conflictset->nbdchginfos,
3790 SCIPpqueueNElems(conflict->bdchgqueue));
3791
3792 SCIP_CALL( conflictAddConflictset(conflict, blkmem, set, stat, tree, validdepth, diving, TRUE, &success, &nlits) );
3793 lastconsnresolutions = nresolutions;
3794 lastconsresoldepth = bdchgdepth;
3795 if( success )
3796 {
3797 (*nconss)++;
3798 (*nliterals) += nlits;
3799 }
3800 }
3801 }
3802
3803 /* remove currently processed candidate and get next conflicting bound from the conflict candidate queue before
3804 * we remove the candidate we have to collect the relaxed bound since removing the candidate from the queue
3805 * invalidates the relaxed bound
3806 */
3807 assert(bdchginfo == conflictFirstCand(conflict));
3808 relaxedbd = SCIPbdchginfoGetRelaxedBound(bdchginfo);
3809 bdchginfo = conflictRemoveCand(conflict);
3810 nextbdchginfo = conflictFirstCand(conflict);
3811 assert(bdchginfo != NULL);
3812 assert(!SCIPbdchginfoIsRedundant(bdchginfo));
3813 assert(nextbdchginfo == NULL || SCIPbdchginfoGetDepth(bdchginfo) >= SCIPbdchginfoGetDepth(nextbdchginfo)
3814 || forceresolve);
3815
3816 /* we don't need to resolve bound changes that are already active in the valid depth of the current conflict set,
3817 * because the conflict set can only be added locally at the valid depth, and all bound changes applied in this
3818 * depth or earlier can be removed from the conflict constraint, since they are already applied in the constraint's
3819 * subtree;
3820 * if the next bound change on the remaining queue is equal to the current bound change,
3821 * this is a multiple insertion in the conflict candidate queue and we can ignore the current
3822 * bound change
3823 */
3824 if( bdchgdepth > validdepth && bdchginfo != nextbdchginfo )
3825 {
3826 SCIP_VAR* actvar;
3827 SCIP_Bool resolved;
3828
3829 actvar = SCIPbdchginfoGetVar(bdchginfo);
3830 assert(actvar != NULL);
3831 assert(SCIPvarIsActive(actvar));
3832
3833 /* check if we want to resolve the bound change in this depth level
3834 * - bound changes should be resolved, if
3835 * (i) we must apply at least one resolution and didn't resolve a bound change yet, or
3836 * (ii) their depth level is at least equal to the minimal resolving depth, and
3837 * they are not the last remaining conflicting bound change in their depth level
3838 * (iii) the bound change resolving is forced (i.e., the forced queue was non-empty)
3839 */
3840 resolved = FALSE;
3841 if( (mustresolve && nresolutions == 0)
3842 || (bdchgdepth >= resolvedepth
3843 && nextbdchginfo != NULL
3844 && SCIPbdchginfoGetDepth(nextbdchginfo) == bdchgdepth)
3845 || forceresolve )
3846 {
3847 SCIP_CALL( conflictResolveBound(conflict, set, bdchginfo, relaxedbd, validdepth, &resolved) );
3848 }
3849
3850 if( resolved )
3851 nresolutions++;
3852 else if( forceresolve )
3853 {
3854 /* variable cannot enter the conflict clause: we have to make the conflict clause local, s.t.
3855 * the unresolved bound change is active in the whole sub tree of the conflict clause
3856 */
3857 assert(bdchgdepth >= validdepth);
3858 validdepth = bdchgdepth;
3859
3860 SCIPsetDebugMsg(set, "couldn't resolve forced bound change on <%s> -> new valid depth: %d\n",
3861 SCIPvarGetName(actvar), validdepth);
3862 }
3863 else
3864 {
3865 /* if this is a UIP (the last bound change in its depth level), it can be used to generate a
3866 * UIP reconvergence constraint
3867 */
3868 if( nextbdchginfo == NULL || SCIPbdchginfoGetDepth(nextbdchginfo) != bdchgdepth )
3869 {
3870 assert(nfirstuips < 2*(currentdepth+1));
3871 firstuips[nfirstuips] = bdchginfo;
3872 nfirstuips++;
3873 }
3874
3875 /* put variable into the conflict set, using the literal that is currently fixed to FALSE */
3876 SCIP_CALL( conflictAddConflictBound(conflict, blkmem, set, bdchginfo, relaxedbd) );
3877 }
3878 }
3879
3880 /* check conflict graph frontier on debugging solution */
3881 SCIP_CALL( SCIPdebugCheckConflictFrontier(blkmem, set, tree->path[validdepth], \
3882 bdchginfo, conflict->conflictset->bdchginfos, conflict->conflictset->relaxedbds, conflict->conflictset->nbdchginfos, \
3883 conflict->bdchgqueue, conflict->forcedbdchgqueue) ); /*lint !e506 !e774*/
3884
3885 /* get next conflicting bound from the conflict candidate queue (this needs not to be nextbdchginfo, because
3886 * due to resolving the bound changes, a bound change could be added to the queue which must be
3887 * resolved before nextbdchginfo)
3888 */
3889 bdchginfo = conflictFirstCand(conflict);
3890 }
3891
3892 /* check, if a valid conflict set was found */
3893 if( bdchginfo == NULL
3894 && nresolutions > lastconsnresolutions
3895 && validdepth <= maxvaliddepth
3896 && (!mustresolve || nresolutions > 0 || conflict->conflictset->nbdchginfos == 0)
3897 && SCIPpqueueNElems(conflict->forcedbdchgqueue) == 0 )
3898 {
3899 int nlits;
3900 SCIP_Bool success;
3901
3902 /* call the conflict handlers to create a conflict set */
3903 SCIP_CALL( conflictAddConflictset(conflict, blkmem, set, stat, tree, validdepth, diving, TRUE, &success, &nlits) );
3904 if( success )
3905 {
3906 (*nconss)++;
3907 (*nliterals) += nlits;
3908 }
3909 }
3910
3911 /* produce reconvergence constraints defined by succeeding UIP's of the last depth level */
3912 if( set->conf_reconvlevels != 0 && validdepth <= maxvaliddepth )
3913 {
3914 int reconvlevels;
3915 int i;
3916
3917 reconvlevels = (set->conf_reconvlevels == -1 ? INT_MAX : set->conf_reconvlevels);
3918 for( i = 0; i < nfirstuips; ++i )
3919 {
3920 if( SCIPbdchginfoHasInferenceReason(firstuips[i])
3921 && currentdepth - SCIPbdchginfoGetDepth(firstuips[i]) < reconvlevels )
3922 {
3923 SCIP_CALL( conflictCreateReconvergenceConss(conflict, blkmem, set, stat, prob, tree, diving, \
3924 validdepth, firstuips[i], nreconvconss, nreconvliterals) );
3925 }
3926 }
3927 }
3928
3929 /* free the temporary memory */
3930 SCIPsetFreeBufferArray(set, &firstuips);
3931
3932 /* store last conflict type */
3933 conftype = conflict->conflictset->conflicttype;
3934
3935 /* clear the conflict candidate queue and the conflict set */
3936 conflictClear(conflict);
3937
3938 /* restore last conflict type */
3939 conflict->conflictset->conflicttype = conftype;
3940
3941 return SCIP_OKAY;
3942}
3943
3944/** calculates the score of a bound change within a conflict */
3945static
3947 SCIP_Real prooflhs, /**< lhs of proof constraint */
3948 SCIP_Real proofact, /**< activity of the proof constraint */
3949 SCIP_Real proofactdelta, /**< activity change */
3950 SCIP_Real proofcoef, /**< coefficient in proof constraint */
3951 int depth, /**< bound change depth */
3952 int currentdepth, /**< current depth */
3953 SCIP_VAR* var, /**< variable corresponding to bound change */
3954 SCIP_SET* set /**< global SCIP settings */
3955 )
3956{
3957 SCIP_COL* col;
3958 SCIP_Real score;
3959
3960 score = set->conf_proofscorefac * (1.0 - proofactdelta/(prooflhs - proofact));
3961 score = MAX(score, 0.0);
3962 score += set->conf_depthscorefac * (SCIP_Real)(depth+1)/(SCIP_Real)(currentdepth+1);
3963
3965 col = SCIPvarGetCol(var);
3966 else
3967 col = NULL;
3968
3969 if( proofcoef > 0.0 )
3970 {
3971 if( col != NULL && SCIPcolGetNNonz(col) > 0 )
3972 score += set->conf_uplockscorefac
3974 else
3975 score += set->conf_uplockscorefac * SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL);
3976 }
3977 else
3978 {
3979 if( col != NULL && SCIPcolGetNNonz(col) > 0 )
3980 score += set->conf_downlockscorefac
3982 else
3983 score += set->conf_downlockscorefac * SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL);
3984 }
3985
3986 return score;
3987}
3988
3989/** ensures, that candidate array can store at least num entries */
3990static
3992 SCIP_SET* set, /**< global SCIP settings */
3993 SCIP_VAR*** cands, /**< pointer to candidate array */
3994 SCIP_Real** candscores, /**< pointer to candidate score array */
3995 SCIP_Real** newbounds, /**< pointer to candidate new bounds array */
3996 SCIP_Real** proofactdeltas, /**< pointer to candidate proof delta array */
3997 int* candssize, /**< pointer to size of array */
3998 int num /**< minimal number of candidates to store in array */
3999 )
4000{
4001 assert(cands != NULL);
4002 assert(candssize != NULL);
4003
4004 if( num > *candssize )
4005 {
4006 int newsize;
4007
4008 newsize = SCIPsetCalcMemGrowSize(set, num);
4009 SCIP_CALL( SCIPsetReallocBufferArray(set, cands, newsize) );
4010 SCIP_CALL( SCIPsetReallocBufferArray(set, candscores, newsize) );
4011 SCIP_CALL( SCIPsetReallocBufferArray(set, newbounds, newsize) );
4012 SCIP_CALL( SCIPsetReallocBufferArray(set, proofactdeltas, newsize) );
4013 *candssize = newsize;
4014 }
4015 assert(num <= *candssize);
4016
4017 return SCIP_OKAY;
4018}
4019
4020/** after changing the global bound of a variable, the bdchginfos that are now redundant are replaced with
4021 * oldbound = newbound = global bound; if the current bdchginfo is of such kind, the bound is equal to the
4022 * global bound and we can ignore it by installing a -1 as the corresponding bound change info position
4023 */
4024static
4026 SCIP_VAR* var, /**< problem variable */
4027 int* lbchginfopos, /**< pointer to lower bound change information position */
4028 int* ubchginfopos /**< pointer to upper bound change information position */
4029 )
4030{
4031 assert(var != NULL);
4032 assert(lbchginfopos != NULL);
4033 assert(ubchginfopos != NULL);
4034 assert(-1 <= *lbchginfopos && *lbchginfopos <= var->nlbchginfos);
4035 assert(-1 <= *ubchginfopos && *ubchginfopos <= var->nubchginfos);
4036 assert(*lbchginfopos == -1 || *lbchginfopos == var->nlbchginfos
4037 || var->lbchginfos[*lbchginfopos].redundant
4038 == (var->lbchginfos[*lbchginfopos].oldbound == var->lbchginfos[*lbchginfopos].newbound)); /*lint !e777*/
4039 assert(*ubchginfopos == -1 || *ubchginfopos == var->nubchginfos
4040 || var->ubchginfos[*ubchginfopos].redundant
4041 == (var->ubchginfos[*ubchginfopos].oldbound == var->ubchginfos[*ubchginfopos].newbound)); /*lint !e777*/
4042
4043 if( *lbchginfopos >= 0 && *lbchginfopos < var->nlbchginfos && var->lbchginfos[*lbchginfopos].redundant )
4044 {
4045 assert(SCIPvarGetLbGlobal(var) == var->lbchginfos[*lbchginfopos].oldbound); /*lint !e777*/
4046 *lbchginfopos = -1;
4047 }
4048 if( *ubchginfopos >= 0 && *ubchginfopos < var->nubchginfos && var->ubchginfos[*ubchginfopos].redundant )
4049 {
4050 assert(SCIPvarGetUbGlobal(var) == var->ubchginfos[*ubchginfopos].oldbound); /*lint !e777*/
4051 *ubchginfopos = -1;
4052 }
4053}
4054
4055/** adds variable's bound to conflict candidate queue */
4057 SCIP_CONFLICT* conflict, /**< conflict analysis data */
4058 BMS_BLKMEM* blkmem, /**< block memory */
4059 SCIP_SET* set, /**< global SCIP settings */
4060 SCIP_STAT* stat, /**< dynamic problem statistics */
4061 SCIP_VAR* var, /**< problem variable */
4062 SCIP_BOUNDTYPE boundtype, /**< type of bound that was changed: lower or upper bound */
4063 SCIP_BDCHGIDX* bdchgidx /**< bound change index (time stamp of bound change), or NULL for current time */
4064 )
4065{
4066 SCIP_BDCHGINFO* bdchginfo;
4067
4068 assert(conflict != NULL);
4069 assert(stat != NULL);
4070 assert(var != NULL);
4071
4072 /* convert bound to active problem variable */
4073 SCIP_CALL( convertToActiveVar(&var, set, &boundtype, NULL) );
4074
4075 /* we can ignore fixed variables */
4077 return SCIP_OKAY;
4078
4079 /* if the variable is multi-aggregated, add the bounds of all aggregation variables */
4081 {
4082 SCIP_VAR** vars;
4084 int nvars;
4085 int i;
4086
4087 vars = SCIPvarGetMultaggrVars(var);
4089 nvars = SCIPvarGetMultaggrNVars(var);
4090 for( i = 0; i < nvars; ++i )
4091 {
4092 SCIP_CALL( SCIPconflictAddBound(conflict, blkmem, set, stat, vars[i],
4093 (scalars[i] < 0.0 ? SCIPboundtypeOpposite(boundtype) : boundtype), bdchgidx) );
4094 }
4095
4096 return SCIP_OKAY;
4097 }
4098 assert(SCIPvarIsActive(var));
4099
4100 /* get bound change information */
4101 bdchginfo = SCIPvarGetBdchgInfo(var, boundtype, bdchgidx, FALSE);
4102
4103 /* if bound of variable was not changed (this means it is still the global bound), we can ignore the conflicting
4104 * bound
4105 */
4106 if( bdchginfo == NULL )
4107 return SCIP_OKAY;
4108
4109 assert(SCIPbdchgidxIsEarlier(SCIPbdchginfoGetIdx(bdchginfo), bdchgidx));
4110
4111 SCIP_CALL( conflictAddBound(conflict, blkmem, set, stat, var, boundtype, bdchginfo, SCIPbdchginfoGetNewbound(bdchginfo)) );
4112
4113 return SCIP_OKAY;
4114}
4115
4116/** adds variable's bound to conflict candidate queue */
4118 SCIP_CONFLICT* conflict, /**< conflict analysis data */
4119 BMS_BLKMEM* blkmem, /**< block memory */
4120 SCIP_SET* set, /**< global SCIP settings */
4121 SCIP_STAT* stat, /**< dynamic problem statistics */
4122 SCIP_VAR* var, /**< problem variable */
4123 SCIP_BOUNDTYPE boundtype, /**< type of bound that was changed: lower or upper bound */
4124 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
4125 SCIP_Real relaxedbd /**< the relaxed bound */
4126 )
4127{
4128 SCIP_BDCHGINFO* bdchginfo;
4129 int nbdchgs;
4130
4131 assert(conflict != NULL);
4132 assert(stat != NULL);
4133 assert(var != NULL);
4134
4135 if( !SCIPvarIsActive(var) )
4136 {
4137 /* convert bound to active problem variable */
4138 SCIP_CALL( convertToActiveVar(&var, set, &boundtype, &relaxedbd) );
4139
4140 /* we can ignore fixed variables */
4142 return SCIP_OKAY;
4143
4144 /* if the variable is multi-aggregated, add the bounds of all aggregation variables */
4146 {
4147 SCIPsetDebugMsg(set, "ignoring relaxed bound information since variable <%s> is multi-aggregated active\n", SCIPvarGetName(var));
4148
4149 SCIP_CALL( SCIPconflictAddBound(conflict, blkmem, set, stat, var, boundtype, bdchgidx) );
4150
4151 return SCIP_OKAY;
4152 }
4153 }
4154 assert(SCIPvarIsActive(var));
4155
4156 /* get bound change information */
4157 bdchginfo = SCIPvarGetBdchgInfo(var, boundtype, bdchgidx, FALSE);
4158
4159 /* if bound of variable was not changed (this means it is still the global bound), we can ignore the conflicting
4160 * bound
4161 */
4162 if( bdchginfo == NULL )
4163 return SCIP_OKAY;
4164
4165 /* check that the bound change info is not a temporary one */
4166 assert(SCIPbdchgidxGetPos(&bdchginfo->bdchgidx) >= 0);
4167
4168 /* get the position of the bound change information within the bound change array of the variable */
4169 nbdchgs = (int) bdchginfo->pos;
4170 assert(nbdchgs >= 0);
4171
4172 /* if the relaxed bound should be ignored, set the relaxed bound to the bound given by the bdchgidx; that ensures
4173 * that the loop(s) below will be skipped
4174 */
4175 if( set->conf_ignorerelaxedbd )
4176 relaxedbd = SCIPbdchginfoGetNewbound(bdchginfo);
4177
4178 /* search for the bound change information which includes the relaxed bound */
4179 if( boundtype == SCIP_BOUNDTYPE_LOWER )
4180 {
4181 SCIP_Real newbound;
4182
4183 /* adjust relaxed lower bound w.r.t. variable type */
4184 SCIPvarAdjustLb(var, set, &relaxedbd);
4185
4186 /* due to numericis we compare the relaxed lower bound to the one present at the particular time point and take
4187 * the better one
4188 */
4189 newbound = SCIPbdchginfoGetNewbound(bdchginfo);
4190 relaxedbd = MIN(relaxedbd, newbound);
4191
4192 /* check if relaxed lower bound is smaller or equal to global lower bound; if so we can ignore the conflicting
4193 * bound
4194 */
4195 if( SCIPsetIsLE(set, relaxedbd, SCIPvarGetLbGlobal(var)) )
4196 return SCIP_OKAY;
4197
4198 while( nbdchgs > 0 )
4199 {
4200 assert(SCIPsetIsLE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)));
4201
4202 /* check if the old lower bound is greater than or equal to relaxed lower bound; if not we found the bound
4203 * change info which we need to report
4204 */
4205 if( SCIPsetIsGT(set, relaxedbd, SCIPbdchginfoGetOldbound(bdchginfo)) )
4206 break;
4207
4208 bdchginfo = SCIPvarGetBdchgInfoLb(var, nbdchgs-1);
4209
4210 SCIPsetDebugMsg(set, "lower bound change %d oldbd=%.15g, newbd=%.15g, depth=%d, pos=%d, redundant=%u\n",
4211 nbdchgs, SCIPbdchginfoGetOldbound(bdchginfo), SCIPbdchginfoGetNewbound(bdchginfo),
4212 SCIPbdchginfoGetDepth(bdchginfo), SCIPbdchginfoGetPos(bdchginfo),
4213 SCIPbdchginfoIsRedundant(bdchginfo));
4214
4215 /* if bound change is redundant (this means it now a global bound), we can ignore the conflicting bound */
4216 if( SCIPbdchginfoIsRedundant(bdchginfo) )
4217 return SCIP_OKAY;
4218
4219 nbdchgs--;
4220 }
4221 assert(SCIPsetIsGT(set, relaxedbd, SCIPbdchginfoGetOldbound(bdchginfo)));
4222 }
4223 else
4224 {
4225 SCIP_Real newbound;
4226
4227 assert(boundtype == SCIP_BOUNDTYPE_UPPER);
4228
4229 /* adjust relaxed upper bound w.r.t. variable type */
4230 SCIPvarAdjustUb(var, set, &relaxedbd);
4231
4232 /* due to numericis we compare the relaxed upper bound to the one present at the particular time point and take
4233 * the better one
4234 */
4235 newbound = SCIPbdchginfoGetNewbound(bdchginfo);
4236 relaxedbd = MAX(relaxedbd, newbound);
4237
4238 /* check if relaxed upper bound is greater or equal to global upper bound; if so we can ignore the conflicting
4239 * bound
4240 */
4241 if( SCIPsetIsGE(set, relaxedbd, SCIPvarGetUbGlobal(var)) )
4242 return SCIP_OKAY;
4243
4244 while( nbdchgs > 0 )
4245 {
4246 assert(SCIPsetIsGE(set, relaxedbd, SCIPbdchginfoGetNewbound(bdchginfo)));
4247
4248 /* check if the old upper bound is smaller than or equal to the relaxed upper bound; if not we found the
4249 * bound change info which we need to report
4250 */
4251 if( SCIPsetIsLT(set, relaxedbd, SCIPbdchginfoGetOldbound(bdchginfo)) )
4252 break;
4253
4254 bdchginfo = SCIPvarGetBdchgInfoUb(var, nbdchgs-1);
4255
4256 SCIPsetDebugMsg(set, "upper bound change %d oldbd=%.15g, newbd=%.15g, depth=%d, pos=%d, redundant=%u\n",
4257 nbdchgs, SCIPbdchginfoGetOldbound(bdchginfo), SCIPbdchginfoGetNewbound(bdchginfo),
4258 SCIPbdchginfoGetDepth(bdchginfo), SCIPbdchginfoGetPos(bdchginfo),
4259 SCIPbdchginfoIsRedundant(bdchginfo));
4260
4261 /* if bound change is redundant (this means it now a global bound), we can ignore the conflicting bound */
4262 if( SCIPbdchginfoIsRedundant(bdchginfo) )
4263 return SCIP_OKAY;
4264
4265 nbdchgs--;
4266 }
4267 assert(SCIPsetIsLT(set, relaxedbd, SCIPbdchginfoGetOldbound(bdchginfo)));
4268 }
4269
4270 assert(SCIPbdchgidxIsEarlier(SCIPbdchginfoGetIdx(bdchginfo), bdchgidx));
4271
4272 /* put bound change information into priority queue */
4273 SCIP_CALL( conflictAddBound(conflict, blkmem, set, stat, var, boundtype, bdchginfo, relaxedbd) );
4274
4275 return SCIP_OKAY;
4276}
4277
4278/** checks if the given variable is already part of the current conflict set or queued for resolving with the same or
4279 * even stronger bound
4280 */
4282 SCIP_CONFLICT* conflict, /**< conflict analysis data */
4283 SCIP_VAR* var, /**< problem variable */
4284 SCIP_SET* set, /**< global SCIP settings */
4285 SCIP_BOUNDTYPE boundtype, /**< type of bound for which the score should be increased */
4286 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
4287 SCIP_Bool* used /**< pointer to store if the variable is already used */
4288 )
4289{
4290 SCIP_Real newbound;
4291
4292 /* convert bound to active problem variable */
4293 SCIP_CALL( convertToActiveVar(&var, set, &boundtype, NULL) );
4294
4296 *used = FALSE;
4297 else
4298 {
4299 assert(SCIPvarIsActive(var));
4300 assert(var != NULL);
4301
4302 switch( boundtype )
4303 {
4305
4306 newbound = SCIPgetVarLbAtIndex(set->scip, var, bdchgidx, FALSE);
4307
4308 if( var->conflictlbcount == conflict->count && var->conflictlb >= newbound )
4309 {
4310 SCIPsetDebugMsg(set, "already queued bound change <%s> >= %g\n", SCIPvarGetName(var), newbound);
4311 *used = TRUE;
4312 }
4313 else
4314 *used = FALSE;
4315 break;
4317
4318 newbound = SCIPgetVarUbAtIndex(set->scip, var, bdchgidx, FALSE);
4319
4320 if( var->conflictubcount == conflict->count && var->conflictub <= newbound )
4321 {
4322 SCIPsetDebugMsg(set, "already queued bound change <%s> <= %g\n", SCIPvarGetName(var), newbound);
4323 *used = TRUE;
4324 }
4325 else
4326 *used = FALSE;
4327 break;
4328 default:
4329 SCIPerrorMessage("invalid bound type %d\n", boundtype);
4330 SCIPABORT();
4331 *used = FALSE; /*lint !e527*/
4332 }
4333 }
4334
4335 return SCIP_OKAY;
4336}
4337
4338/** inserts variable's new bounds into bound change arrays */
4339static
4341 SCIP_SET* set, /**< global SCIP settings */
4342 SCIP_VAR* var, /**< variable to change the LP bounds for */
4343 SCIP_Real newlb, /**< new lower bound */
4344 SCIP_Real newub, /**< new upper bound */
4345 SCIP_LPBDCHGS* oldlpbdchgs, /**< old LP bound changes used for reset the LP bound change */
4346 SCIP_LPBDCHGS* relaxedlpbdchgs, /**< relaxed LP bound changes used for reset the LP bound change */
4347 SCIP_LPI* lpi /**< pointer to LPi to access infinity of LP solver; necessary to set correct value */
4348 )
4349{
4350 assert(newlb <= newub);
4351 assert(oldlpbdchgs != NULL);
4352 assert(relaxedlpbdchgs != NULL);
4353
4355 {
4356 SCIP_COL* col;
4357 int idx;
4358 int c;
4359
4360 col = SCIPvarGetCol(var);
4361 c = SCIPcolGetLPPos(col);
4362
4363 if( c >= 0 )
4364 {
4365 /* store old bound change for resetting the LP later */
4366 if( !oldlpbdchgs->usedcols[c] )
4367 {
4368 idx = oldlpbdchgs->nbdchgs;
4369 oldlpbdchgs->usedcols[c] = TRUE;
4370 oldlpbdchgs->bdchgcolinds[c] = idx;
4371 oldlpbdchgs->nbdchgs++;
4372
4373 oldlpbdchgs->bdchginds[idx] = c;
4374 oldlpbdchgs->bdchglbs[idx] = SCIPvarGetLbLP(var, set);
4375 oldlpbdchgs->bdchgubs[idx] = SCIPvarGetUbLP(var, set);
4376 }
4377 assert(oldlpbdchgs->bdchginds[oldlpbdchgs->bdchgcolinds[c]] == c);
4378 assert((SCIPlpiIsInfinity(lpi, -oldlpbdchgs->bdchglbs[oldlpbdchgs->bdchgcolinds[c]]) && SCIPsetIsInfinity(set, -SCIPvarGetLbLP(var, set))) ||
4379 SCIPsetIsEQ(set, oldlpbdchgs->bdchglbs[oldlpbdchgs->bdchgcolinds[c]], SCIPvarGetLbLP(var, set)));
4380 assert((SCIPlpiIsInfinity(lpi, oldlpbdchgs->bdchgubs[oldlpbdchgs->bdchgcolinds[c]]) && SCIPsetIsInfinity(set, SCIPvarGetUbLP(var, set))) ||
4381 SCIPsetIsEQ(set, oldlpbdchgs->bdchgubs[oldlpbdchgs->bdchgcolinds[c]], SCIPvarGetUbLP(var, set)));
4382
4383 /* store bound change for conflict analysis */
4384 if( !relaxedlpbdchgs->usedcols[c] )
4385 {
4386 idx = relaxedlpbdchgs->nbdchgs;
4387 relaxedlpbdchgs->usedcols[c] = TRUE;
4388 relaxedlpbdchgs->bdchgcolinds[c] = idx;
4389 relaxedlpbdchgs->nbdchgs++;
4390
4391 /* remember the positive for later further bound widenings */
4392 relaxedlpbdchgs->bdchginds[idx] = c;
4393 }
4394 else
4395 {
4396 idx = relaxedlpbdchgs->bdchgcolinds[c];
4397 assert(relaxedlpbdchgs->bdchginds[idx] == c);
4398
4399 /* the new bound should be the same or more relaxed */
4400 assert(relaxedlpbdchgs->bdchglbs[idx] >= newlb ||
4401 (SCIPlpiIsInfinity(lpi, -relaxedlpbdchgs->bdchglbs[idx]) && SCIPsetIsInfinity(set, -newlb)));
4402 assert(relaxedlpbdchgs->bdchgubs[idx] <= newub ||
4403 (SCIPlpiIsInfinity(lpi, relaxedlpbdchgs->bdchgubs[idx]) && SCIPsetIsInfinity(set, newub)));
4404 }
4405
4406 /* set the new bounds for the LP with the correct infinity value */
4407 relaxedlpbdchgs->bdchglbs[idx] = SCIPsetIsInfinity(set, -newlb) ? -SCIPlpiInfinity(lpi) : newlb;
4408 relaxedlpbdchgs->bdchgubs[idx] = SCIPsetIsInfinity(set, newub) ? SCIPlpiInfinity(lpi) : newub;
4409 if( SCIPsetIsInfinity(set, -oldlpbdchgs->bdchglbs[idx]) )
4410 oldlpbdchgs->bdchglbs[idx] = -SCIPlpiInfinity(lpi);
4411 if( SCIPsetIsInfinity(set, oldlpbdchgs->bdchgubs[idx]) )
4412 oldlpbdchgs->bdchgubs[idx] = SCIPlpiInfinity(lpi);
4413 }
4414 }
4415
4416 return SCIP_OKAY;
4417}
4418
4419/** adds variable to candidate list, if the current best bound corresponding to the proof coefficient is local;
4420 * returns the array position in the candidate list, where the new candidate was inserted, or -1 if the
4421 * variable can relaxed to global bounds immediately without increasing the proof's activity;
4422 * the candidates are sorted with respect to the following two criteria:
4423 * - prefer bound changes that have been applied deeper in the tree, to get a more global conflict
4424 * - prefer variables with small Farkas coefficient to get rid of as many bound changes as possible
4425 */
4426static
4428 SCIP_SET* set, /**< global SCIP settings */
4429 int currentdepth, /**< current depth in the tree */
4430 SCIP_VAR* var, /**< variable to add to candidate array */
4431 int lbchginfopos, /**< positions of currently active lower bound change information in variable's array */
4432 int ubchginfopos, /**< positions of currently active upper bound change information in variable's array */
4433 SCIP_Real proofcoef, /**< coefficient of variable in infeasibility/bound proof */
4434 SCIP_Real prooflhs, /**< left hand side of infeasibility/bound proof */
4435 SCIP_Real proofact, /**< activity of infeasibility/bound proof row */
4436 SCIP_VAR*** cands, /**< pointer to candidate array for undoing bound changes */
4437 SCIP_Real** candscores, /**< pointer to candidate score array for undoing bound changes */
4438 SCIP_Real** newbounds, /**< pointer to candidate new bounds array for undoing bound changes */
4439 SCIP_Real** proofactdeltas, /**< pointer to proof activity increase array for undoing bound changes */
4440 int* candssize, /**< pointer to size of cands arrays */
4441 int* ncands, /**< pointer to count number of candidates in bound change list */
4442 int firstcand /**< position of first unprocessed bound change candidate */
4443 )
4444{
4445 SCIP_Real oldbound;
4446 SCIP_Real newbound;
4447 SCIP_Real QUAD(proofactdelta);
4448 SCIP_Real score;
4449 int depth;
4450 int i;
4451 SCIP_Bool resolvable;
4452
4453 assert(set != NULL);
4454 assert(var != NULL);
4455 assert(-1 <= lbchginfopos && lbchginfopos <= var->nlbchginfos);
4456 assert(-1 <= ubchginfopos && ubchginfopos <= var->nubchginfos);
4457 assert(!SCIPsetIsZero(set, proofcoef));
4458 assert(SCIPsetIsGT(set, prooflhs, proofact));
4459 assert(cands != NULL);
4460 assert(candscores != NULL);
4461 assert(newbounds != NULL);
4462 assert(proofactdeltas != NULL);
4463 assert(candssize != NULL);
4464 assert(ncands != NULL);
4465 assert(*ncands <= *candssize);
4466 assert(0 <= firstcand && firstcand <= *ncands);
4467
4468 /* in the infeasibility or dual bound proof, the variable's bound is chosen to maximize the proof's activity */
4469 if( proofcoef > 0.0 )
4470 {
4471 assert(ubchginfopos >= 0); /* otherwise, undoBdchgsProof() should already have relaxed the local bound */
4472
4473 /* calculate the difference of current bound to the previous bound the variable was set to */
4474 if( ubchginfopos == var->nubchginfos )
4475 {
4476 /* current bound is the strong branching or diving bound */
4477 oldbound = SCIPvarGetUbLP(var, set);
4478 newbound = SCIPvarGetUbLocal(var);
4479 depth = currentdepth+1;
4480 resolvable = FALSE;
4481 }
4482 else
4483 {
4484 /* current bound is the result of a local bound change */
4485 resolvable = bdchginfoIsResolvable(&var->ubchginfos[ubchginfopos]);
4486 depth = var->ubchginfos[ubchginfopos].bdchgidx.depth;
4487 oldbound = var->ubchginfos[ubchginfopos].newbound;
4488 newbound = var->ubchginfos[ubchginfopos].oldbound;
4489 }
4490 }
4491 else
4492 {
4493 assert(lbchginfopos >= 0); /* otherwise, undoBdchgsProof() should already have relaxed the local bound */
4494
4495 /* calculate the difference of current bound to the previous bound the variable was set to */
4496 if( lbchginfopos == var->nlbchginfos )
4497 {
4498 /* current bound is the strong branching or diving bound */
4499 oldbound = SCIPvarGetLbLP(var, set);
4500 newbound = SCIPvarGetLbLocal(var);
4501 depth = currentdepth+1;
4502 resolvable = FALSE;
4503 }
4504 else
4505 {
4506 /* current bound is the result of a local bound change */
4507 resolvable = bdchginfoIsResolvable(&var->lbchginfos[lbchginfopos]);
4508 depth = var->lbchginfos[lbchginfopos].bdchgidx.depth;
4509 oldbound = var->lbchginfos[lbchginfopos].newbound;
4510 newbound = var->lbchginfos[lbchginfopos].oldbound;
4511 }
4512 }
4513
4514 /* calculate the increase in the proof's activity */
4515 SCIPquadprecSumDD(proofactdelta, newbound, -oldbound);
4516 SCIPquadprecProdQD(proofactdelta, proofactdelta, proofcoef);
4517 assert(QUAD_TO_DBL(proofactdelta) > 0.0);
4518
4519 /* calculate score for undoing the bound change */
4520 score = calcBdchgScore(prooflhs, proofact, QUAD_TO_DBL(proofactdelta), proofcoef, depth, currentdepth, var, set);
4521
4522 if( !resolvable )
4523 {
4524 score += 10.0;
4525 if( !SCIPvarIsBinary(var) )
4526 score += 10.0;
4527 }
4528
4529 /* get enough memory to store new candidate */
4530 SCIP_CALL( ensureCandsSize(set, cands, candscores, newbounds, proofactdeltas, candssize, (*ncands)+1) );
4531 assert(*cands != NULL);
4532 assert(*candscores != NULL);
4533 assert(*newbounds != NULL);
4534 assert(*proofactdeltas != NULL);
4535
4536 SCIPsetDebugMsg(set, " -> local <%s> %s %g, relax <%s> %s %g, proofcoef=%g, dpt=%d, resolve=%u, delta=%g, score=%g\n",
4537 SCIPvarGetName(var), proofcoef > 0.0 ? "<=" : ">=", oldbound,
4538 SCIPvarGetName(var), proofcoef > 0.0 ? "<=" : ">=", newbound,
4539 proofcoef, depth, resolvable, QUAD_TO_DBL(proofactdelta), score);
4540
4541 /* insert variable in candidate list without touching the already processed candidates */
4542 for( i = *ncands; i > firstcand && score > (*candscores)[i-1]; --i )
4543 {
4544 (*cands)[i] = (*cands)[i-1];
4545 (*candscores)[i] = (*candscores)[i-1];
4546 (*newbounds)[i] = (*newbounds)[i-1];
4547 (*proofactdeltas)[i] = (*proofactdeltas)[i-1];
4548 }
4549 (*cands)[i] = var;
4550 (*candscores)[i] = score;
4551 (*newbounds)[i] = newbound;
4552 (*proofactdeltas)[i] = QUAD_TO_DBL(proofactdelta);
4553 (*ncands)++;
4554
4555 return SCIP_OKAY;
4556}
4557
4558/** undoes bound changes on variables, still leaving the given infeasibility proof valid */
4560 SCIP_SET* set, /**< global SCIP settings */
4561 SCIP_PROB* prob, /**< problem data */
4562 int currentdepth, /**< current depth in the tree */
4563 SCIP_Real* proofcoefs, /**< coefficients in infeasibility proof */
4564 SCIP_Real prooflhs, /**< left hand side of proof */
4565 SCIP_Real* proofact, /**< current activity of proof */
4566 SCIP_Real* curvarlbs, /**< current lower bounds of active problem variables */
4567 SCIP_Real* curvarubs, /**< current upper bounds of active problem variables */
4568 int* lbchginfoposs, /**< positions of currently active lower bound change information in variables' arrays */
4569 int* ubchginfoposs, /**< positions of currently active upper bound change information in variables' arrays */
4570 SCIP_LPBDCHGS* oldlpbdchgs, /**< old LP bound changes used for reset the LP bound change, or NULL */
4571 SCIP_LPBDCHGS* relaxedlpbdchgs, /**< relaxed LP bound changes used for reset the LP bound change, or NULL */
4572 SCIP_Bool* resolve, /**< pointer to store whether the changed LP should be resolved again, or NULL */
4573 SCIP_LPI* lpi /**< pointer to LPi to access infinity of LP solver; necessary to set correct values */
4574 )
4575{
4576 SCIP_VAR** vars;
4577 SCIP_VAR** cands;
4578 SCIP_Real* candscores;
4579 SCIP_Real* newbounds;
4580 SCIP_Real* proofactdeltas;
4581 int nvars;
4582 int ncands;
4583 int candssize;
4584 int v;
4585 int i;
4586
4587 assert(prob != NULL);
4588 assert(proofcoefs != NULL);
4589 assert(SCIPsetIsFeasGT(set, prooflhs, (*proofact)));
4590 assert(curvarlbs != NULL);
4591 assert(curvarubs != NULL);
4592 assert(lbchginfoposs != NULL);
4593 assert(ubchginfoposs != NULL);
4594
4595 if( resolve != NULL )
4596 *resolve = FALSE;
4597
4598 vars = prob->vars;
4599 nvars = prob->nvars;
4600 assert(nvars == 0 || vars != NULL);
4601
4602 /* calculate the order in which the bound changes are tried to be undone, and relax all bounds if this doesn't
4603 * increase the proof's activity
4604 */
4605 SCIP_CALL( SCIPsetAllocBufferArray(set, &cands, nvars) );
4606 SCIP_CALL( SCIPsetAllocBufferArray(set, &candscores, nvars) );
4607 SCIP_CALL( SCIPsetAllocBufferArray(set, &newbounds, nvars) );
4608 SCIP_CALL( SCIPsetAllocBufferArray(set, &proofactdeltas, nvars) );
4609 ncands = 0;
4610 candssize = nvars;
4611 for( v = 0; v < nvars; ++v )
4612 {
4613 SCIP_VAR* var;
4614 SCIP_Bool relaxed;
4615
4616 var = vars[v];
4617
4618 /* after changing the global bound of a variable, the bdchginfos that are now redundant are replaced with
4619 * oldbound = newbound = global bound; if the current bdchginfo is of such kind, the bound is equal to the
4620 * global bound and we can ignore it
4621 */
4622 skipRedundantBdchginfos(var, &lbchginfoposs[v], &ubchginfoposs[v]);
4623
4624 /* ignore variables already relaxed to global bounds */
4625 if( (lbchginfoposs[v] == -1 && ubchginfoposs[v] == -1) )
4626 {
4627 proofcoefs[v] = 0.0;
4628 continue;
4629 }
4630
4631 /* relax bounds that are not used in the proof to the global bounds */
4632 relaxed = FALSE;
4633 if( !SCIPsetIsNegative(set, proofcoefs[v]) )
4634 {
4635 /* the lower bound is not used */
4636 if( lbchginfoposs[v] >= 0 )
4637 {
4638 SCIPsetDebugMsg(set, " -> relaxing variable <%s>[%g,%g] to [%g,%g]: proofcoef=%g, %g <= %g\n",
4639 SCIPvarGetName(var), curvarlbs[v], curvarubs[v], SCIPvarGetLbGlobal(var), curvarubs[v],
4640 proofcoefs[v], prooflhs, (*proofact));
4641 curvarlbs[v] = SCIPvarGetLbGlobal(var);
4642 lbchginfoposs[v] = -1;
4643 relaxed = TRUE;
4644 }
4645 }
4646 if( !SCIPsetIsPositive(set, proofcoefs[v]) )
4647 {
4648 /* the upper bound is not used */
4649 if( ubchginfoposs[v] >= 0 )
4650 {
4651 SCIPsetDebugMsg(set, " -> relaxing variable <%s>[%g,%g] to [%g,%g]: proofcoef=%g, %g <= %g\n",
4652 SCIPvarGetName(var), curvarlbs[v], curvarubs[v], curvarlbs[v], SCIPvarGetUbGlobal(var),
4653 proofcoefs[v], prooflhs, (*proofact));
4654 curvarubs[v] = SCIPvarGetUbGlobal(var);
4655 ubchginfoposs[v] = -1;
4656 relaxed = TRUE;
4657 }
4658 }
4659 if( relaxed && oldlpbdchgs != NULL )
4660 {
4661 SCIP_CALL( addBdchg(set, var, curvarlbs[v], curvarubs[v], oldlpbdchgs, relaxedlpbdchgs, lpi) );
4662 }
4663
4664 /* add bound to candidate list */
4665 if( lbchginfoposs[v] >= 0 || ubchginfoposs[v] >= 0 )
4666 {
4667 SCIP_CALL( addCand(set, currentdepth, var, lbchginfoposs[v], ubchginfoposs[v], proofcoefs[v],
4668 prooflhs, (*proofact), &cands, &candscores, &newbounds, &proofactdeltas, &candssize, &ncands, 0) );
4669 }
4670 /* we can set the proof coefficient to zero, because the variable is not needed */
4671 else
4672 proofcoefs[v] = 0.0;
4673 }
4674
4675 /* try to undo remaining local bound changes while still keeping the proof row violated:
4676 * bound changes can be undone, if prooflhs > proofact + proofactdelta;
4677 * afterwards, the current proof activity has to be updated
4678 */
4679 for( i = 0; i < ncands; ++i )
4680 {
4681 assert(proofactdeltas[i] > 0.0);
4682 assert((lbchginfoposs[SCIPvarGetProbindex(cands[i])] >= 0) != (ubchginfoposs[SCIPvarGetProbindex(cands[i])] >= 0));
4683
4684 /* when relaxing a constraint we still need to stay infeasible; therefore we need to do the comparison in
4685 * feasibility tolerance because if 'prooflhs' is (feas-))equal to 'proofact + proofactdeltas[i]' it would mean
4686 * that there is no violation
4687 */
4688 if( SCIPsetIsFeasGT(set, prooflhs, (*proofact) + proofactdeltas[i]) )
4689 {
4690 v = SCIPvarGetProbindex(cands[i]);
4691 assert(0 <= v && v < nvars);
4692 assert((lbchginfoposs[v] >= 0) != (ubchginfoposs[v] >= 0));
4693
4694 SCIPsetDebugMsg(set, " -> relaxing variable <%s>[%g,%g] to [%g,%g]: proofcoef=%g, %g <= %g + %g\n",
4695 SCIPvarGetName(cands[i]), curvarlbs[v], curvarubs[v],
4696 proofcoefs[v] > 0.0 ? curvarlbs[v] : newbounds[i],
4697 proofcoefs[v] > 0.0 ? newbounds[i] : curvarubs[v],
4698 proofcoefs[v], prooflhs, (*proofact), proofactdeltas[i]);
4699
4700#ifndef NDEBUG
4701 {
4702 SCIP_Real QUAD(verifylb);
4703 SCIP_Real QUAD(verifyub);
4704
4705 SCIPquadprecSumDD(verifylb, newbounds[i], -curvarlbs[v]);
4706 SCIPquadprecProdQD(verifylb, verifylb, proofcoefs[v]);
4707
4708 SCIPquadprecSumDD(verifyub, newbounds[i], -curvarubs[v]);
4709 SCIPquadprecProdQD(verifyub, verifyub, proofcoefs[v]);
4710
4711 assert((SCIPsetIsPositive(set, proofcoefs[v]) && SCIPsetIsGT(set, newbounds[i], curvarubs[v]))
4712 || (SCIPsetIsNegative(set, proofcoefs[v]) && SCIPsetIsLT(set, newbounds[i], curvarlbs[v])));
4713 assert((SCIPsetIsPositive(set, proofcoefs[v])
4714 && SCIPsetIsEQ(set, proofactdeltas[i], QUAD_TO_DBL(verifyub)))
4715 || (SCIPsetIsNegative(set, proofcoefs[v])
4716 && SCIPsetIsEQ(set, proofactdeltas[i], QUAD_TO_DBL(verifylb))));
4717 assert(!SCIPsetIsZero(set, proofcoefs[v]));
4718 }
4719#endif
4720
4721 if( proofcoefs[v] > 0.0 )
4722 {
4723 assert(ubchginfoposs[v] >= 0);
4724 assert(lbchginfoposs[v] == -1);
4725 curvarubs[v] = newbounds[i];
4726 ubchginfoposs[v]--;
4727 }
4728 else
4729 {
4730 assert(lbchginfoposs[v] >= 0);
4731 assert(ubchginfoposs[v] == -1);
4732 curvarlbs[v] = newbounds[i];
4733 lbchginfoposs[v]--;
4734 }
4735 if( oldlpbdchgs != NULL )
4736 {
4737 SCIP_CALL( addBdchg(set, cands[i], curvarlbs[v], curvarubs[v], oldlpbdchgs, relaxedlpbdchgs, lpi) );
4738 }
4739 (*proofact) += proofactdeltas[i];
4740 if( resolve != NULL && SCIPvarIsInLP(cands[i]) )
4741 *resolve = TRUE;
4742
4743 /* after changing the global bound of a variable, the bdchginfos that are now redundant are replaced with
4744 * oldbound = newbound = global bound; if the current bdchginfo is of such kind, the bound is equal to the
4745 * global bound and we can ignore it
4746 */
4747 skipRedundantBdchginfos(cands[i], &lbchginfoposs[v], &ubchginfoposs[v]);
4748
4749 /* insert the new local bound of the variable into the candidate list */
4750 if( lbchginfoposs[v] >= 0 || ubchginfoposs[v] >= 0 )
4751 {
4752 SCIP_CALL( addCand(set, currentdepth, cands[i], lbchginfoposs[v], ubchginfoposs[v], proofcoefs[v],
4753 prooflhs, (*proofact), &cands, &candscores, &newbounds, &proofactdeltas, &candssize, &ncands, i+1) );
4754 }
4755 else
4756 proofcoefs[v] = 0.0;
4757 }
4758 }
4759
4760 /* free the buffer for the sorted bound change candidates */
4761 SCIPsetFreeBufferArray(set, &proofactdeltas);
4762 SCIPsetFreeBufferArray(set, &newbounds);
4763 SCIPsetFreeBufferArray(set, &candscores);
4764 SCIPsetFreeBufferArray(set, &cands);
4765
4766 return SCIP_OKAY;
4767}
4768
4769/** analyzes an infeasible LP and undoes additional bound changes while staying infeasible */
4770static
4772 SCIP_SET* set, /**< global SCIP settings */
4773 SCIP_PROB* prob, /**< problem data */
4774 SCIP_LP* lp, /**< LP data */
4775 int currentdepth, /**< current depth in the tree */
4776 SCIP_Real* curvarlbs, /**< current lower bounds of active problem variables */
4777 SCIP_Real* curvarubs, /**< current upper bounds of active problem variables */
4778 int* lbchginfoposs, /**< positions of currently active lower bound change information in variables' arrays */
4779 int* ubchginfoposs, /**< positions of currently active upper bound change information in variables' arrays */
4780 SCIP_LPBDCHGS* oldlpbdchgs, /**< old LP bound changes used for reset the LP bound change, or NULL */
4781 SCIP_LPBDCHGS* relaxedlpbdchgs, /**< relaxed LP bound changes used for reset the LP bound change, or NULL */
4782 SCIP_Bool* valid, /**< pointer to store whether the unfixings are valid */
4783 SCIP_Bool* resolve, /**< pointer to store whether the changed LP should be resolved again */
4784 SCIP_Real* farkascoefs, /**< coefficients in the proof constraint */
4785 SCIP_Real farkaslhs, /**< lhs of the proof constraint */
4786 SCIP_Real* farkasactivity /**< maximal activity of the proof constraint */
4787 )
4788{
4789 SCIP_LPI* lpi;
4790
4791 assert(prob != NULL);
4792 assert(lp != NULL);
4793 assert(lp->flushed);
4794 assert(lp->solved);
4795 assert(curvarlbs != NULL);
4796 assert(curvarubs != NULL);
4797 assert(lbchginfoposs != NULL);
4798 assert(ubchginfoposs != NULL);
4799 assert(valid != NULL);
4800 assert(resolve != NULL);
4801
4802 SCIPsetDebugMsg(set, "undoing bound changes in infeasible LP: cutoff=%g\n", lp->cutoffbound);
4803
4804 *valid = FALSE;
4805 *resolve = FALSE;
4806
4807 lpi = SCIPlpGetLPI(lp);
4808
4809 /* check, if the Farkas row is still violated (using current bounds and ignoring local rows) */
4810 if( SCIPsetIsFeasGT(set, farkaslhs, *farkasactivity) )
4811 {
4812 /* undo bound changes while keeping the infeasibility proof valid */
4813 SCIP_CALL( SCIPundoBdchgsProof(set, prob, currentdepth, farkascoefs, farkaslhs, farkasactivity, \
4814 curvarlbs, curvarubs, lbchginfoposs, ubchginfoposs, oldlpbdchgs, relaxedlpbdchgs, resolve, lpi) );
4815
4816 *valid = TRUE;
4817
4818 /* resolving does not make sense: the old dual ray is still valid -> resolving will not change the solution */
4819 *resolve = FALSE;
4820 }
4821
4822 return SCIP_OKAY;
4823}
4824
4825
4826/*
4827 * Conflict LP Bound Changes
4828 */
4829
4830/** create conflict LP bound change data structure */
4831static
4833 SCIP_LPBDCHGS** lpbdchgs, /**< pointer to store the conflict LP bound change data structure */
4834 SCIP_SET* set, /**< global SCIP settings */
4835 int ncols /**< number of columns */
4836 )
4837{
4838 SCIP_CALL( SCIPsetAllocBuffer(set, lpbdchgs) );
4839
4840 SCIP_CALL( SCIPsetAllocBufferArray(set, &(*lpbdchgs)->bdchginds, ncols) );
4841 SCIP_CALL( SCIPsetAllocBufferArray(set, &(*lpbdchgs)->bdchglbs, ncols) );
4842 SCIP_CALL( SCIPsetAllocBufferArray(set, &(*lpbdchgs)->bdchgubs, ncols) );
4843 SCIP_CALL( SCIPsetAllocBufferArray(set, &(*lpbdchgs)->bdchgcolinds, ncols) );
4844 SCIP_CALL( SCIPsetAllocBufferArray(set, &(*lpbdchgs)->usedcols, ncols) );
4845 BMSclearMemoryArray((*lpbdchgs)->usedcols, ncols);
4846
4847 (*lpbdchgs)->nbdchgs = 0;
4848
4849 return SCIP_OKAY;
4850}
4851
4852
4853/*
4854 * Propagation Conflict Analysis
4855 */
4856
4857/** ensures, that side change arrays can store at least num entries */
4858static
4860 SCIP_SET* set, /**< global SCIP settings */
4861 int** sidechginds, /**< pointer to side change index array */
4862 SCIP_Real** sidechgoldlhss, /**< pointer to side change old left hand sides array */
4863 SCIP_Real** sidechgoldrhss, /**< pointer to side change old right hand sides array */
4864 SCIP_Real** sidechgnewlhss, /**< pointer to side change new left hand sides array */
4865 SCIP_Real** sidechgnewrhss, /**< pointer to side change new right hand sides array */
4866 int* sidechgssize, /**< pointer to size of side change arrays */
4867 int num /**< minimal number of entries to be able to store in side change arrays */
4868 )
4869{
4870 assert(sidechginds != NULL);
4871 assert(sidechgoldlhss != NULL);
4872 assert(sidechgoldrhss != NULL);
4873 assert(sidechgnewlhss != NULL);
4874 assert(sidechgnewrhss != NULL);
4875 assert(sidechgssize != NULL);
4876
4877 if( num > *sidechgssize )
4878 {
4879 int newsize;
4880
4881 newsize = SCIPsetCalcMemGrowSize(set, num);
4882 SCIP_CALL( SCIPsetReallocBufferArray(set, sidechginds, newsize) );
4883 SCIP_CALL( SCIPsetReallocBufferArray(set, sidechgoldlhss, newsize) );
4884 SCIP_CALL( SCIPsetReallocBufferArray(set, sidechgoldrhss, newsize) );
4885 SCIP_CALL( SCIPsetReallocBufferArray(set, sidechgnewlhss, newsize) );
4886 SCIP_CALL( SCIPsetReallocBufferArray(set, sidechgnewrhss, newsize) );
4887 *sidechgssize = newsize;
4888 }
4889 assert(num <= *sidechgssize);
4890
4891 return SCIP_OKAY;
4892}
4893
4894/** adds removal of row's side to side change arrays; finite sides are only replaced by near infinite sides, such
4895 * that the row's sense in the LP solver is not changed
4896 */
4897static
4899 SCIP_SET* set, /**< global SCIP settings */
4900 SCIP_ROW* row, /**< LP row to change the sides for */
4901 SCIP_Real lpiinfinity, /**< value treated as infinity in LP solver */
4902 int** sidechginds, /**< pointer to side change index array */
4903 SCIP_Real** sidechgoldlhss, /**< pointer to side change old left hand sides array */
4904 SCIP_Real** sidechgoldrhss, /**< pointer to side change old right hand sides array */
4905 SCIP_Real** sidechgnewlhss, /**< pointer to side change new left hand sides array */
4906 SCIP_Real** sidechgnewrhss, /**< pointer to side change new right hand sides array */
4907 int* sidechgssize, /**< pointer to size of side change arrays */
4908 int* nsidechgs /**< pointer to number of used slots in side change arrays */
4909 )
4910{
4911 SCIP_Real lhs;
4912 SCIP_Real rhs;
4913 SCIP_Real constant;
4914
4915 assert(sidechginds != NULL);
4916 assert(sidechgoldlhss != NULL);
4917 assert(sidechgoldrhss != NULL);
4918 assert(sidechgnewlhss != NULL);
4919 assert(sidechgnewrhss != NULL);
4920 assert(sidechgssize != NULL);
4921 assert(nsidechgs != NULL);
4922
4923 lhs = SCIProwGetLhs(row);
4924 rhs = SCIProwGetRhs(row);
4925 constant = SCIProwGetConstant(row);
4926 assert(!SCIPsetIsInfinity(set, -lhs) || !SCIPsetIsInfinity(set, rhs));
4927
4928 /* get memory to store additional side change */
4929 SCIP_CALL( ensureSidechgsSize(set, sidechginds, sidechgoldlhss, sidechgoldrhss, sidechgnewlhss, sidechgnewrhss, \
4930 sidechgssize, (*nsidechgs)+1) );
4931 assert(*nsidechgs < *sidechgssize);
4932 assert(*sidechginds != NULL);
4933 assert(*sidechgoldlhss != NULL);
4934 assert(*sidechgoldrhss != NULL);
4935 assert(*sidechgnewlhss != NULL);
4936 assert(*sidechgnewrhss != NULL);
4937
4938 /* store side change */
4939 (*sidechginds)[*nsidechgs] = SCIProwGetLPPos(row);
4940 if( SCIPsetIsInfinity(set, -lhs) )
4941 {
4942 (*sidechgoldlhss)[*nsidechgs] = -lpiinfinity;
4943 (*sidechgnewlhss)[*nsidechgs] = -lpiinfinity;
4944 }
4945 else
4946 {
4947 (*sidechgoldlhss)[*nsidechgs] = lhs - constant;
4948 (*sidechgnewlhss)[*nsidechgs] = -lpiinfinity;
4949 }
4950 if( SCIPsetIsInfinity(set, rhs) )
4951 {
4952 (*sidechgoldrhss)[*nsidechgs] = lpiinfinity;
4953 (*sidechgnewrhss)[*nsidechgs] = lpiinfinity;
4954 }
4955 else
4956 {
4957 (*sidechgoldrhss)[*nsidechgs] = rhs - constant;
4958 (*sidechgnewrhss)[*nsidechgs] = lpiinfinity;
4959 }
4960 (*nsidechgs)++;
4961
4962 return SCIP_OKAY;
4963}
4964
4965
4966/*
4967 * Infeasible LP Conflict Analysis
4968 */
4969
4970/** reset conflict LP bound change data structure */
4971static
4973 SCIP_LPBDCHGS* lpbdchgs, /**< conflict LP bound change data structure */
4974 int ncols /**< number of columns */
4975 )
4976{
4977 assert(lpbdchgs != NULL);
4978
4979 BMSclearMemoryArray(lpbdchgs->usedcols, ncols);
4980 lpbdchgs->nbdchgs = 0;
4981}
4982
4983/** free conflict LP bound change data structure */
4984static
4986 SCIP_LPBDCHGS** lpbdchgs, /**< pointer to store the conflict LP bound change data structure */
4987 SCIP_SET* set /**< global SCIP settings */
4988 )
4989{
4990 SCIPsetFreeBufferArray(set, &(*lpbdchgs)->usedcols);
4991 SCIPsetFreeBufferArray(set, &(*lpbdchgs)->bdchgcolinds);
4992 SCIPsetFreeBufferArray(set, &(*lpbdchgs)->bdchgubs);
4993 SCIPsetFreeBufferArray(set, &(*lpbdchgs)->bdchglbs);
4994 SCIPsetFreeBufferArray(set, &(*lpbdchgs)->bdchginds);
4995
4996 SCIPsetFreeBuffer(set, lpbdchgs);
4997}
4998
4999/** analyzes an LP exceeding the objective limit and undoes additional bound changes while staying beyond the
5000 * objective limit
5001 */
5002static
5004 SCIP_SET* set, /**< global SCIP settings */
5005 SCIP_PROB* prob, /**< problem data */
5006 SCIP_LP* lp, /**< LP data */
5007 int currentdepth, /**< current depth in the tree */
5008 SCIP_Real* curvarlbs, /**< current lower bounds of active problem variables */
5009 SCIP_Real* curvarubs, /**< current upper bounds of active problem variables */
5010 int* lbchginfoposs, /**< positions of currently active lower bound change information in variables' arrays */
5011 int* ubchginfoposs, /**< positions of currently active upper bound change information in variables' arrays */
5012 SCIP_LPBDCHGS* oldlpbdchgs, /**< old LP bound changes used for reset the LP bound change, or NULL */
5013 SCIP_LPBDCHGS* relaxedlpbdchgs, /**< relaxed LP bound changes used for reset the LP bound change, or NULL */
5014 SCIP_Bool* valid, /**< pointer to store whether the unfixings are valid */
5015 SCIP_Bool* resolve, /**< pointer to store whether the changed LP should be resolved again */
5016 SCIP_Real* dualcoefs, /**< coefficients in the proof constraint */
5017 SCIP_Real duallhs, /**< lhs of the proof constraint */
5018 SCIP_Real* dualactivity /**< maximal activity of the proof constraint */
5019 )
5020{
5021 SCIP_LPI* lpi;
5022
5023 assert(set != NULL);
5024 assert(prob != NULL);
5025 assert(lp != NULL);
5026 assert(lp->flushed);
5027 assert(lp->solved);
5028 assert(curvarlbs != NULL);
5029 assert(curvarubs != NULL);
5030 assert(lbchginfoposs != NULL);
5031 assert(ubchginfoposs != NULL);
5032 assert(valid != NULL);
5033 assert(resolve != NULL);
5034
5035 *valid = FALSE;
5036 *resolve = FALSE;
5037
5038 SCIPsetDebugMsg(set, "undoing bound changes in LP exceeding cutoff: cutoff=%g\n", lp->cutoffbound);
5039
5040 /* get LP solver interface */
5041 lpi = SCIPlpGetLPI(lp);
5042
5043 /* check, if the dual row is still violated (using current bounds and ignoring local rows) */
5044 if( SCIPsetIsFeasGT(set, duallhs, *dualactivity) )
5045 {
5046 /* undo bound changes while keeping the infeasibility proof valid */
5047 SCIP_CALL( SCIPundoBdchgsProof(set, prob, currentdepth, dualcoefs, duallhs, dualactivity, curvarlbs, curvarubs, \
5048 lbchginfoposs, ubchginfoposs, oldlpbdchgs, relaxedlpbdchgs, resolve, lpi) );
5049
5050 *valid = TRUE;
5051 }
5052
5053 return SCIP_OKAY;
5054}
5055
5056/** try to find a subset of changed bounds leading to an infeasible LP
5057 *
5058 * 1. call undoBdchgsDualfarkas() or undoBdchgsDualsol()
5059 * -> update lb/ubchginfoposs arrays
5060 * -> store additional changes in bdchg and curvarlbs/ubs arrays
5061 * -> apply additional changes to the LPI
5062 * 2. (optional) if additional bound changes were undone:
5063 * -> resolve LP
5064 * -> goto 1.
5065 * 3. redo all bound changes in the LPI to restore the LPI to its original state
5066 * 4. analyze conflict
5067 * -> put remaining changed bounds (see lb/ubchginfoposs arrays) into starting conflict set
5068 */
5070 SCIP_CONFLICT* conflict, /**< conflict data */
5071 SCIP_SET* set, /**< global SCIP settings */
5072 SCIP_STAT* stat, /**< problem statistics */
5073 SCIP_PROB* origprob, /**< original problem */
5074 SCIP_PROB* transprob, /**< transformed problem */
5075 SCIP_TREE* tree, /**< branch and bound tree */
5076 SCIP_REOPT* reopt, /**< reoptimization data */
5077 SCIP_LP* lp, /**< LP data */
5078 SCIP_LPI* lpi, /**< LPI data */
5079 BMS_BLKMEM* blkmem, /**< block memory */
5080 SCIP_Real* proofcoefs, /**< coefficients in the proof constraint */
5081 SCIP_Real* prooflhs, /**< lhs of the proof constraint */
5082 SCIP_Real* proofactivity, /**< maximal activity of the proof constraint */
5083 SCIP_Real* curvarlbs, /**< current lower bounds of active problem variables */
5084 SCIP_Real* curvarubs, /**< current upper bounds of active problem variables */
5085 int* lbchginfoposs, /**< positions of currently active lower bound change information in variables' arrays */
5086 int* ubchginfoposs, /**< positions of currently active upper bound change information in variables' arrays */
5087 int* iterations, /**< pointer to store the total number of LP iterations used */
5088 SCIP_Bool marklpunsolved, /**< whether LP should be marked unsolved after analysis (needed for strong branching) */
5089 SCIP_Bool* dualproofsuccess, /**< pointer to store success result of dual proof analysis */
5090 SCIP_Bool* valid /**< pointer to store whether the result is still a valid proof */
5091 )
5092{
5093 SCIP_LPBDCHGS* oldlpbdchgs;
5094 SCIP_LPBDCHGS* relaxedlpbdchgs;
5095 SCIP_Bool solvelp;
5096 SCIP_Bool resolve;
5097 int ncols;
5098
5099 assert(set != NULL);
5100
5101 /* get number of columns in the LP */
5102 ncols = SCIPlpGetNCols(lp);
5103
5104 /* get temporary memory for remembering bound changes on LPI columns */
5105 SCIP_CALL( lpbdchgsCreate(&oldlpbdchgs, set, ncols) );
5106 SCIP_CALL( lpbdchgsCreate(&relaxedlpbdchgs, set, ncols) );
5107
5108 /* undo as many bound changes as possible with the current LP solution */
5109 resolve = FALSE;
5110 if( (*valid) )
5111 {
5112 int currentdepth;
5113 currentdepth = SCIPtreeGetCurrentDepth(tree);
5114
5115 if( SCIPlpiIsPrimalInfeasible(lpi) )
5116 {
5117 SCIP_CALL( undoBdchgsDualfarkas(set, transprob, lp, currentdepth, curvarlbs, curvarubs, lbchginfoposs, \
5118 ubchginfoposs, oldlpbdchgs, relaxedlpbdchgs, valid, &resolve, proofcoefs, *prooflhs, proofactivity) );
5119 }
5120 else
5121 {
5122 assert(SCIPlpiIsDualFeasible(lpi) || SCIPlpiIsObjlimExc(lpi));
5123 SCIP_CALL( undoBdchgsDualsol(set, transprob, lp, currentdepth, curvarlbs, curvarubs, lbchginfoposs, ubchginfoposs, \
5124 oldlpbdchgs, relaxedlpbdchgs, valid, &resolve, proofcoefs, *prooflhs, proofactivity) );
5125 }
5126 }
5127
5128 /* check if we want to solve the LP */
5129 assert(SCIPprobAllColsInLP(transprob, set, lp));
5130 solvelp = (set->conf_maxlploops != 0 && set->conf_lpiterations != 0);
5131
5132 if( (*valid) && resolve && solvelp )
5133 {
5134 SCIP_RETCODE retcode;
5135 SCIP_ROW** rows;
5136 int* sidechginds;
5137 SCIP_Real* sidechgoldlhss;
5138 SCIP_Real* sidechgoldrhss;
5139 SCIP_Real* sidechgnewlhss;
5140 SCIP_Real* sidechgnewrhss;
5141 SCIP_Real lpiinfinity;
5142 SCIP_Bool globalinfeasible;
5143 int maxlploops;
5144 int lpiterations;
5145 int sidechgssize;
5146 int nsidechgs;
5147 int nrows;
5148 int nloops;
5149 int r;
5150
5151 /* get infinity value of LP solver */
5152 lpiinfinity = SCIPlpiInfinity(lpi);
5153
5154 /* temporarily disable objective limit and install an iteration limit */
5155 maxlploops = (set->conf_maxlploops >= 0 ? set->conf_maxlploops : INT_MAX);
5156 lpiterations = (set->conf_lpiterations >= 0 ? set->conf_lpiterations : INT_MAX);
5157 SCIP_CALL( SCIPlpiSetRealpar(lpi, SCIP_LPPAR_OBJLIM, lpiinfinity) );
5158 SCIP_CALL( SCIPlpiSetIntpar(lpi, SCIP_LPPAR_LPITLIM, lpiterations) );
5159
5160 /* get LP rows */
5161 rows = SCIPlpGetRows(lp);
5162 nrows = SCIPlpGetNRows(lp);
5163 assert(nrows == 0 || rows != NULL);
5164
5165 /* get temporary memory for remembering side changes on LPI rows */
5166 SCIP_CALL( SCIPsetAllocBufferArray(set, &sidechginds, nrows) );
5167 SCIP_CALL( SCIPsetAllocBufferArray(set, &sidechgoldlhss, nrows) );
5168 SCIP_CALL( SCIPsetAllocBufferArray(set, &sidechgoldrhss, nrows) );
5169 SCIP_CALL( SCIPsetAllocBufferArray(set, &sidechgnewlhss, nrows) );
5170 SCIP_CALL( SCIPsetAllocBufferArray(set, &sidechgnewrhss, nrows) );
5171 sidechgssize = nrows;
5172 nsidechgs = 0;
5173
5174 /* remove all local rows by setting their sides to infinity;
5175 * finite sides are only changed to near infinity, such that the row's sense in the LP solver
5176 * is not affected (e.g. CPLEX cannot handle free rows)
5177 */
5178 for( r = 0; r < nrows; ++r )
5179 {
5180 assert(SCIProwGetLPPos(rows[r]) == r);
5181
5182 if( SCIProwIsLocal(rows[r]) )
5183 {
5184 SCIPsetDebugMsg(set, " -> removing local row <%s> [%g,%g]\n",
5185 SCIProwGetName(rows[r]), SCIProwGetLhs(rows[r]), SCIProwGetRhs(rows[r]));
5186 SCIP_CALL( addSideRemoval(set, rows[r], lpiinfinity, &sidechginds, &sidechgoldlhss, &sidechgoldrhss,
5187 &sidechgnewlhss, &sidechgnewrhss, &sidechgssize, &nsidechgs) );
5188 }
5189 }
5190
5191 /* apply changes of local rows to the LP solver */
5192 if( nsidechgs > 0 )
5193 {
5194 SCIP_CALL( SCIPlpiChgSides(lpi, nsidechgs, sidechginds, sidechgnewlhss, sidechgnewrhss) );
5195 }
5196
5197 /* undo as many additional bound changes as possible by resolving the LP */
5198 assert((*valid));
5199 assert(resolve);
5200 nloops = 0;
5201 globalinfeasible = FALSE;
5202 while( (*valid) && resolve && nloops < maxlploops )
5203 {
5204 int iter;
5205
5206 assert(!globalinfeasible);
5207
5208 nloops++;
5209 resolve = FALSE;
5210
5211 SCIPsetDebugMsg(set, "infeasible LP conflict analysis loop %d (changed col bounds: %d)\n", nloops, relaxedlpbdchgs->nbdchgs);
5212
5213 /* apply bound changes to the LP solver */
5214 assert(relaxedlpbdchgs->nbdchgs >= 0);
5215 if( relaxedlpbdchgs->nbdchgs > 0 )
5216 {
5217 SCIPsetDebugMsg(set, " -> applying %d bound changes to the LP solver\n", relaxedlpbdchgs->nbdchgs);
5218 SCIP_CALL( SCIPlpiChgBounds(lpi, relaxedlpbdchgs->nbdchgs, relaxedlpbdchgs->bdchginds, \
5219 relaxedlpbdchgs->bdchglbs, relaxedlpbdchgs->bdchgubs) );
5220
5221 /* reset conflict LP bound change data structure */
5222 lpbdchgsReset(relaxedlpbdchgs, ncols);
5223 }
5224
5225 /* start LP timer */
5227
5228 /* resolve LP */
5229 retcode = SCIPlpiSolveDual(lpi);
5230
5231 /* stop LP timer */
5233
5234 /* check return code of LP solving call */
5235 if( retcode == SCIP_LPERROR )
5236 {
5237 (*valid) = FALSE;
5238 break;
5239 }
5240 SCIP_CALL( retcode );
5241
5242 /* count number of LP iterations */
5243 SCIP_CALL( SCIPlpiGetIterations(lpi, &iter) );
5244 (*iterations) += iter;
5245 stat->nconflictlps++;
5246 stat->nconflictlpiterations += iter;
5247 SCIPsetDebugMsg(set, " -> resolved LP in %d iterations (total: %" SCIP_LONGINT_FORMAT ") (infeasible:%u)\n",
5249
5250 /* evaluate result */
5251 if( SCIPlpiIsDualFeasible(lpi) || SCIPlpiIsObjlimExc(lpi) )
5252 {
5253 SCIP_Real objval;
5254
5255 SCIP_CALL( SCIPlpiGetObjval(lpi, &objval) );
5256 (*valid) = (objval >= lp->lpiobjlim && !SCIPlpDivingObjChanged(lp));
5257 }
5258 else
5259 (*valid) = SCIPlpiIsPrimalInfeasible(lpi);
5260
5261 if( (*valid) )
5262 {
5263 int currentdepth;
5264 currentdepth = SCIPtreeGetCurrentDepth(tree);
5265
5266 /* undo additional bound changes */
5267 if( SCIPlpiIsPrimalInfeasible(lpi) )
5268 {
5269 SCIP_AGGRROW* farkasrow;
5270 int* inds;
5271 int validdepth;
5272 int nnz;
5273 int v;
5274
5275#ifndef NDEBUG
5276 SCIP_VAR** vars = SCIPprobGetVars(transprob);
5277#endif
5278
5279 SCIP_CALL( SCIPaggrRowCreate(set->scip, &farkasrow) );
5280
5281 /* the original LP exceeds the current cutoff bound, thus, we have not constructed the Farkas proof */
5282 SCIP_CALL( SCIPgetFarkasProof(set, transprob, lp, lpi, tree, farkasrow, proofactivity, &validdepth,
5283 curvarlbs, curvarubs, valid) );
5284
5285 /* the constructed Farkas proof is not valid, we need to break here */
5286 if( !(*valid) )
5287 {
5288 SCIPaggrRowFree(set->scip, &farkasrow);
5289 break;
5290 }
5291
5292 /* start dual proof analysis */
5293 if( set->conf_useinflp == 'd' || set->conf_useinflp == 'b' )
5294 {
5295 /* change the conflict type */
5296 SCIP_CONFTYPE oldconftype = conflict->conflictset->conflicttype;
5298
5299 /* start dual proof analysis */
5300 SCIP_CALL( SCIPconflictAnalyzeDualProof(conflict, set, stat, blkmem, origprob, transprob, tree, reopt, lp, \
5301 farkasrow, validdepth, curvarlbs, curvarubs, FALSE, &globalinfeasible, dualproofsuccess) );
5302
5303 conflict->conflictset->conflicttype = oldconftype;
5304 }
5305
5306 /* todo: in theory, we could apply conflict graph analysis for locally valid proofs, too, but this needs to be implemented */
5307 if( globalinfeasible || validdepth > SCIPtreeGetEffectiveRootDepth(tree) )
5308 {
5309 SCIPaggrRowFree(set->scip, &farkasrow);
5310 goto TERMINATE;
5311 }
5312
5313 BMSclearMemoryArray(proofcoefs, SCIPprobGetNVars(transprob));
5314 (*prooflhs) = -SCIPaggrRowGetRhs(farkasrow);
5315 (*proofactivity) = -(*proofactivity);
5316
5317 inds = SCIPaggrRowGetInds(farkasrow);
5318 nnz = SCIPaggrRowGetNNz(farkasrow);
5319
5320 for( v = 0; v < nnz; v++ )
5321 {
5322 int i = inds[v];
5323
5324 assert(SCIPvarGetProbindex(vars[i]) == inds[v]);
5325
5326 proofcoefs[i] = -SCIPaggrRowGetProbvarValue(farkasrow, i);
5327 }
5328
5329 /* free aggregation rows */
5330 SCIPaggrRowFree(set->scip, &farkasrow);
5331
5332 SCIP_CALL( undoBdchgsDualfarkas(set, transprob, lp, currentdepth, curvarlbs, curvarubs, lbchginfoposs, \
5333 ubchginfoposs, oldlpbdchgs, relaxedlpbdchgs, valid, &resolve, proofcoefs, (*prooflhs), proofactivity) );
5334 }
5335 else
5336 {
5337 SCIP_AGGRROW* proofrow;
5338 int* inds;
5339 int validdepth;
5340 int nnz;
5341 int v;
5342
5343#ifndef NDEBUG
5344 SCIP_VAR** vars = SCIPprobGetVars(transprob);
5345#endif
5346
5347 assert(SCIPlpiIsDualFeasible(lpi) || SCIPlpiIsObjlimExc(lpi));
5348
5349 SCIP_CALL( SCIPaggrRowCreate(set->scip, &proofrow) );
5350
5351 SCIP_CALL( SCIPgetDualProof(set, transprob, lp, lpi, tree, proofrow, proofactivity, &validdepth,
5352 curvarlbs, curvarubs, valid) );
5353
5354 /* the constructed dual proof is not valid, we need to break here */
5355 if( !(*valid) || validdepth > SCIPtreeGetEffectiveRootDepth(tree) )
5356 {
5357 SCIPaggrRowFree(set->scip, &proofrow);
5358 break;
5359 }
5360 /* in contrast to the infeasible case we don't want to analyze the (probably identical) proof again. */
5361
5362 BMSclearMemoryArray(proofcoefs, SCIPprobGetNVars(transprob));
5363 (*prooflhs) = -SCIPaggrRowGetRhs(proofrow);
5364 (*proofactivity) = -(*proofactivity);
5365
5366 inds = SCIPaggrRowGetInds(proofrow);
5367 nnz = SCIPaggrRowGetNNz(proofrow);
5368
5369 for( v = 0; v < nnz; v++ )
5370 {
5371 int i = inds[v];
5372
5373 assert(SCIPvarGetProbindex(vars[i]) == inds[v]);
5374
5375 proofcoefs[i] = -SCIPaggrRowGetProbvarValue(proofrow, i);
5376 }
5377
5378 /* free aggregation rows */
5379 SCIPaggrRowFree(set->scip, &proofrow);
5380
5381 SCIP_CALL( undoBdchgsDualsol(set, transprob, lp, currentdepth, curvarlbs, curvarubs, lbchginfoposs, \
5382 ubchginfoposs, oldlpbdchgs, relaxedlpbdchgs, valid, &resolve, proofcoefs, *prooflhs, proofactivity) );
5383 }
5384 }
5385 assert(!resolve || (*valid));
5386 assert(!resolve || relaxedlpbdchgs->nbdchgs > 0);
5387 SCIPsetDebugMsg(set, " -> finished infeasible LP conflict analysis loop %d (iter: %d, nbdchgs: %d)\n",
5388 nloops, iter, relaxedlpbdchgs->nbdchgs);
5389 }
5390
5391 SCIPsetDebugMsg(set, "finished undoing bound changes after %d loops (valid=%u, nbdchgs: %d)\n",
5392 nloops, (*valid), oldlpbdchgs->nbdchgs);
5393
5394 TERMINATE:
5395 /* reset variables to local bounds */
5396 if( oldlpbdchgs->nbdchgs > 0 )
5397 {
5398 SCIP_CALL( SCIPlpiChgBounds(lpi, oldlpbdchgs->nbdchgs, oldlpbdchgs->bdchginds, oldlpbdchgs->bdchglbs, oldlpbdchgs->bdchgubs) );
5399 }
5400
5401 /* reset changes of local rows */
5402 if( nsidechgs > 0 )
5403 {
5404 SCIP_CALL( SCIPlpiChgSides(lpi, nsidechgs, sidechginds, sidechgoldlhss, sidechgoldrhss) );
5405 }
5406
5407 /* mark the LP unsolved */
5408 if( oldlpbdchgs->nbdchgs > 0 || nsidechgs > 0 )
5409 {
5410 /* The LPI data are out of sync with LP data. Thus, the LP should be marked
5411 * unsolved. However, for strong branching calls, the LP has to have status 'solved'; in
5412 * this case, marklpunsolved is FALSE and synchronization is performed later. */
5413 if ( marklpunsolved )
5414 {
5415 lp->solved = FALSE;
5416 lp->primalfeasible = FALSE;
5417 lp->primalchecked = FALSE;
5418 lp->dualfeasible = FALSE;
5419 lp->dualchecked = FALSE;
5420 lp->lpobjval = SCIP_INVALID;
5422 }
5423 }
5424
5425 /* reinstall old objective and iteration limits in LP solver */
5428
5429 /* free temporary memory */
5430 SCIPsetFreeBufferArray(set, &sidechgnewrhss);
5431 SCIPsetFreeBufferArray(set, &sidechgnewlhss);
5432 SCIPsetFreeBufferArray(set, &sidechgoldrhss);
5433 SCIPsetFreeBufferArray(set, &sidechgoldlhss);
5434 SCIPsetFreeBufferArray(set, &sidechginds);
5435 }
5436
5437 /* free temporary memory */
5438 lpbdchgsFree(&relaxedlpbdchgs, set);
5439 lpbdchgsFree(&oldlpbdchgs, set);
5440
5441 return SCIP_OKAY;
5442}
5443
5444/** analyzes conflicting bound changes that were added with calls to SCIPconflictAddBound(), and on success, calls the
5445 * conflict handlers to create a conflict constraint out of the resulting conflict set;
5446 * updates statistics for propagation conflict analysis
5447 */
5449 SCIP_CONFLICT* conflict, /**< conflict analysis data */
5450 BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
5451 SCIP_SET* set, /**< global SCIP settings */
5452 SCIP_STAT* stat, /**< problem statistics */
5453 SCIP_PROB* prob, /**< problem data */
5454 SCIP_TREE* tree, /**< branch and bound tree */
5455 int validdepth, /**< minimal depth level at which the initial conflict set is valid */
5456 SCIP_Bool* success /**< pointer to store whether a conflict constraint was created, or NULL */
5457 )
5458{
5459 int nconss;
5460 int nliterals;
5461 int nreconvconss;
5462 int nreconvliterals;
5463
5464 assert(conflict != NULL);
5465 assert(conflict->conflictset != NULL);
5466 assert(set != NULL);
5467 assert(prob != NULL);
5468
5469 if( success != NULL )
5470 *success = FALSE;
5471
5472 /* check if the conflict analysis is applicable */
5474 return SCIP_OKAY;
5475
5476 /* check, if the conflict set will get too large with high probability */
5477 if( conflict->conflictset->nbdchginfos + SCIPpqueueNElems(conflict->bdchgqueue)
5478 + SCIPpqueueNElems(conflict->forcedbdchgqueue) >= 2*conflictCalcMaxsize(set, prob) )
5479 return SCIP_OKAY;
5480
5481 SCIPsetDebugMsg(set, "analyzing conflict after infeasible propagation in depth %d\n", SCIPtreeGetCurrentDepth(tree));
5482
5483 /* start timing */
5485
5486 conflict->npropcalls++;
5487
5488 /* analyze the conflict set, and create a conflict constraint on success */
5489 SCIP_CALL( conflictAnalyze(conflict, blkmem, set, stat, prob, tree, FALSE, validdepth, TRUE, &nconss, &nliterals, \
5490 &nreconvconss, &nreconvliterals) );
5491 conflict->npropsuccess += (nconss > 0 ? 1 : 0);
5492 conflict->npropconfconss += nconss;
5493 conflict->npropconfliterals += nliterals;
5494 conflict->npropreconvconss += nreconvconss;
5495 conflict->npropreconvliterals += nreconvliterals;
5496 if( success != NULL )
5497 *success = (nconss > 0);
5498
5499 /* stop timing */
5500 SCIPclockStop(conflict->propanalyzetime, set);
5501
5502 return SCIP_OKAY;
5503}
static long bound
SCIP_VAR * h
Definition: circlepacking.c:68
SCIP_Real * r
Definition: circlepacking.c:59
void SCIPclockStop(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:360
void SCIPclockEnableOrDisable(SCIP_CLOCK *clck, SCIP_Bool enable)
Definition: clock.c:260
void SCIPclockStart(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:290
SCIP_Real SCIPclockGetTime(SCIP_CLOCK *clck)
Definition: clock.c:438
void SCIPclockReset(SCIP_CLOCK *clck)
Definition: clock.c:209
void SCIPclockFree(SCIP_CLOCK **clck)
Definition: clock.c:185
SCIP_RETCODE SCIPclockCreate(SCIP_CLOCK **clck, SCIP_CLOCKTYPE clocktype)
Definition: clock.c:170
internal methods for clocks and timing issues
internal methods for conflict analysis
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)
internal methods for dual proof conflict analysis
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)
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)
void SCIPconflictsetFree(SCIP_CONFLICTSET **conflictset, BMS_BLKMEM *blkmem)
static SCIP_Bool conflictsetIsRedundant(SCIP_CONFLICTSET *conflictset1, SCIP_CONFLICTSET *conflictset2)
static SCIP_RETCODE detectImpliedBounds(SCIP_SET *set, SCIP_PROB *prob, SCIP_STAT *stat, SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_PROB *origprob, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_CONFLICTSET *conflictset, int *nbdchgs, int *nredvars, SCIP_Bool *redundant)
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)
static SCIP_RETCODE ensureSidechgsSize(SCIP_SET *set, int **sidechginds, SCIP_Real **sidechgoldlhss, SCIP_Real **sidechgoldrhss, SCIP_Real **sidechgnewlhss, SCIP_Real **sidechgnewrhss, int *sidechgssize, int num)
static SCIP_RETCODE conflictQueueBound(SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_BDCHGINFO *bdchginfo, SCIP_Real relaxedbd)
static SCIP_RETCODE undoBdchgsDualsol(SCIP_SET *set, SCIP_PROB *prob, SCIP_LP *lp, int currentdepth, SCIP_Real *curvarlbs, SCIP_Real *curvarubs, int *lbchginfoposs, int *ubchginfoposs, SCIP_LPBDCHGS *oldlpbdchgs, SCIP_LPBDCHGS *relaxedlpbdchgs, SCIP_Bool *valid, SCIP_Bool *resolve, SCIP_Real *dualcoefs, SCIP_Real duallhs, SCIP_Real *dualactivity)
static void conflictClear(SCIP_CONFLICT *conflict)
void SCIPconflicthdlrEnableOrDisableClocks(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_Bool enable)
SCIP_RETCODE conflictCreateTmpBdchginfo(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_Real oldbound, SCIP_Real newbound, SCIP_BDCHGINFO **bdchginfo)
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)
static SCIP_RETCODE conflictEnsureTmpbdchginfosMem(SCIP_CONFLICT *conflict, SCIP_SET *set, int num)
static SCIP_Bool isBoundchgUseless(SCIP_SET *set, SCIP_BDCHGINFO *bdchginfo)
SCIP_RETCODE SCIPconflicthdlrCreate(SCIP_CONFLICTHDLR **conflicthdlr, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int priority, SCIP_DECL_CONFLICTCOPY((*conflictcopy)), SCIP_DECL_CONFLICTFREE((*conflictfree)), SCIP_DECL_CONFLICTINIT((*conflictinit)), SCIP_DECL_CONFLICTEXIT((*conflictexit)), SCIP_DECL_CONFLICTINITSOL((*conflictinitsol)), SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol)), SCIP_DECL_CONFLICTEXEC((*conflictexec)), SCIP_CONFLICTHDLRDATA *conflicthdlrdata)
static void conflictsetCalcConflictDepth(SCIP_CONFLICTSET *conflictset)
SCIP_RETCODE SCIPconflicthdlrExit(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set)
static SCIP_Bool bdchginfoIsInvalid(SCIP_CONFLICT *conflict, SCIP_BDCHGINFO *bdchginfo)
static SCIP_Real calcBdchgScore(SCIP_Real prooflhs, SCIP_Real proofact, SCIP_Real proofactdelta, SCIP_Real proofcoef, int depth, int currentdepth, SCIP_VAR *var, SCIP_SET *set)
void SCIPconflicthdlrSetInit(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_DECL_CONFLICTINIT((*conflictinit)))
int conflictCalcMaxsize(SCIP_SET *set, SCIP_PROB *prob)
void SCIPconflicthdlrSetPriority(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set, int priority)
SCIP_RETCODE SCIPconflictAddBound(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx)
static SCIP_RETCODE conflictAddConflictCons(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_CONFLICTSET *conflictset, int insertdepth, SCIP_Bool *success)
SCIP_RETCODE SCIPconflicthdlrFree(SCIP_CONFLICTHDLR **conflicthdlr, SCIP_SET *set)
SCIP_RETCODE SCIPconflictAnalyze(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_TREE *tree, int validdepth, SCIP_Bool *success)
static SCIP_RETCODE undoBdchgsDualfarkas(SCIP_SET *set, SCIP_PROB *prob, SCIP_LP *lp, int currentdepth, SCIP_Real *curvarlbs, SCIP_Real *curvarubs, int *lbchginfoposs, int *ubchginfoposs, SCIP_LPBDCHGS *oldlpbdchgs, SCIP_LPBDCHGS *relaxedlpbdchgs, SCIP_Bool *valid, SCIP_Bool *resolve, SCIP_Real *farkascoefs, SCIP_Real farkaslhs, SCIP_Real *farkasactivity)
static SCIP_RETCODE addCand(SCIP_SET *set, int currentdepth, SCIP_VAR *var, int lbchginfopos, int ubchginfopos, SCIP_Real proofcoef, SCIP_Real prooflhs, SCIP_Real proofact, SCIP_VAR ***cands, SCIP_Real **candscores, SCIP_Real **newbounds, SCIP_Real **proofactdeltas, int *candssize, int *ncands, int firstcand)
static SCIP_RETCODE addBdchg(SCIP_SET *set, SCIP_VAR *var, SCIP_Real newlb, SCIP_Real newub, SCIP_LPBDCHGS *oldlpbdchgs, SCIP_LPBDCHGS *relaxedlpbdchgs, SCIP_LPI *lpi)
static SCIP_RETCODE conflictCreateReconvergenceConss(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_TREE *tree, SCIP_Bool diving, int validdepth, SCIP_BDCHGINFO *firstuip, int *nreconvconss, int *nreconvliterals)
SCIP_RETCODE SCIPconflicthdlrExitsol(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set)
SCIP_Bool SCIPconflictApplicable(SCIP_SET *set)
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)
static SCIP_RETCODE conflictResolveBound(SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_BDCHGINFO *bdchginfo, SCIP_Real relaxedbd, int validdepth, SCIP_Bool *resolved)
static void conflictsetClear(SCIP_CONFLICTSET *conflictset)
SCIP_RETCODE SCIPconflictAddRelaxedBound(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd)
void SCIPconflicthdlrSetFree(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_DECL_CONFLICTFREE((*conflictfree)))
static SCIP_Real conflictsetCalcScore(SCIP_CONFLICTSET *conflictset, SCIP_SET *set)
void SCIPconflicthdlrSetExitsol(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol)))
static SCIP_RETCODE conflictAddConflictBound(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_BDCHGINFO *bdchginfo, SCIP_Real relaxedbd)
static SCIP_RETCODE lpbdchgsCreate(SCIP_LPBDCHGS **lpbdchgs, SCIP_SET *set, int ncols)
static SCIP_RETCODE doConflicthdlrCreate(SCIP_CONFLICTHDLR **conflicthdlr, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int priority, SCIP_DECL_CONFLICTCOPY((*conflictcopy)), SCIP_DECL_CONFLICTFREE((*conflictfree)), SCIP_DECL_CONFLICTINIT((*conflictinit)), SCIP_DECL_CONFLICTEXIT((*conflictexit)), SCIP_DECL_CONFLICTINITSOL((*conflictinitsol)), SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol)), SCIP_DECL_CONFLICTEXEC((*conflictexec)), SCIP_CONFLICTHDLRDATA *conflicthdlrdata)
static SCIP_RETCODE conflictsetCopy(SCIP_CONFLICTSET **targetconflictset, BMS_BLKMEM *blkmem, SCIP_CONFLICTSET *sourceconflictset, int nadditionalelems)
static SCIP_RETCODE conflictsetAddBound(SCIP_CONFLICTSET *conflictset, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_BDCHGINFO *bdchginfo, SCIP_Real relaxedbd)
static SCIP_Bool conflictMarkBoundCheckPresence(SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_BDCHGINFO *bdchginfo, SCIP_Real relaxedbd)
SCIP_RETCODE SCIPconflicthdlrCopyInclude(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set)
void SCIPconflicthdlrSetExit(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_DECL_CONFLICTEXIT((*conflictexit)))
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)
static SCIP_RETCODE conflictsetAddBounds(SCIP_CONFLICT *conflict, SCIP_CONFLICTSET *conflictset, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_BDCHGINFO **bdchginfos, int nbdchginfos)
static SCIP_RETCODE addSideRemoval(SCIP_SET *set, SCIP_ROW *row, SCIP_Real lpiinfinity, int **sidechginds, SCIP_Real **sidechgoldlhss, SCIP_Real **sidechgoldrhss, SCIP_Real **sidechgnewlhss, SCIP_Real **sidechgnewrhss, int *sidechgssize, int *nsidechgs)
static SCIP_RETCODE convertToActiveVar(SCIP_VAR **var, SCIP_SET *set, SCIP_BOUNDTYPE *boundtype, SCIP_Real *bound)
static SCIP_RETCODE incVSIDS(SCIP_VAR *var, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_BOUNDTYPE boundtype, SCIP_Real value, SCIP_Real weight)
static SCIP_Bool bdchginfoIsResolvable(SCIP_BDCHGINFO *bdchginfo)
SCIP_RETCODE conflictAnalyze(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_TREE *tree, SCIP_Bool diving, int validdepth, SCIP_Bool mustresolve, int *nconss, int *nliterals, int *nreconvconss, int *nreconvliterals)
void SCIPconflicthdlrSetCopy(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_DECL_CONFLICTCOPY((*conflictcopy)))
static SCIP_Bool checkRedundancy(SCIP_SET *set, SCIP_CONFLICTSET *conflictset)
static void lpbdchgsReset(SCIP_LPBDCHGS *lpbdchgs, int ncols)
SCIP_RETCODE SCIPconflictIsVarUsed(SCIP_CONFLICT *conflict, SCIP_VAR *var, SCIP_SET *set, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool *used)
static SCIP_RETCODE conflictAddBound(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGINFO *bdchginfo, SCIP_Real relaxedbd)
SCIP_RETCODE SCIPconflictsetCreate(SCIP_CONFLICTSET **conflictset, BMS_BLKMEM *blkmem)
static SCIP_RETCODE conflictsetCalcInsertDepth(SCIP_CONFLICTSET *conflictset, SCIP_SET *set, SCIP_TREE *tree)
static SCIP_BDCHGINFO * conflictRemoveCand(SCIP_CONFLICT *conflict)
static SCIP_DECL_PARAMCHGD(paramChgdConflicthdlrPriority)
static SCIP_RETCODE conflictsetEnsureBdchginfosMem(SCIP_CONFLICTSET *conflictset, BMS_BLKMEM *blkmem, SCIP_SET *set, int num)
static SCIP_BDCHGINFO * conflictFirstCand(SCIP_CONFLICT *conflict)
SCIP_RETCODE SCIPconflictInit(SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_CONFTYPE conftype, SCIP_Bool usescutoffbound)
static SCIP_RETCODE ensureCandsSize(SCIP_SET *set, SCIP_VAR ***cands, SCIP_Real **candscores, SCIP_Real **newbounds, SCIP_Real **proofactdeltas, int *candssize, int num)
SCIP_RETCODE SCIPconflicthdlrExec(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set, SCIP_NODE *node, SCIP_NODE *validnode, SCIP_BDCHGINFO **bdchginfos, SCIP_Real *relaxedbds, int nbdchginfos, SCIP_CONFTYPE conftype, SCIP_Bool usescutoffbound, SCIP_Bool resolved, SCIP_RESULT *result)
SCIP_RETCODE SCIPconflicthdlrInitsol(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set)
static void skipRedundantBdchginfos(SCIP_VAR *var, int *lbchginfopos, int *ubchginfopos)
static SCIP_RETCODE conflictInsertConflictset(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_CONFLICTSET **conflictset)
static SCIP_RETCODE conflictEnsureConflictsetsMem(SCIP_CONFLICT *conflict, SCIP_SET *set, int num)
static void lpbdchgsFree(SCIP_LPBDCHGS **lpbdchgs, SCIP_SET *set)
SCIP_RETCODE SCIPconflicthdlrInit(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set)
static SCIP_RETCODE conflictAddConflictset(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, int validdepth, SCIP_Bool diving, SCIP_Bool repropagate, SCIP_Bool *success, int *nliterals)
static void conflictFreeTmpBdchginfos(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem)
void SCIPconflicthdlrSetInitsol(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_DECL_CONFLICTINITSOL((*conflictinitsol)))
static SCIP_RETCODE updateStatistics(SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_CONFLICTSET *conflictset, int insertdepth)
methods and datastructures for conflict analysis
SCIP_RETCODE SCIPconsResolvePropagation(SCIP_CONS *cons, SCIP_SET *set, SCIP_VAR *infervar, int inferinfo, SCIP_BOUNDTYPE inferboundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd, SCIP_RESULT *result)
Definition: cons.c:7318
internal methods for constraints and constraint handlers
Constraint handler for linear constraints in their most general form, .
methods for the aggregation rows
#define SCIPquadprecProdQD(r, a, b)
Definition: dbldblarith.h:63
#define QUAD(x)
Definition: dbldblarith.h:47
#define SCIPquadprecSumDD(r, a, b)
Definition: dbldblarith.h:60
#define QUAD_TO_DBL(x)
Definition: dbldblarith.h:49
#define SCIPdebugCheckConflict(blkmem, set, node, bdchginfos, relaxedbds, nliterals)
Definition: debug.h:295
#define SCIPdebugCheckConflictFrontier(blkmem, set, node, bdchginfo, bdchginfos, relaxedbds, nliterals, bdchgqueue, forcedbdchgqueue)
Definition: debug.h:296
#define NULL
Definition: def.h:267
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define SCIP_Longint
Definition: def.h:158
#define SCIP_REAL_MAX
Definition: def.h:174
#define SCIP_INVALID
Definition: def.h:193
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_ALLOC(x)
Definition: def.h:385
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
#define SCIPABORT()
Definition: def.h:346
#define SCIP_REAL_MIN
Definition: def.h:175
#define SCIP_CALL(x)
Definition: def.h:374
#define SCIP_CALL_FINALLY(x, y)
Definition: def.h:416
void SCIPdotWriteOpening(FILE *file)
Definition: misc.c:711
void SCIPdotWriteClosing(FILE *file)
Definition: misc.c:749
void SCIPdotWriteArc(FILE *file, int source, int target, const char *color)
Definition: misc.c:736
void SCIPgmlWriteNode(FILE *file, unsigned int id, const char *label, const char *nodetype, const char *fillcolor, const char *bordercolor)
Definition: misc.c:497
void SCIPgmlWriteClosing(FILE *file)
Definition: misc.c:699
void SCIPdotWriteNode(FILE *file, int node, const char *label, const char *nodetype, const char *fillcolor, const char *bordercolor)
Definition: misc.c:721
void SCIPgmlWriteOpening(FILE *file, SCIP_Bool directed)
Definition: misc.c:683
void SCIPgmlWriteEdge(FILE *file, unsigned int source, unsigned int target, const char *label, const char *color)
Definition: misc.c:595
void SCIPgmlWriteArc(FILE *file, unsigned int source, unsigned int target, const char *label, const char *color)
Definition: misc.c:639
SCIP_RETCODE SCIPlpiChgSides(SCIP_LPI *lpi, int nrows, const int *ind, const SCIP_Real *lhs, const SCIP_Real *rhs)
Definition: lpi_clp.cpp:1167
SCIP_Real SCIPlpiInfinity(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:3919
SCIP_Bool SCIPlpiIsObjlimExc(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:2690
SCIP_Bool SCIPlpiIsInfinity(SCIP_LPI *lpi, SCIP_Real val)
Definition: lpi_clp.cpp:3931
SCIP_RETCODE SCIPlpiSetRealpar(SCIP_LPI *lpi, SCIP_LPPARAM type, SCIP_Real dval)
Definition: lpi_clp.cpp:3833
SCIP_RETCODE SCIPlpiGetObjval(SCIP_LPI *lpi, SCIP_Real *objval)
Definition: lpi_clp.cpp:2766
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_Bool SCIPlpiIsDualFeasible(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:2609
SCIP_RETCODE SCIPlpiSetIntpar(SCIP_LPI *lpi, SCIP_LPPARAM type, int ival)
Definition: lpi_clp.cpp:3692
SCIP_Bool SCIPlpiIsPrimalInfeasible(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:2502
SCIP_RETCODE SCIPlpiSolveDual(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:1880
SCIP_RETCODE SCIPlpiGetIterations(SCIP_LPI *lpi, int *iterations)
Definition: lpi_clp.cpp:2921
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
void ** SCIPpqueueElems(SCIP_PQUEUE *pqueue)
Definition: misc.c:1538
void SCIPpqueueClear(SCIP_PQUEUE *pqueue)
Definition: misc.c:1333
SCIP_RETCODE SCIPpqueueInsert(SCIP_PQUEUE *pqueue, void *elem)
Definition: misc.c:1394
int SCIPpqueueNElems(SCIP_PQUEUE *pqueue)
Definition: misc.c:1527
void * SCIPpqueueRemove(SCIP_PQUEUE *pqueue)
Definition: misc.c:1493
void * SCIPpqueueFirst(SCIP_PQUEUE *pqueue)
Definition: misc.c:1513
int SCIPcolGetLPPos(SCIP_COL *col)
Definition: lp.c:17093
int SCIPcolGetNNonz(SCIP_COL *col)
Definition: lp.c:17126
SCIP_BOUNDTYPE SCIPboundtypeOpposite(SCIP_BOUNDTYPE boundtype)
Definition: lp.c:17203
SCIP_CONFLICTHDLRDATA * SCIPconflicthdlrGetData(SCIP_CONFLICTHDLR *conflicthdlr)
SCIP_DECL_SORTPTRCOMP(SCIPconflicthdlrComp)
int SCIPconflicthdlrGetPriority(SCIP_CONFLICTHDLR *conflicthdlr)
const char * SCIPconflicthdlrGetName(SCIP_CONFLICTHDLR *conflicthdlr)
void SCIPconflicthdlrSetData(SCIP_CONFLICTHDLR *conflicthdlr, SCIP_CONFLICTHDLRDATA *conflicthdlrdata)
SCIP_Bool SCIPconflicthdlrIsInitialized(SCIP_CONFLICTHDLR *conflicthdlr)
SCIP_Real SCIPconflicthdlrGetTime(SCIP_CONFLICTHDLR *conflicthdlr)
SCIP_Real SCIPconflicthdlrGetSetupTime(SCIP_CONFLICTHDLR *conflicthdlr)
const char * SCIPconflicthdlrGetDesc(SCIP_CONFLICTHDLR *conflicthdlr)
SCIP_RETCODE SCIPsetConflicthdlrPriority(SCIP *scip, SCIP_CONFLICTHDLR *conflicthdlr, int priority)
int SCIPconsGetValidDepth(SCIP_CONS *cons)
Definition: cons.c:8297
SCIP_Bool SCIPconsIsGlobal(SCIP_CONS *cons)
Definition: cons.c:8443
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8214
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition: cuts.c:1723
SCIP_Real SCIPaggrRowGetRhs(SCIP_AGGRROW *aggrrow)
Definition: cuts.c:2581
void SCIPaggrRowFree(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition: cuts.c:1755
int * SCIPaggrRowGetInds(SCIP_AGGRROW *aggrrow)
Definition: cuts.c:2541
int SCIPaggrRowGetNNz(SCIP_AGGRROW *aggrrow)
Definition: cuts.c:2551
static INLINE SCIP_Real SCIPaggrRowGetProbvarValue(SCIP_AGGRROW *aggrrow, int probindex)
Definition: cuts.h:251
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7503
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:941
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17292
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17302
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:17501
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:17401
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17351
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:17258
SCIP_RETCODE SCIPshrinkDisjunctiveVarSet(SCIP *scip, SCIP_VAR **vars, SCIP_Real *bounds, SCIP_Bool *boundtypes, SCIP_Bool *redundants, int nvars, int *nredvars, int *nglobalred, SCIP_Bool *setredundant, SCIP_Bool *glbinfeas, SCIP_Bool fullshortening)
Definition: presolve.c:995
SCIP_Real SCIPgetVarBdAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2264
int SCIPvarGetNVlbs(SCIP_VAR *var)
Definition: var.c:18270
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:17789
SCIP_Bool SCIPbdchginfoIsRedundant(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18808
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17748
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17599
SCIP_Bool SCIPbdchgidxIsEarlier(SCIP_BDCHGIDX *bdchgidx1, SCIP_BDCHGIDX *bdchgidx2)
Definition: var.c:18640
SCIP_BDCHGIDX * SCIPbdchginfoGetIdx(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18730
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17538
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3353
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIP_PROP * SCIPbdchginfoGetInferProp(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18764
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
int SCIPbdchginfoGetDepth(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18710
int SCIPbdchginfoGetInferInfo(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18775
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17758
SCIP_CONS * SCIPbdchginfoGetInferCons(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18752
int SCIPbdchginfoGetPos(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18720
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2128
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17768
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_VAR * SCIPbdchginfoGetVar(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18680
int SCIPvarGetNVubs(SCIP_VAR *var)
Definition: var.c:18312
SCIP_Real SCIPbdchginfoGetOldbound(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18660
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17610
SCIP_BOUNDTYPE SCIPbdchginfoGetInferBoundtype(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18787
SCIP_BDCHGINFO * SCIPvarGetBdchgInfo(SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:16689
SCIP_VAR ** SCIPvarGetMultaggrVars(SCIP_VAR *var)
Definition: var.c:17858
SCIP_Bool SCIPbdchginfoIsTighter(SCIP_BDCHGINFO *bdchginfo1, SCIP_BDCHGINFO *bdchginfo2)
Definition: var.c:18833
int SCIPvarGetMultaggrNVars(SCIP_VAR *var)
Definition: var.c:17846
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18430
SCIP_BOUNDCHGTYPE SCIPbdchginfoGetChgtype(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18690
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
SCIP_VAR * SCIPbdchginfoGetInferVar(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18740
SCIP_Bool SCIPbdchginfoHasInferenceReason(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18819
SCIP_Bool SCIPvarIsRelaxationOnly(SCIP_VAR *var)
Definition: var.c:17706
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
SCIP_BDCHGINFO * SCIPvarGetBdchgInfoLb(SCIP_VAR *var, int pos)
Definition: var.c:18478
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1992
SCIP_BOUNDTYPE SCIPbdchginfoGetBoundtype(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18700
SCIP_Real SCIPbdchginfoGetNewbound(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18670
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3295
SCIP_BDCHGINFO * SCIPvarGetBdchgInfoUb(SCIP_VAR *var, int pos)
Definition: var.c:18498
SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var)
Definition: var.c:17870
SCIP_Bool SCIPvarIsInLP(SCIP_VAR *var)
Definition: var.c:17800
void SCIPsortedvecInsertIntPtrReal(int *intarray, void **ptrarray, SCIP_Real *realarray, int keyval, void *field1val, SCIP_Real field2val, int *len, int *pos)
void SCIPsortIntPtrReal(int *intarray, void **ptrarray, SCIP_Real *realarray, int len)
void SCIPsortLongPtrRealRealBool(SCIP_Longint *longarray, void **ptrarray, SCIP_Real *realarray, SCIP_Real *realarray2, SCIP_Bool *boolarray, int len)
void SCIPsortedvecDelPosIntPtrReal(int *intarray, void **ptrarray, SCIP_Real *realarray, int pos, int *len)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
void SCIPhistoryIncNActiveConflicts(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real length)
Definition: history.c:549
void SCIPhistoryScaleVSIDS(SCIP_HISTORY *history, SCIP_Real scalar)
Definition: history.c:524
void SCIPhistoryIncVSIDS(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real weight)
Definition: history.c:510
internal methods for branching and inference history
SCIP_Bool SCIPlpDivingObjChanged(SCIP_LP *lp)
Definition: lp.c:17857
SCIP_LPI * SCIPlpGetLPI(SCIP_LP *lp)
Definition: lp.c:17774
int SCIPlpGetNCols(SCIP_LP *lp)
Definition: lp.c:17575
SCIP_ROW ** SCIPlpGetRows(SCIP_LP *lp)
Definition: lp.c:17612
static const SCIP_Real scalars[]
Definition: lp.c:5743
int SCIPlpGetNRows(SCIP_LP *lp)
Definition: lp.c:17622
internal methods for LP management
interface methods for specific LP solvers
static const char * paramname[]
Definition: lpi_msk.c:5096
#define BMSfreeMemory(ptr)
Definition: memory.h:145
#define BMSfreeBlockMemory(mem, ptr)
Definition: memory.h:465
#define BMSallocBlockMemory(mem, ptr)
Definition: memory.h:451
#define BMSreallocMemoryArray(ptr, num)
Definition: memory.h:127
#define BMSfreeBlockMemoryArrayNull(mem, ptr, num)
Definition: memory.h:468
#define BMSduplicateMemoryArray(ptr, source, num)
Definition: memory.h:143
#define BMSclearMemory(ptr)
Definition: memory.h:129
#define BMSallocBlockMemoryArray(mem, ptr, num)
Definition: memory.h:454
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:134
#define BMSreallocBlockMemoryArray(mem, ptr, oldnum, newnum)
Definition: memory.h:458
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:437
#define BMSfreeMemoryArrayNull(ptr)
Definition: memory.h:148
#define BMSallocMemory(ptr)
Definition: memory.h:118
SCIP_PARAMDATA * SCIPparamGetData(SCIP_PARAM *param)
Definition: paramset.c:679
int SCIPparamGetInt(SCIP_PARAM *param)
Definition: paramset.c:734
methods commonly used for presolving
const char * SCIPprobGetName(SCIP_PROB *prob)
Definition: prob.c:2384
int SCIPprobGetNVars(SCIP_PROB *prob)
Definition: prob.c:2393
SCIP_VAR ** SCIPprobGetVars(SCIP_PROB *prob)
Definition: prob.c:2438
SCIP_Bool SCIPprobAllColsInLP(SCIP_PROB *prob, SCIP_SET *set, SCIP_LP *lp)
Definition: prob.c:2350
SCIP_Bool SCIPprobIsTransformed(SCIP_PROB *prob)
Definition: prob.c:2328
internal methods for storing and manipulating the main problem
SCIP_RETCODE SCIPpropResolvePropagation(SCIP_PROP *prop, SCIP_SET *set, SCIP_VAR *infervar, int inferinfo, SCIP_BOUNDTYPE inferboundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd, SCIP_RESULT *result)
Definition: prop.c:737
internal methods for propagators
public methods for conflict analysis handlers
public methods for managing constraints
public methods for LP management
public methods for message output
#define SCIPerrorMessage
Definition: pub_message.h:64
#define SCIPdebug(x)
Definition: pub_message.h:93
#define SCIPdebugMessage
Definition: pub_message.h:96
#define SCIPdebugPrintf
Definition: pub_message.h:99
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for handling parameter settings
public methods for propagators
public methods for branch and bound tree
public methods for problem variables
public methods for conflict handler plugins and conflict analysis
public methods for constraint handler plugins and constraints
public methods for memory management
public methods for message handling
public methods for solutions
public methods for SCIP variables
SCIP_RETCODE SCIPsetAddIntParam(SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: set.c:2984
SCIP_Bool SCIPsetIsGE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6293
SCIP_Bool SCIPsetIsFeasGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6663
SCIP_Bool SCIPsetIsFeasLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6641
SCIP_Bool SCIPsetIsFeasEQ(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6597
SCIP_Bool SCIPsetIsPositive(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6322
SCIP_Bool SCIPsetIsLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6257
SCIP_Bool SCIPsetIsEQ(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6221
SCIP_Bool SCIPsetIsFeasLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6619
SCIP_Bool SCIPsetIsLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6239
SCIP_Bool SCIPsetIsInfinity(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6199
SCIP_Bool SCIPsetIsGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6275
SCIP_Bool SCIPsetIsIntegral(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6344
SCIP_Bool SCIPsetIsZero(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6311
SCIP_Bool SCIPsetIsFeasGE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6685
void SCIPsetSortConflicthdlrs(SCIP_SET *set)
Definition: set.c:4049
int SCIPsetCalcMemGrowSize(SCIP_SET *set, int num)
Definition: set.c:5764
SCIP_Bool SCIPsetIsNegative(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6333
internal methods for global SCIP settings
#define SCIPsetFreeBufferArray(set, ptr)
Definition: set.h:1755
#define SCIPsetFreeCleanBufferArray(set, ptr)
Definition: set.h:1762
#define SCIPsetDebugMsgPrint
Definition: set.h:1785
#define SCIPsetAllocBufferArray(set, ptr, num)
Definition: set.h:1748
#define SCIPsetFreeBuffer(set, ptr)
Definition: set.h:1753
#define SCIPsetAllocCleanBufferArray(set, ptr, num)
Definition: set.h:1759
#define SCIPsetDebugMsg
Definition: set.h:1784
#define SCIPsetAllocBuffer(set, ptr)
Definition: set.h:1746
#define SCIPsetReallocBufferArray(set, ptr, num)
Definition: set.h:1752
internal methods for storing primal CIP solutions
SCIP_BDCHGIDX bdchgidx
Definition: struct_var.h:121
SCIP_Real newbound
Definition: struct_var.h:118
unsigned int boundtype
Definition: struct_var.h:124
SCIP_VAR * var
Definition: struct_var.h:119
unsigned int redundant
Definition: struct_var.h:126
SCIP_Real oldbound
Definition: struct_var.h:117
unsigned int pos
Definition: struct_var.h:122
unsigned int hasrelaxonlyvar
SCIP_BDCHGINFO ** bdchginfos
unsigned int repropagate
SCIP_Real * relaxedbds
SCIP_CONFTYPE conflicttype
unsigned int usescutoffbound
SCIP_Real * conflictsetscores
SCIP_Longint nappliedglbconss
SCIP_Longint npropconfconss
SCIP_CLOCK * dIBclock
SCIP_CLOCK * propanalyzetime
SCIP_PQUEUE * forcedbdchgqueue
SCIP_Longint nappliedglbliterals
SCIP_CONFLICTSET ** conflictsets
SCIP_PQUEUE * bdchgqueue
SCIP_Longint npropsuccess
SCIP_Longint nappliedlocconss
SCIP_Longint npropcalls
SCIP_Longint npropreconvliterals
SCIP_BDCHGINFO ** tmpbdchginfos
SCIP_Longint npropconfliterals
SCIP_CONFLICTSET * conflictset
SCIP_Longint nappliedlocliterals
SCIP_Longint npropreconvconss
SCIP_CONFLICTHDLRDATA * conflicthdlrdata
SCIP_CLOCK * setuptime
SCIP_CLOCK * conflicttime
SCIP_BOUNDCHG * boundchgs
Definition: struct_var.h:134
unsigned int nboundchgs
Definition: struct_var.h:132
SCIP_Real * bdchgubs
SCIP_Bool * usedcols
SCIP_Real * bdchglbs
int lpiitlim
Definition: struct_lp.h:345
SCIP_Bool strongbranching
Definition: struct_lp.h:377
SCIP_Bool primalfeasible
Definition: struct_lp.h:368
SCIP_Real cutoffbound
Definition: struct_lp.h:284
SCIP_Bool dualfeasible
Definition: struct_lp.h:370
SCIP_Bool primalchecked
Definition: struct_lp.h:369
SCIP_LPSOLSTAT lpsolstat
Definition: struct_lp.h:353
SCIP_Real lpobjval
Definition: struct_lp.h:271
SCIP_Bool solved
Definition: struct_lp.h:367
SCIP_Bool dualchecked
Definition: struct_lp.h:371
SCIP_Bool diving
Definition: struct_lp.h:380
SCIP_Bool flushed
Definition: struct_lp.h:366
SCIP_Real lpiobjlim
Definition: struct_lp.h:286
SCIP_DOMCHG * domchg
Definition: struct_tree.h:159
unsigned int depth
Definition: struct_tree.h:160
int ncontvars
Definition: struct_prob.h:75
SCIP_VAR ** vars
Definition: struct_prob.h:64
SCIP_Longint nnodes
Definition: struct_stat.h:82
SCIP_Longint nconflictlps
Definition: struct_stat.h:213
SCIP_HISTORY * glbhistory
Definition: struct_stat.h:181
SCIP_VISUAL * visual
Definition: struct_stat.h:184
SCIP_Real vsidsweight
Definition: struct_stat.h:132
SCIP_Longint lastconflictnode
Definition: struct_stat.h:112
SCIP_HISTORY * glbhistorycrun
Definition: struct_stat.h:182
SCIP_Longint nconflictlpiterations
Definition: struct_stat.h:79
SCIP_CLOCK * conflictlptime
Definition: struct_stat.h:171
SCIP_NODE * root
Definition: struct_tree.h:186
SCIP_NODE ** path
Definition: struct_tree.h:188
int nubchginfos
Definition: struct_var.h:269
SCIP_BDCHGINFO * lbchginfos
Definition: struct_var.h:248
int conflictubcount
Definition: struct_var.h:271
SCIP_Real conflictrelaxedub
Definition: struct_var.h:222
SCIP_BDCHGINFO * ubchginfos
Definition: struct_var.h:249
SCIP_Real conflictub
Definition: struct_var.h:220
SCIP_Real conflictrelaxedlb
Definition: struct_var.h:221
int nlbchginfos
Definition: struct_var.h:267
SCIP_Real conflictlb
Definition: struct_var.h:219
int conflictlbcount
Definition: struct_var.h:270
datastructures for conflict analysis
data structures for LP management
datastructures for storing and manipulating the main problem
datastructures for global SCIP settings
datastructures for problem statistics
data structures for branch and bound tree
datastructures for problem variables
Definition: heur_padm.c:135
SCIP_RETCODE SCIPnodeCutoff(SCIP_NODE *node, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_REOPT *reopt, SCIP_LP *lp, BMS_BLKMEM *blkmem)
Definition: tree.c:1234
int SCIPtreeGetFocusDepth(SCIP_TREE *tree)
Definition: tree.c:8377
void SCIPnodePropagateAgain(SCIP_NODE *node, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree)
Definition: tree.c:1294
SCIP_NODE * SCIPtreeGetRootNode(SCIP_TREE *tree)
Definition: tree.c:8502
int SCIPtreeGetEffectiveRootDepth(SCIP_TREE *tree)
Definition: tree.c:8491
SCIP_RETCODE SCIPnodeAddBoundchg(SCIP_NODE *node, 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_VAR *var, SCIP_Real newbound, SCIP_BOUNDTYPE boundtype, SCIP_Bool probingchange)
Definition: tree.c:2097
int SCIPtreeGetCurrentDepth(SCIP_TREE *tree)
Definition: tree.c:8452
internal methods for branch and bound tree
@ SCIP_CLOCKTYPE_DEFAULT
Definition: type_clock.h:43
#define SCIP_DECL_CONFLICTEXIT(x)
#define SCIP_DECL_CONFLICTCOPY(x)
Definition: type_conflict.h:87
#define SCIP_DECL_CONFLICTEXEC(x)
#define SCIP_DECL_CONFLICTINITSOL(x)
#define SCIP_DECL_CONFLICTFREE(x)
Definition: type_conflict.h:95
@ SCIP_CONFTYPE_BNDEXCEEDING
Definition: type_conflict.h:62
@ SCIP_CONFTYPE_PROPAGATION
Definition: type_conflict.h:60
@ SCIP_CONFTYPE_INFEASLP
Definition: type_conflict.h:61
@ SCIP_CONFTYPE_UNKNOWN
Definition: type_conflict.h:59
#define SCIP_DECL_CONFLICTINIT(x)
enum SCIP_ConflictType SCIP_CONFTYPE
Definition: type_conflict.h:66
struct SCIP_ConflicthdlrData SCIP_CONFLICTHDLRDATA
Definition: type_conflict.h:50
#define SCIP_DECL_CONFLICTEXITSOL(x)
@ SCIP_BRANCHDIR_DOWNWARDS
Definition: type_history.h:43
@ SCIP_BRANCHDIR_UPWARDS
Definition: type_history.h:44
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:48
@ SCIP_BOUNDTYPE_UPPER
Definition: type_lp.h:57
@ SCIP_BOUNDTYPE_LOWER
Definition: type_lp.h:56
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
@ SCIP_LPSOLSTAT_NOTSOLVED
Definition: type_lp.h:42
@ SCIP_LPPAR_LPITLIM
Definition: type_lpi.h:60
@ SCIP_LPPAR_OBJLIM
Definition: type_lpi.h:59
struct SCIP_ParamData SCIP_PARAMDATA
Definition: type_paramset.h:87
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_CONSADDED
Definition: type_result.h:52
@ SCIP_SUCCESS
Definition: type_result.h:58
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_LPERROR
Definition: type_retcode.h:49
@ SCIP_INVALIDRESULT
Definition: type_retcode.h:53
@ SCIP_INVALIDDATA
Definition: type_retcode.h:52
@ SCIP_WRITEERROR
Definition: type_retcode.h:46
@ SCIP_OKAY
Definition: type_retcode.h:42
@ SCIP_INVALIDCALL
Definition: type_retcode.h:51
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:71
@ SCIP_BOUNDCHGTYPE_PROPINFER
Definition: type_var.h:89
@ SCIP_BOUNDCHGTYPE_BRANCHING
Definition: type_var.h:87
@ SCIP_BOUNDCHGTYPE_CONSINFER
Definition: type_var.h:88
@ SCIP_VARSTATUS_FIXED
Definition: type_var.h:52
@ SCIP_VARSTATUS_COLUMN
Definition: type_var.h:51
@ SCIP_VARSTATUS_MULTAGGR
Definition: type_var.h:54
@ SCIP_VARSTATUS_NEGATED
Definition: type_var.h:55
@ SCIP_VARSTATUS_AGGREGATED
Definition: type_var.h:53
@ SCIP_LOCKTYPE_MODEL
Definition: type_var.h:97
SCIP_DOMCHGBOUND domchgbound
Definition: struct_var.h:162
void SCIPbdchginfoFree(SCIP_BDCHGINFO **bdchginfo, BMS_BLKMEM *blkmem)
Definition: var.c:16563
SCIP_RETCODE SCIPvarIncVSIDS(SCIP_VAR *var, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_BRANCHDIR dir, SCIP_Real value, SCIP_Real weight)
Definition: var.c:15051
SCIP_RETCODE SCIPvarIncNActiveConflicts(SCIP_VAR *var, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_BRANCHDIR dir, SCIP_Real value, SCIP_Real length)
Definition: var.c:15187
void SCIPvarAdjustLb(SCIP_VAR *var, SCIP_SET *set, SCIP_Real *lb)
Definition: var.c:6517
SCIP_Real SCIPvarGetLbLP(SCIP_VAR *var, SCIP_SET *set)
Definition: var.c:12932
SCIP_RETCODE SCIPvarScaleVSIDS(SCIP_VAR *var, SCIP_Real scalar)
Definition: var.c:15137
SCIP_Real SCIPvarGetUbLP(SCIP_VAR *var, SCIP_SET *set)
Definition: var.c:13002
int SCIPbdchgidxGetPos(SCIP_BDCHGIDX *bdchgidx)
Definition: var.c:18610
SCIP_RETCODE SCIPbdchginfoCreate(SCIP_BDCHGINFO **bdchginfo, BMS_BLKMEM *blkmem, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_Real oldbound, SCIP_Real newbound)
Definition: var.c:16533
SCIP_RETCODE SCIPvarGetProbvarSum(SCIP_VAR **var, SCIP_SET *set, SCIP_Real *scalar, SCIP_Real *constant)
Definition: var.c:12647
void SCIPvarAdjustUb(SCIP_VAR *var, SCIP_SET *set, SCIP_Real *ub)
Definition: var.c:6534
SCIP_Real SCIPbdchginfoGetRelaxedBound(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18799
internal methods for problem variables
void SCIPvisualFoundConflict(SCIP_VISUAL *visual, SCIP_STAT *stat, SCIP_NODE *node)
Definition: visual.c:612
methods for creating output for visualization tools (VBC, BAK)