SCIP
Solving Constraint Integer Programs
conflict_dualproofanalysis.c File Reference
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/certificate.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/cons_exactlinear.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_certificate.h"#include "scip/scip_conflict.h"#include "scip/scip_cons.h"#include "scip/scip_exact.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/struct_certificate.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 | VARTYPEUSEVBDS 0 |
| #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 89 of file conflict_dualproofanalysis.c.
◆ POSTPROCESS
| #define POSTPROCESS FALSE |
apply postprocessing to the cut - see cuts.c
Definition at line 90 of file conflict_dualproofanalysis.c.
◆ VARTYPEUSEVBDS
| #define VARTYPEUSEVBDS 0 |
We do not allow variable bound substitution - see cuts.c for more information.
Definition at line 91 of file conflict_dualproofanalysis.c.
◆ ALLOWLOCAL
| #define ALLOWLOCAL FALSE |
allow to generate local cuts - see cuts.
Definition at line 92 of file conflict_dualproofanalysis.c.
◆ MINFRAC
| #define MINFRAC 0.05 |
minimal fractionality of floor(rhs) - see cuts.c
Definition at line 93 of file conflict_dualproofanalysis.c.
◆ MAXFRAC
| #define MAXFRAC 0.999 |
maximal fractionality of floor(rhs) - see cuts.c
Definition at line 94 of file conflict_dualproofanalysis.c.
◆ debugPrintViolationInfo
| #define debugPrintViolationInfo | ( | ... | ) |
Definition at line 1308 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 103 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 116 of file conflict_dualproofanalysis.c.
References SCIP_ProofSet::certificateline, SCIP_ProofSet::conflicttype, SCIP_ProofSet::nnz, NULL, SCIP_ProofSet::rhs, SCIP_CONFTYPE_UNKNOWN, SCIP_LONGINT_MAX, 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 131 of file conflict_dualproofanalysis.c.
References BMSallocBlockMemory, NULL, SCIP_ALLOC, SCIP_CONFTYPE_UNKNOWN, SCIP_LONGINT_MAX, 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 152 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 169 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 180 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 191 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 201 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 212 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 223 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 274 of file conflict_dualproofanalysis.c.
References SCIP_ProofSet::certificateline, SCIP_AggrRow::certificateline, NULL, proofsetAddSparseData(), SCIP_CALL, SCIP_Longint, SCIP_LONGINT_MAX, SCIP_OKAY, SCIP_Real, SCIPaggrRowGetInds(), SCIPaggrRowGetNNz(), SCIPaggrRowGetProbvarValue(), SCIPaggrRowGetRhs(), SCIPisCertified(), SCIPsetAllocBufferArray, SCIPsetFreeBufferArray, and SCIP_AggrRow::vals.
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 325 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 364 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 379 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 403 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 eventfilter global event filter 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 428 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 579 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 653 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 eventfilter global event filter 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 727 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 eventfilter global event filter cliquetable clique table data structure blkmem block memory
Definition at line 831 of file conflict_dualproofanalysis.c.
References SCIP_Stat::avgnnz, SCIP_ProofSet::certificateline, 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_Certificate::rowdatahash, 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_R_ROUND_NEAREST, SCIP_Real, SCIPaddCoefLinear(), SCIPallocBufferArray, SCIPbuffer(), SCIPconflictstoreAddDualraycons(), SCIPconflictstoreAddDualsolcons(), SCIPconflictstoreGetAvgNnzDualBndProofs(), SCIPconflictstoreGetAvgNnzDualInfProofs(), SCIPconflictstoreGetNDualBndProofs(), SCIPconflictstoreGetNDualInfProofs(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPconsMarkConflict(), SCIPcreateConsExactLinear(), SCIPcreateConsLinear(), SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetCertificate(), SCIPgetLhsExactLinear(), SCIPgetLhsLinear(), SCIPgetRhsExactLinear(), SCIPgetRhsLinear(), SCIPhashmapInsertLong(), SCIPisCertified(), SCIPnodeAddCons(), SCIPnodeCutoff(), SCIPnodeGetNumber(), SCIPprobAddCons(), SCIPprobGetVars(), SCIPproofsetGetNVars(), SCIPrationalCreateBuffer(), SCIPrationalCreateBufferArray(), SCIPrationalFreeBuffer(), SCIPrationalFreeBufferArray(), SCIPrationalIsAbsInfinity(), SCIPrationalRoundReal(), SCIPrationalSetNegInfinity(), SCIPrationalSetReal(), 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_EVENTFILTER * | eventfilter, | ||
| 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 eventfilter global event filter cliquetable clique table data structure
Definition at line 1173 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 1316 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 1358 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 VARTYPEUSEVBDS.
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 1489 of file conflict_dualproofanalysis.c.
References conflictInsertProofset(), SCIP_Conflict::conflictset, SCIP_ConflictSet::conflicttype, SCIP_ProofSet::conflicttype, debugPrintViolationInfo, eps, FALSE, 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, SCIPaggrRowGetInds(), SCIPaggrRowGetMinActivity(), SCIPaggrRowGetNNz(), SCIPaggrRowGetRhs(), SCIPprobGetVars(), SCIPproofsetFree(), SCIPproofsetGetNVars(), SCIPsetDebugMsg, SCIPsetIsEQ(), SCIPsetIsInfinity(), SCIPsetIsZero(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), SCIPvarIsIntegral(), SCIPvarIsNonimpliedIntegral(), 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, | ||
| SCIP_EVENTFILTER * | eventfilter, | ||
| 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 eventfilter global event filter 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 1682 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().