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-2022 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 scipopt.org. */
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 */
62  SCIP* scip /**< SCIP data structure */
63  );
64 
65 /** returns the stable set with the given index */
67  SCIP* scip, /**< SCIP data structure */
68  int setindex, /**< index of the stable set */
69  int** stableset, /**< return value: pointer to the stable set */
70  int* nelements /**< return value: number of elements in the stable set */
71  );
72 
73 /** returns all stable sets */
75  SCIP* scip, /**< SCIP data structure */
76  int*** stablesets, /**< return value: pointer to the stable sets */
77  int** nelements, /**< return value: number of elements in the stable sets */
78  int* nstablesets /**< return value: number of sets */
79  );
80 
81 /** adds a new stable set, the set must be sorted descendingly,
82  attention: you need to check whether it is new before adding it*/
84  SCIP* scip, /**< SCIP data structure */
85  int* cliquenodes, /**< array of nodes in the stable set */
86  int ncliquenodes, /**< number of nodes in the stable set */
87  int* setindex /**< return value: index of the stable set, -i-1 if set was not new
88  * and is already saved as set i */
89  );
90 
91 /** adds a variable that belongs to a given stable set */
93  SCIP* scip, /**< SCIP data structure */
94  int setindex, /**< index of the stable set */
95  SCIP_VAR* var /**< pointer to the variable */
96  );
97 
98 /** gets the variable belonging to a given stable set */
100  SCIP* scip, /**< SCIP data structure */
101  int setindex /**< index of the stable set */
102  );
103 
104 /** checks whether the given stable set is new, returns TRUE if the stable is new and
105  * FALSE if it is part of or equal to an already existing stable set
106  */
108  SCIP* scip, /**< SCIP data structure */
109  int* stablesetnodes, /**< array of nodes in the stable set */
110  int nstablesetnodes /**< number of nodes in the stable set */
111  );
112 
113 /** checks whether the first set is equal to the second set, both sets have to be sorted in a decreasing way */
115  SCIP* scip, /**< SCIP data structure */
116  int* set1, /**< array of nodes in the first set */
117  int nset1nodes, /**< number of nodes in the first set */
118  int* set2, /**< array of nodes in the second set */
119  int nset2nodes /**< number of nodes in the second set */
120  );
121 
122 /** prints all stable sets to standart output */
124  SCIP* scip /**< SCIP data structure */
125  );
126 
127 /** prints the requested stable set to standart output */
129  SCIP* scip, /**< SCIP data structure */
130  int setnumber /**< the number of the requested set */
131  );
132 
133 /** checks whether a node is in a given stable set, returns true iff it is */
135  SCIP* scip, /**< SCIP data structure */
136  int setindex, /**< index of the stable set */
137  int node /**< number of the node */
138  );
139 
140 /* constraint functions */
141 
142 /** creates all node-constraints and saves them in an array */
144  SCIP* scip /**< SCIP data structure */
145  );
146 
147 /** returns all node-constraints */
149  SCIP* scip /**< SCIP data structure */
150  );
151 
152 /** returns the node-constraint belonging to a given node */
154  SCIP* scip, /**< SCIP data structure */
155  int node /**< number of the node, for which this constraint assures coloring */
156  );
157 
158 
159 
160 /* graph and preprocessing functions */
161 
162 /** returns the (preprocessed) graph */
164  SCIP* scip /**< SCIP data structure */
165  );
166 
167 /** returns the original graph */
169  SCIP* scip /**< SCIP data structure */
170  );
171 
172 /** computes the complementary graph for a given graph and stores it in the given pointer */
174  SCIP* scip, /**< SCIP data structure */
175  TCLIQUE_GRAPH* graph, /**< the given graph */
176  TCLIQUE_GRAPH* cgraph /**< the complementary graph is saved in here */
177  );
178 
179 /** returns the number of nodes in the (preprocessed) graph */
181  SCIP* scip /**< SCIP data structure */
182  );
183 
184 /** returns the number of nodes in the original graph */
186  SCIP* scip /**< SCIP data structure */
187  );
188 
189 /** returns the array of nodes deleted during preprocessing, length = COLORprobGetOriginalNNodes(),
190  * filled with -1 at the end
191  */
193  SCIP* scip /**< SCIP data structure */
194  );
195 
196 /** returns the array in which for every node in the preprocessed graph, the related node in the original graph is saved */
198  SCIP* scip /**< SCIP data structure */
199  );
200 
201 /** returns the node in the preprocessed graph, that belongs to the given node, returns -1 if node was deleted */
203  SCIP* scip, /**< SCIP data structure */
204  int node /**< a node in the original graph */
205  );
206 
207 
208 
209 /* miscellaneous functions */
210 
211 /** checks whether the given node is in the given array */
213  int node, /**< the number of the node */
214  int* arrayNodes, /**< the nodes of the maximum clique */
215  int narraynodes /**< number of nodes in the maximum clique */
216  );
217 
218 /** checks whether the given two given arrays are equal */
220  int* array1nodes, /**< the nodes of the first set */
221  int narray1nodes, /**< number of nodes in the first set */
222  int* array2nodes, /**< the nodes of the second set */
223  int narray2nodes /**< number of nodes in the second set */
224  );
225 
226 
227 /* create probdate */
228 
229 /** sets up the problem data */
231  SCIP* scip, /**< SCIP data structure */
232  const char* name, /**< problem name */
233  int nnodes, /**< number of nodes */
234  int nedges, /**< number of edges */
235  int** edges /**< array with start- and endpoints of the edges */
236  );
237 
238 #ifdef __cplusplus
239 }
240 #endif
241 
242 #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:54
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:84
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.