# SCIP

Solving Constraint Integer Programs

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 /* */
7 /* fuer Informationstechnik Berlin */
8 /* */
10 /* */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
17  * @brief file reader and writer for vertex coloring solutions
18  * @author Gerald Gamrath
19  *
20  * This file implements the reader and writer for coloring solution files.
21  *
22  * These files have the following structure:@n The first line contains the name of the problem, the
23  * number of colors used in the solution, and - optional - the name of the algorithm that computed
24  * this solution. The second line lists the colors of the nodes, separated by spaces. It is sorted
25  * increasingly by the node indices. The numbers for the colors start with 0.
26  */
27
28 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
29
30 #include <assert.h>
31 #include <string.h>
32 #include <ctype.h>
33 #include <stdlib.h>
34
37 #include "probdata_coloring.h"
38
39
43
44 #define COL_MAX_LINELEN 65535
45
46
47
48 /*
49  * Local methods
50  */
51
52 /** get next number from string s */
53 static
55  char** s /**< pointer to the pointer of the current position in the string */
56  )
57 {
58  long tmp;
59  /* skip whitespaces */
60  while ( isspace(**s) )
61  ++(*s);
63  tmp = atol(*s);
64  /* skip whitespaces */
65  while ( (**s != 0) && (!isspace(**s)) )
66  ++(*s);
67  return tmp;
68 }
69
70
71 /* put your local methods here, and declare them static */
72
73 /** copy method for reader plugins (called when SCIP copies plugins) */
74 static
76 { /*lint --e{715}*/
77  assert(scip != NULL);
80
81  return SCIP_OKAY;
82 }
83
85 static
87 {
88  SCIP_FILE* fp; /* file-reader */
89  char buf[COL_MAX_LINELEN]; /* maximal length of line */
90  char* char_p;
91  char* solprobname;
92  const char* probname;
93
94  SCIP_Bool correctinstance;
95  TCLIQUE_GRAPH* graph;
96  SCIP_VAR* var;
97  SCIP_CONS** constraints;
98
99  int** sets;
100  int* setlengths;
101  int nsets;
102  int setindex;
103
104  int i;
105  int j;
106  int k;
107  int color;
108  int node;
109
112  assert(scip != NULL);
113  assert(result != NULL);
114  assert(filename != NULL);
115  *result = SCIP_SUCCESS;
116
118  {
120  return SCIP_OKAY;
121  }
122
123  if (NULL == (fp = SCIPfopen(filename, "r")))
124  {
125  SCIPerrorMessage("cannot open file <%s> for reading\n", filename);
126  perror(filename);
127  return SCIP_NOFILE;
128  }
129
130  /* Read out the name of the problem belonging to this solution*/
131  if( SCIPfgets(buf, (int) sizeof(buf), fp) == NULL )
133
134  i = 1;
135  while ( !isspace(buf[i]) )
136  {
137  i++;
138  }
139  SCIP_CALL( SCIPallocBufferArray(scip, &solprobname, i+2) );
140  strncpy(solprobname, &buf[0], (unsigned int) i);
141  solprobname[i]= '\0';
142
143  printf("Reading solution for %s...\n", solprobname);
144
145  /* get the name of the current problem */
146  probname = SCIPgetProbName(scip);
147
148  /* check whether the solution belongs to the current problem */
149  correctinstance = TRUE;
150  for ( j = 0; j <= i; j++ )
151  {
152  if ( solprobname[j] != probname[j] )
153  {
154  correctinstance = FALSE;
155  }
156  }
157  if ( !correctinstance )
158  {
159  SCIPerrorMessage("The selected solution file doesn't belong to the current problem!\n");
160  return SCIP_OKAY;
161  }
162
163  /* get the graph of the current problem */
164  graph = COLORprobGetGraph(scip);
165  assert(graph != NULL);
166
167  /* read out number of colors */
168  char_p = &buf[i];
169  nsets = (int) getNextNumber(&char_p);
170  assert(nsets > 0);
171
172  /* allocate memory for the stable sets */
173  SCIP_CALL( SCIPallocBufferArray(scip, &sets, nsets) );
174  SCIP_CALL( SCIPallocBufferArray(scip, &setlengths, nsets) );
175  for ( i = 0; i < nsets; i++ )
176  {
177  int size;
178
179  size = COLORprobGetOriginalNNodes(scip) + 1;
180  SCIP_CALL( SCIPallocBufferArray(scip, &(sets[i]), size) ); /*lint !e866*/
181  setlengths[i] = 0;
182  }
183
184  /* read out the colors for the nodes */
185  SCIPfgets(buf, (int) sizeof(buf), fp); /*lint !e534*/
186  char_p = &buf[0];
187  for ( i = 0; i < COLORprobGetOriginalNNodes(scip); i++ )
188  {
189  color = (int) getNextNumber(&char_p);
190  sets[color][setlengths[color]] = i;
191  sets[color][setlengths[color]+1] = -1;
192  setlengths[color]++;
193  }
194
195  /* the given coloring is a coloring for the original graph, now transform it into a coloring for the transformed graph */
196  for ( i = 0; i < nsets; i++ )
197  {
198  j = 0;
199  k = 0;
200  while ( sets[i][j] != -1 )
201  {
202  node = COLORprobGetNewNodeForOriginalNode(scip, sets[i][j]);
203  if ( node == -1 )
204  {
205  j++;
206  }
207  else
208  {
209  sets[i][k] = node;
210  setlengths[i] = k+1;
211  k++;
212  j++;
213  }
214  }
215  while ( k < j )
216  {
217  sets[i][k] = -1;
218  k++;
219  }
220  }
221
222  printf("testing validity...\n");
223  /* check solution */
224  for ( i = 0; i < nsets; i++ )
225  {
226  for ( j = 0; j < setlengths[i]; j++ )
227  {
228  for ( k = j+1; k < setlengths[i]; k++ )
229  {
230  if ( tcliqueIsEdge(graph, sets[i][j], sets[i][k]) )
231  {
232  SCIPerrorMessage("The solution is not valid!\n");
233  return SCIP_OKAY;
234  }
235  }
236  }
237  }
238  printf("valid!\n");
239
240  /* get the node-constraits */
241  constraints = COLORprobGetConstraints(scip);
242  assert(constraints != NULL);
243  /* try to add nodes to the stable sets */
244  for ( i = 0; i < nsets; i++ )
245  {
246  for ( node = 0; node < COLORprobGetNNodes(scip); node++ )
247  {
248  for ( j = 0; j < setlengths[i]; j++ )
249  {
250  if ( sets[i][j] == node )
251  {
252  break;
253  }
254  if ( tcliqueIsEdge(graph, sets[i][j], node) )
255  {
256  break;
257  }
258  }
259  if ( j == setlengths[i] )
260  {
261  sets[i][setlengths[i]] = node;
262  sets[i][setlengths[i]+1] = -1;
263  setlengths[i]++;
264  }
265  }
266  }
267
268  /* sort the sets and add them to the problem, creating one variable for each set */
269  for ( i = 0; i < nsets; i++ )
270  {
271  SCIPsortDownInt(sets[i], setlengths[i]);
272  SCIP_CALL( COLORprobAddNewStableSet(scip, sets[i], setlengths[i], &setindex) );
273  assert(setindex == i);
274
275  SCIP_CALL( SCIPcreateVar(scip, &var, NULL, 0.0, 1.0, 1.0, SCIP_VARTYPE_BINARY,
276  TRUE, FALSE, NULL, NULL, NULL, NULL, (SCIP_VARDATA*)(size_t)setindex) ); /*lint !e571*/
277
278  SCIP_CALL( COLORprobAddVarForStableSet(scip, setindex, var) );
280  SCIP_CALL( SCIPchgVarUbLazy(scip, var, 1.0) );
281
282  /* add variable to node constraints of nodes in the set */
283  for ( j = 0; j < setlengths[i]; j++ )
284  {
285  SCIP_CALL( SCIPaddCoefSetppc(scip, constraints[sets[i][j]], var) );
286  }
287
288  }
289
290
291  /* free memory for the stable sets */
292  for ( i = nsets-1; i >= 0; i-- )
293  {
294  SCIPfreeBufferArray(scip, &(sets[i]));
295  }
296  SCIPfreeBufferArray(scip, &setlengths);
297  SCIPfreeBufferArray(scip, &sets);
298  SCIPfreeBufferArray(scip, &solprobname);
299
300  return SCIP_OKAY;
301 }
302
303
304
305
306 /*
307  * Callback methods of reader
308  */
309
310 /** problem writing method of reader */
311 static
313 {
314  SCIP_SOL* sol;
315  SCIP_Bool colorpossible;
316  TCLIQUE_GRAPH* oldgraph;
317  int** sets;
318  int* nsetelements;
319  int nsets;
320  int nnodes;
321  int i;
322  int j;
323  int actcolor;
324  int node;
325  int* originalnodes;
326  int* deletednodes;
327  int* firstedge;
328  int* lastedge;
329  int* colors;
330
331  *result = SCIP_DIDNOTRUN;
332
333  /* get the data of the original graph, the preprocessing information and the array stable sets in the preprocessed graph */
336  assert(originalnodes != NULL);
337  deletednodes = COLORprobGetDeletedNodes(scip);
338  assert(deletednodes != NULL);
339  oldgraph = COLORprobGetOriginalGraph(scip);
340  COLORprobGetStableSets(scip, &sets, &nsetelements, &nsets);
341  assert(sets != NULL && nsetelements != NULL);
342
343  /* get the solution */
344  sol = SCIPgetBestSol(scip);
345
346  /* create array for the colors of the nodes and initialize it with -1 */
347  SCIP_CALL( SCIPallocBufferArray(scip, &colors, nnodes) );
348  for ( i = 0; i < nnodes; i++ )
349  {
350  colors[i] = -1;
351  }
352
353  /* for all stable sets in the solution, color all nodes, that are in the set and not yet colored with the same, new color */
354  actcolor = 0;
355  for ( i = 0; i < nsets; i++ )
356  {
357  if ( SCIPgetSolVal(scip, sol, COLORprobGetVarForStableSet(scip, i)) > 0 )
358  {
359  assert(SCIPgetSolVal( scip, sol, COLORprobGetVarForStableSet(scip, i)) == 1);
360  for ( j = 0; j < nsetelements[i]; j++ )
361  {
362  if ( colors[originalnodes[sets[i][j]]] == -1 )
363  {
364  colors[originalnodes[sets[i][j]]] = actcolor;
365  }
366  }
367  actcolor++;
368  }
369  }
370
371  /* set i to the index of the last node deleted during preprocessing */
373  while ( deletednodes[i] == -1 )
374  {
375  i--;
376  }
377
378  /*compute colors for nodes deleted during preprocessing */
379  while ( i >= 0 )
380  {
381  node = deletednodes[i];
382  j = 0;
383  while ( colors[node] == -1 )
384  {
385  colorpossible = TRUE;
388  while ( firstedge <= lastedge )
389  {
390  if ( colors[*firstedge] == j )
391  {
392  colorpossible = FALSE;
393  break;
394  }
395  firstedge++;
396  }
397  if ( colorpossible == TRUE )
398  {
399  colors[node] = j;
400  }
401  else
402  {
403  j++;
404  }
405  }
406  i--;
407  }
408
409  SCIPinfoMessage(scip, file, "%s %d generated by ColumnGenerationColoring\n", name, actcolor);
410  for ( i = 0; i < nnodes; i++ )
411  {
412  SCIPinfoMessage(scip, file, "%d ", colors[i]);
413  }
414
415  SCIPfreeBufferArray(scip, &colors);
416
417  *result = SCIP_SUCCESS;
418
419  return SCIP_OKAY;
420 }/*lint !e715*/
421
422
423 /*
424  * reader specific interface methods
425  */
426
427 /** includes the csol file reader in SCIP */
429  SCIP* scip /**< SCIP data structure */
430  )
431 {
434
435  /* create csol reader data */
437
438  /* include csol reader */
441
445
446  return SCIP_OKAY;
447 }
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_setppc.c:9372
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
int COLORprobGetOriginalNNodes(SCIP *scip)
static long getNextNumber(char **s)
struct TCLIQUE_Graph TCLIQUE_GRAPH
Definition: tclique.h:40
problem data for vertex coloring algorithm
SCIP_RETCODE SCIPchgVarUbLazy(SCIP *scip, SCIP_VAR *var, SCIP_Real lazyub)
Definition: scip_var.c:5161
#define FALSE
Definition: def.h:87
struct SCIP_VarData SCIP_VARDATA
Definition: type_var.h:107
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
file reader for vertex coloring instances
void COLORprobGetStableSets(SCIP *scip, int ***stablesets, int **nelements, int *nstablesets)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
int COLORprobGetNewNodeForOriginalNode(SCIP *scip, int node)
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1066
int * COLORprobGetOriginalNodesForNewNodes(SCIP *scip)
SCIP_FILE * SCIPfopen(const char *path, const char *mode)
Definition: fileio.c:144
TCLIQUE_GRAPH * COLORprobGetGraph(SCIP *scip)
#define SCIPerrorMessage
Definition: pub_message.h:55
int COLORprobGetNNodes(SCIP *scip)
struct SCIP_File SCIP_FILE
Definition: pub_fileio.h:34
char * SCIPfgets(char *s, int size, SCIP_FILE *stream)
Definition: fileio.c:191
SCIP_RETCODE COLORprobAddVarForStableSet(SCIP *scip, int setindex, SCIP_VAR *var)
SCIP_RETCODE COLORprobAddNewStableSet(SCIP *scip, int *stablesetnodes, int nstablesetnodes, int *setindex)
TCLIQUE_GRAPH * COLORprobGetOriginalGraph(SCIP *scip)
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_VAR * COLORprobGetVarForStableSet(SCIP *scip, int setindex)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define COL_MAX_LINELEN
#define SCIP_Bool
Definition: def.h:84
SCIP_CONS ** COLORprobGetConstraints(SCIP *scip)
int * tcliqueGetLastAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
Definition: scip_var.c:105
int * COLORprobGetDeletedNodes(SCIP *scip)
int * tcliqueGetFirstAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)