GOBNILP
f164d83
|
Implements a method for finding and adding cluster cuts. More...
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... | |
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.
|
static |
Adds cuts to rule out each of the found cycles.
scip | The SCIP instance. |
conshdlr | The constraint handler to add cuts for. |
sol | The current solution. |
forcecuts | Whether to force cuts to be added |
found_efficacious_ptr | Whether at least one efficacious cut was added. |
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().
SCIP_RETCODE CC_addParams | ( | SCIP * | scip | ) |
Adds parameters to those recognised by SCIP.
scip | The SCIP instance to add parameters to. |
scip | SCIP data structure |
References UT_addBoolParam().
SCIP_RETCODE CC_finalise | ( | SCIP * | scip, |
CircuitCutsStorage * | ccs, | ||
int | n | ||
) |
Frees all memory allocated by CC_initialise
.
scip | SCIP data structure |
ccs | Circuit storage to free |
n | Number of DAG nodes |
References StackDelete(), VectorDelete(), and VectorListDelete().
Referenced by SCIP_DECL_CONSDELETE().
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.
scip | The SCIP instance the cuts are to be found for. |
conshdlr | The constraint handler responsible for the cuts. |
sol | The current relaxed solution. |
nGen | The number of cuts that were added. |
forcecuts | Whether to force cuts to be added |
found_efficacious_ptr | A pointer to return whether any efficacious cuts were found. |
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().
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.
scip | The SCIP instance the separation is to take place in. |
data | The problem data that the separation will occur on. |
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().
|
static |
Find the elementary cycles of a SCC.
scip | SCIP data structure |
nodes | The nodes in the SCC. |
current_index | The index of the current node. |
start_index | The index of the start node for this SCC. |
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().
|
static |
Finds Strongly Connected Components in the current solution.
current_node | The node to consider next. |
current_index | The current depth index. |
References Vector::items, Vector::size, StackContains(), StackPop(), StackPush(), StackSize(), VectorAppend(), VectorCreate(), VectorDelete(), and VectorListAppend().
Referenced by CC_findCuts().
|
static |
Return whether a value is strictly less than 1 Uses SCIPepsilon to guard against rounding errors.
scip | SCIP data structure |
value | value to test |
Referenced by circuit().
|
static |
Whether a parent set should be included in the current cut.
cycle | The nodes in the current cycle. |
previous_node | The previous node in the cycle. |
child | The current node in the cycle. |
parent_set | The index number of the current parent set. |
in_cluster | Whether the parent set should be included in the current cluster cut. |
in_cycle | Whether the parent set should be included in the current cycle cut. |
References ParentSetData::nParents, ParentSetData::ParentSets, and VectorContains().
Referenced by addCuts().
|
static |
Unblocks a node during the cycle finding algorithm.
u | The node to unblock. |
nodes | The nodes in the current SCC. |
References Vector::items, VectorList::items, Vector::size, and VectorClear().
Referenced by circuit().