Scippy

SCIP

Solving Constraint Integer Programs

reader_cmin.c File Reference

Detailed Description

cmin file reader

Author
Stefan Heinz

Definition in file reader_cmin.c.

#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <strings.h>
#include <ctype.h>
#include "scip/cons_linear.h"
#include "scip/cons_setppc.h"
#include "scip/cons_knapsack.h"
#include "cons_optcumulative.h"
#include "heur_optcumulative.h"
#include "reader_cmin.h"

Go to the source code of this file.

Data Structures

struct  CminInput
 

Macros

#define READER_NAME   "cminreader"
 
#define READER_DESC   "file reader for cmin file format"
 
#define READER_EXTENSION   "cmin"
 
#define DEFAULT_FILENAME   "-"
 
#define DEFAULT_DUALREDUCTION   TRUE
 
#define DEFAULT_MIP   FALSE
 
#define DEFAULT_INITIAL   TRUE
 
#define DEFAULT_CIP   TRUE
 
#define DEFAULT_RELAXATION   3
 

Typedefs

typedef struct CminInput CMININPUT
 

Functions

static void syntaxError (SCIP *scip, CMININPUT *cmininput, const char *msg)
 
static SCIP_Bool getNextLine (CMININPUT *cmininput)
 
static SCIP_Bool isDelimChar (char c)
 
static SCIP_Bool getNextToken (CMININPUT *cmininput)
 
static SCIP_RETCODE findBestObjectiveValue (SCIP *scip, SCIP_Real *objval)
 
static void createSortedEventpoints (SCIP *scip, int *releasedates, int *deadlinedates, int *starttimes, int *endtimes, int *startindices, int *endindices, int njobs)
 
static SCIP_Longint computeMaxEnergy (int njobs, int *durations, int *demands, int *releasedates, int *deadlinedates, int starttime, int endtime)
 
static int removeRedundantRows (SCIP_Longint *rowtightness, int *startidxs, int nrows, SCIP_Longint tightness)
 
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_RETCODE createMipFormulation (SCIP *scip, int **durations, int **demands, int **costs, int *capacities, int *releasedates, int *deadlinedates, int njobs, int nmachines)
 
static SCIP_RETCODE createMipCpFormulation (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 SCIP_RETCODE readFile (SCIP *scip, CMININPUT *cmininput, const char *filename)
 
static SCIP_DECL_READERREAD (readerReadCmin)
 
SCIP_RETCODE SCIPincludeReaderCmin (SCIP *scip)
 

Variables

static const char delimchars [] = " \f\n\r\t\v"
 

Macro Definition Documentation

◆ READER_NAME

#define READER_NAME   "cminreader"

◆ READER_DESC

#define READER_DESC   "file reader for cmin file format"

Definition at line 50 of file reader_cmin.c.

Referenced by SCIPincludeReaderCmin().

◆ READER_EXTENSION

#define READER_EXTENSION   "cmin"

Definition at line 51 of file reader_cmin.c.

Referenced by SCIPincludeReaderCmin().

◆ DEFAULT_FILENAME

#define DEFAULT_FILENAME   "-"

name of the file including best known solutions

Definition at line 53 of file reader_cmin.c.

Referenced by SCIPincludeReaderCmin().

◆ DEFAULT_DUALREDUCTION

#define DEFAULT_DUALREDUCTION   TRUE

add locks to avoid dual reductions

Definition at line 54 of file reader_cmin.c.

Referenced by SCIPincludeReaderCmin().

◆ DEFAULT_MIP

#define DEFAULT_MIP   FALSE

create a MIP formulation

Definition at line 55 of file reader_cmin.c.

Referenced by SCIPincludeReaderCmin().

◆ DEFAULT_INITIAL

#define DEFAULT_INITIAL   TRUE

should model constraints be in initial LP?

Definition at line 56 of file reader_cmin.c.

Referenced by SCIPincludeReaderCmin().

◆ DEFAULT_CIP

#define DEFAULT_CIP   TRUE

create a CIP formulation

Definition at line 57 of file reader_cmin.c.

Referenced by SCIPincludeReaderCmin().

◆ DEFAULT_RELAXATION

#define DEFAULT_RELAXATION   3

which relaxation should be added to the maseter (0: none; 1: single; 2: edge-finding; 3: energetic-reasoning

Definition at line 58 of file reader_cmin.c.

Referenced by SCIPincludeReaderCmin().

Typedef Documentation

◆ CMININPUT

typedef struct CminInput CMININPUT

Definition at line 77 of file reader_cmin.c.

Function Documentation

◆ syntaxError()

static void syntaxError ( SCIP scip,
CMININPUT cmininput,
const char *  msg 
)
static

issues an error message and marks the LP data to have errors

Parameters
scipSCIP data structure
cmininputCMIN reading data
msgerror message

Definition at line 81 of file reader_cmin.c.

References CminInput::haserror, CminInput::linebuf, CminInput::linenumber, NULL, SCIP_VERBLEVEL_MINIMAL, SCIPverbMessage(), CminInput::token, and TRUE.

Referenced by readFile().

◆ getNextLine()

static SCIP_Bool getNextLine ( CMININPUT cmininput)
static

gets the next line out of the file stream

Parameters
cmininputCMIN reading data

Definition at line 99 of file reader_cmin.c.

References BMSclearMemoryArray, FALSE, CminInput::file, CminInput::haserror, CminInput::linebuf, CminInput::linenumber, CminInput::linepos, NULL, SCIP_MAXSTRLEN, SCIPdebugMessage, SCIPfgets(), and TRUE.

Referenced by getNextToken().

◆ isDelimChar()

static SCIP_Bool isDelimChar ( char  c)
static

returns whether the given character is a token delimiter

Parameters
cinput character

Definition at line 132 of file reader_cmin.c.

References delimchars, and NULL.

Referenced by getNextToken().

◆ getNextToken()

static SCIP_Bool getNextToken ( CMININPUT cmininput)
static

reads the next token from the input file into the token buffer; returns whether a token was read

Parameters
cmininputCMIN reading data

Definition at line 141 of file reader_cmin.c.

References FALSE, getNextLine(), isDelimChar(), CminInput::linebuf, CminInput::linenumber, CminInput::linepos, NULL, SCIP_MAXSTRLEN, SCIPdebugMessage, CminInput::token, and TRUE.

Referenced by readFile().

◆ findBestObjectiveValue()

static SCIP_RETCODE findBestObjectiveValue ( SCIP scip,
SCIP_Real objval 
)
static

method parses the best known solution for the total leftover out of the give file; if file does not exist or the problem is not listed the best known solution is set to -1 which means unknown

Parameters
scipSCIP data structure
objvalpointer to store best known solution

Definition at line 192 of file reader_cmin.c.

References FALSE, CminInput::file, NULL, READER_NAME, SCIP_Bool, SCIP_CALL, SCIP_INVALIDCALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_VERBLEVEL_HIGH, SCIPdebugMessage, SCIPfclose(), SCIPfgets(), SCIPfopen(), SCIPgetProbName(), SCIPgetStringParam(), SCIPinfinity(), SCIPsnprintf(), SCIPstrtok(), SCIPverbMessage(), SCIPwarningMessage(), CminInput::token, and TRUE.

Referenced by createCipFormulation().

◆ createSortedEventpoints()

static void createSortedEventpoints ( SCIP scip,
int *  releasedates,
int *  deadlinedates,
int *  starttimes,
int *  endtimes,
int *  startindices,
int *  endindices,
int  njobs 
)
static

initialize the sorted event point arrays

Parameters
scipSCIP data structure
releasedatesrelease dates
deadlinedatesdeadline dates
starttimesarray to store sorted start events
endtimesarray to store sorted end events
startindicespermutation with rspect to the start times
endindicespermutation with rspect to the end times
njobsnumber of jobs

Definition at line 302 of file reader_cmin.c.

References SCIPsortIntInt().

Referenced by createIntervalRelaxation().

◆ computeMaxEnergy()

static SCIP_Longint computeMaxEnergy ( int  njobs,
int *  durations,
int *  demands,
int *  releasedates,
int *  deadlinedates,
int  starttime,
int  endtime 
)
static

computes the maximum energy for all variables which correspond to jobs which start between the given start time and end time

Returns
Maximum energy for the given time window
Parameters
njobsnumber of jobs
durationsdurations
demandsdemands
releasedatesrelease dates
deadlinedatesdeadline dates
starttimestart time
endtimeend time

Definition at line 336 of file reader_cmin.c.

References SCIP_Longint.

Referenced by createIntervalRelaxation().

◆ removeRedundantRows()

static int removeRedundantRows ( SCIP_Longint rowtightness,
int *  startidxs,
int  nrows,
SCIP_Longint  tightness 
)
static

remove row which have a tightness which is smaller or equal to the given one

Returns
The number of remaining rows
Parameters
rowtightnessarray containing the tightness for the previously selected rows
startidxsarray containing for each row the index for the start event
nrowscurrent number of rows
tightnesstightness to use to detect redundant rows

Definition at line 367 of file reader_cmin.c.

Referenced by createIntervalRelaxation().

◆ createIntervalRelaxation()

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

create interval relaxation for given sub-problem

Parameters
scipSCIP data structure
relaxationa linear relaxation base on edge-finding idea or energetic-reasoning idea
resourceresource id
varsassignment variables
durationsdurations
demandsdemands
capacitymachine capacity
releasedatesrelease dates
deadlinedatesdeadline dates
njobsnumber of jobs

Definition at line 394 of file reader_cmin.c.

References BMSclearMemoryArray, computeMaxEnergy(), createSortedEventpoints(), MIN, MIN3, NULL, removeRedundantRows(), SCIP_CALL, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCoefKnapsack(), SCIPaddCons(), SCIPallocBufferArray, SCIPcreateConsBasicKnapsack(), SCIPdebugMessage, SCIPfreeBufferArray, SCIPinfoMessage(), SCIPreleaseCons(), and SCIPsnprintf().

Referenced by createMipFormulation().

◆ createMipFormulation()

static SCIP_RETCODE createMipFormulation ( SCIP scip,
int **  durations,
int **  demands,
int **  costs,
int *  capacities,
int *  releasedates,
int *  deadlinedates,
int  njobs,
int  nmachines 
)
static

create MIP formulation and CP constraints

Parameters
scipSCIP data structure
durationsdurations
demandsdemands
costscost
capacitiesmachine capacities
releasedatesrelease dates
deadlinedatesdeadline dates
njobsnumber of jobs
nmachinesnumber of machines

Definition at line 566 of file reader_cmin.c.

References createIntervalRelaxation(), h, MAX, MIN, NULL, READER_NAME, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPaddCoefKnapsack(), SCIPaddCoefLinear(), SCIPaddCoefSetppc(), SCIPaddCons(), SCIPaddVar(), SCIPallocBufferArray, SCIPcreateConsBasicKnapsack(), SCIPcreateConsBasicLinear(), SCIPcreateConsBasicSetpart(), SCIPcreateVarBasic(), SCIPfreeBufferArray, SCIPgetIntParam(), SCIPreleaseCons(), SCIPreleaseVar(), and SCIPsnprintf().

Referenced by readFile().

◆ createMipCpFormulation()

static SCIP_RETCODE createMipCpFormulation ( SCIP scip,
int **  durations,
int **  demands,
int **  costs,
int *  capacities,
int *  releasedates,
int *  deadlinedates,
int  njobs,
int  nmachines 
)
static

create MIP formulation

Parameters
scipSCIP data structure
durationsdurations
demandsdemands
costscost
capacitiesmachine capacities
releasedatesrelease dates
deadlinedatesdeadline dates
njobsnumber of jobs
nmachinesnumber of machines

Definition at line 784 of file reader_cmin.c.

References BMSclearMemoryArray, FALSE, h, MAX, MIN, NULL, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_IMPLINT, SCIPaddCoefKnapsack(), SCIPaddCoefLinear(), SCIPaddCoefSetppc(), SCIPaddCons(), SCIPaddVar(), SCIPallocBufferArray, SCIPcreateConsKnapsack(), SCIPcreateConsLinear(), SCIPcreateConsOptcumulative(), SCIPcreateConsSetpart(), SCIPcreateVar(), SCIPfreeBufferArray, SCIPgetNegatedVar(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsnprintf(), and TRUE.

Referenced by readFile().

◆ createCipFormulation()

static SCIP_RETCODE createCipFormulation ( SCIP scip,
int **  durations,
int **  demands,
int **  costs,
int *  capacities,
int *  releasedates,
int *  deadlinedates,
int  njobs,
int  nmachines 
)
static

create CIP formulation

Parameters
scipSCIP data structure
durationsdurations
demandsdemands
costscost
capacitiesmachine capacities
releasedatesrelease dates
deadlinedatesdeadline dates
njobsnumber of jobs
nmachinesnumber of machines

Definition at line 998 of file reader_cmin.c.

References BMSclearMemoryArray, FALSE, findBestObjectiveValue(), NULL, READER_NAME, SCIP_Bool, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPaddCoefSetppc(), SCIPaddCons(), SCIPaddVar(), SCIPaddVarLocksType(), SCIPallocBufferArray, SCIPcreateConsBasicSetpart(), SCIPcreateConsOptcumulative(), SCIPcreateVarBasic(), SCIPfreeBufferArray, SCIPgetBoolParam(), SCIPgetIntParam(), SCIPinitHeurOptcumulative(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsetObjlimit(), SCIPsnprintf(), and TRUE.

Referenced by readFile().

◆ readFile()

static SCIP_RETCODE readFile ( SCIP scip,
CMININPUT cmininput,
const char *  filename 
)
static

◆ SCIP_DECL_READERREAD()

◆ SCIPincludeReaderCmin()

SCIP_RETCODE SCIPincludeReaderCmin ( SCIP scip)

Variable Documentation

◆ delimchars

const char delimchars[] = " \f\n\r\t\v"
static

Definition at line 60 of file reader_cmin.c.

Referenced by isDelimChar().