Detailed Description

Methods for generalized resolution conflict analysis.

Author: Gioni Mexi

This file implements a conflict analysis method based on generalized resolution, as detailed in the paper:

Gioni Mexi, et al. "Cut-based Conflict Analysis in Mixed Integer Programming." arXiv preprint arXiv:2410.15110 (2024).

The generalized resolution conflict analysis procedure starts with an initial conflict row and it iteratively aggregates this row with a reason row—the row that propagated the bound change causing the conflict. The aggregation cancels the coefficient of the resolving variable. This process continues until a first unique implication point (FUIP) is reached. If the aggregation does not yield a valid (infeasible) row, the algorithm attempts to reduce the reason row (e.g., using MIR reduction) and retries the aggregation. Once a valid conflict row with negative slack is generated, a conflict constraint is constructed and added to the problem.

Definition in file conflict_resolution.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 "scip/type_branch.h"
#include "scip/type_var.h"
#include "scip/type_prob.h"
#include "scip/type_event.h"

Go to the source code of this file.

Functions
SCIP_Bool	SCIPconflictResolutionApplicable (SCIP_SET *set)
SCIP_Longint	SCIPconflictGetNResConflictConss (SCIP_CONFLICT *conflict)
SCIP_Longint	SCIPconflictGetNResSuccess (SCIP_CONFLICT *conflict)
SCIP_Longint	SCIPconflictGetNResLargeCoefs (SCIP_CONFLICT *conflict)
SCIP_Longint	SCIPconflictGetNResLongConflicts (SCIP_CONFLICT *conflict)
SCIP_Longint	SCIPconflictGetNResCalls (SCIP_CONFLICT *conflict)
SCIP_RETCODE	SCIPconflictAddConflictCon (SCIP_CONFLICT conflict, 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, SCIP_CONFLICTROW conflictrow, SCIP_Bool *success)
SCIP_RETCODE	SCIPconflictInitRows (SCIP_CONFLICT conflict, BMS_BLKMEM blkmem)
void	SCIPconflictRowFree (SCIP_CONFLICTROW *row, BMS_BLKMEM blkmem)

Function Documentation

◆ SCIPconflictResolutionApplicable()

SCIP_Bool SCIPconflictResolutionApplicable ( SCIP_SET * set )

return TRUE if generalized resolution conflict analysis is applicable

Parameters

set	global SCIP settings

Definition at line 1161 of file conflict_resolution.c.

References FALSE, SCIP_Bool, and TRUE.

Referenced by SCIPconflictAnalyzeResolution().

◆ SCIPconflictGetNResConflictConss()

SCIP_Longint SCIPconflictGetNResConflictConss ( SCIP_CONFLICT * conflict )

gets number of conflict constraints found during propagation with the generalized resolution conflict analysis

Parameters

conflict conflict analysis data

Definition at line 233 of file conflict_resolution.c.

References assert(), SCIP_Conflict::nresconfconss, NULL, and SCIP_Longint.

Referenced by SCIPgetNConflictConssFound(), and SCIPprintConflictStatistics().

◆ SCIPconflictGetNResSuccess()

SCIP_Longint SCIPconflictGetNResSuccess ( SCIP_CONFLICT * conflict )

gets number of calls to generalized resolution conflict analysis that yield at least one conflict constraint

Parameters

conflict conflict analysis data

Definition at line 243 of file conflict_resolution.c.

References assert(), SCIP_Conflict::nressuccess, NULL, and SCIP_Longint.

Referenced by SCIPprintConflictStatistics().

◆ SCIPconflictGetNResLargeCoefs()

SCIP_Longint SCIPconflictGetNResLargeCoefs ( SCIP_CONFLICT * conflict )

gets number of calls to generalized resolution conflict analysis terminating because of large coefficients

Parameters

conflict conflict analysis data

Definition at line 254 of file conflict_resolution.c.

References assert(), SCIP_Conflict::nreslargecoefs, NULL, and SCIP_Longint.

Referenced by SCIPprintConflictStatistics().

◆ SCIPconflictGetNResLongConflicts()

SCIP_Longint SCIPconflictGetNResLongConflicts ( SCIP_CONFLICT * conflict )

gets number of calls to generalized resolution conflict analysis terminating because of long conflicts

Parameters

conflict conflict analysis data

Definition at line 264 of file conflict_resolution.c.

References assert(), SCIP_Conflict::nreslongconfs, NULL, and SCIP_Longint.

Referenced by SCIPprintConflictStatistics().

◆ SCIPconflictGetNResCalls()

SCIP_Longint SCIPconflictGetNResCalls ( SCIP_CONFLICT * conflict )

gets number of calls to generalized resolution conflict analysis

Parameters

conflict conflict analysis data

Definition at line 274 of file conflict_resolution.c.

References assert(), SCIP_Conflict::nrescalls, NULL, and SCIP_Longint.

Referenced by SCIPprintConflictStatistics().

◆ SCIPconflictAddConflictCon()

SCIP_RETCODE SCIPconflictAddConflictCon	(	SCIP_CONFLICT *	conflict,
		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,
		SCIP_CONFLICTROW *	conflictrow,
		SCIP_Bool *	success )

create constraints out of the conflict row and add them to the problem

create conflict constraints out of conflict row and add them to the problem

Parameters

conflict	conflict analysis data
blkmem	block memory
set	global SCIP settings
stat	dynamic problem statistics
transprob	transformed problem
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
conflictrow	conflict row to add to the tree
success	true if the conflict is added to the problem