Detailed Description
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:
- Put all the given bound changes to a priority queue, which is ordered, such that the bound change that was applied last due to branching or deduction is at the top of the queue. The variables in the queue are always active problem variables. Because binary variables are preferred over general integer variables, integer variables are put on the priority queue prior to the binary variables. Create an empty conflict set.
- Remove the top bound change b from the priority queue.
- Perform the following case distinction:
- If the remaining queue is non-empty, and bound change b' (the one that is now on the top of the queue) was applied at the same depth level as b, and if b was a deduction with known inference reason, and if the inference constraint's valid depth is smaller or equal to the conflict detecting constraint's valid depth:
- Resolve bound change b by asking the constraint that inferred the bound change to put all the bound changes on the priority queue, that lead to the deduction of b. Note that these bound changes have at most the same inference depth level as b, and were deduced earlier than b.
- Otherwise, the bound change b was a branching decision or a deduction with missing inference reason, or the inference constraint's validity is more local than the one of the conflict detecting constraint.
- If a the bound changed corresponds to a binary variable, add it or its negation to the conflict set, depending on which of them is currently fixed to FALSE (i.e., the conflict set consists of literals that cannot be FALSE altogether at the same time).
- Otherwise put the bound change into the conflict set. Note that if the bound change was a branching, all deduced bound changes remaining in the priority queue have smaller inference depth level than b, since deductions are always applied after the branching decisions. However, there is the possibility, that b was a deduction, where the inference reason was not given or the inference constraint was too local. With this lack of information, we must treat the deduced bound change like a branching, and there may exist other deduced bound changes of the same inference depth level in the priority queue.
- If the remaining queue is non-empty, and bound change b' (the one that is now on the top of the queue) was applied at the same depth level as b, and if b was a deduction with known inference reason, and if the inference constraint's valid depth is smaller or equal to the conflict detecting constraint's valid depth:
- If priority queue is non-empty, goto step 2.
- The conflict set represents the conflict clause saying that at least one of the conflict variables must take a different value. The conflict set is then passed to the conflict handlers, that may create a corresponding constraint (e.g. a logicor constraint or bound disjunction constraint) out of these conflict variables and add it to the problem.
If all deduced bound changes come with (global) inference information, depending on the conflict analyzing strategy, the resulting conflict set has the following property:
- 1-FirstUIP: In the depth level where the conflict was found, at most one variable assigned at that level is member of the conflict set. This conflict variable is the first unique implication point of its depth level (FUIP).
- All-FirstUIP: For each depth level, at most one variable assigned at that level is member of the conflict set. This conflict variable is the first unique implication point of its depth level (FUIP).
The user has to do the following to get the conflict analysis running in its current implementation:
- A constraint handler or propagator supporting the conflict analysis must implement the CONSRESPROP/PROPRESPROP call, that processes a bound change inference b and puts all the reason bounds leading to the application of b with calls to SCIPaddConflictBound() on the conflict queue (algorithm step 3.(a)).
- If the current bounds lead to a deduction of a bound change (e.g. in domain propagation), a constraint handler should call SCIPinferVarLbCons() or SCIPinferVarUbCons(), thus providing the constraint that inferred the bound change. A propagator should call SCIPinferVarLbProp() or SCIPinferVarUbProp() instead, thus providing a pointer to itself.
- If (in the current bounds) an infeasibility is detected, the constraint handler or propagator should
- call SCIPinitConflictAnalysis() to initialize the conflict queue,
- call SCIPaddConflictBound() for each bound that lead to the conflict,
- call SCIPanalyzeConflictCons() or SCIPanalyzeConflict() to analyze the conflict and add an appropriate conflict constraint.
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.
Function Documentation
◆ SCIPconflictsetCreate()
SCIP_RETCODE SCIPconflictsetCreate | ( | SCIP_CONFLICTSET ** | conflictset, |
BMS_BLKMEM * | blkmem | ||
) |
creates an empty conflict set
- Parameters
-
conflictset pointer to store the conflict set blkmem block memory of transformed problem
Definition at line 989 of file conflict_graphanalysis.c.
References BMSallocBlockMemory, conflictsetClear(), NULL, SCIP_ALLOC, and SCIP_OKAY.
Referenced by SCIPconflictCreate().
◆ SCIPconflictsetFree()
void SCIPconflictsetFree | ( | SCIP_CONFLICTSET ** | conflictset, |
BMS_BLKMEM * | blkmem | ||
) |
frees a conflict set
- Parameters
-
conflictset pointer to the conflict set blkmem block memory of transformed problem
Definition at line 1045 of file conflict_graphanalysis.c.
References BMSfreeBlockMemory, BMSfreeBlockMemoryArrayNull, and NULL.
Referenced by conflictAddConflictset(), conflictInsertConflictset(), SCIPconflictFlushConss(), and SCIPconflictFree().
◆ SCIPconflicthdlrCopyInclude()
SCIP_RETCODE SCIPconflicthdlrCopyInclude | ( | SCIP_CONFLICTHDLR * | conflicthdlr, |
SCIP_SET * | set | ||
) |
copies the given conflict handler to a new scip
- Parameters
-
conflicthdlr conflict handler set SCIP_SET of SCIP to copy to
Definition at line 1109 of file conflict_graphanalysis.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPconflicthdlrGetName(), and SCIPsetDebugMsg.
Referenced by SCIPsetCopyPlugins().
◆ 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
- Parameters
-
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 doConflicthdlrCreate(), NULL, SCIP_CALL_FINALLY, SCIP_OKAY, and SCIPconflicthdlrFree().
Referenced by SCIPincludeConflicthdlr(), and SCIPincludeConflicthdlrBasic().
◆ SCIPconflicthdlrFree()
SCIP_RETCODE SCIPconflicthdlrFree | ( | SCIP_CONFLICTHDLR ** | conflicthdlr, |
SCIP_SET * | set | ||
) |
calls destructor and frees memory of conflict handler
- Parameters
-
conflicthdlr pointer to conflict handler data structure set global SCIP settings
Definition at line 1214 of file conflict_graphanalysis.c.
References BMSfreeMemory, BMSfreeMemoryArrayNull, NULL, SCIP_CALL, SCIP_OKAY, and SCIPclockFree().
Referenced by SCIPconflicthdlrCreate().
◆ SCIPconflicthdlrInit()
SCIP_RETCODE SCIPconflicthdlrInit | ( | SCIP_CONFLICTHDLR * | conflicthdlr, |
SCIP_SET * | set | ||
) |
calls init method of conflict handler
calls initialization method of conflict handler
- Parameters
-
conflicthdlr conflict handler set global SCIP settings
Definition at line 1242 of file conflict_graphanalysis.c.
References 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.
◆ SCIPconflicthdlrExit()
SCIP_RETCODE SCIPconflicthdlrExit | ( | SCIP_CONFLICTHDLR * | conflicthdlr, |
SCIP_SET * | set | ||
) |
calls exit method of conflict handler
- Parameters
-
conflicthdlr conflict handler set global SCIP settings
Definition at line 1279 of file conflict_graphanalysis.c.
References FALSE, SCIP_Conflicthdlr::initialized, SCIP_Conflicthdlr::name, NULL, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPclockStart(), SCIPclockStop(), SCIPerrorMessage, and SCIP_Conflicthdlr::setuptime.
Referenced by SCIPsetInitPlugins().
◆ SCIPconflicthdlrInitsol()
SCIP_RETCODE SCIPconflicthdlrInitsol | ( | SCIP_CONFLICTHDLR * | conflicthdlr, |
SCIP_SET * | set | ||
) |
informs conflict handler that the branch and bound process is being started
- Parameters
-
conflicthdlr conflict handler set global SCIP settings
Definition at line 1310 of file conflict_graphanalysis.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPclockStart(), SCIPclockStop(), and SCIP_Conflicthdlr::setuptime.
Referenced by SCIPsetExitprePlugins().
◆ SCIPconflicthdlrExitsol()
SCIP_RETCODE SCIPconflicthdlrExitsol | ( | SCIP_CONFLICTHDLR * | conflicthdlr, |
SCIP_SET * | set | ||
) |
informs conflict handler that the branch and bound process data is being freed
- Parameters
-
conflicthdlr conflict handler set global SCIP settings
Definition at line 1334 of file conflict_graphanalysis.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPclockStart(), SCIPclockStop(), and SCIP_Conflicthdlr::setuptime.
Referenced by SCIPsetInitsolPlugins().
◆ SCIPconflicthdlrExec()
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
- Parameters
-
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 SCIP_Conflicthdlr::conflicttime, SCIP_Conflicthdlr::name, NULL, SCIP_CALL, SCIP_CONSADDED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_INVALIDRESULT, SCIP_OKAY, SCIPclockStart(), SCIPclockStop(), SCIPerrorMessage, and SCIPnodeGetDepth().
Referenced by conflictAddConflictCons().
◆ SCIPconflicthdlrSetPriority()
void SCIPconflicthdlrSetPriority | ( | SCIP_CONFLICTHDLR * | conflicthdlr, |
SCIP_SET * | set, | ||
int | priority | ||
) |
sets priority of conflict handler
- Parameters
-
conflicthdlr conflict handler set global SCIP settings priority new priority of the conflict handler
Definition at line 1523 of file conflict_graphanalysis.c.
References FALSE, NULL, and SCIP_Conflicthdlr::priority.
Referenced by SCIPsetConflicthdlrPriority().
◆ SCIPconflicthdlrSetCopy()
void SCIPconflicthdlrSetCopy | ( | SCIP_CONFLICTHDLR * | conflicthdlr, |
SCIP_DECL_CONFLICTCOPY((*conflictcopy)) | |||
) |
set copy method of conflict handler
- Parameters
-
conflicthdlr conflict handler
Definition at line 1426 of file conflict_graphanalysis.c.
References NULL.
Referenced by SCIPsetConflicthdlrCopy().
◆ SCIPconflicthdlrSetFree()
void SCIPconflicthdlrSetFree | ( | SCIP_CONFLICTHDLR * | conflicthdlr, |
SCIP_DECL_CONFLICTFREE((*conflictfree)) | |||
) |
set destructor of conflict handler
- Parameters
-
conflicthdlr conflict handler
Definition at line 1437 of file conflict_graphanalysis.c.
References NULL.
Referenced by SCIPsetConflicthdlrFree().
◆ SCIPconflicthdlrSetInit()
void SCIPconflicthdlrSetInit | ( | SCIP_CONFLICTHDLR * | conflicthdlr, |
SCIP_DECL_CONFLICTINIT((*conflictinit)) | |||
) |
set initialization method of conflict handler
- Parameters
-
conflicthdlr conflict handler
Definition at line 1449 of file conflict_graphanalysis.c.
References NULL.
Referenced by SCIPsetConflicthdlrInit().
◆ SCIPconflicthdlrSetExit()
void SCIPconflicthdlrSetExit | ( | SCIP_CONFLICTHDLR * | conflicthdlr, |
SCIP_DECL_CONFLICTEXIT((*conflictexit)) | |||
) |
set deinitialization method of conflict handler
- Parameters
-
conflicthdlr conflict handler
Definition at line 1460 of file conflict_graphanalysis.c.
References NULL.
Referenced by SCIPsetConflicthdlrExit().
◆ SCIPconflicthdlrSetInitsol()
void SCIPconflicthdlrSetInitsol | ( | SCIP_CONFLICTHDLR * | conflicthdlr, |
SCIP_DECL_CONFLICTINITSOL((*conflictinitsol)) | |||
) |
set solving process initialization method of conflict handler
- Parameters
-
conflicthdlr conflict handler
Definition at line 1471 of file conflict_graphanalysis.c.
References NULL.
Referenced by SCIPsetConflicthdlrInitsol().
◆ SCIPconflicthdlrSetExitsol()
void SCIPconflicthdlrSetExitsol | ( | SCIP_CONFLICTHDLR * | conflicthdlr, |
SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol)) | |||
) |
set solving process deinitialization method of conflict handler
- Parameters
-
conflicthdlr conflict handler
Definition at line 1482 of file conflict_graphanalysis.c.
References NULL.
Referenced by SCIPsetConflicthdlrExitsol().
◆ SCIPconflicthdlrEnableOrDisableClocks()
void SCIPconflicthdlrEnableOrDisableClocks | ( | SCIP_CONFLICTHDLR * | conflicthdlr, |
SCIP_Bool | enable | ||
) |
enables or disables all clocks of conflicthdlr
, depending on the value of the flag
- Parameters
-
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 SCIP_Conflicthdlr::conflicttime, NULL, SCIPclockEnableOrDisable(), and SCIP_Conflicthdlr::setuptime.
Referenced by SCIP_DECL_PARAMCHGD().
◆ SCIPconflictApplicable()
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
- Parameters
-
set global SCIP settings
Definition at line 1581 of file conflict_graphanalysis.c.
Referenced by SCIPconflictAnalyze(), and SCIPisConflictAnalysisApplicable().
◆ 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
- Parameters
-
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 conflictEnsureTmpbdchginfosMem(), SCIP_Conflict::ntmpbdchginfos, NULL, SCIP_CALL, SCIP_OKAY, SCIPbdchginfoCreate(), and SCIP_Conflict::tmpbdchginfos.
Referenced by conflictCreateReconvergenceConss(), and SCIPconflictAnalyzeRemainingBdchgs().
◆ conflictCalcMaxsize()
calculates the maximal size of conflict sets to be used
- Parameters
-
set global SCIP settings prob problem data
Definition at line 1896 of file conflict_graphanalysis.c.
References MAX, SCIP_Prob::ncontvars, NULL, and SCIP_Prob::nvars.
Referenced by SCIPconflictAnalyze(), SCIPconflictAnalyzeRemainingBdchgs(), and SCIPconflictFlushConss().
◆ 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
- Parameters
-
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(), FALSE, NULL, 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, and SCIP_Prob::vars.
Referenced by SCIPconflictAnalyzePseudo(), undoBdchgsDualfarkas(), and undoBdchgsDualsol().
◆ 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
- Parameters
-
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 conflictAddBound(), conflictAddConflictBound(), conflictAnalyze(), conflictCalcMaxsize(), conflictCreateTmpBdchginfo(), SCIP_Conflict::conflictset, SCIP_ConflictSet::conflicttype, FALSE, incVSIDS(), SCIP_Var::lbchginfos, SCIP_Var::nlbchginfos, SCIP_Var::nubchginfos, NULL, 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_Var::ubchginfos, SCIP_ConflictSet::usescutoffbound, and SCIP_Prob::vars.
Referenced by conflictAnalyzeLP(), and SCIPconflictAnalyzePseudo().
◆ 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
- Parameters
-
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 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_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().
◆ SCIPconflictAddBound()
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
- Parameters
-
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 conflictAddBound(), convertToActiveVar(), FALSE, NULL, scalars, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_MULTAGGR, SCIPbdchgidxIsEarlier(), SCIPbdchginfoGetIdx(), SCIPbdchginfoGetNewbound(), SCIPboundtypeOpposite(), SCIPconflictAddBound(), SCIPvarGetBdchgInfo(), SCIPvarGetMultaggrNVars(), SCIPvarGetMultaggrScalars(), SCIPvarGetMultaggrVars(), SCIPvarGetStatus(), and SCIPvarIsActive().
Referenced by SCIPaddConflictBd(), SCIPaddConflictBinvar(), SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPconflictAddBound(), and SCIPconflictAddRelaxedBound().
◆ 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
- Parameters
-
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 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(), and SCIPvarIsActive().
Referenced by SCIPaddConflictRelaxedBd(), SCIPaddConflictRelaxedLb(), and SCIPaddConflictRelaxedUb().
◆ SCIPconflictIsVarUsed()
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
- Parameters
-
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 SCIP_Var::conflictlb, SCIP_Var::conflictlbcount, SCIP_Var::conflictub, SCIP_Var::conflictubcount, convertToActiveVar(), SCIP_Conflict::count, FALSE, NULL, 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(), and TRUE.
Referenced by SCIPisConflictVarUsed().
◆ SCIPconflictGetVarLb()
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
- Parameters
-
conflict conflict analysis data var problem variable
Definition at line 357 of file conflict_general.c.
References SCIP_Var::conflictlb, SCIP_Var::conflictlbcount, SCIP_Var::conflictrelaxedlb, SCIP_Conflict::count, EPSGE, and SCIPvarGetLbGlobal().
Referenced by SCIPgetConflictVarLb().
◆ SCIPconflictGetVarUb()
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
- Parameters
-
conflict conflict analysis data var problem variable
Definition at line 374 of file conflict_general.c.
References SCIP_Var::conflictrelaxedub, SCIP_Var::conflictub, SCIP_Var::conflictubcount, SCIP_Conflict::count, EPSLE, and SCIPvarGetUbGlobal().
Referenced by SCIPgetConflictVarUb().
◆ 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
- call undoBdchgsDualfarkas() or undoBdchgsDualsol() -> update lb/ubchginfoposs arrays -> store additional changes in bdchg and curvarlbs/ubs arrays -> apply additional changes to the LPI
- (optional) if additional bound changes were undone: -> resolve LP -> goto 1.
- redo all bound changes in the LPI to restore the LPI to its original state
- analyze conflict -> put remaining changed bounds (see lb/ubchginfoposs arrays) into starting conflict set
- Parameters
-
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(), 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, 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, 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(), and undoBdchgsDualsol().
Referenced by conflictAnalyzeLP().