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.h.
#include "blockmemshell/memory.h"
#include "scip/def.h"
#include "scip/type_branch.h"
#include "scip/type_conflict.h"
#include "scip/type_conflictstore.h"
#include "scip/type_event.h"
#include "scip/type_implics.h"
#include "scip/type_lp.h"
#include "scip/type_prob.h"
#include "scip/type_reopt.h"
#include "scip/type_retcode.h"
#include "scip/type_set.h"
#include "scip/type_stat.h"
#include "scip/type_tree.h"
#include "scip/type_var.h"
#include "scip/type_cuts.h"
Go to the source code of this file.
Functions | |
void | SCIPproofsetFree (SCIP_PROOFSET **proofset, BMS_BLKMEM *blkmem) |
int | SCIPproofsetGetNVars (SCIP_PROOFSET *proofset) |
SCIP_RETCODE | SCIPconflictInitProofset (SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem) |
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) |
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) |
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().
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().
SCIP_RETCODE SCIPconflictInitProofset | ( | SCIP_CONFLICT * | conflict, |
BMS_BLKMEM * | blkmem ) |
returns the number of variables in the proofset creates and clears the proofset
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().
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().
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().