internal methods for dual proof conflict analysis
In dual proof analysis, an infeasible LP relaxation is analysed. Using the dual solution, a valid constraint is derived that is violated by all values in the domain. This constraint is added to the problem and can then be used for domain propagation. More details can be found in [1]
[1] J. Witzig, T. Berthold, en S. Heinz, ‘Computational aspects of infeasibility analysis in mixed integer programming’, Math. Prog. Comp., mrt. 2021, doi: 10.1007/s12532-021-00202-0.
Definition in file conflict_dualproofanalysis.c.
#include "lpi/lpi.h"
#include "scip/clock.h"
#include "scip/conflict_general.h"
#include "scip/conflict_dualproofanalysis.h"
#include "scip/conflictstore.h"
#include "scip/cons.h"
#include "scip/cons_linear.h"
#include "scip/cuts.h"
#include "scip/history.h"
#include "scip/lp.h"
#include "scip/presolve.h"
#include "scip/prob.h"
#include "scip/prop.h"
#include "scip/pub_conflict.h"
#include "scip/pub_cons.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_paramset.h"
#include "scip/pub_prop.h"
#include "scip/pub_tree.h"
#include "scip/pub_var.h"
#include "scip/scip_conflict.h"
#include "scip/scip_cons.h"
#include "scip/scip_mem.h"
#include "scip/scip_sol.h"
#include "scip/scip_var.h"
#include "scip/set.h"
#include "scip/sol.h"
#include "scip/struct_conflict.h"
#include "scip/struct_lp.h"
#include "scip/struct_prob.h"
#include "scip/struct_set.h"
#include "scip/struct_stat.h"
#include "scip/struct_tree.h"
#include "scip/struct_var.h"
#include "scip/tree.h"
#include "scip/var.h"
#include "scip/visual.h"
Go to the source code of this file.
Macros | |
#define | BOUNDSWITCH 0.51 |
#define | POSTPROCESS FALSE |
#define | USEVBDS FALSE |
#define | ALLOWLOCAL FALSE |
#define | MINFRAC 0.05 |
#define | MAXFRAC 0.999 |
#define | debugPrintViolationInfo(...) |
#define BOUNDSWITCH 0.51 |
threshold for bound switching - see cuts.c
Definition at line 83 of file conflict_dualproofanalysis.c.
Referenced by aggregation(), buildMod2Matrix(), createCGCutCMIR(), createCGCutStrongCG(), generateClusterCuts(), generateGMICuts(), generateZerohalfCut(), SCIP_DECL_SEPAEXECLP(), and separateAlternativeProofs().
#define POSTPROCESS FALSE |
apply postprocessing to the cut - see cuts.c
Definition at line 84 of file conflict_dualproofanalysis.c.
Referenced by aggregation(), createCGCutCMIR(), createCGCutStrongCG(), generateClusterCuts(), generateGMICuts(), SCIP_DECL_SEPAEXECLP(), and separateAlternativeProofs().
#define USEVBDS FALSE |
use variable bounds - see cuts.c
Definition at line 85 of file conflict_dualproofanalysis.c.
Referenced by aggregation(), createCGCutCMIR(), createCGCutStrongCG(), generateClusterCuts(), generateGMICuts(), SCIP_DECL_SEPAEXECLP(), and separateAlternativeProofs().
#define ALLOWLOCAL FALSE |
allow to generate local cuts - see cuts.
Definition at line 86 of file conflict_dualproofanalysis.c.
Referenced by separateAlternativeProofs().
#define MINFRAC 0.05 |
minimal fractionality of floor(rhs) - see cuts.c
Definition at line 87 of file conflict_dualproofanalysis.c.
Referenced by aggregation(), createCGCutCMIR(), createCGCutStrongCG(), generateClusterCuts(), and separateAlternativeProofs().
#define MAXFRAC 0.999 |
maximal fractionality of floor(rhs) - see cuts.c
Definition at line 88 of file conflict_dualproofanalysis.c.
Referenced by aggregation(), createCGCutCMIR(), createCGCutStrongCG(), generateClusterCuts(), and separateAlternativeProofs().
#define debugPrintViolationInfo | ( | ... | ) |
Definition at line 1236 of file conflict_dualproofanalysis.c.
Referenced by tightenDualproof().
|
static |
return the char associated with the type of the variable
var | variable |
Definition at line 97 of file conflict_dualproofanalysis.c.
References SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPvarGetType(), SCIPvarIsIntegral(), and var.
Referenced by tightenSingleVar().
|
static |
resets the data structure of a proofset
proofset | proof set |
Definition at line 110 of file conflict_dualproofanalysis.c.
References assert(), SCIP_ProofSet::conflicttype, SCIP_ProofSet::nnz, NULL, SCIP_ProofSet::rhs, SCIP_CONFTYPE_UNKNOWN, and SCIP_ProofSet::validdepth.
Referenced by SCIPconflictFlushProofset(), and tightenDualproof().
|
static |
creates a proofset
proofset | proof set |
blkmem | block memory of transformed problem |
Definition at line 124 of file conflict_dualproofanalysis.c.
References assert(), BMSallocBlockMemory, NULL, SCIP_ALLOC, SCIP_CONFTYPE_UNKNOWN, and SCIP_OKAY.
Referenced by SCIPconflictInitProofset(), separateAlternativeProofs(), and tightenDualproof().
void SCIPproofsetFree | ( | SCIP_PROOFSET ** | proofset, |
BMS_BLKMEM * | blkmem ) |
frees a proofset
proofset | proof set |
blkmem | block memory |
Definition at line 144 of file conflict_dualproofanalysis.c.
References assert(), BMSfreeBlockMemory, BMSfreeBlockMemoryArrayNull, and NULL.
Referenced by SCIPconflictFlushProofset(), SCIPconflictFree(), separateAlternativeProofs(), and tightenDualproof().
|
static |
return the indices of variables in the proofset
proofset | proof set |
Definition at line 161 of file conflict_dualproofanalysis.c.
References assert(), SCIP_ProofSet::inds, and NULL.
Referenced by createAndAddProofcons(), SCIPconflictFlushProofset(), and tightenDualproof().
|
static |
return coefficient of variable in the proofset with given probindex
proofset | proof set |
Definition at line 172 of file conflict_dualproofanalysis.c.
References assert(), NULL, SCIP_Real, and SCIP_ProofSet::vals.
Referenced by createAndAddProofcons(), SCIPconflictFlushProofset(), and tightenDualproof().
|
static |
return the right-hand side if a proofset
proofset | proof set |
Definition at line 183 of file conflict_dualproofanalysis.c.
References assert(), NULL, SCIP_ProofSet::rhs, and SCIP_Real.
Referenced by createAndAddProofcons(), SCIPconflictFlushProofset(), and tightenCoefficients().
int SCIPproofsetGetNVars | ( | SCIP_PROOFSET * | proofset | ) |
returns the number of variables in the proofset
proofset | proof set |
Definition at line 193 of file conflict_dualproofanalysis.c.
References assert(), SCIP_ProofSet::nnz, and NULL.
Referenced by conflictAnalyzeLP(), createAndAddProofcons(), SCIPconflictFlushProofset(), tightenCoefficients(), and tightenDualproof().
|
static |
returns the number of variables in the proofset
proofset | proof set |
Definition at line 204 of file conflict_dualproofanalysis.c.
References assert(), SCIP_ProofSet::conflicttype, and NULL.
Referenced by createAndAddProofcons(), and SCIPconflictFlushProofset().
|
static |
adds given data as aggregation row to the proofset
proofset | proof set |
blkmem | block memory |
vals | variable coefficients |
inds | variable array |
nnz | size of variable and coefficient array |
rhs | right-hand side of the aggregation row |
Definition at line 215 of file conflict_dualproofanalysis.c.
References assert(), BMSduplicateBlockMemoryArray, BMSreallocBlockMemoryArray, i, SCIP_ProofSet::inds, SCIP_ProofSet::nnz, NULL, SCIP_ProofSet::rhs, SCIP_ALLOC, SCIP_OKAY, SCIP_Real, SCIP_ProofSet::size, and SCIP_ProofSet::vals.
Referenced by proofsetAddAggrrow(), and separateAlternativeProofs().
|
static |
adds an aggregation row to the proofset
proofset | proof set |
set | global SCIP settings |
blkmem | block memory |
aggrrow | aggregation row to add |
Definition at line 266 of file conflict_dualproofanalysis.c.
References assert(), i, NULL, proofsetAddSparseData(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaggrRowGetInds(), SCIPaggrRowGetNNz(), SCIPaggrRowGetProbvarValue(), SCIPaggrRowGetRhs(), SCIPsetAllocBufferArray, and SCIPsetFreeBufferArray.
Referenced by tightenDualproof().
|
static |
Removes a given variable var
from position pos
from the proofset and updates the right-hand side according to sign of the coefficient, i.e., rhs -= coef * bound, where bound = lb if coef >= 0 and bound = ub, otherwise.
pos
. Definition at line 307 of file conflict_dualproofanalysis.c.
References assert(), FALSE, SCIP_ProofSet::inds, SCIP_ProofSet::nnz, NULL, SCIP_ProofSet::rhs, SCIP_Bool, SCIPsetIsInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), TRUE, valid, SCIP_ProofSet::vals, and var.
Referenced by tightenDualproof().
SCIP_RETCODE SCIPconflictInitProofset | ( | SCIP_CONFLICT * | conflict, |
BMS_BLKMEM * | blkmem ) |
creates and clears the proofset
conflict | conflict analysis data |
blkmem | block memory of transformed problem |
Definition at line 346 of file conflict_dualproofanalysis.c.
References assert(), NULL, SCIP_Conflict::proofset, proofsetCreate(), SCIP_CALL, and SCIP_OKAY.
Referenced by SCIPconflictCreate().
|
static |
resizes proofsets array to be able to store at least num entries
conflict | conflict analysis data |
set | global SCIP settings |
num | minimal number of slots in array |
Definition at line 361 of file conflict_dualproofanalysis.c.
References assert(), BMSreallocMemoryArray, NULL, SCIP_Conflict::proofsets, SCIP_Conflict::proofsetssize, SCIP_ALLOC, SCIP_OKAY, and SCIPsetCalcMemGrowSize().
Referenced by conflictInsertProofset().
|
static |
add a proofset to the list of all proofsets
conflict | conflict analysis data |
set | global SCIP settings |
proofset | proof set to add |
Definition at line 385 of file conflict_dualproofanalysis.c.
References assert(), conflictEnsureProofsetsMem(), SCIP_Conflict::nproofsets, NULL, SCIP_Conflict::proofsets, SCIP_CALL, and SCIP_OKAY.
Referenced by separateAlternativeProofs(), and tightenDualproof().
|
static |
tighten the bound of a singleton variable in a constraint
if the bound is contradicting with a global bound we cannot tighten the bound directly. in this case we need to create and add a constraint of size one such that propagating this constraint will enforce the infeasibility.
conflict | conflict analysis data |
set | global SCIP settings |
stat | dynamic SCIP statistics |
tree | tree data |
blkmem | block memory |
origprob | original problem |
transprob | transformed problem |
reopt | reoptimization data |
lp | LP data |
branchcand | branching candidates |
eventqueue | event queue |
cliquetable | clique table |
var | problem variable |
val | coefficient of the variable |
rhs | rhs of the constraint |
prooftype | type of the proof |
validdepth | depth where the bound change is valid |
Definition at line 410 of file conflict_dualproofanalysis.c.
References assert(), SCIP_Conflict::dualproofsbndnnonzeros, SCIP_Conflict::dualproofsinfnnonzeros, FALSE, SCIP_Conflict::nboundlpsuccess, SCIP_Conflict::ndualproofsbndglobal, SCIP_Conflict::ndualproofsbndlocal, SCIP_Conflict::ndualproofsbndsuccess, SCIP_Conflict::ndualproofsinfglobal, SCIP_Conflict::ndualproofsinflocal, SCIP_Conflict::ndualproofsinfsuccess, SCIP_Conflict::nglbchgbds, SCIP_Conflict::ninflpsuccess, SCIP_Conflict::nlocchgbds, NULL, SCIP_Tree::path, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_CONFTYPE_ALTINFPROOF, SCIP_CONFTYPE_INFEASLP, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPconsRelease(), SCIPcreateConsLinear(), SCIPnodeAddBoundchg(), SCIPnodeAddCons(), SCIPnodeCutoff(), SCIPnodeGetNumber(), SCIPnodePropagateAgain(), SCIPprobAddCons(), SCIPsetDebugMsg, SCIPsetFeasFloor(), SCIPsetInfinity(), SCIPsetIsGE(), SCIPsetIsGT(), SCIPsetIsIntegral(), SCIPsetIsLE(), SCIPsetIsLT(), SCIPsnprintf(), SCIPtreeGetEffectiveRootDepth(), SCIPvarAdjustBd(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), SCIP_Lp::strongbranching, TRUE, var, and varGetChar().
Referenced by propagateLongProof(), and SCIPconflictFlushProofset().
|
static |
calculates the minimal activity of a given set of bounds and coefficients
set | global SCIP settings |
transprob | transformed problem data |
coefs | coefficients in sparse representation |
inds | non-zero indices |
nnz | number of non-zero indices |
curvarlbs | current lower bounds of active problem variables (or NULL for global bounds) |
curvarubs | current upper bounds of active problem variables (or NULL for global bounds) |
Definition at line 560 of file conflict_dualproofanalysis.c.
References assert(), i, NULL, QUAD, QUAD_ASSIGN, QUAD_TO_DBL, SCIP_Real, SCIPprobGetVars(), SCIPquadprecProdDD, SCIPquadprecSumQQ, SCIPsetInfinity(), SCIPsetIsInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), and vars.
Referenced by createAndAddProofcons(), and propagateLongProof().
|
static |
calculates the minimal activity of a given set of bounds and coefficients
set | global SCIP settings |
transprob | transformed problem data |
coefs | coefficients in sparse representation |
inds | non-zero indices |
nnz | number of non-zero indices |
curvarlbs | current lower bounds of active problem variables (or NULL for global bounds) |
curvarubs | current upper bounds of active problem variables (or NULL for global bounds) |
Definition at line 634 of file conflict_dualproofanalysis.c.
References assert(), i, NULL, QUAD, QUAD_ASSIGN, QUAD_TO_DBL, SCIP_Real, SCIPprobGetVars(), SCIPquadprecProdDD, SCIPquadprecSumQQ, SCIPsetInfinity(), SCIPsetIsInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), and vars.
Referenced by createAndAddProofcons(), and tightenDualproof().
|
static |
propagate a long proof
conflict | conflict analysis data |
set | global SCIP settings |
stat | dynamic SCIP statistics |
reopt | reoptimization data |
tree | tree data |
blkmem | block memory |
origprob | original problem |
transprob | transformed problem |
lp | LP data |
branchcand | branching candidate storage |
eventqueue | event queue |
cliquetable | clique table data structure |
coefs | coefficients in sparse representation |
inds | non-zero indices |
nnz | number of non-zero indices |
rhs | right-hand side |
conflicttype | type of the conflict |
validdepth | depth where the proof is valid |
Definition at line 708 of file conflict_dualproofanalysis.c.
References assert(), getMinActivity(), i, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPprobGetVars(), SCIPsetIsEQ(), SCIPsetIsGE(), SCIPsetIsInfinity(), SCIPsetIsLE(), SCIPsetIsZero(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), tightenSingleVar(), var, and vars.
Referenced by createAndAddProofcons().
|
static |
creates a proof constraint and tries to add it to the storage
conflict | conflict analysis data |
conflictstore | conflict pool data |
proofset | proof set |
set | global SCIP settings |
stat | dynamic SCIP statistics |
origprob | original problem |
transprob | transformed problem |
tree | tree data |
reopt | reoptimization data |
lp | LP data |
branchcand | branching candidate storage |
eventqueue | event queue |
cliquetable | clique table data structure |
blkmem | block memory |
Definition at line 811 of file conflict_dualproofanalysis.c.
References assert(), SCIP_Stat::avgnnz, SCIP_Conflict::dualproofsbndnnonzeros, SCIP_Conflict::dualproofsinfnnonzeros, FALSE, getMaxActivity(), getMinActivity(), i, MIN, SCIP_Conflict::ndualproofsbndglobal, SCIP_Conflict::ndualproofsbndlocal, SCIP_Conflict::ndualproofsbndsuccess, SCIP_Conflict::ndualproofsinfglobal, SCIP_Conflict::ndualproofsinflocal, SCIP_Conflict::ndualproofsinfsuccess, NULL, SCIP_Prob::nvars, SCIP_Tree::path, proofsetGetConftype(), proofsetGetInds(), proofsetGetRhs(), proofsetGetVals(), propagateLongProof(), SCIP_Bool, SCIP_CALL, SCIP_CONFTYPE_ALTBNDPROOF, SCIP_CONFTYPE_ALTINFPROOF, SCIP_CONFTYPE_BNDEXCEEDING, SCIP_CONFTYPE_INFEASLP, SCIP_INVALIDCALL, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPconflictstoreAddDualraycons(), SCIPconflictstoreAddDualsolcons(), SCIPconflictstoreGetAvgNnzDualBndProofs(), SCIPconflictstoreGetAvgNnzDualInfProofs(), SCIPconflictstoreGetNDualBndProofs(), SCIPconflictstoreGetNDualInfProofs(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPconsMarkConflict(), SCIPcreateConsLinear(), SCIPgetLhsLinear(), SCIPgetRhsLinear(), SCIPnodeAddCons(), SCIPnodeCutoff(), SCIPnodeGetNumber(), SCIPprobAddCons(), SCIPprobGetVars(), SCIPproofsetGetNVars(), SCIPreleaseCons(), SCIPsetDebugMsg, SCIPsetInfinity(), SCIPsetIsGT(), SCIPsetIsInfinity(), SCIPsetIsLE(), SCIPsetIsNegative(), SCIPsetIsPositive(), SCIPsetIsZero(), SCIPsnprintf(), SCIPtreeGetEffectiveRootDepth(), SCIPtreeGetFocusDepth(), SCIPupgradeConsLinear(), SCIPvarIsIntegral(), SCIPvarIsRelaxationOnly(), SCIP_Prob::startnconss, TRUE, SCIP_ProofSet::validdepth, and vars.
Referenced by SCIPconflictFlushProofset().
SCIP_RETCODE SCIPconflictFlushProofset | ( | SCIP_CONFLICT * | conflict, |
SCIP_CONFLICTSTORE * | conflictstore, | ||
BMS_BLKMEM * | blkmem, | ||
SCIP_SET * | set, | ||
SCIP_STAT * | stat, | ||
SCIP_PROB * | transprob, | ||
SCIP_PROB * | origprob, | ||
SCIP_TREE * | tree, | ||
SCIP_REOPT * | reopt, | ||
SCIP_LP * | lp, | ||
SCIP_BRANCHCAND * | branchcand, | ||
SCIP_EVENTQUEUE * | eventqueue, | ||
SCIP_CLIQUETABLE * | cliquetable ) |
create proof constraints out of proof sets
conflict | conflict analysis data |
conflictstore | conflict store |
blkmem | block memory |
set | global SCIP settings |
stat | dynamic problem statistics |
transprob | transformed problem after presolve |
origprob | original problem |
tree | branch and bound tree |
reopt | reoptimization data structure |
lp | current LP data |
branchcand | branching candidate storage |
eventqueue | event queue |
cliquetable | clique table data structure |
Definition at line 1104 of file conflict_dualproofanalysis.c.
References assert(), SCIP_ProofSet::conflicttype, createAndAddProofcons(), FALSE, i, SCIP_Conflict::nproofsets, NULL, SCIP_Conflict::proofset, proofsetClear(), proofsetGetConftype(), proofsetGetInds(), proofsetGetRhs(), proofsetGetVals(), SCIP_Conflict::proofsets, SCIP_Bool, SCIP_CALL, SCIP_CONFTYPE_BNDEXCEEDING, SCIP_CONFTYPE_INFEASLP, SCIP_CONFTYPE_UNKNOWN, SCIP_OKAY, SCIP_Real, SCIPprobGetVars(), SCIPproofsetFree(), SCIPproofsetGetNVars(), tightenSingleVar(), TRUE, SCIP_ProofSet::validdepth, and vars.
Referenced by conflictAnalyzeLP().
|
static |
apply coefficient tightening
set | global SCIP settings |
proofset | proof set |
nchgcoefs | pointer to store number of changed coefficients |
redundant | pointer to store whether the proof set is redundant |
Definition at line 1241 of file conflict_dualproofanalysis.c.
References FALSE, i, SCIP_ProofSet::inds, MAX, MIN, SCIP_ProofSet::nnz, proofsetGetRhs(), REALABS, SCIP_ProofSet::rhs, SCIP_Bool, SCIP_Real, SCIPcutsTightenCoefficients(), SCIPproofsetGetNVars(), SCIPsetDebugMsg, SCIPsetInfinity(), and SCIP_ProofSet::vals.
Referenced by separateAlternativeProofs(), and tightenDualproof().
|
static |
try to generate alternative proofs by applying subadditive functions
conflict | conflict analysis data |
set | global SCIP settings |
stat | dynamic SCIP statistics |
transprob | transformed problem |
tree | tree data |
blkmem | block memory |
proofrow | proof rows data |
curvarlbs | current lower bounds of active problem variables |
curvarubs | current upper bounds of active problem variables |
conflicttype | type of the conflict |
Definition at line 1283 of file conflict_dualproofanalysis.c.
References ALLOWLOCAL, BOUNDSWITCH, conflictInsertProofset(), SCIP_ProofSet::conflicttype, i, MAX, MAXFRAC, MINFRAC, NULL, nvars, POSTPROCESS, proofsetAddSparseData(), proofsetCreate(), SCIP_Bool, SCIP_CALL, SCIP_CONFTYPE_ALTBNDPROOF, SCIP_CONFTYPE_ALTINFPROOF, SCIP_CONFTYPE_INFEASLP, SCIP_OKAY, SCIP_Real, SCIPaggrRowCalcEfficacyNorm(), SCIPaggrRowGetInds(), SCIPaggrRowGetMinActivity(), SCIPaggrRowGetNNz(), SCIPaggrRowGetProbvarValue(), SCIPaggrRowGetRhs(), SCIPcalcFlowCover(), SCIPcreateSol(), SCIPcutGenerationHeuristicCMIR(), SCIPfreeSol(), SCIPprobGetNVars(), SCIPprobGetVars(), SCIPproofsetFree(), SCIPsetAllocBufferArray, SCIPsetFreeBufferArray, SCIPsetInfinity(), SCIPsetIsPositive(), SCIPsolSetVal(), SCIPvarGetAvgSol(), tightenCoefficients(), USEVBDS, and vars.
Referenced by tightenDualproof().
|
static |
tighten a given infeasibility proof a^Tx <= b with minact > b w.r.t. local bounds
1) Apply cut generating functions
conflict | conflict analysis data |
set | global SCIP settings |
stat | dynamic SCIP statistics |
blkmem | block memory |
transprob | transformed problem |
tree | tree data |
proofrow | aggregated row representing the proof |
validdepth | depth where the proof is valid |
curvarlbs | current lower bounds of active problem variables |
curvarubs | current upper bounds of active problem variables |
initialproof | do we analyze the initial reason of infeasibility? |
Definition at line 1414 of file conflict_dualproofanalysis.c.
References assert(), conflictInsertProofset(), SCIP_Conflict::conflictset, SCIP_ConflictSet::conflicttype, SCIP_ProofSet::conflicttype, debugPrintViolationInfo, eps, getMaxActivity(), i, SCIP_ProofSet::inds, MIN, nbinvars, nintvars, SCIP_ProofSet::nnz, NULL, SCIP_Conflict::proofset, proofsetAddAggrrow(), proofsetCancelVarWithBound(), proofsetClear(), proofsetCreate(), proofsetGetInds(), proofsetGetVals(), SCIP_ProofSet::rhs, SCIP_Bool, SCIP_CALL, SCIP_CONFTYPE_ALTBNDPROOF, SCIP_CONFTYPE_ALTINFPROOF, SCIP_CONFTYPE_BNDEXCEEDING, SCIP_CONFTYPE_INFEASLP, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIPaggrRowGetInds(), SCIPaggrRowGetMinActivity(), SCIPaggrRowGetNNz(), SCIPaggrRowGetRhs(), SCIPprobGetVars(), SCIPproofsetFree(), SCIPproofsetGetNVars(), SCIPsetDebugMsg, SCIPsetIsEQ(), SCIPsetIsInfinity(), SCIPsetIsZero(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), SCIPvarIsIntegral(), separateAlternativeProofs(), tightenCoefficients(), valid, SCIP_ProofSet::validdepth, SCIP_ProofSet::vals, and vars.
Referenced by SCIPconflictAnalyzeDualProof().
SCIP_RETCODE SCIPconflictAnalyzeDualProof | ( | SCIP_CONFLICT * | conflict, |
SCIP_SET * | set, | ||
SCIP_STAT * | stat, | ||
BMS_BLKMEM * | blkmem, | ||
SCIP_PROB * | origprob, | ||
SCIP_PROB * | transprob, | ||
SCIP_TREE * | tree, | ||
SCIP_REOPT * | reopt, | ||
SCIP_LP * | lp, | ||
SCIP_AGGRROW * | proofrow, | ||
int | validdepth, | ||
SCIP_Real * | curvarlbs, | ||
SCIP_Real * | curvarubs, | ||
SCIP_Bool | initialproof, | ||
SCIP_Bool * | globalinfeasible, | ||
SCIP_Bool * | success ) |
perform conflict analysis based on a dual unbounded ray
given an aggregation of rows lhs <= a^Tx such that lhs > maxactivity. if the constraint has size one we add a bound change instead of the constraint.
conflict | conflict analysis data |
set | global SCIP settings |
stat | dynamic SCIP statistics |
blkmem | block memory |
origprob | original problem |
transprob | transformed problem |
tree | tree data |
reopt | reoptimization data |
lp | LP data |
proofrow | aggregated row representing the proof |
validdepth | valid depth of the dual proof |
curvarlbs | current lower bounds of active problem variables |
curvarubs | current upper bounds of active problem variables |
initialproof | do we analyze the initial reason of infeasibility? |
globalinfeasible | pointer to store whether global infeasibility could be proven |
success | pointer to store success result |
Definition at line 1605 of file conflict_dualproofanalysis.c.
References assert(), FALSE, SCIP_Conflict::ndualproofsinfsuccess, NULL, SCIP_Tree::path, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaggrRowGetMinActivity(), SCIPaggrRowGetNNz(), SCIPaggrRowGetRhs(), SCIPnodeCutoff(), SCIPsetDebugMsg, SCIPsetIsFeasLE(), SCIPtreeGetFocusDepth(), tightenDualproof(), and TRUE.
Referenced by conflictAnalyzeLP(), and SCIPrunBoundHeuristic().