Scippy

SCIP

Solving Constraint Integer Programs

heur_optcumulative.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2020 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 
49 {
53  unsigned int* keys;
54  int* nones;
57 };
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
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
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",
186 
187  /* check if problem is already infeasible */
188  SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, infeasible, NULL) );
189 
190  if( *infeasible )
191  {
192  /* backtrack */
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
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
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 
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
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 */
584 
585  return SCIP_OKAY;
586 }
587 
588 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
589 static
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
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",
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 */
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 */
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 */
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 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
SCIP_RETCODE SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:557
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:86
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:977
static SCIP_RETCODE applyOptcumulative(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_RESULT *result)
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:687
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:80
static SCIP_DECL_HEUREXEC(heurExecOptcumulative)
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1429
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1213
constraint handler for cumulative constraints
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
Definition: scip_probing.c:409
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip_probing.c:156
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1340
static void heurdataReset(SCIP *scip, SCIP_HEURDATA *heurdata)
#define HEUR_FREQOFS
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)
Definition: scip_heur.c:58
SCIP_EXPORT SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7420
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:81
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:360
#define FALSE
Definition: def.h:73
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17510
#define HEUR_TIMING
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
#define HEUR_USESSUBSCIP
#define HEUR_PRIORITY
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition: scip_mem.c:91
#define SCIPdebugMessage
Definition: pub_message.h:87
SCIP_RETCODE SCIPanalyzeConflict(SCIP *scip, int validdepth, SCIP_Bool *success)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
#define DEFAULT_MAXNODES
SCIP_Real SCIPgetPseudoObjval(SCIP *scip)
Definition: scip_lp.c:324
#define SCIP_LONGINT_MAX
Definition: def.h:149
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
#define DEFAULT_MAXPROPROUNDS
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition: scip_heur.c:249
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)
int SCIPgetNPseudoBranchCands(SCIP *scip)
Definition: scip_branch.c:749
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:92
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17012
static SCIP_DECL_HEURFREE(heurFreeOptcumulative)
#define SCIPerrorMessage
Definition: pub_message.h:55
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)
static SCIP_RETCODE initializeSol(SCIP *scip, SCIP_SOL *sol)
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip_probing.c:189
SCIP_EXPORT void SCIPsortPtrPtrIntInt(void **ptrarray1, void **ptrarray2, int *intarray1, int *intarray2, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1350
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:251
#define heurInitsolOptcumulative
#define heurExitsolOptcumulative
#define SCIP_CALL(x)
Definition: def.h:364
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip_probing.c:216
Definition: grphload.c:88
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip_prob.c:2426
#define HEUR_MAXDEPTH
#define HEUR_NAME
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:298
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:130
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:638
#define SCIP_Bool
Definition: def.h:70
#define HEUR_DISPCHAR
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:571
SCIP_VAR ** SCIPgetOrigVars(SCIP *scip)
Definition: scip_prob.c:2399
unsigned int * keys
SCIP_Real ** solvals
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17718
#define HEUR_DESC
heuristic for cumulative scheduling with optional activities
#define heurExitOptcumulative
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17728
#define heurInitOptcumulative
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:110
SCIP_VAR * a
Definition: circlepacking.c:57
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)
Definition: scip_param.c:74
#define SCIP_Real
Definition: def.h:163
SCIP_Bool * feasibles
static SCIP_DECL_HEURCOPY(heurCopyOptcumulative)
#define SCIP_Longint
Definition: def.h:148
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)
Definition: scip_param.c:102
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:98
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:122
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
Definition: scip_mem.c:117
#define HEUR_FREQ
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)
Definition: scip_sol.c:3231
static SCIP_RETCODE applyOptcumulativeFixings(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Bool *infeasible)
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1436