Scippy

SCIP

Solving Constraint Integer Programs

reader_sm.c File Reference

Detailed Description

scheduling problem file reader for RCPSP format

Author
Michael Bastubbe
Stefan Heinz

This reader is capabale of parsing resource-constrained project scheduling problem (RCPSP) instances. The PSPlib provides several instances set.

Definition in file reader_sm.c.

#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"

Go to the source code of this file.

Macros

#define READER_NAME   "smreader"
 
#define READER_DESC   "scheduling file reader for sm files (RCPSP format)"
 
#define READER_EXTENSION   "sm"
 
#define SM_MAX_LINELEN   65536
 
Default parameter values
#define DEFAULT_FILENAME   "-"
 

Typedefs

typedef enum reading_states STATE
 
typedef struct SCIP_RcpspData SCIP_RCPSPDATA
 

Enumerations

enum  reading_states {
  ERROR = 0,
  NEXT,
  NJOBS,
  JOBS,
  NRESOURCES,
  RESOURCENAMES,
  RESOURCECAPACITIES,
  PRECEDENCES,
  END
}
 

Functions

static void parseError (SCIP *scip, int lineno, const char *msg, const char *erritem, STATE *state)
 
static void checkForNewSection (char *linestr, STATE *state)
 
static SCIP_RETCODE getNResources (SCIP *scip, int lineno, char *linestr, STATE *state, SCIP_RCPSPDATA *rcpspdata)
 
static SCIP_RETCODE getNJobs (SCIP *scip, int lineno, char *linestr, STATE *state, SCIP_RCPSPDATA *rcpspdata)
 
static SCIP_RETCODE getResourcesNames (SCIP *scip, char *linestr, STATE *state, SCIP_RCPSPDATA *rcpspdata)
 
static SCIP_RETCODE getResourcesCapacities (SCIP *scip, char *linestr, STATE *state, SCIP_RCPSPDATA *rcpspdata)
 
static SCIP_RETCODE getJobs (SCIP *scip, char *linestr, STATE *state, SCIP_RCPSPDATA *rcpspdata)
 
static SCIP_RETCODE getPrecedence (SCIP *scip, char *s, STATE *state, SCIP_RCPSPDATA *rcpspdata)
 
static int computeUbmakespan (int *durations, int njobs, SCIP_DIGRAPH *precedencegraph)
 
static SCIP_RETCODE readFile (SCIP *scip, const char *filename, SCIP_RCPSPDATA *rcpspdata)
 
static SCIP_DECL_READERCOPY (readerCopySm)
 
static SCIP_DECL_READERREAD (readerReadSm)
 
SCIP_RETCODE SCIPincludeReaderSm (SCIP *scip)
 
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)
 

Macro Definition Documentation

◆ READER_NAME

#define READER_NAME   "smreader"

Definition at line 49 of file reader_sm.c.

Referenced by SCIP_DECL_READERCOPY(), SCIP_DECL_READERREAD(), and SCIPincludeReaderSm().

◆ READER_DESC

#define READER_DESC   "scheduling file reader for sm files (RCPSP format)"

Definition at line 50 of file reader_sm.c.

Referenced by SCIPincludeReaderSm().

◆ READER_EXTENSION

#define READER_EXTENSION   "sm"

Definition at line 51 of file reader_sm.c.

Referenced by SCIPincludeReaderSm().

◆ DEFAULT_FILENAME

#define DEFAULT_FILENAME   "-"

file name of precedence graph output file (in GML format), or - if no output should be created

Definition at line 59 of file reader_sm.c.

Referenced by SCIPincludeReaderSm().

◆ SM_MAX_LINELEN

#define SM_MAX_LINELEN   65536

size of the line buffer for reading or writing

Definition at line 65 of file reader_sm.c.

Referenced by readFile().

Typedef Documentation

◆ STATE

typedef enum reading_states STATE

Definition at line 78 of file reader_sm.c.

◆ SCIP_RCPSPDATA

typedef struct SCIP_RcpspData SCIP_RCPSPDATA

Definition at line 93 of file reader_sm.c.

Enumeration Type Documentation

◆ reading_states

Enumerator
ERROR 
NEXT 
NJOBS 
JOBS 
NRESOURCES 
RESOURCENAMES 
RESOURCECAPACITIES 
PRECEDENCES 
END 

Definition at line 67 of file reader_sm.c.

Function Documentation

◆ parseError()

static void parseError ( SCIP scip,
int  lineno,
const char *  msg,
const char *  erritem,
STATE state 
)
static

print error message

Parameters
scipSCIP data structure
linenocurrent line number of input file
msgerror message to display
erritemtoken where the error occured, or NULL
statepointer to current reading state

Definition at line 151 of file reader_sm.c.

References ERROR, NULL, SCIP_VERBLEVEL_MINIMAL, and SCIPverbMessage().

Referenced by getNJobs(), getNResources(), and readFile().

◆ checkForNewSection()

static void checkForNewSection ( char *  linestr,
STATE state 
)
static

check if we reached a section

Parameters
linestrcurrent line
statepointer to current reading state

Definition at line 176 of file reader_sm.c.

References JOBS, NJOBS, NRESOURCES, NULL, PRECEDENCES, and RESOURCENAMES.

Referenced by readFile().

◆ getNResources()

static SCIP_RETCODE getNResources ( SCIP scip,
int  lineno,
char *  linestr,
STATE state,
SCIP_RCPSPDATA rcpspdata 
)
static

parese number of resources

Parameters
scipSCIP data structure
linenocurrent line number of input file
linestrcurrent line
statepointer to current reading state
rcpspdatapointer to resources constrained project scheduling data

Definition at line 198 of file reader_sm.c.

References NEXT, NULL, number, parseError(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPstrtok(), and SCIPstrToRealValue().

Referenced by readFile().

◆ getNJobs()

static SCIP_RETCODE getNJobs ( SCIP scip,
int  lineno,
char *  linestr,
STATE state,
SCIP_RCPSPDATA rcpspdata 
)
static

parse number of jobs

Parameters
scipSCIP data structure
linenocurrent line number of input file
linestrcurrent line
statepointer to current reading state
rcpspdatapointer to resources constrained project scheduling data

Definition at line 238 of file reader_sm.c.

References NEXT, NULL, number, parseError(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPstrtok(), and SCIPstrToRealValue().

Referenced by readFile().

◆ getResourcesNames()

static SCIP_RETCODE getResourcesNames ( SCIP scip,
char *  linestr,
STATE state,
SCIP_RCPSPDATA rcpspdata 
)
static

pares resource capacities

Parameters
scipSCIP data structure
linestrcurrent line
statepointer to current reading state
rcpspdatapointer to resources constrained project scheduling data

Definition at line 276 of file reader_sm.c.

References NULL, r, RESOURCECAPACITIES, SCIP_CALL, SCIP_OKAY, SCIPduplicateBufferArray, and SCIPstrtok().

Referenced by readFile().

◆ getResourcesCapacities()

static SCIP_RETCODE getResourcesCapacities ( SCIP scip,
char *  linestr,
STATE state,
SCIP_RCPSPDATA rcpspdata 
)
static

parse resource capacities

Parameters
scipSCIP data structure
linestrcurrent line
statepointer to current reading state
rcpspdatapointer to resources constrained project scheduling data

Definition at line 314 of file reader_sm.c.

References END, NULL, r, SCIP_OKAY, SCIP_Real, and SCIPstrToRealValue().

Referenced by readFile().

◆ getJobs()

static SCIP_RETCODE getJobs ( SCIP scip,
char *  linestr,
STATE state,
SCIP_RCPSPDATA rcpspdata 
)
static

parese job informations

Parameters
scipSCIP data structure
linestrcurrent line
statepointer to current reading state
rcpspdatapointer to resources constrained project scheduling data

Definition at line 341 of file reader_sm.c.

References JOBS, NEXT, NULL, r, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_READERROR, SCIPallocBufferArray, SCIPduplicateBufferArray, SCIPsnprintf(), and SCIPstrToIntValue().

Referenced by readFile().

◆ getPrecedence()

static SCIP_RETCODE getPrecedence ( SCIP scip,
char *  s,
STATE state,
SCIP_RCPSPDATA rcpspdata 
)
static

get precedence relationship

Parameters
scipSCIP data structure
scurrent line
statepointer to current reading state
rcpspdatapointer to resources constrained project scheduling data

Definition at line 405 of file reader_sm.c.

References NEXT, NULL, PRECEDENCES, SCIP_CALL, SCIP_OKAY, SCIP_READERROR, SCIPcreateDigraph(), SCIPdigraphAddArc(), and SCIPstrToIntValue().

Referenced by readFile().

◆ computeUbmakespan()

static int computeUbmakespan ( int *  durations,
int  njobs,
SCIP_DIGRAPH precedencegraph 
)
static

compute trivial upper bound for makespan

Parameters
durationsarray of durations
njobsnumber og jobs
precedencegraphdirect graph to store the precedence conditions

Definition at line 468 of file reader_sm.c.

References MAX, SCIPdigraphGetNSuccessors(), and SCIPdigraphGetSuccessorsData().

Referenced by SCIPcreateSchedulingProblem().

◆ readFile()

static SCIP_RETCODE readFile ( SCIP scip,
const char *  filename,
SCIP_RCPSPDATA rcpspdata 
)
static

read file

Parameters
scipSCIP data structure
filenamename of input file
rcpspdatapointer to resources constrained project scheduling data

Definition at line 509 of file reader_sm.c.

References checkForNewSection(), END, ERROR, getJobs(), getNJobs(), getNResources(), getPrecedence(), getResourcesCapacities(), getResourcesNames(), JOBS, NEXT, NJOBS, NRESOURCES, NULL, parseError(), PRECEDENCES, RESOURCECAPACITIES, RESOURCENAMES, SCIP_CALL, SCIP_OKAY, SCIP_READERROR, SCIPABORT, SCIPdebugMessage, SCIPerrorMessage, SCIPfclose(), SCIPfgets(), SCIPfopen(), and SM_MAX_LINELEN.

Referenced by SCIP_DECL_READERREAD().

◆ SCIP_DECL_READERCOPY()

static SCIP_DECL_READERCOPY ( readerCopySm  )
static

copy method for reader plugins (called when SCIP copies plugins)

Definition at line 617 of file reader_sm.c.

References NULL, READER_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludeReaderSm(), and SCIPreaderGetName().

◆ SCIP_DECL_READERREAD()

static SCIP_DECL_READERREAD ( readerReadSm  )
static

◆ SCIPincludeReaderSm()

SCIP_RETCODE SCIPincludeReaderSm ( SCIP scip)

includes the sch file reader in SCIP

Parameters
scipSCIP data structure

Definition at line 716 of file reader_sm.c.

References DEFAULT_FILENAME, FALSE, NULL, READER_DESC, READER_EXTENSION, READER_NAME, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddStringParam(), SCIPincludeReaderBasic(), SCIPsetReaderCopy(), and SCIPsetReaderRead().

Referenced by runShell(), and SCIP_DECL_READERCOPY().

◆ SCIPcreateSchedulingProblem()

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 
)

creates a cumulative scheduling problem

Parameters
scipSCIP data structure
problemnameproblem name
jobnamesjob names, or NULL
resourcenamesresource names, or NULL
demandsdemand matrix resource job demand
precedencegraphdirect graph to store the precedence conditions
durationsarray to store the processing for each job
capacitiesarray to store the different capacities
njobsnumber of jobs to be parsed
nresourcesnumber of capacities to be parsed
initializeinitialize list scheduling heuristic

Definition at line 747 of file reader_sm.c.

References computeUbmakespan(), FALSE, NULL, r, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_INTEGER, SCIPaddCons(), SCIPaddVar(), SCIPallocBufferArray, SCIPcreateConsCumulative(), SCIPcreateConsVarbound(), SCIPcreateProb(), SCIPcreateVar(), SCIPdebugMessage, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPfreeBufferArray, SCIPinfinity(), SCIPinitializeHeurListScheduling(), SCIPmarkDoNotMultaggrVar(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsnprintf(), and TRUE.

Referenced by readFile(), and SCIP_DECL_READERREAD().