Scippy

SCIP

Solving Constraint Integer Programs

reader_sm.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-2019 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 scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file reader_sm.c
17  * @brief scheduling problem file reader for RCPSP format
18  * @author Michael Bastubbe
19  * @author Stefan Heinz
20  *
21  * This reader is capabale of parsing resource-constrained project scheduling problem (RCPSP) instances. The <a
22  * href="http://129.187.106.231/psplib/datasm.html">PSPlib</a> 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 
33 #include "heur_listscheduling.h"
34 #include "reader_sm.h"
35 
36 #include "scip/cons_cumulative.h"
37 #include "scip/cons_linear.h"
38 #include "scip/cons_varbound.h"
39 
40 #define READER_NAME "smreader"
41 #define READER_DESC "scheduling file reader for sm files (RCPSP format)"
42 #define READER_EXTENSION "sm"
43 
44 
45 /**@name Default parameter values
46  *
47  * @{
48  */
49 
50 #define DEFAULT_FILENAME "-" /**< file name of precedence graph output file (in GML format), or - if no output should be created */
51 
52 /**@} */
53 
54 
55 
56 #define SM_MAX_LINELEN 65536 /**< size of the line buffer for reading or writing */
57 
59  ERROR = 0,
68 };
69 typedef enum reading_states STATE;
70 
71 
72 /** data structure for resources constrained project scheduling problems */
73 struct SCIP_RcpspData
74 {
75  SCIP_DIGRAPH* precedencegraph; /**< precedence graph of the jobs */
76  const char** jobnames; /**< array of job names */
77  const char** resourcenames; /**< array of resource names */
78  int** demands; /**< resource demands matrix (job i needs demands[i][j] units of resource j) */
79  int* durations; /**< array of job durations */
80  int* capacities; /**< array of resource capacities */
81  int njobs; /**< number of jobs */
82  int nresources; /**< number of resources */
83 };
84 typedef struct SCIP_RcpspData SCIP_RCPSPDATA;
85 
86 
87 /*
88  * Local methods
89  */
90 
91 #ifdef SCIP_DEBUG
92 /* print the resource constrained project scheduling data */
93 static
94 void outputRcpspData(
95  SCIP* scip, /**< SCIP data structure */
96  SCIP_RCPSPDATA* rcpspdata /**< pointer to resources constrained project scheduling data */
97  )
98 {
99  int i;
100  int r;
101 
102  /* output jobs */
103  SCIPinfoMessage(scip, NULL, "Number of jobs: %d\n", rcpspdata->njobs);
104  for(i = 0; i < rcpspdata->njobs ; ++i )
105  {
106  SCIPinfoMessage(scip, NULL, "job: %-10s \n", rcpspdata->jobnames[i]);
107  SCIPinfoMessage(scip, NULL, " duration: %3d \n", rcpspdata->durations[i] );
108  SCIPinfoMessage(scip, NULL, " resource profile: ");
109 
110  for( r = 0; r < rcpspdata->nresources; ++r )
111  {
112  SCIPinfoMessage(scip, NULL, " %3d" , rcpspdata->demands[i][r] );
113  }
114 
115  SCIPinfoMessage(scip, NULL, "\n");
116  }
117  SCIPinfoMessage(scip, NULL, "\n");
118 
119  /* output resource capacities */
120  SCIPinfoMessage(scip, NULL, "Resource capacities: ");
121  for( r = 0; r < rcpspdata->nresources; ++r )
122  {
123  if( r == 0 )
124  {
125  SCIPinfoMessage(scip, NULL, " %d " , rcpspdata->capacities[r] );
126  }
127  else
128  {
129  SCIPinfoMessage(scip, NULL, ", %d " , rcpspdata->capacities[r] );
130  }
131  }
132  SCIPinfoMessage(scip, NULL, "\n");
133 
134  /* print precedence graph */
135  SCIPinfoMessage(scip, NULL, "Precedences:\n");
136  SCIPdigraphPrint(rcpspdata->precedencegraph, SCIPgetMessagehdlr(scip), NULL);
137 }
138 #endif
139 
140 /** print error message */
141 static
143  SCIP* scip, /**< SCIP data structure */
144  int lineno, /**< current line number of input file */
145  const char* msg, /**< error message to display */
146  const char* erritem, /**< token where the error occured, or NULL */
147  STATE* state /**< pointer to current reading state */
148  )
149 {
150  assert(msg != NULL);
151  assert(state != NULL);
152 
153  if( erritem != NULL )
154  {
155  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "Line %d: %s <%s>\n", lineno, msg, erritem);
156  }
157  else
158  {
159  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "Line %d: %s\n", lineno, msg);
160  }
161 
162  *state = ERROR;
163 }
164 
165 /** check if we reached a section */
166 static
168  char* linestr, /**< current line */
169  STATE* state /**< pointer to current reading state */
170  )
171 {
172  assert(linestr != NULL);
173  assert(state != NULL);
174 
175  if( strncmp(linestr, "jobs", 4) == 0 )
176  *state = NJOBS;
177  else if( strncmp(linestr, "RESOURCES", 9) == 0 )
178  *state = NRESOURCES;
179  else if( strncmp(linestr, "PRECEDENCE", 4) == 0 )
180  *state = PRECEDENCES;
181  else if( strncmp(linestr, "REQUESTS", 4) == 0 )
182  *state = JOBS;
183  else if( strncmp(linestr, "RESOURCEAVAILABILITIES", 10) == 0 )
184  *state = RESOURCENAMES;
185 }
186 
187 /** parese number of resources */
188 static
190  SCIP* scip, /**< SCIP data structure */
191  int lineno, /**< current line number of input file */
192  char* linestr, /**< current line */
193  STATE* state, /**< pointer to current reading state */
194  SCIP_RCPSPDATA* rcpspdata /**< pointer to resources constrained project scheduling data */
195  )
196 {
197  SCIP_Real nresources;
198  char* endptr;
199  char* number;
200 
201  assert(linestr != NULL);
202  assert(state != NULL);
203 
204  if( strncmp(linestr, "RESOURCES", 4) == 0 )
205  return SCIP_OKAY;
206 
207  /* truncate the line via ':' and ignore the first part */
208  (void)SCIPstrtok(linestr, ":", &endptr);
209  number = SCIPstrtok(NULL, ":", &endptr);
210 
211  if( !SCIPstrToRealValue(number, &nresources, &endptr) )
212  {
213  parseError(scip, lineno, "expexted number of resources", linestr, state);
214  return SCIP_OKAY;
215  }
216 
217  rcpspdata->nresources = (int)(nresources + 0.5);
218 
219  SCIP_CALL( SCIPallocBufferArray(scip, &rcpspdata->capacities, nresources) );
220  SCIP_CALL( SCIPallocBufferArray(scip, &rcpspdata->resourcenames, nresources) );
221 
222  *state = NEXT;
223 
224  return SCIP_OKAY;
225 }
226 
227 /** parse number of jobs */
228 static
230  SCIP* scip, /**< SCIP data structure */
231  int lineno, /**< current line number of input file */
232  char* linestr, /**< current line */
233  STATE* state, /**< pointer to current reading state */
234  SCIP_RCPSPDATA* rcpspdata /**< pointer to resources constrained project scheduling data */
235  )
236 {
237  SCIP_Real njobs;
238  char* endptr;
239  char* number;
240 
241  assert(linestr != NULL);
242  assert(state != NULL);
243 
244  /* truncate the line via ':' and ignore the first part */
245  (void)SCIPstrtok(linestr, ":", &endptr);
246  number = SCIPstrtok(NULL, ":", &endptr);
247 
248  if( !SCIPstrToRealValue(number, &njobs, &endptr) )
249  {
250  parseError(scip, lineno, "expexted number of jobs", linestr, state);
251  return SCIP_OKAY;
252  }
253 
254  rcpspdata->njobs = (int)(njobs + 0.5);
255 
256  SCIP_CALL( SCIPallocBufferArray(scip, &rcpspdata->jobnames, njobs) );
257  SCIP_CALL( SCIPallocBufferArray(scip, &rcpspdata->durations, njobs) );
258  SCIP_CALL( SCIPallocBufferArray(scip, &rcpspdata->demands, njobs) );
259 
260  *state = NEXT;
261 
262  return SCIP_OKAY;
263 }
264 
265 /** pares resource capacities */
266 static
268  SCIP* scip, /**< SCIP data structure */
269  char* linestr, /**< current line */
270  STATE* state, /**< pointer to current reading state */
271  SCIP_RCPSPDATA* rcpspdata /**< pointer to resources constrained project scheduling data */
272  )
273 {
274  char* name;
275  char* endptr;
276  int r;
277 
278  assert(linestr != NULL);
279  assert(state != NULL);
280 
281  if( strncmp(linestr, "RESOURCEAVAILABILITIES", 10) == 0 )
282  return SCIP_OKAY;
283 
284  /* pares resource names */
285  name = SCIPstrtok(linestr, "R", &endptr);
286  r = 0;
287 
288  do
289  {
290  while(isspace(*name))
291  name++;
292 
293  SCIP_CALL( SCIPduplicateBufferArray(scip, &rcpspdata->resourcenames[r], name, strlen(name) + 1) ); /*lint !e866*/
294  r++;
295  }
296  while( (name = SCIPstrtok(NULL, "R", &endptr)) != NULL );
297 
298  *state = RESOURCECAPACITIES;
299 
300  return SCIP_OKAY;
301 }
302 
303 /** parse resource capacities */
304 static
306  SCIP* scip, /**< SCIP data structure */
307  char* linestr, /**< current line */
308  STATE* state, /**< pointer to current reading state */
309  SCIP_RCPSPDATA* rcpspdata /**< pointer to resources constrained project scheduling data */
310  )
311 {
312  SCIP_Real value;
313  int r;
314 
315  assert(linestr != NULL);
316  assert(state != NULL);
317 
318  /* parse resources capacities */
319  for( r = 0; r < rcpspdata->nresources; ++r )
320  {
321  if( SCIPstrToRealValue(linestr, &value, &linestr) )
322  rcpspdata->capacities[r] = (int)(value + 0.5);
323  }
324 
325  *state = END;
326 
327  return SCIP_OKAY;
328 }
329 
330 /** parese job informations */
331 static
333  SCIP* scip, /**< SCIP data structure */
334  char* linestr, /**< current line */
335  STATE* state, /**< pointer to current reading state */
336  SCIP_RCPSPDATA* rcpspdata /**< pointer to resources constrained project scheduling data */
337  )
338 {
339  char jobname[SCIP_MAXSTRLEN];
340  int value;
341  int jobid;
342  int r;
343 
344  assert(linestr != NULL);
345  assert(state != NULL);
346 
347  /* skip lines which are not of interest */
348  if ( (!strncmp(linestr, "REQUESTS", 4) ) || ( !strncmp(linestr, "jobnr", 3) ) || ( !strncmp(linestr, "-", 1) ) )
349  {
350  *state = JOBS;
351  return SCIP_OKAY;
352  }
353 
354  /* parse job id */
355  if( !SCIPstrToIntValue(linestr, &value, &linestr) )
356  return SCIP_READERROR;
357 
358  jobid = value - 1;
359 
360  /* construct job name */
361  (void)SCIPsnprintf(jobname, SCIP_MAXSTRLEN, "%d" , jobid) ;
362 
363  /* copy job name */
364  SCIP_CALL( SCIPduplicateBufferArray(scip, &rcpspdata->jobnames[jobid], jobname, strlen(jobname) + 1) ); /*lint !e866*/
365 
366  /* skip next value */
367  if( !SCIPstrToIntValue(linestr, &value, &linestr) )
368  return SCIP_READERROR;
369 
370  /* parse duration */
371  if( !SCIPstrToIntValue(linestr, &value, &linestr) )
372  return SCIP_READERROR;
373 
374  rcpspdata->durations[jobid] = value;
375 
376  SCIP_CALL( SCIPallocBufferArray(scip, &rcpspdata->demands[jobid], rcpspdata->nresources) ); /*lint !e866*/
377 
378  /* parse demands */
379  for( r = 0; r < rcpspdata->nresources; ++r )
380  {
381  if( !SCIPstrToIntValue(linestr, &value, &linestr) )
382  return SCIP_READERROR;
383 
384  rcpspdata->demands[jobid][r] = value;
385  }
386 
387  /* check if we paresed the last job */
388  if( jobid == rcpspdata->njobs - 1 )
389  *state = NEXT;
390 
391  return SCIP_OKAY;
392 }
393 
394 /** get precedence relationship */
395 static
397  SCIP* scip, /**< SCIP data structure */
398  char* s, /**< current line */
399  STATE* state, /**< pointer to current reading state */
400  SCIP_RCPSPDATA* rcpspdata /**< pointer to resources constrained project scheduling data */
401  )
402 {
403  int nsuccessors;
404  int value;
405  int pred;
406  int p;
407 
408  assert(s != NULL);
409  assert(state != NULL);
410 
411  if( ( !strncmp(s, "PRECEDENCES", 3) ) || ( !strncmp(s, "jobnr", 4) ) )
412  {
413  *state = PRECEDENCES;
414  return SCIP_OKAY;
415  }
416 
417  /* create precedence graph if does not exist yet */
418  if( rcpspdata->precedencegraph == NULL )
419  {
420  SCIP_CALL( SCIPcreateDigraph(scip, &rcpspdata->precedencegraph, rcpspdata->njobs) );
421  }
422 
423  /* parse predecessor */
424  if( !SCIPstrToIntValue(s, &value, &s) )
425  return SCIP_READERROR;
426 
427  pred = value - 1;
428 
429  /* skip integer value */
430  if( !SCIPstrToIntValue(s, &value, &s) )
431  return SCIP_READERROR;
432 
433  /* parse number of successors */
434  if( !SCIPstrToIntValue(s, &nsuccessors, &s) )
435  return SCIP_READERROR;
436 
437  /* parse successors */
438  for( p = 0; p < nsuccessors; ++p )
439  {
440  int succ;
441 
442  if( !SCIPstrToIntValue(s, &value, &s) )
443  return SCIP_READERROR;
444 
445  succ = value - 1;
446 
447  /* add precedence to digraph */
448  SCIP_CALL( SCIPdigraphAddArc(rcpspdata->precedencegraph, pred, succ, (void*)(size_t)INT_MAX) );
449  }
450 
451  if(pred == rcpspdata->njobs-1)
452  *state = NEXT;
453 
454  return SCIP_OKAY;
455 }
456 
457 /** compute trivial upper bound for makespan */
458 static
460  int* durations, /**< array of durations */
461  int njobs, /**< number og jobs */
462  SCIP_DIGRAPH* precedencegraph /**< direct graph to store the precedence conditions */
463  )
464 {
465  int ub;
466  int j;
467 
468  ub = 0;
469 
470  for( j = 0; j < njobs; ++j )
471  {
472  void** distances;
473  int nsuccessors;
474  int duration;
475  int i;
476 
477  nsuccessors = SCIPdigraphGetNSuccessors(precedencegraph, j);
478  distances = SCIPdigraphGetSuccessorsData(precedencegraph, j);
479 
480  duration = durations[j];
481 
482  for( i = 0; i < nsuccessors; ++i )
483  {
484  int distance;
485 
486  distance = (int)(size_t)distances[i];
487 
488  if( distance != INT_MAX )
489  duration = MAX(duration, distance);
490  }
491 
492  ub += duration;
493  }
494 
495  return ub;
496 }
497 
498 /** read file */
499 static
501  SCIP* scip, /**< SCIP data structure */
502  const char* filename, /**< name of input file */
503  SCIP_RCPSPDATA* rcpspdata /**< pointer to resources constrained project scheduling data */
504  )
505 {
506  SCIP_FILE* fp;
507  char buf[SM_MAX_LINELEN];
508  int lineno = 0;
509  char* s;
510  STATE state = NEXT;
511 
512  assert(filename != NULL);
513 
514  if( NULL == (fp = SCIPfopen(filename, "r")) )
515  {
516  perror(filename);
517  return SCIP_READERROR;
518  }
519 
520  /* parse file line by line */
521  while( state != END && state != ERROR && (NULL != SCIPfgets(buf, (int) sizeof(buf), fp)) )
522  {
523  /* count line number */
524  lineno++;
525 
526  if( NULL != (s = strpbrk(buf, "*\r\n")) )
527  *s = '\0';
528  else
529  {
530  parseError(scip, lineno, "line truncated", NULL, &state);
531  break;
532  }
533  s = buf;
534 
535  /* remove white space */
536  while(isspace(*s))
537  s++;
538 
539  /* skip empty lines */
540  if (*s == '\0')
541  continue;
542 
543  if( state == NEXT )
544  {
545  checkForNewSection(s, &state);
546  }
547 
548  SCIPdebugMessage("input line: <%s>\n", s);
549  switch( state )
550  {
551  case ERROR:
552  break;
553 
554  case NEXT:
555  break;
556 
557  case NJOBS:
558  SCIP_CALL( getNJobs(scip, lineno, s, &state, rcpspdata) );
559  break;
560 
561  case JOBS:
562  SCIP_CALL( getJobs(scip, s, &state, rcpspdata) );
563  break;
564 
565 
566  case NRESOURCES:
567  SCIP_CALL( getNResources(scip, lineno, s, &state, rcpspdata) );
568  break;
569 
570  case RESOURCENAMES:
571  SCIP_CALL( getResourcesNames(scip, s, &state, rcpspdata) );
572  break;
573 
574  case RESOURCECAPACITIES:
575  SCIP_CALL( getResourcesCapacities(scip, s, &state, rcpspdata) );
576  break;
577 
578  case PRECEDENCES:
579  SCIP_CALL( getPrecedence(scip, s, &state, rcpspdata) );
580  break;
581 
582  case END:
583  parseError(scip, lineno, "additional characters after END", NULL, &state);
584  break;
585 
586  default:
587  SCIPerrorMessage("invalid reading state\n");
588  SCIPABORT();
589  }
590  }
591  SCIPfclose(fp);
592 
593  if( state != END && state != ERROR )
594  parseError(scip, lineno, "unexpected EOF", NULL, &state);
595 
596  if( state == ERROR )
597  return SCIP_READERROR;
598  else
599  return SCIP_OKAY;
600 }
601 
602 /*
603  * Callback methods of reader
604  */
605 
606 /** copy method for reader plugins (called when SCIP copies plugins) */
607 static
608 SCIP_DECL_READERCOPY(readerCopySm)
609 { /*lint --e{715}*/
610  assert(scip != NULL);
611  assert(reader != NULL);
612  assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0);
613 
614  /* call inclusion method of reader handler */
616 
617  return SCIP_OKAY;
618 }
619 
620 /** problem reading method of reader */
621 static
622 SCIP_DECL_READERREAD(readerReadSm)
623 { /*lint --e{715}*/
624  SCIP_RCPSPDATA rcpspdata;
625  char* predfilename;
626  int j;
627 
628  /* initialize resources constrained project scheduling data */
629  rcpspdata.precedencegraph = NULL;
630  rcpspdata.jobnames = NULL;
631  rcpspdata.durations = NULL;
632  rcpspdata.demands = NULL;
633  rcpspdata.capacities = NULL;
634  rcpspdata.njobs = 0;
635  rcpspdata.nresources = 0;
636 
637  /* read file */
638  SCIP_CALL( readFile(scip, filename, &rcpspdata) );
639 
640  /* output rcpspdata to check it */
641  SCIPdebug( outputRcpspData(scip, &rcpspdata) );
642 
643  SCIP_CALL( SCIPgetStringParam(scip, "reading/"READER_NAME"/filename", &predfilename) );
644 
645  if( strncmp(predfilename, "-", 1) != 0 )
646  {
647  FILE* file;
648 
649  file = fopen(predfilename, "w");
650 
651  if( file == NULL )
652  {
653  SCIPerrorMessage("cannot create file <%s> for writing\n", predfilename);
654  SCIPprintSysError(predfilename);
655  return SCIP_FILECREATEERROR;
656  }
657 
658  SCIPdigraphPrintGml(rcpspdata.precedencegraph, file);
659 
660  fclose(file);
661  }
662 
663  /* create problem */
664  SCIP_CALL( SCIPcreateSchedulingProblem(scip, filename, rcpspdata.jobnames, rcpspdata.resourcenames, rcpspdata.demands,
665  rcpspdata.precedencegraph, rcpspdata.durations, rcpspdata.capacities, rcpspdata.njobs, rcpspdata.nresources, TRUE) );
666 
667  (*result) = SCIP_SUCCESS;
668 
669  /* free buffer arrays */
670  if( rcpspdata.njobs > 0 )
671  {
672  for( j = 0; j < rcpspdata.njobs; ++j )
673  {
674  SCIPfreeBufferArray(scip, &(rcpspdata.jobnames[j]));
675  SCIPfreeBufferArray(scip, &(rcpspdata.demands[j]));
676  }
677 
678  SCIPfreeBufferArray(scip, &rcpspdata.jobnames);
679  SCIPfreeBufferArray(scip, &rcpspdata.durations);
680  SCIPfreeBufferArray(scip, &rcpspdata.demands);
681  }
682 
683  if( rcpspdata.nresources > 0 )
684  {
685  int r;
686 
687  for( r = 0; r < rcpspdata.nresources; ++r )
688  SCIPfreeBufferArray(scip, &rcpspdata.resourcenames[r]);
689 
690  SCIPfreeBufferArray(scip, &rcpspdata.resourcenames);
691  SCIPfreeBufferArray(scip, &rcpspdata.capacities);
692  }
693 
694  if( rcpspdata.precedencegraph != NULL )
695  {
696  SCIPdigraphFree(&rcpspdata.precedencegraph);
697  }
698 
699  return SCIP_OKAY;
700 }
701 
702 /*
703  * reader specific interface methods
704  */
705 
706 /** includes the sch file reader in SCIP */
708  SCIP* scip /**< SCIP data structure */
709  )
710 {
711  SCIP_READERDATA* readerdata;
712  SCIP_READER* reader;
713 
714  /* create sch reader data */
715  readerdata = NULL;
716 
717  /* include sch reader */
719  assert(reader != NULL);
720 
721  SCIP_CALL( SCIPsetReaderCopy(scip, reader, readerCopySm) );
722  SCIP_CALL( SCIPsetReaderRead(scip, reader, readerReadSm) );
723 
724  /* add reader parameters */
726  "reading/"READER_NAME"/mipmodel", "create MIP model?",
727  NULL, FALSE, FALSE, NULL, NULL) );
728 
730  "reading/"READER_NAME"/filename",
731  "file name of precedence graph output file (in GML format), or - if no output should be created",
733 
734  return SCIP_OKAY;
735 }
736 
737 /** creates a cumulative scheduling problem */
739  SCIP* scip, /**< SCIP data structure */
740  const char* problemname, /**< problem name */
741  const char** jobnames, /**< job names, or NULL */
742  const char** resourcenames, /**< resource names, or NULL */
743  int** demands, /**< demand matrix resource job demand */
744  SCIP_DIGRAPH* precedencegraph, /**< direct graph to store the precedence conditions */
745  int* durations, /**< array to store the processing for each job */
746  int* capacities, /**< array to store the different capacities */
747  int njobs, /**< number of jobs to be parsed */
748  int nresources, /**< number of capacities to be parsed */
749  SCIP_Bool initialize /**< initialize list scheduling heuristic */
750  )
751 {
752  SCIP_VAR** jobs;
753  SCIP_VAR** vars;
754  SCIP_VAR* var;
755 
756  SCIP_CONS* cons;
757 
758  char name[SCIP_MAXSTRLEN];
759 
760  int* consdurations;
761  int* consdemands;
762 
763  int nvars;
764  int ubmakespan;
765  int i;
766  int j;
767  int r;
768 
769  assert( scip != NULL );
770  assert( njobs >= 0 );
771 
772  SCIPdebugMessage( "start method SCIPcreateSchedulingSMProblem\n");
773 
774  /* create SCIP data structure */
775  SCIP_CALL( SCIPcreateProb(scip, problemname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
776 
777  /* compute a feasible upper bound on the makespan */
778  ubmakespan = computeUbmakespan(durations, njobs, precedencegraph);
779 
780  /* allocate buffer for jobs and precedence constraints */
781  SCIP_CALL( SCIPallocBufferArray(scip, &jobs, njobs) );
782 
783  /* create an activity constraint for each activity */
784  for( j = 0; j < njobs - 1; ++j ) /* but not for last job which is the makespan (-1) */
785  {
786  /* construct variable name */
787  if( jobnames != NULL )
788  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "start_%s", jobnames[j]);
789  else
790  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "start_%d", j);
791 
792  /* create integer starting variable */
793  SCIP_CALL( SCIPcreateVar(scip, &var, name, 0.0, (SCIP_Real)ubmakespan, 0.0, SCIP_VARTYPE_INTEGER,
794  TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
795 
796  SCIP_CALL( SCIPaddVar(scip, var) );
797  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, var) );
798  jobs[j] = var;
799  SCIP_CALL( SCIPreleaseVar(scip, &var) );
800  }
801 
802  /* create makespan variable */
803  SCIP_CALL( SCIPcreateVar(scip, &var, "makespan", 0.0, (SCIP_Real)ubmakespan, 1.0, SCIP_VARTYPE_INTEGER,
804  TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
805 
806  SCIP_CALL( SCIPaddVar(scip, var) );
807  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, var) );
808 
809  jobs[njobs-1] = var;
810  SCIP_CALL( SCIPreleaseVar(scip, &var) );
811 
812  /* precedence constraints */
813  for( j = 0; j < njobs - 1; ++j )
814  {
815  SCIP_VAR* predvar;
816  int nsuccessors;
817 
818  nsuccessors = SCIPdigraphGetNSuccessors(precedencegraph, j);
819 
820  predvar = jobs[j];
821  assert(predvar != NULL);
822 
823  if( nsuccessors > 0 )
824  {
825  int* successors;
826  void** distances;
827 
828  successors = SCIPdigraphGetSuccessors(precedencegraph, j);
829  distances = SCIPdigraphGetSuccessorsData(precedencegraph, j);
830 
831  for( i = 0; i < nsuccessors; ++i )
832  {
833  SCIP_VAR* succvar;
834  int distance;
835 
836  succvar = jobs[successors[i]];
837  assert(succvar != NULL);
838 
839  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "precedences_(%d,%d)", j, successors[i]);
840 
841  distance = (int)(size_t)distances[i];
842 
843  if( distance == INT_MAX )
844  distance = durations[j];
845 
846  SCIP_CALL( SCIPcreateConsVarbound(scip, &cons, name, predvar, succvar, -1.0,
847  -SCIPinfinity(scip), (SCIP_Real) -distance,
849  SCIP_CALL( SCIPaddCons(scip, cons) );
850  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
851  }
852  }
853  else
854  {
855  /* add precedence constraints for those jobs without successor */
856  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "precedences_(%d,%d)", j, njobs);
857 
858  SCIP_CALL( SCIPcreateConsVarbound(scip, &cons, name, predvar, jobs[njobs-1], -1.0,
859  -SCIPinfinity(scip), (SCIP_Real) -durations[j],
861  SCIP_CALL( SCIPaddCons(scip, cons) );
862  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
863  }
864  }
865 
866  SCIP_CALL( SCIPallocBufferArray(scip, &vars, njobs) );
867  SCIP_CALL( SCIPallocBufferArray(scip, &consdemands, njobs) );
868  SCIP_CALL( SCIPallocBufferArray(scip, &consdurations, njobs) );
869 
870  /* create resource constraints */
871  for( r = 0; r < nresources; ++r )
872  {
873  nvars = 0;
874  for( j = 0; j < njobs; ++j ) /* also makespan constraint! */
875  {
876  if( demands[j][r] > 0 )
877  {
878  vars[nvars] = jobs[j];
879  consdemands[nvars] = demands[j][r];
880  consdurations[nvars] = durations[j];
881  nvars++;
882  }
883  }
884 
885  if( nvars > 0 )
886  {
887  /* construct constraint name */
888  if( resourcenames != NULL )
889  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "R%s", resourcenames[r]);
890  else
891  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "R%d", r);
892 
893  SCIP_CALL( SCIPcreateConsCumulative(scip, &cons, name,
894  nvars, vars, consdurations, consdemands, capacities[r],
896  SCIP_CALL( SCIPaddCons(scip, cons) );
897  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
898  }
899  }
900 
901  /* initialize the problem specific heuristic */
902  if( initialize )
903  {
904  SCIP_CALL( SCIPinitializeHeurListScheduling(scip, precedencegraph, jobs,
905  durations, demands, capacities, njobs, nresources) );
906  }
907 
908  /* free buffer array */
909  SCIPfreeBufferArray(scip, &consdurations);
910  SCIPfreeBufferArray(scip, &consdemands);
911  SCIPfreeBufferArray(scip, &vars);
912  SCIPfreeBufferArray(scip, &jobs);
913 
914  return SCIP_OKAY;
915 }
static void checkForNewSection(char *linestr, STATE *state)
Definition: reader_sm.c:167
void ** SCIPdigraphGetSuccessorsData(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7565
SCIP_RETCODE SCIPgetStringParam(SCIP *scip, const char *name, char **value)
Definition: scip_param.c:417
Definition: reader_sm.c:62
#define NULL
Definition: def.h:246
static SCIP_RETCODE getJobs(SCIP *scip, char *linestr, STATE *state, SCIP_RCPSPDATA *rcpspdata)
Definition: reader_sm.c:332
constraint handler for cumulative constraints
Constraint handler for variable bound constraints .
#define SCIP_MAXSTRLEN
Definition: def.h:267
SCIP_RETCODE SCIPcreateProb(SCIP *scip, const char *name, SCIP_DECL_PROBDELORIG((*probdelorig)), SCIP_DECL_PROBTRANS((*probtrans)), SCIP_DECL_PROBDELTRANS((*probdeltrans)), SCIP_DECL_PROBINITSOL((*probinitsol)), SCIP_DECL_PROBEXITSOL((*probexitsol)), SCIP_DECL_PROBCOPY((*probcopy)), SCIP_PROBDATA *probdata)
Definition: scip_prob.c:162
static SCIP_RETCODE getNJobs(SCIP *scip, int lineno, char *linestr, STATE *state, SCIP_RCPSPDATA *rcpspdata)
Definition: reader_sm.c:229
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7547
const char * SCIPreaderGetName(SCIP_READER *reader)
Definition: reader.c:547
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1251
#define FALSE
Definition: def.h:72
#define READER_DESC
Definition: reader_sm.c:41
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10253
#define TRUE
Definition: def.h:71
#define SCIPdebug(x)
Definition: pub_message.h:74
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPaddStringParam(SCIP *scip, const char *name, const char *desc, char **valueptr, SCIP_Bool isadvanced, const char *defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:266
SCIP_Bool SCIPstrToIntValue(const char *str, int *value, char **endptr)
Definition: misc.c:10323
#define SCIPdebugMessage
Definition: pub_message.h:77
SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
Definition: scip_message.c:171
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:138
static int computeUbmakespan(int *durations, int njobs, SCIP_DIGRAPH *precedencegraph)
Definition: reader_sm.c:459
static SCIP_RETCODE getPrecedence(SCIP *scip, char *s, STATE *state, SCIP_RCPSPDATA *rcpspdata)
Definition: reader_sm.c:396
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:279
SCIP_RETCODE SCIPcreateDigraph(SCIP *scip, SCIP_DIGRAPH **digraph, int nnodes)
SCIP_RETCODE SCIPcreateConsVarbound(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *var, SCIP_VAR *vbdvar, SCIP_Real vbdcoef, SCIP_Real lhs, SCIP_Real rhs, 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_FILE * SCIPfopen(const char *path, const char *mode)
Definition: fileio.c:140
static void parseError(SCIP *scip, int lineno, const char *msg, const char *erritem, STATE *state)
Definition: reader_sm.c:142
static SCIP_RETCODE getNResources(SCIP *scip, int lineno, char *linestr, STATE *state, SCIP_RCPSPDATA *rcpspdata)
Definition: reader_sm.c:189
static SCIP_DECL_READERREAD(readerReadSm)
Definition: reader_sm.c:622
static SCIP_RETCODE getResourcesCapacities(SCIP *scip, char *linestr, STATE *state, SCIP_RCPSPDATA *rcpspdata)
Definition: reader_sm.c:305
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2822
struct SCIP_File SCIP_FILE
Definition: pub_fileio.h:34
char * SCIPfgets(char *s, int size, SCIP_FILE *stream)
Definition: fileio.c:187
SCIP_RETCODE SCIPincludeReaderSm(SCIP *scip)
Definition: reader_sm.c:707
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8524
void SCIPdigraphPrint(SCIP_DIGRAPH *digraph, SCIP_MESSAGEHDLR *messagehdlr, FILE *file)
Definition: misc.c:8119
#define SCIP_CALL(x)
Definition: def.h:358
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:296
SCIP_RETCODE SCIPdigraphAddArc(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
Definition: misc.c:7396
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
struct SCIP_ReaderData SCIP_READERDATA
Definition: type_reader.h:37
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7532
#define SCIP_Bool
Definition: def.h:69
SCIP_RETCODE SCIPincludeReaderBasic(SCIP *scip, SCIP_READER **readerptr, const char *name, const char *desc, const char *extension, SCIP_READERDATA *readerdata)
Definition: scip_reader.c:180
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
void SCIPprintSysError(const char *message)
Definition: misc.c:10162
static SCIP_RETCODE readFile(SCIP *scip, const char *filename, SCIP_RCPSPDATA *rcpspdata)
Definition: reader_sm.c:500
static SCIP_DECL_READERCOPY(readerCopySm)
Definition: reader_sm.c:608
struct SCIP_RcpspData SCIP_RCPSPDATA
Definition: reader_sm.c:84
SCIP_Bool SCIPstrToRealValue(const char *str, SCIP_Real *value, char **endptr)
Definition: misc.c:10354
Definition: reader_sm.c:60
enum reading_states STATE
Definition: reader_sm.c:69
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:104
Definition: reader_sm.c:67
#define SM_MAX_LINELEN
Definition: reader_sm.c:56
Constraint handler for linear constraints in their most general form, .
static long * number
SCIP_RETCODE SCIPsetReaderCopy(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERCOPY((*readercopy)))
Definition: scip_reader.c:218
scheduling problem file reader for RCPSP format
SCIP_Real * r
Definition: circlepacking.c:50
#define MAX(x, y)
Definition: def.h:215
#define READER_EXTENSION
Definition: reader_sm.c:42
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1724
reading_states
Definition: reader_sm.c:58
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1187
#define DEFAULT_FILENAME
Definition: reader_sm.c:50
SCIP_RETCODE SCIPinitializeHeurListScheduling(SCIP *scip, SCIP_DIGRAPH *precedencegraph, SCIP_VAR **vars, int *durations, int **resourcedemands, int *capacities, int njobs, int nresources)
#define SCIP_Real
Definition: def.h:157
SCIP_RETCODE SCIPsetReaderRead(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERREAD((*readerread)))
Definition: scip_reader.c:266
SCIP_RETCODE SCIPcreateConsCumulative(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, 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 READER_NAME
Definition: reader_sm.c:40
static SCIP_RETCODE getResourcesNames(SCIP *scip, char *linestr, STATE *state, SCIP_RCPSPDATA *rcpspdata)
Definition: reader_sm.c:267
int SCIPfclose(SCIP_FILE *fp)
Definition: fileio.c:219
void SCIPdigraphFree(SCIP_DIGRAPH **digraph)
Definition: misc.c:7306
#define SCIPABORT()
Definition: def.h:330
char * SCIPstrtok(char *s, const char *delim, char **ptrptr)
Definition: misc.c:10211
void SCIPdigraphPrintGml(SCIP_DIGRAPH *digraph, FILE *file)
Definition: misc.c:8154
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:129
scheduling specific primal heuristic which is based on bidirectional serial generation scheme...