SCIP Doxygen Documentation
Loading...
Searching...
No Matches
conflict_dualproofanalysis.c 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.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(...)

Functions

static char varGetChar (SCIP_VAR *var)
static void proofsetClear (SCIP_PROOFSET *proofset)
static SCIP_RETCODE proofsetCreate (SCIP_PROOFSET **proofset, BMS_BLKMEM *blkmem)
void SCIPproofsetFree (SCIP_PROOFSET **proofset, BMS_BLKMEM *blkmem)
static int * proofsetGetInds (SCIP_PROOFSET *proofset)
static SCIP_RealproofsetGetVals (SCIP_PROOFSET *proofset)
static SCIP_Real proofsetGetRhs (SCIP_PROOFSET *proofset)
int SCIPproofsetGetNVars (SCIP_PROOFSET *proofset)
static SCIP_CONFTYPE proofsetGetConftype (SCIP_PROOFSET *proofset)
static SCIP_RETCODE proofsetAddSparseData (SCIP_PROOFSET *proofset, BMS_BLKMEM *blkmem, SCIP_Real *vals, int *inds, int nnz, SCIP_Real rhs)
static SCIP_RETCODE proofsetAddAggrrow (SCIP_PROOFSET *proofset, SCIP_SET *set, BMS_BLKMEM *blkmem, SCIP_AGGRROW *aggrrow)
static void proofsetCancelVarWithBound (SCIP_PROOFSET *proofset, SCIP_SET *set, SCIP_VAR *var, int pos, SCIP_Bool *valid)
SCIP_RETCODE SCIPconflictInitProofset (SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem)
static SCIP_RETCODE conflictEnsureProofsetsMem (SCIP_CONFLICT *conflict, SCIP_SET *set, int num)
static SCIP_RETCODE conflictInsertProofset (SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_PROOFSET *proofset)
static SCIP_RETCODE tightenSingleVar (SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_PROB *origprob, SCIP_PROB *transprob, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *var, SCIP_Real val, SCIP_Real rhs, SCIP_CONFTYPE prooftype, int validdepth)
static SCIP_Real getMinActivity (SCIP_SET *set, SCIP_PROB *transprob, SCIP_Real *coefs, int *inds, int nnz, SCIP_Real *curvarlbs, SCIP_Real *curvarubs)
static SCIP_Real getMaxActivity (SCIP_SET *set, SCIP_PROB *transprob, SCIP_Real *coefs, int *inds, int nnz, SCIP_Real *curvarlbs, SCIP_Real *curvarubs)
static SCIP_RETCODE propagateLongProof (SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_STAT *stat, SCIP_REOPT *reopt, SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_PROB *origprob, SCIP_PROB *transprob, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_Real *coefs, int *inds, int nnz, SCIP_Real rhs, SCIP_CONFTYPE conflicttype, int validdepth)
static SCIP_RETCODE createAndAddProofcons (SCIP_CONFLICT *conflict, SCIP_CONFLICTSTORE *conflictstore, SCIP_PROOFSET *proofset, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *origprob, SCIP_PROB *transprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, 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)
static void tightenCoefficients (SCIP_SET *set, SCIP_PROOFSET *proofset, int *nchgcoefs, SCIP_Bool *redundant)
static SCIP_RETCODE separateAlternativeProofs (SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_AGGRROW *proofrow, SCIP_Real *curvarlbs, SCIP_Real *curvarubs, SCIP_CONFTYPE conflicttype)
static SCIP_RETCODE tightenDualproof (SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_PROB *transprob, SCIP_TREE *tree, SCIP_AGGRROW *proofrow, int validdepth, SCIP_Real *curvarlbs, SCIP_Real *curvarubs, SCIP_Bool initialproof)
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)

Macro Definition Documentation

◆ BOUNDSWITCH

◆ POSTPROCESS

#define POSTPROCESS   FALSE

◆ USEVBDS

◆ ALLOWLOCAL

#define ALLOWLOCAL   FALSE

allow to generate local cuts - see cuts.

Definition at line 86 of file conflict_dualproofanalysis.c.

Referenced by separateAlternativeProofs().

◆ MINFRAC

#define MINFRAC   0.05

minimal fractionality of floor(rhs) - see cuts.c

Definition at line 87 of file conflict_dualproofanalysis.c.

Referenced by aggregation(), createCGCutCMIR(), createCGCutStrongCG(), generateClusterCuts(), and separateAlternativeProofs().

◆ MAXFRAC

#define MAXFRAC   0.999

maximal fractionality of floor(rhs) - see cuts.c

Definition at line 88 of file conflict_dualproofanalysis.c.

Referenced by aggregation(), createCGCutCMIR(), createCGCutStrongCG(), generateClusterCuts(), and separateAlternativeProofs().

◆ debugPrintViolationInfo

#define debugPrintViolationInfo ( ...)

Definition at line 1236 of file conflict_dualproofanalysis.c.

Referenced by tightenDualproof().

Function Documentation

◆ varGetChar()

char varGetChar ( SCIP_VAR * var)
static

return the char associated with the type of the variable

Parameters
varvariable

Definition at line 97 of file conflict_dualproofanalysis.c.

References SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPvarGetType(), SCIPvarIsIntegral(), and var.

Referenced by tightenSingleVar().

◆ proofsetClear()

void proofsetClear ( SCIP_PROOFSET * proofset)
static

resets the data structure of a proofset

Parameters
proofsetproof set

Definition at line 110 of file conflict_dualproofanalysis.c.

References assert(), SCIP_ProofSet::conflicttype, SCIP_ProofSet::nnz, NULL, SCIP_ProofSet::rhs, SCIP_CONFTYPE_UNKNOWN, and SCIP_ProofSet::validdepth.

Referenced by SCIPconflictFlushProofset(), and tightenDualproof().

◆ proofsetCreate()

SCIP_RETCODE proofsetCreate ( SCIP_PROOFSET ** proofset,
BMS_BLKMEM * blkmem )
static

creates a proofset

Parameters
proofsetproof set
blkmemblock memory of transformed problem

Definition at line 124 of file conflict_dualproofanalysis.c.

References assert(), 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
proofsetproof set
blkmemblock memory

Definition at line 144 of file conflict_dualproofanalysis.c.

References assert(), BMSfreeBlockMemory, BMSfreeBlockMemoryArrayNull, and NULL.

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

◆ proofsetGetInds()

int * proofsetGetInds ( SCIP_PROOFSET * proofset)
static

return the indices of variables in the proofset

Parameters
proofsetproof set

Definition at line 161 of file conflict_dualproofanalysis.c.

References assert(), SCIP_ProofSet::inds, and NULL.

Referenced by createAndAddProofcons(), SCIPconflictFlushProofset(), and tightenDualproof().

◆ proofsetGetVals()

SCIP_Real * proofsetGetVals ( SCIP_PROOFSET * proofset)
static

return coefficient of variable in the proofset with given probindex

Parameters
proofsetproof set

Definition at line 172 of file conflict_dualproofanalysis.c.

References assert(), NULL, SCIP_Real, and SCIP_ProofSet::vals.

Referenced by createAndAddProofcons(), SCIPconflictFlushProofset(), and tightenDualproof().

◆ proofsetGetRhs()

SCIP_Real proofsetGetRhs ( SCIP_PROOFSET * proofset)
static

return the right-hand side if a proofset

Parameters
proofsetproof set

Definition at line 183 of file conflict_dualproofanalysis.c.

References assert(), NULL, SCIP_ProofSet::rhs, and SCIP_Real.

Referenced by createAndAddProofcons(), SCIPconflictFlushProofset(), and tightenCoefficients().

◆ 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 assert(), SCIP_ProofSet::nnz, and NULL.

Referenced by conflictAnalyzeLP(), createAndAddProofcons(), SCIPconflictFlushProofset(), tightenCoefficients(), and tightenDualproof().

◆ proofsetGetConftype()

SCIP_CONFTYPE proofsetGetConftype ( SCIP_PROOFSET * proofset)
static

returns the number of variables in the proofset

Parameters
proofsetproof set

Definition at line 204 of file conflict_dualproofanalysis.c.

References assert(), SCIP_ProofSet::conflicttype, and NULL.

Referenced by createAndAddProofcons(), and SCIPconflictFlushProofset().

◆ proofsetAddSparseData()

SCIP_RETCODE proofsetAddSparseData ( SCIP_PROOFSET * proofset,
BMS_BLKMEM * blkmem,
SCIP_Real * vals,
int * inds,
int nnz,
SCIP_Real rhs )
static

adds given data as aggregation row to the proofset

Parameters
proofsetproof set
blkmemblock memory
valsvariable coefficients
indsvariable array
nnzsize of variable and coefficient array
rhsright-hand side of the aggregation row

Definition at line 215 of file conflict_dualproofanalysis.c.

References assert(), BMSduplicateBlockMemoryArray, BMSreallocBlockMemoryArray, i, SCIP_ProofSet::inds, SCIP_ProofSet::nnz, NULL, SCIP_ProofSet::rhs, SCIP_ALLOC, SCIP_OKAY, SCIP_Real, SCIP_ProofSet::size, and SCIP_ProofSet::vals.

Referenced by proofsetAddAggrrow(), and separateAlternativeProofs().

◆ proofsetAddAggrrow()

SCIP_RETCODE proofsetAddAggrrow ( SCIP_PROOFSET * proofset,
SCIP_SET * set,
BMS_BLKMEM * blkmem,
SCIP_AGGRROW * aggrrow )
static

adds an aggregation row to the proofset

Parameters
proofsetproof set
setglobal SCIP settings
blkmemblock memory
aggrrowaggregation row to add

Definition at line 266 of file conflict_dualproofanalysis.c.

References assert(), i, NULL, proofsetAddSparseData(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaggrRowGetInds(), SCIPaggrRowGetNNz(), SCIPaggrRowGetProbvarValue(), SCIPaggrRowGetRhs(), SCIPsetAllocBufferArray, and SCIPsetFreeBufferArray.

Referenced by tightenDualproof().

◆ proofsetCancelVarWithBound()

void proofsetCancelVarWithBound ( SCIP_PROOFSET * proofset,
SCIP_SET * set,
SCIP_VAR * var,
int pos,
SCIP_Bool * valid )
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 assert(), FALSE, SCIP_ProofSet::inds, SCIP_ProofSet::nnz, NULL, SCIP_ProofSet::rhs, SCIP_Bool, SCIPsetIsInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), TRUE, valid, SCIP_ProofSet::vals, and var.

Referenced by tightenDualproof().

◆ SCIPconflictInitProofset()

SCIP_RETCODE SCIPconflictInitProofset ( SCIP_CONFLICT * conflict,
BMS_BLKMEM * blkmem )

creates and clears the proofset

Parameters
conflictconflict analysis data
blkmemblock 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().

◆ conflictEnsureProofsetsMem()

SCIP_RETCODE conflictEnsureProofsetsMem ( SCIP_CONFLICT * conflict,
SCIP_SET * set,
int num )
static

resizes proofsets array to be able to store at least num entries

Parameters
conflictconflict analysis data
setglobal SCIP settings
numminimal number of slots in array

Definition at line 361 of file conflict_dualproofanalysis.c.

References assert(), BMSreallocMemoryArray, NULL, SCIP_Conflict::proofsets, SCIP_Conflict::proofsetssize, SCIP_ALLOC, SCIP_OKAY, and SCIPsetCalcMemGrowSize().

Referenced by conflictInsertProofset().

◆ conflictInsertProofset()

SCIP_RETCODE conflictInsertProofset ( SCIP_CONFLICT * conflict,
SCIP_SET * set,
SCIP_PROOFSET * proofset )
static

add a proofset to the list of all proofsets

Parameters
conflictconflict analysis data
setglobal SCIP settings
proofsetproof set to add

Definition at line 385 of file conflict_dualproofanalysis.c.

References assert(), conflictEnsureProofsetsMem(), SCIP_Conflict::nproofsets, NULL, SCIP_Conflict::proofsets, SCIP_CALL, and SCIP_OKAY.

Referenced by separateAlternativeProofs(), and tightenDualproof().

◆ tightenSingleVar()

SCIP_RETCODE tightenSingleVar ( SCIP_CONFLICT * conflict,
SCIP_SET * set,
SCIP_STAT * stat,
SCIP_TREE * tree,
BMS_BLKMEM * blkmem,
SCIP_PROB * origprob,
SCIP_PROB * transprob,
SCIP_REOPT * reopt,
SCIP_LP * lp,
SCIP_BRANCHCAND * branchcand,
SCIP_EVENTQUEUE * eventqueue,
SCIP_CLIQUETABLE * cliquetable,
SCIP_VAR * var,
SCIP_Real val,
SCIP_Real rhs,
SCIP_CONFTYPE prooftype,
int validdepth )
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
conflictconflict analysis data
setglobal SCIP settings
statdynamic SCIP statistics
treetree data
blkmemblock memory
origproboriginal problem
transprobtransformed problem
reoptreoptimization data
lpLP data
branchcandbranching candidates
eventqueueevent queue
cliquetableclique table
varproblem variable
valcoefficient of the variable
rhsrhs of the constraint
prooftypetype of the proof
validdepthdepth where the bound change is valid

Definition at line 410 of file conflict_dualproofanalysis.c.

References assert(), 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, var, and varGetChar().

Referenced by propagateLongProof(), and SCIPconflictFlushProofset().

◆ getMinActivity()

SCIP_Real getMinActivity ( SCIP_SET * set,
SCIP_PROB * transprob,
SCIP_Real * coefs,
int * inds,
int nnz,
SCIP_Real * curvarlbs,
SCIP_Real * curvarubs )
static

calculates the minimal activity of a given set of bounds and coefficients

Parameters
setglobal SCIP settings
transprobtransformed problem data
coefscoefficients in sparse representation
indsnon-zero indices
nnznumber of non-zero indices
curvarlbscurrent lower bounds of active problem variables (or NULL for global bounds)
curvarubscurrent upper bounds of active problem variables (or NULL for global bounds)

Definition at line 560 of file conflict_dualproofanalysis.c.

References assert(), i, NULL, QUAD, QUAD_ASSIGN, QUAD_TO_DBL, SCIP_Real, SCIPprobGetVars(), SCIPquadprecProdDD, SCIPquadprecSumQQ, SCIPsetInfinity(), SCIPsetIsInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), and vars.

Referenced by createAndAddProofcons(), and propagateLongProof().

◆ getMaxActivity()

SCIP_Real getMaxActivity ( SCIP_SET * set,
SCIP_PROB * transprob,
SCIP_Real * coefs,
int * inds,
int nnz,
SCIP_Real * curvarlbs,
SCIP_Real * curvarubs )
static

calculates the minimal activity of a given set of bounds and coefficients

Parameters
setglobal SCIP settings
transprobtransformed problem data
coefscoefficients in sparse representation
indsnon-zero indices
nnznumber of non-zero indices
curvarlbscurrent lower bounds of active problem variables (or NULL for global bounds)
curvarubscurrent upper bounds of active problem variables (or NULL for global bounds)

Definition at line 634 of file conflict_dualproofanalysis.c.

References assert(), i, NULL, QUAD, QUAD_ASSIGN, QUAD_TO_DBL, SCIP_Real, SCIPprobGetVars(), SCIPquadprecProdDD, SCIPquadprecSumQQ, SCIPsetInfinity(), SCIPsetIsInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), and vars.

Referenced by createAndAddProofcons(), and tightenDualproof().

◆ propagateLongProof()

SCIP_RETCODE propagateLongProof ( SCIP_CONFLICT * conflict,
SCIP_SET * set,
SCIP_STAT * stat,
SCIP_REOPT * reopt,
SCIP_TREE * tree,
BMS_BLKMEM * blkmem,
SCIP_PROB * origprob,
SCIP_PROB * transprob,
SCIP_LP * lp,
SCIP_BRANCHCAND * branchcand,
SCIP_EVENTQUEUE * eventqueue,
SCIP_CLIQUETABLE * cliquetable,
SCIP_Real * coefs,
int * inds,
int nnz,
SCIP_Real rhs,
SCIP_CONFTYPE conflicttype,
int validdepth )
static

propagate a long proof

Parameters
conflictconflict analysis data
setglobal SCIP settings
statdynamic SCIP statistics
reoptreoptimization data
treetree data
blkmemblock memory
origproboriginal problem
transprobtransformed problem
lpLP data
branchcandbranching candidate storage
eventqueueevent queue
cliquetableclique table data structure
coefscoefficients in sparse representation
indsnon-zero indices
nnznumber of non-zero indices
rhsright-hand side
conflicttypetype of the conflict
validdepthdepth where the proof is valid

Definition at line 708 of file conflict_dualproofanalysis.c.

References assert(), getMinActivity(), i, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPprobGetVars(), SCIPsetIsEQ(), SCIPsetIsGE(), SCIPsetIsInfinity(), SCIPsetIsLE(), SCIPsetIsZero(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), tightenSingleVar(), var, and vars.

Referenced by createAndAddProofcons().

◆ createAndAddProofcons()

SCIP_RETCODE createAndAddProofcons ( SCIP_CONFLICT * conflict,
SCIP_CONFLICTSTORE * conflictstore,
SCIP_PROOFSET * proofset,
SCIP_SET * set,
SCIP_STAT * stat,
SCIP_PROB * origprob,
SCIP_PROB * transprob,
SCIP_TREE * tree,
SCIP_REOPT * reopt,
SCIP_LP * lp,
SCIP_BRANCHCAND * branchcand,
SCIP_EVENTQUEUE * eventqueue,
SCIP_CLIQUETABLE * cliquetable,
BMS_BLKMEM * blkmem )
static

creates a proof constraint and tries to add it to the storage

Parameters
conflictconflict analysis data
conflictstoreconflict pool data
proofsetproof set
setglobal SCIP settings
statdynamic SCIP statistics
origproboriginal problem
transprobtransformed problem
treetree data
reoptreoptimization data
lpLP data
branchcandbranching candidate storage
eventqueueevent queue
cliquetableclique table data structure
blkmemblock memory

Definition at line 811 of file conflict_dualproofanalysis.c.

References assert(), SCIP_Stat::avgnnz, SCIP_Conflict::dualproofsbndnnonzeros, SCIP_Conflict::dualproofsinfnnonzeros, FALSE, getMaxActivity(), getMinActivity(), i, 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, SCIP_ProofSet::validdepth, and vars.

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
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 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().

◆ tightenCoefficients()

void tightenCoefficients ( SCIP_SET * set,
SCIP_PROOFSET * proofset,
int * nchgcoefs,
SCIP_Bool * redundant )
static

apply coefficient tightening

Parameters
setglobal SCIP settings
proofsetproof set
nchgcoefspointer to store number of changed coefficients
redundantpointer to store whether the proof set is redundant

Definition at line 1241 of file conflict_dualproofanalysis.c.

References FALSE, i, SCIP_ProofSet::inds, MAX, MIN, SCIP_ProofSet::nnz, proofsetGetRhs(), REALABS, SCIP_ProofSet::rhs, SCIP_Bool, SCIP_Real, SCIPcutsTightenCoefficients(), SCIPproofsetGetNVars(), SCIPsetDebugMsg, SCIPsetInfinity(), and SCIP_ProofSet::vals.

Referenced by separateAlternativeProofs(), and tightenDualproof().

◆ separateAlternativeProofs()

SCIP_RETCODE separateAlternativeProofs ( SCIP_CONFLICT * conflict,
SCIP_SET * set,
SCIP_STAT * stat,
SCIP_PROB * transprob,
SCIP_TREE * tree,
BMS_BLKMEM * blkmem,
SCIP_AGGRROW * proofrow,
SCIP_Real * curvarlbs,
SCIP_Real * curvarubs,
SCIP_CONFTYPE conflicttype )
static

try to generate alternative proofs by applying subadditive functions

Parameters
conflictconflict analysis data
setglobal SCIP settings
statdynamic SCIP statistics
transprobtransformed problem
treetree data
blkmemblock memory
proofrowproof rows data
curvarlbscurrent lower bounds of active problem variables
curvarubscurrent upper bounds of active problem variables
conflicttypetype of the conflict

Definition at line 1283 of file conflict_dualproofanalysis.c.

References ALLOWLOCAL, BOUNDSWITCH, conflictInsertProofset(), SCIP_ProofSet::conflicttype, i, MAX, MAXFRAC, MINFRAC, NULL, nvars, 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(), USEVBDS, and vars.

Referenced by tightenDualproof().

◆ tightenDualproof()

SCIP_RETCODE tightenDualproof ( SCIP_CONFLICT * conflict,
SCIP_SET * set,
SCIP_STAT * stat,
BMS_BLKMEM * blkmem,
SCIP_PROB * transprob,
SCIP_TREE * tree,
SCIP_AGGRROW * proofrow,
int validdepth,
SCIP_Real * curvarlbs,
SCIP_Real * curvarubs,
SCIP_Bool initialproof )
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
conflictconflict analysis data
setglobal SCIP settings
statdynamic SCIP statistics
blkmemblock memory
transprobtransformed problem
treetree data
proofrowaggregated row representing the proof
validdepthdepth where the proof is valid
curvarlbscurrent lower bounds of active problem variables
curvarubscurrent upper bounds of active problem variables
initialproofdo we analyze the initial reason of infeasibility?

Definition at line 1414 of file conflict_dualproofanalysis.c.

References assert(), conflictInsertProofset(), SCIP_Conflict::conflictset, SCIP_ConflictSet::conflicttype, SCIP_ProofSet::conflicttype, debugPrintViolationInfo, eps, getMaxActivity(), i, SCIP_ProofSet::inds, MIN, nbinvars, nintvars, 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(), valid, SCIP_ProofSet::validdepth, SCIP_ProofSet::vals, and vars.

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
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 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().