SCIP
Solving Constraint Integer Programs
conflict_resolution.c File Reference
Detailed Description
Methods for generalized resolution conflict analysis.
This file implements a conflict analysis method based on generalized resolution, as detailed in the paper:
Gioni Mexi, et al. "Cut-based Conflict Analysis in Mixed Integer Programming." arXiv preprint arXiv:2410.15110 (2024).
The generalized resolution conflict analysis procedure starts with an initial conflict row and it iteratively aggregates this row with a reason row—the row that propagated the bound change causing the conflict. The aggregation cancels the coefficient of the resolving variable. This process continues until a first unique implication point (FUIP) is reached. If the aggregation does not yield a valid (infeasible) row, the algorithm attempts to reduce the reason row (e.g., using MIR reduction) and retries the aggregation. Once a valid conflict row with negative slack is generated, a conflict constraint is constructed and added to the problem.
Definition in file conflict_resolution.c.
#include "blockmemshell/memory.h"#include "scip/clock.h"#include "scip/conflict.h"#include "scip/conflict_resolution.h"#include "scip/cons.h"#include "scip/cons_linear.h"#include "scip/cuts.h"#include "scip/history.h"#include "scip/prob.h"#include "scip/prop.h"#include "scip/pub_cons.h"#include "scip/pub_conflict.h"#include "scip/pub_lp.h"#include "scip/pub_message.h"#include "scip/pub_misc.h"#include "scip/pub_var.h"#include "scip/scip_conflict.h"#include "scip/scip_cons.h"#include "scip/scip_mem.h"#include "scip/scip_prob.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/tree.h"#include "scip/var.h"#include <string.h>#include <strings.h>Go to the source code of this file.
Macros | |
| #define | BOUNDSWITCH 0.51 |
| #define | POSTPROCESS FALSE |
| #define | USEVBDS FALSE |
| #define | FIXINTEGRALRHS FALSE |
| #define | MINFRAC 0.05 |
| #define | MAXFRAC 0.999 |
| #define | EPS 1e-06 |
Macro Definition Documentation
◆ BOUNDSWITCH
| #define BOUNDSWITCH 0.51 |
threshold for bound switching - see cuts.c
Definition at line 87 of file conflict_resolution.c.
◆ POSTPROCESS
| #define POSTPROCESS FALSE |
apply postprocessing after MIR calculation - see SCIPcalcMIR()
Definition at line 88 of file conflict_resolution.c.
◆ USEVBDS
| #define USEVBDS FALSE |
use variable bounds - see SCIPcalcMIR()
Definition at line 89 of file conflict_resolution.c.
◆ FIXINTEGRALRHS
| #define FIXINTEGRALRHS FALSE |
try to generate an integral rhs - see SCIPcalcMIR()
Definition at line 90 of file conflict_resolution.c.
◆ MINFRAC
| #define MINFRAC 0.05 |
minimal fractionality of floor(rhs) - see cuts.c
Definition at line 91 of file conflict_resolution.c.
◆ MAXFRAC
| #define MAXFRAC 0.999 |
maximal fractionality of floor(rhs) - see cuts.c
Definition at line 92 of file conflict_resolution.c.
◆ EPS
| #define EPS 1e-06 |
Definition at line 94 of file conflict_resolution.c.
Function Documentation
◆ conflictRowCopy()
|
static |
creates a copy of the given generalized resolution row, allocating an additional amount of memory
- Parameters
-
targetrow pointer to store the generalized resolution row blkmem block memory of transformed problem sourcerow source generalized resolution row
Definition at line 98 of file conflict_resolution.c.
References BMSallocBlockMemory, BMSallocBlockMemoryArray, BMScopyMemoryArray, SCIP_ConflictRow::coefquotient, SCIP_ConflictRow::conflictdepth, SCIP_ConflictRow::conflicttype, SCIP_ConflictRow::inds, SCIP_ConflictRow::insertdepth, SCIP_ConflictRow::isbinary, SCIP_ConflictRow::lhs, SCIP_ConflictRow::nnz, NULL, SCIP_ConflictRow::nvars, SCIP_ConflictRow::repropdepth, SCIP_ALLOC, SCIP_OKAY, SCIP_ConflictRow::slack, SCIP_ConflictRow::usescutoffbound, SCIP_ConflictRow::validdepth, and SCIP_ConflictRow::vals.
Referenced by conflictAnalyzeResolution().
◆ conflictRowReplace()
|
static |
replaces a generalized resolution row by another; allocate an additional amount of memory if needed
- Parameters
-
targetrow pointer to store the generalized resolution row blkmem block memory of transformed problem sourcerow source generalized resolution row
Definition at line 140 of file conflict_resolution.c.
References BMScopyMemoryArray, BMSreallocBlockMemoryArray, SCIP_ConflictRow::coefquotient, SCIP_ConflictRow::conflictdepth, SCIP_ConflictRow::conflicttype, SCIP_ConflictRow::inds, SCIP_ConflictRow::insertdepth, SCIP_ConflictRow::isbinary, SCIP_ConflictRow::lhs, MAX, SCIP_ConflictRow::nnz, NULL, SCIP_ConflictRow::nvars, SCIP_ConflictRow::repropdepth, SCIP_ALLOC, SCIP_OKAY, SCIP_ConflictRow::size, SCIP_ConflictRow::slack, SCIP_ConflictRow::usescutoffbound, SCIP_ConflictRow::validdepth, and SCIP_ConflictRow::vals.
Referenced by conflictAnalyzeResolution(), executeResolutionStep(), and rescaleAndResolve().
◆ conflictEnsureConflictRowsMem()
|
static |
resizes conflict rows array to be able to store at least num entries
- Parameters
-
conflict conflict analysis data set global SCIP settings num minimal number of slots in array
Definition at line 184 of file conflict_resolution.c.
References BMSreallocMemoryArray, SCIP_Conflict::conflictrows, SCIP_Conflict::conflictrowssize, NULL, SCIP_ALLOC, SCIP_OKAY, and SCIPsetCalcMemGrowSize().
Referenced by conflictInsertConflictRow().
◆ conflictInsertConflictRow()
|
static |
add conflict row to the array of all conflicts rows
- Parameters
-
conflict conflict analysis data set global SCIP settings conflictrow conflict row to add
Definition at line 208 of file conflict_resolution.c.
References conflictEnsureConflictRowsMem(), SCIP_Conflict::conflictrows, SCIP_Conflict::nconflictrows, NULL, SCIP_CALL, SCIP_OKAY, and SCIPsetDebugMsgPrint.
Referenced by conflictAnalyzeResolution().
◆ SCIPconflictGetNResConflictConss()
| SCIP_Longint SCIPconflictGetNResConflictConss | ( | SCIP_CONFLICT * | conflict | ) |
gets number of conflict constraints found during propagation with the generalized resolution conflict analysis
- Parameters
-
conflict conflict analysis data
Definition at line 233 of file conflict_resolution.c.
References SCIP_Conflict::nresconfconss, and NULL.
Referenced by SCIPgetNConflictConssFound(), and SCIPprintConflictStatistics().
◆ SCIPconflictGetNResSuccess()
| SCIP_Longint SCIPconflictGetNResSuccess | ( | SCIP_CONFLICT * | conflict | ) |
gets number of calls to generalized resolution conflict analysis that yield at least one conflict constraint
- Parameters
-
conflict conflict analysis data
Definition at line 243 of file conflict_resolution.c.
References SCIP_Conflict::nressuccess, and NULL.
Referenced by SCIPprintConflictStatistics().
◆ SCIPconflictGetNResLargeCoefs()
| SCIP_Longint SCIPconflictGetNResLargeCoefs | ( | SCIP_CONFLICT * | conflict | ) |
gets number of calls to generalized resolution conflict analysis terminating because of large coefficients
- Parameters
-
conflict conflict analysis data
Definition at line 254 of file conflict_resolution.c.
References SCIP_Conflict::nreslargecoefs, and NULL.
Referenced by SCIPprintConflictStatistics().
◆ SCIPconflictGetNResLongConflicts()
| SCIP_Longint SCIPconflictGetNResLongConflicts | ( | SCIP_CONFLICT * | conflict | ) |
gets number of calls to generalized resolution conflict analysis terminating because of long conflicts
- Parameters
-
conflict conflict analysis data
Definition at line 264 of file conflict_resolution.c.
References SCIP_Conflict::nreslongconfs, and NULL.
Referenced by SCIPprintConflictStatistics().
◆ SCIPconflictGetNResCalls()
| SCIP_Longint SCIPconflictGetNResCalls | ( | SCIP_CONFLICT * | conflict | ) |
gets number of calls to generalized resolution conflict analysis
- Parameters
-
conflict conflict analysis data
Definition at line 274 of file conflict_resolution.c.
References SCIP_Conflict::nrescalls, and NULL.
Referenced by SCIPprintConflictStatistics().
◆ conflictCalcResMaxsize()
calculates the maximal size of conflict sets to be used
- Parameters
-
set global SCIP settings prob problem data
Definition at line 487 of file conflict_resolution.c.
References MAX, SCIP_Prob::ncontvars, NULL, and SCIP_Prob::nvars.
Referenced by conflictAnalyzeResolution(), and SCIPconflictAddConflictCon().
◆ tightenCoefs()
|
static |
perform activity based coefficient tightening on a semi-sparse or sparse row defined with a left hand side
- Parameters
-
set global SCIP settings vars array of variables localbounds do we use local bounds? rowcoefs dense row of coefficients rowinds indices of the variables in the row rownnz number of non-zeros in the row rowlhs left hand side of the row nchgcoefs number of changed coefficients redundant pointer to store whether the row is redundant
Definition at line 504 of file conflict_resolution.c.
References EPS, FALSE, MAX, NULL, QUAD, QUAD_ASSIGN, QUAD_TO_DBL, SCIP_CALL_ABORT, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugPrintf, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetNContVars(), SCIPgetNVars(), SCIPquadprecProdQD, SCIPquadprecSumDD, SCIPquadprecSumQD, SCIPquadprecSumQQ, SCIPsetIsGE(), SCIPsetIsInfinity(), SCIPsetIsLE(), SCIPsetIsLT(), SCIPsetIsNegative(), SCIPsetIsPositive(), SCIPsetIsRelGE(), SCIPsetIsRelLE(), SCIPsortDownRealInt(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), and TRUE.
Referenced by conflictAnalyzeResolution().
◆ hasRelaxationOnlyVar()
|
static |
check if the generalized resolution row has a relaxation only variable
- Parameters
-
set global SCIP settings vars array of variables row generalized resolution row
Definition at line 728 of file conflict_resolution.c.
References FALSE, SCIP_ConflictRow::inds, SCIP_ConflictRow::nnz, NULL, SCIPvarIsRelaxationOnly(), and TRUE.
Referenced by SCIPconflictAddConflictCon().
◆ isBinaryConflictRow()
|
static |
check if a generalized resolution row has only binary variables
- Parameters
-
set global SCIP settings vars array of variables row generalized resolution row
Definition at line 755 of file conflict_resolution.c.
References FALSE, SCIP_ConflictRow::inds, SCIP_ConflictRow::nnz, NULL, SCIPvarIsBinary(), and TRUE.
Referenced by ComplementedMirLhs(), executeResolutionStep(), and reduceReason().
◆ conflictRowRemoveZeroVar()
|
static |
Removes a variable with zero coefficient in the generalized resolution row
- Parameters
-
row generalized resolution row set global SCIP settings pos position of variable in conflict row
Definition at line 782 of file conflict_resolution.c.
References SCIP_ConflictRow::inds, SCIP_ConflictRow::nnz, NULL, SCIPsetIsZero(), and SCIP_ConflictRow::vals.
Referenced by conflictRowRemoveZeroVars().
◆ conflictRowRemoveZeroVars()
|
static |
Removes all variables with zero coefficient (< 1e-09) in the generalized resolution row
- Parameters
-
row generalized resolution row set global SCIP settings
Definition at line 803 of file conflict_resolution.c.
References conflictRowRemoveZeroVar(), SCIP_ConflictRow::inds, SCIP_ConflictRow::nnz, NULL, SCIPsetIsZero(), and SCIP_ConflictRow::vals.
Referenced by ComplementedMirLhs(), conflictAnalyzeResolution(), linearCombRows(), and MirReduction().
◆ ComplementedMirLhs()
|
static |
complement and apply MIR to a 0-1 reason constraint lhs <= a^T x
- Parameters
-
set global SCIP settings vars array of variables reasonrow reason row fixsides dense array of variables fixed to a bound currbdchgidx current bound change index idxreason index in the reason divisor the divisor of the row
Definition at line 821 of file conflict_resolution.c.
References conflictRowRemoveZeroVars(), SCIP_ConflictRow::inds, isBinaryConflictRow(), SCIP_ConflictRow::lhs, MAXFRAC, MINFRAC, SCIP_ConflictRow::nnz, NULL, SCIP_OKAY, SCIP_Real, SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPsetCeil(), SCIPsetDebugMsgPrint, SCIPsetFloor(), SCIPsetIsGT(), SCIPvarIsBinary(), TRUE, and SCIP_ConflictRow::vals.
Referenced by reduceReason().
◆ linearCombRows()
|
static |
- Parameters
-
set global SCIP settings row1 first row (aggregated row) row2 second row scale scale factor for second row
Definition at line 975 of file conflict_resolution.c.
References conflictRowRemoveZeroVars(), SCIP_ConflictRow::inds, SCIP_ConflictRow::lhs, SCIP_ConflictRow::nnz, NULL, SCIPsetIsZero(), and SCIP_ConflictRow::vals.
Referenced by rescaleAndResolve().
◆ isResolvableBdchg()
|
static |
returns whether a bound change is resolvable or not
- Parameters
-
bdchginfo bound change to check
Definition at line 1012 of file conflict_resolution.c.
References FALSE, SCIP_BOUNDCHGTYPE_BRANCHING, SCIP_BOUNDCHGTYPE_CONSINFER, SCIP_BOUNDCHGTYPE_PROPINFER, SCIPbdchginfoGetChgtype(), SCIPbdchginfoGetInferCons(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), and TRUE.
Referenced by conflictAnalyzeResolution(), existsResolvablebdchginfo(), and getReasonRow().
◆ existsResolvablebdchginfo()
|
static |
returns whether there exists a resolvable bound change or not
- Parameters
-
conflict conflict analysis data
Definition at line 1041 of file conflict_resolution.c.
References FALSE, isResolvableBdchg(), SCIP_Conflict::resbdchgqueue, SCIPpqueueElems(), SCIPpqueueNElems(), and TRUE.
Referenced by conflictAnalyzeResolution(), and markBdchgAsFixed().
◆ isBdchgConflictRelevant()
|
static |
returns whether a bound change is relevant for the infeasibility of the conflict row. A bound change is relevant if:
- It is an upper bound change with a positive row coefficient,
- It is a lower bound change with a negative row coefficient
- Parameters
-
conflict conflict analysis data bdchginfo bound change to check initial whether we are in the initialization of conflict analysis
Definition at line 1064 of file conflict_resolution.c.
References SCIP_Conflict::conflictrow, FALSE, SCIP_ConflictRow::nnz, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIPbdchginfoGetBoundtype(), SCIPbdchginfoGetVar(), SCIPvarGetProbindex(), TRUE, and SCIP_ConflictRow::vals.
Referenced by conflictFirstCand(), and conflictRemoveCand().
◆ conflictFirstCand()
|
static |
returns next conflict analysis bound change candidate from the queue without removing it
- Parameters
-
set global SCIP settings conflict conflict analysis data initial whether we are in the initialization of conflict analysis
Definition at line 1095 of file conflict_resolution.c.
References conflictFirstCand(), SCIP_Conflict::conflictvarslbs, SCIP_Conflict::conflictvarsubs, isBdchgConflictRelevant(), NULL, SCIP_Conflict::resbdchgqueue, SCIP_BOUNDTYPE_LOWER, SCIP_REAL_MAX, SCIP_REAL_MIN, SCIPbdchginfoGetBoundtype(), SCIPbdchginfoGetDepth(), SCIPbdchginfoGetNewbound(), SCIPbdchginfoGetPos(), SCIPbdchginfoGetVar(), SCIPbdchginfoIsRedundant(), SCIPpqueueFirst(), SCIPpqueueRemove(), SCIPsetDebugMsgPrint, SCIPvarGetName(), and SCIPvarGetProbindex().
Referenced by conflictAnalyzeResolution(), conflictFirstCand(), and markBdchgAsFixed().
◆ conflictRemoveCand()
|
static |
removes and returns next conflict analysis bound change candidate from the queue
- Parameters
-
conflict conflict analysis data initial whether we are in the initialization of conflict analysis
Definition at line 1141 of file conflict_resolution.c.
References isBdchgConflictRelevant(), NULL, SCIP_Conflict::resbdchgqueue, SCIPbdchginfoIsRedundant(), and SCIPpqueueRemove().
Referenced by conflictAnalyzeResolution(), and markBdchgAsFixed().
◆ SCIPconflictResolutionApplicable()
return TRUE if generalized resolution conflict analysis is applicable
- Parameters
-
set global SCIP settings
Definition at line 1161 of file conflict_resolution.c.
Referenced by SCIPconflictAnalyzeResolution().
◆ conflictRowCreate()
|
static |
creates a generalized resolution row
- Parameters
-
row generalized resolution row blkmem block memory of transformed problem
Definition at line 1174 of file conflict_resolution.c.
References BMSallocBlockMemory, FALSE, NULL, SCIP_ALLOC, SCIP_CONFTYPE_PROPAGATION, and SCIP_OKAY.
Referenced by SCIPconflictInitRows().
◆ SCIPconflictInitRows()
| SCIP_RETCODE SCIPconflictInitRows | ( | SCIP_CONFLICT * | conflict, |
| BMS_BLKMEM * | blkmem | ||
| ) |
creates conflict and reason rows
- Parameters
-
conflict conflict analysis data blkmem block memory of transformed problem
Definition at line 1202 of file conflict_resolution.c.
References SCIP_Conflict::conflictrow, conflictRowCreate(), NULL, SCIP_Conflict::reasonrow, SCIP_Conflict::reducedreasonrow, SCIP_Conflict::resolvedconflictrow, SCIP_CALL, and SCIP_OKAY.
Referenced by SCIPconflictCreate().
◆ SCIPconflictRowFree()
| void SCIPconflictRowFree | ( | SCIP_CONFLICTROW ** | row, |
| BMS_BLKMEM * | blkmem | ||
| ) |
frees a generalized resolution row
- Parameters
-
row conflict row blkmem block memory
Definition at line 1220 of file conflict_resolution.c.
References BMSfreeBlockMemory, BMSfreeBlockMemoryArrayNull, and NULL.
Referenced by freeConflictResources(), SCIPconflictAnalyzeResolution(), and SCIPconflictFree().
◆ freeConflictResources()
|
static |
frees all conflict rows and arrays that track unresolvable (fixed) variables
- Parameters
-
conflict conflict analysis data blkmem block memory set global SCIP settings fixbounds dense array of fixed bounds fixsides dense array of variables fixed to a bound
Definition at line 1237 of file conflict_resolution.c.
References SCIP_Conflict::conflictrows, SCIP_Conflict::nconflictrows, SCIPconflictRowFree(), and SCIPsetFreeBufferArray.
Referenced by conflictAnalyzeResolution().
◆ conflictRowClear()
|
static |
resets the data structure of a generalized resolution row
- Parameters
-
blkmem block memory row generalized resolution row nvars number of variables in the problem
Definition at line 1257 of file conflict_resolution.c.
References BMSallocBlockMemoryArray, BMSfreeBlockMemoryArrayNull, SCIP_ConflictRow::coefquotient, SCIP_ConflictRow::conflictdepth, SCIP_ConflictRow::conflicttype, FALSE, SCIP_ConflictRow::insertdepth, SCIP_ConflictRow::isbinary, SCIP_ConflictRow::lhs, SCIP_ConflictRow::nnz, NULL, SCIP_ConflictRow::nvars, SCIP_ConflictRow::repropdepth, SCIP_CONFTYPE_PROPAGATION, SCIP_ConflictRow::slack, SCIP_ConflictRow::usescutoffbound, SCIP_ConflictRow::validdepth, and SCIP_ConflictRow::vals.
Referenced by conflictAnalyzeResolution(), executeResolutionStep(), and MirReduction().
◆ computeSlack()
|
static |
calculates the slack (maxact - rhs) for a generalized resolution row given a set of bounds and coefficients
- Parameters
-
set global SCIP settings vars array of variables row generalized resolution row currbdchginfo current bound change fixbounds dense array of fixed bounds fixsides dense array of variables fixed to a bound
Definition at line 1291 of file conflict_resolution.c.
References bound, SCIP_ConflictRow::inds, SCIP_ConflictRow::lhs, SCIP_ConflictRow::nnz, NULL, QUAD, QUAD_ASSIGN, QUAD_TO_DBL, SCIP_OKAY, SCIP_Real, SCIPbdchginfoGetDepth(), SCIPbdchginfoGetIdx(), SCIPbdchginfoGetPos(), SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPquadprecProdDD, SCIPquadprecSumQD, SCIPquadprecSumQQ, SCIPsetDebugMsgPrint, SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIP_ConflictRow::slack, TRUE, and SCIP_ConflictRow::vals.
Referenced by conflictAnalyzeResolution(), executeResolutionStep(), getConflictRow(), getReasonRow(), markBdchgAsFixed(), MirReduction(), and reduceReason().
◆ MirReduction()
|
static |
reduces the reason row by applying MIR. In the reference solution, each variable is set to the value that was used for the propagation of currbdchginfo.
- Parameters
-
set global SCIP settings blkmem block memory of transformed problem vars array of variables nvars number of variables reasonrow reason row currbdchginfo current bound change to resolve varidx index of the variable to resolve divisor the divisor of the row
Definition at line 1375 of file conflict_resolution.c.
References BOUNDSWITCH, computeSlack(), conflictRowClear(), conflictRowRemoveZeroVars(), FALSE, FIXINTEGRALRHS, SCIP_ConflictRow::inds, SCIP_ConflictRow::lhs, MAX, MAXFRAC, MIN, MINFRAC, SCIP_ConflictRow::nnz, NULL, POSTPROCESS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaggrRowAddCustomCons(), SCIPaggrRowCreate(), SCIPaggrRowFree(), SCIPbdchginfoGetIdx(), SCIPcalcMIR(), SCIPcreateSol(), SCIPdebug, SCIPfreeSol(), SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPsetAllocBufferArray, SCIPsetDebugMsgPrint, SCIPsetFreeBufferArray, SCIPsetIsGT(), SCIPsetSolVal(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), SCIPvarIsIntegral(), SCIP_ConflictRow::slack, USEVBDS, and SCIP_ConflictRow::vals.
Referenced by reduceReason().
◆ weakenVarConflictRow()
|
static |
weaken variable in a generalized resolution row
- Parameters
-
row generalized resolution row set global SCIP settings var variable to weaken pos position in array of indices
Definition at line 1511 of file conflict_resolution.c.
References SCIP_ConflictRow::inds, SCIP_ConflictRow::lhs, SCIP_ConflictRow::nnz, NULL, SCIPdebugMessage, SCIPsetIsGT(), SCIPsetIsLT(), SCIPsetIsZero(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), and SCIP_ConflictRow::vals.
Referenced by weakenConflictRow(), and weakenContinuousVarsConflictRow().
◆ weakenConflictRow()
|
static |
weaken generalized resolution row by setting variables to their global bounds
- Parameters
-
row generalized resolution row set global SCIP settings vars array of variables currbdchgidx current bound change index fixsides dense array of variables fixed to a bound
Definition at line 1543 of file conflict_resolution.c.
References SCIP_ConflictRow::inds, SCIP_ConflictRow::nnz, NULL, SCIP_Real, SCIPdebugMessage, SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPsetIsEQ(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), TRUE, SCIP_ConflictRow::vals, and weakenVarConflictRow().
Referenced by conflictAnalyzeResolution(), and getConflictRow().
◆ weakenContinuousVarsConflictRow()
|
static |
weaken all continuous variables in a generalized resolution row
- Parameters
-
row generalized resolution row set global SCIP settings vars array of variables residx index of variable we are resolving on
Definition at line 1600 of file conflict_resolution.c.
References SCIP_ConflictRow::inds, SCIP_ConflictRow::nnz, NULL, SCIP_OKAY, SCIPdebugMessage, SCIPvarIsIntegral(), SCIP_ConflictRow::vals, and weakenVarConflictRow().
Referenced by executeResolutionStep().
◆ getQuotLargestSmallestCoef()
|
static |
returns the quotient of the largest and smallest value in a semi-sparse array
- Parameters
-
set global SCIP settings inds array of indices vals dense array of values nnz number of nonzeros
Definition at line 1647 of file conflict_resolution.c.
References MAX, MIN, NULL, REALABS, SCIP_Real, and SCIPsetInfinity().
Referenced by conflictAnalyzeResolution().
◆ updateBdchgQueue()
|
static |
for every variable in the row, except the inferred variable, add bound changes
- Parameters
-
set global SCIP settings vars array of variables conflictrow conflict row inferbdchgidx bound change index (time stamp of bound change), or NULL for current time
Definition at line 1678 of file conflict_resolution.c.
References FALSE, SCIP_ConflictRow::inds, SCIP_ConflictRow::nnz, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPsetIsGT(), SCIPsetIsLT(), SCIPvarGetLbGlobal(), SCIPvarGetNBdchgInfosLb(), SCIPvarGetNBdchgInfosUb(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), and SCIP_ConflictRow::vals.
Referenced by conflictAnalyzeResolution(), and markBdchgAsFixed().
◆ slackReducingContinuousBdchgQueue()
|
static |
add all slack reducing continuous bound changes to the continuous bound change queue
- Parameters
-
conflict conflict analysis data vars array of variables row conflict row inferbdchgidx bound change index of latest continuous bound change
Definition at line 1730 of file conflict_resolution.c.
References SCIP_Conflict::continuousbdchgqueue, FALSE, SCIP_ConflictRow::inds, SCIP_ConflictRow::nnz, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbdchgidxGetDepth(), SCIPbdchgidxGetPos(), SCIPbdchginfoGetDepth(), SCIPbdchginfoGetPos(), SCIPpqueueClear(), SCIPpqueueInsert(), SCIPpqueueNElems(), SCIPvarGetLbchgInfo(), SCIPvarGetProbindex(), SCIPvarGetUbchgInfo(), SCIPvarIsIntegral(), and SCIP_ConflictRow::vals.
Referenced by executeResolutionStep().
◆ incVSIDS()
|
static |
increases the conflict score of the variable in the given direction
- Parameters
-
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 1795 of file conflict_resolution.c.
References SCIP_Stat::glbhistory, SCIP_Stat::glbhistorycrun, NULL, SCIP_BOUNDTYPE_LOWER, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_UPWARDS, SCIP_CALL, SCIP_OKAY, SCIPhistoryIncVSIDS(), SCIPsetIsZero(), SCIPvarIncVSIDS(), and SCIP_Stat::vsidsweight.
Referenced by updateStatistics().
◆ updateStatistics()
|
static |
update conflict statistics
- Parameters
-
conflict conflict analysis data vars array of variables blkmem block memory set global SCIP settings stat dynamic problem statistics conflictrow conflict row to add to the tree insertdepth depth level at which the conflict set should be added
Definition at line 1826 of file conflict_resolution.c.
References bound, SCIP_Stat::glbhistory, SCIP_Stat::glbhistorycrun, incVSIDS(), SCIP_ConflictRow::inds, SCIP_Conflict::nappliedglbconss, SCIP_Conflict::nappliedglbliterals, SCIP_Conflict::nappliedlocconss, SCIP_Conflict::nappliedlocliterals, SCIP_ConflictRow::nnz, NULL, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_UPWARDS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPhistoryIncNActiveConflicts(), SCIPsetIsZero(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPvarIncNActiveConflicts(), and SCIP_ConflictRow::vals.
Referenced by createAndAddConflictCon(), and SCIPconflictAddConflictCon().
◆ createAndAddConflictCon()
|
static |
creates a conflict constraint and tries to add it to the storage
- Parameters
-
conflict conflict analysis data blkmem block memory set global SCIP settings stat dynamic problem statistics vars array of variables tree branch and bound tree reopt reoptimization data structure lp current LP data cliquetable clique table data structure conflictrow conflict row 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 1885 of file conflict_resolution.c.
References SCIP_ConflictRow::conflicttype, FALSE, SCIP_ConflictRow::inds, SCIP_ConflictRow::lhs, SCIP_ConflictRow::nnz, SCIP_Conflict::nresconfconss, NULL, SCIP_Tree::path, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddConflict(), SCIPallocBufferArray, SCIPcreateConsLinear(), SCIPdebugCheckConss, SCIPfreeBufferArray, SCIPnodeGetDepth(), SCIPreleaseCons(), SCIPsetInfinity(), SCIPsnprintf(), SCIPupgradeConsLinear(), TRUE, updateStatistics(), SCIP_ConflictRow::usescutoffbound, SCIP_ConflictRow::validdepth, and SCIP_ConflictRow::vals.
Referenced by SCIPconflictAddConflictCon().
◆ SCIPconflictAddConflictCon()
| SCIP_RETCODE SCIPconflictAddConflictCon | ( | 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_EVENTFILTER * | eventfilter, | ||
| SCIP_CLIQUETABLE * | cliquetable, | ||
| SCIP_CONFLICTROW * | conflictrow, | ||
| SCIP_Bool * | success | ||
| ) |
create conflict constraints out of conflict row and add them to the problem
- Parameters
-
conflict conflict analysis data blkmem block memory 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 eventfilter global event filter cliquetable clique table data structure conflictrow conflict row to add to the tree success true if the conflict is added to the problem
Definition at line 1958 of file conflict_resolution.c.
References bound, conflictCalcResMaxsize(), SCIP_ConflictRow::conflictdepth, createAndAddConflictCon(), SCIP_Lp::diving, FALSE, hasRelaxationOnlyVar(), SCIP_ConflictRow::inds, SCIP_ConflictRow::insertdepth, SCIP_ConflictRow::lhs, SCIP_Conflict::nappliedglbresconss, SCIP_ConflictRow::nnz, SCIP_Conflict::nreslongconfs, NULL, SCIP_Tree::path, SCIP_Tree::pathlen, SCIP_ConflictRow::repropdepth, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPnodeAddBoundchg(), SCIPnodeCutoff(), SCIPprobGetVars(), SCIPsetCeil(), SCIPsetDebugMsg, SCIPsetDebugMsgPrint, SCIPsetFloor(), SCIPsetIsFeasGT(), SCIPsetIsGT(), SCIPsetIsLT(), SCIPsetIsZero(), SCIPtreeGetCurrentDepth(), SCIPtreeGetFocusDepth(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarIsIntegral(), SCIP_Lp::strongbranching, TRUE, updateStatistics(), SCIP_ConflictRow::validdepth, and SCIP_ConflictRow::vals.
Referenced by addConflictRows().
◆ conflictRowAddSemiSparseData()
|
static |
adds given data as row to the generalized resolution row
- Parameters
-
resolutionrow generalized resolution row blkmem block memory vals variable coefficients inds variable array nnz size of variable and coefficient array lhs left-hand side of conflict row reverse reverse coefficients
Definition at line 2102 of file conflict_resolution.c.
References BMSallocBlockMemoryArray, BMSreallocBlockMemoryArray, SCIP_ConflictRow::inds, SCIP_ConflictRow::lhs, SCIP_ConflictRow::nnz, NULL, SCIP_ALLOC, SCIP_OKAY, SCIP_ConflictRow::size, and SCIP_ConflictRow::vals.
Referenced by conflictRowFromLpRow(), and reasonRowFromLpRow().
◆ computeScaleReason()
|
static |
compute scale for the reason constraint such that the resolving variable cancels out
- Parameters
-
set global SCIP settings conflictrow conflict row reasonrow reason row residx index of variable to resolve
Definition at line 2165 of file conflict_resolution.c.
References REALABS, SCIP_Real, SCIPsetIsZero(), and SCIP_ConflictRow::vals.
Referenced by rescaleAndResolve().
◆ rescaleAndResolve()
|
static |
compute the resolved conflict row resolvedrow = row1 + scale * row2
- Parameters
-
set global SCIP settings conflict conflict analysis data row1 conflict row row2 reason conflict row resolvedrow resolved conflict row blkmem block memory residx index of variable to resolve success apply resolution
Definition at line 2188 of file conflict_resolution.c.
References BMSreallocBlockMemoryArray, SCIP_ConflictRow::coefquotient, computeScaleReason(), conflictRowReplace(), FALSE, SCIP_ConflictRow::inds, linearCombRows(), MAX, MIN, SCIP_ConflictRow::nnz, SCIP_Conflict::nreslargecoefs, NULL, SCIP_ALLOC, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPsetDebugMsgPrint, SCIPsetInfinity(), SCIPsetIsGE(), SCIPsetIsGT(), SCIPsetIsZero(), SCIP_ConflictRow::size, SCIP_ConflictRow::slack, TRUE, and SCIP_ConflictRow::vals.
Referenced by executeResolutionStep().
◆ reduceReason()
|
static |
reduce the reason constraint
- Parameters
-
set global SCIP settings blkmem block memory of transformed problem vars array of variables nvars number of variables rowtoreduce the row to reduce currbdchginfo current bound change to resolve residx index of variable to resolve fixbounds dense array of fixed bounds fixsides dense array of variables fixed to a bound
Definition at line 2270 of file conflict_resolution.c.
References ComplementedMirLhs(), computeSlack(), isBinaryConflictRow(), MirReduction(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbdchginfoGetIdx(), SCIPdebug, SCIPsetIsZero(), and SCIP_ConflictRow::vals.
Referenced by executeResolutionStep().
◆ reasonRowFromLpRow()
|
static |
reason row from an LP row
- Parameters
-
set global SCIP settings blkmem block memory row row to add reasonrow reason row bdchginfo bound change to resolve
Definition at line 2306 of file conflict_resolution.c.
References conflictRowAddSemiSparseData(), FALSE, SCIP_BdChgInfo::inferencedata, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_UNUSED, SCIPABORT, SCIPbdchginfoGetBoundtype(), SCIPbdchginfoGetVar(), SCIPcolGetVar(), SCIPconshdlrGetName(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIPsetAllocBufferArray, SCIPsetFreeBufferArray, SCIPsetIsInfinity(), SCIPvarGetProbindex(), and TRUE.
Referenced by getReasonRow().
◆ conflictRowFromLpRow()
|
static |
add a row to the conflict row
- Parameters
-
set global SCIP settings blkmem block memory row row to add conflictrow conflict row bdchginfo bound change to resolve
Definition at line 2396 of file conflict_resolution.c.
References conflictRowAddSemiSparseData(), FALSE, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_UNUSED, SCIPABORT, SCIPbdchginfoGetBoundtype(), SCIPbdchginfoGetVar(), SCIPcolGetVar(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIPsetAllocBufferArray, SCIPsetFreeBufferArray, SCIPvarGetProbindex(), and TRUE.
Referenced by getConflictRow().
◆ getReasonRow()
|
static |
get the reason for the given bound change
- Parameters
-
blkmem block memory vars array of variables set global SCIP settings currbdchginfo bound change to resolve reasonrow reason row for the bound change residx index of the bound change to resolve fixbounds dense array of fixed bounds fixsides dense array of variables fixed to a bound success pointer to store whether we could get a linear reason
Definition at line 2479 of file conflict_resolution.c.
References computeSlack(), SCIP_Cons::conshdlr, FALSE, isResolvableBdchg(), SCIP_ConflictRow::lhs, NULL, reasonRowFromLpRow(), SCIP_BOUNDCHGTYPE_CONSINFER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbdchginfoGetChgtype(), SCIPbdchginfoGetIdx(), SCIPbdchginfoGetInferCons(), SCIPbdchginfoGetOldbound(), SCIPbdchginfoGetVar(), SCIPconsCreateRow(), SCIPconshdlrGetName(), SCIPconsIsGlobal(), SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPsetDebugMsgPrint, SCIPsetIsGT(), SCIPsetIsInfinity(), SCIPsetIsLT(), SCIPvarGetProbindex(), SCIP_ConflictRow::slack, TRUE, and SCIP_ConflictRow::vals.
Referenced by conflictAnalyzeResolution(), and executeResolutionStep().
◆ getConflictRow()
|
static |
get the conflict row for the given bound change from the LP row.
- Parameters
-
conflict conflict analysis data blkmem block memory of transformed problem set global SCIP settings prob problem data initialconflictrow row of constraint that detected the conflict currbdchginfo bound change to resolve maxsize maximal size of conflict rows success pointer to store whether we could get a conflict row
Definition at line 2573 of file conflict_resolution.c.
References computeSlack(), SCIP_Conflict::conflictrow, conflictRowFromLpRow(), FALSE, SCIP_ConflictRow::nnz, SCIP_Conflict::nreslongconfs, NULL, SCIP_CALL, SCIP_OKAY, SCIPbdchginfoGetIdx(), SCIProwGetName(), SCIProwGetNNonz(), SCIPsetDebugMsgPrint, SCIPsetIsGE(), SCIPsetIsLT(), SCIP_ConflictRow::slack, TRUE, SCIP_Prob::vars, and weakenConflictRow().
Referenced by conflictAnalyzeResolution().
◆ executeResolutionStep()
|
static |
execute resolution; reduce reason if necessary
- Parameters
-
conflict conflict analysis data set global SCIP settings vars array of variables blkmem block memory of transformed problem currbdchginfo current bound change to resolve residx index of variable to resolve maxsize maximal size of conflict rows fixbounds dense array of fixed bounds fixsides dense array of variables fixed to a bound successresolution pointer to store whether the resolution was successful
Definition at line 2650 of file conflict_resolution.c.
References computeSlack(), SCIP_Conflict::conflictrow, conflictRowClear(), conflictRowReplace(), SCIP_Conflict::continuousbdchgqueue, FALSE, getReasonRow(), isBinaryConflictRow(), SCIP_ConflictRow::nnz, SCIP_Conflict::nreslongconfs, NULL, SCIP_Conflict::reasonrow, SCIP_Conflict::reducedreasonrow, reduceReason(), rescaleAndResolve(), SCIP_Conflict::resolvedconflictrow, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbdchginfoGetIdx(), SCIPbdchginfoGetVar(), SCIPdebug, SCIPgetNVars(), SCIPpqueueNElems(), SCIPpqueueRemove(), SCIPsetDebugMsgPrint, SCIPsetIsGE(), SCIPsetIsLE(), SCIPsetIsLT(), SCIPsetIsZero(), SCIPvarGetName(), SCIPvarGetProbindex(), SCIP_ConflictRow::slack, slackReducingContinuousBdchgQueue(), TRUE, SCIP_ConflictRow::vals, and weakenContinuousVarsConflictRow().
Referenced by conflictAnalyzeResolution().
◆ markBdchgAsFixed()
|
static |
If a bound change cannot be resolved, it is treated as a branching decision. Subsequent bound changes for that variable are ignored by recording the variable's index in fixsides and its bound type in fixbounds (1 for upper, -1 for lower).
- Parameters
-
conflict conflict analysis data set global SCIP settings vars array of variables currbdchginfo pointer to current bound change to resolve currbdchgdepth pointer to store the depth of the bound change nressteps number of bound changes that have been resolved so far fixbounds dense array of fixed bounds fixsides dense array of variables fixed to a bound success pointer to store whether the bound change was ignored
Definition at line 2820 of file conflict_resolution.c.
References computeSlack(), conflictFirstCand(), conflictRemoveCand(), SCIP_Conflict::conflictrow, SCIP_Conflict::conflictvarslbs, SCIP_Conflict::conflictvarsubs, existsResolvablebdchginfo(), FALSE, NULL, SCIP_BOUNDCHGTYPE_BRANCHING, SCIP_BOUNDCHGTYPE_CONSINFER, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_REAL_MAX, SCIP_REAL_MIN, SCIPbdchginfoGetBoundtype(), SCIPbdchginfoGetChgtype(), SCIPbdchginfoGetDepth(), SCIPbdchginfoGetIdx(), SCIPbdchginfoGetInferCons(), SCIPbdchginfoGetNewbound(), SCIPbdchginfoGetVar(), SCIPconsIsGlobal(), SCIPsetDebugMsgPrint, SCIPsetIsLT(), SCIPvarGetName(), SCIPvarGetProbindex(), SCIP_ConflictRow::slack, TRUE, and updateBdchgQueue().
Referenced by conflictAnalyzeResolution().
◆ addConflictRows()
|
static |
add the conflict rows to the problem
- Parameters
-
conflict conflict analysis data blkmem block memory 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 eventfilter global event filter cliquetable clique table data structure nconstoadd number of conflict constraints to add nconss pointer to store the number of generated conflict constraints nconfvars pointer to store the number of variables in generated conflict constraints
Definition at line 2909 of file conflict_resolution.c.
References SCIP_ConflictRow::coefquotient, SCIP_Conflict::conflictrows, SCIP_ConflictRow::nnz, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconflictAddConflictCon(), SCIPsetIsLT(), and SCIP_ConflictRow::slack.
Referenced by conflictAnalyzeResolution().
◆ conflictAnalyzeResolution()
| SCIP_RETCODE conflictAnalyzeResolution | ( | 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_EVENTFILTER * | eventfilter, | ||
| SCIP_CLIQUETABLE * | cliquetable, | ||
| SCIP_ROW * | initialconflictrow, | ||
| int | validdepth, | ||
| int * | nconss, | ||
| int * | nconfvars | ||
| ) |
Analyzes conflicting bound changes added via SCIPconflictAddBound(). This function performs generalized resolution conflict analysis by iteratively aggregating the infeasible conflict row (conflictrow) with the reason row (reasonrow) that propagated the bound change. In each iteration, the coefficient of the resolving variable is cancelled. If the aggregation does not yield an infeasible row, MIR reduction is applied to the reason row and the aggregation is retried, continuing until a first unique implication point (FUIP) is reached. On success, a linear conflict constraint that explains the infeasibility is added to the problem.
- Parameters
-
conflict conflict analysis data blkmem block memory of transformed problem set global SCIP settings stat problem statistics transprob transformed problem origprob original problem tree branch and bound tree reopt reoptimization data structure lp LP data branchcand branching candidate storage eventqueue event queue eventfilter global event filter cliquetable clique table data structure initialconflictrow row of constraint that detected the conflict validdepth minimal depth level at which the initial conflict set is valid nconss pointer to store the number of generated conflict constraints nconfvars pointer to store the number of variables in generated conflict constraints
Definition at line 2961 of file conflict_resolution.c.
References addConflictRows(), SCIP_ConflictRow::coefquotient, computeSlack(), conflictCalcResMaxsize(), SCIP_ConflictRow::conflictdepth, conflictFirstCand(), conflictInsertConflictRow(), conflictRemoveCand(), SCIP_Conflict::conflictrow, conflictRowClear(), conflictRowCopy(), conflictRowRemoveZeroVars(), conflictRowReplace(), SCIP_ConflictRow::conflicttype, SCIP_Conflict::conflictvarslbs, SCIP_Conflict::conflictvarsubs, EPS, executeResolutionStep(), existsResolvablebdchginfo(), FALSE, freeConflictResources(), getConflictRow(), getQuotLargestSmallestCoef(), getReasonRow(), SCIP_ConflictRow::inds, SCIP_ConflictRow::insertdepth, isResolvableBdchg(), SCIP_ConflictRow::lhs, markBdchgAsFixed(), MAX, MIN, SCIP_Conflict::nconflictrows, SCIP_ConflictRow::nnz, SCIP_Conflict::nreslongconfs, NULL, SCIP_Prob::nvars, SCIP_Tree::pathlen, SCIP_Conflict::reasonrow, SCIP_Conflict::reducedreasonrow, SCIP_ConflictRow::repropdepth, SCIP_Conflict::resolvedconflictrow, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIP_REAL_MIN, SCIPbdchginfoGetBoundtype(), SCIPbdchginfoGetDepth(), SCIPbdchginfoGetIdx(), SCIPbdchginfoGetVar(), SCIPdebug, SCIPprobGetVars(), SCIPsetAllocBufferArray, SCIPsetDebugMsgPrint, SCIPsetIsEQ(), SCIPsetIsGE(), SCIPsetIsLE(), SCIPsetIsLT(), SCIPsetIsRelLE(), SCIPsetIsZero(), SCIPtreeGetCurrentDepth(), SCIPtreeGetFocusDepth(), SCIPvarGetName(), SCIPvarGetProbindex(), SCIPvarIsActive(), SCIP_ConflictRow::slack, tightenCoefs(), TRUE, updateBdchgQueue(), SCIP_ConflictRow::validdepth, SCIP_ConflictRow::vals, and weakenConflictRow().
Referenced by SCIPconflictAnalyzeResolution().
◆ SCIPconflictAnalyzeResolution()
| SCIP_RETCODE SCIPconflictAnalyzeResolution | ( | 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_EVENTFILTER * | eventfilter, | ||
| SCIP_CLIQUETABLE * | cliquetable, | ||
| SCIP_ROW * | initialconflictrow, | ||
| int | validdepth, | ||
| SCIP_Bool * | success | ||
| ) |
analyzes conflicting bound changes that were added with calls to SCIPconflictAddBound(), and on success, creates a linear constraint that explains the infeasibility
- Parameters
-
conflict conflict analysis data blkmem block memory of transformed problem set global SCIP settings stat problem statistics transprob transformed problem origprob original problem tree branch and bound tree reopt reoptimization data structure lp LP data branchcand branching candidate storage eventqueue event queue eventfilter global event filter cliquetable clique table data structure initialconflictrow row of constraint that detected the conflict 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 3336 of file conflict_resolution.c.
References SCIP_Conflict::bdchgonlyresqueue, conflictAnalyzeResolution(), SCIP_Conflict::conflictrows, SCIP_Conflict::continuousbdchgqueue, FALSE, SCIP_Conflict::nconflictrows, SCIP_Conflict::nrescalls, SCIP_Conflict::nresconfconss, SCIP_Conflict::nresconfvariables, SCIP_Conflict::nressuccess, NULL, SCIP_Conflict::resanalyzetime, SCIP_Conflict::resbdchgqueue, SCIP_CALL, SCIP_OKAY, SCIPclockStart(), SCIPclockStop(), SCIPconflictResolutionApplicable(), SCIPconflictRowFree(), SCIPpqueueClear(), SCIPsetDebugMsgPrint, SCIPtreeGetCurrentDepth(), and TRUE.
Referenced by SCIPanalyzeConflict(), and SCIPanalyzeConflictCons().