Scippy

SCIP

Solving Constraint Integer Programs

reader_cyc.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-2020 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 reader_cyc.c
17  * @brief file reader for cycle clustering instances
18  * @author Leon Eifler
19  *
20  * This file implements the reader for the cycle clustering problem. The data is read from a matrix, entries separated
21  * by whitespace. The first line in the file has to be of the form "# p nstates ncluster",
22  * where nstates is the size of the matrix and ncluster is the number of clusters that should be used.
23  * The file has to have the ending ".cyc" to be recognized by the reader.
24  */
25 
26 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
27 #include "reader_cyc.h"
28 
29 #include <assert.h>
30 #include <string.h>
31 #include <ctype.h>
32 #include "probdata_cyc.h"
33 
34 #define READER_NAME "cycreader"
35 #define READER_DESC "file reader for a .cyc-file with a transition matrix for a cycle clustering problem"
36 #define READER_EXTENSION "cyc"
37 
38 #define COL_MAX_LINELEN 10000
39 
40 
41 /*
42  * Local methods
43  */
44 
45 /** get next number from string s */
46 static
48  char** s /**< pointer to the pointer of the current position in the string */
49  )
50 {
51  SCIP_Real tmp;
52 
53  /* skip whitespaces */
54  while( isspace(**s) )
55  ++(*s);
56  /* read number */
57  tmp = atof(*s);
58  /* skip whitespaces */
59  while( (**s != 0) && (!isspace(**s)) )
60  ++(*s);
61 
62  return tmp;
63 }
64 
65 /** read LP in Cyc File Format.
66  * That means first line is "p edges nbins ncluster".
67  * Then a matrix with whitespace-separated entries of size nbins x nbins
68 */
69 static
71  SCIP* scip, /**< SCIP data structure */
72  const char* filename /**< name of the input file */
73  )
74 {
75  SCIP_FILE* fp; /* file-reader */
76  char buf[COL_MAX_LINELEN]; /* maximal length of line */
77  char* char_p; /* current char */
78  SCIP_Real** cmatrix; /* transition matrix */
79  int nbins; /* number of states */
80  int ncluster; /* number of clusters */
81  int i;
82  int col;
83 
84  assert(scip != NULL);
85  assert(filename != NULL);
86 
87  if( NULL == (fp = SCIPfopen(filename, "r")) )
88  {
89  SCIPerrorMessage("cannot open file <%s> for reading\n", filename);
90  perror(filename);
91  return SCIP_NOFILE;
92  }
93 
94  /* Get problem name from filename and save it */
95  if( SCIPfgets(buf, (int) sizeof(buf), fp) == NULL )
96  return SCIP_READERROR;
97 
98  while( !SCIPfeof(fp) && (buf[0] != '#' || buf[2] != 'p') )
99  {
100  SCIPfgets(buf, (int) sizeof(buf), fp); /*lint !e534*/
101  }
102 
103  /* no graph information in file! */
104  if( SCIPfeof(fp) )
105  {
106  SCIPerrorMessage("Error! Could not find line starting with 'p'.\n");
107  return SCIP_READERROR;
108  }
109  char_p = &buf[3];
110 
111  /* read out number of nodes and edges, the pointer char_p will be changed */
112  nbins = (int) getNextNumber(&char_p);
113  ncluster = (int) getNextNumber(&char_p);
114 
115  if( nbins <= 0 )
116  {
117  SCIPerrorMessage("Number of bins must be positive!\n");
118  return SCIP_READERROR;
119  }
120 
121  if( ncluster <= 0 || nbins <= ncluster )
122  {
123  SCIPerrorMessage("Number of cluster must be positive and smaller than number of bins!\n");
124  return SCIP_READERROR;
125  }
126 
127  /* create cmatrix */
128  SCIP_CALL( SCIPallocMemoryArray(scip, &cmatrix, nbins) );
129  for( i = 0; i < nbins; i++ )
130  {
131  SCIP_CALL( SCIPallocMemoryArray(scip, &(cmatrix[i]), nbins) ); /*lint !e866*/
132  }
133 
134  /* fill array the cmatrix */
135  i = 0;
136  while( !SCIPfeof(fp) && i < nbins )
137  {
138  SCIPfgets(buf, (int) sizeof(buf), fp); /*lint !e534*/
139  char_p = &buf[0];
140  for( col = 0; col < nbins; ++col )
141  {
142  cmatrix[i][col] = (SCIP_Real) getNextNumber(&char_p);
143  }
144 
145  if( i >= nbins )
146  {
147  SCIPerrorMessage( "more lines than expected: expected %d many, but got already %d'th (non-duplicate) edge",
148  nbins, i+1 );
149 
150  return SCIP_READERROR;
151  }
152 
153  i++;
154  }
155 
156  /* create problem data */
157  SCIP_CALL( SCIPcreateProbCyc(scip, filename, nbins, ncluster, cmatrix) );
158 
159  SCIPinfoMessage(scip, NULL, "Original problem: \n");
160 
161  for( i = nbins - 1; i >= 0; i-- )
162  {
163  SCIPfreeMemoryArray(scip, &(cmatrix[i]));
164  }
165 
166  SCIPfreeMemoryArray(scip, &cmatrix);
167 
168  SCIPfclose(fp);
169 
170  return SCIP_OKAY;
171 }
172 
173 /*
174  * Callback methods of reader
175  */
176 
177 /** copy method for reader plugins (called when SCIP copies plugins) */
178 static
179 SCIP_DECL_READERCOPY(readerCopyCyc)
180 {
181  assert(scip != NULL);
182  assert(reader != NULL);
183  assert(strcmp( SCIPreaderGetName(reader), READER_NAME) == 0);
184 
185  return SCIP_OKAY;
186 }
187 
188 /** problem reading method of reader */
189 static
190 SCIP_DECL_READERREAD(readerReadCyc)
191 {
192  assert(reader != NULL);
193  assert(strcmp( SCIPreaderGetName(reader), READER_NAME) == 0);
194  assert(scip != NULL);
195  assert(result != NULL);
196 
197  SCIP_CALL( readCyc( scip, filename) );
198 
199  *result = SCIP_SUCCESS;
200 
201  return SCIP_OKAY;
202 }
203 
204 /*
205  * cyc file reader specific interface methods
206  */
207 
208 /** includes the cyc file reader in SCIP */
210  SCIP* scip /**< SCIP data structure */
211  )
212 {
213  SCIP_READERDATA* readerdata;
214  SCIP_READER* reader;
215 
216  /* create cyc reader data */
217  readerdata = NULL;
218 
219  /* include cyc reader */
221  readerdata) );
222 
223  SCIP_CALL( SCIPsetReaderCopy( scip, reader, readerCopyCyc) );
224  SCIP_CALL( SCIPsetReaderRead( scip, reader, readerReadCyc ) );
225 
226  SCIP_CALL( SCIPaddRealParam(scip,"cycleclustering/scale_coherence",
227  "factor to scale the cohrence in the target function", NULL, FALSE, 0.001, 0.0, 1.0, NULL, NULL ) );
228  SCIP_CALL( SCIPaddCharParam(scip, "cycleclustering/model",
229  "the model variant", NULL, FALSE, 's', "seqt", NULL, NULL) );
230  SCIP_CALL( SCIPaddBoolParam(scip, "cycleclustering/usecutselection",
231  "true if cut selection should be used in cyc-separators", NULL, FALSE, TRUE, NULL, NULL) );
232  SCIP_CALL( SCIPaddRealParam(scip, "cycleclustering/goodscorefac", "used for cut-selection in cycle-clustering",
233  NULL, FALSE, 0.8, 0.0, 1.0, NULL, NULL) );
234  SCIP_CALL( SCIPaddRealParam(scip, "cycleclustering/badscorefac", "used for cut-selection in cycle-clustering",
235  NULL, FALSE, 0.0, 0.0, 1.0, NULL, NULL) );
236  SCIP_CALL( SCIPaddRealParam(scip, "cycleclustering/goodmaxparall", "used for cut-selection in cycle-clustering",
237  NULL, FALSE, 0.1, 0.0, 1.0, NULL, NULL) );
238  SCIP_CALL( SCIPaddRealParam(scip, "cycleclustering/maxparall", "used for cut-selection in cycle-clustering",
239  NULL, FALSE, 0.5, 0.0, 1.0, NULL, NULL) );
240  SCIP_CALL( SCIPaddRealParam(scip, "cycleclustering/dircutoffdist", "used for cut-selection in cycle-clustering",
241  NULL, FALSE, 0.5, 0.0, 1.0, NULL, NULL) );
242  SCIP_CALL( SCIPaddRealParam(scip, "cycleclustering/efficacyweight", "used for cut-selection in cycle-clustering",
243  NULL, FALSE, 0.4, 0.0, 1.0, NULL, NULL) );
244  SCIP_CALL( SCIPaddRealParam(scip, "cycleclustering/objparalweight", "used for cut-selection in cycle-clustering",
245  NULL, FALSE, 0.1, 0.0, 1.0, NULL, NULL) );
246  SCIP_CALL( SCIPaddRealParam(scip, "cycleclustering/intsuppweight", "used for cut-selection in cycle-clustering",
247  NULL, FALSE, 0.3, 0.0, 1.0, NULL, NULL) );
248 
249  return SCIP_OKAY;
250 }
SCIP_EXPORT const char * SCIPreaderGetName(SCIP_READER *reader)
Definition: reader.c:548
SCIP_RETCODE SCIPcreateProbCyc(SCIP *scip, const char *name, int nbins, int ncluster, SCIP_Real **cmatrix)
SCIP_RETCODE SCIPincludeReaderCyc(SCIP *scip)
Definition: reader_cyc.c:209
#define READER_DESC
Definition: reader_cyc.c:35
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:69
static SCIP_DECL_READERCOPY(readerCopyCyc)
Definition: reader_cyc.c:179
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:53
SCIP_RETCODE SCIPsetReaderRead(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERREAD((*readerread)))
Definition: scip_reader.c:186
static SCIP_Real getNextNumber(char **s)
Definition: reader_cyc.c:47
#define FALSE
Definition: def.h:73
SCIP_RETCODE SCIPsetReaderCopy(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERCOPY((*readercopy)))
Definition: scip_reader.c:138
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
#define READER_EXTENSION
Definition: reader_cyc.c:36
SCIP_FILE * SCIPfopen(const char *path, const char *mode)
Definition: fileio.c:144
#define SCIPerrorMessage
Definition: pub_message.h:55
int SCIPfeof(SCIP_FILE *stream)
Definition: fileio.c:218
struct SCIP_File SCIP_FILE
Definition: pub_fileio.h:34
char * SCIPfgets(char *s, int size, SCIP_FILE *stream)
Definition: fileio.c:191
static SCIP_RETCODE readCyc(SCIP *scip, const char *filename)
Definition: reader_cyc.c:70
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:364
struct SCIP_ReaderData SCIP_READERDATA
Definition: type_reader.h:44
SCIP_RETCODE SCIPincludeReaderBasic(SCIP *scip, SCIP_READER **readerptr, const char *name, const char *desc, const char *extension, SCIP_READERDATA *readerdata)
Definition: scip_reader.c:100
problem data for cycle clustering problem
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:130
static SCIP_DECL_READERREAD(readerReadCyc)
Definition: reader_cyc.c:190
#define COL_MAX_LINELEN
Definition: reader_cyc.c:38
file reader for cycle clustering instances
#define SCIP_Real
Definition: def.h:163
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
int SCIPfclose(SCIP_FILE *fp)
Definition: fileio.c:223
#define READER_NAME
Definition: reader_cyc.c:34
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:158