1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 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
35 #include "scip/cons_bounddisjunction.h"
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
addLowerboundCons(SCIP * scip)50 SCIP_RETCODE addLowerboundCons(
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,
75 TRUE, TRUE, TRUE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
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
getJobId(SCIP * scip,const char * str,int * job,char ** endptr)90 SCIP_RETCODE getJobId(
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
parseDetails(SCIP * scip,SCIP_FILE * file,int * lineno,int ** demands,SCIP_DIGRAPH * precedencegraph,int * durations,int * capacities,int njobs,int nresources)118 SCIP_RETCODE parseDetails(
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
readFile(SCIP * scip,SCIP_FILE * file,const char * filename)254 SCIP_RETCODE readFile(
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
SCIP_DECL_READERCOPY(readerCopySch)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 */
354 SCIP_CALL( SCIPincludeReaderSch(scip) );
355
356 return SCIP_OKAY;
357 }/*lint !e830*/
358
359 /** problem reading method of reader */
360 static
SCIP_DECL_READERREAD(readerReadSch)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 */
SCIPincludeReaderSch(SCIP * scip)400 SCIP_RETCODE SCIPincludeReaderSch(
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 */
411 SCIP_CALL( SCIPincludeReaderBasic(scip, &reader, READER_NAME, READER_DESC, READER_EXTENSION, readerdata) );
412 assert(reader != NULL);
413
414 SCIP_CALL( SCIPsetReaderCopy(scip, reader, readerCopySch) );
415 SCIP_CALL( SCIPsetReaderRead(scip, reader, readerReadSch) );
416
417 /* add reader parameters */
418 SCIP_CALL( SCIPaddBoolParam(scip,
419 "reading/"READER_NAME"/mipmodel", "create MIP model?",
420 NULL, FALSE, FALSE, NULL, NULL) );
421
422 return SCIP_OKAY;
423 }
424