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 2002-2022 Zuse Institute Berlin */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file probdata_coloring.h
26  * @brief problem data for vertex coloring algorithm
27  * @author Gerald Gamrath
28  *
29  * This file implements the problem data for the coloring algorithm.
30  *
31  * The problem data contains the original graph, preprocessing information, the preprocessed graph,
32  * the array with the node-constraints, and an array with all stable sets and corresponding
33  * variables.
34  *
35  * The preprocessing deletes nodes that have a lower degree than the size of a maximum clique.
36  * Additionally, it also deletes nodes that have a dominated neighborhood. For further information,
37  * look at the documentation for the method preprocessGraph().
38  *
39  * The deleted nodes and the relation between the nodes of the original graph and the nodes of the
40  * preprocessed graph are stored in order to convert a solution of the preprocessed problem to a
41  * solution for the original graph and vice versa.
42  *
43  * Each variable has a pointer of type SCIP_VARDATA* that is used in this case to store an integer
44  * representing the number of the stable set. With the aid of this, the corresponding stable set can
45  * be found in the array returned by COLORprobGetStableSets(). This array contains all stable sets
46  * and is also used to check whether a stable set found by the pricer is really new. This can be
47  * done by calling COLORprobStableSetIsNew(). All sets are sorted decreasingly with respect to the
48  * indices of the nodes. New candidates should also be sorted that way.
49  */
50 
51 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
52 
53 #ifndef __SCIP_PROBDATA_COLORING__
54 #define __SCIP_PROBDATA_COLORING__
55 
56 #include <assert.h>
57 
58 #include "scip/scip.h"
59 #include "tclique/tclique.h" /* def. of clique data structures */
60 #include "scip/cons_setppc.h"
61 #include "reader_col.h"
62 
63 #ifdef __cplusplus
64 extern "C" {
65 #endif
66 
67 /* stable set / variable functions */
68 
69 /** returns the number of stable sets / variables */
71  SCIP* scip /**< SCIP data structure */
72  );
73 
74 /** returns the stable set with the given index */
76  SCIP* scip, /**< SCIP data structure */
77  int setindex, /**< index of the stable set */
78  int** stableset, /**< return value: pointer to the stable set */
79  int* nelements /**< return value: number of elements in the stable set */
80  );
81 
82 /** returns all stable sets */
84  SCIP* scip, /**< SCIP data structure */
85  int*** stablesets, /**< return value: pointer to the stable sets */
86  int** nelements, /**< return value: number of elements in the stable sets */
87  int* nstablesets /**< return value: number of sets */
88  );
89 
90 /** adds a new stable set, the set must be sorted descendingly,
91  attention: you need to check whether it is new before adding it*/
93  SCIP* scip, /**< SCIP data structure */
94  int* cliquenodes, /**< array of nodes in the stable set */
95  int ncliquenodes, /**< number of nodes in the stable set */
96  int* setindex /**< return value: index of the stable set, -i-1 if set was not new
97  * and is already saved as set i */
98  );
99 
100 /** adds a variable that belongs to a given stable set */
102  SCIP* scip, /**< SCIP data structure */
103  int setindex, /**< index of the stable set */
104  SCIP_VAR* var /**< pointer to the variable */
105  );
106 
107 /** gets the variable belonging to a given stable set */
109  SCIP* scip, /**< SCIP data structure */
110  int setindex /**< index of the stable set */
111  );
112 
113 /** checks whether the given stable set is new, returns TRUE if the stable is new and
114  * FALSE if it is part of or equal to an already existing stable set
115  */
117  SCIP* scip, /**< SCIP data structure */
118  int* stablesetnodes, /**< array of nodes in the stable set */
119  int nstablesetnodes /**< number of nodes in the stable set */
120  );
121 
122 /** checks whether the first set is equal to the second set, both sets have to be sorted in a decreasing way */
124  SCIP* scip, /**< SCIP data structure */
125  int* set1, /**< array of nodes in the first set */
126  int nset1nodes, /**< number of nodes in the first set */
127  int* set2, /**< array of nodes in the second set */
128  int nset2nodes /**< number of nodes in the second set */
129  );
130 
131 /** prints all stable sets to standart output */
133  SCIP* scip /**< SCIP data structure */
134  );
135 
136 /** prints the requested stable set to standart output */
138  SCIP* scip, /**< SCIP data structure */
139  int setnumber /**< the number of the requested set */
140  );
141 
142 /** checks whether a node is in a given stable set, returns true iff it is */
144  SCIP* scip, /**< SCIP data structure */
145  int setindex, /**< index of the stable set */
146  int node /**< number of the node */
147  );
148 
149 /* constraint functions */
150 
151 /** creates all node-constraints and saves them in an array */
153  SCIP* scip /**< SCIP data structure */
154  );
155 
156 /** returns all node-constraints */
158  SCIP* scip /**< SCIP data structure */
159  );
160 
161 /** returns the node-constraint belonging to a given node */
163  SCIP* scip, /**< SCIP data structure */
164  int node /**< number of the node, for which this constraint assures coloring */
165  );
166 
167 
168 
169 /* graph and preprocessing functions */
170 
171 /** returns the (preprocessed) graph */
173  SCIP* scip /**< SCIP data structure */
174  );
175 
176 /** returns the original graph */
178  SCIP* scip /**< SCIP data structure */
179  );
180 
181 /** computes the complementary graph for a given graph and stores it in the given pointer */
183  SCIP* scip, /**< SCIP data structure */
184  TCLIQUE_GRAPH* graph, /**< the given graph */
185  TCLIQUE_GRAPH* cgraph /**< the complementary graph is saved in here */
186  );
187 
188 /** returns the number of nodes in the (preprocessed) graph */
190  SCIP* scip /**< SCIP data structure */
191  );
192 
193 /** returns the number of nodes in the original graph */
195  SCIP* scip /**< SCIP data structure */
196  );
197 
198 /** returns the array of nodes deleted during preprocessing, length = COLORprobGetOriginalNNodes(),
199  * filled with -1 at the end
200  */
202  SCIP* scip /**< SCIP data structure */
203  );
204 
205 /** returns the array in which for every node in the preprocessed graph, the related node in the original graph is saved */
207  SCIP* scip /**< SCIP data structure */
208  );
209 
210 /** returns the node in the preprocessed graph, that belongs to the given node, returns -1 if node was deleted */
212  SCIP* scip, /**< SCIP data structure */
213  int node /**< a node in the original graph */
214  );
215 
216 
217 
218 /* miscellaneous functions */
219 
220 /** checks whether the given node is in the given array */
222  int node, /**< the number of the node */
223  int* arrayNodes, /**< the nodes of the maximum clique */
224  int narraynodes /**< number of nodes in the maximum clique */
225  );
226 
227 /** checks whether the given two given arrays are equal */
229  int* array1nodes, /**< the nodes of the first set */
230  int narray1nodes, /**< number of nodes in the first set */
231  int* array2nodes, /**< the nodes of the second set */
232  int narray2nodes /**< number of nodes in the second set */
233  );
234 
235 
236 /* create probdate */
237 
238 /** sets up the problem data */
240  SCIP* scip, /**< SCIP data structure */
241  const char* name, /**< problem name */
242  int nnodes, /**< number of nodes */
243  int nedges, /**< number of edges */
244  int** edges /**< array with start- and endpoints of the edges */
245  );
246 
247 #ifdef __cplusplus
248 }
249 #endif
250 
251 #endif
int * COLORprobGetOriginalNodesForNewNodes(SCIP *scip)
struct TCLIQUE_Graph TCLIQUE_GRAPH
Definition: tclique.h:49
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:63
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:93
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:74
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.