1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file heur_optcumulative.h
17 * @ingroup PRIMALHEURISTICS
18 * @brief heuristic for cumulative scheduling with optional activities
19 * @author Stefan Heinz
20 */
21
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23
24 #include <assert.h>
25 #include <string.h>
26
27 #include "scip/cons_cumulative.h"
28 #include "heur_optcumulative.h"
29
30
31 #define HEUR_NAME "optcumulative"
32 #define HEUR_DESC "problem specific heuristic of cumulative scheduling problems with optional jobs"
33 #define HEUR_DISPCHAR 'q'
34 #define HEUR_PRIORITY -1106000
35 #define HEUR_FREQ -1
36 #define HEUR_FREQOFS 0
37 #define HEUR_MAXDEPTH -1
38 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
39 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
40
41 #define DEFAULT_MAXNODES 1000LL /**< maximum number of nodes to regard in the subproblem */
42 #define DEFAULT_MAXPROPROUNDS -1 /**< maximum number of propagation rounds during probing */
43
44 /*
45 * Data structures
46 */
47
48 struct SCIP_Assignment
49 {
50 SCIP_Bool** vars;
51 SCIP_Real** solvals;
52 SCIP_Bool* feasibles;
53 unsigned int* keys;
54 int* nones;
55 int nassignments;
56 int sassignments;
57 };
58 typedef struct SCIP_Assignment SCIP_ASSIGNMENT;
59
60
61 /** primal heuristic data */
62 struct SCIP_HeurData
63 {
64 SCIP_VAR*** binvars; /**< machnine job matrix (choice variables) */
65 SCIP_VAR*** vars; /**< machnine job matrix (start time variables) */
66 int** durations; /**< machnine job duration matrix */
67 int** demands; /**< machnine job demands matrix */
68 int* machines; /**< number of jobs for each machines */
69 int* capacities; /**< machine capacities */
70 int nmachines; /**< number of machines */
71 int njobs; /**< number of njobs */
72
73 SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
74 int maxproprounds; /**< maximum number of propagation rounds during probing */
75 SCIP_Bool initialized; /**< are the candidate list initialized? */
76
77 SCIP_ASSIGNMENT** machineassignments;
78 };
79
80 /*
81 * Local methods
82 */
83
84 /** reset heuristic data structure */
85 static
heurdataReset(SCIP * scip,SCIP_HEURDATA * heurdata)86 void heurdataReset(
87 SCIP* scip, /**< original SCIP data structure */
88 SCIP_HEURDATA* heurdata /**< structure containing heurdata */
89 )
90 {
91 heurdata->vars = NULL;
92 heurdata->binvars = NULL;
93 heurdata->durations = NULL;
94 heurdata->demands = NULL;
95 heurdata->machines = NULL;
96 heurdata->capacities = NULL;
97 heurdata->machineassignments = NULL;
98 heurdata->nmachines = 0;
99 heurdata->njobs = 0;
100
101 heurdata->initialized = FALSE;
102 }
103
104 /** apply variable bound fixing during probing */
105 static
applyOptcumulativeFixings(SCIP * scip,SCIP_HEURDATA * heurdata,SCIP_Bool * infeasible)106 SCIP_RETCODE applyOptcumulativeFixings(
107 SCIP* scip, /**< original SCIP data structure */
108 SCIP_HEURDATA* heurdata, /**< structure containing heurdata */
109 SCIP_Bool* infeasible /**< pointer to store whether problem is infeasible */
110 )
111 {
112 SCIP_VAR*** binvars;
113 int* machines;
114 int* possitions;
115 int nmachines;
116 int j;
117 int m;
118
119 binvars = heurdata->binvars;
120 nmachines = heurdata->nmachines;
121 machines = heurdata->machines;
122
123 SCIP_CALL( SCIPallocBufferArray(scip, &possitions, nmachines) );
124 BMSclearMemoryArray(possitions, nmachines);
125
126 while( !(*infeasible) )
127 {
128 SCIP_VAR* var;
129 SCIP_Real objval;
130 int bestmachine;
131
132 bestmachine = -1;
133 objval = SCIPinfinity(scip);
134
135 /* search over all machines and find the next cheapest job to assign */
136 for( m = 0; m < nmachines; ++m )
137 {
138 int currentpos;
139
140 currentpos = possitions[m];
141
142 /* find next unfixed variable for the current machine */
143 for( j = currentpos; j < machines[m]; ++j )
144 {
145 if( SCIPvarGetLbLocal(binvars[m][j]) + 0.5 < SCIPvarGetUbLocal(binvars[m][j]) )
146 break;
147
148 possitions[m]++;
149 }
150
151 currentpos = possitions[m];
152
153 /* check if we have a variable left on that machine */
154 if( currentpos < machines[m] )
155 {
156 assert(binvars[m][currentpos] != NULL);
157
158 /* check if the objective coefficient is better than the best known one */
159 if( SCIPvarGetObj(binvars[m][currentpos]) < objval )
160 {
161 objval = SCIPvarGetObj(binvars[m][currentpos]);
162 bestmachine = m;
163 }
164 }
165 }
166
167 /* check if unsigned variable was left */
168 if( bestmachine == -1 )
169 break;
170
171 assert(bestmachine < nmachines);
172 assert(possitions[bestmachine] < machines[bestmachine]);
173
174 var = binvars[bestmachine][possitions[bestmachine]];
175 assert(var != NULL);
176 assert(SCIPvarGetLbLocal(var) + 0.5 < SCIPvarGetUbLocal(var));
177
178 possitions[bestmachine]++;
179
180 SCIP_CALL( SCIPnewProbingNode(scip) );
181
182 SCIP_CALL( SCIPfixVarProbing(scip, var, 1.0) );
183
184 SCIPdebugMessage("variable <%s> objective coefficient <%g> fixed to 1.0 (%d pseudo cands)\n",
185 SCIPvarGetName(var), SCIPvarGetObj(var), SCIPgetNPseudoBranchCands(scip));
186
187 /* check if problem is already infeasible */
188 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, infeasible, NULL) );
189
190 if( *infeasible )
191 {
192 /* backtrack */
193 SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip)-1) );
194
195 /* after backtracking the variable might be already fixed to zero */
196 if( SCIPvarGetUbLocal(var) > 0.5 )
197 {
198 SCIP_CALL( SCIPfixVarProbing(scip, var, 0.0) );
199 }
200
201 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, infeasible, NULL) );
202 }
203 }
204
205 SCIPfreeBufferArray(scip, &possitions);
206
207 SCIPdebugMessage("probing ended with %sfeasible problem\n", (*infeasible) ? "in" : "");
208
209 return SCIP_OKAY;
210 }
211
212 /** initialize the solution by assign the lower bound of the variable as solution value */
213 static
initializeSol(SCIP * scip,SCIP_SOL * sol)214 SCIP_RETCODE initializeSol(
215 SCIP* scip, /**< SCIP data structure */
216 SCIP_SOL* sol /**< solution to be initialize */
217 )
218 {
219 SCIP_VAR** vars;
220 int nvars;
221 int v;
222
223 nvars = SCIPgetNOrigVars(scip);
224 vars = SCIPgetOrigVars(scip);
225
226 for( v = 0; v < nvars; ++v )
227 {
228 SCIP_CALL( SCIPsetSolVal(scip, sol, vars[v], SCIPvarGetLbLocal(vars[v])) );
229 }
230
231 return SCIP_OKAY;
232 }
233
234 /** main procedure of the optcumulative heuristic */
235 static
applyOptcumulative(SCIP * scip,SCIP_HEUR * heur,SCIP_HEURDATA * heurdata,SCIP_RESULT * result)236 SCIP_RETCODE applyOptcumulative(
237 SCIP* scip, /**< SCIP data structure */
238 SCIP_HEUR* heur, /**< heuristic */
239 SCIP_HEURDATA* heurdata, /**< heuristic data structure */
240 SCIP_RESULT* result /**< pointer to store the result */
241 )
242 {
243 SCIP_Real lowerbound;
244 SCIP_Real upperbound;
245 SCIP_Real pseudoobj;
246 SCIP_Bool infeasible;
247 #if 0
248 int depth;
249 #endif
250
251 assert(heur != NULL);
252 assert(heurdata != NULL);
253
254 /* initialize default values */
255 infeasible = FALSE;
256
257 *result = SCIP_DIDNOTFIND;
258 #if 0
259 depth = SCIPgetDepth(scip);
260 #endif
261
262 /* start probing */
263 SCIP_CALL( SCIPstartProbing(scip) );
264
265 /* apply the variable fixings */
266 SCIP_CALL( applyOptcumulativeFixings(scip, heurdata, &infeasible) );
267
268 lowerbound = SCIPgetLowerbound(scip);
269 upperbound = SCIPgetUpperbound(scip);
270 pseudoobj = SCIPgetPseudoObjval(scip);
271
272 /* if a solution has been found --> fix all other variables by subscip if necessary */
273 if( !infeasible && pseudoobj >= lowerbound && pseudoobj < upperbound )
274 {
275 SCIP_ASSIGNMENT* machineassignment;
276 int pos;
277
278 SCIP_SOL* sol;
279 SCIP_VAR** vars;
280 SCIP_Real* lbs;
281 SCIP_Real* ubs;
282 int* durations;
283 int* demands;
284 SCIP_Bool unbounded;
285 int njobs;
286 int nvars;
287 int j;
288 int m;
289
290 /* create temporary solution */
291 SCIP_CALL( SCIPcreateOrigSol(scip, &sol, heur) );
292
293 /* initialize the solution with the lower bound of all variables */
294 SCIP_CALL( initializeSol(scip, sol) );
295
296 njobs = heurdata->njobs;
297
298 /* allocate memory for collecting the information for the single machines */
299 SCIP_CALL( SCIPallocBufferArray(scip, &vars, njobs) );
300 SCIP_CALL( SCIPallocBufferArray(scip, &durations, njobs) );
301 SCIP_CALL( SCIPallocBufferArray(scip, &demands, njobs) );
302 SCIP_CALL( SCIPallocBufferArray(scip, &lbs, njobs) );
303 SCIP_CALL( SCIPallocBufferArray(scip, &ubs, njobs) );
304
305 nvars = -1;
306
307 for( m = 0; m < heurdata->nmachines && !infeasible; ++m )
308 {
309 unsigned int key;
310 int a;
311
312 machineassignment = heurdata->machineassignments[m];
313
314 pos = machineassignment->nassignments;
315
316 /* realloc memory if not enough space left */
317 if( machineassignment->nassignments == machineassignment->sassignments)
318 {
319 int oldsize;
320 int newsize;
321
322 oldsize = machineassignment->sassignments;
323 newsize = SCIPcalcMemGrowSize(scip, pos + 1);
324
325 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(machineassignment->vars), oldsize, newsize) );
326 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(machineassignment->solvals), oldsize, newsize) );
327 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(machineassignment->feasibles), oldsize, newsize) );
328 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(machineassignment->keys), oldsize, newsize) );
329 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(machineassignment->nones), oldsize, newsize) );
330
331 machineassignment->sassignments = newsize;
332 }
333 assert(machineassignment->sassignments > pos);
334
335 assert(njobs >= heurdata->machines[m]);
336 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &machineassignment->vars[pos], heurdata->machines[m]) ); /*lint !e866*/
337 BMSclearMemoryArray(machineassignment->vars[pos], heurdata->machines[m]); /*lint !e866*/
338 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &machineassignment->solvals[pos], heurdata->machines[m]) ); /*lint !e866*/
339 machineassignment->nassignments++;
340 nvars = 0;
341 key = 0;
342
343 /* collect the jobs which are assign to that machine */
344 for( j = 0; j < heurdata->machines[m]; ++j )
345 {
346 SCIP_VAR* binvar;
347
348 binvar = heurdata->binvars[m][j];
349 assert(binvar != NULL);
350
351 /* check if job is assign to that machine */
352 if( SCIPvarGetLbLocal(binvar) > 0.5 )
353 {
354 vars[nvars] = heurdata->vars[m][j];
355 durations[nvars] = heurdata->durations[m][j];
356 demands[nvars] = heurdata->demands[m][j];
357 nvars++;
358
359 machineassignment->vars[pos][j] = TRUE;
360 key |= (1 << (j % 32)); /*lint !e701*/
361
362 SCIP_CALL( SCIPsetSolVal(scip, sol, binvar, 1.0) );
363 }
364 }
365 machineassignment->nones[pos] = nvars;
366 machineassignment->keys[pos] = key;
367
368 /* if none of the variables is assigned to that machine we skip it */
369 if( nvars == 0 )
370 {
371 SCIPfreeBlockMemoryArray(scip, &machineassignment->vars[pos], heurdata->machines[m]); /*lint !e866*/
372 SCIPfreeBlockMemoryArray(scip, &machineassignment->solvals[pos], heurdata->machines[m]); /*lint !e866*/
373 machineassignment->nassignments--;
374 continue;
375 }
376
377 /* check whether we already have try a subset of this variable combination */
378 for( a = pos - 1; a >= 0; --a )
379 {
380 /* infeasible check */
381 if( !machineassignment->feasibles[a]
382 && nvars > machineassignment->nones[a] && ((~key & machineassignment->keys[a]) == 0) )
383 {
384 /* if we compare to an infeasible assignment, that assignment can be smaller or equal since a smaller
385 * infeasible assignment induces a infeasibility for all assignments which include that assignment
386 */
387
388 /* do the expensive pairwise comparison */
389 for( j = heurdata->machines[m] - 1; j >= 0; --j )
390 {
391 /* at least the same variables in the old combination have to be assigned to 1 */
392 if( machineassignment->vars[pos][j] < machineassignment->vars[a][j] )
393 break;
394 }
395 /* we already tried this combination */
396 if( j == -1 )
397 break;
398 }
399 /* feasible check */
400 else if( machineassignment->feasibles[a] &&
401 nvars < machineassignment->nones[a] && ((key & ~(machineassignment->keys[a])) == 0) )
402 {
403 /* if we compare to a feasible assignment, that assignment can be larger or equal since a larger feasible
404 * assignment induces a feasibility for all assignments which is subset of that assignment
405 */
406
407 /* do the expensive pairwise comparison */
408 for( j = heurdata->machines[m] - 1; j >= 0; --j )
409 {
410 if( machineassignment->vars[pos][j] > machineassignment->vars[a][j] )
411 break;
412 }
413 /* we already tried this combination */
414 if( j == -1 )
415 break;
416 }
417 else if( nvars == machineassignment->nones[a] && ((~key & machineassignment->keys[a]) == 0) )
418 {
419 /* do the expensive pairwise comparison */
420 for( j = heurdata->machines[m] - 1; j >= 0; --j )
421 {
422 if( machineassignment->vars[pos][j] != machineassignment->vars[a][j] )
423 break;
424 }
425 /* we already tried this combination */
426 if( j == -1 )
427 break;
428 }
429 }
430
431 if( a >= 0 )
432 {
433 SCIPdebugMessage("We already tried %s this combination, it was %s\n",
434 machineassignment->nones[pos] > machineassignment->nones[a] ? "a subset of" : (machineassignment->nones[pos] > machineassignment->nones[a] ? "a superset of" : ""),
435 machineassignment->feasibles[a] ? "feasible" : "infeasible");
436
437 /* delete unnecessary data */
438 SCIPfreeBlockMemoryArray(scip, &machineassignment->vars[pos], heurdata->machines[m]); /*lint !e866*/
439 SCIPfreeBlockMemoryArray(scip, &machineassignment->solvals[pos], heurdata->machines[m]); /*lint !e866*/
440 machineassignment->nassignments--;
441
442 infeasible = !machineassignment->feasibles[a];
443
444 if( infeasible )
445 break;
446
447 for( j = 0; j < heurdata->machines[m]; ++j )
448 {
449 if( machineassignment->vars[a][j] && SCIPvarGetLbLocal(heurdata->binvars[m][j]) > 0.5 )
450 {
451 SCIP_CALL( SCIPsetSolVal(scip, sol, heurdata->vars[m][j], machineassignment->solvals[a][j]) );
452 }
453 }
454 }
455 else
456 {
457 SCIP_Real* objvals;
458 SCIP_Real timelimit;
459 SCIP_Real memorylimit;
460 SCIP_Bool solved;
461 SCIP_Bool error;
462 int v;
463
464 SCIPdebugMessage("check machine %d (variables %d)\n", m, nvars);
465
466 SCIP_CALL( SCIPallocBufferArray(scip, &objvals, nvars) );
467
468 for( v = 0; v < nvars; ++v )
469 {
470 SCIP_VAR* var;
471
472 var = vars[v];
473 assert(var != NULL);
474
475 lbs[v] = SCIPvarGetLbLocal(var);
476 ubs[v] = SCIPvarGetUbLocal(var);
477 objvals[v] = SCIPvarGetObj(var);
478 }
479
480 /* check whether there is enough time and memory left */
481 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
482 if( !SCIPisInfinity(scip, timelimit) )
483 timelimit -= SCIPgetSolvingTime(scip);
484 SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
485
486 /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
487 if( !SCIPisInfinity(scip, memorylimit) )
488 {
489 memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
490 memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
491 }
492
493 /* solve the cumulative condition separately */
494 SCIP_CALL( SCIPsolveCumulative(scip, nvars, lbs, ubs, objvals, durations, demands, heurdata->capacities[m], 0, INT_MAX,
495 timelimit, memorylimit, heurdata->maxnodes, &solved, &infeasible, &unbounded, &error) );
496 assert(!unbounded);
497 assert(!error);
498
499 SCIPfreeBufferArray(scip, &objvals);
500
501 machineassignment->feasibles[pos] = !infeasible;
502
503 if( infeasible )
504 {
505 SCIPdebugMessage("infeasible :-(\n");
506 break;
507 }
508
509 for( j = 0, v = 0; j < heurdata->machines[m]; ++j )
510 {
511 if( machineassignment->vars[pos][j] && SCIPvarGetLbLocal(heurdata->binvars[m][j]) > 0.5 )
512 {
513 SCIP_CALL( SCIPsetSolVal(scip, sol, heurdata->vars[m][j], lbs[v]) );
514 machineassignment->solvals[pos][j] = lbs[v];
515 v++;
516 }
517 }
518 }
519 }
520
521 SCIPfreeBufferArray(scip, &ubs);
522 SCIPfreeBufferArray(scip, &lbs);
523 SCIPfreeBufferArray(scip, &demands);
524 SCIPfreeBufferArray(scip, &durations);
525 SCIPfreeBufferArray(scip, &vars);
526
527 /* try and free solution */
528 if( !infeasible )
529 {
530 SCIP_Bool stored;
531
532 SCIPdebugMessage("************ try solution <%g>\n", SCIPgetSolOrigObj(scip, sol));
533
534 SCIP_CALL( SCIPtrySolFree(scip, &sol, FALSE, FALSE, FALSE, FALSE, TRUE, &stored) );
535
536 if( stored )
537 *result = SCIP_FOUNDSOL;
538 }
539 #if 0
540 else
541 {
542 /* check that code */
543 int v;
544
545 SCIP_CALL( SCIPinitConflictAnalysis(scip) );
546
547 for( v = 0; v < heurdata->machines[m]; ++v )
548 {
549 SCIP_CALL( SCIPaddConflictBinvar(scip, heurdata->binvars[m][v]) );
550 SCIP_CALL( SCIPaddConflictLb(scip, heurdata->vars[m][v], NULL) );
551 SCIP_CALL( SCIPaddConflictUb(scip, heurdata->vars[m][v], NULL) );
552 }
553
554 /* analyze the conflict */
555 #if 0
556 SCIP_CALL( SCIPanalyzeConflict(scip, depth, NULL) );
557 #endif
558 SCIP_CALL( SCIPanalyzeConflict(scip, 0, NULL) );
559 SCIP_CALL( SCIPfreeSol(scip, &sol) );
560 }
561 #endif
562 }
563
564 /* exit probing mode */
565 SCIP_CALL( SCIPendProbing(scip) );
566
567 return SCIP_OKAY;
568 }
569
570 /*
571 * Callback methods of primal heuristic
572 */
573
574 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
575 static
SCIP_DECL_HEURCOPY(heurCopyOptcumulative)576 SCIP_DECL_HEURCOPY(heurCopyOptcumulative)
577 { /*lint --e{715}*/
578 assert(scip != NULL);
579 assert(heur != NULL);
580 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
581
582 /* call inclusion method of heuristic */
583 SCIP_CALL( SCIPincludeHeurOptcumulative(scip) );
584
585 return SCIP_OKAY;
586 }
587
588 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
589 static
SCIP_DECL_HEURFREE(heurFreeOptcumulative)590 SCIP_DECL_HEURFREE(heurFreeOptcumulative)
591 { /*lint --e{715}*/
592 SCIP_HEURDATA* heurdata;
593 int m;
594
595 /* free heuristic data */
596 heurdata = SCIPheurGetData(heur);
597 assert(heurdata != NULL);
598
599 /* release all variables */
600 for( m = heurdata->nmachines - 1; m >= 0; --m )
601 {
602 int a;
603
604 for( a = 0; a < heurdata->machineassignments[m]->nassignments; ++a )
605 {
606 SCIPfreeBlockMemoryArray(scip, &(heurdata->machineassignments[m]->vars[a]), heurdata->machines[m]); /*lint !e866*/
607 SCIPfreeBlockMemoryArray(scip, &(heurdata->machineassignments[m]->solvals[a]), heurdata->machines[m]); /*lint !e866*/
608 }
609
610 SCIPfreeBlockMemoryArray(scip, &(heurdata->machineassignments[m]->nones), heurdata->machineassignments[m]->sassignments);
611 SCIPfreeBlockMemoryArray(scip, &(heurdata->machineassignments[m]->keys), heurdata->machineassignments[m]->sassignments);
612 SCIPfreeBlockMemoryArray(scip, &(heurdata->machineassignments[m]->feasibles), heurdata->machineassignments[m]->sassignments);
613 SCIPfreeBlockMemoryArray(scip, &(heurdata->machineassignments[m]->solvals), heurdata->machineassignments[m]->sassignments);
614 SCIPfreeBlockMemoryArray(scip, &(heurdata->machineassignments[m]->vars), heurdata->machineassignments[m]->sassignments);
615 SCIPfreeBlockMemory(scip, &heurdata->machineassignments[m]); /*lint !e866*/
616
617 SCIPfreeBlockMemoryArray(scip, &heurdata->vars[m], heurdata->machines[m]);
618 SCIPfreeBlockMemoryArray(scip, &heurdata->binvars[m], heurdata->machines[m]);
619 SCIPfreeBlockMemoryArray(scip, &heurdata->durations[m], heurdata->machines[m]);
620 SCIPfreeBlockMemoryArray(scip, &heurdata->demands[m], heurdata->machines[m]);
621 }
622
623 /* free arrays */
624 SCIPfreeBlockMemoryArrayNull(scip, &heurdata->machineassignments, heurdata->nmachines);
625 SCIPfreeBlockMemoryArrayNull(scip, &heurdata->demands, heurdata->nmachines);
626 SCIPfreeBlockMemoryArrayNull(scip, &heurdata->durations, heurdata->nmachines);
627 SCIPfreeBlockMemoryArrayNull(scip, &heurdata->binvars, heurdata->nmachines);
628 SCIPfreeBlockMemoryArrayNull(scip, &heurdata->vars, heurdata->nmachines);
629
630 SCIPfreeBlockMemoryArrayNull(scip, &heurdata->capacities, heurdata->nmachines);
631 SCIPfreeBlockMemoryArrayNull(scip, &heurdata->machines, heurdata->nmachines);
632
633 SCIPfreeBlockMemory(scip, &heurdata);
634 SCIPheurSetData(heur, NULL);
635
636 return SCIP_OKAY;
637 }
638
639 /** initialization method of primal heuristic (called after problem was transformed) */
640 #define heurInitOptcumulative NULL
641
642 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
643 #define heurExitOptcumulative NULL
644
645 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
646 #define heurInitsolOptcumulative NULL
647
648 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
649 #define heurExitsolOptcumulative NULL
650
651 /** execution method of primal heuristic */
652 static
SCIP_DECL_HEUREXEC(heurExecOptcumulative)653 SCIP_DECL_HEUREXEC(heurExecOptcumulative)
654 { /*lint --e{715}*/
655 SCIP_HEURDATA* heurdata;
656
657 assert( heur != NULL );
658 assert( scip != NULL );
659 assert( result != NULL );
660
661 *result = SCIP_DIDNOTRUN;
662
663 if( SCIPgetNPseudoBranchCands(scip) == 0 )
664 return SCIP_OKAY;
665
666 heurdata = SCIPheurGetData(heur);
667 assert(heurdata != NULL);
668
669 if( !heurdata->initialized )
670 return SCIP_OKAY;
671
672 if( SCIPisStopped(scip) )
673 return SCIP_OKAY;
674
675 SCIPdebugMessage("apply optcumulative heuristic at node %"SCIP_LONGINT_FORMAT"\n",
676 SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
677
678 *result = SCIP_DIDNOTFIND;
679
680 /* try variable lower and upper bounds which respect to objective coefficients */
681 SCIP_CALL( applyOptcumulative(scip, heur, heurdata, result) );
682
683 return SCIP_OKAY;
684 }
685
686 /*
687 * primal heuristic specific interface methods
688 */
689
690 /** creates the optcumulative primal heuristic and includes it in SCIP */
SCIPincludeHeurOptcumulative(SCIP * scip)691 SCIP_RETCODE SCIPincludeHeurOptcumulative(
692 SCIP* scip /**< SCIP data structure */
693 )
694 {
695 SCIP_HEURDATA* heurdata;
696
697 /* create optcumulative primal heuristic data */
698 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
699 heurdataReset(scip, heurdata);
700
701 /* include primal heuristic */
702 SCIP_CALL( SCIPincludeHeur(scip, HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
703 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP,
704 heurCopyOptcumulative,
705 heurFreeOptcumulative, heurInitOptcumulative, heurExitOptcumulative,
706 heurInitsolOptcumulative, heurExitsolOptcumulative, heurExecOptcumulative,
707 heurdata) );
708
709 /* add variable bounds primal heuristic parameters */
710 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/"HEUR_NAME"/maxnodes",
711 "maximum number of nodes to regard in the subproblem",
712 &heurdata->maxnodes, TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
713 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/maxproprounds",
714 "maximum number of propagation rounds during probing (-1 infinity)",
715 &heurdata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -1, INT_MAX/4, NULL, NULL) );
716
717 return SCIP_OKAY;
718 }
719
720 /** initialize the heuristics data structure */
SCIPinitHeurOptcumulative(SCIP * scip,int nmachines,int njobs,int * machines,SCIP_VAR *** binvars,SCIP_VAR *** vars,int ** durations,int ** demands,int * capacities)721 SCIP_RETCODE SCIPinitHeurOptcumulative(
722 SCIP* scip, /**< original SCIP data structure */
723 int nmachines, /**< number of machines */
724 int njobs, /**< number of njobs */
725 int* machines, /**< number of jobs for each machines */
726 SCIP_VAR*** binvars, /**< machnine job matrix (choice variables) */
727 SCIP_VAR*** vars, /**< machnine job matrix (start time variables) */
728 int** durations, /**< machnine job duration matrix */
729 int** demands, /**< machnine job demands matrix */
730 int* capacities /**< machine capacities */
731 )
732 {
733 SCIP_HEUR* heur;
734 SCIP_HEURDATA* heurdata;
735 int m;
736
737 heur = SCIPfindHeur(scip, HEUR_NAME);
738
739 if( heur == NULL )
740 {
741 SCIPerrorMessage("optcumulative heuristic not found\n");
742 return SCIP_PLUGINNOTFOUND;
743 }
744
745 heurdata = SCIPheurGetData(heur);
746 assert(heurdata != NULL);
747
748 /* copy the problem data */
749 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->vars, nmachines) );
750 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->binvars, nmachines) );
751 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->durations, nmachines) );
752 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->demands, nmachines) );
753 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->machineassignments, nmachines) );
754
755 for( m = 0; m < nmachines; ++m )
756 {
757 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &heurdata->vars[m], vars[m], machines[m]) ); /*lint !e866*/
758 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &heurdata->binvars[m], binvars[m], machines[m]) ); /*lint !e866*/
759 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &heurdata->durations[m], durations[m], machines[m]) ); /*lint !e866*/
760 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &heurdata->demands[m], demands[m], machines[m]) ); /*lint !e866*/
761
762 /* sort variable w.r.t. their objective coefficient */
763 SCIPsortPtrPtrIntInt((void**)heurdata->binvars[m], (void**)heurdata->vars[m],
764 heurdata->durations[m], heurdata->demands[m], SCIPvarCompObj, machines[m]);
765
766 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata->machineassignments[m]) ); /*lint !e866*/
767 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(heurdata->machineassignments[m]->vars), njobs) );
768 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(heurdata->machineassignments[m]->solvals), njobs) );
769 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(heurdata->machineassignments[m]->feasibles), njobs) );
770 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(heurdata->machineassignments[m]->keys), njobs) );
771 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(heurdata->machineassignments[m]->nones), njobs) );
772 heurdata->machineassignments[m]->nassignments = 0;
773 heurdata->machineassignments[m]->sassignments = njobs;
774 }
775
776 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &heurdata->machines, machines, nmachines) );
777 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &heurdata->capacities, capacities, nmachines) );
778
779 heurdata->nmachines = nmachines;
780 heurdata->njobs = njobs;
781 heurdata->initialized = TRUE;
782
783 return SCIP_OKAY;
784 }
785