Scippy

SCIP

Solving Constraint Integer Programs

reader_sch.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_sch.c
17  * @brief scheduling problem file reader for RCPSP/max format
18  * @author Stefan Heinz
19  *
20  * This reader is capabale of parsing resource-constrained project scheduling problem with minimal and maximal time lags
21  * (RCPSP/max) instances. The <a http://www.wior.uni-karlsruhe.de/LS_Neumann/Forschung/ProGenMax/rcpspmax.html">PSPlib</a>
22  * provides several instances set.
23  *
24  */
25 
26 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
27 
28 #include <assert.h>
29 #include <string.h>
30 #include <ctype.h>
31 
32 #include "reader_sch.h"
33 #include "reader_sm.h"
34 
36 
37 
38 #define READER_NAME "schreader"
39 #define READER_DESC "scheduling file reader for sch files (RCPSP/max format)"
40 #define READER_EXTENSION "sch"
41 
42 
43 #define SCH_MAX_LINELEN 65536 /**< size of the line buffer for reading or writing */
44 
45 /*
46  * Local methods
47  */
48 
49 static
51  SCIP* scip /**< SCIP data structure */
52  )
53 {
54  SCIP_CONS* cons;
55  SCIP_VAR** vars;
56  SCIP_Real* bounds;
57  SCIP_BOUNDTYPE* boundtypes;
58  int nvars;
59  int v;
60 
61  nvars = SCIPgetNVars(scip);
62  vars = SCIPgetVars(scip);
63 
64  SCIP_CALL( SCIPallocBufferArray(scip, &bounds, nvars) );
65  SCIP_CALL( SCIPallocBufferArray(scip, &boundtypes, nvars) );
66 
67  for( v = 0; v < nvars; ++v )
68  {
69  bounds[v] = SCIPvarGetLbGlobal(vars[v]);
70  boundtypes[v] = SCIP_BOUNDTYPE_UPPER;
71  }
72 
73  /* add a constraint that at least one jobs needs to start at its lower bound */
74  SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &cons, "lowerbound", nvars, vars, boundtypes, bounds,
76 
77  SCIP_CALL( SCIPaddCons(scip, cons) );
78  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
79 
80  SCIPfreeBufferArray(scip, &boundtypes);
81  SCIPfreeBufferArray(scip, &bounds);
82 
83  return SCIP_OKAY;
84 }
85 
86 
87 
88 /** parse job id and check if only one job mode is present */
89 static
91  SCIP* scip, /**< SCIP data structure */
92  const char* str, /**< string to search */
93  int* job, /**< pointer to store the parsed job id */
94  char** endptr /**< pointer to store the final string position if successfully parsed */
95  )
96 {
97  int mode;
98 
99  /* get job id */
100  if( !SCIPstrToIntValue(str, job, endptr) )
101  return SCIP_READERROR;
102 
103  /* get job mode */
104  if( !SCIPstrToIntValue(*endptr, &mode, endptr) )
105  return SCIP_READERROR;
106 
107  if( mode != 1 )
108  {
109  SCIPwarningMessage(scip, "jobs with different modes are not supported\n");
110  return SCIP_READERROR;
111  }
112 
113  return SCIP_OKAY;
114 }
115 
116 /** parse job and capacities details */
117 static
119  SCIP* scip, /**< SCIP data structure */
120  SCIP_FILE* file, /**< file to parse */
121  int* lineno, /**< pointer to store line number of the file */
122  int** demands, /**< demand matrix resource job demand */
123  SCIP_DIGRAPH* precedencegraph, /**< direct graph to store the precedence conditions */
124  int* durations, /**< array to store the processing for each job */
125  int* capacities, /**< array to store the different capacities */
126  int njobs, /**< number of jobs to be parsed */
127  int nresources /**< number of capacities to be parsed */
128  )
129 {
130  char buf[SCH_MAX_LINELEN];
131  char* endptr;
132  int j;
133 
134  /* get data for each job including a dummy job at the beginning and a dummy job at the end */
135  for( j = 0; j < njobs; ++j )
136  {
137  if( NULL != SCIPfgets(buf, (int) sizeof(buf), file) )
138  {
139  int* successors;
140  int distance;
141  int nsuccessors;
142  int job;
143  int s;
144 
145  /* get job id and check if only one mode is present */
146  SCIP_CALL( getJobId(scip, buf, &job, &endptr) );
147 
148  SCIPdebugMessage("job %d -> ", j);
149 
150  /* get number of direct successors */
151  if( !SCIPstrToIntValue(endptr, &nsuccessors, &endptr) )
152  return SCIP_READERROR;
153 
154  /* allocate buffer to temporarily collect the successors */
155  SCIP_CALL( SCIPallocBufferArray(scip, &successors, nsuccessors) );
156 
157  /* parse successor job ids */
158  for( s = 0; s < nsuccessors; ++s )
159  {
160  if( !SCIPstrToIntValue(endptr, &successors[s], &endptr) )
161  return SCIP_READERROR;
162  }
163 
164  /* parse distances between the job and its successor and add the arc with their data to the precedence graph */
165  for( s = 0; s < nsuccessors; ++s )
166  {
167  char token[SCIP_MAXSTRLEN];
168  char* tmpptr;
169 
170  SCIPstrCopySection(endptr, '[', ']', token, SCIP_MAXSTRLEN, &endptr);
171 
172  if( SCIPstrToIntValue(token, &distance, &tmpptr) )
173  {
174  SCIP_CALL( SCIPdigraphAddArc(precedencegraph, job, successors[s], (void*)(size_t)distance) ); /*lint !e571*/
175 
176  SCIPdebugPrintf(" %d[%d] ", successors[s], distance);
177  }
178  else
179  return SCIP_READERROR;
180  }
181 
182  SCIPdebugPrintf("\n");
183 
184  /* free the buffers */
185  SCIPfreeBufferArray(scip, &successors);
186  }
187  else
188  return SCIP_READERROR;
189 
190  (*lineno)++;
191  }
192 
193  /* get data for each job including a dummy job at the beginning and a dummy job at the end */
194  for( j = 0; j < njobs; ++j )
195  {
196  if( NULL != SCIPfgets(buf, (int) sizeof(buf), file) )
197  {
198  int job;
199  int r;
200 
201  /* get job id and check if only one mode is present */
202  SCIP_CALL( getJobId(scip, buf, &job, &endptr) );
203 
204  /* get processing time */
205  if( !SCIPstrToIntValue(endptr, &durations[job], &endptr) )
206  return SCIP_READERROR;
207 
208  SCIPdebugMessage("job %d has a processing times: %d\n", job, durations[job]);
209 
210  for( r = 0; r < nresources; ++r )
211  {
212  if( !SCIPstrToIntValue(endptr, &demands[job][r], &endptr) )
213  return SCIP_READERROR;
214  }
215  }
216  else
217  return SCIP_READERROR;
218 
219  (*lineno)++;
220  }
221 
222  /* get resources capacities */
223  if( nresources > 0 && NULL != SCIPfgets(buf, (int) sizeof(buf), file) )
224  {
225  int r;
226 
227  SCIPdebugMessage("line %d %s", *lineno, buf);
228 
229  if( !SCIPstrToIntValue(buf, &capacities[0], &endptr) )
230  return SCIP_READERROR;
231 
232  SCIPdebugMessage("paresed capacities: <%d>", capacities[0]);
233 
234  for( r = 1; r < nresources; ++r )
235  {
236  if( !SCIPstrToIntValue(endptr, &capacities[r], &endptr) )
237  return SCIP_READERROR;
238 
239  SCIPdebugPrintf(", <%d>", capacities[r]);
240  }
241 
242  SCIPdebugPrintf("\n");
243  }
244  else
245  return SCIP_READERROR;
246 
247  (*lineno)++;
248 
249  return SCIP_OKAY;
250 }
251 
252 /** read file and create problem */
253 static
255  SCIP* scip, /**< SCIP data structure */
256  SCIP_FILE* file, /**< file to pares */
257  const char* filename /**< name of input file */
258  )
259 {
260  SCIP_RETCODE retcode;
261  char buf[SCH_MAX_LINELEN];
262  SCIP_DIGRAPH* precedencegraph;
263  int** demands;
264  int* durations;
265  int* capacities;
266  int lineno;
267  int njobs;
268  int nresources;
269  int j;
270 
271  assert(scip != NULL);
272  assert(file != NULL);
273  assert(filename != NULL);
274 
275  lineno = 0;
276 
277  /* get number of jobs and resources */
278  if( NULL != SCIPfgets(buf, (int) sizeof(buf), file) )
279  {
280  char* endptr;
281  int value;
282 
283  lineno++;
284 
285  if( !SCIPstrToIntValue(buf, &value, &endptr) )
286  return SCIP_READERROR;
287 
288  /* note that this format includes two dummy jobs */
289  njobs = value + 2;
290 
291  /* get number of resources */
292  if( !SCIPstrToIntValue(endptr, &nresources, &endptr) )
293  return SCIP_READERROR;
294  }
295  else
296  return SCIP_READERROR;
297 
298  SCIP_CALL( SCIPallocBufferArray(scip, &capacities, nresources) );
299  SCIP_CALL( SCIPallocBufferArray(scip, &durations, njobs) );
300  SCIP_CALL( SCIPallocBufferArray(scip, &demands, njobs) );
301 
302  for( j = 0; j < njobs; ++j )
303  {
304  SCIP_CALL( SCIPallocBufferArray(scip, &demands[j], nresources) ); /*lint !e866*/
305  BMSclearMemoryArray(demands[j], nresources); /*lint !e866*/
306  }
307 
308  SCIP_CALL( SCIPcreateDigraph(scip, &precedencegraph, njobs) );
309 
310  SCIPdebugMessage("problem has <%d> jobs and <%d> resources\n", njobs, nresources);
311 
312  retcode = parseDetails(scip, file, &lineno, demands, precedencegraph, durations, capacities, njobs, nresources);
313 
314  if( retcode == SCIP_OKAY )
315  {
316  SCIP_CALL( SCIPcreateSchedulingProblem(scip, filename, NULL, NULL, demands,
317  precedencegraph, durations, capacities, njobs, nresources, FALSE) );
318  }
319 
320  /* add constraint that at least one job needs to start on its lower bound */
321  SCIP_CALL( addLowerboundCons(scip) );
322 
323  /* free the precedence graph */
324  SCIPdigraphFree(&precedencegraph);
325 
326  /* free buffer before evaluating the retcode */
327  for( j = njobs - 1; j >= 0; --j )
328  {
329  SCIPfreeBufferArray(scip, &demands[j]);
330  }
331  SCIPfreeBufferArray(scip, &demands);
332  SCIPfreeBufferArray(scip, &durations);
333  SCIPfreeBufferArray(scip, &capacities);
334 
335  SCIP_CALL( retcode );
336 
337  return SCIP_OKAY;
338 }
339 
340 
341 /*
342  * Callback methods of reader
343  */
344 
345 /** copy method for reader plugins (called when SCIP copies plugins) */
346 static
347 SCIP_DECL_READERCOPY(readerCopySch)
348 { /*lint --e{715}*/
349  assert(scip != NULL);
350  assert(reader != NULL);
351  assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0);
352 
353  /* call inclusion method of reader handler */
355 
356  return SCIP_OKAY;
357 }/*lint !e830*/
358 
359 /** problem reading method of reader */
360 static
361 SCIP_DECL_READERREAD(readerReadSch)
362 { /*lint --e{715}*/
363  SCIP_FILE* file;
364  SCIP_RETCODE retcode;
365 
366  if( NULL == (file = SCIPfopen(filename, "r")) )
367  {
368  SCIPerrorMessage("cannot open file <%s> for reading\n", filename);
369  SCIPprintSysError(filename);
370  return SCIP_NOFILE;
371  }
372 
373  /* read file */
374  retcode = readFile(scip, file, filename);
375 
376  /* close file */
377  SCIPfclose(file);
378 
379  /* check retcode after the file was closed */
380  SCIP_CALL( retcode );
381 
382  (*result) = SCIP_SUCCESS;
383 
384  return SCIP_OKAY;
385 }/*lint !e830*/
386 
387 #ifdef SCIP_DISABLED_CODE
388 /** destructor of reader to free user data (called when SCIP is exiting) */
389 #define readerFreeSch NULL
390 
391 /** problem writing method of reader */
392 #define readerWriteSch NULL
393 #endif
394 
395 /*
396  * reader specific interface methods
397  */
398 
399 /** includes the sch file reader in SCIP */
401  SCIP* scip /**< SCIP data structure */
402  )
403 {
404  SCIP_READERDATA* readerdata;
405  SCIP_READER* reader;
406 
407  /* create sch reader data */
408  readerdata = NULL;
409 
410  /* include sch reader */
412  assert(reader != NULL);
413 
414  SCIP_CALL( SCIPsetReaderCopy(scip, reader, readerCopySch) );
415  SCIP_CALL( SCIPsetReaderRead(scip, reader, readerReadSch) );
416 
417  /* add reader parameters */
419  "reading/"READER_NAME"/mipmodel", "create MIP model?",
420  NULL, FALSE, FALSE, NULL, NULL) );
421 
422  return SCIP_OKAY;
423 }
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
SCIP_EXPORT const char * SCIPreaderGetName(SCIP_READER *reader)
Definition: reader.c:548
static SCIP_RETCODE getJobId(SCIP *scip, const char *str, int *job, char **endptr)
Definition: reader_sch.c:90
SCIP_RETCODE SCIPcreateDigraph(SCIP *scip, SCIP_DIGRAPH **digraph, int nnodes)
#define SCIP_MAXSTRLEN
Definition: def.h:273
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:123
static SCIP_DECL_READERREAD(readerReadSch)
Definition: reader_sch.c:361
SCIP_RETCODE SCIPsetReaderRead(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERREAD((*readerread)))
Definition: scip_reader.c:186
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1986
#define FALSE
Definition: def.h:73
void SCIPstrCopySection(const char *str, char startchar, char endchar, char *token, int size, char **endptr)
Definition: misc.c:10735
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
static SCIP_RETCODE readFile(SCIP *scip, SCIP_FILE *file, const char *filename)
Definition: reader_sch.c:254
void SCIPdigraphFree(SCIP_DIGRAPH **digraph)
Definition: misc.c:7470
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 SCIPdebugMessage
Definition: pub_message.h:87
static SCIP_RETCODE parseDetails(SCIP *scip, SCIP_FILE *file, int *lineno, int **demands, SCIP_DIGRAPH *precedencegraph, int *durations, int *capacities, int njobs, int nresources)
Definition: reader_sch.c:118
SCIP_FILE * file
Definition: reader_cmin.c:61
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
char * token
Definition: reader_cmin.c:63
static SCIP_RETCODE addLowerboundCons(SCIP *scip)
Definition: reader_sch.c:50
SCIP_FILE * SCIPfopen(const char *path, const char *mode)
Definition: fileio.c:144
SCIP_RETCODE SCIPincludeReaderSch(SCIP *scip)
Definition: reader_sch.c:400
#define SCIPerrorMessage
Definition: pub_message.h:55
#define SCIPdebugPrintf
Definition: pub_message.h:90
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1941
struct SCIP_File SCIP_FILE
Definition: pub_fileio.h:34
char * SCIPfgets(char *s, int size, SCIP_FILE *stream)
Definition: fileio.c:191
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:364
#define READER_NAME
Definition: reader_sch.c:38
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
struct SCIP_ReaderData SCIP_READERDATA
Definition: type_reader.h:44
SCIP_RETCODE SCIPcreateSchedulingProblem(SCIP *scip, const char *problemname, const char **jobnames, const char **resourcenames, int **demands, SCIP_DIGRAPH *precedencegraph, int *durations, int *capacities, int njobs, int nresources, SCIP_Bool initialize)
Definition: reader_sm.c:738
#define SCH_MAX_LINELEN
Definition: reader_sch.c:43
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
scheduling problem file reader for RCPSP format
SCIP_Real * r
Definition: circlepacking.c:50
#define READER_DESC
Definition: reader_sch.c:39
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17667
#define SCIP_Real
Definition: def.h:163
#define READER_EXTENSION
Definition: reader_sch.c:40
void SCIPprintSysError(const char *message)
Definition: misc.c:10513
SCIP_RETCODE SCIPcreateConsBounddisjunction(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_BOUNDTYPE *boundtypes, SCIP_Real *bounds, 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)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2764
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:122
static SCIP_DECL_READERCOPY(readerCopySch)
Definition: reader_sch.c:347
int SCIPfclose(SCIP_FILE *fp)
Definition: fileio.c:223
SCIP_Bool SCIPstrToIntValue(const char *str, int *value, char **endptr)
Definition: misc.c:10674
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
constraint handler for bound disjunction constraints
scheduling problem file reader for RCPSP/max format
SCIP_RETCODE SCIPdigraphAddArc(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
Definition: misc.c:7564