Scippy

SCIP

Solving Constraint Integer Programs

reader_lop.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-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 reader_lop.c
17  * @brief linear ordering file reader
18  * @author Marc Pfetsch
19  *
20  * This file implements the reader/parser used to read linear ordering problems. For more details see \ref READER. The
21  * data should be given in LOLIB format, see <a href="http://grafo.etsii.urjc.es/optsicom/lolib/">LOLIB</a>.
22  */
23 
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
25 
26 #include <assert.h>
27 #include <string.h>
28 #include <ctype.h>
29 
30 #include "cons_lop.h"
31 #include "reader_lop.h"
32 #include <scip/pub_fileio.h>
33 
34 #define READER_NAME "lopreader"
35 #define READER_DESC "file reader for linear ordering problems"
36 #define READER_EXTENSION "lop"
37 
38 #define READER_STRLEN 65536
39 
40 /* ----------------- auxiliary functions ------------------------ */
41 
42 /** Get next number from file */
43 static
45  SCIP_FILE* file, /**< file to read from */
46  char* buffer, /**< buffer to store lines in */
47  char** s, /**< pointer to string pointer */
48  SCIP_Real* value /**< pointer to store the read value */
49  )
50 {
51  assert( file != NULL );
52  assert( buffer != NULL );
53  assert( s != NULL );
54  assert( value != NULL );
55 
56  *value = SCIP_INVALID; /* for debugging */
57 
58  /* skip whitespace */
59  while ( isspace(**s) )
60  ++(*s);
61 
62  /* if we reached the end of the line, read new line */
63  if ( **s == '\n' || **s == '\0' )
64  {
65  /* read line into buffer */
66  if ( SCIPfgets(buffer, READER_STRLEN, file) == NULL )
67  {
68  SCIPerrorMessage("Error reading from file.\n");
69  return SCIP_READERROR;
70  }
71  *s = buffer;
72 
73  /* skip whitespace */
74  while ( isspace(**s) )
75  ++(*s);
76  }
77 
78  /* check whether we found a number */
79  if ( isdigit(**s) || **s == '-' || **s == '+' )
80  {
81  *value = atof(*s);
82 
83  /* skip number */
84  while ( isdigit(**s) || **s == '-' || **s == '+' )
85  ++(*s);
86  }
87  else
88  {
89  SCIPerrorMessage("Error reading from file.\n");
90  return SCIP_READERROR;
91  }
92 
93  return SCIP_OKAY;
94 }
95 
96 
97 
98 /** read weight matrix from file (in LOLIB format)
99  *
100  * Format:
101  * comment line
102  * n = # of elements
103  * weight matrix (n times n double matrix)
104  */
105 static
107  SCIP* scip, /**< SCIP data structure */
108  const char* filename, /**< name of file to read */
109  int* n, /**< pointer to store the number of elements on exit */
110  SCIP_Real*** W /**< pointer to store the weight matrix on exit */
111  )
112 {
113  char buffer[READER_STRLEN];
114  SCIP_FILE* file;
115  char* s;
116  char* nstr;
117  int i;
118  int j;
119 
120  assert( n != NULL );
121  assert( W != NULL );
122 
123  /* open file */
124  file = SCIPfopen(filename, "r");
125  if ( file == NULL )
126  {
127  SCIPerrorMessage("Could not open file <%s>.\n", filename);
128  SCIPprintSysError(filename);
129  return SCIP_NOFILE;
130  }
131 
132  /* skip lines as comments until we found the first line that only contains the number of elements */
133  *n = -1;
134  do
135  {
136  /* read line */
137  if ( SCIPfgets(buffer, READER_STRLEN, file) == NULL )
138  {
139  SCIPerrorMessage("Error reading file <%s>.\n", filename);
140  return SCIP_READERROR;
141  }
142 
143  /* skip whitespace */
144  s = buffer;
145  while( isspace(*s) )
146  ++s;
147 
148  /* check whether rest of line only contains whitespace or numbers */
149  nstr = s;
150  while ( *s != '\0' && (isspace(*s) || isdigit(*s)) )
151  ++s;
152 
153  /* if the line only contains a number, use this as the number of elements */
154  if ( *s == '\0' || *s == '\n' )
155  *n = atoi(nstr);
156  }
157  while ( ! SCIPfeof(file) && *n < 0 );
158 
159  if ( *n <= 0 )
160  {
161  SCIPerrorMessage("Reading of number of elements failed.\n");
162  return SCIP_READERROR;
163  }
164  assert( *n > 0 );
165 
166  /* set up matrix */
167  SCIP_CALL( SCIPallocBlockMemoryArray(scip, W, *n) );
168  for (i = 0; i < *n; ++i)
169  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*W)[i]), *n) ); /*lint !e866*/
170 
171  /* read weight matrix */
172  for (i = 0; i < *n; ++i)
173  {
174  for (j = 0; j < *n; ++j)
175  {
176  SCIP_Real val;
177 
178  SCIP_CALL( getNextNumber(file, buffer, &s, &val) );
179  assert( val != SCIP_INVALID );
180  (*W)[i][j] = val;
181  }
182  }
183  (void) SCIPfclose(file);
184 
185  return SCIP_OKAY;
186 }
187 
188 /** get problem name
189  *
190  * Returns NULL on error
191  */
192 static
194  const char* filename, /**< input filename */
195  char* probname, /**< output problemname */
196  int maxSize /**< maximum size of probname */
197  )
198 {
199  int i = 0;
200  int j = 0;
201  int l;
202 
203  /* first find end of string */
204  while ( filename[i] != 0)
205  ++i;
206  l = i;
207 
208  /* go back until '.' or '/' or '\' appears */
209  while ((i > 0) && (filename[i] != '.') && (filename[i] != '/') && (filename[i] != '\\'))
210  --i;
211 
212  /* if we found '.', search for '/' or '\\' */
213  if (filename[i] == '.')
214  {
215  l = i;
216  while ((i > 0) && (filename[i] != '/') && (filename[i] != '\\'))
217  --i;
218  }
219 
220  /* correct counter */
221  if ((filename[i] == '/') || (filename[i] == '\\'))
222  ++i;
223 
224  /* copy name */
225  while ( (i < l) && (filename[i] != 0) )
226  {
227  probname[j++] = filename[i++];
228  if (j > maxSize-1)
229  return SCIP_ERROR;
230  }
231  probname[j] = 0;
232 
233  return SCIP_OKAY;
234 }
235 
236 
237 
238 /**@name Callback methods
239  *
240  * @{
241  */
242 
243 /** problem reading method of reader */
244 static
245 SCIP_DECL_READERREAD(LOPreaderRead)
246 { /*lint --e{715}*/
247  char name[SCIP_MAXSTRLEN];
248  SCIP_VAR*** vars;
249  SCIP_CONS* cons;
250  SCIP_Real** W;
251  int n;
252  int i;
253  int j;
254 
255  assert( scip != NULL );
256  assert( result != NULL );
257 
258  *result = SCIP_DIDNOTRUN;
259 
260  SCIPinfoMessage(scip, NULL, "File name:\t\t%s\n", filename);
261 
262  /* read problem */
263  SCIP_CALL( LOPreadFile(scip, filename, &n, &W) );
264 
265  /* generate problem name from filename */
266  SCIP_CALL( getProblemName(filename, name, SCIP_MAXSTRLEN) );
267 
268  SCIPinfoMessage(scip, NULL, "Problem name:\t\t%s\n", name);
269  SCIPinfoMessage(scip, NULL, "Number of elements:\t%d\n\n", n);
270 
271  /* create problem */
273 
274  /* set maximization */
276 
277  /* generate variables */
279  for (i = 0; i < n; ++i)
280  {
281  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(vars[i]), n) );
282  for (j = 0; j < n; ++j)
283  {
284  if (j != i)
285  {
286  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "x#%d#%d", i, j);
287  SCIP_CALL( SCIPcreateVar(scip, &(vars[i][j]), name, 0.0, 1.0, W[i][j], SCIP_VARTYPE_BINARY,
288  TRUE, FALSE, NULL, NULL, NULL, NULL, NULL));
289  SCIP_CALL( SCIPaddVar(scip, vars[i][j]) );
290  }
291  else
292  vars[i][j] = NULL;
293  }
294  }
295 
296  /* generate linear ordering constraint */
297  SCIP_CALL( SCIPcreateConsLOP(scip, &cons, "LOP", n, vars, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE,
298  FALSE, FALSE, FALSE, FALSE));
299  SCIP_CALL( SCIPaddCons(scip, cons) );
300  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
301 
302  /* print small model */
303  if ( n <= 10 )
304  {
306  SCIPinfoMessage(scip, NULL, "\n");
307  }
308 
309  /* free memory */
310  for (i = 0; i < n; ++i)
311  {
312  for (j = 0; j < n; ++j)
313  {
314  if (j != i)
315  {
316  SCIP_CALL( SCIPreleaseVar(scip, &(vars[i][j])) );
317  }
318  }
319  SCIPfreeBlockMemoryArray(scip, &(vars[i]), n);
320  SCIPfreeBlockMemoryArray(scip, &(W[i]), n);
321  }
322  SCIPfreeBlockMemoryArray(scip, &vars, n);
324 
325  *result = SCIP_SUCCESS;
326 
327  return SCIP_OKAY;
328 }
329 
330 /**@} */
331 
332 
333 /**@name Interface methods
334  *
335  * @{
336  */
337 
338 /** includes the linear ordering file reader in SCIP */
340  SCIP* scip /**< SCIP data structure */
341  )
342 {
343  SCIP_READER* reader;
344 
345  /* include reader */
347  assert( reader != NULL );
348 
349  SCIP_CALL( SCIPsetReaderRead(scip, reader, LOPreaderRead) );
350 
351  return SCIP_OKAY;
352 }
353 
354 /**@} */
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:101
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
SCIP_RETCODE SCIPcreateConsLOP(SCIP *scip, SCIP_CONS **cons, const char *name, int n, SCIP_VAR ***vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_lop.c:1196
static SCIP_RETCODE getNextNumber(SCIP_FILE *file, char *buffer, char **s, SCIP_Real *value)
Definition: reader_lop.c:44
#define SCIP_MAXSTRLEN
Definition: def.h:293
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1245
#define FALSE
Definition: def.h:87
#define READER_STRLEN
Definition: reader_lop.c:38
static SCIP_RETCODE LOPreadFile(SCIP *scip, const char *filename, int *n, SCIP_Real ***W)
Definition: reader_lop.c:106
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition: scip_prob.c:171
SCIP_FILE * SCIPfopen(const char *path, const char *mode)
Definition: fileio.c:144
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
Definition: scip_prob.c:1241
SCIP_RETCODE SCIPincludeReaderLOP(SCIP *scip)
Definition: reader_lop.c:339
#define SCIPerrorMessage
Definition: pub_message.h:55
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2769
constraint handler for linear ordering constraints
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
#define READER_DESC
Definition: reader_lop.c:35
SCIP_RETCODE SCIPprintOrigProblem(SCIP *scip, FILE *file, const char *extension, SCIP_Bool genericnames)
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:384
wrapper functions to map file i/o to standard or zlib file i/o
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
void SCIPprintSysError(const char *message)
Definition: misc.c:10664
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
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1667
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
#define SCIP_Real
Definition: def.h:177
#define SCIP_INVALID
Definition: def.h:197
static SCIP_DECL_READERREAD(LOPreaderRead)
Definition: reader_lop.c:245
SCIP_RETCODE SCIPsetReaderRead(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERREAD((*readerread)))
Definition: scip_reader.c:186
#define READER_NAME
Definition: reader_lop.c:34
linear ordering file reader
int SCIPfclose(SCIP_FILE *fp)
Definition: fileio.c:223
#define READER_EXTENSION
Definition: reader_lop.c:36
static SCIP_RETCODE getProblemName(const char *filename, char *probname, int maxSize)
Definition: reader_lop.c:193