Scippy

SCIP

Solving Constraint Integer Programs

conflict_dualproofanalysis.h File Reference

Detailed Description

internal methods for dual proof conflict analysis

Author
Timo Berthold
Jakob Witzig

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
proofsetproof set
blkmemblock memory

Definition at line 144 of file conflict_dualproofanalysis.c.

References BMSfreeBlockMemory, BMSfreeBlockMemoryArrayNull, and NULL.

Referenced by SCIPconflictFlushProofset(), SCIPconflictFree(), separateAlternativeProofs(), and tightenDualproof().

◆ SCIPproofsetGetNVars()

int SCIPproofsetGetNVars ( SCIP_PROOFSET proofset)

returns the number of variables in the proofset

Parameters
proofsetproof set

Definition at line 193 of file conflict_dualproofanalysis.c.

References SCIP_ProofSet::nnz, and NULL.

Referenced by conflictAnalyzeLP(), createAndAddProofcons(), SCIPconflictFlushProofset(), tightenCoefficients(), 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
conflictconflict analysis data
blkmemblock 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().

◆ 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
conflictconflict analysis data
conflictstoreconflict store
blkmemblock memory
setglobal SCIP settings
statdynamic problem statistics
transprobtransformed problem after presolve
origproboriginal problem
treebranch and bound tree
reoptreoptimization data structure
lpcurrent LP data
branchcandbranching candidate storage
eventqueueevent queue
cliquetableclique table data structure

Definition at line 1089 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
conflictconflict analysis data
setglobal SCIP settings
statdynamic SCIP statistics
blkmemblock memory
origproboriginal problem
transprobtransformed problem
treetree data
reoptreoptimization data
lpLP data
proofrowaggregated row representing the proof
validdepthvalid depth of the dual proof
curvarlbscurrent lower bounds of active problem variables
curvarubscurrent upper bounds of active problem variables
initialproofdo we analyze the initial reason of infeasibility?
globalinfeasiblepointer to store whether global infeasibility could be proven
successpointer to store success result

Definition at line 1590 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().