Detailed Description
constraint handler for storing the graph at each node of the tree
This file implements the constraints that are used for the branching in the coloring algorithm.
For each node in the branch-and-bound tree, a constraint of this type is created, which stores all restrictions related to that branch-and-bound node.
First of all, it stores the type of the constraint ("same" or "differ", the root has type root) and the two nodes in the graph on which this restriction is applied. When the branch-and-bound node corresponding to the constraint is examined for the first time, the constraint creates a graph that takes into account all the restrictions, which are active at this node. At the root, this is the original (preprocessed) graph. At any other branch-and-bound node, it takes the graph of the constraint related to the branch-and-bound father of the current node and modifies it so that all restrictions up to this node are respected. Since the graph in the branch-and-bound father respects all restrictions on the path to that node, only the last requirement, the one saved at the current branch-and-bound node, must be added. This is done as follows: Adding a DIFFER(v,w) constraint is easy, since it suffices to add an edge between v and w. For a SAME(v,w) constraint, the original idea is to collapse the nodes v and w into one single vertex. Since this is not possible in the tclique-graph data structure, we introduce new edges in the graph, so that v and w have the same neighborhood. Hence, in the pricing routine, each new stable set will either contain both nodes or none of them, since we create (inclusion-) maximal sets.
This does of course not hold for sets created in a higher level of the branch-and-bound tree or in another subtree. In order to forbid all of these sets, which do not fulfill the current restrictions, a propagation is started when the node is entered the first time and repeated later, if the node is reentered after the creation of new variables in another subtree. The propagation simply fixes to 0 all variables representing a stable set that does not fulfill the restriction at the current node.
The information about all fusions of nodes (caused by the SAME() operation) is stored, so that the nodes constituting a union can be accessed easily. Each union has a representative and a set of nodes, whereas each node knows the representative of the union it belongs to. At the beginning, each node forms its own union and therefore each node also represents this union, consisting of only this node. Later on, some nodes represent unions of several nodes, while other nodes are part of a union which they do not represent, so they have another node as representative. The representatives of the nodes are returned by the methods COLORconsGetRepresentative() / COLORconsGetRepresentatives(), the union represented by a node is returned by COLORconsGetUnion(), the array of unions, indexed by the representing node, is returned by COLORconsGetUnions().
Definition in file cons_storeGraph.h.
Go to the source code of this file.
Typedefs | |
typedef enum COLOR_ConsType | COLOR_CONSTYPE |
Enumerations | |
enum | COLOR_ConsType { COLOR_CONSTYPE_DIFFER = 0, COLOR_CONSTYPE_SAME = 1, COLOR_CONSTYPE_ROOT = 2 } |
Functions | |
SCIP_CONS * | COLORconsGetActiveStoreGraphConsFromHandler (SCIP_CONSHDLR *conshdlr) |
SCIP_CONS * | COLORconsGetActiveStoreGraphCons (SCIP *scip) |
int * | COLORconsGetRepresentatives (SCIP *scip) |
TCLIQUE_GRAPH * | COLORconsGetCurrentGraph (SCIP *scip) |
TCLIQUE_GRAPH * | COLORconsGetComplementaryGraph (SCIP *scip) |
int | COLORconsGetRepresentative (SCIP *scip, int node) |
void | COLORconsGetUnions (SCIP *scip, int ***unions, int **lengths) |
void | COLORconsGetUnion (SCIP *scip, int **unionSet, int *length, int node) |
SCIP_RETCODE | COLORincludeConshdlrStoreGraph (SCIP *scip) |
SCIP_RETCODE | COLORcreateConsStoreGraph (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONS *fatherconstraint, COLOR_CONSTYPE type, int node1, int node2, SCIP_NODE *stickingnode) |
void | COLORconsGetStack (SCIP *scip, SCIP_CONS ***stack, int *nstackelements) |
Typedef Documentation
◆ COLOR_CONSTYPE
typedef enum COLOR_ConsType COLOR_CONSTYPE |
Definition at line 85 of file cons_storeGraph.h.
Enumeration Type Documentation
◆ COLOR_ConsType
enum COLOR_ConsType |
Enumerator | |
---|---|
COLOR_CONSTYPE_DIFFER | |
COLOR_CONSTYPE_SAME | |
COLOR_CONSTYPE_ROOT |
Definition at line 79 of file cons_storeGraph.h.
Function Documentation
◆ COLORconsGetActiveStoreGraphConsFromHandler()
SCIP_CONS* COLORconsGetActiveStoreGraphConsFromHandler | ( | SCIP_CONSHDLR * | conshdlr | ) |
returns the store graph constraint of the current node, needs the pointer to the constraint handler
- Parameters
-
conshdlr constaint handler for store-graph constraints
Definition at line 854 of file cons_storeGraph.c.
References COLORconsGetActiveStoreGraphCons(), NULL, and SCIPconshdlrGetData().
Referenced by COLORcreateConsStoreGraph().
◆ COLORconsGetActiveStoreGraphCons()
returns the store graph constraint of the current node, needs only the pointer to scip
returns the store graph constraint of the current node, only needs the pointer to scip
- Parameters
-
scip SCIP data structure
Definition at line 870 of file cons_storeGraph.c.
References COLORconsGetCurrentGraph(), NULL, SCIPconshdlrGetData(), SCIPerrorMessage, and SCIPfindConshdlr().
Referenced by COLORconsGetActiveStoreGraphConsFromHandler(), executeStrongBranching(), SCIP_DECL_BRANCHEXECLP(), SCIP_DECL_BRANCHEXECPS(), and SCIP_DECL_CONSPROP().
◆ COLORconsGetRepresentatives()
int* COLORconsGetRepresentatives | ( | SCIP * | scip | ) |
returns array of representatives of all nodes
- Parameters
-
scip SCIP data structure
Definition at line 953 of file cons_storeGraph.c.
References COLORconsGetRepresentative(), NULL, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPerrorMessage, and SCIPfindConshdlr().
Referenced by COLORconsGetComplementaryGraph().
◆ COLORconsGetCurrentGraph()
TCLIQUE_GRAPH* COLORconsGetCurrentGraph | ( | SCIP * | scip | ) |
returns the current graph
- Parameters
-
scip SCIP data structure
Definition at line 894 of file cons_storeGraph.c.
References COLORconsGetComplementaryGraph(), NULL, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPerrorMessage, and SCIPfindConshdlr().
Referenced by COLORconsGetActiveStoreGraphCons(), computeBranchingPriorities(), SCIP_DECL_BRANCHEXECLP(), SCIP_DECL_BRANCHEXECPS(), SCIP_DECL_PRICERFARKAS(), and SCIP_DECL_PRICERREDCOST().
◆ COLORconsGetComplementaryGraph()
TCLIQUE_GRAPH* COLORconsGetComplementaryGraph | ( | SCIP * | scip | ) |
returns the complementary graph
- Parameters
-
scip SCIP data structure
Definition at line 922 of file cons_storeGraph.c.
References COLORconsGetRepresentatives(), NULL, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPerrorMessage, and SCIPfindConshdlr().
Referenced by COLORconsGetCurrentGraph(), and SCIP_DECL_PRICERREDCOST().
◆ COLORconsGetRepresentative()
int COLORconsGetRepresentative | ( | SCIP * | scip, |
int | node | ||
) |
returns representative of the union which contains a given node
returns the representative of the union which contains a given node
- Parameters
-
scip SCIP data structure node the node, for wich the representative is searched
Definition at line 981 of file cons_storeGraph.c.
References COLORconsGetUnions(), NULL, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPerrorMessage, and SCIPfindConshdlr().
Referenced by COLORconsGetRepresentatives(), computeBranchingPriorities(), SCIP_DECL_BRANCHEXECLP(), and SCIP_DECL_BRANCHEXECPS().
◆ COLORconsGetUnions()
void COLORconsGetUnions | ( | SCIP * | scip, |
int *** | unions, | ||
int ** | lengths | ||
) |
returns array of all unions, a union is saved in the array at the position of its representative
returns the array of all unions, a union is saved in the array at the position of its representative
- Parameters
-
scip SCIP data structure unions output: array containing array which contains nodes in the union lengths output: lengths of the unions
Definition at line 1014 of file cons_storeGraph.c.
References COLORconsGetUnion(), NULL, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPerrorMessage, and SCIPfindConshdlr().
Referenced by COLORconsGetRepresentative().
◆ COLORconsGetUnion()
void COLORconsGetUnion | ( | SCIP * | scip, |
int ** | nodesinunion, | ||
int * | nnodesinunion, | ||
int | node | ||
) |
returns the union which has a given node as representative
- Parameters
-
scip SCIP data structure nodesinunion output: array containig nodes in the union nnodesinunion output: length of the union node the node, whose union we want to get
Definition at line 1046 of file cons_storeGraph.c.
References COLORconsGetStack(), NULL, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPerrorMessage, and SCIPfindConshdlr().
Referenced by COLORconsGetUnions().
◆ COLORincludeConshdlrStoreGraph()
SCIP_RETCODE COLORincludeConshdlrStoreGraph | ( | SCIP * | scip | ) |
creates the handler for graph storing constraints and includes it in SCIP
creates the handler for storeGraph constraints and includes it in SCIP
- Parameters
-
scip SCIP data structure
Definition at line 758 of file cons_storeGraph.c.
References COLORcreateConsStoreGraph(), CONSHDLR_CHECKPRIORITY, CONSHDLR_DELAYPROP, CONSHDLR_DESC, CONSHDLR_EAGERFREQ, CONSHDLR_ENFOPRIORITY, CONSHDLR_NAME, CONSHDLR_NEEDSCONS, CONSHDLR_PROP_TIMING, CONSHDLR_PROPFREQ, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPdebugMessage, SCIPincludeConshdlrBasic(), SCIPsetConshdlrActive(), SCIPsetConshdlrDeactive(), SCIPsetConshdlrDelete(), SCIPsetConshdlrExitsol(), SCIPsetConshdlrFree(), SCIPsetConshdlrInitsol(), and SCIPsetConshdlrProp().
Referenced by SCIP_DECL_CONSPROP(), and SCIPincludeColoringPlugins().
◆ COLORcreateConsStoreGraph()
SCIP_RETCODE COLORcreateConsStoreGraph | ( | SCIP * | scip, |
SCIP_CONS ** | cons, | ||
const char * | name, | ||
SCIP_CONS * | fatherconstraint, | ||
COLOR_CONSTYPE | type, | ||
int | node1, | ||
int | node2, | ||
SCIP_NODE * | stickingnode | ||
) |
creates and captures a storeGraph constraint, uses knowledge of the B&B-father
- Parameters
-
scip SCIP data structure cons pointer to hold the created constraint name name of constraint fatherconstraint constraint in B&B-father type type of the constraint: COLOR_CONSTYPE_SAME or COLOR_CONSTYPE_DIFFER node1 the first node of the constraint node2 the second node of the constraint stickingnode the B&B-tree node at which the constraint will be sticking
Definition at line 793 of file cons_storeGraph.c.
References COLOR_CONSTYPE_DIFFER, COLOR_CONSTYPE_SAME, COLORconsGetActiveStoreGraphConsFromHandler(), CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPallocBlockMemory, SCIPcreateCons(), SCIPdebugMessage, SCIPerrorMessage, SCIPfindConshdlr(), SCIP_Cons::stickingatnode, and TRUE.
Referenced by COLORincludeConshdlrStoreGraph(), executeStrongBranching(), SCIP_DECL_BRANCHEXECLP(), and SCIP_DECL_BRANCHEXECPS().
◆ COLORconsGetStack()
returns the stack and the number of elements on it
- Parameters
-
scip SCIP data structure stack return value: pointer to the stack nstackelements return value: pointer to int, for number of elements on the stack
Definition at line 1077 of file cons_storeGraph.c.
References NULL, SCIPconshdlrGetData(), SCIPerrorMessage, and SCIPfindConshdlr().
Referenced by COLORconsGetUnion().