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