35#if defined(_WIN32) || defined(_WIN64)
49#define READER_NAME "cminreader"
50#define READER_DESC "file reader for cmin file format"
51#define READER_EXTENSION "cmin"
53#define DEFAULT_FILENAME "-"
54#define DEFAULT_DUALREDUCTION TRUE
55#define DEFAULT_MIP FALSE
56#define DEFAULT_INITIAL TRUE
57#define DEFAULT_CIP TRUE
58#define DEFAULT_RELAXATION 3
117 pch = strstr (cmininput->
linebuf,
"\n");
121 if (cmininput->
linebuf[0] !=
'\0')
154 if( buf[cmininput->
linepos] ==
'\0' )
171 while( isdigit(buf[cmininput->
linepos]) )
181 cmininput->
token[tokenlen] =
'\0';
198 const char* probname;
214 if( *solufile ==
'-')
242 if( strncmp(
token, probname, strlen(
token)+1) == 0 )
244 SCIPdebugMessage(
"found problem <%s> in solution file <%s>\n", probname, solufile);
246 if( strncmp(status,
"=opt=", 5) == 0 )
251 (*objval) = atof(
token);
272void displayInputData(
287 for( j = 0; j < njobs; ++j )
291 for( m = 0; m < nmachines; ++m )
316 for ( j = 0; j < njobs; ++j )
318 starttimes[j] = releasedates[j];
321 endtimes[j] = deadlinedates[j];
349 assert(starttime < endtime);
352 for( v = 0; v < njobs; ++v )
355 if( deadlinedates[v] <= endtime && releasedates[v] >= starttime)
379 for( j = 0; j < nrows; ++j )
381 rowtightness[keptrows] = rowtightness[j];
382 startidxs[keptrows] = startidxs[j];
385 if( rowtightness[j] > tightness )
430 for( j = 0; j < njobs; ++j )
438 starttime = -INT_MAX;
441 for( j = 0; j < njobs; ++j )
445 assert(starttime <= starttimes[j]);
448 if( starttime == starttimes[j])
451 starttime = starttimes[j];
455 for(
i = 0;
i < njobs; ++
i )
461 assert(endtime <= endtimes[
i]);
464 if( endtime == endtimes[
i] )
467 endtime = endtimes[
i];
470 if( endtime <= starttime )
473 maxenergy =
computeMaxEnergy(njobs, durations, demands, releasedates, deadlinedates, starttime, endtime);
475 energy = (endtime - starttime) * capacity;
476 tightness = maxenergy - energy;
479 if( tightness > besttightness )
481 besttightness = tightness;
486 rowtightness[
i][nrows[
i]] = tightness;
487 startidxs[
i][nrows[
i]] = j;
495 for( j = njobs-1; j >= 0; --j )
497 for(
i = 0;
i < nrows[j]; ++
i )
504 starttime = starttimes[startidxs[j][
i]];
505 endtime = endtimes[j];
507 energy = (endtime - starttime) * capacity;
510 starttime, endtime, energy, rowtightness[j][
i]);
515 for( v = 0; v < njobs; ++v)
520 duration = durations[v];
521 overlap =
MIN(endtime - starttime, duration);
523 overlap =
MIN3(overlap, releasedates[v] + duration - starttime, endtime - deadlinedates[v] + duration);
526 if( relaxation == 2 && releasedates[v] >= starttime && deadlinedates[v] <= endtime )
528 assert(duration == overlap);
531 else if( relaxation == 3 && overlap > 0 )
533 assert(overlap <= duration);
547 for( j = njobs-1; j >= 0; --j )
594 for( j = 0; j < njobs; ++j )
596 maxtime =
MAX(maxtime, deadlinedates[j]);
604 for(
i = 0;
i < nmachines; ++
i )
608 for( j = 0; j < njobs; ++j )
619 if( releasedates[j] > deadlinedates[j] - durations[
i][j] || demands[
i][j] > capacities[
i] )
634 for( j = 0; j < njobs; ++j )
640 for(
i = 0;
i < nmachines; ++
i )
650 for(
i = 0;
i < nmachines; ++
i )
654 for( t = 0; t < maxtime; ++t )
669 for( j = 0; j < njobs; ++j )
673 est = releasedates[j];
675 for(
i = 0;
i < nmachines; ++
i )
679 lst = deadlinedates[j] - durations[
i][j];
687 for( t = est; t <= lst; ++t )
702 for(
h = t ;
h <
MIN(t + durations[
i][j], maxtime); ++
h )
716 for(
i = nmachines - 1;
i >= 0; --
i )
722 if( relaxation == 1 )
725 for(
i = 0;
i < nmachines; ++
i )
735 for( j = 0; j < njobs; ++j )
737 if( demands[
i][j] > 0 )
739 est =
MIN(est, releasedates[j]);
740 lct =
MAX(lct, deadlinedates[j]);
747 capacity = capacities[
i] * (lct - est);
751 for( j = 0; j < njobs; ++j )
753 if( demands[
i][j] > 0 )
764 else if( relaxation >= 2 )
767 for(
i = 0;
i < nmachines; ++
i )
773 for(
i = nmachines-1;
i >= 0; --
i )
803 int** localdurations;
814 for( j = 0; j < njobs; ++j )
816 maxtime =
MAX(maxtime, deadlinedates[j]);
829 for(
i = 0;
i < nmachines; ++
i )
833 for( t = 0; t < maxtime; ++t )
853 for( j = 0; j < njobs; ++j )
858 est = releasedates[j];
866 for(
i = 0;
i < nmachines; ++
i )
872 lst = deadlinedates[j] - durations[
i][j];
892 binvars[
i][idx] =
var;
921 localdemands[
i][idx] = demands[
i][j];
922 localdurations[
i][idx] = durations[
i][j];
924 for( t = est; t <= lst; ++t )
942 for(
h = t ;
h <
MIN(t + durations[
i][j], maxtime); ++
h )
964 for(
i = 0;
i < nmachines; ++
i )
977 for(
i = nmachines - 1;
i >= 0; --
i )
1032 for( j = 0; j < njobs; ++j )
1047 for(
i = 0;
i < nmachines; ++
i )
1059 for( j = 0; j < njobs; ++j )
1062 if(releasedates[j] + durations[
i][j] > deadlinedates[j] || demands[
i][j] > capacities[
i] )
1081 if( !dualreduction )
1090 demands[
i][
nvars] = demands[
i][j];
1091 durations[
i][
nvars] = durations[
i][j];
1103 if( relaxation == 0 )
1133 for(
i = 0;
i < nmachines; ++
i )
1151 const char* filename
1174 njobs = atoi(cmininput->
token);
1183 nmachines = atoi(cmininput->
token);
1191 for(
i = 0;
i < nmachines; ++
i )
1201 for(
i = 0;
i < nmachines && !cmininput->
haserror; ++
i )
1203 for( j = 0; j < njobs; ++j )
1213 durations[
i][j] = atoi(cmininput->
token);
1223 demands[
i][j] = atoi(cmininput->
token);
1233 costs[
i][j] = atoi(cmininput->
token);
1235 SCIPdebugMessage(
"job %2d: duration %d, demand %d, cost %d\n", j, durations[
i][j], demands[
i][j], costs[
i][j]);
1240 for(
i = 0;
i < nmachines && !cmininput->
haserror; ++
i)
1249 capacities[
i] = atoi(cmininput->
token);
1255 for( j = 0; j < njobs && !cmininput->
haserror; ++j )
1265 releasedates[j] = atoi(cmininput->
token);
1273 deadlinedates[j] = atoi(cmininput->
token);
1275 SCIPdebugMessage(
"job %2d: [%d,%d]\n", j, releasedates[j], deadlinedates[j]);
1285 SCIPdebug( displayInputData(
scip, durations, demands, costs, capacities, releasedates, deadlinedates, njobs, nmachines) );
1318 for(
i = nmachines - 1;
i >= 0; --
i )
1359 cmininput.
token[0] =
'\0';
1392 "reading/"READER_NAME"/filename",
"name of the file including best known solutions",
1396 "reading/"READER_NAME"/dualreduction",
"add locks to avoid dual reductions?",
1400 "reading/"READER_NAME"/mip",
"create a MIP formulation?",
1404 "reading/"READER_NAME"/initial",
"should model constraints be in initial LP?",
1408 "reading/"READER_NAME"/cip",
"create a CIP formulation?",
1412 "reading/"READER_NAME"/relaxation",
"which relaxation should be added to the maseter (0: none; 1: single; 2: edge-finding; 3: energetic-reasoning",
Constraint handler for knapsack constraints of the form , x binary and .
Constraint handler for linear constraints in their most general form, .
SCIP_RETCODE SCIPcreateConsOptcumulative(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_VAR **binvars, 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)
constraint handler for cumulative constraints with optional activities
Constraint handler for the set partitioning / packing / covering constraints .
#define SCIP_LONGINT_FORMAT
SCIP_FILE * SCIPfopen(const char *path, const char *mode)
int SCIPfclose(SCIP_FILE *fp)
char * SCIPfgets(char *s, int size, SCIP_FILE *stream)
SCIP_RETCODE SCIPcreateConsBasicSetpart(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars)
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPaddCoefKnapsack(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Longint weight)
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
SCIP_RETCODE SCIPcreateConsBasicKnapsack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity)
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
SCIP_RETCODE SCIPcreateConsKnapsack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint 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)
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, 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_RETCODE SCIPcreateConsSetpart(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, 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)
void SCIPsplitFilename(char *filename, char **path, char **name, char **extension, char **compression)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
const char * SCIPgetProbName(SCIP *scip)
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
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)
SCIP_RETCODE SCIPgetStringParam(SCIP *scip, const char *name, char **value)
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)
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPduplicateBufferArray(scip, ptr, source, num)
SCIP_RETCODE SCIPincludeReaderBasic(SCIP *scip, SCIP_READER **readerptr, const char *name, const char *desc, const char *extension, SCIP_READERDATA *readerdata)
SCIP_RETCODE SCIPsetReaderRead(SCIP *scip, SCIP_READER *reader,)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
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)
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
char * SCIPstrtok(char *s, const char *delim, char **ptrptr)
assert(minobj< SCIPgetCutoffbound(scip))
SCIP_RETCODE SCIPinitHeurOptcumulative(SCIP *scip, int nmachines, int njobs, int *machines, SCIP_VAR ***binvars, SCIP_VAR ***vars, int **durations, int **demands, int *capacities)
heuristic for cumulative scheduling with optional activities
#define BMSclearMemoryArray(ptr, num)
struct SCIP_File SCIP_FILE
static int removeRedundantRows(SCIP_Longint *rowtightness, int *startidxs, int nrows, SCIP_Longint tightness)
SCIP_RETCODE SCIPincludeReaderCmin(SCIP *scip)
static SCIP_RETCODE createIntervalRelaxation(SCIP *scip, int relaxation, int resource, SCIP_VAR **vars, int *durations, int *demands, int capacity, int *releasedates, int *deadlinedates, int njobs)
static SCIP_Longint computeMaxEnergy(int njobs, int *durations, int *demands, int *releasedates, int *deadlinedates, int starttime, int endtime)
static SCIP_RETCODE readFile(SCIP *scip, CMININPUT *cmininput, const char *filename)
#define DEFAULT_RELAXATION
static SCIP_Bool getNextLine(CMININPUT *cmininput)
static SCIP_Bool getNextToken(CMININPUT *cmininput)
#define DEFAULT_DUALREDUCTION
static SCIP_RETCODE createMipCpFormulation(SCIP *scip, int **durations, int **demands, int **costs, int *capacities, int *releasedates, int *deadlinedates, int njobs, int nmachines)
static void createSortedEventpoints(SCIP *scip, int *releasedates, int *deadlinedates, int *starttimes, int *endtimes, int *startindices, int *endindices, int njobs)
static SCIP_Bool isDelimChar(char c)
struct CminInput CMININPUT
static void syntaxError(SCIP *scip, CMININPUT *cmininput, const char *msg)
static SCIP_RETCODE findBestObjectiveValue(SCIP *scip, SCIP_Real *objval)
static SCIP_RETCODE createMipFormulation(SCIP *scip, int **durations, int **demands, int **costs, int *capacities, int *releasedates, int *deadlinedates, int njobs, int nmachines)
static SCIP_RETCODE createCipFormulation(SCIP *scip, int **durations, int **demands, int **costs, int *capacities, int *releasedates, int *deadlinedates, int njobs, int nmachines)
static const char delimchars[]
struct SCIP_Cons SCIP_CONS
struct SCIP_Reader SCIP_READER
#define SCIP_DECL_READERREAD(x)
enum SCIP_Retcode SCIP_RETCODE