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