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"

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

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.

Referenced by SCIPincludeHeurOptcumulative().

◆ heurExitOptcumulative

#define heurExitOptcumulative NULL

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

Definition at line 623 of file heur_optcumulative.c.

Referenced by SCIPincludeHeurOptcumulative().

◆ 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.

Referenced by SCIPincludeHeurOptcumulative().

◆ 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.

Referenced by SCIPincludeHeurOptcumulative().

Typedef Documentation

◆ SCIP_ASSIGNMENT

typedef struct SCIP_Assignment SCIP_ASSIGNMENT

Definition at line 67 of file heur_optcumulative.c.

Function Documentation

◆ heurdataReset()

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, heurdata, and NULL.

Referenced by SCIPincludeHeurOptcumulative().

◆ applyOptcumulativeFixings()

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 assert(), BMSclearMemoryArray, heurdata, NULL, objval, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPbacktrackProbing(), SCIPdebugMessage, SCIPfixVarProbing(), SCIPfreeBufferArray, SCIPgetNPseudoBranchCands(), SCIPgetProbingDepth(), SCIPinfinity(), SCIPnewProbingNode(), SCIPpropagateProbing(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetUbLocal(), and var.

Referenced by applyOptcumulative().

◆ initializeSol()

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 nvars, SCIP_CALL, SCIP_OKAY, SCIPgetNOrigVars(), SCIPgetOrigVars(), SCIPsetSolVal(), SCIPvarGetLbLocal(), sol, and vars.

Referenced by applyOptcumulative().

◆ applyOptcumulative()

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(), assert(), BMSclearMemoryArray, FALSE, SCIP_Assignment::feasibles, heurdata, initializeSol(), SCIP_Assignment::keys, SCIP_Assignment::nassignments, SCIP_Assignment::nones, NULL, nvars, result, 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(), sol, SCIP_Assignment::solvals, TRUE, var, SCIP_Assignment::vars, and vars.

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIP_DECL_HEURCOPY()

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 assert(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurOptcumulative().

◆ SCIP_DECL_HEURFREE()

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, assert(), heurdata, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPheurGetData(), and SCIPheurSetData().

◆ SCIP_DECL_HEUREXEC()

SCIP_DECL_HEUREXEC ( heurExecOptcumulative )

static

execution method of primal heuristic

Definition at line 633 of file heur_optcumulative.c.

References applyOptcumulative(), assert(), heurdata, NULL, result, 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, heurdata, 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 assert(), HEUR_NAME, heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPduplicateBlockMemoryArray, SCIPerrorMessage, SCIPfindHeur(), SCIPheurGetData(), SCIPsortPtrPtrIntInt(), TRUE, and vars.

Referenced by createCipFormulation().

Detailed Description

Data Structures

Macros

Functions

Macro Definition Documentation

◆ HEUR_NAME

◆ HEUR_DESC

◆ HEUR_DISPCHAR

◆ HEUR_PRIORITY

◆ HEUR_FREQ

◆ HEUR_FREQOFS

◆ HEUR_MAXDEPTH

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

◆ DEFAULT_MAXNODES

◆ DEFAULT_MAXPROPROUNDS

◆ heurInitOptcumulative

◆ heurExitOptcumulative

◆ heurInitsolOptcumulative

◆ heurExitsolOptcumulative

Typedef Documentation

◆ SCIP_ASSIGNMENT

Function Documentation

◆ heurdataReset()

◆ applyOptcumulativeFixings()

◆ initializeSol()

◆ applyOptcumulative()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEUREXEC()

◆ SCIPincludeHeurOptcumulative()

◆ SCIPinitHeurOptcumulative()