Scippy

SCIP

Solving Constraint Integer Programs

probdata_coloring.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2018 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file probdata_coloring.h
17  * @brief problem data for vertex coloring algorithm
18  * @author Gerald Gamrath
19  *
20  * This file implements the problem data for the coloring algorithm.
21  *
22  * The problem data contains the original graph, preprocessing information, the preprocessed graph,
23  * the array with the node-constraints, and an array with all stable sets and corresponding
24  * variables.
25  *
26  * The preprocessing deletes nodes that have a lower degree than the size of a maximum clique.
27  * Additionally, it also deletes nodes that have a dominated neighborhood. For further information,
28  * look at the documentation for the method preprocessGraph().
29  *
30  * The deleted nodes and the relation between the nodes of the original graph and the nodes of the
31  * preprocessed graph are stored in order to convert a solution of the preprocessed problem to a
32  * solution for the original graph and vice versa.
33  *
34  * Each variable has a pointer of type SCIP_VARDATA* that is used in this case to store an integer
35  * representing the number of the stable set. With the aid of this, the corresponding stable set can
36  * be found in the array returned by COLORprobGetStableSets(). This array contains all stable sets
37  * and is also used to check whether a stable set found by the pricer is really new. This can be
38  * done by calling COLORprobStableSetIsNew(). All sets are sorted decreasingly with respect to the
39  * indices of the nodes. New candidates should also be sorted that way.
40  */
41 
42 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
43 
44 #ifndef __SCIP_PROBDATA_COLORING__
45 #define __SCIP_PROBDATA_COLORING__
46 
47 #include <assert.h>
48 
49 #include "scip/scip.h"
50 #include "tclique/tclique.h" /* def. of clique data structures */
51 #include "scip/cons_setppc.h"
52 #include "reader_col.h"
53 
54 #ifdef __cplusplus
55 extern "C" {
56 #endif
57 
58 /* stable set / variable functions */
59 
60 /** returns the number of stable sets / variables */
61 extern
63  SCIP* scip /**< SCIP data structure */
64  );
65 
66 /** returns the stable set with the given index */
67 extern
69  SCIP* scip, /**< SCIP data structure */
70  int setindex, /**< index of the stable set */
71  int** stableset, /**< return value: pointer to the stable set */
72  int* nelements /**< return value: number of elements in the stable set */
73  );
74 
75 /** returns all stable sets */
76 extern
78  SCIP* scip, /**< SCIP data structure */
79  int*** stablesets, /**< return value: pointer to the stable sets */
80  int** nelements, /**< return value: number of elements in the stable sets */
81  int* nstablesets /**< return value: number of sets */
82  );
83 
84 /** adds a new stable set, the set must be sorted descendingly,
85  attention: you need to check whether it is new before adding it*/
86 extern
88  SCIP* scip, /**< SCIP data structure */
89  int* cliquenodes, /**< array of nodes in the stable set */
90  int ncliquenodes, /**< number of nodes in the stable set */
91  int* setindex /**< return value: index of the stable set, -i-1 if set was not new
92  * and is already saved as set i */
93  );
94 
95 /** adds a variable that belongs to a given stable set */
96 extern
98  SCIP* scip, /**< SCIP data structure */
99  int setindex, /**< index of the stable set */
100  SCIP_VAR* var /**< pointer to the variable */
101  );
102 
103 /** gets the variable belonging to a given stable set */
104 extern
106  SCIP* scip, /**< SCIP data structure */
107  int setindex /**< index of the stable set */
108  );
109 
110 /** checks whether the given stable set is new, returns TRUE if the stable is new and
111  * FALSE if it is part of or equal to an already existing stable set
112  */
113 extern
115  SCIP* scip, /**< SCIP data structure */
116  int* stablesetnodes, /**< array of nodes in the stable set */
117  int nstablesetnodes /**< number of nodes in the stable set */
118  );
119 
120 /** checks whether the first set is equal to the second set, both sets have to be sorted in a decreasing way */
121 extern
123  SCIP* scip, /**< SCIP data structure */
124  int* set1, /**< array of nodes in the first set */
125  int nset1nodes, /**< number of nodes in the first set */
126  int* set2, /**< array of nodes in the second set */
127  int nset2nodes /**< number of nodes in the second set */
128  );
129 
130 /** prints all stable sets to standart output */
131 extern
133  SCIP* scip /**< SCIP data structure */
134  );
135 
136 /** prints the requested stable set to standart output */
137 extern
139  SCIP* scip, /**< SCIP data structure */
140  int setnumber /**< the number of the requested set */
141  );
142 
143 /** checks whether a node is in a given stable set, returns true iff it is */
144 extern
146  SCIP* scip, /**< SCIP data structure */
147  int setindex, /**< index of the stable set */
148  int node /**< number of the node */
149  );
150 
151 /* constraint functions */
152 
153 /** creates all node-constraints and saves them in an array */
154 extern
156  SCIP* scip /**< SCIP data structure */
157  );
158 
159 /** returns all node-constraints */
160 extern
162  SCIP* scip /**< SCIP data structure */
163  );
164 
165 /** returns the node-constraint belonging to a given node */
166 extern
168  SCIP* scip, /**< SCIP data structure */
169  int node /**< number of the node, for which this constraint assures coloring */
170  );
171 
172 
173 
174 /* graph and preprocessing functions */
175 
176 /** returns the (preprocessed) graph */
177 extern
179  SCIP* scip /**< SCIP data structure */
180  );
181 
182 /** returns the original graph */
183 extern
185  SCIP* scip /**< SCIP data structure */
186  );
187 
188 /** computes the complementary graph for a given graph and stores it in the given pointer */
189 extern
191  SCIP* scip, /**< SCIP data structure */
192  TCLIQUE_GRAPH* graph, /**< the given graph */
193  TCLIQUE_GRAPH* cgraph /**< the complementary graph is saved in here */
194  );
195 
196 /** returns the number of nodes in the (preprocessed) graph */
197 extern
199  SCIP* scip /**< SCIP data structure */
200  );
201 
202 /** returns the number of nodes in the original graph */
203 extern
205  SCIP* scip /**< SCIP data structure */
206  );
207 
208 /** returns the array of nodes deleted during preprocessing, length = COLORprobGetOriginalNNodes(),
209  * filled with -1 at the end
210  */
211 extern
213  SCIP* scip /**< SCIP data structure */
214  );
215 
216 /** returns the array in which for every node in the preprocessed graph, the related node in the original graph is saved */
217 extern
219  SCIP* scip /**< SCIP data structure */
220  );
221 
222 /** returns the node in the preprocessed graph, that belongs to the given node, returns -1 if node was deleted */
223 extern
225  SCIP* scip, /**< SCIP data structure */
226  int node /**< a node in the original graph */
227  );
228 
229 
230 
231 /* miscellaneous functions */
232 
233 /** checks whether the given node is in the given array */
234 extern
236  int node, /**< the number of the node */
237  int* arrayNodes, /**< the nodes of the maximum clique */
238  int narraynodes /**< number of nodes in the maximum clique */
239  );
240 
241 /** checks whether the given two given arrays are equal */
242 extern
244  int* array1nodes, /**< the nodes of the first set */
245  int narray1nodes, /**< number of nodes in the first set */
246  int* array2nodes, /**< the nodes of the second set */
247  int narray2nodes /**< number of nodes in the second set */
248  );
249 
250 
251 /* create probdate */
252 
253 /** sets up the problem data */
254 extern
256  SCIP* scip, /**< SCIP data structure */
257  const char* name, /**< problem name */
258  int nnodes, /**< number of nodes */
259  int nedges, /**< number of edges */
260  int** edges /**< array with start- and endpoints of the edges */
261  );
262 
263 #ifdef __cplusplus
264 }
265 #endif
266 
267 #endif
int * COLORprobGetOriginalNodesForNewNodes(SCIP *scip)
struct TCLIQUE_Graph TCLIQUE_GRAPH
Definition: tclique.h:40
SCIP_RETCODE COLORprobSetUpArrayOfCons(SCIP *scip)
int COLORprobGetNewNodeForOriginalNode(SCIP *scip, int node)
TCLIQUE_GRAPH * COLORprobGetOriginalGraph(SCIP *scip)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
file reader for vertex coloring instances
SCIP_CONS * COLORprobGetConstraint(SCIP *scip, int node)
tclique user interface
Constraint handler for the set partitioning / packing / covering constraints .
void COLORprobGetStableSet(SCIP *scip, int setindex, int **stableset, int *nelements)
SCIP_Bool COLORprobStableSetIsNew(SCIP *scip, int *stablesetnodes, int nstablesetnodes)
SCIP_CONS ** COLORprobGetConstraints(SCIP *scip)
SCIP_RETCODE COLORprobAddNewStableSet(SCIP *scip, int *cliquenodes, int ncliquenodes, int *setindex)
int * COLORprobGetDeletedNodes(SCIP *scip)
TCLIQUE_GRAPH * COLORprobGetGraph(SCIP *scip)
void COLORprobPrintStableSet(SCIP *scip, int setnumber)
int COLORprobGetNNodes(SCIP *scip)
SCIP_Bool COLORprobIsNodeInArray(int node, int *arrayNodes, int narraynodes)
SCIP_RETCODE COLORprobAddVarForStableSet(SCIP *scip, int setindex, SCIP_VAR *var)
#define SCIP_Bool
Definition: def.h:62
SCIP_Bool COLORprobEqualSortedArrays(int *array1nodes, int narray1nodes, int *array2nodes, int narray2nodes)
SCIP_Bool COLORprobStableSetsAreEqual(SCIP *scip, int *set1, int nset1nodes, int *set2, int nset2nodes)
int COLORprobGetNStableSets(SCIP *scip)
SCIP_RETCODE COLORprobGetComplementaryGraph(SCIP *scip, TCLIQUE_GRAPH *graph, TCLIQUE_GRAPH *cgraph)
SCIP_VAR * COLORprobGetVarForStableSet(SCIP *scip, int setindex)
int COLORprobGetOriginalNNodes(SCIP *scip)
#define nnodes
Definition: gastrans.c:65
SCIP_Bool COLORprobIsNodeInStableSet(SCIP *scip, int setindex, int node)
SCIP_RETCODE SCIPcreateProbColoring(SCIP *scip, const char *name, int nnodes, int nedges, int **edges)
void COLORprobPrintStableSets(SCIP *scip)
void COLORprobGetStableSets(SCIP *scip, int ***stablesets, int **nelements, int *nstablesets)
SCIP callable library.