Implements a method for finding and adding cluster cuts. More...

#include "fractional_circuit_cuts.h"
#include "utils.h"

Include dependency graph for fractional_circuit_cuts.c:

Data Structures
struct	FC_info
	A collection of storage items for finding fractional cuts. More...

Macros
#define	DEFAULT_ADD_CUTS TRUE

#define	DEFAULT_ADD_CUTS_TO_POOL FALSE

Functions
static SCIP_RETCODE	addClusterCut (SCIP scip, SCIP_ROW cut, SCIP_SOL sol, SCIP_Bool was_added, SCIP_Bool forcecuts, SCIP_Bool is_efficacious, SCIP_Bool cutoff)

static SCIP_RETCODE	addClusterCutOverNodes (SCIP scip, SCIP_CONSHDLR conshdlr, SCIP_SOL sol, SCIP_VAR included, SCIP_VAR excluded, ParentSetData psd, int nodes, int num, SCIP_Bool was_added, SCIP_Bool forcecuts, SCIP_Bool is_efficacious, SCIP_Bool cutoff)

static SCIP_RETCODE	allocateSuccessorsMemory (FC_info *fc_info)

static SCIP_RETCODE	allocDataStructures (FC_info *fc_info)

static void	clearAdjMatrix (FC_info *fc_info)

static void	clearDataStructures (FC_info *fc_info)

static void	clearDistanceStructure (FC_info *fc_info)

static void	clearNumSuccessors (FC_info *fc_info)

static void	clearPredecessorStructure (FC_info *fc_info)

static void	clearQueueStructure (FC_info *fc_info)

static void	countNumSuccessors (FC_info *fc_info)

static SCIP_RETCODE	createClusterCut (SCIP scip, SCIP_CONSHDLR conshdlr, SCIP_VAR include, int num_include, SCIP_VAR exclude, int num_exclude, int num, int num_nodes_excluded, SCIP_ROW **cut)

static SCIP_RETCODE	extractNodesInCycle (FC_info fc_info, int start, int cycle, int cycle_length)

SCIP_RETCODE	FC_addParams (SCIP *scip)

SCIP_RETCODE	FC_findCuts (SCIP scip, SCIP_CONSHDLR conshdlr, ParentSetData psd, SCIP_SOL sol, CircuitCutsStorage ccs, int nGen, SCIP_Bool forcecuts, SCIP_Bool found_efficacious_ptr, SCIP_Bool cutoff)

static int	findCycleLength (FC_info *fc_info, int start)

static SCIP_RETCODE	findSuccessors (FC_info *fc_info)

static void	freeDataStructures (FC_info *fc_info)

static int	getClosestQueuedNode (FC_info *fc_info)

static void	initAdjMatrix (FC_info fc_info, SCIP_SOL sol, ParentSetData *psd)

static void	initialiseForStartNode (FC_info *fc_info, int start)

static SCIP_Bool	isLessThanOne (SCIP *scip, float value)

static void	partitionVariablesToInclude (ParentSetData psd, int node, int nodes, int num, SCIP_VAR *included, int num_vars_included, SCIP_VAR *excluded, int num_vars_excluded)

static SCIP_Bool	queueEmpty (FC_info *fc_info)

static void	removeFromQueue (FC_info *fc_info, int node)

static void	roundAdjMatrix (FC_info *fc_info)

static SCIP_Bool	runDijkstra (FC_info fc_info, SCIP scip, int start)

static void	setAdjMatrix (FC_info fc_info, SCIP_SOL sol, ParentSetData *psd)

static void	setDistanceTo (FC_info *fc_info, int node, SCIP_Real value)

static void	setSuccessors (FC_info *fc_info)

static SCIP_Bool	shouldIncludeVariableInCut (int parent_set, int parent_set_size, int nodes, int num)

static void	updateDistance (FC_info *fc_info, int from_node, int to_node)

static void	updateNeighboursDistances (FC_info *fc_info, int from_node)

Detailed Description

Implements a method for finding and adding cluster cuts.

The technique involves finding cycles in the current fractional solution of the linear relaxation, and adding cuts to rule out some of these.

Function Documentation

◆ addClusterCut()

static SCIP_RETCODE addClusterCut	(	SCIP *	scip,
		SCIP_ROW *	cut,
		SCIP_SOL *	sol,
		SCIP_Bool *	was_added,
		SCIP_Bool	forcecuts,
		SCIP_Bool *	is_efficacious,
		SCIP_Bool *	cutoff
	)

static

Parameters

scip	SCIP data structure

◆ addClusterCutOverNodes()

static SCIP_RETCODE addClusterCutOverNodes	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr,
		SCIP_SOL *	sol,
		SCIP_VAR **	included,
		SCIP_VAR **	excluded,
		ParentSetData *	psd,
		int *	nodes,
		int	num,
		SCIP_Bool *	was_added,
		SCIP_Bool	forcecuts,
		SCIP_Bool *	is_efficacious,
		SCIP_Bool *	cutoff
	)

static

Parameters

scip	SCIP data structure

Referenced by FC_findCuts().

◆ allocateSuccessorsMemory()

static SCIP_RETCODE allocateSuccessorsMemory ( FC_info * fc_info )

static

Parameters

fc_info Fractional cuts info/storage

Referenced by findSuccessors().

◆ allocDataStructures()

static SCIP_RETCODE allocDataStructures ( FC_info * fc_info )

static

Parameters

fc_info Fractional cuts info/storage

Referenced by FC_findCuts().

◆ clearAdjMatrix()

static void clearAdjMatrix ( FC_info * fc_info )

static

Parameters

fc_info Fractional cuts info/storage

Referenced by initAdjMatrix().

◆ clearDataStructures()

static void clearDataStructures ( FC_info * fc_info )

static

Parameters

fc_info Fractional cuts info/storage

References clearDistanceStructure(), clearPredecessorStructure(), and clearQueueStructure().

Referenced by initialiseForStartNode().

Here is the call graph for this function:

◆ clearDistanceStructure()

static void clearDistanceStructure ( FC_info * fc_info )

static

Parameters

fc_info Fractional cuts info/storage

Referenced by clearDataStructures().

◆ clearNumSuccessors()

static void clearNumSuccessors ( FC_info * fc_info )

static

Parameters

fc_info Fractional cuts info/storage

Referenced by findSuccessors().

◆ clearPredecessorStructure()

static void clearPredecessorStructure ( FC_info * fc_info )

static

Parameters

fc_info Fractional cuts info/storage

Referenced by clearDataStructures().

◆ clearQueueStructure()

static void clearQueueStructure ( FC_info * fc_info )

static

Parameters

fc_info Fractional cuts info/storage

Referenced by clearDataStructures().

◆ countNumSuccessors()

static void countNumSuccessors ( FC_info * fc_info )

static

Parameters

fc_info Fractional cuts info/storage

Referenced by findSuccessors().

◆ createClusterCut()

static SCIP_RETCODE createClusterCut	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr,
		SCIP_VAR **	include,
		int	num_include,
		SCIP_VAR **	exclude,
		int	num_exclude,
		int	num,
		int	num_nodes_excluded,
		SCIP_ROW **	cut
	)

static

Parameters

scip	SCIP data structure

◆ extractNodesInCycle()

static SCIP_RETCODE extractNodesInCycle	(	FC_info *	fc_info,
		int	start,
		int **	cycle,
		int *	cycle_length
	)

static

Parameters

fc_info Fractional cuts info/storage

References findCycleLength().

Referenced by FC_findCuts().

Here is the call graph for this function:

◆ FC_addParams()

SCIP_RETCODE FC_addParams ( SCIP * scip )

Parameters

scip	SCIP data structure

References UT_addBoolParam().

Here is the call graph for this function:

◆ FC_findCuts()

SCIP_RETCODE FC_findCuts	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr,
		ParentSetData *	psd,
		SCIP_SOL *	sol,
		CircuitCutsStorage *	ccs,
		int *	nGen,
		SCIP_Bool	forcecuts,
		SCIP_Bool *	found_efficacious_ptr,
		SCIP_Bool *	cutoff
	)

Parameters

scip	SCIP data structure

References addClusterCutOverNodes(), allocDataStructures(), extractNodesInCycle(), findSuccessors(), freeDataStructures(), initAdjMatrix(), ParentSetData::n, and runDijkstra().

Here is the call graph for this function:

◆ findCycleLength()

static int findCycleLength	(	FC_info *	fc_info,
		int	start
	)

static

Parameters

fc_info Fractional cuts info/storage

Referenced by extractNodesInCycle().

◆ findSuccessors()

static SCIP_RETCODE findSuccessors ( FC_info * fc_info )

static

Parameters

fc_info Fractional cuts info/storage

References allocateSuccessorsMemory(), clearNumSuccessors(), countNumSuccessors(), and setSuccessors().

Referenced by FC_findCuts().

Here is the call graph for this function:

◆ freeDataStructures()

static void freeDataStructures ( FC_info * fc_info )

static

Parameters

fc_info Fractional cuts info/storage

Referenced by FC_findCuts().

◆ getClosestQueuedNode()

static int getClosestQueuedNode ( FC_info * fc_info )

static

Parameters

fc_info Fractional cuts info/storage

Referenced by runDijkstra().

◆ initAdjMatrix()

static void initAdjMatrix	(	FC_info *	fc_info,
		SCIP_SOL *	sol,
		ParentSetData *	psd
	)

static

Parameters

fc_info Fractional cuts info/storage

References clearAdjMatrix(), roundAdjMatrix(), and setAdjMatrix().

Referenced by FC_findCuts().

Here is the call graph for this function:

◆ initialiseForStartNode()

static void initialiseForStartNode	(	FC_info *	fc_info,
		int	start
	)

static

Parameters

fc_info Fractional cuts info/storage

References clearDataStructures(), and setDistanceTo().

Referenced by runDijkstra().

Here is the call graph for this function:

◆ isLessThanOne()

static SCIP_Bool isLessThanOne	(	SCIP *	scip,
		float	value
	)

static

Parameters

scip	SCIP data structure

Referenced by runDijkstra().

◆ queueEmpty()

static SCIP_Bool queueEmpty ( FC_info * fc_info )

static

Parameters

fc_info Fractional cuts info/storage

Referenced by runDijkstra().

◆ removeFromQueue()

static void removeFromQueue	(	FC_info *	fc_info,
		int	node
	)

static

Parameters

fc_info Fractional cuts info/storage

Referenced by runDijkstra().

◆ roundAdjMatrix()

static void roundAdjMatrix ( FC_info * fc_info )

static

Parameters

fc_info Fractional cuts info/storage

Referenced by initAdjMatrix().

◆ runDijkstra()

static SCIP_Bool runDijkstra	(	FC_info *	fc_info,
		SCIP *	scip,
		int	start
	)

static

Parameters

fc_info	Fractional cuts info/storage
scip	SCIP data structure

References getClosestQueuedNode(), initialiseForStartNode(), isLessThanOne(), queueEmpty(), removeFromQueue(), setDistanceTo(), and updateNeighboursDistances().

Referenced by FC_findCuts().

Here is the call graph for this function:

◆ setAdjMatrix()

static void setAdjMatrix	(	FC_info *	fc_info,
		SCIP_SOL *	sol,
		ParentSetData *	psd
	)

static

Parameters

fc_info Fractional cuts info/storage

References ParentSetData::n, ParentSetData::nParents, ParentSetData::nParentSets, ParentSetData::ParentSets, and ParentSetData::PaVars.

Referenced by initAdjMatrix().

◆ setDistanceTo()

static void setDistanceTo	(	FC_info *	fc_info,
		int	node,
		SCIP_Real	value
	)

static

Parameters

fc_info Fractional cuts info/storage

Referenced by initialiseForStartNode(), and runDijkstra().

◆ setSuccessors()

static void setSuccessors ( FC_info * fc_info )

static

Parameters

fc_info Fractional cuts info/storage

Referenced by findSuccessors().

◆ updateDistance()

static void updateDistance	(	FC_info *	fc_info,
		int	from_node,
		int	to_node
	)

static

Parameters

fc_info Fractional cuts info/storage

Referenced by updateNeighboursDistances().

◆ updateNeighboursDistances()

static void updateNeighboursDistances	(	FC_info *	fc_info,
		int	from_node
	)

static

Parameters

fc_info Fractional cuts info/storage

References updateDistance().

Referenced by runDijkstra().

Here is the call graph for this function:

Data Structures

Macros

Functions

Detailed Description

Function Documentation

◆ addClusterCut()

◆ addClusterCutOverNodes()

◆ allocateSuccessorsMemory()

◆ allocDataStructures()

◆ clearAdjMatrix()

◆ clearDataStructures()

◆ clearDistanceStructure()

◆ clearNumSuccessors()

◆ clearPredecessorStructure()

◆ clearQueueStructure()

◆ countNumSuccessors()

◆ createClusterCut()

◆ extractNodesInCycle()

◆ FC_addParams()

◆ FC_findCuts()

◆ findCycleLength()

◆ findSuccessors()

◆ freeDataStructures()

◆ getClosestQueuedNode()

◆ initAdjMatrix()

◆ initialiseForStartNode()

◆ isLessThanOne()

◆ queueEmpty()

◆ removeFromQueue()

◆ roundAdjMatrix()

◆ runDijkstra()

◆ setAdjMatrix()

◆ setDistanceTo()

◆ setSuccessors()

◆ updateDistance()

◆ updateNeighboursDistances()