Detailed Description
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(...) |
Macro Definition Documentation
◆ BOUNDSWITCH
#define BOUNDSWITCH 0.51 |
threshold for bound switching - see cuts.c
Definition at line 83 of file conflict_dualproofanalysis.c.
◆ POSTPROCESS
#define POSTPROCESS FALSE |
apply postprocessing to the cut - see cuts.c
Definition at line 84 of file conflict_dualproofanalysis.c.
◆ USEVBDS
#define USEVBDS FALSE |
use variable bounds - see cuts.c
Definition at line 85 of file conflict_dualproofanalysis.c.
◆ ALLOWLOCAL
#define ALLOWLOCAL FALSE |
allow to generate local cuts - see cuts.
Definition at line 86 of file conflict_dualproofanalysis.c.
◆ MINFRAC
#define MINFRAC 0.05 |
minimal fractionality of floor(rhs) - see cuts.c
Definition at line 87 of file conflict_dualproofanalysis.c.
◆ MAXFRAC
#define MAXFRAC 0.999 |
maximal fractionality of floor(rhs) - see cuts.c
Definition at line 88 of file conflict_dualproofanalysis.c.
◆ debugPrintViolationInfo
#define debugPrintViolationInfo | ( | ... | ) |
Definition at line 1236 of file conflict_dualproofanalysis.c.
Function Documentation
◆ varGetChar()
|
static |
return the char associated with the type of the variable
- Parameters
-
var variable
Definition at line 97 of file conflict_dualproofanalysis.c.
References SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPvarGetType(), and SCIPvarIsIntegral().
Referenced by tightenSingleVar().
◆ proofsetClear()
|
static |
resets the data structure of a proofset
- Parameters
-
proofset proof set
Definition at line 110 of file conflict_dualproofanalysis.c.
References SCIP_ProofSet::conflicttype, SCIP_ProofSet::nnz, NULL, SCIP_ProofSet::rhs, SCIP_CONFTYPE_UNKNOWN, and SCIP_ProofSet::validdepth.
Referenced by SCIPconflictFlushProofset(), and tightenDualproof().
◆ proofsetCreate()
|
static |
creates a proofset
- Parameters
-
proofset proof set blkmem block memory of transformed problem
Definition at line 124 of file conflict_dualproofanalysis.c.
References BMSallocBlockMemory, NULL, SCIP_ALLOC, SCIP_CONFTYPE_UNKNOWN, and SCIP_OKAY.
Referenced by SCIPconflictInitProofset(), separateAlternativeProofs(), and tightenDualproof().
◆ SCIPproofsetFree()
void SCIPproofsetFree | ( | SCIP_PROOFSET ** | proofset, |
BMS_BLKMEM * | blkmem | ||
) |
frees a proofset
- Parameters
-
proofset proof set blkmem block memory
Definition at line 144 of file conflict_dualproofanalysis.c.
References BMSfreeBlockMemory, BMSfreeBlockMemoryArrayNull, and NULL.
Referenced by SCIPconflictFlushProofset(), SCIPconflictFree(), separateAlternativeProofs(), and tightenDualproof().
◆ proofsetGetInds()
|
static |
return the indices of variables in the proofset
- Parameters
-
proofset proof set
Definition at line 161 of file conflict_dualproofanalysis.c.
References SCIP_ProofSet::inds, and NULL.
Referenced by createAndAddProofcons(), SCIPconflictFlushProofset(), and tightenDualproof().
◆ proofsetGetVals()
|
static |
return coefficient of variable in the proofset with given probindex
- Parameters
-
proofset proof set
Definition at line 172 of file conflict_dualproofanalysis.c.
References NULL, and SCIP_ProofSet::vals.
Referenced by createAndAddProofcons(), SCIPconflictFlushProofset(), and tightenDualproof().
◆ proofsetGetRhs()
|
static |
return the right-hand side if a proofset
- Parameters
-
proofset proof set
Definition at line 183 of file conflict_dualproofanalysis.c.
References NULL, and SCIP_ProofSet::rhs.
Referenced by createAndAddProofcons(), SCIPconflictFlushProofset(), and tightenCoefficients().
◆ SCIPproofsetGetNVars()
int SCIPproofsetGetNVars | ( | SCIP_PROOFSET * | proofset | ) |
returns the number of variables in the proofset
- Parameters
-
proofset proof set
Definition at line 193 of file conflict_dualproofanalysis.c.
References SCIP_ProofSet::nnz, and NULL.
Referenced by conflictAnalyzeLP(), createAndAddProofcons(), SCIPconflictFlushProofset(), tightenCoefficients(), and tightenDualproof().
◆ proofsetGetConftype()
|
static |
returns the number of variables in the proofset
- Parameters
-
proofset proof set
Definition at line 204 of file conflict_dualproofanalysis.c.
References SCIP_ProofSet::conflicttype, and NULL.
Referenced by createAndAddProofcons(), and SCIPconflictFlushProofset().
◆ proofsetAddSparseData()
|
static |
adds given data as aggregation row to the proofset
- Parameters
-
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 BMSduplicateBlockMemoryArray, BMSreallocBlockMemoryArray, SCIP_ProofSet::inds, SCIP_ProofSet::nnz, NULL, SCIP_ProofSet::rhs, SCIP_ALLOC, SCIP_OKAY, SCIP_ProofSet::size, and SCIP_ProofSet::vals.
Referenced by proofsetAddAggrrow(), and separateAlternativeProofs().
◆ proofsetAddAggrrow()
|
static |
adds an aggregation row to the proofset
- Parameters
-
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 NULL, proofsetAddSparseData(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaggrRowGetInds(), SCIPaggrRowGetNNz(), SCIPaggrRowGetProbvarValue(), SCIPaggrRowGetRhs(), SCIPsetAllocBufferArray, and SCIPsetFreeBufferArray.
Referenced by tightenDualproof().
◆ proofsetCancelVarWithBound()
|
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.
- Note
- : The list of non-zero indices and coefficients will be updated by swapping the last non-zero index to
pos
.
Definition at line 307 of file conflict_dualproofanalysis.c.
References FALSE, SCIP_ProofSet::inds, SCIP_ProofSet::nnz, NULL, SCIP_ProofSet::rhs, SCIPsetIsInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), TRUE, and SCIP_ProofSet::vals.
Referenced by tightenDualproof().
◆ SCIPconflictInitProofset()
SCIP_RETCODE SCIPconflictInitProofset | ( | SCIP_CONFLICT * | conflict, |
BMS_BLKMEM * | blkmem | ||
) |
creates and clears the proofset
- Parameters
-
conflict conflict analysis data blkmem block memory of transformed problem
Definition at line 346 of file conflict_dualproofanalysis.c.
References NULL, SCIP_Conflict::proofset, proofsetCreate(), SCIP_CALL, and SCIP_OKAY.
Referenced by SCIPconflictCreate().
◆ conflictEnsureProofsetsMem()
|
static |
resizes proofsets 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 361 of file conflict_dualproofanalysis.c.
References BMSreallocMemoryArray, NULL, SCIP_Conflict::proofsets, SCIP_Conflict::proofsetssize, SCIP_ALLOC, SCIP_OKAY, and SCIPsetCalcMemGrowSize().
Referenced by conflictInsertProofset().
◆ conflictInsertProofset()
|
static |
add a proofset to the list of all proofsets
- Parameters
-
conflict conflict analysis data set global SCIP settings proofset proof set to add
Definition at line 385 of file conflict_dualproofanalysis.c.
References conflictEnsureProofsetsMem(), SCIP_Conflict::nproofsets, NULL, SCIP_Conflict::proofsets, SCIP_CALL, and SCIP_OKAY.
Referenced by separateAlternativeProofs(), and tightenDualproof().
◆ tightenSingleVar()
|
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.
- Parameters
-
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 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, and varGetChar().
Referenced by propagateLongProof(), and SCIPconflictFlushProofset().
◆ getMinActivity()
|
static |
calculates the minimal activity of a given set of bounds and coefficients
- Parameters
-
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 NULL, QUAD, QUAD_ASSIGN, QUAD_TO_DBL, SCIP_Real, SCIPprobGetVars(), SCIPquadprecProdDD, SCIPquadprecSumQQ, SCIPsetInfinity(), SCIPsetIsInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetProbindex(), and SCIPvarGetUbGlobal().
Referenced by createAndAddProofcons(), and propagateLongProof().
◆ getMaxActivity()
|
static |
calculates the minimal activity of a given set of bounds and coefficients
- Parameters
-
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 NULL, QUAD, QUAD_ASSIGN, QUAD_TO_DBL, SCIP_Real, SCIPprobGetVars(), SCIPquadprecProdDD, SCIPquadprecSumQQ, SCIPsetInfinity(), SCIPsetIsInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetProbindex(), and SCIPvarGetUbGlobal().
Referenced by createAndAddProofcons(), and tightenDualproof().
◆ propagateLongProof()
|
static |
propagate a long proof
- Parameters
-
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 getMinActivity(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPprobGetVars(), SCIPsetIsEQ(), SCIPsetIsGE(), SCIPsetIsInfinity(), SCIPsetIsLE(), SCIPsetIsZero(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and tightenSingleVar().
Referenced by createAndAddProofcons().
◆ createAndAddProofcons()
|
static |
creates a proof constraint and tries to add it to the storage
- Parameters
-
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 SCIP_Stat::avgnnz, SCIP_Conflict::dualproofsbndnnonzeros, SCIP_Conflict::dualproofsinfnnonzeros, FALSE, getMaxActivity(), getMinActivity(), 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, and SCIP_ProofSet::validdepth.
Referenced by SCIPconflictFlushProofset().
◆ 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
- Parameters
-
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 SCIP_ProofSet::conflicttype, createAndAddProofcons(), FALSE, 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, and SCIP_ProofSet::validdepth.
Referenced by conflictAnalyzeLP().
◆ tightenCoefficients()
|
static |
apply coefficient tightening
- Parameters
-
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, SCIP_ProofSet::inds, MAX, MIN, SCIP_ProofSet::nnz, proofsetGetRhs(), REALABS, SCIP_ProofSet::rhs, SCIP_Real, SCIPcutsTightenCoefficients(), SCIPproofsetGetNVars(), SCIPsetDebugMsg, SCIPsetInfinity(), and SCIP_ProofSet::vals.
Referenced by separateAlternativeProofs(), and tightenDualproof().
◆ separateAlternativeProofs()
|
static |
try to generate alternative proofs by applying subadditive functions
- Parameters
-
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, MAX, MAXFRAC, MINFRAC, NULL, 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(), and USEVBDS.
Referenced by tightenDualproof().
◆ tightenDualproof()
|
static |
tighten a given infeasibility proof a^Tx <= b with minact > b w.r.t. local bounds
1) Apply cut generating functions
- c-MIR
- Flow-cover
- TODO: implement other subadditive functions 2) Remove continuous variables contributing with its global bound
- TODO: implement a variant of non-zero-cancellation
- Parameters
-
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 conflictInsertProofset(), SCIP_Conflict::conflictset, SCIP_ConflictSet::conflicttype, SCIP_ProofSet::conflicttype, debugPrintViolationInfo, eps, getMaxActivity(), SCIP_ProofSet::inds, MIN, 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(), SCIP_ProofSet::validdepth, and SCIP_ProofSet::vals.
Referenced by SCIPconflictAnalyzeDualProof().
◆ 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.
- Parameters
-
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 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().