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

proofset	proof set
blkmem	block 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

proofset

proof 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

conflict	conflict analysis data
blkmem	block 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

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 SCIP_ProofSet::conflicttype, createAndAddProofcons(), 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(), 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 1605 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().