tree.c
Go to the documentation of this file.
33/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
65#define MAXREPROPMARK 511 /**< maximal subtree repropagation marker; must correspond to node data structure */
180 SCIPdebugMessage("captured LPI state of fork %p %d times -> new nlpistateref=%d\n", (void*)fork, nuses, fork->nlpistateref);
202 SCIPdebugMessage("released LPI state of fork %p -> new nlpistateref=%d\n", (void*)fork, fork->nlpistateref);
242 SCIPdebugMessage("released LPI state of subroot %p -> new nlpistateref=%d\n", (void*)subroot, subroot->nlpistateref);
255 SCIPdebugMessage("capture %d times LPI state of node #%" SCIP_LONGINT_FORMAT " at depth %d (current: %d)\n",
257 SCIPnodeGetType(node) == SCIP_NODETYPE_FORK ? node->data.fork->nlpistateref : node->data.subroot->nlpistateref);
284 SCIPdebugMessage("release LPI state of node #%" SCIP_LONGINT_FORMAT " at depth %d (current: %d)\n",
286 SCIPnodeGetType(node) == SCIP_NODETYPE_FORK ? node->data.fork->nlpistateref : node->data.subroot->nlpistateref);
321 SCIPdebugMessage("created probingnode information (%d cols, %d rows)\n", (*probingnode)->ncols, (*probingnode)->nrows);
376 SCIPdebugMessage("updated probingnode information (%d cols, %d rows)\n", probingnode->ncols, probingnode->nrows);
466 SCIPdebugMessage("creating pseudofork information with %d children (%d new cols, %d new rows)\n",
472 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*pseudofork)->addedcols, SCIPlpGetNewcols(lp), (*pseudofork)->naddedcols) ); /*lint !e666*/
479 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*pseudofork)->addedrows, SCIPlpGetNewrows(lp), (*pseudofork)->naddedrows) ); /*lint !e666*/
563 SCIPsetDebugMsg(set, "creating fork information with %u children (%d new cols, %d new rows)\n", (*fork)->nchildren, (*fork)->naddedcols, (*fork)->naddedrows);
568 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*fork)->addedcols, SCIPlpGetNewcols(lp), (*fork)->naddedcols) ); /*lint !e666*/
575 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*fork)->addedrows, SCIPlpGetNewrows(lp), (*fork)->naddedrows) ); /*lint !e666*/
660 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*subroot)->cols, SCIPlpGetCols(lp), (*subroot)->ncols) );
666 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*subroot)->rows, SCIPlpGetRows(lp), (*subroot)->nrows) );
727 assert(sibling->data.sibling.arraypos >= 0 && sibling->data.sibling.arraypos < tree->nsiblings);
790/** makes node a child of the given parent node, which must be the focus node; if the child is a probing node,
805 assert(SCIPnodeGetType(node) == SCIP_NODETYPE_CHILD || SCIPnodeGetType(node) == SCIP_NODETYPE_PROBINGNODE);
834 SCIPsetDebugMsg(set, "assigning parent #%" SCIP_LONGINT_FORMAT " to node #%" SCIP_LONGINT_FORMAT " at depth %d\n",
835 parent != NULL ? SCIPnodeGetNumber(parent) : -1, SCIPnodeGetNumber(node), SCIPnodeGetDepth(node));
866 SCIPsetDebugMsg(set, "releasing parent-child relationship of node #%" SCIP_LONGINT_FORMAT " at depth %d of type %d with parent #%" SCIP_LONGINT_FORMAT " of type %d\n",
879 assert(SCIPnodeGetType(node) == SCIP_NODETYPE_CHILD || SCIPnodeGetType(node) == SCIP_NODETYPE_PROBINGNODE
904 freeParent = (parent->data.junction.nchildren == 0); /* free parent if it has no more children */
910 freeParent = (parent->data.pseudofork->nchildren == 0); /* free parent if it has no more children */
922 freeParent = (parent->data.subroot->nchildren == 0); /* free parent if it has no more children */
925 /* the only possible child a refocused node can have in its refocus state is the probing root node;
926 * we don't want to free the refocused node, because we first have to convert it back to its original
1047 SCIP_Real estimate /**< estimate for (transformed) objective value of best feasible solution in subtree */
1059 assert(tree->focusnode == NULL || SCIPnodeGetType(tree->focusnode) == SCIP_NODETYPE_FOCUSNODE);
1083 SCIPsetDebugMsg(set, "created child node #%" SCIP_LONGINT_FORMAT " at depth %u (prio: %g)\n", SCIPnodeGetNumber(*node), (*node)->depth, nodeselprio);
1121 SCIPsetDebugMsg(set, "free node #%" SCIP_LONGINT_FORMAT " at depth %d of type %d\n", SCIPnodeGetNumber(*node), SCIPnodeGetDepth(*node), SCIPnodeGetType(*node));
1193 /* release special root LPI state capture which is used to keep the root LPI state over the whole solving
1255 assert((tree->focusnode != NULL && SCIPnodeGetType(tree->focusnode) == SCIP_NODETYPE_REFOCUSNODE)
1256 || !set->misc_calcintegral || SCIPsetIsRelEQ(set, SCIPtreeGetLowerbound(tree, set), stat->lastlowerbound));
1258 SCIPsetDebugMsg(set, "cutting off %s node #%" SCIP_LONGINT_FORMAT " at depth %d (cutoffdepth: %d)\n",
1259 node->active ? "active" : "inactive", SCIPnodeGetNumber(node), SCIPnodeGetDepth(node), tree->cutoffdepth);
1281 if( nodetype == SCIP_NODETYPE_FOCUSNODE || nodetype == SCIP_NODETYPE_CHILD || nodetype == SCIP_NODETYPE_SIBLING )
1290 /* updating the primal integral is only necessary if lower bound has increased since last evaluation */
1292 SCIPstatUpdatePrimalDualIntegrals(stat, set, transprob, origprob, SCIPsetInfinity(set), lowerbound);
1301/** marks node, that propagation should be applied again the next time, a node of its subtree is focused */
1322 SCIPsetDebugMsg(set, "marked %s node #%" SCIP_LONGINT_FORMAT " at depth %d to be propagated again (repropdepth: %d)\n",
1323 node->active ? "active" : "inactive", SCIPnodeGetNumber(node), SCIPnodeGetDepth(node), tree->repropdepth);
1340 /* if the node was the highest repropagation node in the path, update the repropdepth in the tree data */
1415 SCIPsetDebugMsg(set, "propagating again node #%" SCIP_LONGINT_FORMAT " at depth %d\n", SCIPnodeGetNumber(node), SCIPnodeGetDepth(node));
1421 SCIP_CALL( SCIPeventqueueProcess(eventqueue, blkmem, set, primal, lp, branchcand, eventfilter) );
1450 SCIP_CALL( SCIPpropagateDomains(blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
1451 eventqueue, conflict, cliquetable, SCIPnodeGetDepth(node), 0, SCIP_PROPTIMING_ALWAYS, cutoff) );
1469 SCIPsetDebugMsg(set, "repropagation %" SCIP_LONGINT_FORMAT " at depth %u changed %" SCIP_LONGINT_FORMAT " bounds (total reprop bound changes: %" SCIP_LONGINT_FORMAT "), cutoff: %u\n",
1470 stat->nreprops, node->depth, stat->nboundchgs - oldnboundchgs, stat->nrepropboundchgs, *cutoff);
1472 /* if a propagation marked with the reprop flag was successful, we want to repropagate the whole subtree */
1473 /**@todo because repropsubtree is only a bit flag, we cannot mark a whole subtree a second time for
1481 SCIPsetDebugMsg(set, "initial repropagation at depth %u changed %" SCIP_LONGINT_FORMAT " bounds -> repropagating subtree (new mark: %d)\n",
1483 assert((int)(node->repropsubtreemark) == tree->repropsubtreecount); /* bitfield must be large enough */
1519/** informs node, that it is now on the active path and applies any domain and constraint set changes */
1547 SCIPsetDebugMsg(set, "activate node #%" SCIP_LONGINT_FORMAT " at depth %d of type %d (reprop subtree mark: %u)\n",
1548 SCIPnodeGetNumber(node), SCIPnodeGetDepth(node), SCIPnodeGetType(node), node->repropsubtreemark);
1552 SCIPnodeUpdateLowerbound(node, stat, set, tree, transprob, origprob, node->parent->lowerbound);
1555 SCIP_CALL( SCIPdomchgApply(node->domchg, blkmem, set, stat, lp, branchcand, eventqueue, (int) node->depth, cutoff) );
1564 /* try to repropagate the node to see, if the propagation also leads to a conflict and a conflict constraint
1565 * could be generated; if propagation conflict analysis is turned off, repropagating the node makes no
1574 /* propagate node again, if the reprop flag is set; in the new focus node, no repropagation is necessary, because
1578 && (node->reprop || (node->parent != NULL && node->repropsubtreemark != node->parent->repropsubtreemark)) )
1582 SCIP_CALL( nodeRepropagate(node, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, conflict,
1590/** informs node, that it is no longer on the active path and undoes any domain and constraint set changes */
1608 SCIPsetDebugMsg(set, "deactivate node #%" SCIP_LONGINT_FORMAT " at depth %d of type %d (reprop subtree mark: %u)\n",
1609 SCIPnodeGetNumber(node), SCIPnodeGetDepth(node), SCIPnodeGetType(node), node->repropsubtreemark);
1625/** adds constraint locally to the node and captures it; activates constraint, if node is active;
1626 * if a local constraint is added to the root node, it is automatically upgraded into a global constraint
1654 /* add constraint addition to the node's constraint set change data, and activate constraint if node is active */
1655 SCIP_CALL( SCIPconssetchgAddAddedCons(&node->conssetchg, blkmem, set, stat, cons, (int) node->depth,
1661 /* if the constraint is added to an active node which is not a probing node, increment the corresponding counter */
1668/** locally deletes constraint at the given node by disabling its separation, enforcing, and propagation capabilities
1684 SCIPsetDebugMsg(set, "disabling constraint <%s> at node at depth %u\n", cons->name, node->depth);
1828/** adds bound change with inference information to focus node, child of focus node, or probing node;
1891 SCIPsetDebugMsg(set, "adding boundchange at node %" SCIP_LONGINT_FORMAT " at depth %u to variable <%s>: old bounds=[%g,%g], new %s bound: %g (infer%s=<%s>, inferinfo=%d)\n",
1892 node->number, node->depth, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var),
1893 boundtype == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper", newbound, infercons != NULL ? "cons" : "prop",
1894 infercons != NULL ? SCIPconsGetName(infercons) : (inferprop != NULL ? SCIPpropGetName(inferprop) : "-"), inferinfo);
1896 /* remember variable as inference variable, and get corresponding active variable, bound and bound type */
1904 SCIPerrorMessage("cannot change bounds of multi-aggregated variable <%s>\n", SCIPvarGetName(var));
1908 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
1933 SCIPerrorMessage("cannot change lower bound of variable <%s> to infinity.\n", SCIPvarGetName(var));
1950 SCIPerrorMessage("cannot change upper bound of variable <%s> to minus infinity.\n", SCIPvarGetName(var));
1963 SCIPsetDebugMsg(set, " -> transformed to active variable <%s>: old bounds=[%g,%g], new %s bound: %g, obj: %g\n",
1964 SCIPvarGetName(var), oldlb, oldub, boundtype == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper", newbound,
1967 /* if the bound change takes place at an active node but is conflicting with the current local bounds,
1968 * we cannot apply it immediately because this would introduce inconsistencies to the bound change data structures
1970 * instead we have to remember the bound change as a pending bound change and mark the affected nodes on the active
1985 SCIPsetDebugMsg(set, " -> bound change <%s> %s %g violates current local bounds [%g,%g] since depth %d: remember for later application\n",
1990 SCIP_CALL( treeAddPendingBdchg(tree, set, node, var, newbound, boundtype, infercons, inferprop, inferinfo,
1994 SCIP_CALL( SCIPnodeCutoff(tree->path[conflictingdepth], set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
2002 /* if we are in probing mode we have to additionally count the bound changes for the probing statistic */
2014 SCIP_CALL( SCIPvarChgBdGlobal(var, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable, newbound, boundtype) );
2020 SCIPsetDebugMsg(set, "marked root node to be repropagated due to global bound change <%s>:[%g,%g] -> [%g,%g] found in depth %u\n",
2043 * - if the last solved LP was the one in the current lpstatefork, the LP value in the columns are still valid
2047 || (tree->focuslpstateforklpcount == stat->lpcount && SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN) )
2054 /* remember the bound change as branching decision (infervar/infercons/inferprop are not important: use NULL) */
2055 SCIP_CALL( SCIPdomchgAddBoundchg(&node->domchg, blkmem, set, var, newbound, boundtype, SCIP_BOUNDCHGTYPE_BRANCHING,
2060 newpseudoobjval = SCIPlpGetModifiedProvedPseudoObjval(lp, set, var, oldbound, newbound, boundtype);
2062 newpseudoobjval = SCIPlpGetModifiedPseudoObjval(lp, set, transprob, var, oldbound, newbound, boundtype);
2068 SCIP_CALL( SCIPdebugCheckInference(blkmem, set, node, var, newbound, boundtype) ); /*lint !e506 !e774*/
2081 assert(node->domchg->domchgdyn.boundchgs[node->domchg->domchgdyn.nboundchgs-1].newbound == newbound); /*lint !e777*/
2088 /**@todo if the node is active, it currently must either be the effective root (see above) or the current node;
2089 * if a bound change to an intermediate active node should be added, we must make sure, the bound change
2090 * information array of the variable stays sorted (new info must be sorted in instead of putting it to
2091 * the end of the array), and we should identify now redundant bound changes that are applied at a
2095 SCIP_CALL( SCIPboundchgApply(&node->domchg->domchgdyn.boundchgs[node->domchg->domchgdyn.nboundchgs-1],
2096 blkmem, set, stat, lp, branchcand, eventqueue, (int) node->depth, node->domchg->domchgdyn.nboundchgs-1, &cutoff) );
2126 SCIP_CALL( SCIPnodeAddBoundinfer(node, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
2191 SCIPsetDebugMsg(set, "adding hole (%g,%g) at node at depth %u to variable <%s>: bounds=[%g,%g], (infer%s=<%s>, inferinfo=%d)\n",
2192 left, right, node->depth, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), infercons != NULL ? "cons" : "prop",
2193 infercons != NULL ? SCIPconsGetName(infercons) : (inferprop != NULL ? SCIPpropGetName(inferprop) : "-"), inferinfo);
2199 SCIPerrorMessage("cannot change bounds of multi-aggregated variable <%s>\n", SCIPvarGetName(var));
2203 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
2205 SCIPsetDebugMsg(set, " -> transformed to active variable <%s>: hole (%g,%g), obj: %g\n", SCIPvarGetName(var), left, right, SCIPvarGetObj(var));
2209 /* if we are in probing mode we have to additionally count the bound changes for the probing statistic */
2227 SCIPsetDebugMsg(set, "marked root node to be repropagated due to global added hole <%s>: (%g,%g) found in depth %u\n",
2241 /* if we are in probing mode we have to additionally count the bound changes for the probing statistic */
2312 /* It can happen, that a pending bound change conflicts with the global bounds, because when it was collected, it
2313 * just conflicted with the local bounds, but a conflicting global bound change was applied afterwards. In this
2318 SCIP_CALL( SCIPnodeCutoff(tree->pendingbdchgs[i].node, set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
2333 /* ignore bounds that are now redundant (for example, multiple entries in the pendingbdchgs for the same
2354 SCIP_CALL( SCIPnodeAddBoundinfer(tree->pendingbdchgs[i].node, blkmem, set, stat, transprob, origprob, tree, reopt,
2355 lp, branchcand, eventqueue, cliquetable, var, tree->pendingbdchgs[i].newbound, tree->pendingbdchgs[i].boundtype,
2356 tree->pendingbdchgs[i].infercons, tree->pendingbdchgs[i].inferprop, tree->pendingbdchgs[i].inferinfo,
2358 assert(tree->npendingbdchgs == npendingbdchgs); /* this time, the bound change can be applied! */
2376/** if given value is larger than the node's lower bound, sets the node's lower bound to the new value
2393 assert((tree->focusnode != NULL && SCIPnodeGetType(tree->focusnode) == SCIP_NODETYPE_REFOCUSNODE)
2394 || !set->misc_calcintegral || SCIPsetIsRelEQ(set, SCIPtreeGetLowerbound(tree, set), stat->lastlowerbound));
2410 if( nodetype == SCIP_NODETYPE_FOCUSNODE || nodetype == SCIP_NODETYPE_CHILD || nodetype == SCIP_NODETYPE_SIBLING )
2416 /* updating the primal integral is only necessary if lower bound has increased since last evaluation */
2418 SCIPstatUpdatePrimalDualIntegrals(stat, set, transprob, origprob, SCIPsetInfinity(set), lowerbound);
2441 /* @todo check for dual feasibility of LP solution and use sub-optimal solution if they are dual feasible */
2448 SCIP_CALL( SCIPnodeCutoff(node, set, stat, tree, transprob, origprob, set->scip->reopt, lp, set->scip->mem->probmem) );
2496 /* due to numerical reasons we need this check, see https://git.zib.de/integer/scip/issues/2866 */
2501/** propagates implications of binary fixings at the given node triggered by the implication graph and the clique table */
2528 SCIPsetDebugMsg(set, "implication graph propagation of node #%" SCIP_LONGINT_FORMAT " in depth %d\n",
2570 /* @note should this be checked here (because SCIPnodeAddBoundinfer fails for multi-aggregated variables)
2610 SCIP_CALL( SCIPnodeAddBoundinfer(node, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
2669 SCIP_CALL( SCIPnodeAddBoundinfer(node, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
2670 eventqueue, cliquetable, vars[k], (SCIP_Real)(!values[k]), values[k] ? SCIP_BOUNDTYPE_UPPER : SCIP_BOUNDTYPE_LOWER,
2730 || (ncols == node->data.probingnode->ninitialcols && nrows == node->data.probingnode->ninitialrows));
2793/** finds the common fork node, the new LP state defining fork, and the new focus subroot, if the path is switched to
2804 SCIP_Bool* cutoff /**< pointer to store whether the given node can be cut off and no path switching
2819 assert(tree->focuslpstatefork == NULL || tree->focuslpstatefork->depth <= tree->focuslpfork->depth);
2821 assert(tree->focussubroot == NULL || tree->focussubroot->depth <= tree->focuslpstatefork->depth);
2840 /* if the new focus node is NULL, there is no common fork node, and the new LP fork, LP state fork, and subroot
2857 /* if the old focus node is NULL, there is no common fork node, and we have to search the new LP fork, LP state fork
2869 && SCIPnodeGetType(lpfork) != SCIP_NODETYPE_FORK && SCIPnodeGetType(lpfork) != SCIP_NODETYPE_SUBROOT )
2883 while( SCIPnodeGetType(lpstatefork) != SCIP_NODETYPE_FORK && SCIPnodeGetType(lpstatefork) != SCIP_NODETYPE_SUBROOT )
2923 /* find the common fork node, the new LP defining fork, the new LP state defining fork, and the new focus subroot */
2942 || SCIPnodeGetType(fork) == SCIP_NODETYPE_FORK || SCIPnodeGetType(fork) == SCIP_NODETYPE_SUBROOT) )
2945 && (SCIPnodeGetType(fork) == SCIP_NODETYPE_FORK || SCIPnodeGetType(fork) == SCIP_NODETYPE_SUBROOT) )
2955 /* if the common fork node is below the current cutoff depth, the cutoff node is an ancestor of the common fork
2974 /* if not already found, continue searching the LP defining fork; it cannot be deeper than the common fork */
2979 /* focuslpfork is not on the same active path as the new node: we have to continue searching */
2992 /* focuslpfork is on the same active path as the new node: old and new node have the same lpfork */
3002 SCIPdebugMessage("find switch forks: lpforkdepth=%d\n", lpfork == NULL ? -1 : (int)(lpfork->depth));
3004 /* if not already found, continue searching the LP state defining fork; it cannot be deeper than the
3011 /* focuslpstatefork is not on the same active path as the new node: we have to continue searching */
3026 /* focuslpstatefork is on the same active path as the new node: old and new node have the same lpstatefork */
3036 SCIPdebugMessage("find switch forks: lpstateforkdepth=%d\n", lpstatefork == NULL ? -1 : (int)(lpstatefork->depth));
3038 /* if not already found, continue searching the subroot; it cannot be deeper than the LP defining fork, the
3045 /* focussubroot is not on the same active path as the new node: we have to continue searching */
3065 SCIPdebugMessage("find switch forks: subrootdepth=%d\n", subroot == NULL ? -1 : (int)(subroot->depth));
3067 /* if a node prior to the common fork should be repropagated, we select the node to be repropagated as common
3068 * fork in order to undo all bound changes up to this node, repropagate the node, and redo the bound changes
3095/** switches the active path to the new focus node, frees dead end, applies domain and constraint set changes */
3119 int forkdepth; /* depth of the common subroot/fork/pseudofork/junction node, or -1 if no common fork exists */
3142 /* delay events in node deactivations to fork and node activations to parent of new focus node */
3145 /* undo the domain and constraint set changes of the old active path by deactivating the path's nodes */
3148 SCIP_CALL( nodeDeactivate(tree->path[i], blkmem, set, stat, tree, lp, branchcand, eventqueue) );
3153 SCIP_CALL( treeApplyPendingBdchgs(tree, reopt, blkmem, set, stat, transprob, origprob, lp, branchcand, eventqueue, cliquetable) );
3208 SCIP_CALL( SCIPnodeFree(&oldfocusnode, blkmem, set, stat, eventfilter, eventqueue, tree, lp) );
3217 /* promote the constraint set and bound changes up to the new effective root to be global changes */
3221 "shift effective root from depth %d to %d: applying constraint set and bound changes to global problem\n",
3224 /* at first globalize constraint changes to update constraint handlers before changing bounds */
3229 SCIP_CALL( SCIPconssetchgMakeGlobal(&tree->path[i]->conssetchg, blkmem, set, stat, transprob, reopt) );
3232 /* at last globalize bound changes triggering delayed events processed after the path switch */
3233 for( i = tree->appliedeffectiverootdepth + 1; i <= newappliedeffectiverootdepth && !(*cutoff); ++i )
3237 SCIP_CALL( SCIPdomchgApplyGlobal(tree->path[i]->domchg, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable, cutoff) );
3254 SCIP_CALL( nodeRepropagate(fork, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, conflict,
3260 * on the way, domain propagation might be applied again to the path's nodes, which can result in the cutoff of
3262 * We only activate all nodes down to the parent of the new focus node, because the events in this process are
3263 * delayed, which means that multiple changes of a bound of a variable are merged (and might even be cancelled out,
3264 * if the bound is first relaxed when deactivating a node on the old path and then tightened to the same value
3266 * This is valid for all nodes down to the parent of the new focus node, since they have already been propagated.
3267 * Bound change events on the new focus node, however, must not be cancelled out, since they need to be propagated
3268 * and thus, the event must be thrown and catched by the constraint handlers to mark constraints for propagation.
3277 SCIP_CALL( nodeActivate(tree->path[i], blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand,
3282 SCIP_CALL( SCIPeventqueueProcess(eventqueue, blkmem, set, primal, lp, branchcand, eventfilter) );
3292 SCIP_CALL( nodeActivate(tree->path[focusnodedepth], blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand,
3299 SCIP_CALL( SCIPnodeCutoff(tree->focusnode, set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
3349 SCIP_CALL( SCIPlpAddRow(lp, blkmem, set, eventqueue, eventfilter, rows[r], (int) subroot->depth) );
3394 SCIP_CALL( SCIPlpAddRow(lp, blkmem, set, eventqueue, eventfilter, rows[r], (int) fork->depth) );
3439 SCIP_CALL( SCIPlpAddRow(lp, blkmem, set, eventqueue, eventfilter, rows[r], (int) pseudofork->depth) );
3473 || (ncols == node->data.probingnode->ninitialcols && nrows == node->data.probingnode->ninitialrows));
3507 SCIPerrorMessage("node at depth %d on active path has to be of type JUNCTION, PSEUDOFORK, FORK, SUBROOT, FOCUSNODE, REFOCUSNODE, or PROBINGNODE, but is %d\n",
3527 SCIP_Bool* initroot /**< pointer to store whether the root LP relaxation has to be initialized */
3551 SCIPsetDebugMsg(set, "-> old LP has %d cols and %d rows\n", SCIPlpGetNCols(lp), SCIPlpGetNRows(lp));
3573 || SCIPnodeGetType(lpfork) == SCIP_NODETYPE_FORK || SCIPnodeGetType(lpfork) == SCIP_NODETYPE_SUBROOT);
3578 assert(lpforkdepth < tree->pathlen-1); /* lpfork must not be the last (the focus) node of the active path */
3584 assert(lpforkdepth == -1 || tree->pathnlpcols[tree->correctlpdepth] <= tree->pathnlpcols[lpforkdepth]);
3585 assert(lpforkdepth == -1 || tree->pathnlprows[tree->correctlpdepth] <= tree->pathnlprows[lpforkdepth]);
3589 SCIP_CALL( SCIPlpShrinkRows(lp, blkmem, set, eventqueue, eventfilter, tree->pathnlprows[tree->correctlpdepth]) );
3625 assert(lpforkdepth == -1 || tree->pathnlpcols[tree->correctlpdepth] == tree->pathnlpcols[lpforkdepth]);
3626 assert(lpforkdepth == -1 || tree->pathnlprows[tree->correctlpdepth] == tree->pathnlprows[lpforkdepth]);
3636 SCIPsetDebugMsg(set, "-> new LP has %d cols and %d rows\n", SCIPlpGetNCols(lp), SCIPlpGetNRows(lp));
3678 SCIPsetDebugMsg(set, "load LP state for current fork node #%" SCIP_LONGINT_FORMAT " at depth %d\n",
3689 assert(SCIPnodeGetType(lpstatefork) == SCIP_NODETYPE_FORK || SCIPnodeGetType(lpstatefork) == SCIP_NODETYPE_SUBROOT);
3693 assert(lpstateforkdepth < tree->pathlen-1); /* lpstatefork must not be the last (the focus) node of the active path */
3694 assert(lpstateforkdepth <= tree->correctlpdepth); /* LP must have been constructed at least up to the fork depth */
3695 assert(tree->pathnlpcols[tree->correctlpdepth] >= tree->pathnlpcols[lpstateforkdepth]); /* LP can only grow */
3696 assert(tree->pathnlprows[tree->correctlpdepth] >= tree->pathnlprows[lpstateforkdepth]); /* LP can only grow */
3712 SCIP_CALL( SCIPlpSetState(lp, blkmem, set, prob, eventqueue, lpstatefork->data.subroot->lpistate,
3723 /* we do not need to check the bounds, since primalfeasible is updated anyway when flushing the LP */
3739 /* check the path from LP fork to focus node for domain changes (destroying primal feasibility of LP basis) */
3745 lp->primalfeasible = (tree->path[d]->domchg == NULL || tree->path[d]->domchg->domchgbound.nboundchgs == 0);
3751 SCIPsetDebugMsg(set, "-> primalfeasible=%u, dualfeasible=%u\n", lp->primalfeasible, lp->dualfeasible);
3779 SCIP_Real cutoffbound /**< cutoff bound: all nodes with lowerbound >= cutoffbound are cut off */
3782 assert(SCIPnodeGetType(*node) == SCIP_NODETYPE_SIBLING || SCIPnodeGetType(*node) == SCIP_NODETYPE_CHILD
3786 assert(lpstatefork == NULL || lpstatefork->active || SCIPsetIsGE(set, (*node)->lowerbound, cutoffbound));
3792 /* check, if the LP state fork is the first node with LP state information on the path back to the root */
3793 if( !SCIPsetIsInfinity(set, -cutoffbound) ) /* if the node was cut off in SCIPnodeFocus(), the lpstatefork is invalid */
3808 if( !SCIPsetIsInfinity(set, (*node)->lowerbound) && SCIPsetIsLT(set, (*node)->lowerbound, cutoffbound) )
3811 SCIPsetDebugMsg(set, "convert node #%" SCIP_LONGINT_FORMAT " at depth %d to leaf with lpstatefork #%" SCIP_LONGINT_FORMAT " at depth %d\n",
3830 SCIP_CALL( SCIPnodeCutoff(*node, set, stat, tree, set->scip->transprob, set->scip->origprob, reopt, lp, blkmem) );
3842/** removes variables from the problem, that are marked to be deletable, and were created at the focusnode;
3843 * only removes variables that were created at the focusnode, unless inlp is TRUE (e.g., when the node is cut off, anyway)
3884 /* also delete variables currently in the LP, thus remove all new variables from the LP, first */
3911 tree, reopt, lp, branchcand, eventqueue, cliquetable, var, 0.0, SCIP_BOUNDTYPE_LOWER, FALSE) );
3916 tree, reopt, lp, branchcand, eventqueue, cliquetable, var, 0.0, SCIP_BOUNDTYPE_UPPER, FALSE) );
3934 SCIPsetDebugMsg(set, "delvars at node %" SCIP_LONGINT_FORMAT ", deleted %d vars\n", stat->nnodes, ndelvars);
3939 SCIP_CALL( SCIPprobPerformVarDeletions(transprob, blkmem, set, stat, eventqueue, cliquetable, lp, branchcand) );
3971 /* remove variables from the problem that are marked as deletable and were created at this node */
3972 SCIP_CALL( focusnodeCleanupVars(blkmem, set, stat, eventqueue, transprob, origprob, tree, reopt, lp, branchcand, cliquetable, TRUE) );
3997 SCIP_Real cutoffbound /**< cutoff bound: all nodes with lowerbound >= cutoffbound are cut off */
4010 SCIP_CALL( nodeToLeaf(&tree->focusnode, blkmem, set, stat, eventfilter, eventqueue, tree, reopt, lp, lpstatefork, cutoffbound));
4028 assert(tree->focusnode->active); /* otherwise, no children could be created at the focus node */
4074 assert(tree->focusnode->active); /* otherwise, no children could be created at the focus node */
4082 /* remove variables from the problem that are marked as deletable and were created at this node */
4083 SCIP_CALL( focusnodeCleanupVars(blkmem, set, stat, eventqueue, transprob, origprob, tree, reopt, lp, branchcand, cliquetable, FALSE) );
4128 assert(tree->focusnode->active); /* otherwise, no children could be created at the focus node */
4145 SCIP_CALL( SCIPlpCleanupNew(lp, blkmem, set, stat, eventqueue, eventfilter, (tree->focusnode->depth == 0)) );
4149 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, -1LL, FALSE, FALSE, TRUE, &lperror) );
4159 * - Something numerically weird happened after cleaning up or after resolving a diving or probing LP.
4169 "(node %" SCIP_LONGINT_FORMAT ") numerical troubles: LP %" SCIP_LONGINT_FORMAT " not optimal -- convert node into junction instead of fork\n",
4174 SCIP_CALL( SCIPlpShrinkRows(lp, blkmem, set, eventqueue, eventfilter, SCIPlpGetNRows(lp) - SCIPlpGetNNewrows(lp)) );
4185 /* remove variables from the problem that are marked as deletable, were created at this node and are not contained in the LP */
4186 SCIP_CALL( focusnodeCleanupVars(blkmem, set, stat, eventqueue, transprob, origprob, tree, reopt, lp, branchcand, cliquetable, FALSE) );
4197 /* capture the LPI state of the root node to ensure that the LPI state of the root stays for the whole solving
4241 assert(tree->focusnode->active); /* otherwise, no children could be created at the focus node */
4260 SCIP_CALL( SCIPlpCleanupAll(lp, blkmem, set, stat, eventqueue, eventfilter, (tree->focusnode->depth == 0)) );
4270 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, -1LL, FALSE, FALSE, TRUE, &lperror) );
4290 "(node %" SCIP_LONGINT_FORMAT ") numerical troubles: LP %" SCIP_LONGINT_FORMAT " not optimal -- convert node into junction instead of subroot\n",
4295 SCIP_CALL( SCIPlpShrinkRows(lp, blkmem, set, eventqueue, eventfilter, SCIPlpGetNRows(lp) - SCIPlpGetNNewrows(lp)) );
4306 /* remove variables from the problem that are marked as deletable, were created at this node and are not contained in the LP */
4307 SCIP_CALL( focusnodeCleanupVars(blkmem, set, stat, eventqueue, transprob, origprob, tree, lp, branchcand, cliquetable, FALSE) );
4348 SCIP_Real cutoffbound /**< cutoff bound: all nodes with lowerbound >= cutoffbound are cut off */
4359 /* convert last node to LEAF and put it into leaves queue, or delete it if its lower bound exceeds the cutoff bound */
4362 SCIP_CALL( nodeToLeaf(&nodes[*nnodes-1], blkmem, set, stat, eventfilter, eventqueue, tree, reopt, lp, lpstatefork, cutoffbound) );
4404 /* because CHILD and SIBLING structs contain the same data in the same order, we do not have to copy it */
4405 assert(&(tree->siblings[i]->data.sibling.arraypos) == &(tree->siblings[i]->data.child.arraypos));
4461 *node != NULL ? SCIPnodeGetNumber(*node) : -1, *node != NULL ? (int)SCIPnodeGetType(*node) : 0,
4464 /* remember old cutoff depth in order to know, whether the children and siblings can be deleted */
4471 SCIPsetDebugMsg(set, "focus node: focusnodedepth=%ld, forkdepth=%ld, lpforkdepth=%ld, lpstateforkdepth=%ld, subrootdepth=%ld, cutoff=%u\n",
4472 *node != NULL ? (long)((*node)->depth) : -1, fork != NULL ? (long)(fork->depth) : -1, /*lint !e705 */
4473 lpfork != NULL ? (long)(lpfork->depth) : -1, lpstatefork != NULL ? (long)(lpstatefork->depth) : -1, /*lint !e705 */
4488 SCIPsetDebugMsg(set, "cutting off leaf node #%lld (queuelen=%d) at depth %d with lowerbound=%g\n",
4489 SCIPnodeGetNumber(*node), SCIPnodepqLen(tree->leaves), SCIPnodeGetDepth(*node), SCIPnodeGetLowerbound(*node));
4495 SCIPlpGetSolstat(lp), tree->root == *node, FALSE, (*node)->lowerbound, tree->effectiverootdepth) );
4515 /* updating the primal integral is only necessary if lower bound has increased since last evaluation */
4517 SCIPstatUpdatePrimalDualIntegrals(stat, set, transprob, origprob, SCIPsetInfinity(set), lowerbound);