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.h.
#include "scip/def.h"
#include "scip/type_cuts.h"
#include "scip/type_conflict.h"
#include "scip/type_reopt.h"
#include "scip/type_implics.h"
#include "scip/type_set.h"
#include "scip/type_stat.h"
#include "scip/type_lp.h"
#include "lpi/type_lpi.h"
#include "scip/type_branch.h"
#include "scip/type_mem.h"
#include "scip/type_var.h"
#include "scip/type_prob.h"
#include "scip/type_event.h"
#include "scip/type_message.h"
#include <string.h>
#include <strings.h>
Go to the source code of this file.
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().
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().
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().
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 init method of conflict handler
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 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 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 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().
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().
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 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().
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().
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().
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 with the additional information of a relaxed bound
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().
SCIP_Real SCIPconflictGetVarLb | ( | SCIP_CONFLICT * | conflict, |
SCIP_VAR * | var ) |
returns the conflict lower bound if the variable is present in the current conflict set; otherwise the global lower bound
conflict | conflict analysis data |
var | problem variable |
Definition at line 361 of file conflict_general.c.
References assert(), SCIP_Conflict::count, EPSGE, SCIP_Real, SCIPvarGetLbGlobal(), and var.
Referenced by SCIPgetConflictVarLb().
SCIP_Real SCIPconflictGetVarUb | ( | SCIP_CONFLICT * | conflict, |
SCIP_VAR * | var ) |
returns the conflict upper bound if the variable is present in the current conflict set; otherwise the global upper bound
conflict | conflict analysis data |
var | problem variable |
Definition at line 378 of file conflict_general.c.
References assert(), SCIP_Conflict::count, EPSLE, SCIP_Real, SCIPvarGetUbGlobal(), and var.
Referenced by SCIPgetConflictVarUb().
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().