GOBNILP  f164d83
Macros | Functions
circuit_cuts.c File Reference

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

#include "circuit_cuts.h"
#include "utils.h"
Include dependency graph for circuit_cuts.c:

Macros

#define DEFAULT_ADD_CLUSTER_CUTS   TRUE
 
#define DEFAULT_ADD_CLUSTER_CUTS_TO_POOL   FALSE
 
#define DEFAULT_ADD_CYCLE_CUTS   FALSE
 
#define DEFAULT_ADD_CYCLE_CUTS_TO_POOL   FALSE
 
#define DEFAULT_ADD_FRACTIONAL_CUTS   TRUE
 
#define DEFAULT_MAX_CYCLE_LENGTH   6
 
#define DEFAULT_MAX_CYCLES   1000
 

Functions

static SCIP_RETCODE addCuts (SCIP *scip, SCIP_CONSHDLR *conshdlr, ParentSetData *psd, SCIP_SOL *sol, SCIP_VAR **included_cluster, SCIP_VAR **excluded_cluster, SCIP_VAR **included_cycle, SCIP_VAR **excluded_cycle, VectorList *cycles, SCIP_Bool forcecuts, SCIP_Bool *found_efficacious_ptr, SCIP_Bool *cutoff, CircuitCutsStorage *ccs)
 Adds cuts to rule out each of the found cycles. More...
 
SCIP_RETCODE CC_addParams (SCIP *scip)
 Adds parameters to those recognised by SCIP. More...
 
SCIP_RETCODE CC_finalise (SCIP *scip, CircuitCutsStorage *ccs, int n)
 Frees all memory allocated by CC_initialise. More...
 
SCIP_RETCODE CC_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)
 Find cuts to rule out cycles in the current solution. More...
 
SCIP_RETCODE CC_initialise (SCIP *scip, CircuitCutsStorage *ccs, ParentSetData *data)
 Sets up data structures once, to avoid creating them everytime the separation routine is called. More...
 
static SCIP_Bool circuit (SCIP *scip, Vector *nodes, int current_index, int start_index, VectorList *b, SCIP_Bool *blocked, Stack *s, SCIP_Real **adj_matrix, VectorList *cycles, SCIP_Real weight, int max_cycles, int max_cycle_length)
 Find the elementary cycles of a SCC. More...
 
static SCIP_RETCODE findStronglyConnectedComponents (int current_node, int *current_index, int n, Vector *index_array, Vector *lowlink, Stack *s, SCIP_Real **adj_matrix, VectorList *components)
 Finds Strongly Connected Components in the current solution. More...
 
static SCIP_Bool isLessThanOne (SCIP *scip, float value)
 Return whether a value is strictly less than 1 Uses SCIPepsilon to guard against rounding errors. More...
 
static SCIP_RETCODE shouldIncludeInCuts (Vector *cycle, ParentSetData *psd, int previous_node, int child, int parent_set, SCIP_Bool *in_cluster, SCIP_Bool *in_cycle)
 Whether a parent set should be included in the current cut. More...
 
static SCIP_RETCODE unblock (int u, Vector *nodes, VectorList *b, SCIP_Bool *blocked)
 Unblocks a node during the cycle finding algorithm. More...
 

Detailed Description

Implements a method for finding and adding cluster cuts.

The technique involves finding all elementary circuits in the current (possibly partially fractional) solution of the linear relaxation, and adding cuts to rule out each of these.

Function Documentation

◆ addCuts()

static SCIP_RETCODE addCuts ( SCIP *  scip,
SCIP_CONSHDLR *  conshdlr,
ParentSetData psd,
SCIP_SOL *  sol,
SCIP_VAR **  included_cluster,
SCIP_VAR **  excluded_cluster,
SCIP_VAR **  included_cycle,
SCIP_VAR **  excluded_cycle,
VectorList cycles,
SCIP_Bool  forcecuts,
SCIP_Bool *  found_efficacious_ptr,
SCIP_Bool *  cutoff,
CircuitCutsStorage ccs 
)
static

Adds cuts to rule out each of the found cycles.

Parameters
scipThe SCIP instance.
conshdlrThe constraint handler to add cuts for.
solThe current solution.
forcecutsWhether to force cuts to be added
found_efficacious_ptrWhether at least one efficacious cut was added.
Returns
SCIP_OKAY if the operation succeded or an error othewrwise.

References CircuitCutsStorage::add_cluster_cuts, CircuitCutsStorage::add_cluster_cuts_to_pool, CircuitCutsStorage::add_cycle_cuts, CircuitCutsStorage::add_cycle_cuts_to_pool, Vector::items, VectorList::items, ParentSetData::nParentSets, ParentSetData::PaVars, shouldIncludeInCuts(), Vector::size, and VectorList::size.

Referenced by CC_findCuts().

Here is the call graph for this function:

◆ CC_addParams()

SCIP_RETCODE CC_addParams ( SCIP *  scip)

Adds parameters to those recognised by SCIP.

Parameters
scipThe SCIP instance to add parameters to.
Returns
SCIP_OKAY if the operation succeded or an error othewrwise.
Parameters
scipSCIP data structure

References UT_addBoolParam().

Here is the call graph for this function:

◆ CC_finalise()

SCIP_RETCODE CC_finalise ( SCIP *  scip,
CircuitCutsStorage ccs,
int  n 
)

Frees all memory allocated by CC_initialise.

Returns
SCIP_OKAY if the finalisation was successful or an appropriate error code otherwise.
Parameters
scipSCIP data structure
ccsCircuit storage to free
nNumber of DAG nodes

References StackDelete(), VectorDelete(), and VectorListDelete().

Referenced by SCIP_DECL_CONSDELETE().

Here is the call graph for this function:

◆ CC_findCuts()

SCIP_RETCODE CC_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 
)

Find cuts to rule out cycles in the current solution.

Parameters
scipThe SCIP instance the cuts are to be found for.
conshdlrThe constraint handler responsible for the cuts.
solThe current relaxed solution.
nGenThe number of cuts that were added.
forcecutsWhether to force cuts to be added
found_efficacious_ptrA pointer to return whether any efficacious cuts were found.
Returns
SCIP_OKAY if the algorithm terminated correctly, or an appropriate error otherwise.

References CircuitCutsStorage::add_cluster_cuts, CircuitCutsStorage::add_cluster_cuts_to_pool, CircuitCutsStorage::add_cycle_cuts, CircuitCutsStorage::add_cycle_cuts_to_pool, CircuitCutsStorage::add_fractional_cuts, addCuts(), circuit(), findStronglyConnectedComponents(), Vector::items, VectorList::items, CircuitCutsStorage::max_cycle_length, CircuitCutsStorage::max_cycles, ParentSetData::n, ParentSetData::nParents, ParentSetData::nParentSets, ParentSetData::ParentSets, ParentSetData::PaVars, Vector::size, VectorList::size, VectorClear(), and VectorListClear().

Referenced by DagClusterSeparate().

Here is the call graph for this function:

◆ CC_initialise()

SCIP_RETCODE CC_initialise ( SCIP *  scip,
CircuitCutsStorage ccs,
ParentSetData data 
)

Sets up data structures once, to avoid creating them everytime the separation routine is called.

Parameters
scipThe SCIP instance the separation is to take place in.
dataThe problem data that the separation will occur on.
Returns
SCIP_OKAY if the initialisation was successful or an appropriate error code otherwise.

References CircuitCutsStorage::add_cluster_cuts, CircuitCutsStorage::add_cluster_cuts_to_pool, CircuitCutsStorage::add_cycle_cuts, CircuitCutsStorage::add_cycle_cuts_to_pool, CircuitCutsStorage::add_fractional_cuts, CircuitCutsStorage::max_cycle_length, and CircuitCutsStorage::max_cycles.

Referenced by createConsData().

◆ circuit()

static SCIP_Bool circuit ( SCIP *  scip,
Vector nodes,
int  current_index,
int  start_index,
VectorList b,
SCIP_Bool *  blocked,
Stack s,
SCIP_Real **  adj_matrix,
VectorList cycles,
SCIP_Real  weight,
int  max_cycles,
int  max_cycle_length 
)
static

Find the elementary cycles of a SCC.

Parameters
scipSCIP data structure
nodesThe nodes in the SCC.
current_indexThe index of the current node.
start_indexThe index of the start node for this SCC.
Returns
True if a cycle was found.

References isLessThanOne(), Vector::items, Stack::items, VectorList::items, Vector::size, VectorList::size, StackPop(), StackPush(), StackSize(), unblock(), VectorAppend(), VectorContains(), VectorCreate(), and VectorListAppend().

Referenced by CC_findCuts().

Here is the call graph for this function:

◆ findStronglyConnectedComponents()

static SCIP_RETCODE findStronglyConnectedComponents ( int  current_node,
int *  current_index,
int  n,
Vector index_array,
Vector lowlink,
Stack s,
SCIP_Real **  adj_matrix,
VectorList components 
)
static

Finds Strongly Connected Components in the current solution.

Parameters
current_nodeThe node to consider next.
current_indexThe current depth index.
Returns
SCIP_OKAY if the procedure worked correctly, or an error otherwsie.

References Vector::items, Vector::size, StackContains(), StackPop(), StackPush(), StackSize(), VectorAppend(), VectorCreate(), VectorDelete(), and VectorListAppend().

Referenced by CC_findCuts().

Here is the call graph for this function:

◆ isLessThanOne()

static SCIP_Bool isLessThanOne ( SCIP *  scip,
float  value 
)
static

Return whether a value is strictly less than 1 Uses SCIPepsilon to guard against rounding errors.

Returns
TRUE is the input value is strictly less than 1, else FALSE
Parameters
scipSCIP data structure
valuevalue to test

Referenced by circuit().

◆ shouldIncludeInCuts()

static SCIP_RETCODE shouldIncludeInCuts ( Vector cycle,
ParentSetData psd,
int  previous_node,
int  child,
int  parent_set,
SCIP_Bool *  in_cluster,
SCIP_Bool *  in_cycle 
)
static

Whether a parent set should be included in the current cut.

Parameters
cycleThe nodes in the current cycle.
previous_nodeThe previous node in the cycle.
childThe current node in the cycle.
parent_setThe index number of the current parent set.
in_clusterWhether the parent set should be included in the current cluster cut.
in_cycleWhether the parent set should be included in the current cycle cut.
Returns
SCIP_OKAY if the operation succeded or an error othewrwise.

References ParentSetData::nParents, ParentSetData::ParentSets, and VectorContains().

Referenced by addCuts().

Here is the call graph for this function:

◆ unblock()

static SCIP_RETCODE unblock ( int  u,
Vector nodes,
VectorList b,
SCIP_Bool *  blocked 
)
static

Unblocks a node during the cycle finding algorithm.

Parameters
uThe node to unblock.
nodesThe nodes in the current SCC.
Returns
SCIP_OKAY if the unblocking succeeded.

References Vector::items, VectorList::items, Vector::size, and VectorClear().

Referenced by circuit().

Here is the call graph for this function: