Detailed Description

internal methods for dual proof conflict analysis

Author: Timo Berthold; Jakob Witzig; Sander Borst

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

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_Real *	proofsetGetVals (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_EVENTFILTER eventfilter, 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_EVENTFILTER eventfilter, 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_EVENTFILTER eventfilter, 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_EVENTFILTER eventfilter, 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, 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)

Macro Definition Documentation

◆ BOUNDSWITCH

#define BOUNDSWITCH 0.51

threshold for bound switching - see cuts.c

Definition at line 89 of file conflict_dualproofanalysis.c.

Referenced by aggregation(), buildMod2Matrix(), createCGCutCMIR(), createCGCutStrongCG(), generateClusterCuts(), generateGMICuts(), generateZerohalfCut(), MirReduction(), SCIP_DECL_SEPAEXECLP(), and separateAlternativeProofs().

◆ POSTPROCESS

#define POSTPROCESS FALSE

apply postprocessing to the cut - see cuts.c

Definition at line 90 of file conflict_dualproofanalysis.c.

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

◆ 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.

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

◆ ALLOWLOCAL

#define ALLOWLOCAL FALSE

allow to generate local cuts - see cuts.

Definition at line 92 of file conflict_dualproofanalysis.c.

Referenced by separateAlternativeProofs().

◆ MINFRAC

#define MINFRAC 0.05

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

Definition at line 93 of file conflict_dualproofanalysis.c.

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

◆ MAXFRAC

#define MAXFRAC 0.999

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

Definition at line 94 of file conflict_dualproofanalysis.c.

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

◆ debugPrintViolationInfo

#define debugPrintViolationInfo ( ... )

Definition at line 1308 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

var variable

Definition at line 103 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

proofset proof set

Definition at line 116 of file conflict_dualproofanalysis.c.

References assert(), 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()

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

static

creates a proofset

Parameters

proofset	proof set
blkmem	block memory of transformed problem

Definition at line 131 of file conflict_dualproofanalysis.c.

References assert(), 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 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

proofset proof set

Definition at line 169 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

proofset proof set

Definition at line 180 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

proofset proof set

Definition at line 191 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

proofset proof set

Definition at line 201 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

proofset proof set

Definition at line 212 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

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 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

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 assert(), SCIP_AggrRow::certificateline, SCIP_ProofSet::certificateline, i, 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()

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 325 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

conflict	conflict analysis data
blkmem	block memory of transformed problem

Definition at line 364 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

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 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

conflict	conflict analysis data
set	global SCIP settings
proofset	proof set to add

Definition at line 403 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_EVENTFILTER *	eventfilter,
		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

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 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

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 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

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 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_EVENTFILTER *	eventfilter,
		SCIP_CLIQUETABLE *	cliquetable,
		SCIP_Real *	coefs,
		int *	inds,
		int	nnz,
		SCIP_Real	rhs,
		SCIP_CONFTYPE	conflicttype,
		int	validdepth )

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 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_EVENTFILTER *	eventfilter,
		SCIP_CLIQUETABLE *	cliquetable,
		BMS_BLKMEM *	blkmem )

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 assert(), SCIP_Stat::avgnnz, SCIP_ProofSet::certificateline, 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_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, 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_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 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

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, 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

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, 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(), vars, and VARTYPEUSEVBDS.

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

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 assert(), conflictInsertProofset(), SCIP_Conflict::conflictset, SCIP_ConflictSet::conflicttype, SCIP_ProofSet::conflicttype, debugPrintViolationInfo, eps, FALSE, getMaxActivity(), i, 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(), 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,
		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 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().

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ BOUNDSWITCH

◆ POSTPROCESS

◆ VARTYPEUSEVBDS

◆ ALLOWLOCAL

◆ MINFRAC

◆ MAXFRAC

◆ debugPrintViolationInfo

Function Documentation

◆ varGetChar()

◆ proofsetClear()

◆ proofsetCreate()

◆ SCIPproofsetFree()

◆ proofsetGetInds()

◆ proofsetGetVals()

◆ proofsetGetRhs()

◆ SCIPproofsetGetNVars()

◆ proofsetGetConftype()

◆ proofsetAddSparseData()

◆ proofsetAddAggrrow()

◆ proofsetCancelVarWithBound()

◆ SCIPconflictInitProofset()

◆ conflictEnsureProofsetsMem()

◆ conflictInsertProofset()

◆ tightenSingleVar()

◆ getMinActivity()

◆ getMaxActivity()

◆ propagateLongProof()

◆ createAndAddProofcons()

◆ SCIPconflictFlushProofset()

◆ tightenCoefficients()

◆ separateAlternativeProofs()

◆ tightenDualproof()

◆ SCIPconflictAnalyzeDualProof()