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