Scippy

SCIP

Solving Constraint Integer Programs

reader_csol.c
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 reader_csol.c
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 
35 #include "reader_csol.h"
36 #include "reader_col.h"
37 #include "probdata_coloring.h"
38 
39 
40 #define READER_NAME "csolreader"
41 #define READER_DESC "file reader which reads and writes csol-files"
42 #define READER_EXTENSION "csol"
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);
62  /* read number */
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
75 SCIP_DECL_READERCOPY(readerCopyCsol)
76 { /*lint --e{715}*/
77  assert(scip != NULL);
78  assert(reader != NULL);
79  assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0);
80 
81  return SCIP_OKAY;
82 }
83 
84 /** problem reading method of reader */
85 static
86 SCIP_DECL_READERREAD(readerReadCsol)
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 
110  assert(reader != NULL);
111  assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0);
112  assert(scip != NULL);
113  assert(result != NULL);
114  assert(filename != NULL);
115  *result = SCIP_SUCCESS;
116 
118  {
119  SCIPerrorMessage("Please read in problem before reading the solution!\n");
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 )
132  return SCIP_READERROR;
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) );
279  SCIP_CALL( SCIPaddVar(scip, 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
312 SCIP_DECL_READERWRITE(readerWriteCsol)
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;
386  firstedge = tcliqueGetFirstAdjedge(oldgraph, node);
387  lastedge = tcliqueGetLastAdjedge(oldgraph, node);
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 {
432  SCIP_READERDATA* readerdata;
433  SCIP_READER* reader;
434 
435  /* create csol reader data */
436  readerdata = NULL;
437 
438  /* include csol reader */
440  readerdata) );
441 
442  SCIP_CALL( SCIPsetReaderCopy(scip, reader, readerCopyCsol) );
443  SCIP_CALL( SCIPsetReaderRead(scip, reader, readerReadCsol) );
444  SCIP_CALL( SCIPsetReaderWrite(scip, reader, readerWriteCsol) );
445 
446  return SCIP_OKAY;
447 }
#define NULL
Definition: def.h:239
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_setppc.c:9227
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:412
int COLORprobGetOriginalNNodes(SCIP *scip)
static long getNextNumber(char **s)
Definition: reader_csol.c:54
struct TCLIQUE_Graph TCLIQUE_GRAPH
Definition: tclique.h:40
problem data for vertex coloring algorithm
const char * SCIPreaderGetName(SCIP_READER *reader)
Definition: reader.c:547
SCIP_RETCODE SCIPchgVarUbLazy(SCIP *scip, SCIP_VAR *var, SCIP_Real lazyub)
Definition: scip_var.c:5086
#define FALSE
Definition: def.h:65
struct SCIP_VarData SCIP_VARDATA
Definition: type_var.h:107
static SCIP_DECL_READERREAD(readerReadCsol)
Definition: reader_csol.c:86
SCIP_RETCODE SCIPincludeReaderCsol(SCIP *scip)
Definition: reader_csol.c:428
#define TRUE
Definition: def.h:64
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
file reader for vertex coloring instances
void COLORprobGetStableSets(SCIP *scip, int ***stablesets, int **nelements, int *nstablesets)
#define READER_NAME
Definition: reader_csol.c:40
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:279
int COLORprobGetNewNodeForOriginalNode(SCIP *scip, int node)
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1123
int * COLORprobGetOriginalNodesForNewNodes(SCIP *scip)
SCIP_FILE * SCIPfopen(const char *path, const char *mode)
Definition: fileio.c:140
#define READER_DESC
Definition: reader_csol.c:41
TCLIQUE_GRAPH * COLORprobGetGraph(SCIP *scip)
static SCIP_DECL_READERWRITE(readerWriteCsol)
Definition: reader_csol.c:312
#define SCIPerrorMessage
Definition: pub_message.h:45
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:187
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 SCIP_CALL(x)
Definition: def.h:351
SCIP_VAR * COLORprobGetVarForStableSet(SCIP *scip, int setindex)
static SCIP_DECL_READERCOPY(readerCopyCsol)
Definition: reader_csol.c:75
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
struct SCIP_ReaderData SCIP_READERDATA
Definition: type_reader.h:37
#define COL_MAX_LINELEN
Definition: reader_csol.c:44
#define SCIP_Bool
Definition: def.h:62
SCIP_CONS ** COLORprobGetConstraints(SCIP *scip)
SCIP_RETCODE SCIPincludeReaderBasic(SCIP *scip, SCIP_READER **readerptr, const char *name, const char *desc, const char *extension, SCIP_READERDATA *readerdata)
Definition: scip_reader.c:180
int * tcliqueGetLastAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
#define READER_EXTENSION
Definition: reader_csol.c:42
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:104
int * COLORprobGetDeletedNodes(SCIP *scip)
int * tcliqueGetFirstAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
SCIP_RETCODE SCIPsetReaderWrite(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERWRITE((*readerwrite)))
Definition: scip_reader.c:290
SCIP_RETCODE SCIPsetReaderCopy(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERCOPY((*readercopy)))
Definition: scip_reader.c:218
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2379
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1724
void SCIPsortDownInt(int *intarray, int len)
SCIP_RETCODE SCIPsetReaderRead(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERREAD((*readerread)))
Definition: scip_reader.c:266
#define nnodes
Definition: gastrans.c:65
file reader and writer for vertex coloring solutions
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1410