reader_sm.c

Go to the documentation of this file.

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/*                                                                           */
/*                  This file is part of the program and library             */
/*         SCIP --- Solving Constraint Integer Programs                      */
/*                                                                           */
/*  Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB)                      */
/*                                                                           */
/*  Licensed under the Apache License, Version 2.0 (the "License");          */
/*  you may not use this file except in compliance with the License.         */
/*  You may obtain a copy of the License at                                  */
/*                                                                           */
/*      http://www.apache.org/licenses/LICENSE-2.0                           */
/*                                                                           */
/*  Unless required by applicable law or agreed to in writing, software      */
/*  distributed under the License is distributed on an "AS IS" BASIS,        */
/*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
/*  See the License for the specific language governing permissions and      */
/*  limitations under the License.                                           */
/*                                                                           */
/*  You should have received a copy of the Apache-2.0 license                */
/*  along with SCIP; see the file LICENSE. If not visit scipopt.org.         */
/*                                                                           */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 
/**@file   reader_sm.c
 * @brief  scheduling problem file reader for RCPSP format
 * @author Michael Bastubbe
 * @author Stefan Heinz
 *
 * This reader is capabale of parsing resource-constrained project scheduling problem (RCPSP) instances. The <a
 * href="http://129.187.106.231/psplib/datasm.html">PSPlib</a> provides several instances set.
 *
 */
 
/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
 
#include <assert.h>
#include <string.h>
#include <ctype.h>
 
 
#include "heur_listscheduling.h"
#include "reader_sm.h"
 
#include "scip/cons_cumulative.h"
#include "scip/cons_linear.h"
#include "scip/cons_varbound.h"
 
#define READER_NAME             "smreader"
#define READER_DESC             "scheduling file reader for sm files (RCPSP format)"
#define READER_EXTENSION        "sm"
 
 
/**@name Default parameter values
 *
 * @{
 */
 
#define DEFAULT_FILENAME            "-" /**< file name of precedence graph output file (in GML format), or - if no output should be created */
 
/**@} */
 
 
 
#define SM_MAX_LINELEN      65536     /**< size of the line buffer for reading or writing */
 
enum reading_states {
   ERROR = 0,
   NEXT,
   NJOBS,
   JOBS,
   NRESOURCES,
   RESOURCENAMES,
   RESOURCECAPACITIES,
   PRECEDENCES,
   END
};
typedef enum reading_states STATE;
 
 
/** data structure for resources constrained project scheduling problems */
struct SCIP_RcpspData
{
   SCIP_DIGRAPH*        precedencegraph;     /**< precedence graph of the jobs */
   const char**         jobnames;            /**< array of job names */
   const char**         resourcenames;       /**< array of resource names */
   int**                demands;             /**< resource demands matrix (job i needs demands[i][j] units of resource j) */
   int*                 durations;           /**< array of job durations */
   int*                 capacities;          /**< array of resource capacities */
   int                  njobs;               /**< number of jobs */
   int                  nresources;          /**< number of resources */
};
typedef struct SCIP_RcpspData SCIP_RCPSPDATA;
 
 
/*
 * Local methods
 */
 
#ifdef SCIP_DEBUG
/* print the resource constrained project scheduling data */
static
void outputRcpspData(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_RCPSPDATA*       rcpspdata           /**< pointer to resources constrained project scheduling data */
   )
{
   int i;
   int r;
 
   /* output jobs */
   SCIPinfoMessage(scip, NULL, "Number of jobs: %d\n", rcpspdata->njobs);
   for(i = 0; i < rcpspdata->njobs ; ++i )
   {
      SCIPinfoMessage(scip, NULL, "job: %-10s \n", rcpspdata->jobnames[i]);
      SCIPinfoMessage(scip, NULL, "  duration: %3d \n", rcpspdata->durations[i] );
      SCIPinfoMessage(scip, NULL, "  resource profile: ");
 
      for( r = 0; r < rcpspdata->nresources; ++r )
      {
         SCIPinfoMessage(scip, NULL, " %3d" , rcpspdata->demands[i][r] );
      }
 
      SCIPinfoMessage(scip, NULL, "\n");
   }
   SCIPinfoMessage(scip, NULL, "\n");
 
   /* output resource capacities */
   SCIPinfoMessage(scip, NULL, "Resource capacities: ");
   for( r = 0; r < rcpspdata->nresources; ++r )
   {
      if( r == 0 )
      {
         SCIPinfoMessage(scip, NULL, " %d " , rcpspdata->capacities[r] );
      }
      else
      {
         SCIPinfoMessage(scip, NULL, ", %d " , rcpspdata->capacities[r] );
      }
   }
   SCIPinfoMessage(scip, NULL, "\n");
 
   /* print precedence graph */
   SCIPinfoMessage(scip, NULL, "Precedences:\n");
   SCIPdigraphPrint(rcpspdata->precedencegraph, SCIPgetMessagehdlr(scip), NULL);
}
#endif
 
/** print error message */
static
void parseError(
   SCIP*                 scip,               /**< SCIP data structure */
   int                   lineno,             /**< current line number of input file */
   const char*           msg,                /**< error message to display */
   const char*           erritem,            /**< token where the error occured, or NULL */
   STATE*                state               /**< pointer to current reading state */
   )
{
   assert(msg != NULL);
   assert(state != NULL);
 
   if( erritem != NULL )
   {
      SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "Line %d: %s <%s>\n", lineno, msg, erritem);
   }
   else
   {
      SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "Line %d: %s\n", lineno, msg);
   }
 
   *state = ERROR;
}
 
/** check if we reached a section */
static
void checkForNewSection(
   char*                 linestr,            /**< current line */
   STATE*                state               /**< pointer to current reading state */
   )
{
   assert(linestr != NULL);
   assert(state != NULL);
 
   if( strncmp(linestr, "jobs", 4) == 0 )
      *state = NJOBS;
   else if( strncmp(linestr, "RESOURCES", 9) == 0 )
      *state = NRESOURCES;
   else if( strncmp(linestr, "PRECEDENCE", 4) == 0 )
      *state = PRECEDENCES;
   else if( strncmp(linestr, "REQUESTS", 4) == 0 )
      *state = JOBS;
   else if( strncmp(linestr, "RESOURCEAVAILABILITIES", 10) == 0 )
      *state = RESOURCENAMES;
}
 
/** parese number of resources */
static
SCIP_RETCODE getNResources(
   SCIP*                 scip,               /**< SCIP data structure */
   int                   lineno,             /**< current line number of input file */
   char*                 linestr,            /**< current line */
   STATE*                state,              /**< pointer to current reading state */
   SCIP_RCPSPDATA*       rcpspdata           /**< pointer to resources constrained project scheduling data */
   )
{
   SCIP_Real nresources;
   char* endptr;
   char* number;
 
   assert(linestr != NULL);
   assert(state != NULL);
 
   if( strncmp(linestr, "RESOURCES", 4) == 0 )
      return SCIP_OKAY;
 
   /* truncate the line via ':' and ignore the first part */
   (void)SCIPstrtok(linestr, ":", &endptr);
   number = SCIPstrtok(NULL, ":", &endptr);
 
   if( !SCIPstrToRealValue(number, &nresources, &endptr) )
   {
      parseError(scip, lineno, "expexted number of resources", linestr, state);
      return SCIP_OKAY;
   }
 
   rcpspdata->nresources = (int)(nresources + 0.5);
 
   SCIP_CALL( SCIPallocBufferArray(scip, &rcpspdata->capacities, nresources) );
   SCIP_CALL( SCIPallocBufferArray(scip, &rcpspdata->resourcenames, nresources) );
 
   *state = NEXT;
 
   return SCIP_OKAY;
}
 
/** parse number of jobs */
static
SCIP_RETCODE getNJobs(
   SCIP*                 scip,               /**< SCIP data structure */
   int                   lineno,             /**< current line number of input file */
   char*                 linestr,            /**< current line */
   STATE*                state,              /**< pointer to current reading state */
   SCIP_RCPSPDATA*       rcpspdata           /**< pointer to resources constrained project scheduling data */
   )
{
   SCIP_Real njobs;
   char* endptr;
   char* number;
 
   assert(linestr != NULL);
   assert(state != NULL);
 
   /* truncate the line via ':' and ignore the first part */
   (void)SCIPstrtok(linestr, ":", &endptr);
   number = SCIPstrtok(NULL, ":", &endptr);
 
   if( !SCIPstrToRealValue(number, &njobs, &endptr) )
   {
      parseError(scip, lineno, "expexted number of jobs", linestr, state);
      return SCIP_OKAY;
   }
 
   rcpspdata->njobs = (int)(njobs + 0.5);
 
   SCIP_CALL( SCIPallocBufferArray(scip, &rcpspdata->jobnames, njobs) );
   SCIP_CALL( SCIPallocBufferArray(scip, &rcpspdata->durations, njobs) );
   SCIP_CALL( SCIPallocBufferArray(scip, &rcpspdata->demands, njobs) );
 
   *state = NEXT;
 
   return SCIP_OKAY;
}
 
/** pares resource capacities */
static
SCIP_RETCODE getResourcesNames(
   SCIP*                 scip,               /**< SCIP data structure */
   char*                 linestr,            /**< current line */
   STATE*                state,              /**< pointer to current reading state */
   SCIP_RCPSPDATA*       rcpspdata           /**< pointer to resources constrained project scheduling data */
   )
{
   char* name;
   char* endptr;
   int r;
 
   assert(linestr != NULL);
   assert(state != NULL);
 
   if( strncmp(linestr, "RESOURCEAVAILABILITIES", 10) == 0 )
      return SCIP_OKAY;
 
   /* pares resource names */
   name = SCIPstrtok(linestr, "R", &endptr);
   r = 0;
 
   do
   {
      while(isspace(*name))
         name++;
 
      SCIP_CALL( SCIPduplicateBufferArray(scip, &rcpspdata->resourcenames[r], name, strlen(name) + 1) ); /*lint !e866*/
      r++;
   }
   while( (name = SCIPstrtok(NULL, "R", &endptr)) != NULL );
 
   *state = RESOURCECAPACITIES;
 
   return SCIP_OKAY;
}
 
/** parse resource capacities */
static
SCIP_RETCODE getResourcesCapacities(
   SCIP*                 scip,               /**< SCIP data structure */
   char*                 linestr,            /**< current line */
   STATE*                state,              /**< pointer to current reading state */
   SCIP_RCPSPDATA*       rcpspdata           /**< pointer to resources constrained project scheduling data */
   )
{
   SCIP_Real value;
   int r;
 
   assert(linestr != NULL);
   assert(state != NULL);
 
   /* parse resources capacities */
   for( r = 0; r < rcpspdata->nresources; ++r )
   {
      if( SCIPstrToRealValue(linestr, &value, &linestr) )
         rcpspdata->capacities[r] = (int)(value + 0.5);
   }
 
   *state = END;
 
   return SCIP_OKAY;
}
 
/** parese job informations */
static
SCIP_RETCODE getJobs(
   SCIP*                 scip,               /**< SCIP data structure */
   char*                 linestr,            /**< current line */
   STATE*                state,              /**< pointer to current reading state */
   SCIP_RCPSPDATA*       rcpspdata           /**< pointer to resources constrained project scheduling data */
   )
{
   char jobname[SCIP_MAXSTRLEN];
   int value;
   int jobid;
   int r;
 
   assert(linestr != NULL);
   assert(state != NULL);
 
   /* skip lines which are not of interest */
   if ( (!strncmp(linestr, "REQUESTS", 4) ) || ( !strncmp(linestr, "jobnr", 3) ) || ( !strncmp(linestr, "-", 1) )  )
   {
      *state = JOBS;
      return SCIP_OKAY;
   }
 
   /* parse job id */
   if( !SCIPstrToIntValue(linestr, &value, &linestr) )
      return SCIP_READERROR;
 
   jobid = value - 1;
 
   /* construct job name */
   (void)SCIPsnprintf(jobname, SCIP_MAXSTRLEN, "%d" , jobid) ;
 
   /* copy job name */
   SCIP_CALL( SCIPduplicateBufferArray(scip, &rcpspdata->jobnames[jobid], jobname, strlen(jobname) + 1) ); /*lint !e866*/
 
   /* skip next value */
   if( !SCIPstrToIntValue(linestr, &value, &linestr) )
      return SCIP_READERROR;
 
   /* parse duration */
   if( !SCIPstrToIntValue(linestr, &value, &linestr) )
      return SCIP_READERROR;
 
   rcpspdata->durations[jobid] = value;
 
   SCIP_CALL( SCIPallocBufferArray(scip, &rcpspdata->demands[jobid], rcpspdata->nresources) ); /*lint !e866*/
 
   /* parse demands */
   for( r = 0; r < rcpspdata->nresources; ++r )
   {
      if( !SCIPstrToIntValue(linestr, &value, &linestr) )
         return SCIP_READERROR;
 
      rcpspdata->demands[jobid][r] = value;
   }
 
   /* check if we paresed the last job */
   if( jobid == rcpspdata->njobs - 1 )
      *state = NEXT;
 
   return SCIP_OKAY;
}
 
/** get precedence relationship */
static
SCIP_RETCODE getPrecedence(
   SCIP*                 scip,               /**< SCIP data structure */
   char*                 s,                  /**< current line */
   STATE*                state,              /**< pointer to current reading state */
   SCIP_RCPSPDATA*       rcpspdata           /**< pointer to resources constrained project scheduling data */
   )
{
   int nsuccessors;
   int value;
   int pred;
   int p;
 
   assert(s != NULL);
   assert(state != NULL);
 
   if( ( !strncmp(s, "PRECEDENCES", 3) ) ||    ( !strncmp(s, "jobnr", 4) ) )
   {
      *state = PRECEDENCES;
      return SCIP_OKAY;
   }
 
   /* create precedence graph if does not exist yet */
   if( rcpspdata->precedencegraph == NULL )
   {
      SCIP_CALL( SCIPcreateDigraph(scip, &rcpspdata->precedencegraph, rcpspdata->njobs) );
   }
 
   /* parse predecessor */
   if( !SCIPstrToIntValue(s, &value, &s) )
      return SCIP_READERROR;
 
   pred = value - 1;
 
   /* skip integer value */
   if( !SCIPstrToIntValue(s, &value, &s) )
      return SCIP_READERROR;
 
   /* parse number of successors */
   if( !SCIPstrToIntValue(s, &nsuccessors, &s) )
      return SCIP_READERROR;
 
   /* parse successors */
   for( p = 0; p < nsuccessors; ++p )
   {
      int succ;
 
      if( !SCIPstrToIntValue(s, &value, &s) )
         return SCIP_READERROR;
 
      succ = value - 1;
 
      /* add precedence to digraph */
      SCIP_CALL( SCIPdigraphAddArc(rcpspdata->precedencegraph, pred, succ, (void*)(size_t)INT_MAX) );
   }
 
   if(pred == rcpspdata->njobs-1)
      *state = NEXT;
 
   return SCIP_OKAY;
}
 
/** compute trivial upper bound for makespan */
static
int computeUbmakespan(
   int*                  durations,          /**< array of durations */
   int                   njobs,              /**< number og jobs */
   SCIP_DIGRAPH*         precedencegraph     /**< direct graph to store the precedence conditions */
   )
{
   int ub;
   int j;
 
   ub = 0;
 
   for( j = 0; j < njobs; ++j )
   {
      void** distances;
      int nsuccessors;
      int duration;
      int i;
 
      nsuccessors = SCIPdigraphGetNSuccessors(precedencegraph, j);
      distances = SCIPdigraphGetSuccessorsData(precedencegraph, j);
 
      duration = durations[j];
 
      for( i = 0; i < nsuccessors; ++i )
      {
         int distance;
 
         distance = (int)(size_t)distances[i];
 
         if( distance != INT_MAX )
            duration = MAX(duration, distance);
      }
 
      ub += duration;
   }
 
   return ub;
}
 
/** read file */
static
SCIP_RETCODE readFile(
   SCIP*                 scip,               /**< SCIP data structure */
   const char*           filename,           /**< name of input file */
   SCIP_RCPSPDATA*       rcpspdata           /**< pointer to resources constrained project scheduling data */
   )
{
   SCIP_FILE* fp;
   char       buf[SM_MAX_LINELEN];
   int        lineno = 0;
   char* s;
   STATE state = NEXT;
 
   assert(filename != NULL);
 
   if( NULL == (fp = SCIPfopen(filename, "r")) )
   {
      perror(filename);
      return SCIP_READERROR;
   }
 
   /* parse file line by line */
   while( state != END && state != ERROR && (NULL != SCIPfgets(buf, (int) sizeof(buf), fp)) )
   {
      /* count line number */
      lineno++;
 
      if( NULL != (s = strpbrk(buf, "*\r\n")) )
         *s = '\0';
      else
      {
         parseError(scip, lineno, "line truncated", NULL, &state);
         break;
      }
      s = buf;
 
      /* remove white space */
      while(isspace(*s))
         s++;
 
      /* skip empty lines */
      if (*s == '\0')
         continue;
 
      if( state == NEXT )
      {
         checkForNewSection(s, &state);
      }
 
      SCIPdebugMessage("input line: <%s>\n", s);
      switch( state )
      {
      case ERROR:
         break;
 
      case NEXT:
         break;
 
      case NJOBS:
         SCIP_CALL( getNJobs(scip, lineno, s, &state, rcpspdata) );
         break;
 
      case JOBS:
         SCIP_CALL( getJobs(scip, s, &state, rcpspdata) );
         break;
 
 
      case NRESOURCES:
         SCIP_CALL( getNResources(scip, lineno, s, &state, rcpspdata) );
         break;
 
      case RESOURCENAMES:
         SCIP_CALL( getResourcesNames(scip, s, &state, rcpspdata) );
         break;
 
      case RESOURCECAPACITIES:
         SCIP_CALL( getResourcesCapacities(scip, s, &state, rcpspdata) );
         break;
 
      case PRECEDENCES:
         SCIP_CALL( getPrecedence(scip, s, &state, rcpspdata) );
         break;
 
      case END:
         parseError(scip, lineno, "additional characters after END", NULL, &state);
         break;
 
      default:
         SCIPerrorMessage("invalid reading state\n");
         SCIPABORT();
      }
   }
   SCIPfclose(fp);
 
   if( state != END && state != ERROR )
      parseError(scip, lineno, "unexpected EOF", NULL, &state);
 
   if( state == ERROR )
      return SCIP_READERROR;
   else
      return SCIP_OKAY;
}
 
/*
 * Callback methods of reader
 */
 
/** copy method for reader plugins (called when SCIP copies plugins) */
static
SCIP_DECL_READERCOPY(readerCopySm)
{  /*lint --e{715}*/
   assert(scip != NULL);
   assert(reader != NULL);
   assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0);
 
   /* call inclusion method of reader handler */
   SCIP_CALL( SCIPincludeReaderSm(scip) );
 
   return SCIP_OKAY;
}
 
/** problem reading method of reader */
static
SCIP_DECL_READERREAD(readerReadSm)
{  /*lint --e{715}*/
   SCIP_RCPSPDATA rcpspdata;
   char* predfilename;
   int j;
 
   /* initialize resources constrained project scheduling data */
   rcpspdata.precedencegraph = NULL;
   rcpspdata.jobnames = NULL;
   rcpspdata.durations = NULL;
   rcpspdata.demands = NULL;
   rcpspdata.capacities = NULL;
   rcpspdata.njobs = 0;
   rcpspdata.nresources = 0;
 
   /* read file */
   SCIP_CALL( readFile(scip, filename, &rcpspdata) );
 
   /* output rcpspdata to check it */
   SCIPdebug( outputRcpspData(scip, &rcpspdata) );
 
   SCIP_CALL( SCIPgetStringParam(scip, "reading/"READER_NAME"/filename", &predfilename) );
 
   if( strncmp(predfilename, "-", 1) != 0 )
   {
      FILE* file;
 
      file = fopen(predfilename, "w");
 
      if( file == NULL )
      {
         SCIPerrorMessage("cannot create file <%s> for writing\n", predfilename);
         SCIPprintSysError(predfilename);
         return SCIP_FILECREATEERROR;
      }
 
      SCIPdigraphPrintGml(rcpspdata.precedencegraph, file);
 
      fclose(file);
   }
 
   /* create problem */
   SCIP_CALL( SCIPcreateSchedulingProblem(scip, filename, rcpspdata.jobnames, rcpspdata.resourcenames, rcpspdata.demands,
         rcpspdata.precedencegraph, rcpspdata.durations, rcpspdata.capacities, rcpspdata.njobs, rcpspdata.nresources, TRUE) );
 
   (*result) = SCIP_SUCCESS;
 
   /* free buffer arrays */
   if( rcpspdata.njobs > 0 )
   {
      for( j = 0; j < rcpspdata.njobs; ++j )
      {
         SCIPfreeBufferArray(scip, &(rcpspdata.jobnames[j]));
         SCIPfreeBufferArray(scip, &(rcpspdata.demands[j]));
      }
 
      SCIPfreeBufferArray(scip, &rcpspdata.jobnames);
      SCIPfreeBufferArray(scip, &rcpspdata.durations);
      SCIPfreeBufferArray(scip, &rcpspdata.demands);
   }
 
   if( rcpspdata.nresources > 0 )
   {
      int r;
 
      for( r = 0; r < rcpspdata.nresources; ++r )
         SCIPfreeBufferArray(scip, &rcpspdata.resourcenames[r]);
 
      SCIPfreeBufferArray(scip, &rcpspdata.resourcenames);
      SCIPfreeBufferArray(scip, &rcpspdata.capacities);
   }
 
   if( rcpspdata.precedencegraph != NULL )
   {
      SCIPdigraphFree(&rcpspdata.precedencegraph);
   }
 
   return SCIP_OKAY;
}
 
/*
 * reader specific interface methods
 */
 
/** includes the sch file reader in SCIP */
SCIP_RETCODE SCIPincludeReaderSm(
   SCIP*                 scip                /**< SCIP data structure */
   )
{
   SCIP_READERDATA* readerdata;
   SCIP_READER* reader;
 
   /* create sch reader data */
   readerdata = NULL;
 
   /* include sch reader */
   SCIP_CALL( SCIPincludeReaderBasic(scip, &reader, READER_NAME, READER_DESC, READER_EXTENSION, readerdata) );
   assert(reader != NULL);
 
   SCIP_CALL( SCIPsetReaderCopy(scip, reader, readerCopySm) );
   SCIP_CALL( SCIPsetReaderRead(scip, reader, readerReadSm) );
 
   /* add reader parameters */
   SCIP_CALL( SCIPaddBoolParam(scip,
         "reading/"READER_NAME"/mipmodel", "create MIP model?",
         NULL, FALSE, FALSE, NULL, NULL) );
 
   SCIP_CALL( SCIPaddStringParam(scip,
         "reading/"READER_NAME"/filename",
         "file name of precedence graph output file (in GML format), or - if no output should be created",
         NULL, FALSE, DEFAULT_FILENAME, NULL, NULL) );
 
   return SCIP_OKAY;
}
 
/** creates a cumulative scheduling problem */
SCIP_RETCODE SCIPcreateSchedulingProblem(
   SCIP*                 scip,               /**< SCIP data structure */
   const char*           problemname,        /**< problem name */
   const char**          jobnames,           /**< job names, or NULL */
   const char**          resourcenames,      /**< resource names, or NULL */
   int**                 demands,            /**< demand matrix resource job demand */
   SCIP_DIGRAPH*         precedencegraph,    /**< direct graph to store the precedence conditions */
   int*                  durations,          /**< array to store the processing for each job */
   int*                  capacities,         /**< array to store the different capacities */
   int                   njobs,              /**< number of jobs to be parsed */
   int                   nresources,         /**< number of capacities to be parsed */
   SCIP_Bool             initialize          /**< initialize list scheduling heuristic */
   )
{
   SCIP_VAR** jobs;
   SCIP_VAR** vars;
   SCIP_VAR* var;
 
   SCIP_CONS* cons;
 
   char name[SCIP_MAXSTRLEN];
 
   int* consdurations;
   int* consdemands;
 
   int nvars;
   int ubmakespan;
   int i;
   int j;
   int r;
 
   assert( scip != NULL );
   assert( njobs >= 0 );
 
   SCIPdebugMessage( "start method SCIPcreateSchedulingSMProblem\n");
 
   /* create SCIP data structure */
   SCIP_CALL( SCIPcreateProb(scip, problemname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
 
   /* compute a feasible upper bound on the makespan */
   ubmakespan = computeUbmakespan(durations, njobs, precedencegraph);
 
   /* allocate buffer for jobs and precedence constraints */
   SCIP_CALL( SCIPallocBufferArray(scip, &jobs, njobs) );
 
   /* create an activity constraint for each activity */
   for( j = 0; j < njobs - 1; ++j ) /* but not for last job which is the makespan (-1) */
   {
      /* construct variable name */
      if( jobnames != NULL )
         (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "start_%s", jobnames[j]);
      else
         (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "start_%d", j);
 
      /* create integer starting variable */
      SCIP_CALL( SCIPcreateVar(scip, &var, name, 0.0, (SCIP_Real)ubmakespan, 0.0, SCIP_VARTYPE_INTEGER,
            TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
 
      SCIP_CALL( SCIPaddVar(scip, var) );
      SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, var) );
      jobs[j] = var;
      SCIP_CALL( SCIPreleaseVar(scip, &var) );
   }
 
   /* create makespan variable */
   SCIP_CALL( SCIPcreateVar(scip, &var, "makespan", 0.0, (SCIP_Real)ubmakespan, 1.0, SCIP_VARTYPE_INTEGER,
         TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
 
   SCIP_CALL( SCIPaddVar(scip, var) );
   SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, var) );
 
   jobs[njobs-1] = var;
   SCIP_CALL( SCIPreleaseVar(scip, &var) );
 
   /* precedence constraints */
   for( j = 0; j < njobs - 1; ++j )
   {
      SCIP_VAR* predvar;
      int nsuccessors;
 
      nsuccessors = SCIPdigraphGetNSuccessors(precedencegraph, j);
 
      predvar = jobs[j];
      assert(predvar != NULL);
 
      if( nsuccessors > 0 )
      {
         int* successors;
         void** distances;
 
         successors = SCIPdigraphGetSuccessors(precedencegraph, j);
         distances = SCIPdigraphGetSuccessorsData(precedencegraph, j);
 
         for( i = 0; i < nsuccessors; ++i )
         {
            SCIP_VAR* succvar;
            int distance;
 
            succvar = jobs[successors[i]];
            assert(succvar != NULL);
 
            (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "precedences_(%d,%d)", j, successors[i]);
 
            distance = (int)(size_t)distances[i];
 
            if( distance == INT_MAX )
               distance = durations[j];
 
            SCIP_CALL( SCIPcreateConsVarbound(scip, &cons, name, predvar, succvar, -1.0,
                  -SCIPinfinity(scip), (SCIP_Real) -distance,
                  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
            SCIP_CALL( SCIPaddCons(scip, cons) );
            SCIP_CALL( SCIPreleaseCons(scip, &cons) );
         }
      }
      else
      {
         /* add precedence constraints for those jobs without successor */
         (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "precedences_(%d,%d)", j, njobs);
 
         SCIP_CALL( SCIPcreateConsVarbound(scip, &cons, name, predvar, jobs[njobs-1], -1.0,
               -SCIPinfinity(scip), (SCIP_Real) -durations[j],
               TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
         SCIP_CALL( SCIPaddCons(scip, cons) );
         SCIP_CALL( SCIPreleaseCons(scip, &cons) );
      }
   }
 
   SCIP_CALL( SCIPallocBufferArray(scip, &vars, njobs) );
   SCIP_CALL( SCIPallocBufferArray(scip, &consdemands, njobs) );
   SCIP_CALL( SCIPallocBufferArray(scip, &consdurations, njobs) );
 
   /* create resource constraints */
   for( r = 0; r < nresources; ++r )
   {
      nvars = 0;
      for( j = 0; j < njobs; ++j ) /* also makespan constraint! */
      {
         if( demands[j][r] > 0 )
         {
            vars[nvars] = jobs[j];
            consdemands[nvars] = demands[j][r];
            consdurations[nvars] = durations[j];
            nvars++;
         }
      }
 
      if( nvars > 0 )
      {
         /* construct constraint name */
         if( resourcenames != NULL )
            (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "R%s", resourcenames[r]);
         else
            (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "R%d", r);
 
         SCIP_CALL( SCIPcreateConsCumulative(scip, &cons, name,
               nvars, vars, consdurations, consdemands, capacities[r],
               TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
         SCIP_CALL( SCIPaddCons(scip, cons) );
         SCIP_CALL( SCIPreleaseCons(scip, &cons) );
      }
   }
 
   /* initialize the problem specific heuristic */
   if( initialize )
   {
      SCIP_CALL( SCIPinitializeHeurListScheduling(scip, precedencegraph, jobs,
            durations, demands, capacities, njobs, nresources) );
   }
 
   /* free buffer array */
   SCIPfreeBufferArray(scip, &consdurations);
   SCIPfreeBufferArray(scip, &consdemands);
   SCIPfreeBufferArray(scip, &vars);
   SCIPfreeBufferArray(scip, &jobs);
 
   return SCIP_OKAY;
}