40#define HEUR_NAME "optcumulative"
41#define HEUR_DESC "problem specific heuristic of cumulative scheduling problems with optional jobs"
42#define HEUR_DISPCHAR 'q'
43#define HEUR_PRIORITY -1106000
46#define HEUR_MAXDEPTH -1
47#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
48#define HEUR_USESSUBSCIP TRUE
50#define DEFAULT_MAXNODES 1000LL
51#define DEFAULT_MAXPROPROUNDS -1
135 while( !(*infeasible) )
145 for( m = 0; m < nmachines; ++m )
149 currentpos = possitions[m];
152 for( j = currentpos; j < machines[m]; ++j )
160 currentpos = possitions[m];
163 if( currentpos < machines[m] )
177 if( bestmachine == -1 )
180 assert(bestmachine < nmachines);
181 assert(possitions[bestmachine] < machines[bestmachine]);
183 var = binvars[bestmachine][possitions[bestmachine]];
187 possitions[bestmachine]++;
193 SCIPdebugMessage(
"variable <%s> objective coefficient <%g> fixed to 1.0 (%d pseudo cands)\n",
216 SCIPdebugMessage(
"probing ended with %sfeasible problem\n", (*infeasible) ?
"in" :
"");
235 for( v = 0; v <
nvars; ++v )
276 if( !infeasible && pseudoobj >= lowerbound && pseudoobj < upperbound )
310 for( m = 0; m <
heurdata->nmachines && !infeasible; ++m )
315 machineassignment =
heurdata->machineassignments[m];
347 for( j = 0; j <
heurdata->machines[m]; ++j )
362 machineassignment->
vars[pos][j] =
TRUE;
363 key |= (1 << (j % 32));
369 machineassignment->
keys[pos] = key;
381 for(
a = pos - 1;
a >= 0; --
a )
385 &&
nvars > machineassignment->
nones[
a] && ((~key & machineassignment->
keys[
a]) == 0) )
392 for( j =
heurdata->machines[m] - 1; j >= 0; --j )
395 if( machineassignment->
vars[pos][j] < machineassignment->
vars[
a][j] )
411 for( j =
heurdata->machines[m] - 1; j >= 0; --j )
413 if( machineassignment->
vars[pos][j] > machineassignment->
vars[
a][j] )
420 else if(
nvars == machineassignment->
nones[
a] && ((~key & machineassignment->
keys[
a]) == 0) )
423 for( j =
heurdata->machines[m] - 1; j >= 0; --j )
425 if( machineassignment->
vars[pos][j] != machineassignment->
vars[
a][j] )
437 machineassignment->
nones[pos] > machineassignment->
nones[
a] ?
"a subset of" : (machineassignment->
nones[pos] > machineassignment->
nones[
a] ?
"a superset of" :
""),
438 machineassignment->
feasibles[
a] ?
"feasible" :
"infeasible");
445 infeasible = !machineassignment->
feasibles[
a];
450 for( j = 0; j <
heurdata->machines[m]; ++j )
471 for( v = 0; v <
nvars; ++v )
497 SCIP_CALL(
SCIPsolveCumulative(
scip,
nvars, lbs, ubs, objvals, durations, demands,
heurdata->capacities[m], 0, INT_MAX,
498 timelimit, memorylimit,
heurdata->maxnodes, &solved, &infeasible, &unbounded, &error) );
504 machineassignment->
feasibles[pos] = !infeasible;
512 for( j = 0, v = 0; j <
heurdata->machines[m]; ++j )
517 machineassignment->
solvals[pos][j] = lbs[v];
580 for( m =
heurdata->nmachines - 1; m >= 0; --m )
584 for(
a = 0;
a <
heurdata->machineassignments[m]->nassignments; ++
a )
620#define heurInitOptcumulative NULL
623#define heurExitOptcumulative NULL
626#define heurInitsolOptcumulative NULL
629#define heurExitsolOptcumulative NULL
684 heurCopyOptcumulative,
691 "maximum number of nodes to regard in the subproblem",
694 "maximum number of propagation rounds during probing (-1 infinity)",
735 for( m = 0; m < nmachines; ++m )
752 heurdata->machineassignments[m]->nassignments = 0;
753 heurdata->machineassignments[m]->sassignments = njobs;
#define DEFAULT_MAXPROPROUNDS
constraint handler for cumulative constraints
#define SCIP_LONGINT_FORMAT
SCIP_RETCODE SCIPsolveCumulative(SCIP *scip, int njobs, SCIP_Real *ests, SCIP_Real *lsts, SCIP_Real *objvals, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Longint maxnodes, SCIP_Bool *solved, SCIP_Bool *infeasible, SCIP_Bool *unbounded, SCIP_Bool *error)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_VAR ** SCIPgetOrigVars(SCIP *scip)
int SCIPgetNOrigVars(SCIP *scip)
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
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 SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
int SCIPgetNPseudoBranchCands(SCIP *scip)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
SCIP_RETCODE SCIPincludeHeur(SCIP *scip, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEURCOPY((*heurcopy)), SCIP_DECL_HEURFREE((*heurfree)), SCIP_DECL_HEURINIT((*heurinit)), SCIP_DECL_HEUREXIT((*heurexit)), SCIP_DECL_HEURINITSOL((*heurinitsol)), SCIP_DECL_HEUREXITSOL((*heurexitsol)), SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
const char * SCIPheurGetName(SCIP_HEUR *heur)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
SCIP_Real SCIPgetPseudoObjval(SCIP *scip)
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
#define SCIPallocBlockMemory(scip, ptr)
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
int SCIPgetProbingDepth(SCIP *scip)
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
SCIP_RETCODE SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
void SCIPsortPtrPtrIntInt(void **ptrarray1, void **ptrarray2, int *intarray1, int *intarray2, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
assert(minobj< SCIPgetCutoffbound(scip))
#define heurInitsolOptcumulative
static SCIP_RETCODE initializeSol(SCIP *scip, SCIP_SOL *sol)
SCIP_RETCODE SCIPinitHeurOptcumulative(SCIP *scip, int nmachines, int njobs, int *machines, SCIP_VAR ***binvars, SCIP_VAR ***vars, int **durations, int **demands, int *capacities)
static SCIP_RETCODE applyOptcumulativeFixings(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Bool *infeasible)
static SCIP_RETCODE applyOptcumulative(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_RESULT *result)
static void heurdataReset(SCIP *scip, SCIP_HEURDATA *heurdata)
#define heurExitOptcumulative
#define heurExitsolOptcumulative
SCIP_RETCODE SCIPincludeHeurOptcumulative(SCIP *scip)
struct SCIP_Assignment SCIP_ASSIGNMENT
#define heurInitOptcumulative
heuristic for cumulative scheduling with optional activities
#define BMSclearMemoryArray(ptr, num)
#define SCIP_DECL_HEURCOPY(x)
struct SCIP_HeurData SCIP_HEURDATA
struct SCIP_Heur SCIP_HEUR
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_HEUREXEC(x)
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE