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

SCIP

Detailed Description

Functions

Function Documentation

◆ SCIPproofsetFree()

◆ SCIPproofsetGetNVars()

◆ SCIPconflictInitProofset()

◆ SCIPconflictFlushProofset()

◆ SCIPconflictAnalyzeDualProof()