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