1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file conflict_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" 127 #include "scip/conflict_graphanalysis.h" 128 #include "scip/conflict_dualproofanalysis.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 184 static FILE* confgraphfile = NULL; /**< output file for current conflict graph */ 185 static SCIP_BDCHGINFO* confgraphcurrentbdchginfo = NULL; /**< currently resolved bound change */ 186 static int confgraphnconflictsets = 0; /**< number of conflict sets marked in the graph */ 187 188 /** writes a node section to the conflict graph file */ 189 static 190 void 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 */ 210 static 211 void 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 */ 233 static 234 SCIP_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 */ 273 static 274 void 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 */ 293 static 294 void 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 { 309 case SCIP_BOUNDCHGTYPE_BRANCHING: 310 col = 2; 311 break; 312 case SCIP_BOUNDCHGTYPE_CONSINFER: 313 col = 0; 314 break; 315 case SCIP_BOUNDCHGTYPE_PROPINFER: 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 */ 337 static 338 void 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 */ 346 static 347 void 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 */ 355 static 356 void 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 */ 377 static 378 SCIP_RETCODE conflictsetEnsureBdchginfosMem( 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 */ 404 static 405 SCIP_RETCODE conflictsetAddBound( 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 */ 477 static 478 void conflictsetCalcConflictDepth( 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 */ 521 static 522 SCIP_RETCODE conflictsetCalcInsertDepth( 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 */ 568 static 569 SCIP_Bool conflictsetIsRedundant( 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 */ 610 void 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]), 620 SCIPvarGetName(SCIPbdchginfoGetVar(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 */ 632 static 633 SCIP_Bool checkRedundancy( 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; 641 SCIP_Real bound; 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 { 667 if( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS ) 668 { 669 assert(SCIPsetIsIntegral(set, bound)); 670 bound += 1.0; 671 } 672 673 /* check if the bound is already fulfilled globally */ 674 if( SCIPsetIsFeasGE(set, SCIPvarGetLbGlobal(var), bound) ) 675 return TRUE; 676 } 677 else 678 { 679 assert(SCIPbdchginfoGetBoundtype(bdchginfos[v]) == SCIP_BOUNDTYPE_LOWER); 680 681 if( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS ) 682 { 683 assert(SCIPsetIsIntegral(set, bound)); 684 bound -= 1.0; 685 } 686 687 /* check if the bound is already fulfilled globally */ 688 if( SCIPsetIsFeasLE(set, SCIPvarGetUbGlobal(var), bound) ) 689 return TRUE; 690 } 691 } 692 693 return FALSE; 694 } 695 696 /** find global fixings which can be derived from the new conflict set */ 697 static 698 SCIP_RETCODE detectImpliedBounds( 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; 720 SCIP_Real bound; 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]; 767 isupper = (SCIP_Bool) SCIPboundtypeOpposite(SCIPbdchginfoGetBoundtype(bdchginfos[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 ) 880 SCIPsetDebugMsgPrint(set, ", "); 881 } 882 SCIPsetDebugMsgPrint(set, "]\n"); 883 884 SCIP_CALL( SCIPsetAllocBufferArray(set, &vars, v) ); 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); 956 SCIPsetFreeBufferArray(set, &vars); 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 */ 970 static 971 void conflictsetClear( 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 */ 989 SCIP_RETCODE SCIPconflictsetCreate( 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 */ 1008 static 1009 SCIP_RETCODE conflictsetCopy( 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 */ 1045 void SCIPconflictsetFree( 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 */ 1063 static 1064 SCIP_Real conflictsetCalcScore( 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 */ 1082 SCIP_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 */ 1088 SCIP_DECL_SORTPTRCOMP(SCIPconflicthdlrCompName) 1089 { 1090 return strcmp(SCIPconflicthdlrGetName((SCIP_CONFLICTHDLR*)elem1), SCIPconflicthdlrGetName((SCIP_CONFLICTHDLR*)elem2)); 1091 } 1092 1093 /** method to call, when the priority of a conflict handler was changed */ 1094 static 1095 SCIP_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 */ 1109 SCIP_RETCODE SCIPconflicthdlrCopyInclude( 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 */ 1128 static 1129 SCIP_RETCODE doConflicthdlrCreate( 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 { 1147 char paramname[SCIP_MAXSTRLEN]; 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 */ 1183 SCIP_RETCODE SCIPconflicthdlrCreate( 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 */ 1214 SCIP_RETCODE SCIPconflicthdlrFree( 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 */ 1242 SCIP_RETCODE SCIPconflicthdlrInit( 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 */ 1279 SCIP_RETCODE SCIPconflicthdlrExit( 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 */ 1310 SCIP_RETCODE SCIPconflicthdlrInitsol( 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 */ 1334 SCIP_RETCODE SCIPconflicthdlrExitsol( 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 */ 1358 SCIP_RETCODE SCIPconflicthdlrExec( 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 */ 1405 SCIP_CONFLICTHDLRDATA* SCIPconflicthdlrGetData( 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! */ 1415 void SCIPconflicthdlrSetData( 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 */ 1426 void SCIPconflicthdlrSetCopy( 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 */ 1437 void SCIPconflicthdlrSetFree( 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 1449 void SCIPconflicthdlrSetInit( 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 */ 1460 void SCIPconflicthdlrSetExit( 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 */ 1471 void SCIPconflicthdlrSetInitsol( 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 */ 1482 void SCIPconflicthdlrSetExitsol( 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 */ 1493 const char* SCIPconflicthdlrGetName( 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 */ 1503 const char* SCIPconflicthdlrGetDesc( 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 */ 1513 int SCIPconflicthdlrGetPriority( 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 */ 1523 void SCIPconflicthdlrSetPriority( 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? */ 1537 SCIP_Bool SCIPconflicthdlrIsInitialized( 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 */ 1547 void SCIPconflicthdlrEnableOrDisableClocks( 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 */ 1559 SCIP_Real SCIPconflicthdlrGetSetupTime( 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 */ 1569 SCIP_Real SCIPconflicthdlrGetTime( 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 */ 1581 SCIP_Bool SCIPconflictApplicable( 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 */ 1597 static 1598 SCIP_RETCODE conflictEnsureTmpbdchginfosMem( 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 */ 1621 SCIP_RETCODE conflictCreateTmpBdchginfo( 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 1634 SCIP_CALL( conflictEnsureTmpbdchginfosMem(conflict, set, conflict->ntmpbdchginfos+1) ); 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 */ 1644 static 1645 void conflictFreeTmpBdchginfos( 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 */ 1660 static 1661 SCIP_RETCODE incVSIDS( 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 */ 1691 static 1692 SCIP_RETCODE updateStatistics( 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; 1717 SCIP_Real bound; 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 */ 1742 static 1743 SCIP_RETCODE conflictAddConflictCons( 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; 1835 SCIP_Real bound; 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 */ 1863 SCIPsetSortConflicthdlrs(set); 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 */ 1896 int conflictCalcMaxsize( 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 */ 1916 SCIP_RETCODE SCIPconflictFlushConss( 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", 2095 SCIPtreeGetCurrentDepth(tree), SCIPtreeGetFocusDepth(tree), 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 */ 2125 static 2126 SCIP_RETCODE conflictEnsureConflictsetsMem( 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 */ 2150 static 2151 SCIP_RETCODE conflictInsertConflictset( 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 */ 2246 static 2247 SCIP_Bool conflictMarkBoundCheckPresence( 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 { 2265 case SCIP_BOUNDTYPE_LOWER: 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 2296 case SCIP_BOUNDTYPE_UPPER: 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 */ 2335 static 2336 SCIP_RETCODE conflictAddConflictBound( 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", 2352 SCIPvarGetName(SCIPbdchginfoGetVar(bdchginfo)), 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 */ 2378 static 2379 SCIP_Bool isBoundchgUseless( 2380 SCIP_SET* set, /**< global SCIP settings */ 2381 SCIP_BDCHGINFO* bdchginfo /**< bound change information */ 2382 ) 2383 { 2384 SCIP_VAR* var; 2385 SCIP_BOUNDTYPE boundtype; 2386 SCIP_Real bound; 2387 2388 var = SCIPbdchginfoGetVar(bdchginfo); 2389 boundtype = SCIPbdchginfoGetBoundtype(bdchginfo); 2390 bound = SCIPbdchginfoGetNewbound(bdchginfo); 2391 2392 return (SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS 2393 && ((boundtype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsFeasGE(set, bound, SCIPvarGetUbGlobal(var))) 2394 || (boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsFeasLE(set, bound, SCIPvarGetLbGlobal(var))))); 2395 } 2396 2397 /** adds given bound change information to the conflict candidate queue */ 2398 static 2399 SCIP_RETCODE conflictQueueBound( 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 */ 2444 static 2445 SCIP_RETCODE conflictAddBound( 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, 2464 SCIPvarGetStatus(var), SCIPvarGetType(var), 2465 SCIPbdchginfoGetDepth(bdchginfo), SCIPbdchginfoGetPos(bdchginfo), 2466 SCIPbdchginfoGetChgtype(bdchginfo) == SCIP_BOUNDCHGTYPE_BRANCHING ? "branch" 2467 : (SCIPbdchginfoGetChgtype(bdchginfo) == SCIP_BOUNDCHGTYPE_CONSINFER 2468 ? SCIPconsGetName(SCIPbdchginfoGetInferCons(bdchginfo)) 2469 : (SCIPbdchginfoGetInferProp(bdchginfo) != NULL ? SCIPpropGetName(SCIPbdchginfoGetInferProp(bdchginfo)) 2470 : "none")), 2471 SCIPbdchginfoGetChgtype(bdchginfo) != SCIP_BOUNDCHGTYPE_BRANCHING ? SCIPbdchginfoGetInferInfo(bdchginfo) : -1); 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 */ 2503 SCIP_RETCODE SCIPconflictAnalyzeRemainingBdchgs( 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 { 2586 SCIP_CALL( conflictCreateTmpBdchginfo(conflict, blkmem, set, var, SCIP_BOUNDTYPE_LOWER, 2587 SCIPvarGetLbLocal(var), SCIPvarGetLbLP(var, set), &bdchginfo) ); 2588 relaxedbd = SCIPvarGetLbLP(var, set); 2589 } 2590 else 2591 { 2592 SCIP_CALL( conflictCreateTmpBdchginfo(conflict, blkmem, set, var, SCIP_BOUNDTYPE_UPPER, 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 */ 2673 static 2674 SCIP_Bool bdchginfoIsInvalid( 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 */ 2693 if( SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_LOWER ) 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 */ 2716 static 2717 SCIP_RETCODE conflictsetAddBounds( 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), 2761 SCIPvarGetName(SCIPbdchginfoGetVar(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 2805 if( SCIPvarIsRelaxationOnly(SCIPbdchginfoGetVar(bdchginfo)) ) 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), 2811 SCIPvarGetName(SCIPbdchginfoGetVar(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 */ 2885 static 2886 SCIP_BDCHGINFO* conflictRemoveCand( 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); 2909 if( SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_LOWER ) 2910 { 2911 var->conflictlbcount = 0; 2912 var->conflictrelaxedlb = SCIP_REAL_MIN; 2913 } 2914 else 2915 { 2916 assert(SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_UPPER); 2917 var->conflictubcount = 0; 2918 var->conflictrelaxedub = SCIP_REAL_MAX; 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 */ 2929 static 2930 SCIP_BDCHGINFO* conflictFirstCand( 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), 2947 SCIPvarGetName(SCIPbdchginfoGetVar(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), 2966 SCIPvarGetName(SCIPbdchginfoGetVar(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 */ 2983 static 2984 SCIP_RETCODE conflictAddConflictset( 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 */ 3082 static 3083 SCIP_RETCODE conflictResolveBound( 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, 3123 SCIPbdchginfoGetChgtype(bdchginfo) == SCIP_BOUNDCHGTYPE_BRANCHING ? "branch" 3124 : SCIPbdchginfoGetChgtype(bdchginfo) == SCIP_BOUNDCHGTYPE_CONSINFER ? "cons" : "prop", 3125 SCIPbdchginfoGetChgtype(bdchginfo) == SCIP_BOUNDCHGTYPE_BRANCHING ? "-" 3126 : SCIPbdchginfoGetChgtype(bdchginfo) == SCIP_BOUNDCHGTYPE_CONSINFER 3127 ? SCIPconsGetName(SCIPbdchginfoGetInferCons(bdchginfo)) 3128 : SCIPbdchginfoGetInferProp(bdchginfo) == NULL ? "-" 3129 : SCIPpropGetName(SCIPbdchginfoGetInferProp(bdchginfo)), 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]), 3138 SCIPvarGetName(SCIPbdchginfoGetVar(conflict->conflictset->bdchginfos[i])), 3139 SCIPbdchginfoGetBoundtype(conflict->conflictset->bdchginfos[i]) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", 3140 SCIPbdchginfoGetNewbound(conflict->conflictset->bdchginfos[i]), conflict->conflictset->relaxedbds[i]); 3141 } 3142 SCIPsetDebugMsgPrint(set, "\n"); 3143 SCIPsetDebugMsg(set, " - forced candidates :"); 3144 3145 for( i = 0; i < SCIPpqueueNElems(conflict->forcedbdchgqueue); ++i ) 3146 { 3147 SCIP_BDCHGINFO* info = (SCIP_BDCHGINFO*)(SCIPpqueueElems(conflict->forcedbdchgqueue)[i]); 3148 SCIPsetDebugMsgPrint(set, " [%d:<%s> %s %g(%g)]", SCIPbdchginfoGetDepth(info), SCIPvarGetName(SCIPbdchginfoGetVar(info)), 3149 bdchginfoIsInvalid(conflict, info) ? "<!>" : SCIPbdchginfoGetBoundtype(info) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", 3150 SCIPbdchginfoGetNewbound(info), SCIPbdchginfoGetRelaxedBound(info)); 3151 } 3152 SCIPsetDebugMsgPrint(set, "\n"); 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]); 3158 SCIPsetDebugMsgPrint(set, " [%d:<%s> %s %g(%g)]", SCIPbdchginfoGetDepth(info), SCIPvarGetName(SCIPbdchginfoGetVar(info)), 3159 bdchginfoIsInvalid(conflict, info) ? "<!>" : SCIPbdchginfoGetBoundtype(info) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", 3160 SCIPbdchginfoGetNewbound(info), SCIPbdchginfoGetRelaxedBound(info)); 3161 } 3162 SCIPsetDebugMsgPrint(set, "\n"); 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 { 3173 case SCIP_BOUNDCHGTYPE_CONSINFER: 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 3213 assert(SCIPvarGetStatus(infervar) == SCIP_VARSTATUS_AGGREGATED 3214 || SCIPvarGetStatus(infervar) == SCIP_VARSTATUS_NEGATED 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 3235 case SCIP_BOUNDCHGTYPE_PROPINFER: 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 3268 case SCIP_BOUNDCHGTYPE_BRANCHING: 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 */ 3292 static 3293 void conflictClear( 3294 SCIP_CONFLICT* conflict /**< conflict analysis data */ 3295 ) 3296 { 3297 assert(conflict != NULL); 3298 3299 SCIPpqueueClear(conflict->bdchgqueue); 3300 SCIPpqueueClear(conflict->forcedbdchgqueue); 3301 conflictsetClear(conflict->conflictset); 3302 } 3303 3304 /** initializes the propagation conflict analysis by clearing the conflict candidate queue */ 3305 SCIP_RETCODE SCIPconflictInit( 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 } 3355 SCIPhistoryScaleVSIDS(stat->glbhistory, 1.0/stat->vsidsweight); 3356 SCIPhistoryScaleVSIDS(stat->glbhistorycrun, 1.0/stat->vsidsweight); 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 */ 3371 static 3372 SCIP_RETCODE convertToActiveVar( 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 3389 if( SCIPvarGetStatus(*var) == SCIP_VARSTATUS_FIXED ) 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 */ 3406 static 3407 SCIP_Bool bdchginfoIsResolvable( 3408 SCIP_BDCHGINFO* bdchginfo /**< bound change information */ 3409 ) 3410 { 3411 assert(bdchginfo != NULL); 3412 assert(!SCIPbdchginfoIsRedundant(bdchginfo)); 3413 3414 return (SCIPbdchginfoGetChgtype(bdchginfo) == SCIP_BOUNDCHGTYPE_CONSINFER 3415 || (SCIPbdchginfoGetChgtype(bdchginfo) == SCIP_BOUNDCHGTYPE_PROPINFER 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 */ 3424 static 3425 SCIP_RETCODE conflictCreateReconvergenceConss( 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", 3485 SCIPvarGetName(SCIPbdchginfoGetVar(uip)), SCIPbdchginfoGetBoundtype(uip) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", 3486 SCIPbdchginfoGetNewbound(uip), SCIPbdchginfoGetDepth(uip), SCIPbdchginfoGetPos(uip)); 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", 3633 SCIPvarGetName(SCIPbdchginfoGetVar(uip)), SCIPvarGetName(SCIPbdchginfoGetVar(nextuip)), 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 */ 3661 SCIP_RETCODE conflictAnalyze( 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", 3714 SCIPpqueueNElems(conflict->forcedbdchgqueue), SCIPpqueueNElems(conflict->bdchgqueue), 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) 3770 || (SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_LOWER 3771 ? SCIPvarGetLbGlobal(SCIPbdchginfoGetVar(bdchginfo)) : SCIPvarGetUbGlobal(SCIPbdchginfoGetVar(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 */ 3945 static 3946 SCIP_Real calcBdchgScore( 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 3964 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN ) 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 3973 * (SCIP_Real)(SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL))/(SCIP_Real)(SCIPcolGetNNonz(col)); 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 3981 * (SCIP_Real)(SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL))/(SCIP_Real)(SCIPcolGetNNonz(col)); 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 */ 3990 static 3991 SCIP_RETCODE ensureCandsSize( 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 */ 4024 static 4025 void skipRedundantBdchginfos( 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 */ 4056 SCIP_RETCODE SCIPconflictAddBound( 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 */ 4076 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED ) 4077 return SCIP_OKAY; 4078 4079 /* if the variable is multi-aggregated, add the bounds of all aggregation variables */ 4080 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR ) 4081 { 4082 SCIP_VAR** vars; 4083 SCIP_Real* scalars; 4084 int nvars; 4085 int i; 4086 4087 vars = SCIPvarGetMultaggrVars(var); 4088 scalars = SCIPvarGetMultaggrScalars(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 */ 4117 SCIP_RETCODE SCIPconflictAddRelaxedBound( 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 */ 4141 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED ) 4142 return SCIP_OKAY; 4143 4144 /* if the variable is multi-aggregated, add the bounds of all aggregation variables */ 4145 if(SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR ) 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 */ 4281 SCIP_RETCODE SCIPconflictIsVarUsed( 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 4295 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED || SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR ) 4296 *used = FALSE; 4297 else 4298 { 4299 assert(SCIPvarIsActive(var)); 4300 assert(var != NULL); 4301 4302 switch( boundtype ) 4303 { 4304 case SCIP_BOUNDTYPE_LOWER: 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; 4316 case SCIP_BOUNDTYPE_UPPER: 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 */ 4339 static 4340 SCIP_RETCODE addBdchg( 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 4354 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN ) 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 */ 4426 static 4427 SCIP_RETCODE addCand( 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 */ 4559 SCIP_RETCODE SCIPundoBdchgsProof( 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 */ 4770 static 4771 SCIP_RETCODE undoBdchgsDualfarkas( 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 */ 4831 static 4832 SCIP_RETCODE lpbdchgsCreate( 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 */ 4858 static 4859 SCIP_RETCODE ensureSidechgsSize( 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 */ 4897 static 4898 SCIP_RETCODE addSideRemoval( 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 */ 4971 static 4972 void lpbdchgsReset( 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 */ 4984 static 4985 void lpbdchgsFree( 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 */ 5002 static 5003 SCIP_RETCODE undoBdchgsDualsol( 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 */ 5069 SCIP_RETCODE SCIPrunBoundHeuristic( 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 */ 5226 SCIPclockStart(stat->conflictlptime, set); 5227 5228 /* resolve LP */ 5229 retcode = SCIPlpiSolveDual(lpi); 5230 5231 /* stop LP timer */ 5232 SCIPclockStop(stat->conflictlptime, set); 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", 5248 iter, stat->nconflictlpiterations, SCIPlpiIsPrimalInfeasible(lpi)); 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; 5297 conflict->conflictset->conflicttype = SCIP_CONFTYPE_INFEASLP; 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; 5421 lp->lpsolstat = SCIP_LPSOLSTAT_NOTSOLVED; 5422 } 5423 } 5424 5425 /* reinstall old objective and iteration limits in LP solver */ 5426 SCIP_CALL( SCIPlpiSetRealpar(lpi, SCIP_LPPAR_OBJLIM, lp->lpiobjlim) ); 5427 SCIP_CALL( SCIPlpiSetIntpar(lpi, SCIP_LPPAR_LPITLIM, lp->lpiitlim) ); 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 */ 5448 SCIP_RETCODE SCIPconflictAnalyze( 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 */ 5473 if( !SCIPconflictApplicable(set) ) 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 */ 5484 SCIPclockStart(conflict->propanalyzetime, set); 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 } 5504