conflict_graphanalysis.h File Reference

Detailed Description

methods and datastructures for conflict analysis

Author

Tobias Achterberg

Timo Berthold

Stefan Heinz

Marc Pfetsch

Michael Winkler

Jakob Witzig

This file implements a conflict analysis method like the one used in modern SAT solvers like zchaff. The algorithm works as follows:

Given is a set of bound changes that are not allowed being applied simultaneously, because they render the current node infeasible (e.g. because a single constraint is infeasible in the these bounds, or because the LP relaxation is infeasible). The goal is to deduce a clause on variables – a conflict clause – representing the "reason" for this conflict, i.e., the branching decisions or the deductions (applied e.g. in domain propagation) that lead to the conflict. This clause can then be added to the constraint set to help cutting off similar parts of the branch and bound tree, that would lead to the same conflict. A conflict clause can also be generated, if the conflict was detected by a locally valid constraint. In this case, the resulting conflict clause is also locally valid in the same depth as the conflict detecting constraint. If all involved variables are binary, a linear (set covering) constraint can be generated, otherwise a bound disjunction constraint is generated. Details are given in

Tobias Achterberg, Conflict Analysis in Mixed Integer Programming
Discrete Optimization, 4, 4-20 (2007)

See also How to use conflict analysis. Here is an outline of the algorithm:

1. Put all the given bound changes to a priority queue, which is ordered, such that the bound change that was applied last due to branching or deduction is at the top of the queue. The variables in the queue are always active problem variables. Because binary variables are preferred over general integer variables, integer variables are put on the priority queue prior to the binary variables. Create an empty conflict set.
2. Remove the top bound change b from the priority queue.
3. Perform the following case distinction:
   1. If the remaining queue is non-empty, and bound change b' (the one that is now on the top of the queue) was applied at the same depth level as b, and if b was a deduction with known inference reason, and if the inference constraint's valid depth is smaller or equal to the conflict detecting constraint's valid depth:
      • Resolve bound change b by asking the constraint that inferred the bound change to put all the bound changes on the priority queue, that lead to the deduction of b. Note that these bound changes have at most the same inference depth level as b, and were deduced earlier than b.
   2. Otherwise, the bound change b was a branching decision or a deduction with missing inference reason, or the inference constraint's validity is more local than the one of the conflict detecting constraint.
      • If a the bound changed corresponds to a binary variable, add it or its negation to the conflict set, depending on which of them is currently fixed to FALSE (i.e., the conflict set consists of literals that cannot be FALSE altogether at the same time).
      • Otherwise put the bound change into the conflict set. Note that if the bound change was a branching, all deduced bound changes remaining in the priority queue have smaller inference depth level than b, since deductions are always applied after the branching decisions. However, there is the possibility, that b was a deduction, where the inference reason was not given or the inference constraint was too local. With this lack of information, we must treat the deduced bound change like a branching, and there may exist other deduced bound changes of the same inference depth level in the priority queue.
4. If priority queue is non-empty, goto step 2.
5. The conflict set represents the conflict clause saying that at least one of the conflict variables must take a different value. The conflict set is then passed to the conflict handlers, that may create a corresponding constraint (e.g. a logicor constraint or bound disjunction constraint) out of these conflict variables and add it to the problem.

If all deduced bound changes come with (global) inference information, depending on the conflict analyzing strategy, the resulting conflict set has the following property:

• 1-FirstUIP: In the depth level where the conflict was found, at most one variable assigned at that level is member of the conflict set. This conflict variable is the first unique implication point of its depth level (FUIP).
• All-FirstUIP: For each depth level, at most one variable assigned at that level is member of the conflict set. This conflict variable is the first unique implication point of its depth level (FUIP).

The user has to do the following to get the conflict analysis running in its current implementation:

• A constraint handler or propagator supporting the conflict analysis must implement the CONSRESPROP/PROPRESPROP call, that processes a bound change inference b and puts all the reason bounds leading to the application of b with calls to SCIPaddConflictBound() on the conflict queue (algorithm step 3.(a)).
• If the current bounds lead to a deduction of a bound change (e.g. in domain propagation), a constraint handler should call SCIPinferVarLbCons() or SCIPinferVarUbCons(), thus providing the constraint that inferred the bound change. A propagator should call SCIPinferVarLbProp() or SCIPinferVarUbProp() instead, thus providing a pointer to itself.
• If (in the current bounds) an infeasibility is detected, the constraint handler or propagator should
  1. call SCIPinitConflictAnalysis() to initialize the conflict queue,
  2. call SCIPaddConflictBound() for each bound that lead to the conflict,
  3. call SCIPanalyzeConflictCons() or SCIPanalyzeConflict() to analyze the conflict and add an appropriate conflict constraint.

Definition in file conflict_graphanalysis.h.

#include "scip/def.h"
#include "scip/type_cuts.h"
#include "scip/type_conflict.h"
#include "scip/type_reopt.h"
#include "scip/type_implics.h"
#include "scip/type_set.h"
#include "scip/type_stat.h"
#include "scip/type_lp.h"
#include "lpi/type_lpi.h"
#include "scip/type_branch.h"
#include "scip/type_mem.h"
#include "scip/type_var.h"
#include "scip/type_prob.h"
#include "scip/type_event.h"
#include "scip/type_message.h"
#include <string.h>
#include <strings.h>

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPconflictsetCreate (SCIP_CONFLICTSET **conflictset, BMS_BLKMEM *blkmem)
void	SCIPconflictsetFree (SCIP_CONFLICTSET **conflictset, BMS_BLKMEM *blkmem)
SCIP_RETCODE	SCIPconflicthdlrCopyInclude (SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set)
SCIP_RETCODE	SCIPconflicthdlrCreate (SCIP_CONFLICTHDLR **conflicthdlr, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int priority, SCIP_DECL_CONFLICTCOPY((*conflictcopy)), SCIP_DECL_CONFLICTFREE((*conflictfree)), SCIP_DECL_CONFLICTINIT((*conflictinit)), SCIP_DECL_CONFLICTEXIT((*conflictexit)), SCIP_DECL_CONFLICTINITSOL((*conflictinitsol)), SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol)), SCIP_DECL_CONFLICTEXEC((*conflictexec)), SCIP_CONFLICTHDLRDATA *conflicthdlrdata)
SCIP_RETCODE	SCIPconflicthdlrFree (SCIP_CONFLICTHDLR **conflicthdlr, SCIP_SET *set)
SCIP_RETCODE	SCIPconflicthdlrInit (SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set)
SCIP_RETCODE	SCIPconflicthdlrExit (SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set)
SCIP_RETCODE	SCIPconflicthdlrInitsol (SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set)
SCIP_RETCODE	SCIPconflicthdlrExitsol (SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set)
SCIP_RETCODE	SCIPconflicthdlrExec (SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set, SCIP_NODE *node, SCIP_NODE *validnode, SCIP_BDCHGINFO **bdchginfos, SCIP_Real *relaxedbds, int nbdchginfos, SCIP_CONFTYPE conftype, SCIP_Bool usescutoffbound, SCIP_Bool resolved, SCIP_RESULT *result)
void	SCIPconflicthdlrSetPriority (SCIP_CONFLICTHDLR *conflicthdlr, SCIP_SET *set, int priority)
void	SCIPconflicthdlrSetCopy (SCIP_CONFLICTHDLR *conflicthdlr,)
void	SCIPconflicthdlrSetFree (SCIP_CONFLICTHDLR *conflicthdlr,)
void	SCIPconflicthdlrSetInit (SCIP_CONFLICTHDLR *conflicthdlr,)
void	SCIPconflicthdlrSetExit (SCIP_CONFLICTHDLR *conflicthdlr,)
void	SCIPconflicthdlrSetInitsol (SCIP_CONFLICTHDLR *conflicthdlr,)
void	SCIPconflicthdlrSetExitsol (SCIP_CONFLICTHDLR *conflicthdlr,)
void	SCIPconflicthdlrEnableOrDisableClocks (SCIP_CONFLICTHDLR *conflicthdlr, SCIP_Bool enable)
SCIP_Bool	SCIPconflictGraphApplicable (SCIP_SET *set)
SCIP_RETCODE	conflictCreateTmpBdchginfo (SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_Real oldbound, SCIP_Real newbound, SCIP_BDCHGINFO **bdchginfo)
int	conflictCalcMaxsize (SCIP_SET *set, SCIP_PROB *prob)
SCIP_RETCODE	SCIPundoBdchgsProof (SCIP_SET *set, SCIP_PROB *prob, int currentdepth, SCIP_Real *proofcoefs, SCIP_Real prooflhs, SCIP_Real *proofact, SCIP_Real *curvarlbs, SCIP_Real *curvarubs, int *lbchginfoposs, int *ubchginfoposs, SCIP_LPBDCHGS *oldlpbdchgs, SCIP_LPBDCHGS *relaxedlpbdchgs, SCIP_Bool *resolve, SCIP_LPI *lpi)
SCIP_RETCODE	SCIPconflictAnalyzeRemainingBdchgs (SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_TREE *tree, SCIP_Bool diving, int *lbchginfoposs, int *ubchginfoposs, int *nconss, int *nliterals, int *nreconvconss, int *nreconvliterals)
SCIP_RETCODE	SCIPconflictInit (SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_CONFTYPE conftype, SCIP_Bool usescutoffbound)
SCIP_RETCODE	SCIPconflictAddBound (SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx)
SCIP_RETCODE	SCIPconflictAddRelaxedBound (SCIP_CONFLICT *conflict, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd)
SCIP_RETCODE	SCIPconflictIsVarUsed (SCIP_CONFLICT *conflict, SCIP_VAR *var, SCIP_SET *set, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool *used)
SCIP_Real	SCIPconflictGetVarLb (SCIP_CONFLICT *conflict, SCIP_VAR *var)
SCIP_Real	SCIPconflictGetVarUb (SCIP_CONFLICT *conflict, SCIP_VAR *var)
SCIP_RETCODE	SCIPrunBoundHeuristic (SCIP_CONFLICT *conflict, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *origprob, SCIP_PROB *transprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_LPI *lpi, SCIP_EVENTFILTER *eventfilter, BMS_BLKMEM *blkmem, SCIP_Real *proofcoefs, SCIP_Real *prooflhs, SCIP_Real *proofactivity, SCIP_Real *curvarlbs, SCIP_Real *curvarubs, int *lbchginfoposs, int *ubchginfoposs, int *iterations, SCIP_Bool marklpunsolved, SCIP_Bool *dualproofsuccess, SCIP_Bool *valid)
void	conflictsetPrint (SCIP_CONFLICTSET *conflictset)
SCIP_Bool	bdchginfoIsInvalid (SCIP_CONFLICT *conflict, SCIP_BDCHGINFO *bdchginfo)

Function Documentation

SCIPconflictsetCreate()

SCIP_RETCODE SCIPconflictsetCreate	(	SCIP_CONFLICTSET **	conflictset,
		BMS_BLKMEM *	blkmem )

creates an empty conflict set

Parameters

conflictset	pointer to store the conflict set
blkmem	block memory of transformed problem

Definition at line 990 of file conflict_graphanalysis.c.

References assert(), BMSallocBlockMemory, conflictsetClear(), NULL, SCIP_ALLOC, and SCIP_OKAY.

Referenced by SCIPconflictCreate().

SCIPconflictsetFree()

void SCIPconflictsetFree	(	SCIP_CONFLICTSET **	conflictset,
		BMS_BLKMEM *	blkmem )

frees a conflict set

Parameters

conflictset	pointer to the conflict set
blkmem	block memory of transformed problem

Definition at line 1046 of file conflict_graphanalysis.c.

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

Referenced by conflictAddConflictset(), conflictInsertConflictset(), SCIPconflictFlushConss(), and SCIPconflictFree().

SCIPconflicthdlrCopyInclude()

SCIP_RETCODE SCIPconflicthdlrCopyInclude	(	SCIP_CONFLICTHDLR *	conflicthdlr,
		SCIP_SET *	set )

copies the given conflict handler to a new scip

Parameters

conflicthdlr	conflict handler
set	SCIP_SET of SCIP to copy to

Definition at line 1110 of file conflict_graphanalysis.c.

References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconflicthdlrGetName(), and SCIPsetDebugMsg.

Referenced by SCIPsetCopyPlugins().

SCIPconflicthdlrCreate()

SCIP_RETCODE SCIPconflicthdlrCreate	(	SCIP_CONFLICTHDLR **	conflicthdlr,
		SCIP_SET *	set,
		SCIP_MESSAGEHDLR *	messagehdlr,
		BMS_BLKMEM *	blkmem,
		const char *	name,
		const char *	desc,
		int	priority,
		SCIP_DECL_CONFLICTCOPY((*conflictcopy))	,
		SCIP_DECL_CONFLICTFREE((*conflictfree))	,
		SCIP_DECL_CONFLICTINIT((*conflictinit))	,
		SCIP_DECL_CONFLICTEXIT((*conflictexit))	,
		SCIP_DECL_CONFLICTINITSOL((*conflictinitsol))	,
		SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol))	,
		SCIP_DECL_CONFLICTEXEC((*conflictexec))	,
		SCIP_CONFLICTHDLRDATA *	conflicthdlrdata )

creates a conflict handler

Parameters

conflicthdlr	pointer to conflict handler data structure
set	global SCIP settings
messagehdlr	message handler
blkmem	block memory for parameter settings
name	name of conflict handler
desc	description of conflict handler
priority	priority of the conflict handler
conflicthdlrdata	conflict handler data

Definition at line 1184 of file conflict_graphanalysis.c.

References assert(), doConflicthdlrCreate(), NULL, SCIP_CALL_FINALLY, SCIP_OKAY, and SCIPconflicthdlrFree().

Referenced by SCIPincludeConflicthdlr(), and SCIPincludeConflicthdlrBasic().

SCIPconflicthdlrFree()

SCIP_RETCODE SCIPconflicthdlrFree	(	SCIP_CONFLICTHDLR **	conflicthdlr,
		SCIP_SET *	set )

calls destructor and frees memory of conflict handler

Parameters

conflicthdlr	pointer to conflict handler data structure
set	global SCIP settings

Definition at line 1215 of file conflict_graphanalysis.c.

References assert(), BMSfreeMemory, BMSfreeMemoryArrayNull, NULL, SCIP_CALL, SCIP_OKAY, and SCIPclockFree().

Referenced by SCIPconflicthdlrCreate().

SCIPconflicthdlrInit()

SCIP_RETCODE SCIPconflicthdlrInit	(	SCIP_CONFLICTHDLR *	conflicthdlr,
		SCIP_SET *	set )

calls init method of conflict handler

calls initialization method of conflict handler

Parameters

conflicthdlr	conflict handler
set	global SCIP settings

Definition at line 1243 of file conflict_graphanalysis.c.

References assert(), SCIP_Conflicthdlr::conflicttime, SCIP_Conflicthdlr::initialized, SCIP_Conflicthdlr::name, NULL, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPclockReset(), SCIPclockStart(), SCIPclockStop(), SCIPerrorMessage, SCIP_Conflicthdlr::setuptime, and TRUE.

SCIPconflicthdlrExit()

SCIP_RETCODE SCIPconflicthdlrExit	(	SCIP_CONFLICTHDLR *	conflicthdlr,
		SCIP_SET *	set )

calls exit method of conflict handler

Parameters

conflicthdlr	conflict handler
set	global SCIP settings

Definition at line 1280 of file conflict_graphanalysis.c.

References assert(), FALSE, SCIP_Conflicthdlr::initialized, SCIP_Conflicthdlr::name, NULL, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPclockStart(), SCIPclockStop(), SCIPerrorMessage, and SCIP_Conflicthdlr::setuptime.

SCIPconflicthdlrInitsol()

SCIP_RETCODE SCIPconflicthdlrInitsol	(	SCIP_CONFLICTHDLR *	conflicthdlr,
		SCIP_SET *	set )

informs conflict handler that the branch and bound process is being started

Parameters

conflicthdlr	conflict handler
set	global SCIP settings

Definition at line 1311 of file conflict_graphanalysis.c.

References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPclockStart(), SCIPclockStop(), and SCIP_Conflicthdlr::setuptime.

SCIPconflicthdlrExitsol()

SCIP_RETCODE SCIPconflicthdlrExitsol	(	SCIP_CONFLICTHDLR *	conflicthdlr,
		SCIP_SET *	set )

informs conflict handler that the branch and bound process data is being freed

Parameters

conflicthdlr	conflict handler
set	global SCIP settings

Definition at line 1335 of file conflict_graphanalysis.c.

References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPclockStart(), SCIPclockStop(), and SCIP_Conflicthdlr::setuptime.

SCIPconflicthdlrExec()

SCIP_RETCODE SCIPconflicthdlrExec	(	SCIP_CONFLICTHDLR *	conflicthdlr,
		SCIP_SET *	set,
		SCIP_NODE *	node,
		SCIP_NODE *	validnode,
		SCIP_BDCHGINFO **	bdchginfos,
		SCIP_Real *	relaxedbds,
		int	nbdchginfos,
		SCIP_CONFTYPE	conftype,
		SCIP_Bool	usescutoffbound,
		SCIP_Bool	resolved,
		SCIP_RESULT *	result )

calls execution method of conflict handler

Parameters

conflicthdlr	conflict handler
set	global SCIP settings
node	node to add conflict constraint to
validnode	node at which the constraint is valid
bdchginfos	bound change resembling the conflict set
relaxedbds	array with relaxed bounds which are efficient to create a valid conflict
nbdchginfos	number of bound changes in the conflict set
conftype	type of the conflict
usescutoffbound	depends the conflict on the cutoff bound?
resolved	was the conflict set already used to create a constraint?
result	pointer to store the result of the callback method

Definition at line 1359 of file conflict_graphanalysis.c.

References assert(), SCIP_Conflicthdlr::conflicttime, SCIP_Conflicthdlr::name, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_CONSADDED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_INVALIDRESULT, SCIP_OKAY, SCIP_Real, SCIPclockStart(), SCIPclockStop(), SCIPerrorMessage, and SCIPnodeGetDepth().

Referenced by conflictAddConflictCons().

SCIPconflicthdlrSetPriority()

void SCIPconflicthdlrSetPriority	(	SCIP_CONFLICTHDLR *	conflicthdlr,
		SCIP_SET *	set,
		int	priority )

sets priority of conflict handler

Parameters

conflicthdlr	conflict handler
set	global SCIP settings
priority	new priority of the conflict handler

Definition at line 1524 of file conflict_graphanalysis.c.

References assert(), FALSE, NULL, and SCIP_Conflicthdlr::priority.

Referenced by SCIPsetConflicthdlrPriority().

SCIPconflicthdlrSetCopy()

void SCIPconflicthdlrSetCopy

(

SCIP_CONFLICTHDLR *

conflicthdlr

)

set copy method of conflict handler

Parameters

conflicthdlr

conflict handler copy method of the conflict handler

Definition at line 1427 of file conflict_graphanalysis.c.

References assert(), and NULL.

Referenced by SCIPsetConflicthdlrCopy().

SCIPconflicthdlrSetFree()

void SCIPconflicthdlrSetFree

(

SCIP_CONFLICTHDLR *

conflicthdlr

)

set destructor of conflict handler

Parameters

conflicthdlr

conflict handler destructor of conflict handler

Definition at line 1438 of file conflict_graphanalysis.c.

References assert(), and NULL.

Referenced by SCIPsetConflicthdlrFree().

SCIPconflicthdlrSetInit()

void SCIPconflicthdlrSetInit

(

SCIP_CONFLICTHDLR *

conflicthdlr

)

set initialization method of conflict handler

Parameters

conflicthdlr

conflict handler initialization method conflict handler

Definition at line 1450 of file conflict_graphanalysis.c.

References assert(), and NULL.

Referenced by SCIPsetConflicthdlrInit().

SCIPconflicthdlrSetExit()

void SCIPconflicthdlrSetExit

(

SCIP_CONFLICTHDLR *

conflicthdlr

)

set deinitialization method of conflict handler

Parameters

conflicthdlr

conflict handler deinitialization method conflict handler

Definition at line 1461 of file conflict_graphanalysis.c.

References assert(), and NULL.

Referenced by SCIPsetConflicthdlrExit().

SCIPconflicthdlrSetInitsol()

void SCIPconflicthdlrSetInitsol

(

SCIP_CONFLICTHDLR *

conflicthdlr

)

set solving process initialization method of conflict handler

Parameters

conflicthdlr

conflict handler solving process initialization method of conflict handler

Definition at line 1472 of file conflict_graphanalysis.c.

References assert(), and NULL.

Referenced by SCIPsetConflicthdlrInitsol().

SCIPconflicthdlrSetExitsol()

void SCIPconflicthdlrSetExitsol

(

SCIP_CONFLICTHDLR *

conflicthdlr

)

set solving process deinitialization method of conflict handler

Parameters

conflicthdlr

conflict handler solving process deinitialization method of conflict handler

Definition at line 1483 of file conflict_graphanalysis.c.

References assert(), and NULL.

Referenced by SCIPsetConflicthdlrExitsol().

SCIPconflicthdlrEnableOrDisableClocks()

void SCIPconflicthdlrEnableOrDisableClocks	(	SCIP_CONFLICTHDLR *	conflicthdlr,
		SCIP_Bool	enable )

enables or disables all clocks of conflicthdlr, depending on the value of the flag

Parameters

conflicthdlr	the conflict handler for which all clocks should be enabled or disabled
enable	should the clocks of the conflict handler be enabled?

Definition at line 1548 of file conflict_graphanalysis.c.

References assert(), SCIP_Conflicthdlr::conflicttime, NULL, SCIP_Bool, SCIPclockEnableOrDisable(), and SCIP_Conflicthdlr::setuptime.

SCIPconflictGraphApplicable()

SCIP_Bool SCIPconflictGraphApplicable

(

SCIP_SET *

set

)

return TRUE if conflict graph analysis is applicable

Parameters

set	global SCIP settings

Definition at line 1580 of file conflict_graphanalysis.c.

References FALSE, SCIP_Bool, and TRUE.

Referenced by SCIPconflictAnalyze(), and SCIPconflictAnalyzeRemainingBdchgs().

conflictCreateTmpBdchginfo()

SCIP_RETCODE conflictCreateTmpBdchginfo	(	SCIP_CONFLICT *	conflict,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		SCIP_VAR *	var,
		SCIP_BOUNDTYPE	boundtype,
		SCIP_Real	oldbound,
		SCIP_Real	newbound,
		SCIP_BDCHGINFO **	bdchginfo )

creates a temporary bound change information object that is destroyed after the conflict sets are flushed

Parameters

conflict	conflict analysis data
blkmem	block memory
set	global SCIP settings
var	active variable that changed the bounds
boundtype	type of bound for var: lower or upper bound
oldbound	old value for bound
newbound	new value for bound
bdchginfo	pointer to store bound change information

Definition at line 1620 of file conflict_graphanalysis.c.

References assert(), conflictEnsureTmpbdchginfosMem(), SCIP_Conflict::ntmpbdchginfos, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbdchginfoCreate(), SCIP_Conflict::tmpbdchginfos, and var.

Referenced by conflictCreateReconvergenceConss(), and SCIPconflictAnalyzeRemainingBdchgs().

conflictCalcMaxsize()

int conflictCalcMaxsize	(	SCIP_SET *	set,
		SCIP_PROB *	prob )

calculates the maximal size of conflict sets to be used

Parameters

set	global SCIP settings
prob	problem data

Definition at line 1896 of file conflict_graphanalysis.c.

References assert(), MAX, SCIP_Prob::ncontvars, NULL, and SCIP_Prob::nvars.

Referenced by SCIPconflictAnalyze(), SCIPconflictAnalyzeRemainingBdchgs(), and SCIPconflictFlushConss().

SCIPundoBdchgsProof()

SCIP_RETCODE SCIPundoBdchgsProof	(	SCIP_SET *	set,
		SCIP_PROB *	prob,
		int	currentdepth,
		SCIP_Real *	proofcoefs,
		SCIP_Real	prooflhs,
		SCIP_Real *	proofact,
		SCIP_Real *	curvarlbs,
		SCIP_Real *	curvarubs,
		int *	lbchginfoposs,
		int *	ubchginfoposs,
		SCIP_LPBDCHGS *	oldlpbdchgs,
		SCIP_LPBDCHGS *	relaxedlpbdchgs,
		SCIP_Bool *	resolve,
		SCIP_LPI *	lpi )

undoes bound changes on variables, still leaving the given infeasibility proof valid

Parameters

set	global SCIP settings
prob	problem data
currentdepth	current depth in the tree
proofcoefs	coefficients in infeasibility proof
prooflhs	left hand side of proof
proofact	current activity of proof
curvarlbs	current lower bounds of active problem variables
curvarubs	current upper bounds of active problem variables
lbchginfoposs	positions of currently active lower bound change information in variables' arrays
ubchginfoposs	positions of currently active upper bound change information in variables' arrays
oldlpbdchgs	old LP bound changes used for reset the LP bound change, or NULL
relaxedlpbdchgs	relaxed LP bound changes used for reset the LP bound change, or NULL
resolve	pointer to store whether the changed LP should be resolved again, or NULL
lpi	pointer to LPi to access infinity of LP solver; necessary to set correct values

Definition at line 4678 of file conflict_graphanalysis.c.

References addBdchg(), addCand(), assert(), FALSE, i, NULL, nvars, SCIP_Prob::nvars, QUAD, QUAD_TO_DBL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPquadprecProdQD, SCIPquadprecSumDD, SCIPsetAllocBufferArray, SCIPsetDebugMsg, SCIPsetFreeBufferArray, SCIPsetIsEQ(), SCIPsetIsFeasGT(), SCIPsetIsGT(), SCIPsetIsLT(), SCIPsetIsNegative(), SCIPsetIsPositive(), SCIPsetIsZero(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPvarIsInLP(), skipRedundantBdchginfos(), TRUE, var, SCIP_Prob::vars, and vars.

Referenced by SCIPconflictAnalyzePseudo(), undoBdchgsDualfarkas(), and undoBdchgsDualsol().

SCIPconflictAnalyzeRemainingBdchgs()

SCIP_RETCODE SCIPconflictAnalyzeRemainingBdchgs	(	SCIP_CONFLICT *	conflict,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		SCIP_STAT *	stat,
		SCIP_PROB *	prob,
		SCIP_TREE *	tree,
		SCIP_Bool	diving,
		int *	lbchginfoposs,
		int *	ubchginfoposs,
		int *	nconss,
		int *	nliterals,
		int *	nreconvconss,
		int *	nreconvliterals )

applies conflict analysis starting with given bound changes, that could not be undone during previous infeasibility analysis

Parameters

conflict	conflict analysis data
blkmem	block memory of transformed problem
set	global SCIP settings
stat	problem statistics
prob	problem data
tree	branch and bound tree
diving	are we in strong branching or diving mode?
lbchginfoposs	positions of currently active lower bound change information in variables' arrays
ubchginfoposs	positions of currently active upper bound change information in variables' arrays
nconss	pointer to store the number of generated conflict constraints
nliterals	pointer to store the number of literals in generated conflict constraints
nreconvconss	pointer to store the number of generated reconvergence constraints
nreconvliterals	pointer to store the number of literals generated reconvergence constraints

Definition at line 2575 of file conflict_graphanalysis.c.

References assert(), conflictAddBound(), conflictAddConflictBound(), conflictAnalyze(), conflictCalcMaxsize(), conflictCreateTmpBdchginfo(), SCIP_Conflict::conflictset, SCIP_ConflictSet::conflicttype, FALSE, incVSIDS(), NULL, nvars, SCIP_Prob::nvars, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbdchginfoGetBoundtype(), SCIPbdchginfoGetNewbound(), SCIPbdchginfoIsRedundant(), SCIPconflictGraphApplicable(), SCIPconflictInit(), SCIPsetDebugMsg, SCIPvarGetLbLocal(), SCIPvarGetLbLP(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarGetUbLocal(), SCIPvarGetUbLP(), SCIP_ConflictSet::usescutoffbound, var, SCIP_Prob::vars, and vars.

Referenced by conflictAnalyzeLP(), and SCIPconflictAnalyzePseudo().

SCIPconflictInit()

SCIP_RETCODE SCIPconflictInit	(	SCIP_CONFLICT *	conflict,
		SCIP_SET *	set,
		SCIP_STAT *	stat,
		SCIP_PROB *	prob,
		SCIP_CONFTYPE	conftype,
		SCIP_Bool	usescutoffbound )

initializes propagation and resolution conflict analysis by clearing the conflict candidate queues

Parameters

conflict	conflict analysis data
set	global SCIP settings
stat	problem statistics
prob	problem data
conftype	type of the conflict
usescutoffbound	depends the conflict on a cutoff bound?

Definition at line 3420 of file conflict_graphanalysis.c.

References assert(), conflictClear(), conflictClearResolution(), SCIP_Conflict::conflictrow, SCIP_Conflict::conflictset, SCIP_ConflictRow::conflicttype, SCIP_ConflictSet::conflicttype, SCIP_Conflict::count, SCIP_Stat::glbhistory, SCIP_Stat::glbhistorycrun, SCIP_Stat::lastconflictnode, SCIP_Stat::nnodes, NULL, SCIP_Prob::nvars, SCIP_Bool, SCIP_CALL, SCIP_CONFTYPE_BNDEXCEEDING, SCIP_CONFTYPE_INFEASLP, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIPhistoryScaleVSIDS(), SCIPsetDebugMsg, SCIPvarScaleVSIDS(), SCIP_ConflictSet::usescutoffbound, SCIP_Prob::vars, and SCIP_Stat::vsidsweight.

Referenced by conflictCreateReconvergenceConss(), SCIPconflictAnalyzeRemainingBdchgs(), and SCIPinitConflictAnalysis().

SCIPconflictAddBound()

SCIP_RETCODE SCIPconflictAddBound	(	SCIP_CONFLICT *	conflict,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		SCIP_STAT *	stat,
		SCIP_VAR *	var,
		SCIP_BOUNDTYPE	boundtype,
		SCIP_BDCHGIDX *	bdchgidx )

adds variable's bound to conflict candidate queue

Parameters

conflict	conflict analysis data
blkmem	block memory
set	global SCIP settings
stat	dynamic problem statistics
var	problem variable
boundtype	type of bound that was changed: lower or upper bound
bdchgidx	bound change index (time stamp of bound change), or NULL for current time

Definition at line 4175 of file conflict_graphanalysis.c.

References assert(), conflictAddBound(), convertToActiveVar(), FALSE, i, NULL, nvars, scalars, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_MULTAGGR, SCIPbdchgidxIsEarlier(), SCIPbdchginfoGetIdx(), SCIPbdchginfoGetNewbound(), SCIPboundtypeOpposite(), SCIPconflictAddBound(), SCIPvarGetBdchgInfo(), SCIPvarGetMultaggrNVars(), SCIPvarGetMultaggrScalars(), SCIPvarGetMultaggrVars(), SCIPvarGetStatus(), SCIPvarIsActive(), var, and vars.

Referenced by SCIPaddConflictBd(), SCIPaddConflictBinvar(), SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPconflictAddBound(), and SCIPconflictAddRelaxedBound().

SCIPconflictAddRelaxedBound()

SCIP_RETCODE SCIPconflictAddRelaxedBound	(	SCIP_CONFLICT *	conflict,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		SCIP_STAT *	stat,
		SCIP_VAR *	var,
		SCIP_BOUNDTYPE	boundtype,
		SCIP_BDCHGIDX *	bdchgidx,
		SCIP_Real	relaxedbd )

adds variable's bound to conflict candidate queue with the additional information of a relaxed bound

adds variable's bound to conflict candidate queue

Parameters

conflict	conflict analysis data
blkmem	block memory
set	global SCIP settings
stat	dynamic problem statistics
var	problem variable
boundtype	type of bound that was changed: lower or upper bound
bdchgidx	bound change index (time stamp of bound change), or NULL for current time
relaxedbd	the relaxed bound

Definition at line 4236 of file conflict_graphanalysis.c.

References assert(), SCIP_BdChgInfo::bdchgidx, conflictAddBound(), convertToActiveVar(), FALSE, MAX, MIN, NULL, SCIP_BdChgInfo::pos, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_MULTAGGR, SCIPbdchgidxGetPos(), SCIPbdchgidxIsEarlier(), SCIPbdchginfoGetDepth(), SCIPbdchginfoGetIdx(), SCIPbdchginfoGetNewbound(), SCIPbdchginfoGetOldbound(), SCIPbdchginfoGetPos(), SCIPbdchginfoIsRedundant(), SCIPconflictAddBound(), SCIPsetDebugMsg, SCIPsetIsGE(), SCIPsetIsGT(), SCIPsetIsLE(), SCIPsetIsLT(), SCIPvarAdjustLb(), SCIPvarAdjustUb(), SCIPvarGetBdchgInfo(), SCIPvarGetBdchgInfoLb(), SCIPvarGetBdchgInfoUb(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarIsActive(), and var.

Referenced by SCIPaddConflictRelaxedBd(), SCIPaddConflictRelaxedLb(), and SCIPaddConflictRelaxedUb().

SCIPconflictIsVarUsed()

SCIP_RETCODE SCIPconflictIsVarUsed	(	SCIP_CONFLICT *	conflict,
		SCIP_VAR *	var,
		SCIP_SET *	set,
		SCIP_BOUNDTYPE	boundtype,
		SCIP_BDCHGIDX *	bdchgidx,
		SCIP_Bool *	used )

checks if the given variable is already part of the current conflict set or queued for resolving with the same or even stronger bound

Parameters

conflict	conflict analysis data
var	problem variable
set	global SCIP settings
boundtype	type of bound for which the score should be increased
bdchgidx	bound change index (time stamp of bound change), or NULL for current time
used	pointer to store if the variable is already used

Definition at line 4400 of file conflict_graphanalysis.c.

References assert(), convertToActiveVar(), SCIP_Conflict::count, FALSE, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_MULTAGGR, SCIPABORT, SCIPerrorMessage, SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPsetDebugMsg, SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarIsActive(), TRUE, and var.

Referenced by SCIPisConflictVarUsed().

SCIPconflictGetVarLb()

SCIP_Real SCIPconflictGetVarLb	(	SCIP_CONFLICT *	conflict,
		SCIP_VAR *	var )

returns the conflict lower bound if the variable is present in the current conflict set; otherwise the global lower bound

Parameters

conflict	conflict analysis data
var	problem variable

Definition at line 444 of file conflict_general.c.

References assert(), SCIP_Conflict::count, EPSGE, SCIP_Real, SCIPvarGetLbGlobal(), and var.

Referenced by SCIPgetConflictVarLb().

SCIPconflictGetVarUb()

SCIP_Real SCIPconflictGetVarUb	(	SCIP_CONFLICT *	conflict,
		SCIP_VAR *	var )

returns the conflict upper bound if the variable is present in the current conflict set; otherwise the global upper bound

Parameters

conflict	conflict analysis data
var	problem variable

Definition at line 461 of file conflict_general.c.

References assert(), SCIP_Conflict::count, EPSLE, SCIP_Real, SCIPvarGetUbGlobal(), and var.

Referenced by SCIPgetConflictVarUb().

SCIPrunBoundHeuristic()

SCIP_RETCODE SCIPrunBoundHeuristic	(	SCIP_CONFLICT *	conflict,
		SCIP_SET *	set,
		SCIP_STAT *	stat,
		SCIP_PROB *	origprob,
		SCIP_PROB *	transprob,
		SCIP_TREE *	tree,
		SCIP_REOPT *	reopt,
		SCIP_LP *	lp,
		SCIP_LPI *	lpi,
		SCIP_EVENTFILTER *	eventfilter,
		BMS_BLKMEM *	blkmem,
		SCIP_Real *	proofcoefs,
		SCIP_Real *	prooflhs,
		SCIP_Real *	proofactivity,
		SCIP_Real *	curvarlbs,
		SCIP_Real *	curvarubs,
		int *	lbchginfoposs,
		int *	ubchginfoposs,
		int *	iterations,
		SCIP_Bool	marklpunsolved,
		SCIP_Bool *	dualproofsuccess,
		SCIP_Bool *	valid )

try to find a subset of changed bounds leading to an infeasible LP

1. call undoBdchgsDualfarkas() or undoBdchgsDualsol() -> update lb/ubchginfoposs arrays -> store additional changes in bdchg and curvarlbs/ubs arrays -> apply additional changes to the LPI
2. (optional) if additional bound changes were undone: -> resolve LP -> goto 1.
3. redo all bound changes in the LPI to restore the LPI to its original state
4. analyze conflict -> put remaining changed bounds (see lb/ubchginfoposs arrays) into starting conflict set

Parameters

conflict	conflict data
set	global SCIP settings
stat	problem statistics
origprob	original problem
transprob	transformed problem
tree	branch and bound tree
reopt	reoptimization data
lp	LP data
lpi	LPI data
eventfilter	global event filter
blkmem	block memory
proofcoefs	coefficients in the proof constraint
prooflhs	lhs of the proof constraint
proofactivity	maximal activity of the proof constraint
curvarlbs	current lower bounds of active problem variables
curvarubs	current upper bounds of active problem variables
lbchginfoposs	positions of currently active lower bound change information in variables' arrays
ubchginfoposs	positions of currently active upper bound change information in variables' arrays
iterations	pointer to store the total number of LP iterations used
marklpunsolved	whether LP should be marked unsolved after analysis (needed for strong branching)
dualproofsuccess	pointer to store success result of dual proof analysis
valid	pointer to store whether the result is still a valid proof

Definition at line 5188 of file conflict_graphanalysis.c.

References addSideRemoval(), assert(), SCIP_LPBdChgs::bdchginds, SCIP_LPBdChgs::bdchglbs, SCIP_LPBdChgs::bdchgubs, BMSclearMemoryArray, SCIP_Stat::conflictlptime, SCIP_Conflict::conflictset, SCIP_ConflictSet::conflicttype, SCIP_Lp::dualchecked, SCIP_Lp::dualfeasible, FALSE, i, lpbdchgsCreate(), lpbdchgsFree(), lpbdchgsReset(), SCIP_Lp::lpiitlim, SCIP_Lp::lpiobjlim, SCIP_Lp::lpobjval, SCIP_Lp::lpsolstat, SCIP_LPBdChgs::nbdchgs, SCIP_Stat::nconflictlpiterations, SCIP_Stat::nconflictlps, NULL, objval, SCIP_Lp::primalchecked, SCIP_Lp::primalfeasible, r, SCIP_Bool, SCIP_CALL, SCIP_CONFTYPE_INFEASLP, SCIP_INVALID, SCIP_LONGINT_FORMAT, SCIP_LPERROR, SCIP_LPPAR_LPITLIM, SCIP_LPPAR_OBJLIM, SCIP_LPSOLSTAT_NOTSOLVED, SCIP_OKAY, SCIP_Real, SCIPaggrRowCreate(), SCIPaggrRowFree(), SCIPaggrRowGetInds(), SCIPaggrRowGetNNz(), SCIPaggrRowGetProbvarValue(), SCIPaggrRowGetRhs(), SCIPclockStart(), SCIPclockStop(), SCIPconflictAnalyzeDualProof(), SCIPgetDualProof(), SCIPgetFarkasProof(), SCIPlpDivingObjChanged(), SCIPlpGetNCols(), SCIPlpGetNRows(), SCIPlpGetRows(), SCIPlpiChgBounds(), SCIPlpiChgSides(), SCIPlpiGetIterations(), SCIPlpiGetObjval(), SCIPlpiInfinity(), SCIPlpiIsDualFeasible(), SCIPlpiIsObjlimExc(), SCIPlpiIsPrimalInfeasible(), SCIPlpiSetIntpar(), SCIPlpiSetRealpar(), SCIPlpiSolveDual(), SCIPprobAllColsInLP(), SCIPprobGetNVars(), SCIPprobGetVars(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetRhs(), SCIProwIsLocal(), SCIPsetAllocBufferArray, SCIPsetDebugMsg, SCIPsetFreeBufferArray, SCIPtreeGetCurrentDepth(), SCIPtreeGetEffectiveRootDepth(), SCIPvarGetProbindex(), SCIP_Lp::solved, undoBdchgsDualfarkas(), undoBdchgsDualsol(), SCIP_ConflictSet::usescutoffbound, valid, and vars.

Referenced by conflictAnalyzeLP().

conflictsetPrint()

void conflictsetPrint

(

SCIP_CONFLICTSET *

conflictset

)

Parameters

conflictset

conflict set

References SCIP_Bool.

Referenced by conflictAddConflictCons(), conflictInsertConflictset(), and SCIPconflictFlushConss().

bdchginfoIsInvalid()

SCIP_Bool bdchginfoIsInvalid	(	SCIP_CONFLICT *	conflict,
		SCIP_BDCHGINFO *	bdchginfo )

check if the bound change info (which is the potential next candidate which is queued) is valid for the current conflict analysis; a bound change info can get invalid if after this one was added to the queue, a weaker bound change was added to the queue (due the bound widening idea) which immediately makes this bound change redundant; due to the priority we did not removed that bound change info since that cost O(log(n)); hence we have to skip/ignore it now

The following situations can occur before for example the bound change info (x >= 3) is potentially popped from the queue.

Postcondition: the reason why (x >= 3) was queued is that at this time point no lower bound of x was involved yet in the current conflict or the lower bound which was involved until then was stronger, e.g., (x >= 2).

1) during the time until (x >= 3) gets potentially popped no weaker lower bound was added to the queue, in that case the conflictlbcount is valid and conflictlb is 3; that is (var->conflictlbcount == conflict->count && var->conflictlb == 3)

2) a weaker bound change info gets queued (e.g., x >= 4); this bound change is popped before (x >= 3) since it has higher priority (which is the time stamp of the bound change info and (x >= 4) has to be done after (x >= 3) during propagation or branching)

a) if (x >= 4) is popped and added to the conflict set the conflictlbcount is still valid and conflictlb is at most 4; that is (var->conflictlbcount == conflict->count && var->conflictlb >= 4); it follows that any bound change info which is stronger than (x >= 4) gets ignored (for example x >= 2)

b) if (x >= 4) is popped and resolved without introducing a new lower bound on x until (x >= 3) is a potentially candidate the conflictlbcount indicates that bound change is currently not present; that is (var->conflictlbcount != conflict->count)

c) if (x >= 4) is popped and resolved and a new lower bound on x (e.g., x >= 2) is introduced until (x >= 3) is pooped, the conflictlbcount indicates that bound change is currently present; that is (var->conflictlbcount == conflict->count); however the (x >= 3) only has be explained if conflictlb matches that one; that is (var->conflictlb == bdchginfo->newbound); otherwise it redundant/invalid.

Parameters

conflict	conflict analysis data
bdchginfo	bound change information

Definition at line 2749 of file conflict_graphanalysis.c.

References assert(), SCIP_Conflict::count, FALSE, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIPbdchginfoGetBoundtype(), SCIPbdchginfoGetNewbound(), SCIPbdchginfoGetVar(), SCIPvarIsBinary(), TRUE, and var.

Referenced by conflictFirstCand(), conflictRemoveCand(), conflictResolveBound(), and conflictsetAddBounds().