methods and datastructures for conflict analysis
This file implements a conflict analysis method like the one used in modern SAT solvers like zchaff. The algorithm works as follows:
Given is a set of bound changes that are not allowed being applied simultaneously, because they render the current node infeasible (e.g. because a single constraint is infeasible in the these bounds, or because the LP relaxation is infeasible). The goal is to deduce a clause on variables – a conflict clause – representing the "reason" for this conflict, i.e., the branching decisions or the deductions (applied e.g. in domain propagation) that lead to the conflict. This clause can then be added to the constraint set to help cutting off similar parts of the branch and bound tree, that would lead to the same conflict. A conflict clause can also be generated, if the conflict was detected by a locally valid constraint. In this case, the resulting conflict clause is also locally valid in the same depth as the conflict detecting constraint. If all involved variables are binary, a linear (set covering) constraint can be generated, otherwise a bound disjunction constraint is generated. Details are given in
Tobias Achterberg, Conflict Analysis in Mixed Integer Programming
Discrete Optimization, 4, 4-20 (2007)
See also How to use conflict analysis. Here is an outline of the algorithm:
If all deduced bound changes come with (global) inference information, depending on the conflict analyzing strategy, the resulting conflict set has the following property:
The user has to do the following to get the conflict analysis running in its current implementation:
Definition in file conflict_graphanalysis.c.
#include "lpi/lpi.h"
#include "scip/conflict_graphanalysis.h"
#include "scip/conflict_dualproofanalysis.h"
#include "scip/clock.h"
#include "scip/conflict.h"
#include "scip/cons.h"
#include "scip/cons_linear.h"
#include "scip/cuts.h"
#include "scip/history.h"
#include "scip/lp.h"
#include "scip/presolve.h"
#include "scip/prob.h"
#include "scip/prop.h"
#include "scip/pub_conflict.h"
#include "scip/pub_cons.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_paramset.h"
#include "scip/pub_prop.h"
#include "scip/pub_tree.h"
#include "scip/pub_var.h"
#include "scip/scip_conflict.h"
#include "scip/scip_cons.h"
#include "scip/scip_mem.h"
#include "scip/scip_sol.h"
#include "scip/scip_var.h"
#include "scip/set.h"
#include "scip/sol.h"
#include "scip/struct_conflict.h"
#include "scip/struct_lp.h"
#include "scip/struct_prob.h"
#include "scip/struct_set.h"
#include "scip/struct_stat.h"
#include "scip/struct_tree.h"
#include "scip/struct_var.h"
#include "scip/tree.h"
#include "scip/var.h"
#include "scip/visual.h"
#include <string.h>
#include <strings.h>
Go to the source code of this file.
|
static |
Conflict sets resizes the arrays of the conflict set to be able to store at least num bound change entries
conflictset | conflict set |
blkmem | block memory of transformed problem |
set | global SCIP settings |
num | minimal number of slots in arrays |
Definition at line 378 of file conflict_graphanalysis.c.
References assert(), SCIP_ConflictSet::bdchginfos, SCIP_ConflictSet::bdchginfossize, BMSreallocBlockMemoryArray, NULL, SCIP_ConflictSet::relaxedbds, SCIP_ALLOC, SCIP_OKAY, SCIPsetCalcMemGrowSize(), and SCIP_ConflictSet::sortvals.
Referenced by conflictsetAddBound(), and conflictsetAddBounds().
|
static |
adds a bound change to a conflict set
conflictset | conflict set |
blkmem | block memory of transformed problem |
set | global SCIP settings |
bdchginfo | bound change to add to the conflict set |
relaxedbd | relaxed bound |
Definition at line 405 of file conflict_graphanalysis.c.
References assert(), SCIP_ConflictSet::bdchginfos, conflictsetEnsureBdchginfosMem(), SCIP_ConflictSet::hasrelaxonlyvar, MAX, MIN, SCIP_ConflictSet::nbdchginfos, NULL, SCIP_ConflictSet::relaxedbds, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbdchginfoGetBoundtype(), SCIPbdchginfoGetVar(), SCIPbdchginfoIsTighter(), SCIPsortedvecDelPosIntPtrReal(), SCIPsortedvecInsertIntPtrReal(), SCIPvarGetIndex(), SCIPvarIsRelaxationOnly(), SCIP_ConflictSet::sortvals, TRUE, and var.
Referenced by conflictAddConflictBound(), and conflictsetAddBounds().
|
static |
calculates the conflict and the repropagation depths of the conflict set
conflictset | conflict set |
Definition at line 478 of file conflict_graphanalysis.c.
References assert(), SCIP_ConflictSet::bdchginfos, SCIP_ConflictSet::conflictdepth, depth, i, SCIP_ConflictSet::insertdepth, maxdepth, SCIP_ConflictSet::nbdchginfos, NULL, SCIP_ConflictSet::repropdepth, SCIPbdchginfoGetDepth(), and SCIP_ConflictSet::validdepth.
Referenced by conflictInsertConflictset().
|
static |
identifies the depth, at which the conflict set should be added:
conflictset | conflict set |
set | global SCIP settings |
tree | branch and bound tree |
Definition at line 522 of file conflict_graphanalysis.c.
References assert(), SCIP_ConflictSet::bdchginfos, BMSclearMemoryArray, depth, i, SCIP_ConflictSet::insertdepth, MIN, SCIP_ConflictSet::nbdchginfos, NULL, SCIP_Tree::pathlen, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPbdchginfoGetDepth(), SCIPsetAllocBufferArray, SCIPsetFreeBufferArray, SCIPtreeGetCurrentDepth(), TRUE, and SCIP_ConflictSet::validdepth.
Referenced by conflictAddConflictset().
|
static |
checks whether the first conflict set is redundant to the second one
conflictset1 | first conflict conflict set |
conflictset2 | second conflict conflict set |
Definition at line 569 of file conflict_graphanalysis.c.
References assert(), SCIP_ConflictSet::bdchginfos, FALSE, SCIP_ConflictSet::nbdchginfos, NULL, SCIP_Bool, SCIPbdchginfoIsTighter(), SCIP_ConflictSet::sortvals, and SCIP_ConflictSet::validdepth.
Referenced by conflictInsertConflictset().
|
static |
check conflict set for redundancy, other conflicts in the same conflict analysis could have led to global reductions an made this conflict set redundant
set | global SCIP settings |
conflictset | conflict set |
Definition at line 633 of file conflict_graphanalysis.c.
References assert(), SCIP_ConflictSet::bdchginfos, bound, FALSE, SCIP_ConflictSet::nbdchginfos, NULL, SCIP_ConflictSet::relaxedbds, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPbdchginfoGetBoundtype(), SCIPbdchginfoGetNewbound(), SCIPbdchginfoGetVar(), SCIPsetIsFeasGE(), SCIPsetIsFeasLE(), SCIPsetIsGE(), SCIPsetIsIntegral(), SCIPsetIsLE(), SCIPvarGetLbGlobal(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), TRUE, and var.
Referenced by detectImpliedBounds().
|
static |
find global fixings which can be derived from the new conflict set
set | global SCIP settings |
prob | transformed problem after presolve |
stat | dynamic SCIP statistics |
tree | tree data |
blkmem | block memory |
origprob | original problem |
reopt | reoptimization data |
lp | LP data |
conflictset | conflict set to add to the tree |
nbdchgs | number of global deducted bound changes due to the conflict set |
nredvars | number of redundant and removed variables from conflict set |
redundant | did we found a global reduction on a conflict set variable, which makes this conflict redundant |
Definition at line 698 of file conflict_graphanalysis.c.
References assert(), SCIP_ConflictSet::bdchginfos, BMSclearMemoryArray, bound, checkRedundancy(), FALSE, SCIP_ConflictSet::nbdchginfos, NULL, SCIP_ConflictSet::relaxedbds, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPbdchginfoGetBoundtype(), SCIPbdchginfoGetNewbound(), SCIPbdchginfoGetVar(), SCIPboundtypeOpposite(), SCIPnodeCutoff(), SCIPprobGetName(), SCIPprobIsTransformed(), SCIPsetAllocBufferArray, SCIPsetAllocCleanBufferArray, SCIPsetDebugMsg, SCIPsetDebugMsgPrint, SCIPsetFreeBufferArray, SCIPsetFreeCleanBufferArray, SCIPsetIsEQ(), SCIPsetIsFeasEQ(), SCIPsetIsFeasGT(), SCIPsetIsFeasLT(), SCIPsetIsGE(), SCIPsetIsIntegral(), SCIPsetIsLE(), SCIPsetIsZero(), SCIPshrinkDisjunctiveVarSet(), SCIPsortLongPtrRealRealBool(), SCIPtreeGetRootNode(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNCliques(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), SCIPvarIsIntegral(), SCIP_ConflictSet::sortvals, TRUE, var, and vars.
Referenced by conflictAddConflictCons().
|
static |
clears the given conflict set
conflictset | conflict set |
Definition at line 971 of file conflict_graphanalysis.c.
References assert(), SCIP_ConflictSet::conflictdepth, SCIP_ConflictSet::conflicttype, FALSE, SCIP_ConflictSet::hasrelaxonlyvar, SCIP_ConflictSet::insertdepth, SCIP_ConflictSet::nbdchginfos, NULL, SCIP_ConflictSet::repropagate, SCIP_ConflictSet::repropdepth, SCIP_CONFTYPE_UNKNOWN, TRUE, SCIP_ConflictSet::usescutoffbound, and SCIP_ConflictSet::validdepth.
Referenced by conflictClear(), and SCIPconflictsetCreate().
SCIP_RETCODE SCIPconflictsetCreate | ( | SCIP_CONFLICTSET ** | conflictset, |
BMS_BLKMEM * | blkmem ) |
creates an empty conflict set
conflictset | pointer to store the conflict set |
blkmem | block memory of transformed problem |
Definition at line 989 of file conflict_graphanalysis.c.
References assert(), BMSallocBlockMemory, conflictsetClear(), NULL, SCIP_ALLOC, and SCIP_OKAY.
Referenced by SCIPconflictCreate().
|
static |
creates a copy of the given conflict set, allocating an additional amount of memory
targetconflictset | pointer to store the conflict set |
blkmem | block memory of transformed problem |
sourceconflictset | source conflict set |
nadditionalelems | number of additional elements to allocate memory for |
Definition at line 1009 of file conflict_graphanalysis.c.
References assert(), SCIP_ConflictSet::bdchginfos, BMSallocBlockMemory, BMSallocBlockMemoryArray, BMScopyMemoryArray, SCIP_ConflictSet::conflictdepth, SCIP_ConflictSet::conflicttype, SCIP_ConflictSet::hasrelaxonlyvar, SCIP_ConflictSet::insertdepth, SCIP_ConflictSet::nbdchginfos, NULL, SCIP_ConflictSet::relaxedbds, SCIP_ConflictSet::repropdepth, SCIP_ALLOC, SCIP_OKAY, SCIP_ConflictSet::sortvals, SCIP_ConflictSet::usescutoffbound, and SCIP_ConflictSet::validdepth.
Referenced by conflictAddConflictset().
void SCIPconflictsetFree | ( | SCIP_CONFLICTSET ** | conflictset, |
BMS_BLKMEM * | blkmem ) |
frees a conflict set
conflictset | pointer to the conflict set |
blkmem | block memory of transformed problem |
Definition at line 1045 of file conflict_graphanalysis.c.
References assert(), BMSfreeBlockMemory, BMSfreeBlockMemoryArrayNull, and NULL.
Referenced by conflictAddConflictset(), conflictInsertConflictset(), SCIPconflictFlushConss(), and SCIPconflictFree().
|
static |
calculates the score of the conflict set
the score is weighted sum of number of bound changes, repropagation depth, and valid depth
conflictset | conflict set |
set | global SCIP settings |
Definition at line 1064 of file conflict_graphanalysis.c.
References assert(), SCIP_ConflictSet::nbdchginfos, NULL, SCIP_ConflictSet::repropdepth, SCIP_Real, and SCIP_ConflictSet::validdepth.
Referenced by conflictInsertConflictset().
|
static |
method to call, when the priority of a conflict handler was changed
Definition at line 1095 of file conflict_graphanalysis.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPparamGetData(), SCIPparamGetInt(), and SCIPsetConflicthdlrPriority().
SCIP_RETCODE SCIPconflicthdlrCopyInclude | ( | SCIP_CONFLICTHDLR * | conflicthdlr, |
SCIP_SET * | set ) |
copies the given conflict handler to a new scip
Definition at line 1109 of file conflict_graphanalysis.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconflicthdlrGetName(), and SCIPsetDebugMsg.
Referenced by SCIPsetCopyPlugins().
|
static |
internal method for creating a conflict handler
conflicthdlr | pointer to conflict handler data structure |
set | global SCIP settings |
messagehdlr | message handler |
blkmem | block memory for parameter settings |
name | name of conflict handler |
desc | description of conflict handler |
priority | priority of the conflict handler |
conflicthdlrdata | conflict handler data |
Definition at line 1129 of file conflict_graphanalysis.c.
References assert(), BMSallocMemory, BMSclearMemory, BMSduplicateMemoryArray, FALSE, NULL, paramname, SCIP_ALLOC, SCIP_CALL, SCIP_CLOCKTYPE_DEFAULT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPclockCreate(), SCIPsetAddIntParam(), SCIPsnprintf(), and TRUE.
Referenced by SCIPconflicthdlrCreate().
SCIP_RETCODE SCIPconflicthdlrCreate | ( | SCIP_CONFLICTHDLR ** | conflicthdlr, |
SCIP_SET * | set, | ||
SCIP_MESSAGEHDLR * | messagehdlr, | ||
BMS_BLKMEM * | blkmem, | ||
const char * | name, | ||
const char * | desc, | ||
int | priority, | ||
SCIP_DECL_CONFLICTCOPY((*conflictcopy)) | , | ||
SCIP_DECL_CONFLICTFREE((*conflictfree)) | , | ||
SCIP_DECL_CONFLICTINIT((*conflictinit)) | , | ||
SCIP_DECL_CONFLICTEXIT((*conflictexit)) | , | ||
SCIP_DECL_CONFLICTINITSOL((*conflictinitsol)) | , | ||
SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol)) | , | ||
SCIP_DECL_CONFLICTEXEC((*conflictexec)) | , | ||
SCIP_CONFLICTHDLRDATA * | conflicthdlrdata ) |
creates a conflict handler
conflicthdlr | pointer to conflict handler data structure |
set | global SCIP settings |
messagehdlr | message handler |
blkmem | block memory for parameter settings |
name | name of conflict handler |
desc | description of conflict handler |
priority | priority of the conflict handler |
conflicthdlrdata | conflict handler data |
Definition at line 1183 of file conflict_graphanalysis.c.
References assert(), doConflicthdlrCreate(), NULL, SCIP_CALL_FINALLY, SCIP_OKAY, and SCIPconflicthdlrFree().
Referenced by SCIPincludeConflicthdlr(), and SCIPincludeConflicthdlrBasic().
SCIP_RETCODE SCIPconflicthdlrFree | ( | SCIP_CONFLICTHDLR ** | conflicthdlr, |
SCIP_SET * | set ) |
calls destructor and frees memory of conflict handler
conflicthdlr | pointer to conflict handler data structure |
set | global SCIP settings |
Definition at line 1214 of file conflict_graphanalysis.c.
References assert(), BMSfreeMemory, BMSfreeMemoryArrayNull, NULL, SCIP_CALL, SCIP_OKAY, and SCIPclockFree().
Referenced by SCIPconflicthdlrCreate().
SCIP_RETCODE SCIPconflicthdlrInit | ( | SCIP_CONFLICTHDLR * | conflicthdlr, |
SCIP_SET * | set ) |
calls initialization method of conflict handler
conflicthdlr | conflict handler |
set | global SCIP settings |
Definition at line 1242 of file conflict_graphanalysis.c.
References assert(), SCIP_Conflicthdlr::conflicttime, SCIP_Conflicthdlr::initialized, SCIP_Conflicthdlr::name, NULL, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPclockReset(), SCIPclockStart(), SCIPclockStop(), SCIPerrorMessage, SCIP_Conflicthdlr::setuptime, and TRUE.
SCIP_RETCODE SCIPconflicthdlrExit | ( | SCIP_CONFLICTHDLR * | conflicthdlr, |
SCIP_SET * | set ) |
calls exit method of conflict handler
conflicthdlr | conflict handler |
set | global SCIP settings |
Definition at line 1279 of file conflict_graphanalysis.c.
References assert(), FALSE, SCIP_Conflicthdlr::initialized, SCIP_Conflicthdlr::name, NULL, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPclockStart(), SCIPclockStop(), SCIPerrorMessage, and SCIP_Conflicthdlr::setuptime.
SCIP_RETCODE SCIPconflicthdlrInitsol | ( | SCIP_CONFLICTHDLR * | conflicthdlr, |
SCIP_SET * | set ) |
informs conflict handler that the branch and bound process is being started
conflicthdlr | conflict handler |
set | global SCIP settings |
Definition at line 1310 of file conflict_graphanalysis.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPclockStart(), SCIPclockStop(), and SCIP_Conflicthdlr::setuptime.
SCIP_RETCODE SCIPconflicthdlrExitsol | ( | SCIP_CONFLICTHDLR * | conflicthdlr, |
SCIP_SET * | set ) |
informs conflict handler that the branch and bound process data is being freed
conflicthdlr | conflict handler |
set | global SCIP settings |
Definition at line 1334 of file conflict_graphanalysis.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPclockStart(), SCIPclockStop(), and SCIP_Conflicthdlr::setuptime.
SCIP_RETCODE SCIPconflicthdlrExec | ( | SCIP_CONFLICTHDLR * | conflicthdlr, |
SCIP_SET * | set, | ||
SCIP_NODE * | node, | ||
SCIP_NODE * | validnode, | ||
SCIP_BDCHGINFO ** | bdchginfos, | ||
SCIP_Real * | relaxedbds, | ||
int | nbdchginfos, | ||
SCIP_CONFTYPE | conftype, | ||
SCIP_Bool | usescutoffbound, | ||
SCIP_Bool | resolved, | ||
SCIP_RESULT * | result ) |
calls execution method of conflict handler
conflicthdlr | conflict handler |
set | global SCIP settings |
node | node to add conflict constraint to |
validnode | node at which the constraint is valid |
bdchginfos | bound change resembling the conflict set |
relaxedbds | array with relaxed bounds which are efficient to create a valid conflict |
nbdchginfos | number of bound changes in the conflict set |
conftype | type of the conflict |
usescutoffbound | depends the conflict on the cutoff bound? |
resolved | was the conflict set already used to create a constraint? |
result | pointer to store the result of the callback method |
Definition at line 1358 of file conflict_graphanalysis.c.
References assert(), SCIP_Conflicthdlr::conflicttime, SCIP_Conflicthdlr::name, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_CONSADDED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_INVALIDRESULT, SCIP_OKAY, SCIP_Real, SCIPclockStart(), SCIPclockStop(), SCIPerrorMessage, and SCIPnodeGetDepth().
Referenced by conflictAddConflictCons().
void SCIPconflicthdlrSetCopy | ( | SCIP_CONFLICTHDLR * | conflicthdlr | ) |
set copy method of conflict handler
conflicthdlr | conflict handler copy method of the conflict handler |
Definition at line 1426 of file conflict_graphanalysis.c.
References assert(), and NULL.
Referenced by SCIPsetConflicthdlrCopy().
void SCIPconflicthdlrSetFree | ( | SCIP_CONFLICTHDLR * | conflicthdlr | ) |
set destructor of conflict handler
conflicthdlr | conflict handler destructor of conflict handler |
Definition at line 1437 of file conflict_graphanalysis.c.
References assert(), and NULL.
Referenced by SCIPsetConflicthdlrFree().
void SCIPconflicthdlrSetInit | ( | SCIP_CONFLICTHDLR * | conflicthdlr | ) |
set initialization method of conflict handler
conflicthdlr | conflict handler initialization method conflict handler |
Definition at line 1449 of file conflict_graphanalysis.c.
References assert(), and NULL.
Referenced by SCIPsetConflicthdlrInit().
void SCIPconflicthdlrSetExit | ( | SCIP_CONFLICTHDLR * | conflicthdlr | ) |
set deinitialization method of conflict handler
conflicthdlr | conflict handler deinitialization method conflict handler |
Definition at line 1460 of file conflict_graphanalysis.c.
References assert(), and NULL.
Referenced by SCIPsetConflicthdlrExit().
void SCIPconflicthdlrSetInitsol | ( | SCIP_CONFLICTHDLR * | conflicthdlr | ) |
set solving process initialization method of conflict handler
conflicthdlr | conflict handler solving process initialization method of conflict handler |
Definition at line 1471 of file conflict_graphanalysis.c.
References assert(), and NULL.
Referenced by SCIPsetConflicthdlrInitsol().
void SCIPconflicthdlrSetExitsol | ( | SCIP_CONFLICTHDLR * | conflicthdlr | ) |
set solving process deinitialization method of conflict handler
conflicthdlr | conflict handler solving process deinitialization method of conflict handler |
Definition at line 1482 of file conflict_graphanalysis.c.
References assert(), and NULL.
Referenced by SCIPsetConflicthdlrExitsol().
void SCIPconflicthdlrSetPriority | ( | SCIP_CONFLICTHDLR * | conflicthdlr, |
SCIP_SET * | set, | ||
int | priority ) |
sets priority of conflict handler
conflicthdlr | conflict handler |
set | global SCIP settings |
priority | new priority of the conflict handler |
Definition at line 1523 of file conflict_graphanalysis.c.
References assert(), FALSE, NULL, and SCIP_Conflicthdlr::priority.
Referenced by SCIPsetConflicthdlrPriority().
void SCIPconflicthdlrEnableOrDisableClocks | ( | SCIP_CONFLICTHDLR * | conflicthdlr, |
SCIP_Bool | enable ) |
enables or disables all clocks of conflicthdlr
, depending on the value of the flag
conflicthdlr | the conflict handler for which all clocks should be enabled or disabled |
enable | should the clocks of the conflict handler be enabled? |
Definition at line 1547 of file conflict_graphanalysis.c.
References assert(), SCIP_Conflicthdlr::conflicttime, NULL, SCIP_Bool, SCIPclockEnableOrDisable(), and SCIP_Conflicthdlr::setuptime.
return TRUE if conflict analysis is applicable; In case the function return FALSE there is no need to initialize the conflict analysis since it will not be applied
set | global SCIP settings |
Definition at line 1581 of file conflict_graphanalysis.c.
References FALSE, SCIP_Bool, and TRUE.
Referenced by SCIPconflictAnalyze(), and SCIPisConflictAnalysisApplicable().
|
static |
resizes the array of the temporary bound change informations to be able to store at least num bound change entries
conflict | conflict analysis data |
set | global SCIP settings |
num | minimal number of slots in arrays |
Definition at line 1598 of file conflict_graphanalysis.c.
References assert(), BMSreallocMemoryArray, NULL, SCIP_ALLOC, SCIP_OKAY, SCIPsetCalcMemGrowSize(), SCIP_Conflict::tmpbdchginfos, and SCIP_Conflict::tmpbdchginfossize.
Referenced by conflictCreateTmpBdchginfo().
SCIP_RETCODE conflictCreateTmpBdchginfo | ( | SCIP_CONFLICT * | conflict, |
BMS_BLKMEM * | blkmem, | ||
SCIP_SET * | set, | ||
SCIP_VAR * | var, | ||
SCIP_BOUNDTYPE | boundtype, | ||
SCIP_Real | oldbound, | ||
SCIP_Real | newbound, | ||
SCIP_BDCHGINFO ** | bdchginfo ) |
creates a temporary bound change information object that is destroyed after the conflict sets are flushed
conflict | conflict analysis data |
blkmem | block memory |
set | global SCIP settings |
var | active variable that changed the bounds |
boundtype | type of bound for var: lower or upper bound |
oldbound | old value for bound |
newbound | new value for bound |
bdchginfo | pointer to store bound change information |
Definition at line 1621 of file conflict_graphanalysis.c.
References assert(), conflictEnsureTmpbdchginfosMem(), SCIP_Conflict::ntmpbdchginfos, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbdchginfoCreate(), SCIP_Conflict::tmpbdchginfos, and var.
Referenced by conflictCreateReconvergenceConss(), and SCIPconflictAnalyzeRemainingBdchgs().
|
static |
frees all temporarily created bound change information data
conflict | conflict analysis data |
blkmem | block memory |
Definition at line 1645 of file conflict_graphanalysis.c.
References assert(), i, SCIP_Conflict::ntmpbdchginfos, NULL, SCIPbdchginfoFree(), and SCIP_Conflict::tmpbdchginfos.
Referenced by SCIPconflictFlushConss().
|
static |
increases the conflict score of the variable in the given direction
var | problem variable |
blkmem | block memory |
set | global SCIP settings |
stat | dynamic problem statistics |
boundtype | type of bound for which the score should be increased |
value | value of the bound |
weight | weight of this VSIDS updates |
Definition at line 1661 of file conflict_graphanalysis.c.
References assert(), SCIP_Stat::glbhistory, SCIP_Stat::glbhistorycrun, NULL, SCIP_BOUNDTYPE_LOWER, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_UPWARDS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPhistoryIncVSIDS(), SCIPsetIsZero(), SCIPvarIncVSIDS(), var, and SCIP_Stat::vsidsweight.
Referenced by conflictAddBound(), SCIPconflictAnalyzeRemainingBdchgs(), and updateStatistics().
|
static |
update conflict statistics
conflict | conflict analysis data |
blkmem | block memory |
set | global SCIP settings |
stat | dynamic problem statistics |
conflictset | conflict set to add to the tree |
insertdepth | depth level at which the conflict set should be added |
Definition at line 1692 of file conflict_graphanalysis.c.
References assert(), SCIP_ConflictSet::bdchginfos, bound, SCIP_Stat::glbhistory, SCIP_Stat::glbhistorycrun, i, incVSIDS(), SCIP_Conflict::nappliedglbconss, SCIP_Conflict::nappliedglbliterals, SCIP_Conflict::nappliedlocconss, SCIP_Conflict::nappliedlocliterals, SCIP_ConflictSet::nbdchginfos, NULL, SCIP_ConflictSet::relaxedbds, SCIP_BOUNDTYPE_LOWER, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_UPWARDS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbdchginfoGetBoundtype(), SCIPhistoryIncNActiveConflicts(), SCIPvarIncNActiveConflicts(), SCIP_BdChgInfo::var, and var.
Referenced by conflictAddConflictCons().
|
static |
adds the given conflict set as conflict constraint to the problem
conflict | conflict analysis data |
blkmem | block memory |
set | global SCIP settings |
stat | dynamic problem statistics |
transprob | transformed problem after presolve |
origprob | original problem |
tree | branch and bound tree |
reopt | reoptimization data structure |
lp | current LP data |
branchcand | branching candidate storage |
eventqueue | event queue |
cliquetable | clique table data structure |
conflictset | conflict set to add to the tree |
insertdepth | depth level at which the conflict set should be added |
success | pointer to store whether the addition was successful |
Definition at line 1743 of file conflict_graphanalysis.c.
References assert(), SCIP_ConflictSet::bdchginfos, bound, SCIP_BdChgInfo::boundtype, SCIP_ConflictSet::conflictdepth, SCIP_ConflictSet::conflicttype, detectImpliedBounds(), SCIP_Conflict::dIBclock, SCIP_Lp::diving, FALSE, h, SCIP_ConflictSet::hasrelaxonlyvar, SCIP_ConflictSet::nbdchginfos, NULL, SCIP_Tree::path, SCIP_ConflictSet::relaxedbds, result, SCIP_Tree::root, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_CONFTYPE_UNKNOWN, SCIP_CONSADDED, SCIP_OKAY, SCIP_Real, SCIPboundtypeOpposite(), SCIPclockStart(), SCIPclockStop(), SCIPconflicthdlrExec(), SCIPconflicthdlrGetName(), SCIPconflicthdlrGetPriority(), SCIPdebugCheckConflict, SCIPnodeAddBoundchg(), SCIPsetDebugMsg, SCIPsetIsIntegral(), SCIPsetSortConflicthdlrs(), SCIPtreeGetCurrentDepth(), SCIPtreeGetFocusDepth(), SCIPvarGetName(), SCIPvarIsIntegral(), SCIP_Lp::strongbranching, TRUE, updateStatistics(), SCIP_ConflictSet::usescutoffbound, SCIP_ConflictSet::validdepth, SCIP_BdChgInfo::var, and var.
Referenced by SCIPconflictFlushConss().
calculates the maximal size of conflict sets to be used
set | global SCIP settings |
prob | problem data |
Definition at line 1896 of file conflict_graphanalysis.c.
References assert(), MAX, SCIP_Prob::ncontvars, NULL, and SCIP_Prob::nvars.
Referenced by SCIPconflictAnalyze(), SCIPconflictAnalyzeRemainingBdchgs(), and SCIPconflictFlushConss().
SCIP_RETCODE SCIPconflictFlushConss | ( | SCIP_CONFLICT * | conflict, |
BMS_BLKMEM * | blkmem, | ||
SCIP_SET * | set, | ||
SCIP_STAT * | stat, | ||
SCIP_PROB * | transprob, | ||
SCIP_PROB * | origprob, | ||
SCIP_TREE * | tree, | ||
SCIP_REOPT * | reopt, | ||
SCIP_LP * | lp, | ||
SCIP_BRANCHCAND * | branchcand, | ||
SCIP_EVENTQUEUE * | eventqueue, | ||
SCIP_CLIQUETABLE * | cliquetable ) |
adds the collected conflict constraints to the corresponding nodes; the best set->conf_maxconss conflict constraints are added to the node of their validdepth; additionally (if not yet added, and if repropagation is activated), the conflict constraint that triggers the earliest repropagation is added to the node of its validdepth
conflict | conflict analysis data |
blkmem | block memory of transformed problem |
set | global SCIP settings |
stat | dynamic problem statistics |
transprob | transformed problem |
origprob | original problem |
tree | branch and bound tree |
reopt | reoptimization data structure |
lp | current LP data |
branchcand | branching candidate storage |
eventqueue | event queue |
cliquetable | clique table data structure |
Definition at line 1916 of file conflict_graphanalysis.c.
References assert(), conflictAddConflictCons(), conflictCalcMaxsize(), SCIP_ConflictSet::conflictdepth, conflictFreeTmpBdchginfos(), SCIP_Conflict::conflictsets, SCIP_Node::depth, i, SCIP_ConflictSet::insertdepth, SCIP_ConflictSet::nbdchginfos, SCIP_Conflict::nconflictsets, NULL, SCIP_Tree::path, SCIP_Tree::pathlen, SCIP_ConflictSet::repropagate, SCIP_ConflictSet::repropdepth, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconflictsetFree(), SCIPdebug, SCIPnodeCutoff(), SCIPnodePropagateAgain(), SCIPsetDebugMsg, SCIPtreeGetCurrentDepth(), SCIPtreeGetFocusDepth(), SCIPvisualFoundConflict(), SCIP_ConflictSet::validdepth, and SCIP_Stat::visual.
Referenced by conflictAnalyzeLP(), SCIPconflictAnalyzePseudo(), SCIPpropagateDomains(), and solveNode().
|
static |
resizes conflictsets array to be able to store at least num entries
conflict | conflict analysis data |
set | global SCIP settings |
num | minimal number of slots in array |
Definition at line 2126 of file conflict_graphanalysis.c.
References assert(), BMSreallocMemoryArray, SCIP_Conflict::conflictsets, SCIP_Conflict::conflictsetscores, SCIP_Conflict::conflictsetssize, NULL, SCIP_ALLOC, SCIP_OKAY, and SCIPsetCalcMemGrowSize().
Referenced by conflictInsertConflictset().
|
static |
inserts conflict set into sorted conflictsets array and deletes the conflict set pointer
conflict | conflict analysis data |
blkmem | block memory of transformed problem |
set | global SCIP settings |
conflictset | pointer to conflict set to insert |
Definition at line 2151 of file conflict_graphanalysis.c.
References assert(), conflictEnsureConflictsetsMem(), conflictsetCalcConflictDepth(), conflictsetCalcScore(), conflictsetIsRedundant(), SCIP_Conflict::conflictsets, SCIP_Conflict::conflictsetscores, i, MIN, SCIP_Conflict::nconflictsets, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconflictsetFree(), SCIPdebug, and SCIPsetDebugMsg.
Referenced by conflictAddConflictset().
|
static |
marks bound to be present in the current conflict and returns whether a bound which is at least as tight was already member of the current conflict (i.e., the given bound change does not need to be added)
conflict | conflict analysis data |
set | global SCIP settings |
bdchginfo | bound change to add to the conflict set |
relaxedbd | relaxed bound |
Definition at line 2247 of file conflict_graphanalysis.c.
References assert(), SCIP_Conflict::count, FALSE, MAX, MIN, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_Real, SCIPABORT, SCIPbdchginfoGetBoundtype(), SCIPbdchginfoGetNewbound(), SCIPbdchginfoGetVar(), SCIPerrorMessage, SCIPsetDebugMsg, SCIPvarGetName(), TRUE, and var.
Referenced by conflictAddConflictBound(), and conflictQueueBound().
|
static |
puts bound change into the current conflict set
conflict | conflict analysis data |
blkmem | block memory of transformed problem |
set | global SCIP settings |
bdchginfo | bound change to add to the conflict set |
relaxedbd | relaxed bound |
Definition at line 2336 of file conflict_graphanalysis.c.
References assert(), conflictMarkBoundCheckPresence(), SCIP_Conflict::conflictset, conflictsetAddBound(), NULL, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbdchginfoGetBoundtype(), SCIPbdchginfoGetDepth(), SCIPbdchginfoGetNewbound(), SCIPbdchginfoGetVar(), SCIPbdchginfoIsRedundant(), SCIPsetDebugMsg, SCIPsetIsGE(), SCIPsetIsLE(), and SCIPvarGetName().
Referenced by conflictAnalyze(), conflictCreateReconvergenceConss(), and SCIPconflictAnalyzeRemainingBdchgs().
|
static |
returns whether the negation of the given bound change would lead to a globally valid literal
set | global SCIP settings |
bdchginfo | bound change information |
Definition at line 2379 of file conflict_graphanalysis.c.
References bound, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPbdchginfoGetBoundtype(), SCIPbdchginfoGetNewbound(), SCIPbdchginfoGetVar(), SCIPsetIsFeasGE(), SCIPsetIsFeasLE(), SCIPvarGetLbGlobal(), SCIPvarGetType(), SCIPvarGetUbGlobal(), and var.
Referenced by conflictQueueBound().
|
static |
adds given bound change information to the conflict candidate queue
conflict | conflict analysis data |
set | global SCIP settings |
bdchginfo | bound change information |
relaxedbd | relaxed bound |
Definition at line 2399 of file conflict_graphanalysis.c.
References assert(), SCIP_Conflict::bdchgqueue, conflictMarkBoundCheckPresence(), SCIP_Conflict::forcedbdchgqueue, isBoundchgUseless(), NULL, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbdchginfoGetBoundtype(), SCIPbdchginfoGetNewbound(), SCIPbdchginfoGetVar(), SCIPbdchginfoIsRedundant(), SCIPpqueueInsert(), SCIPsetIsGE(), SCIPsetIsLE(), and SCIPvarIsBinary().
Referenced by conflictAddBound(), and conflictCreateReconvergenceConss().
|
static |
adds variable's bound to conflict candidate queue
conflict | conflict analysis data |
blkmem | block memory |
set | global SCIP settings |
stat | dynamic problem statistics |
var | problem variable |
boundtype | type of bound that was changed: lower or upper bound |
bdchginfo | bound change info, or NULL |
relaxedbd | relaxed bound |
Definition at line 2445 of file conflict_graphanalysis.c.
References assert(), conflictQueueBound(), incVSIDS(), NULL, SCIP_BOUNDCHGTYPE_BRANCHING, SCIP_BOUNDCHGTYPE_CONSINFER, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbdchginfoGetBoundtype(), SCIPbdchginfoGetChgtype(), SCIPbdchginfoGetDepth(), SCIPbdchginfoGetInferCons(), SCIPbdchginfoGetInferInfo(), SCIPbdchginfoGetInferProp(), SCIPbdchginfoGetNewbound(), SCIPbdchginfoGetOldbound(), SCIPbdchginfoGetPos(), SCIPbdchginfoGetVar(), SCIPbdchginfoIsRedundant(), SCIPconsGetName(), SCIPpropGetName(), SCIPsetDebugMsg, SCIPsetIsGE(), SCIPsetIsGT(), SCIPsetIsLE(), SCIPsetIsLT(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarIsActive(), and var.
Referenced by SCIPconflictAddBound(), SCIPconflictAddRelaxedBound(), and SCIPconflictAnalyzeRemainingBdchgs().
SCIP_RETCODE SCIPconflictAnalyzeRemainingBdchgs | ( | SCIP_CONFLICT * | conflict, |
BMS_BLKMEM * | blkmem, | ||
SCIP_SET * | set, | ||
SCIP_STAT * | stat, | ||
SCIP_PROB * | prob, | ||
SCIP_TREE * | tree, | ||
SCIP_Bool | diving, | ||
int * | lbchginfoposs, | ||
int * | ubchginfoposs, | ||
int * | nconss, | ||
int * | nliterals, | ||
int * | nreconvconss, | ||
int * | nreconvliterals ) |
applies conflict analysis starting with given bound changes, that could not be undone during previous infeasibility analysis
conflict | conflict analysis data |
blkmem | block memory of transformed problem |
set | global SCIP settings |
stat | problem statistics |
prob | problem data |
tree | branch and bound tree |
diving | are we in strong branching or diving mode? |
lbchginfoposs | positions of currently active lower bound change information in variables' arrays |
ubchginfoposs | positions of currently active upper bound change information in variables' arrays |
nconss | pointer to store the number of generated conflict constraints |
nliterals | pointer to store the number of literals in generated conflict constraints |
nreconvconss | pointer to store the number of generated reconvergence constraints |
nreconvliterals | pointer to store the number of literals generated reconvergence constraints |
Definition at line 2503 of file conflict_graphanalysis.c.
References assert(), conflictAddBound(), conflictAddConflictBound(), conflictAnalyze(), conflictCalcMaxsize(), conflictCreateTmpBdchginfo(), SCIP_Conflict::conflictset, SCIP_ConflictSet::conflicttype, FALSE, incVSIDS(), NULL, nvars, SCIP_Prob::nvars, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbdchginfoGetBoundtype(), SCIPbdchginfoGetNewbound(), SCIPbdchginfoIsRedundant(), SCIPconflictInit(), SCIPsetDebugMsg, SCIPvarGetLbLocal(), SCIPvarGetLbLP(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarGetUbLocal(), SCIPvarGetUbLP(), SCIP_ConflictSet::usescutoffbound, var, SCIP_Prob::vars, and vars.
Referenced by conflictAnalyzeLP(), and SCIPconflictAnalyzePseudo().
|
static |
check if the bound change info (which is the potential next candidate which is queued) is valid for the current conflict analysis; a bound change info can get invalid if after this one was added to the queue, a weaker bound change was added to the queue (due the bound widening idea) which immediately makes this bound change redundant; due to the priority we did not removed that bound change info since that cost O(log(n)); hence we have to skip/ignore it now
The following situations can occur before for example the bound change info (x >= 3) is potentially popped from the queue.
Postcondition: the reason why (x >= 3) was queued is that at this time point no lower bound of x was involved yet in the current conflict or the lower bound which was involved until then was stronger, e.g., (x >= 2).
1) during the time until (x >= 3) gets potentially popped no weaker lower bound was added to the queue, in that case the conflictlbcount is valid and conflictlb is 3; that is (var->conflictlbcount == conflict->count && var->conflictlb == 3)
2) a weaker bound change info gets queued (e.g., x >= 4); this bound change is popped before (x >= 3) since it has higher priority (which is the time stamp of the bound change info and (x >= 4) has to be done after (x >= 3) during propagation or branching)
a) if (x >= 4) is popped and added to the conflict set the conflictlbcount is still valid and conflictlb is at most 4; that is (var->conflictlbcount == conflict->count && var->conflictlb >= 4); it follows that any bound change info which is stronger than (x >= 4) gets ignored (for example x >= 2)
b) if (x >= 4) is popped and resolved without introducing a new lower bound on x until (x >= 3) is a potentially candidate the conflictlbcount indicates that bound change is currently not present; that is (var->conflictlbcount != conflict->count)
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 pooped, the conflictlbcount indicates that bound change is currently present; that is (var->conflictlbcount == conflict->count); however the (x >= 3) only has be explained if conflictlb matches that one; that is (var->conflictlb == bdchginfo->newbound); otherwise it redundant/invalid.
conflict | conflict analysis data |
bdchginfo | bound change information |
Definition at line 2674 of file conflict_graphanalysis.c.
References assert(), SCIP_Conflict::count, FALSE, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIPbdchginfoGetBoundtype(), SCIPbdchginfoGetNewbound(), SCIPbdchginfoGetVar(), SCIPvarIsBinary(), TRUE, and var.
Referenced by conflictFirstCand(), conflictRemoveCand(), conflictResolveBound(), and conflictsetAddBounds().
|
static |
adds given bound changes to a conflict set
conflict | conflict analysis data |
conflictset | conflict set |
blkmem | block memory of transformed problem |
set | global SCIP settings |
bdchginfos | bound changes to add to the conflict set |
nbdchginfos | number of bound changes to add |
Definition at line 2717 of file conflict_graphanalysis.c.
References assert(), bdchginfoIsInvalid(), SCIP_ConflictSet::bdchginfos, conflictsetAddBound(), conflictsetEnsureBdchginfosMem(), FALSE, SCIP_ConflictSet::hasrelaxonlyvar, i, MAX, MIN, SCIP_ConflictSet::nbdchginfos, NULL, SCIP_ConflictSet::relaxedbds, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbdchginfoGetBoundtype(), SCIPbdchginfoGetDepth(), SCIPbdchginfoGetNewbound(), SCIPbdchginfoGetRelaxedBound(), SCIPbdchginfoGetVar(), SCIPbdchginfoIsTighter(), SCIPsetDebugMsg, SCIPsortIntPtrReal(), SCIPvarGetIndex(), SCIPvarGetName(), SCIPvarIsRelaxationOnly(), SCIP_ConflictSet::sortvals, and TRUE.
Referenced by conflictAddConflictset().
|
static |
removes and returns next conflict analysis candidate from the candidate queue
conflict | conflict analysis data |
Definition at line 2886 of file conflict_graphanalysis.c.
References assert(), bdchginfoIsInvalid(), SCIP_Conflict::bdchgqueue, SCIP_Conflict::forcedbdchgqueue, NULL, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_REAL_MAX, SCIP_REAL_MIN, SCIPbdchginfoGetBoundtype(), SCIPbdchginfoGetVar(), SCIPbdchginfoIsRedundant(), SCIPpqueueNElems(), SCIPpqueueRemove(), and var.
Referenced by conflictAnalyze(), and conflictCreateReconvergenceConss().
|
static |
returns next conflict analysis candidate from the candidate queue without removing it
conflict | conflict analysis data |
Definition at line 2930 of file conflict_graphanalysis.c.
References assert(), bdchginfoIsInvalid(), SCIP_Conflict::bdchgqueue, conflictFirstCand(), SCIP_Conflict::forcedbdchgqueue, NULL, SCIP_BOUNDTYPE_LOWER, SCIPbdchginfoGetBoundtype(), SCIPbdchginfoGetDepth(), SCIPbdchginfoGetNewbound(), SCIPbdchginfoGetVar(), SCIPbdchginfoIsRedundant(), SCIPdebugMessage, SCIPpqueueFirst(), SCIPpqueueNElems(), SCIPpqueueRemove(), and SCIPvarGetName().
Referenced by conflictAnalyze(), conflictCreateReconvergenceConss(), and conflictFirstCand().
|
static |
adds the current conflict set (extended by all remaining bound changes in the queue) to the pool of conflict sets
conflict | conflict analysis data |
blkmem | block memory of transformed problem |
set | global SCIP settings |
stat | dynamic problem statistics |
tree | branch and bound tree |
validdepth | minimal depth level at which the conflict set is valid |
diving | are we in strong branching or diving mode? |
repropagate | should the constraint trigger a repropagation? |
success | pointer to store whether the conflict set is valid |
nliterals | pointer to store the number of literals in the generated conflictset |
Definition at line 2984 of file conflict_graphanalysis.c.
References assert(), SCIP_ConflictSet::bdchginfos, SCIP_Conflict::bdchgqueue, conflictInsertConflictset(), SCIP_Conflict::conflictset, conflictsetAddBounds(), conflictsetCalcInsertDepth(), conflictsetCopy(), FALSE, SCIP_Conflict::forcedbdchgqueue, SCIP_ConflictSet::insertdepth, MAX, SCIP_ConflictSet::nbdchginfos, NULL, SCIP_Tree::path, SCIP_Tree::pathlen, SCIP_ConflictSet::relaxedbds, SCIP_ConflictSet::repropagate, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconflictsetFree(), SCIPdebugCheckConflict, SCIPpqueueElems(), SCIPpqueueNElems(), SCIPsetDebugMsg, SCIPtreeGetCurrentDepth(), SCIPtreeGetFocusDepth(), TRUE, and SCIP_ConflictSet::validdepth.
Referenced by conflictAnalyze(), and conflictCreateReconvergenceConss().
|
static |
tries to resolve given bound change
conflict | conflict analysis data |
set | global SCIP settings |
bdchginfo | bound change to resolve |
relaxedbd | the relaxed bound |
validdepth | minimal depth level at which the conflict is valid |
resolved | pointer to store whether the bound change was resolved |
Definition at line 3083 of file conflict_graphanalysis.c.
References assert(), bdchginfoIsInvalid(), SCIP_ConflictSet::bdchginfos, SCIP_Conflict::bdchgqueue, SCIP_Conflict::conflictset, FALSE, SCIP_Conflict::forcedbdchgqueue, i, SCIP_ConflictSet::nbdchginfos, NULL, SCIP_ConflictSet::relaxedbds, result, SCIP_Bool, SCIP_BOUNDCHGTYPE_BRANCHING, SCIP_BOUNDCHGTYPE_CONSINFER, SCIP_BOUNDCHGTYPE_PROPINFER, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIP_VARSTATUS_AGGREGATED, SCIP_VARSTATUS_MULTAGGR, SCIP_VARSTATUS_NEGATED, SCIPbdchginfoGetBoundtype(), SCIPbdchginfoGetChgtype(), SCIPbdchginfoGetDepth(), SCIPbdchginfoGetIdx(), SCIPbdchginfoGetInferBoundtype(), SCIPbdchginfoGetInferCons(), SCIPbdchginfoGetInferInfo(), SCIPbdchginfoGetInferProp(), SCIPbdchginfoGetInferVar(), SCIPbdchginfoGetNewbound(), SCIPbdchginfoGetPos(), SCIPbdchginfoGetRelaxedBound(), SCIPbdchginfoGetVar(), SCIPbdchginfoIsRedundant(), SCIPconsGetName(), SCIPconsGetValidDepth(), SCIPconsIsGlobal(), SCIPconsResolvePropagation(), SCIPerrorMessage, SCIPgetVarBdAtIndex(), SCIPpqueueElems(), SCIPpqueueNElems(), SCIPpropGetName(), SCIPpropResolvePropagation(), SCIPsetDebugMsg, SCIPsetDebugMsgPrint, SCIPvarGetMultaggrNVars(), SCIPvarGetName(), SCIPvarGetProbvarSum(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarIsActive(), TRUE, and var.
Referenced by conflictAnalyze(), and conflictCreateReconvergenceConss().
|
static |
clears the conflict queue and the current conflict set
conflict | conflict analysis data |
Definition at line 3293 of file conflict_graphanalysis.c.
References assert(), SCIP_Conflict::bdchgqueue, SCIP_Conflict::conflictset, conflictsetClear(), SCIP_Conflict::forcedbdchgqueue, NULL, and SCIPpqueueClear().
Referenced by conflictAnalyze(), conflictCreateReconvergenceConss(), and SCIPconflictInit().
SCIP_RETCODE SCIPconflictInit | ( | SCIP_CONFLICT * | conflict, |
SCIP_SET * | set, | ||
SCIP_STAT * | stat, | ||
SCIP_PROB * | prob, | ||
SCIP_CONFTYPE | conftype, | ||
SCIP_Bool | usescutoffbound ) |
initializes the propagation conflict analysis by clearing the conflict candidate queue
conflict | conflict analysis data |
set | global SCIP settings |
stat | problem statistics |
prob | problem data |
conftype | type of the conflict |
usescutoffbound | depends the conflict on a cutoff bound? |
Definition at line 3305 of file conflict_graphanalysis.c.
References assert(), conflictClear(), SCIP_Conflict::conflictset, SCIP_ConflictSet::conflicttype, SCIP_Conflict::count, SCIP_Stat::glbhistory, SCIP_Stat::glbhistorycrun, SCIP_Stat::lastconflictnode, SCIP_Stat::nnodes, NULL, SCIP_Prob::nvars, SCIP_Bool, SCIP_CALL, SCIP_CONFTYPE_BNDEXCEEDING, SCIP_CONFTYPE_INFEASLP, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIPhistoryScaleVSIDS(), SCIPsetDebugMsg, SCIPvarScaleVSIDS(), SCIP_ConflictSet::usescutoffbound, SCIP_Prob::vars, and SCIP_Stat::vsidsweight.
Referenced by conflictCreateReconvergenceConss(), SCIPconflictAnalyzeRemainingBdchgs(), and SCIPinitConflictAnalysis().
|
static |
convert variable and bound change to active variable
var | pointer to variable |
set | global SCIP settings |
boundtype | pointer to type of bound that was changed: lower or upper bound |
bound | pointer to bound to convert, or NULL |
Definition at line 3372 of file conflict_graphanalysis.c.
References assert(), bound, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_FIXED, SCIPboundtypeOpposite(), SCIPvarGetProbvarSum(), SCIPvarGetStatus(), and var.
Referenced by SCIPconflictAddBound(), SCIPconflictAddRelaxedBound(), and SCIPconflictIsVarUsed().
|
static |
returns whether bound change has a valid reason that can be resolved in conflict analysis
bdchginfo | bound change information |
Definition at line 3407 of file conflict_graphanalysis.c.
References assert(), NULL, SCIP_Bool, SCIP_BOUNDCHGTYPE_CONSINFER, SCIP_BOUNDCHGTYPE_PROPINFER, SCIPbdchginfoGetChgtype(), SCIPbdchginfoGetInferProp(), and SCIPbdchginfoIsRedundant().
Referenced by addCand(), and conflictCreateReconvergenceConss().
|
static |
if only one conflicting bound change of the last depth level was used, and if this can be resolved, creates GRASP-like reconvergence conflict constraints in the conflict graph up to the branching variable of this depth level
conflict | conflict analysis data |
blkmem | block memory of transformed problem |
set | global SCIP settings |
stat | problem statistics |
prob | problem data |
tree | branch and bound tree |
diving | are we in strong branching or diving mode? |
validdepth | minimal depth level at which the initial conflict set is valid |
firstuip | first UIP of conflict graph |
nreconvconss | pointer to store the number of generated reconvergence constraints |
nreconvliterals | pointer to store the number of literals generated reconvergence constraints |
Definition at line 3425 of file conflict_graphanalysis.c.
References assert(), bdchginfoIsResolvable(), SCIP_ConflictSet::bdchginfos, SCIP_Conflict::bdchgqueue, conflictAddConflictBound(), conflictAddConflictset(), conflictClear(), conflictCreateTmpBdchginfo(), conflictFirstCand(), conflictQueueBound(), conflictRemoveCand(), conflictResolveBound(), SCIP_Conflict::conflictset, SCIP_ConflictSet::conflicttype, FALSE, SCIP_Conflict::forcedbdchgqueue, MIN, SCIP_ConflictSet::nbdchginfos, NULL, SCIP_Tree::path, SCIP_Tree::pathlen, SCIP_ConflictSet::relaxedbds, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIP_REAL_MIN, SCIPbdchginfoGetBoundtype(), SCIPbdchginfoGetDepth(), SCIPbdchginfoGetNewbound(), SCIPbdchginfoGetPos(), SCIPbdchginfoGetRelaxedBound(), SCIPbdchginfoGetVar(), SCIPbdchginfoIsRedundant(), SCIPboundtypeOpposite(), SCIPconflictInit(), SCIPdebugCheckConflictFrontier, SCIPpqueueNElems(), SCIPsetDebugMsg, SCIPsetIsIntegral(), SCIPtreeGetCurrentDepth(), SCIPtreeGetFocusDepth(), SCIPvarGetName(), SCIPvarIsActive(), SCIPvarIsIntegral(), and SCIP_ConflictSet::usescutoffbound.
Referenced by conflictAnalyze().
SCIP_RETCODE conflictAnalyze | ( | SCIP_CONFLICT * | conflict, |
BMS_BLKMEM * | blkmem, | ||
SCIP_SET * | set, | ||
SCIP_STAT * | stat, | ||
SCIP_PROB * | prob, | ||
SCIP_TREE * | tree, | ||
SCIP_Bool | diving, | ||
int | validdepth, | ||
SCIP_Bool | mustresolve, | ||
int * | nconss, | ||
int * | nliterals, | ||
int * | nreconvconss, | ||
int * | nreconvliterals ) |
analyzes conflicting bound changes that were added with calls to SCIPconflictAddBound() and SCIPconflictAddRelaxedBound(), and on success, calls the conflict handlers to create a conflict constraint out of the resulting conflict set; afterwards the conflict queue and the conflict set is cleared
conflict | conflict analysis data |
blkmem | block memory of transformed problem |
set | global SCIP settings |
stat | problem statistics |
prob | problem data |
tree | branch and bound tree |
diving | are we in strong branching or diving mode? |
validdepth | minimal depth level at which the initial conflict set is valid |
mustresolve | should the conflict set only be used, if a resolution was applied? |
nconss | pointer to store the number of generated conflict constraints |
nliterals | pointer to store the number of literals in generated conflict constraints |
nreconvconss | pointer to store the number of generated reconvergence constraints |
nreconvliterals | pointer to store the number of literals generated reconvergence constraints |
Definition at line 3661 of file conflict_graphanalysis.c.
References assert(), SCIP_ConflictSet::bdchginfos, SCIP_Conflict::bdchgqueue, SCIP_DomChgBound::boundchgs, conflictAddConflictBound(), conflictAddConflictset(), conflictClear(), conflictCreateReconvergenceConss(), conflictFirstCand(), conflictRemoveCand(), conflictResolveBound(), SCIP_Conflict::conflictset, SCIP_ConflictSet::conflicttype, SCIP_Node::domchg, SCIP_DomChg::domchgbound, FALSE, SCIP_Conflict::forcedbdchgqueue, i, MIN, SCIP_ConflictSet::nbdchginfos, SCIP_DomChgBound::nboundchgs, NULL, SCIP_Tree::path, SCIP_Tree::pathlen, SCIP_ConflictSet::relaxedbds, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbdchginfoGetBoundtype(), SCIPbdchginfoGetDepth(), SCIPbdchginfoGetNewbound(), SCIPbdchginfoGetPos(), SCIPbdchginfoGetRelaxedBound(), SCIPbdchginfoGetVar(), SCIPbdchginfoHasInferenceReason(), SCIPbdchginfoIsRedundant(), SCIPdebugCheckConflictFrontier, SCIPpqueueNElems(), SCIPsetAllocBufferArray, SCIPsetDebugMsg, SCIPsetFreeBufferArray, SCIPtreeGetCurrentDepth(), SCIPtreeGetFocusDepth(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarIsActive(), TRUE, and var.
Referenced by SCIPconflictAnalyze(), and SCIPconflictAnalyzeRemainingBdchgs().
|
static |
calculates the score of a bound change within a conflict
prooflhs | lhs of proof constraint |
proofact | activity of the proof constraint |
proofactdelta | activity change |
proofcoef | coefficient in proof constraint |
depth | bound change depth |
currentdepth | current depth |
var | variable corresponding to bound change |
set | global SCIP settings |
Definition at line 3946 of file conflict_graphanalysis.c.
References depth, MAX, NULL, SCIP_LOCKTYPE_MODEL, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPcolGetNNonz(), SCIPvarGetCol(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetStatus(), and var.
Referenced by addCand().
|
static |
ensures, that candidate array can store at least num entries
set | global SCIP settings |
cands | pointer to candidate array |
candscores | pointer to candidate score array |
newbounds | pointer to candidate new bounds array |
proofactdeltas | pointer to candidate proof delta array |
candssize | pointer to size of array |
num | minimal number of candidates to store in array |
Definition at line 3991 of file conflict_graphanalysis.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPsetCalcMemGrowSize(), and SCIPsetReallocBufferArray.
Referenced by addCand().
|
static |
after changing the global bound of a variable, the bdchginfos that are now redundant are replaced with oldbound = newbound = global bound; if the current bdchginfo is of such kind, the bound is equal to the global bound and we can ignore it by installing a -1 as the corresponding bound change info position
var | problem variable |
lbchginfopos | pointer to lower bound change information position |
ubchginfopos | pointer to upper bound change information position |
Definition at line 4025 of file conflict_graphanalysis.c.
References assert(), NULL, SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and var.
Referenced by SCIPundoBdchgsProof().
SCIP_RETCODE SCIPconflictAddBound | ( | SCIP_CONFLICT * | conflict, |
BMS_BLKMEM * | blkmem, | ||
SCIP_SET * | set, | ||
SCIP_STAT * | stat, | ||
SCIP_VAR * | var, | ||
SCIP_BOUNDTYPE | boundtype, | ||
SCIP_BDCHGIDX * | bdchgidx ) |
adds variable's bound to conflict candidate queue
conflict | conflict analysis data |
blkmem | block memory |
set | global SCIP settings |
stat | dynamic problem statistics |
var | problem variable |
boundtype | type of bound that was changed: lower or upper bound |
bdchgidx | bound change index (time stamp of bound change), or NULL for current time |
Definition at line 4056 of file conflict_graphanalysis.c.
References assert(), conflictAddBound(), convertToActiveVar(), FALSE, i, NULL, nvars, scalars, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_MULTAGGR, SCIPbdchgidxIsEarlier(), SCIPbdchginfoGetIdx(), SCIPbdchginfoGetNewbound(), SCIPboundtypeOpposite(), SCIPconflictAddBound(), SCIPvarGetBdchgInfo(), SCIPvarGetMultaggrNVars(), SCIPvarGetMultaggrScalars(), SCIPvarGetMultaggrVars(), SCIPvarGetStatus(), SCIPvarIsActive(), var, and vars.
Referenced by SCIPaddConflictBd(), SCIPaddConflictBinvar(), SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPconflictAddBound(), and SCIPconflictAddRelaxedBound().
SCIP_RETCODE SCIPconflictAddRelaxedBound | ( | SCIP_CONFLICT * | conflict, |
BMS_BLKMEM * | blkmem, | ||
SCIP_SET * | set, | ||
SCIP_STAT * | stat, | ||
SCIP_VAR * | var, | ||
SCIP_BOUNDTYPE | boundtype, | ||
SCIP_BDCHGIDX * | bdchgidx, | ||
SCIP_Real | relaxedbd ) |
adds variable's bound to conflict candidate queue
conflict | conflict analysis data |
blkmem | block memory |
set | global SCIP settings |
stat | dynamic problem statistics |
var | problem variable |
boundtype | type of bound that was changed: lower or upper bound |
bdchgidx | bound change index (time stamp of bound change), or NULL for current time |
relaxedbd | the relaxed bound |
Definition at line 4117 of file conflict_graphanalysis.c.
References assert(), SCIP_BdChgInfo::bdchgidx, conflictAddBound(), convertToActiveVar(), FALSE, MAX, MIN, NULL, SCIP_BdChgInfo::pos, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_MULTAGGR, SCIPbdchgidxGetPos(), SCIPbdchgidxIsEarlier(), SCIPbdchginfoGetDepth(), SCIPbdchginfoGetIdx(), SCIPbdchginfoGetNewbound(), SCIPbdchginfoGetOldbound(), SCIPbdchginfoGetPos(), SCIPbdchginfoIsRedundant(), SCIPconflictAddBound(), SCIPsetDebugMsg, SCIPsetIsGE(), SCIPsetIsGT(), SCIPsetIsLE(), SCIPsetIsLT(), SCIPvarAdjustLb(), SCIPvarAdjustUb(), SCIPvarGetBdchgInfo(), SCIPvarGetBdchgInfoLb(), SCIPvarGetBdchgInfoUb(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarIsActive(), and var.
Referenced by SCIPaddConflictRelaxedBd(), SCIPaddConflictRelaxedLb(), and SCIPaddConflictRelaxedUb().
SCIP_RETCODE SCIPconflictIsVarUsed | ( | SCIP_CONFLICT * | conflict, |
SCIP_VAR * | var, | ||
SCIP_SET * | set, | ||
SCIP_BOUNDTYPE | boundtype, | ||
SCIP_BDCHGIDX * | bdchgidx, | ||
SCIP_Bool * | used ) |
checks if the given variable is already part of the current conflict set or queued for resolving with the same or even stronger bound
conflict | conflict analysis data |
var | problem variable |
set | global SCIP settings |
boundtype | type of bound for which the score should be increased |
bdchgidx | bound change index (time stamp of bound change), or NULL for current time |
used | pointer to store if the variable is already used |
Definition at line 4281 of file conflict_graphanalysis.c.
References assert(), convertToActiveVar(), SCIP_Conflict::count, FALSE, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_MULTAGGR, SCIPABORT, SCIPerrorMessage, SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPsetDebugMsg, SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarIsActive(), TRUE, and var.
Referenced by SCIPisConflictVarUsed().
|
static |
inserts variable's new bounds into bound change arrays
set | global SCIP settings |
var | variable to change the LP bounds for |
newlb | new lower bound |
newub | new upper bound |
oldlpbdchgs | old LP bound changes used for reset the LP bound change |
relaxedlpbdchgs | relaxed LP bound changes used for reset the LP bound change |
lpi | pointer to LPi to access infinity of LP solver; necessary to set correct value |
Definition at line 4340 of file conflict_graphanalysis.c.
References assert(), SCIP_LPBdChgs::bdchgcolinds, SCIP_LPBdChgs::bdchginds, SCIP_LPBdChgs::bdchglbs, SCIP_LPBdChgs::bdchgubs, c, SCIP_LPBdChgs::nbdchgs, NULL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPcolGetLPPos(), SCIPlpiInfinity(), SCIPlpiIsInfinity(), SCIPsetIsEQ(), SCIPsetIsInfinity(), SCIPvarGetCol(), SCIPvarGetLbLP(), SCIPvarGetStatus(), SCIPvarGetUbLP(), TRUE, SCIP_LPBdChgs::usedcols, and var.
Referenced by SCIPundoBdchgsProof().
|
static |
adds variable to candidate list, if the current best bound corresponding to the proof coefficient is local; returns the array position in the candidate list, where the new candidate was inserted, or -1 if the variable can relaxed to global bounds immediately without increasing the proof's activity; the candidates are sorted with respect to the following two criteria:
set | global SCIP settings |
currentdepth | current depth in the tree |
var | variable to add to candidate array |
lbchginfopos | positions of currently active lower bound change information in variable's array |
ubchginfopos | positions of currently active upper bound change information in variable's array |
proofcoef | coefficient of variable in infeasibility/bound proof |
prooflhs | left hand side of infeasibility/bound proof |
proofact | activity of infeasibility/bound proof row |
cands | pointer to candidate array for undoing bound changes |
candscores | pointer to candidate score array for undoing bound changes |
newbounds | pointer to candidate new bounds array for undoing bound changes |
proofactdeltas | pointer to proof activity increase array for undoing bound changes |
candssize | pointer to size of cands arrays |
ncands | pointer to count number of candidates in bound change list |
firstcand | position of first unprocessed bound change candidate |
Definition at line 4427 of file conflict_graphanalysis.c.
References assert(), bdchginfoIsResolvable(), calcBdchgScore(), depth, ensureCandsSize(), FALSE, i, NULL, QUAD, QUAD_TO_DBL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPquadprecProdQD, SCIPquadprecSumDD, SCIPsetDebugMsg, SCIPsetIsGT(), SCIPsetIsZero(), SCIPvarGetLbLocal(), SCIPvarGetLbLP(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIPvarGetUbLP(), SCIPvarIsBinary(), and var.
Referenced by SCIPundoBdchgsProof().
SCIP_RETCODE SCIPundoBdchgsProof | ( | SCIP_SET * | set, |
SCIP_PROB * | prob, | ||
int | currentdepth, | ||
SCIP_Real * | proofcoefs, | ||
SCIP_Real | prooflhs, | ||
SCIP_Real * | proofact, | ||
SCIP_Real * | curvarlbs, | ||
SCIP_Real * | curvarubs, | ||
int * | lbchginfoposs, | ||
int * | ubchginfoposs, | ||
SCIP_LPBDCHGS * | oldlpbdchgs, | ||
SCIP_LPBDCHGS * | relaxedlpbdchgs, | ||
SCIP_Bool * | resolve, | ||
SCIP_LPI * | lpi ) |
undoes bound changes on variables, still leaving the given infeasibility proof valid
set | global SCIP settings |
prob | problem data |
currentdepth | current depth in the tree |
proofcoefs | coefficients in infeasibility proof |
prooflhs | left hand side of proof |
proofact | current activity of proof |
curvarlbs | current lower bounds of active problem variables |
curvarubs | current upper bounds of active problem variables |
lbchginfoposs | positions of currently active lower bound change information in variables' arrays |
ubchginfoposs | positions of currently active upper bound change information in variables' arrays |
oldlpbdchgs | old LP bound changes used for reset the LP bound change, or NULL |
relaxedlpbdchgs | relaxed LP bound changes used for reset the LP bound change, or NULL |
resolve | pointer to store whether the changed LP should be resolved again, or NULL |
lpi | pointer to LPi to access infinity of LP solver; necessary to set correct values |
Definition at line 4559 of file conflict_graphanalysis.c.
References addBdchg(), addCand(), assert(), FALSE, i, NULL, nvars, SCIP_Prob::nvars, QUAD, QUAD_TO_DBL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPquadprecProdQD, SCIPquadprecSumDD, SCIPsetAllocBufferArray, SCIPsetDebugMsg, SCIPsetFreeBufferArray, SCIPsetIsEQ(), SCIPsetIsFeasGT(), SCIPsetIsGT(), SCIPsetIsLT(), SCIPsetIsNegative(), SCIPsetIsPositive(), SCIPsetIsZero(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPvarIsInLP(), skipRedundantBdchginfos(), TRUE, var, SCIP_Prob::vars, and vars.
Referenced by SCIPconflictAnalyzePseudo(), undoBdchgsDualfarkas(), and undoBdchgsDualsol().
|
static |
analyzes an infeasible LP and undoes additional bound changes while staying infeasible
set | global SCIP settings |
prob | problem data |
lp | LP data |
currentdepth | current depth in the tree |
curvarlbs | current lower bounds of active problem variables |
curvarubs | current upper bounds of active problem variables |
lbchginfoposs | positions of currently active lower bound change information in variables' arrays |
ubchginfoposs | positions of currently active upper bound change information in variables' arrays |
oldlpbdchgs | old LP bound changes used for reset the LP bound change, or NULL |
relaxedlpbdchgs | relaxed LP bound changes used for reset the LP bound change, or NULL |
valid | pointer to store whether the unfixings are valid |
resolve | pointer to store whether the changed LP should be resolved again |
farkascoefs | coefficients in the proof constraint |
farkaslhs | lhs of the proof constraint |
farkasactivity | maximal activity of the proof constraint |
Definition at line 4771 of file conflict_graphanalysis.c.
References assert(), SCIP_Lp::cutoffbound, FALSE, SCIP_Lp::flushed, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPlpGetLPI(), SCIPsetDebugMsg, SCIPsetIsFeasGT(), SCIPundoBdchgsProof(), SCIP_Lp::solved, TRUE, and valid.
Referenced by SCIPrunBoundHeuristic().
|
static |
create conflict LP bound change data structure
lpbdchgs | pointer to store the conflict LP bound change data structure |
set | global SCIP settings |
ncols | number of columns |
Definition at line 4832 of file conflict_graphanalysis.c.
References BMSclearMemoryArray, SCIP_CALL, SCIP_OKAY, SCIPsetAllocBuffer, and SCIPsetAllocBufferArray.
Referenced by SCIPrunBoundHeuristic().
|
static |
ensures, that side change arrays can store at least num entries
set | global SCIP settings |
sidechginds | pointer to side change index array |
sidechgoldlhss | pointer to side change old left hand sides array |
sidechgoldrhss | pointer to side change old right hand sides array |
sidechgnewlhss | pointer to side change new left hand sides array |
sidechgnewrhss | pointer to side change new right hand sides array |
sidechgssize | pointer to size of side change arrays |
num | minimal number of entries to be able to store in side change arrays |
Definition at line 4859 of file conflict_graphanalysis.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPsetCalcMemGrowSize(), and SCIPsetReallocBufferArray.
Referenced by addSideRemoval().
|
static |
adds removal of row's side to side change arrays; finite sides are only replaced by near infinite sides, such that the row's sense in the LP solver is not changed
set | global SCIP settings |
row | LP row to change the sides for |
lpiinfinity | value treated as infinity in LP solver |
sidechginds | pointer to side change index array |
sidechgoldlhss | pointer to side change old left hand sides array |
sidechgoldrhss | pointer to side change old right hand sides array |
sidechgnewlhss | pointer to side change new left hand sides array |
sidechgnewrhss | pointer to side change new right hand sides array |
sidechgssize | pointer to size of side change arrays |
nsidechgs | pointer to number of used slots in side change arrays |
Definition at line 4898 of file conflict_graphanalysis.c.
References assert(), ensureSidechgsSize(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetRhs(), and SCIPsetIsInfinity().
Referenced by SCIPrunBoundHeuristic().
|
static |
reset conflict LP bound change data structure
lpbdchgs | conflict LP bound change data structure |
ncols | number of columns |
Definition at line 4972 of file conflict_graphanalysis.c.
References assert(), BMSclearMemoryArray, SCIP_LPBdChgs::nbdchgs, NULL, and SCIP_LPBdChgs::usedcols.
Referenced by SCIPrunBoundHeuristic().
|
static |
free conflict LP bound change data structure
lpbdchgs | pointer to store the conflict LP bound change data structure |
set | global SCIP settings |
Definition at line 4985 of file conflict_graphanalysis.c.
References SCIPsetFreeBuffer, and SCIPsetFreeBufferArray.
Referenced by SCIPrunBoundHeuristic().
|
static |
analyzes an LP exceeding the objective limit and undoes additional bound changes while staying beyond the objective limit
set | global SCIP settings |
prob | problem data |
lp | LP data |
currentdepth | current depth in the tree |
curvarlbs | current lower bounds of active problem variables |
curvarubs | current upper bounds of active problem variables |
lbchginfoposs | positions of currently active lower bound change information in variables' arrays |
ubchginfoposs | positions of currently active upper bound change information in variables' arrays |
oldlpbdchgs | old LP bound changes used for reset the LP bound change, or NULL |
relaxedlpbdchgs | relaxed LP bound changes used for reset the LP bound change, or NULL |
valid | pointer to store whether the unfixings are valid |
resolve | pointer to store whether the changed LP should be resolved again |
dualcoefs | coefficients in the proof constraint |
duallhs | lhs of the proof constraint |
dualactivity | maximal activity of the proof constraint |
Definition at line 5003 of file conflict_graphanalysis.c.
References assert(), SCIP_Lp::cutoffbound, FALSE, SCIP_Lp::flushed, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPlpGetLPI(), SCIPsetDebugMsg, SCIPsetIsFeasGT(), SCIPundoBdchgsProof(), SCIP_Lp::solved, TRUE, and valid.
Referenced by SCIPrunBoundHeuristic().
SCIP_RETCODE SCIPrunBoundHeuristic | ( | SCIP_CONFLICT * | conflict, |
SCIP_SET * | set, | ||
SCIP_STAT * | stat, | ||
SCIP_PROB * | origprob, | ||
SCIP_PROB * | transprob, | ||
SCIP_TREE * | tree, | ||
SCIP_REOPT * | reopt, | ||
SCIP_LP * | lp, | ||
SCIP_LPI * | lpi, | ||
BMS_BLKMEM * | blkmem, | ||
SCIP_Real * | proofcoefs, | ||
SCIP_Real * | prooflhs, | ||
SCIP_Real * | proofactivity, | ||
SCIP_Real * | curvarlbs, | ||
SCIP_Real * | curvarubs, | ||
int * | lbchginfoposs, | ||
int * | ubchginfoposs, | ||
int * | iterations, | ||
SCIP_Bool | marklpunsolved, | ||
SCIP_Bool * | dualproofsuccess, | ||
SCIP_Bool * | valid ) |
try to find a subset of changed bounds leading to an infeasible LP
conflict | conflict data |
set | global SCIP settings |
stat | problem statistics |
origprob | original problem |
transprob | transformed problem |
tree | branch and bound tree |
reopt | reoptimization data |
lp | LP data |
lpi | LPI data |
blkmem | block memory |
proofcoefs | coefficients in the proof constraint |
prooflhs | lhs of the proof constraint |
proofactivity | maximal activity of the proof constraint |
curvarlbs | current lower bounds of active problem variables |
curvarubs | current upper bounds of active problem variables |
lbchginfoposs | positions of currently active lower bound change information in variables' arrays |
ubchginfoposs | positions of currently active upper bound change information in variables' arrays |
iterations | pointer to store the total number of LP iterations used |
marklpunsolved | whether LP should be marked unsolved after analysis (needed for strong branching) |
dualproofsuccess | pointer to store success result of dual proof analysis |
valid | pointer to store whether the result is still a valid proof |
Definition at line 5069 of file conflict_graphanalysis.c.
References addSideRemoval(), assert(), SCIP_LPBdChgs::bdchginds, SCIP_LPBdChgs::bdchglbs, SCIP_LPBdChgs::bdchgubs, BMSclearMemoryArray, SCIP_Stat::conflictlptime, SCIP_Conflict::conflictset, SCIP_ConflictSet::conflicttype, SCIP_Lp::dualchecked, SCIP_Lp::dualfeasible, FALSE, i, lpbdchgsCreate(), lpbdchgsFree(), lpbdchgsReset(), SCIP_Lp::lpiitlim, SCIP_Lp::lpiobjlim, SCIP_Lp::lpobjval, SCIP_Lp::lpsolstat, SCIP_LPBdChgs::nbdchgs, SCIP_Stat::nconflictlpiterations, SCIP_Stat::nconflictlps, NULL, objval, SCIP_Lp::primalchecked, SCIP_Lp::primalfeasible, r, SCIP_Bool, SCIP_CALL, SCIP_CONFTYPE_INFEASLP, SCIP_INVALID, SCIP_LONGINT_FORMAT, SCIP_LPERROR, SCIP_LPPAR_LPITLIM, SCIP_LPPAR_OBJLIM, SCIP_LPSOLSTAT_NOTSOLVED, SCIP_OKAY, SCIP_Real, SCIPaggrRowCreate(), SCIPaggrRowFree(), SCIPaggrRowGetInds(), SCIPaggrRowGetNNz(), SCIPaggrRowGetProbvarValue(), SCIPaggrRowGetRhs(), SCIPclockStart(), SCIPclockStop(), SCIPconflictAnalyzeDualProof(), SCIPgetDualProof(), SCIPgetFarkasProof(), SCIPlpDivingObjChanged(), SCIPlpGetNCols(), SCIPlpGetNRows(), SCIPlpGetRows(), SCIPlpiChgBounds(), SCIPlpiChgSides(), SCIPlpiGetIterations(), SCIPlpiGetObjval(), SCIPlpiInfinity(), SCIPlpiIsDualFeasible(), SCIPlpiIsObjlimExc(), SCIPlpiIsPrimalInfeasible(), SCIPlpiSetIntpar(), SCIPlpiSetRealpar(), SCIPlpiSolveDual(), SCIPprobAllColsInLP(), SCIPprobGetNVars(), SCIPprobGetVars(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetRhs(), SCIProwIsLocal(), SCIPsetAllocBufferArray, SCIPsetDebugMsg, SCIPsetFreeBufferArray, SCIPtreeGetCurrentDepth(), SCIPtreeGetEffectiveRootDepth(), SCIPvarGetProbindex(), SCIP_Lp::solved, undoBdchgsDualfarkas(), undoBdchgsDualsol(), valid, and vars.
Referenced by conflictAnalyzeLP().
SCIP_RETCODE SCIPconflictAnalyze | ( | SCIP_CONFLICT * | conflict, |
BMS_BLKMEM * | blkmem, | ||
SCIP_SET * | set, | ||
SCIP_STAT * | stat, | ||
SCIP_PROB * | prob, | ||
SCIP_TREE * | tree, | ||
int | validdepth, | ||
SCIP_Bool * | success ) |
analyzes conflicting bound changes that were added with calls to SCIPconflictAddBound(), and on success, calls the conflict handlers to create a conflict constraint out of the resulting conflict set; updates statistics for propagation conflict analysis
conflict | conflict analysis data |
blkmem | block memory of transformed problem |
set | global SCIP settings |
stat | problem statistics |
prob | problem data |
tree | branch and bound tree |
validdepth | minimal depth level at which the initial conflict set is valid |
success | pointer to store whether a conflict constraint was created, or NULL |
Definition at line 5448 of file conflict_graphanalysis.c.
References assert(), SCIP_Conflict::bdchgqueue, conflictAnalyze(), conflictCalcMaxsize(), SCIP_Conflict::conflictset, FALSE, SCIP_Conflict::forcedbdchgqueue, SCIP_ConflictSet::nbdchginfos, SCIP_Conflict::npropcalls, SCIP_Conflict::npropconfconss, SCIP_Conflict::npropconfliterals, SCIP_Conflict::npropreconvconss, SCIP_Conflict::npropreconvliterals, SCIP_Conflict::npropsuccess, NULL, SCIP_Conflict::propanalyzetime, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPclockStart(), SCIPclockStop(), SCIPconflictApplicable(), SCIPpqueueNElems(), SCIPsetDebugMsg, SCIPtreeGetCurrentDepth(), and TRUE.
Referenced by SCIPanalyzeConflict(), and SCIPanalyzeConflictCons().