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.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) |
Function Documentation
◆ 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, SCIP_ProofSet::inds, SCIP_ProofSet::nnz, NULL, SCIP_ProofSet::rhs, SCIPprobGetVars(), SCIPvarGetName(), and SCIP_ProofSet::vals.
Referenced by SCIPconflictFlushProofset(), SCIPconflictFree(), separateAlternativeProofs(), and tightenDualproof().
◆ SCIPproofsetGetNVars()
int SCIPproofsetGetNVars | ( | SCIP_PROOFSET * | proofset | ) |
returns the number of variables in the proofset
- Parameters
-
proofset proof set
Definition at line 216 of file conflict_dualproofanalysis.c.
References SCIP_ProofSet::nnz, and NULL.
Referenced by conflictAnalyzeLP(), createAndAddProofcons(), SCIPconflictFlushProofset(), and tightenDualproof().
◆ SCIPconflictInitProofset()
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
- Parameters
-
conflict conflict analysis data blkmem block memory of transformed problem
Definition at line 369 of file conflict_dualproofanalysis.c.
References NULL, SCIP_Conflict::proofset, proofsetCreate(), SCIP_CALL, and SCIP_OKAY.
Referenced by SCIPconflictCreate().
◆ 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 1112 of file conflict_dualproofanalysis.c.
References SCIP_ProofSet::conflicttype, createAndAddProofcons(), debugPrintViolationInfo, 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(), SCIPsetDebugMsg, tightenSingleVar(), TRUE, and SCIP_ProofSet::validdepth.
Referenced by conflictAnalyzeLP().
◆ 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 1613 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().