heur_optcumulative.c File Reference

Detailed Description

heuristic for cumulative scheduling with optional activities

Author

Stefan Heinz

Definition in file heur_optcumulative.c.

#include <assert.h>
#include <string.h>
#include "scip/cons_cumulative.h"
#include "heur_optcumulative.h"

Go to the source code of this file.

Data Structures
struct	SCIP_Assignment

Macros
#define	HEUR_NAME   "optcumulative"
#define	HEUR_DESC   "problem specific heuristic of cumulative scheduling problems with optional jobs"
#define	HEUR_DISPCHAR   'q'
#define	HEUR_PRIORITY   -1106000
#define	HEUR_FREQ   -1
#define	HEUR_FREQOFS   0
#define	HEUR_MAXDEPTH   -1
#define	HEUR_TIMING   SCIP_HEURTIMING_BEFORENODE
#define	HEUR_USESSUBSCIP   TRUE
#define	DEFAULT_MAXNODES   1000LL
#define	DEFAULT_MAXPROPROUNDS   -1
#define	heurInitOptcumulative   NULL
#define	heurExitOptcumulative   NULL
#define	heurInitsolOptcumulative   NULL
#define	heurExitsolOptcumulative   NULL

Typedefs
typedef struct SCIP_Assignment	SCIP_ASSIGNMENT

Functions
static void	heurdataReset (SCIP *scip, SCIP_HEURDATA *heurdata)
static SCIP_RETCODE	applyOptcumulativeFixings (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Bool *infeasible)
static SCIP_RETCODE	initializeSol (SCIP *scip, SCIP_SOL *sol)
static SCIP_RETCODE	applyOptcumulative (SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_RESULT *result)
static	SCIP_DECL_HEURCOPY (heurCopyOptcumulative)
static	SCIP_DECL_HEURFREE (heurFreeOptcumulative)
static	SCIP_DECL_HEUREXEC (heurExecOptcumulative)
SCIP_RETCODE	SCIPincludeHeurOptcumulative (SCIP *scip)
SCIP_RETCODE	SCIPinitHeurOptcumulative (SCIP *scip, int nmachines, int njobs, int *machines, SCIP_VAR ***binvars, SCIP_VAR ***vars, int **durations, int **demands, int *capacities)

Macro Definition Documentation

HEUR_NAME

#define HEUR_NAME   "optcumulative"

Definition at line 40 of file heur_optcumulative.c.

HEUR_DESC

#define HEUR_DESC   "problem specific heuristic of cumulative scheduling problems with optional jobs"

Definition at line 41 of file heur_optcumulative.c.

HEUR_DISPCHAR

#define HEUR_DISPCHAR   'q'

Definition at line 42 of file heur_optcumulative.c.

HEUR_PRIORITY

#define HEUR_PRIORITY   -1106000

Definition at line 43 of file heur_optcumulative.c.

HEUR_FREQ

#define HEUR_FREQ   -1

Definition at line 44 of file heur_optcumulative.c.

HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 45 of file heur_optcumulative.c.

HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 46 of file heur_optcumulative.c.

HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_BEFORENODE

Definition at line 47 of file heur_optcumulative.c.

HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   TRUE

does the heuristic use a secondary SCIP instance?

Definition at line 48 of file heur_optcumulative.c.

DEFAULT_MAXNODES

#define DEFAULT_MAXNODES   1000LL

maximum number of nodes to regard in the subproblem

Definition at line 50 of file heur_optcumulative.c.

DEFAULT_MAXPROPROUNDS

#define DEFAULT_MAXPROPROUNDS   -1

maximum number of propagation rounds during probing

Definition at line 51 of file heur_optcumulative.c.

heurInitOptcumulative

#define heurInitOptcumulative   NULL

initialization method of primal heuristic (called after problem was transformed)

Definition at line 620 of file heur_optcumulative.c.

heurExitOptcumulative

#define heurExitOptcumulative   NULL

deinitialization method of primal heuristic (called before transformed problem is freed)

Definition at line 623 of file heur_optcumulative.c.

heurInitsolOptcumulative

#define heurInitsolOptcumulative   NULL

solving process initialization method of primal heuristic (called when branch and bound process is about to begin)

Definition at line 626 of file heur_optcumulative.c.

heurExitsolOptcumulative

#define heurExitsolOptcumulative   NULL

solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)

Definition at line 629 of file heur_optcumulative.c.

Typedef Documentation

SCIP_ASSIGNMENT

typedef struct SCIP_Assignment SCIP_ASSIGNMENT

Definition at line 67 of file heur_optcumulative.c.

Function Documentation

heurdataReset()

static void heurdataReset ( SCIP *  scip, SCIP_HEURDATA *  heurdata  )

static

reset heuristic data structure

Parameters

scip	original SCIP data structure
heurdata	structure containing heurdata

Definition at line 95 of file heur_optcumulative.c.

References FALSE, and NULL.

Referenced by SCIPincludeHeurOptcumulative().

applyOptcumulativeFixings()

static SCIP_RETCODE applyOptcumulativeFixings ( SCIP *  scip, SCIP_HEURDATA *  heurdata, SCIP_Bool *  infeasible  )

static

apply variable bound fixing during probing

Parameters

scip	original SCIP data structure
heurdata	structure containing heurdata
infeasible	pointer to store whether problem is infeasible

Definition at line 115 of file heur_optcumulative.c.

References BMSclearMemoryArray, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPbacktrackProbing(), SCIPdebugMessage, SCIPfixVarProbing(), SCIPfreeBufferArray, SCIPgetNPseudoBranchCands(), SCIPgetProbingDepth(), SCIPinfinity(), SCIPnewProbingNode(), SCIPpropagateProbing(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetObj(), and SCIPvarGetUbLocal().

Referenced by applyOptcumulative().

initializeSol()

static SCIP_RETCODE initializeSol ( SCIP *  scip, SCIP_SOL *  sol  )

static

initialize the solution by assign the lower bound of the variable as solution value

Parameters

scip	SCIP data structure
sol	solution to be initialize

Definition at line 223 of file heur_optcumulative.c.

References SCIP_CALL, SCIP_OKAY, SCIPgetNOrigVars(), SCIPgetOrigVars(), SCIPsetSolVal(), and SCIPvarGetLbLocal().

Referenced by applyOptcumulative().

applyOptcumulative()

static SCIP_RETCODE applyOptcumulative ( SCIP *  scip, SCIP_HEUR *  heur, SCIP_HEURDATA *  heurdata, SCIP_RESULT *  result  )

static

main procedure of the optcumulative heuristic

Parameters

scip	SCIP data structure
heur	heuristic
heurdata	heuristic data structure
result	pointer to store the result

Definition at line 245 of file heur_optcumulative.c.

References a, applyOptcumulativeFixings(), BMSclearMemoryArray, FALSE, SCIP_Assignment::feasibles, initializeSol(), SCIP_Assignment::keys, SCIP_Assignment::nassignments, SCIP_Assignment::nones, NULL, SCIP_Assignment::sassignments, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_FOUNDSOL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPcalcMemGrowSize(), SCIPcreateOrigSol(), SCIPdebugMessage, SCIPendProbing(), SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPgetLowerbound(), SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetPseudoObjval(), SCIPgetRealParam(), SCIPgetSolOrigObj(), SCIPgetSolvingTime(), SCIPgetUpperbound(), SCIPisInfinity(), SCIPreallocBlockMemoryArray, SCIPsetSolVal(), SCIPsolveCumulative(), SCIPstartProbing(), SCIPtrySolFree(), SCIPvarGetLbLocal(), SCIPvarGetObj(), SCIPvarGetUbLocal(), SCIP_Assignment::solvals, TRUE, and SCIP_Assignment::vars.

Referenced by SCIP_DECL_HEUREXEC().

SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyOptcumulative  )

static

copy method for primal heuristic plugins (called when SCIP copies plugins)

Definition at line 556 of file heur_optcumulative.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurOptcumulative().

SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeOptcumulative  )

static

destructor of primal heuristic to free user data (called when SCIP is exiting)

Definition at line 570 of file heur_optcumulative.c.

References a, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPheurGetData(), and SCIPheurSetData().

SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecOptcumulative  )

static

execution method of primal heuristic

Definition at line 633 of file heur_optcumulative.c.

References applyOptcumulative(), NULL, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIPdebugMessage, SCIPgetCurrentNode(), SCIPgetNPseudoBranchCands(), SCIPheurGetData(), SCIPisStopped(), and SCIPnodeGetNumber().

SCIPincludeHeurOptcumulative()

SCIP_RETCODE SCIPincludeHeurOptcumulative

(

SCIP *

scip

)

creates the optcumulative primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 671 of file heur_optcumulative.c.

References DEFAULT_MAXNODES, DEFAULT_MAXPROPROUNDS, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, heurdataReset(), heurExitOptcumulative, heurExitsolOptcumulative, heurInitOptcumulative, heurInitsolOptcumulative, NULL, SCIP_CALL, SCIP_LONGINT_MAX, SCIP_OKAY, SCIPaddIntParam(), SCIPaddLongintParam(), SCIPallocBlockMemory, SCIPincludeHeur(), and TRUE.

Referenced by runShell(), and SCIP_DECL_HEURCOPY().

SCIPinitHeurOptcumulative()

SCIP_RETCODE SCIPinitHeurOptcumulative	(	SCIP *	scip,
		int	nmachines,
		int	njobs,
		int *	machines,
		SCIP_VAR ***	binvars,
		SCIP_VAR ***	vars,
		int **	durations,
		int **	demands,
		int *	capacities
	)

initialize the heuristics data structure

Parameters

scip	original SCIP data structure
nmachines	number of machines
njobs	number of njobs
machines	number of jobs for each machines
binvars	machnine job matrix (choice variables)
vars	machnine job matrix (start time variables)
durations	machnine job duration matrix
demands	machnine job demands matrix
capacities	machine capacities

Definition at line 701 of file heur_optcumulative.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPduplicateBlockMemoryArray, SCIPerrorMessage, SCIPfindHeur(), SCIPheurGetData(), SCIPsortPtrPtrIntInt(), and TRUE.

Referenced by createCipFormulation().