Scippy

SCIP

Solving Constraint Integer Programs

reader_cmin.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-2019 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 scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file reader_cmin.c
17  * @brief cmin file reader
18  * @author Stefan Heinz
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <stdlib.h>
24 #include <assert.h>
25 #include <string.h>
26 #if defined(_WIN32) || defined(_WIN64)
27 #else
28 #include <strings.h>
29 #endif
30 #include <ctype.h>
31 
32 #include "scip/cons_linear.h"
33 #include "scip/cons_setppc.h"
34 #include "scip/cons_knapsack.h"
35 
36 #include "cons_optcumulative.h"
37 #include "heur_optcumulative.h"
38 #include "reader_cmin.h"
39 
40 #define READER_NAME "cminreader"
41 #define READER_DESC "file reader for cmin file format"
42 #define READER_EXTENSION "cmin"
43 
44 #define DEFAULT_FILENAME "-" /**< name of the file including best known solutions */
45 #define DEFAULT_DUALREDUCTION TRUE /**< add locks to avoid dual reductions */
46 #define DEFAULT_MIP FALSE /**< create a MIP formulation */
47 #define DEFAULT_INITIAL TRUE /**< should model constraints be in initial LP? */
48 #define DEFAULT_CIP TRUE /**< create a CIP formulation */
49 #define DEFAULT_RELAXATION 3 /**< which relaxation should be added to the maseter (0: none; 1: single; 2: edge-finding; 3: energetic-reasoning */
50 
51 static const char delimchars[] = " \f\n\r\t\v";
52 
53 
54 /*
55  * Local methods
56  */
57 
58 /** CP reading data */
59 struct CminInput
60 {
63  char* token;
65  int linepos;
67 };
68 typedef struct CminInput CMININPUT;
69 
70 /** issues an error message and marks the LP data to have errors */
71 static
73  SCIP* scip, /**< SCIP data structure */
74  CMININPUT* cmininput, /**< CMIN reading data */
75  const char* msg /**< error message */
76  )
77 {
78  assert(cmininput != NULL);
79 
80  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "Syntax error in line %d: %s ('%s')\n",
81  cmininput->linenumber, msg, cmininput->token);
82 
83  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, " input: %s\n", cmininput->linebuf);
84 
85  cmininput->haserror = TRUE;
86 }
87 
88 /** gets the next line out of the file stream */
89 static
91  CMININPUT* cmininput /**< CMIN reading data */
92  )
93 {
94  char* pch;
95  assert( cmininput->haserror == FALSE );
96 
97  /* clear the line */
99 
100  if( SCIPfgets(cmininput->linebuf, (int) sizeof(cmininput->linebuf), cmininput->file) == NULL )
101  return FALSE;
102 
103  cmininput->linenumber++;
104  cmininput->linepos = 0;
105 
106  cmininput->linebuf[SCIP_MAXSTRLEN-1] = '\0';
107 
108  pch = strstr (cmininput->linebuf, "\n");
109  if( pch != NULL )
110  *pch = '\0';
111 
112  if (cmininput->linebuf[0] != '\0')
113  {
114  SCIPdebugMessage("input line %d: <%s>\n", cmininput->linenumber, cmininput->linebuf);
115  return TRUE;
116  }
117 
118  return FALSE;
119 }
120 
121 /** returns whether the given character is a token delimiter */
122 static
124  char c /**< input character */
125  )
126 {
127  return (c == '\0') || (strchr(delimchars, c) != NULL);
128 }
129 
130 /** reads the next token from the input file into the token buffer; returns whether a token was read */
131 static
133  CMININPUT* cmininput /**< CMIN reading data */
134  )
135 {
136  char* buf;
137  int tokenlen;
138 
139  assert(cmininput != NULL);
140 
141  /* skip delimiters */
142  buf = cmininput->linebuf;
143  while( isDelimChar(buf[cmininput->linepos]) )
144  {
145  if( buf[cmininput->linepos] == '\0' )
146  {
147  if( !getNextLine(cmininput) )
148  {
149  SCIPdebugMessage("(line %d) end of file\n", cmininput->linenumber);
150  return FALSE;
151  }
152  assert(cmininput->linepos == 0);
153  }
154  else
155  cmininput->linepos++;
156  }
157  assert(cmininput->linepos < SCIP_MAXSTRLEN);
158  assert(!isDelimChar(buf[cmininput->linepos]));
159 
160  /* read value token */
161  tokenlen = 0;
162  while( isdigit(buf[cmininput->linepos]) )
163  {
164  assert(tokenlen < SCIP_MAXSTRLEN);
165  assert(!isDelimChar(buf[cmininput->linepos]));
166  cmininput->token[tokenlen] = buf[cmininput->linepos];
167  tokenlen++;
168  cmininput->linepos++;
169  }
170 
171  assert(tokenlen < SCIP_MAXSTRLEN);
172  cmininput->token[tokenlen] = '\0';
173 
174  SCIPdebugMessage("(line %d) read token: '%s'\n", cmininput->linenumber, cmininput->token);
175 
176  return TRUE;
177 }
178 
179 /** method parses the best known solution for the total leftover out of the give file; if file does not exist or the
180  * problem is not listed the best known solution is set to -1 which means unknown
181  */
182 static
184  SCIP* scip, /**< SCIP data structure */
185  SCIP_Real* objval /**< pointer to store best known solution */
186  )
187 {
188  SCIP_FILE* file;
189  const char* probname;
190  SCIP_Bool found;
191  char* solufile;
192  char buffer[SCIP_MAXSTRLEN];
193  char* token;
194  char* saveptr;
195 
196  assert(scip != NULL);
197  assert(objval != NULL);
198 
199  /* get solution file */
200  SCIP_CALL( SCIPgetStringParam(scip, "reading/"READER_NAME"/filename", &solufile) );
201 
202  /* set objective value to unknown */
203  (*objval) = SCIPinfinity(scip);
204 
205  if( *solufile == '-')
206  return SCIP_OKAY;
207 
208  if( NULL == (file = SCIPfopen(solufile, "r")) )
209  {
210  SCIPwarningMessage(scip, "solution file <%s> does not exist\n", solufile);
211  return SCIP_OKAY;
212  }
213 
214  /* get problem name */
215  probname = SCIPgetProbName(scip);
216  found = FALSE;
217 
218  /* parse file line by line */
219  while( SCIPfgets(buffer, (int) sizeof(buffer), file) != NULL )
220  {
221  char status[SCIP_MAXSTRLEN];
222 
223  SCIPdebugMessage("parse line <%s>\n", buffer);
224 
225  /* solution status */
226  token = SCIPstrtok(buffer, " \n\t", &saveptr);
227  (void)SCIPsnprintf(status, SCIP_MAXSTRLEN, "%s", token);
228 
229  /* problem name */
230  token = SCIPstrtok(NULL, " \n\t", &saveptr);
231 
232  /* check if found the right line for the requested problem */
233  if( strncmp(token, probname, strlen(token)+1) == 0 )
234  {
235  SCIPdebugMessage("found problem <%s> in solution file <%s>\n", probname, solufile);
236 
237  if( strncmp(status, "=opt=", 5) == 0 )
238  {
239  /* objective value */
240  token = SCIPstrtok(NULL, " \n\t", &saveptr);
241 
242  (*objval) = atof(token);
243  found = TRUE;
244 
245  SCIPdebugMessage("best known solution is <%g>\n", *objval);
246  }
247 
248  break;
249  }
250  }
251 
252  SCIPfclose(file);
253 
254  if( !found )
255  return SCIP_INVALIDCALL;
256 
257  return SCIP_OKAY;
258 }
259 
260 #ifdef SCIP_DEBUG
261 /** display input data */
262 static
263 void displayInputData(
264  SCIP* scip, /**< SCIP data structure */
265  int** durations, /**< durations */
266  int** demands, /**< demands */
267  int** costs, /**< cost */
268  int* capacities, /**< machine capacities */
269  int* releasedates, /**< release dates */
270  int* deadlinedates, /**< deadline dates */
271  int njobs, /**< number of jobs */
272  int nmachines /**< number of machines */
273  )
274 {
275  int j;
276  int m;
277 
278  for( j = 0; j < njobs; ++j )
279  {
280  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Job %2d [%3d,%3d] ", j, releasedates[j], deadlinedates[j]);
281 
282  for( m = 0; m < nmachines; ++m )
283  {
284  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "(%2d,%2d)" , durations[m][j], demands[m][j]);
285  }
287  }
288 }
289 #endif
290 
291 /** initialize the sorted event point arrays */
292 static
294  SCIP* scip, /**< SCIP data structure */
295  int* releasedates, /**< release dates */
296  int* deadlinedates, /**< deadline dates */
297  int* starttimes, /**< array to store sorted start events */
298  int* endtimes, /**< array to store sorted end events */
299  int* startindices, /**< permutation with rspect to the start times */
300  int* endindices, /**< permutation with rspect to the end times */
301  int njobs /**< number of jobs */
302  )
303 {
304  int j;
305 
306  /* assign variables, start and endpoints to arrays */
307  for ( j = 0; j < njobs; ++j )
308  {
309  starttimes[j] = releasedates[j];
310  startindices[j] = j;
311 
312  endtimes[j] = deadlinedates[j];
313  endindices[j] = j;
314  }
315 
316  /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */
317  SCIPsortIntInt(starttimes, startindices, njobs);
318  SCIPsortIntInt(endtimes, endindices, njobs);
319 }
320 
321 /** computes the maximum energy for all variables which correspond to jobs which start between the given start time and
322  * end time
323  *
324  * @return Maximum energy for the given time window
325  */
326 static
328  int njobs, /**< number of jobs */
329  int* durations, /**< durations */
330  int* demands, /**< demands */
331  int* releasedates, /**< release dates */
332  int* deadlinedates, /**< deadline dates */
333  int starttime, /**< start time */
334  int endtime /**< end time */
335  )
336 {
337  SCIP_Longint maxenergy;
338  int v;
339 
340  assert(starttime < endtime);
341  maxenergy = 0LL;
342 
343  for( v = 0; v < njobs; ++v )
344  {
345  /* collect jobs which run between the start and end time */
346  if( deadlinedates[v] <= endtime && releasedates[v] >= starttime)
347  maxenergy += (SCIP_Longint)(durations[v] * demands[v]); /*lint !e647*/
348  }
349 
350  return maxenergy;
351 }
352 
353 /** remove row which have a tightness which is smaller or equal to the given one
354  *
355  * @return The number of remaining rows
356  */
357 static
359  SCIP_Longint* rowtightness, /**< array containing the tightness for the previously selected rows */
360  int* startidxs, /**< array containing for each row the index for the start event */
361  int nrows, /**< current number of rows */
362  SCIP_Longint tightness /**< tightness to use to detect redundant rows */
363  )
364 {
365  int keptrows;
366  int j;
367 
368  keptrows = 0;
369 
370  for( j = 0; j < nrows; ++j )
371  {
372  rowtightness[keptrows] = rowtightness[j];
373  startidxs[keptrows] = startidxs[j];
374 
375  /* only keep this row if the tightness is better as the (current) given one */
376  if( rowtightness[j] > tightness )
377  keptrows++;
378  }
379 
380  return keptrows;
381 }
382 
383 /** create interval relaxation for given sub-problem */
384 static
386  SCIP* scip, /**< SCIP data structure */
387  int relaxation, /**< a linear relaxation base on edge-finding idea or energetic-reasoning idea */
388  int resource, /**< resource id */
389  SCIP_VAR** vars, /**< assignment variables */
390  int* durations, /**< durations */
391  int* demands, /**< demands */
392  int capacity, /**< machine capacity */
393  int* releasedates, /**< release dates */
394  int* deadlinedates, /**< deadline dates */
395  int njobs /**< number of jobs */
396  )
397 {
398  SCIP_Longint** rowtightness;
399  int** startidxs;
400  int* nrows;
401  int* starttimes;
402  int* endtimes;
403  int* startindices;
404  int* endindices;
405  int starttime;
406  int endtime;
407  int i;
408  int j;
409 
410  int naddedcons;
411 
412  SCIP_CALL( SCIPallocBufferArray(scip, &starttimes, njobs) );
413  SCIP_CALL( SCIPallocBufferArray(scip, &startindices, njobs) );
414  SCIP_CALL( SCIPallocBufferArray(scip, &endtimes, njobs) );
415  SCIP_CALL( SCIPallocBufferArray(scip, &endindices, njobs) );
416 
417  SCIP_CALL( SCIPallocBufferArray(scip, &nrows, njobs) );
418  BMSclearMemoryArray(nrows, njobs);
419  SCIP_CALL( SCIPallocBufferArray(scip, &rowtightness, njobs) );
420  SCIP_CALL( SCIPallocBufferArray(scip, &startidxs, njobs) );
421  for( j = 0; j < njobs; ++j )
422  {
423  SCIP_CALL( SCIPallocBufferArray(scip, &rowtightness[j], njobs) ); /*lint !e866*/
424  SCIP_CALL( SCIPallocBufferArray(scip, &startidxs[j], njobs) ); /*lint !e866*/
425  }
426 
427  createSortedEventpoints(scip, releasedates, deadlinedates, starttimes, endtimes, startindices, endindices, njobs);
428 
429  starttime = -INT_MAX;
430 
431  /* check each startpoint of a job whether the capacity is kept or not */
432  for( j = 0; j < njobs; ++j )
433  {
434  SCIP_Longint besttightness;
435 
436  assert(starttime <= starttimes[j]);
437 
438  /* if we hit the same start time again we skip the loop */
439  if( starttime == starttimes[j])
440  continue;
441 
442  starttime = starttimes[j];
443  endtime = -INT_MAX;
444  besttightness = 0LL;
445 
446  for( i = 0; i < njobs; ++i )
447  {
448  SCIP_Longint energy;
449  SCIP_Longint maxenergy;
450  SCIP_Longint tightness;
451 
452  assert(endtime <= endtimes[i]);
453 
454  /* if we hit the same end time again we skip the loop */
455  if( endtime == endtimes[i] )
456  continue;
457 
458  endtime = endtimes[i];
459 
460  /* skip all end times which are smaller than the start time */
461  if( endtime <= starttime )
462  continue;
463 
464  maxenergy = computeMaxEnergy(njobs, durations, demands, releasedates, deadlinedates, starttime, endtime);
465 
466  energy = (endtime - starttime) * capacity; /*lint !e647*/
467  tightness = maxenergy - energy;
468 
469  /* check if the linear constraint is not trivially redundant */
470  if( tightness > besttightness )
471  {
472  besttightness = tightness;
473 
474  nrows[i] = removeRedundantRows(rowtightness[i], startidxs[i], nrows[i], tightness);
475 
476  /* add row information */
477  rowtightness[i][nrows[i]] = tightness;
478  startidxs[i][nrows[i]] = j;
479  nrows[i]++;
480  }
481  }
482  }
483 
484  naddedcons = 0;
485 
486  for( j = njobs-1; j >= 0; --j )
487  {
488  for( i = 0; i < nrows[j]; ++i )
489  {
490  SCIP_CONS* cons;
491  SCIP_Longint energy;
492  char name[SCIP_MAXSTRLEN];
493  int v;
494 
495  starttime = starttimes[startidxs[j][i]];
496  endtime = endtimes[j];
497 
498  energy = (endtime - starttime) * capacity; /*lint !e647*/
499 
500  SCIPdebugMessage("create linear relaxation for time interval [%d,%d] <= %"SCIP_LONGINT_FORMAT" (tightness %"SCIP_LONGINT_FORMAT")\n",
501  starttime, endtime, energy, rowtightness[j][i]);
502 
503  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "relax_%d_start_%d_end_%d", resource, starttime, endtime);
504  SCIP_CALL( SCIPcreateConsBasicKnapsack(scip, &cons, name, 0, NULL, NULL, energy) );
505 
506  for( v = 0; v < njobs; ++v)
507  {
508  int overlap;
509  int duration;
510 
511  duration = durations[v];
512  overlap = MIN(endtime - starttime, duration);
513  assert(overlap > 0);
514  overlap = MIN3(overlap, releasedates[v] + duration - starttime, endtime - deadlinedates[v] + duration);
515 
516  /* check for edge-finding idea */
517  if( relaxation == 2 && releasedates[v] >= starttime && deadlinedates[v] <= endtime )
518  {
519  assert(duration == overlap);
520  SCIP_CALL( SCIPaddCoefKnapsack(scip, cons, vars[v], (SCIP_Longint)(duration * demands[v])) ); /*lint !e647*/
521  }
522  else if( relaxation == 3 && overlap > 0 )
523  {
524  assert(overlap <= duration);
525  SCIP_CALL( SCIPaddCoefKnapsack(scip, cons, vars[v], (SCIP_Longint)(overlap * demands[v])) ); /*lint !e647*/
526  }
527  }
528 
529  SCIP_CALL( SCIPaddCons(scip, cons) );
530  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
531  naddedcons++;
532  }
533  }
534 
535  SCIPinfoMessage(scip, NULL, "add %d constraint as relaxation\n", naddedcons);
536 
537  /* free buffers */
538  for( j = njobs-1; j >= 0; --j )
539  {
540  SCIPfreeBufferArray(scip, &startidxs[j]);
541  SCIPfreeBufferArray(scip, &rowtightness[j]);
542  }
543  SCIPfreeBufferArray(scip, &startidxs);
544  SCIPfreeBufferArray(scip, &rowtightness);
545  SCIPfreeBufferArray(scip, &nrows);
546 
547  SCIPfreeBufferArray(scip, &endindices);
548  SCIPfreeBufferArray(scip, &endtimes);
549  SCIPfreeBufferArray(scip, &startindices);
550  SCIPfreeBufferArray(scip, &starttimes);
551 
552  return SCIP_OKAY;
553 }
554 
555 /** create MIP formulation and CP constraints */
556 static
558  SCIP* scip, /**< SCIP data structure */
559  int** durations, /**< durations */
560  int** demands, /**< demands */
561  int** costs, /**< cost */
562  int* capacities, /**< machine capacities */
563  int* releasedates, /**< release dates */
564  int* deadlinedates, /**< deadline dates */
565  int njobs, /**< number of jobs */
566  int nmachines /**< number of machines */
567  )
568 {
569  SCIP_VAR*** vars;
570  SCIP_CONS*** conss;
571  SCIP_CONS* cons;
572 
573  char name[SCIP_MAXSTRLEN];
574 
575  int relaxation;
576  int maxtime;
577  int i;
578  int j;
579  int t;
580 
581  SCIP_CALL( SCIPgetIntParam(scip, "reading/"READER_NAME"/relaxation", &relaxation) );
582 
583  /* compute maximum time */
584  maxtime = 0;
585  for( j = 0; j < njobs; ++j )
586  {
587  maxtime = MAX(maxtime, deadlinedates[j]);
588  }
589 
590  SCIP_CALL( SCIPallocBufferArray(scip, &conss, nmachines) );
591 
592  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nmachines) );
593 
594  /* create master problem */
595  for( i = 0; i < nmachines; ++i )
596  {
597  SCIP_CALL( SCIPallocBufferArray(scip, &vars[i], njobs) ); /*lint !e866*/
598 
599  for( j = 0; j < njobs; ++j )
600  {
601  SCIP_VAR* var;
602  SCIP_Real objval;
603  SCIP_Real ub;
604 
605  objval = (SCIP_Real)costs[i][j];
606 
607  /* construct variable name */
608  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "job_%d_machine_%d", j, i);
609 
610  if( releasedates[j] > deadlinedates[j] - durations[i][j] || demands[i][j] > capacities[i] )
611  ub = 0.0;
612  else
613  ub = 1.0;
614 
615  /* create binary variable */
616  SCIP_CALL( SCIPcreateVarBasic(scip, &var, name, 0.0, ub, objval, SCIP_VARTYPE_BINARY) );
617  vars[i][j] = var;
618 
619  /* add and release binary variable */
620  SCIP_CALL( SCIPaddVar(scip, var) );
621  SCIP_CALL( SCIPreleaseVar(scip, &var) );
622  }
623  }
624 
625  for( j = 0; j < njobs; ++j )
626  {
627  /* construct constraint name */
628  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "job_%d_to_one_machine", j);
629  SCIP_CALL( SCIPcreateConsBasicSetpart(scip, &cons, name, 0, NULL) );
630 
631  for( i = 0; i < nmachines; ++i )
632  {
633  SCIP_CALL( SCIPaddCoefSetppc(scip, cons, vars[i][j]) );
634  }
635 
636  SCIP_CALL( SCIPaddCons(scip, cons) );
637  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
638  }
639 
640  /* create for each machines and time point a knapsack constraint */
641  for( i = 0; i < nmachines; ++i )
642  {
643  SCIP_CALL( SCIPallocBufferArray(scip, &conss[i], maxtime) ); /*lint !e866*/
644 
645  for( t = 0; t < maxtime; ++t )
646  {
647  /* construct constraint name */
648  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "machines_%d_time_%d", i, t);
649 
650  SCIP_CALL( SCIPcreateConsBasicKnapsack(scip, &cons, name, 0, NULL, NULL, (SCIP_Longint)capacities[i]) );
651  SCIP_CALL( SCIPaddCons(scip, cons) );
652 
653  conss[i][t] = cons;
654 
655  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
656  }
657  }
658 
659  /* create for each job/machine/timepoint a binary variables */
660  for( j = 0; j < njobs; ++j )
661  {
662  int est;
663 
664  est = releasedates[j];
665 
666  for( i = 0; i < nmachines; ++i )
667  {
668  int lst;
669 
670  lst = deadlinedates[j] - durations[i][j];
671 
672  /* construct constraint name */
673  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "job_%d_machine_%d", j, i);
674 
675  SCIP_CALL( SCIPcreateConsBasicLinear(scip, &cons, name, 0, NULL, NULL, 0.0, 0.0) );
676  SCIP_CALL( SCIPaddCoefLinear(scip, cons, vars[i][j], -1.0) );
677 
678  for( t = est; t <= lst; ++t )
679  {
680  SCIP_VAR* var;
681  int h;
682 
683  /* construct variable name */
684  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "job_%d_machine_%d_time_%d", j, i, t);
685 
686  SCIP_CALL( SCIPcreateVarBasic(scip, &var, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY) );
687 
688  SCIP_CALL( SCIPaddVar(scip, var) );
689 
690  /* add variable to linear constraint */
691  SCIP_CALL( SCIPaddCoefLinear(scip, cons, var, 1.0) );
692 
693  for( h = t ; h < MIN(t + durations[i][j], maxtime); ++h )
694  {
695  SCIP_CALL( SCIPaddCoefKnapsack(scip, conss[i][h], var, (SCIP_Longint)demands[i][j] ) );
696  }
697 
698  SCIP_CALL( SCIPreleaseVar(scip, &var) );
699  }
700 
701  SCIP_CALL( SCIPaddCons(scip, cons) );
702  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
703  }
704  }
705 
706  /* free constraint buffers */
707  for( i = nmachines - 1; i >= 0; --i )
708  {
709  SCIPfreeBufferArray(scip, &conss[i]);
710  }
711  SCIPfreeBufferArray(scip, &conss);
712 
713  if( relaxation == 1 )
714  {
715  /* create for each optimal resource a singe constraint relaxation */
716  for( i = 0; i < nmachines; ++i )
717  {
718  SCIP_Longint capacity;
719  int est;
720  int lct;
721 
722  est = INT_MAX;
723  lct = INT_MIN;
724 
725  /* compute earliest start end latest completion time */
726  for( j = 0; j < njobs; ++j )
727  {
728  if( demands[i][j] > 0 )
729  {
730  est = MIN(est, releasedates[j]);
731  lct = MAX(lct, deadlinedates[j]);
732  }
733  }
734 
735  /* construct constraint name */
736  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "relax_%d", i);
737 
738  capacity = capacities[i] * (lct - est); /*lint !e647*/
739 
740  SCIP_CALL( SCIPcreateConsBasicKnapsack(scip, &cons, name, 0, NULL, NULL, capacity) );
741 
742  for( j = 0; j < njobs; ++j )
743  {
744  if( demands[i][j] > 0 )
745  {
746  SCIP_CALL( SCIPaddCoefKnapsack(scip, cons, vars[i][j], (SCIP_Longint)(durations[i][j] * demands[i][j]) ) ); /*lint !e647*/
747  }
748  }
749 
750  /* add the constraint to the problem and release it (locally) */
751  SCIP_CALL( SCIPaddCons(scip, cons) );
752  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
753  }
754  }
755  else if( relaxation >= 2 )
756  {
757  /* create for each optimal resource a singe constraint relaxation */
758  for( i = 0; i < nmachines; ++i )
759  {
760  SCIP_CALL( createIntervalRelaxation(scip, relaxation, i, vars[i], durations[i], demands[i], capacities[i], releasedates, deadlinedates, njobs) );
761  }
762  }
763 
764  for( i = nmachines-1; i >= 0; --i )
765  {
766  SCIPfreeBufferArray(scip, &vars[i]);
767  }
768  SCIPfreeBufferArray(scip, &vars);
769 
770  return SCIP_OKAY;
771 }
772 
773 /** create MIP formulation */
774 static
776  SCIP* scip, /**< SCIP data structure */
777  int** durations, /**< durations */
778  int** demands, /**< demands */
779  int** costs, /**< cost */
780  int* capacities, /**< machine capacities */
781  int* releasedates, /**< release dates */
782  int* deadlinedates, /**< deadline dates */
783  int njobs, /**< number of jobs */
784  int nmachines /**< number of machines */
785  )
786 {
787  SCIP_CONS*** conss;
788  SCIP_CONS* cons;
789  SCIP_VAR*** binvars;
790  SCIP_VAR*** vars;
791  SCIP_VAR* var;
792  int* nnvars;
793  int** localdemands;
794  int** localdurations;
795 
796  char name[SCIP_MAXSTRLEN];
797 
798  int maxtime;
799  int i;
800  int j;
801  int t;
802 
803  /* compute maximum time */
804  maxtime = 0;
805  for( j = 0; j < njobs; ++j )
806  {
807  maxtime = MAX(maxtime, deadlinedates[j]);
808  }
809 
810  SCIP_CALL( SCIPallocBufferArray(scip, &conss, nmachines) );
811  SCIP_CALL( SCIPallocBufferArray(scip, &binvars, nmachines) );
812  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nmachines) );
813  SCIP_CALL( SCIPallocBufferArray(scip, &localdemands, nmachines) );
814  SCIP_CALL( SCIPallocBufferArray(scip, &localdurations, nmachines) );
815 
816  SCIP_CALL( SCIPallocBufferArray(scip, &nnvars, nmachines) );
817  BMSclearMemoryArray(nnvars, nmachines);
818 
819  /* create for each machines and time point a knapsack constraint */
820  for( i = 0; i < nmachines; ++i )
821  {
822  SCIP_CALL( SCIPallocBufferArray(scip, &conss[i], maxtime) ); /*lint !e866*/
823 
824  for( t = 0; t < maxtime; ++t )
825  {
826  /* construct constraint name */
827  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "machines_%d_time_%d", i, t);
828 
829  SCIP_CALL( SCIPcreateConsKnapsack(scip, &cons, name, 0, NULL, NULL, (SCIP_Longint)capacities[i],
831  SCIP_CALL( SCIPaddCons(scip, cons) );
832 
833  conss[i][t] = cons;
834 
835  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
836  }
837 
838  SCIP_CALL( SCIPallocBufferArray(scip, &binvars[i], njobs) ); /*lint !e866*/
839  SCIP_CALL( SCIPallocBufferArray(scip, &vars[i], njobs) ); /*lint !e866*/
840  SCIP_CALL( SCIPallocBufferArray(scip, &localdemands[i], njobs) ); /*lint !e866*/
841  SCIP_CALL( SCIPallocBufferArray(scip, &localdurations[i], njobs) ); /*lint !e866*/
842  }
843 
844  for( j = 0; j < njobs; ++j )
845  {
846  SCIP_CONS* maccons;
847  int est;
848 
849  est = releasedates[j];
850 
851  /* construct constraint name */
852  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "job_%d", j);
853 
854  SCIP_CALL( SCIPcreateConsSetpart(scip, &cons, name, 0, NULL,
856 
857  for( i = 0; i < nmachines; ++i )
858  {
859  SCIP_CONS* lincons;
860  int lst;
861  int idx;
862 
863  lst = deadlinedates[j] - durations[i][j];
864 
865  if( est > lst )
866  continue;
867 
868  idx = nnvars[i];
869  nnvars[i]++;
870 
871  /* construct constraint name */
872  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "job_%d_machine_%d", j, i);
873 
874  SCIP_CALL( SCIPcreateConsSetpart(scip, &maccons, name, 0, NULL,
876 
877  /* construct variable name */
878  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "job_%d_choose_%d", j, i);
879 
880  SCIP_CALL( SCIPcreateVar(scip, &var, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY,
881  TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
882  SCIP_CALL( SCIPaddVar(scip, var) );
883  binvars[i][idx] = var;
884  SCIP_CALL( SCIPreleaseVar(scip, &var) );
885 
886  SCIP_CALL( SCIPgetNegatedVar(scip, binvars[i][idx], &var) );
887 
888  SCIP_CALL( SCIPaddCoefSetppc(scip, maccons, var) );
889 
890  /* add variable to set partitioning constraint */
891  SCIP_CALL( SCIPaddCoefSetppc(scip, cons, binvars[i][idx]) );
892 
893  /* construct variable name */
894  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "job_%d_starts_%d", idx, i);
895 
896  SCIP_CALL( SCIPcreateVar(scip, &var, name, 0.0, (SCIP_Real)lst, 0.0, SCIP_VARTYPE_IMPLINT,
897  TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
898 
899  SCIP_CALL( SCIPaddVar(scip, var) );
900  vars[i][idx] = var;
901 
902  SCIP_CALL( SCIPreleaseVar(scip, &var) );
903 
904  /* construct constraint name */
905  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "job_%d_machine_%d", idx, i);
906 
907  SCIP_CALL( SCIPcreateConsLinear(scip, &lincons, name, 0, NULL, NULL, 0.0, 0.0,
909 
910  SCIP_CALL( SCIPaddCoefLinear(scip, lincons, vars[i][idx], -1.0) );
911 
912  localdemands[i][idx] = demands[i][j];
913  localdurations[i][idx] = durations[i][j];
914 
915  for( t = est; t <= lst; ++t )
916  {
917  int h;
918 
919  /* construct variable name */
920  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "job_%d_machine_%d_time_%d", j, i, t);
921 
922  SCIP_CALL( SCIPcreateVar(scip, &var, name, 0.0, 1.0, (SCIP_Real)costs[i][j], SCIP_VARTYPE_BINARY,
923  TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
924 
925  SCIP_CALL( SCIPaddVar(scip, var) );
926 
927  /* add variable to linear linking constraint */
928  SCIP_CALL( SCIPaddCoefLinear(scip, lincons, var, (SCIP_Real)t) );
929 
930  /* add variable to linear linking constraint */
931  SCIP_CALL( SCIPaddCoefSetppc(scip, maccons, var) );
932 
933  for( h = t ; h < MIN(t + durations[i][j], maxtime); ++h )
934  {
935  SCIP_CALL( SCIPaddCoefKnapsack(scip, conss[i][h], var, (SCIP_Longint)demands[i][j] ) );
936  }
937 
938  SCIP_CALL( SCIPreleaseVar(scip, &var) );
939  }
940 
941  SCIP_CALL( SCIPaddCons(scip, lincons) );
942  SCIP_CALL( SCIPreleaseCons(scip, &lincons) );
943 
944  SCIP_CALL( SCIPaddCons(scip, maccons) );
945  SCIP_CALL( SCIPreleaseCons(scip, &maccons) );
946  }
947 
948 
949  SCIP_CALL( SCIPaddCons(scip, cons) );
950  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
951  }
952 
953  /* create CP constraints */
954 
955  for( i = 0; i < nmachines; ++i )
956  {
957  /* construct constraint name */
958  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "machine_%d", i);
959 
960  /* create machine choice constraint */
961  SCIP_CALL( SCIPcreateConsOptcumulative(scip, &cons, name, nnvars[i], vars[i], binvars[i], localdurations[i], localdemands[i], capacities[i],
963  SCIP_CALL( SCIPaddCons(scip, cons) );
964  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
965  }
966 
967 
968  for( i = nmachines - 1; i >= 0; --i )
969  {
970  SCIPfreeBufferArray(scip, &localdurations[i]);
971  SCIPfreeBufferArray(scip, &localdemands[i]);
972  SCIPfreeBufferArray(scip, &vars[i]);
973  SCIPfreeBufferArray(scip, &binvars[i]);
974  SCIPfreeBufferArray(scip, &conss[i]);
975  }
976 
977  SCIPfreeBufferArray(scip, &localdemands);
978  SCIPfreeBufferArray(scip, &localdurations);
979  SCIPfreeBufferArray(scip, &nnvars);
980  SCIPfreeBufferArray(scip, &vars);
981  SCIPfreeBufferArray(scip, &binvars);
982  SCIPfreeBufferArray(scip, &conss);
983 
984  return SCIP_OKAY;
985 }
986 
987 /** create CIP formulation */
988 static
990  SCIP* scip, /**< SCIP data structure */
991  int** durations, /**< durations */
992  int** demands, /**< demands */
993  int** costs, /**< cost */
994  int* capacities, /**< machine capacities */
995  int* releasedates, /**< release dates */
996  int* deadlinedates, /**< deadline dates */
997  int njobs, /**< number of jobs */
998  int nmachines /**< number of machines */
999  )
1000 {
1001  SCIP_CONS** conss;
1002  SCIP_CONS* cons;
1003  SCIP_VAR*** vars;
1004  SCIP_VAR*** binvars;
1005  SCIP_VAR* var;
1006  int* machines;
1007 
1008  char name[SCIP_MAXSTRLEN];
1009 
1010  SCIP_Real objval;
1011  SCIP_Bool dualreduction;
1012 
1013  int relaxation;
1014  int i;
1015  int j;
1016 
1017  SCIP_CALL( SCIPgetIntParam(scip, "reading/"READER_NAME"/relaxation", &relaxation) );
1018  SCIP_CALL( SCIPgetBoolParam(scip, "reading/"READER_NAME"/dualreduction", &dualreduction) );
1019 
1020  SCIP_CALL( SCIPallocBufferArray(scip, &conss, njobs) );
1021 
1022  /* create for each job a set partitioning constraint */
1023  for( j = 0; j < njobs; ++j )
1024  {
1025  /* construct constraint name */
1026  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "job_%d", j);
1027 
1028  SCIP_CALL( SCIPcreateConsBasicSetpart(scip, &cons, name, 0, NULL) );
1029  SCIP_CALL( SCIPaddCons(scip, cons) );
1030  conss[j] = cons;
1031  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
1032  }
1033 
1034  SCIP_CALL( SCIPallocBufferArray(scip, &binvars, nmachines) );
1035  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nmachines) );
1036  SCIP_CALL( SCIPallocBufferArray(scip, &machines, nmachines) );
1037 
1038  for( i = 0; i < nmachines; ++i )
1039  {
1040  int nvars;
1041 
1042  nvars = 0;
1043 
1044  SCIP_CALL( SCIPallocBufferArray(scip, &binvars[i], njobs) ); /*lint !e866*/
1045  SCIP_CALL( SCIPallocBufferArray(scip, &vars[i], njobs) ); /*lint !e866*/
1046 
1047  BMSclearMemoryArray(binvars[i], njobs); /*lint !e866*/
1048  BMSclearMemoryArray(vars[i], njobs); /*lint !e866*/
1049 
1050  for( j = 0; j < njobs; ++j )
1051  {
1052  /* check if job is scheduleable on that machine */
1053  if(releasedates[j] + durations[i][j] > deadlinedates[j] || demands[i][j] > capacities[i] )
1054  continue;
1055 
1056  /* construct variable name */
1057  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "job_%d_choose_%d", j, i);
1058 
1059  SCIP_CALL( SCIPcreateVarBasic(scip, &var, name, 0.0, 1.0, (SCIP_Real)costs[i][j], SCIP_VARTYPE_BINARY) );
1060  SCIP_CALL( SCIPaddVar(scip, var) );
1061  binvars[i][nvars] = var;
1062  SCIP_CALL( SCIPreleaseVar(scip, &var) );
1063 
1064  /* construct variable name */
1065  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "job_%d_starts_%d", j, i);
1066 
1067  SCIP_CALL( SCIPcreateVarBasic(scip, &var, name, (SCIP_Real)releasedates[j], (SCIP_Real)(deadlinedates[j] - durations[i][j]), 0.0, SCIP_VARTYPE_INTEGER) );
1068  SCIP_CALL( SCIPaddVar(scip, var) );
1069  vars[i][nvars] = var;
1070  SCIP_CALL( SCIPreleaseVar(scip, &var) );
1071 
1072  if( !dualreduction )
1073  {
1074  SCIP_CALL( SCIPaddVarLocksType(scip, binvars[i][nvars], SCIP_LOCKTYPE_MODEL, 1, 1) );
1075  SCIP_CALL( SCIPaddVarLocksType(scip, vars[i][nvars], SCIP_LOCKTYPE_MODEL, 1, 1) );
1076  }
1077 
1078  /* add choice variable to set partitioning constraint */
1079  SCIP_CALL( SCIPaddCoefSetppc(scip, conss[j], binvars[i][nvars]) );
1080 
1081  demands[i][nvars] = demands[i][j];
1082  durations[i][nvars] = durations[i][j];
1083 
1084  nvars++;
1085  }
1086 
1087  machines[i] = nvars;
1088 
1089  if( nvars > 0 )
1090  {
1091  SCIP_Bool initial;
1092  SCIP_Bool separate;
1093 
1094  if( relaxation == 0 )
1095  {
1096  initial = FALSE;
1097  separate = FALSE;
1098  }
1099  else
1100  {
1101  initial = TRUE;
1102  separate = TRUE;
1103  }
1104 
1105  /* construct constraint name */
1106  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "machine_%d", i);
1107 
1108  /* create machine choice constraint */
1109  SCIP_CALL( SCIPcreateConsOptcumulative(scip, &cons, name, nvars, vars[i], binvars[i], durations[i], demands[i], capacities[i],
1110  initial, separate, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
1111  SCIP_CALL( SCIPaddCons(scip, cons) );
1112  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
1113  }
1114  }
1115 
1116  SCIP_CALL( SCIPinitHeurOptcumulative(scip, nmachines, njobs, machines, binvars, vars, durations, demands, capacities) );
1117 
1118  /* check for a given total leftover */
1119  SCIP_CALL( findBestObjectiveValue(scip, &objval) );
1120 
1121  SCIP_CALL( SCIPsetObjlimit(scip, objval) );
1122 
1123  /* free all buffers */
1124  for( i = 0; i < nmachines; ++i )
1125  {
1126  SCIPfreeBufferArray(scip, &vars[i]);
1127  SCIPfreeBufferArray(scip, &binvars[i]);
1128  }
1129  SCIPfreeBufferArray(scip, &machines );
1130  SCIPfreeBufferArray(scip, &vars );
1131  SCIPfreeBufferArray(scip, &binvars);
1132  SCIPfreeBufferArray(scip, &conss );
1133 
1134  return SCIP_OKAY;
1135 }
1136 
1137 /** read given file and create corresponding problem */
1138 static
1140  SCIP* scip, /**< SCIP data structure */
1141  CMININPUT* cmininput, /**< CMIN reading data */
1142  const char* filename /**< file name */
1143  )
1144 {
1145  int** durations;
1146  int** demands;
1147  int** costs;
1148  int* capacities;
1149  int* releasedates;
1150  int* deadlinedates;
1151 
1152  int njobs;
1153  int nmachines;
1154 
1155  int i;
1156  int j;
1157 
1158  /* read the number of jobs */
1159  if( !getNextToken(cmininput) )
1160  {
1161  syntaxError(scip, cmininput, "missing number if jobs\n");
1162  return SCIP_OKAY;
1163  }
1164 
1165  njobs = atoi(cmininput->token);
1166 
1167  /* read the number of machines */
1168  if( !getNextToken(cmininput) )
1169  {
1170  syntaxError(scip, cmininput, "missing number of machines");
1171  return SCIP_OKAY;
1172  }
1173 
1174  nmachines = atoi(cmininput->token);
1175 
1176  SCIPdebugMessage("njobs <%d> nmachines <%d>\n", njobs, nmachines);
1177 
1178  /* allocate all neccessary memory */
1179  SCIP_CALL( SCIPallocBufferArray(scip, &durations, nmachines) );
1180  SCIP_CALL( SCIPallocBufferArray(scip, &demands, nmachines) );
1181  SCIP_CALL( SCIPallocBufferArray(scip, &costs, nmachines) );
1182  for( i = 0; i < nmachines; ++i )
1183  {
1184  SCIP_CALL( SCIPallocBufferArray(scip, &durations[i], njobs) ); /*lint !e866*/
1185  SCIP_CALL( SCIPallocBufferArray(scip, &demands[i], njobs) ); /*lint !e866*/
1186  SCIP_CALL( SCIPallocBufferArray(scip, &costs[i], njobs) ); /*lint !e866*/
1187  }
1188  SCIP_CALL( SCIPallocBufferArray(scip, &capacities, nmachines) );
1189  SCIP_CALL( SCIPallocBufferArray(scip, &releasedates, njobs) );
1190  SCIP_CALL( SCIPallocBufferArray(scip, &deadlinedates, njobs) );
1191 
1192  for( i = 0; i < nmachines && !cmininput->haserror; ++i )
1193  {
1194  for( j = 0; j < njobs; ++j )
1195  {
1196  /* get job duration */
1197  if( !getNextToken(cmininput) )
1198  {
1199  syntaxError(scip, cmininput, "missing job duration");
1200  break;
1201  }
1202  assert(cmininput->haserror == FALSE);
1203 
1204  durations[i][j] = atoi(cmininput->token);
1205 
1206  /* get demand */
1207  if( !getNextToken(cmininput) )
1208  {
1209  syntaxError(scip, cmininput, "missing job demand\n");
1210  break;
1211  }
1212  assert(cmininput->haserror == FALSE);
1213 
1214  demands[i][j] = atoi(cmininput->token);
1215 
1216  /* get job cost */
1217  if( !getNextToken(cmininput) )
1218  {
1219  syntaxError(scip, cmininput, "missing job cost\n");
1220  break;
1221  }
1222  assert(cmininput->haserror == FALSE);
1223 
1224  costs[i][j] = atoi(cmininput->token);
1225 
1226  SCIPdebugMessage("job %2d: duration %d, demand %d, cost %d\n", j, durations[i][j], demands[i][j], costs[i][j]);
1227  }
1228  }
1229 
1230  /* parse the machine capacities */
1231  for( i = 0; i < nmachines && !cmininput->haserror; ++i)
1232  {
1233  /* get capacity */
1234  if( !getNextToken(cmininput) )
1235  {
1236  syntaxError(scip, cmininput, "missing machine capacity\n");
1237  break;
1238  }
1239 
1240  capacities[i] = atoi(cmininput->token);
1241 
1242  SCIPdebugMessage("capaciy of machine %d is %d\n", i, capacities[i]);
1243  }
1244 
1245  /* get release and deadline dates */
1246  for( j = 0; j < njobs && !cmininput->haserror; ++j )
1247  {
1248 
1249  /* get release date */
1250  if( !getNextToken(cmininput) )
1251  {
1252  syntaxError(scip, cmininput, "missing release date\n");
1253  break;
1254  }
1255 
1256  releasedates[j] = atoi(cmininput->token);
1257 
1258  /* get deadline data */
1259  if( !getNextToken(cmininput) )
1260  {
1261  syntaxError(scip, cmininput, "missing deadline date\n");
1262  break;
1263  }
1264  deadlinedates[j] = atoi(cmininput->token);
1265 
1266  SCIPdebugMessage("job %2d: [%d,%d]\n", j, releasedates[j], deadlinedates[j]);
1267  }
1268 
1269  if( !cmininput->haserror )
1270  {
1271  SCIP_Bool mip;
1272  SCIP_Bool cip;
1273  char* probname;
1274  char* str;
1275 
1276  SCIPdebug( displayInputData(scip, durations, demands, costs, capacities, releasedates, deadlinedates, njobs, nmachines) );
1277 
1278  SCIP_CALL( SCIPgetBoolParam(scip, "reading/"READER_NAME"/mip", &mip) );
1279  SCIP_CALL( SCIPgetBoolParam(scip, "reading/"READER_NAME"/cip", &cip) );
1280 
1281  /* construct problem name */
1282  SCIP_CALL( SCIPduplicateBufferArray(scip, &str, filename, strlen(filename)+1) );
1283 
1284  SCIPsplitFilename(str, NULL, &probname, NULL, NULL);
1285 
1286  /* initialize problem data */
1287  SCIP_CALL( SCIPcreateProbBasic(scip, probname) );
1288 
1289  SCIPfreeBufferArray(scip, &str);
1290 
1291  if( mip && cip )
1292  {
1293  SCIP_CALL( createMipCpFormulation(scip, durations, demands, costs, capacities, releasedates, deadlinedates, njobs, nmachines) );
1294  }
1295  else if( mip )
1296  {
1297  SCIP_CALL( createMipFormulation(scip, durations, demands, costs, capacities, releasedates, deadlinedates, njobs, nmachines) );
1298  }
1299  else if( cip )
1300  {
1301  SCIP_CALL( createCipFormulation(scip, durations, demands, costs, capacities, releasedates, deadlinedates, njobs, nmachines) );
1302  }
1303  }
1304 
1305  /* free all buffers in the reverse order since the buffers are handled by a stack */
1306  SCIPfreeBufferArray(scip, &deadlinedates);
1307  SCIPfreeBufferArray(scip, &releasedates);
1308  SCIPfreeBufferArray(scip, &capacities);
1309  for( i = nmachines - 1; i >= 0; --i )
1310  {
1311  SCIPfreeBufferArray(scip, &costs[i]);
1312  SCIPfreeBufferArray(scip, &demands[i]);
1313  SCIPfreeBufferArray(scip, &durations[i]);
1314  }
1315  SCIPfreeBufferArray(scip, &costs);
1316  SCIPfreeBufferArray(scip, &demands);
1317  SCIPfreeBufferArray(scip, &durations);
1318 
1319  return SCIP_OKAY;
1320 }
1321 
1322 
1323 /*
1324  * Callback methods of reader
1325  */
1326 
1327 
1328 /** problem reading method of reader */
1329 static
1330 SCIP_DECL_READERREAD(readerReadCmin)
1331 { /*lint --e{715}*/
1332 
1333  CMININPUT cmininput;
1334  SCIP_FILE* file;
1335 
1336  /* try to open the file */
1337  if( NULL == (file = SCIPfopen(filename, "r")) )
1338  {
1339  perror(filename);
1340  return SCIP_NOFILE;
1341  }
1342 
1343  cmininput.linebuf[0] = '\0';
1344  cmininput.linenumber = 0;
1345  cmininput.linepos = 0;
1346  cmininput.haserror = FALSE;
1347  cmininput.file = file;
1348 
1349  SCIP_CALL( SCIPallocBufferArray(scip, &cmininput.token, SCIP_MAXSTRLEN) );
1350  cmininput.token[0] = '\0';
1351 
1352  SCIP_CALL( readFile(scip, &cmininput, filename) );
1353 
1354  SCIPfreeBufferArray(scip, &cmininput.token);
1355 
1356  /* close file */
1357  (void) SCIPfclose(file);
1358 
1359  if( cmininput.haserror )
1360  return SCIP_READERROR;
1361 
1362  *result = SCIP_SUCCESS;
1363 
1364  return SCIP_OKAY;
1365 }
1366 
1367 /*
1368  * reader specific interface methods
1369  */
1370 
1371 /** includes the cp file reader in SCIP */
1373  SCIP* scip /**< SCIP data structure */
1374  )
1375 {
1376  SCIP_READER* reader;
1377 
1378  /* include cp reader */
1380  SCIP_CALL( SCIPsetReaderRead(scip, reader, readerReadCmin) );
1381 
1383  "reading/"READER_NAME"/filename", "name of the file including best known solutions",
1385 
1387  "reading/"READER_NAME"/dualreduction", "add locks to avoid dual reductions?",
1389 
1391  "reading/"READER_NAME"/mip", "create a MIP formulation?",
1392  NULL, FALSE, DEFAULT_MIP, NULL, NULL) );
1393 
1395  "reading/"READER_NAME"/initial", "should model constraints be in initial LP?",
1397 
1399  "reading/"READER_NAME"/cip", "create a CIP formulation?",
1400  NULL, FALSE, DEFAULT_CIP, NULL, NULL) );
1401 
1402  SCIP_CALL( SCIPaddIntParam(scip,
1403  "reading/"READER_NAME"/relaxation", "which relaxation should be added to the maseter (0: none; 1: single; 2: edge-finding; 3: energetic-reasoning",
1404  NULL, FALSE, DEFAULT_RELAXATION, 0, 3, NULL, NULL) );
1405 
1406  return SCIP_OKAY;
1407 }
SCIP_RETCODE SCIPgetStringParam(SCIP *scip, const char *name, char **value)
Definition: scip_param.c:417
static SCIP_RETCODE createIntervalRelaxation(SCIP *scip, int relaxation, int resource, SCIP_VAR **vars, int *durations, int *demands, int capacity, int *releasedates, int *deadlinedates, int njobs)
Definition: reader_cmin.c:385
#define NULL
Definition: def.h:246
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_setppc.c:9229
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
cmin file reader
SCIP_RETCODE SCIPincludeReaderCmin(SCIP *scip)
Definition: reader_cmin.c:1372
#define DEFAULT_RELAXATION
Definition: reader_cmin.c:49
int linenumber
Definition: reader_cmin.c:64
#define DEFAULT_INITIAL
Definition: reader_cmin.c:47
#define DEFAULT_FILENAME
Definition: reader_cmin.c:44
#define SCIP_MAXSTRLEN
Definition: def.h:267
void SCIPsplitFilename(char *filename, char **path, char **name, char **extension, char **compression)
Definition: misc.c:10472
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1251
#define DEFAULT_MIP
Definition: reader_cmin.c:46
static SCIP_RETCODE readFile(SCIP *scip, CMININPUT *cmininput, const char *filename)
Definition: reader_cmin.c:1139
static void createSortedEventpoints(SCIP *scip, int *releasedates, int *deadlinedates, int *starttimes, int *endtimes, int *startindices, int *endindices, int njobs)
Definition: reader_cmin.c:293
SCIP_Bool haserror
Definition: reader_cmin.c:66
#define FALSE
Definition: def.h:72
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10253
#define TRUE
Definition: def.h:71
#define SCIPdebug(x)
Definition: pub_message.h:74
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition: scip_var.c:184
static const char delimchars[]
Definition: reader_cmin.c:51
SCIP_RETCODE SCIPaddStringParam(SCIP *scip, const char *name, const char *desc, char **valueptr, SCIP_Bool isadvanced, const char *defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:266
#define READER_EXTENSION
Definition: reader_cmin.c:42
#define SCIPdebugMessage
Definition: pub_message.h:77
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:138
SCIP_FILE * file
Definition: reader_cmin.c:61
static SCIP_DECL_READERREAD(readerReadCmin)
Definition: reader_cmin.c:1330
static SCIP_RETCODE createMipFormulation(SCIP *scip, int **durations, int **demands, int **costs, int *capacities, int *releasedates, int *deadlinedates, int njobs, int nmachines)
Definition: reader_cmin.c:557
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
SCIP_RETCODE SCIPaddCoefKnapsack(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Longint weight)
Constraint handler for the set partitioning / packing / covering constraints .
static int removeRedundantRows(SCIP_Longint *rowtightness, int *startidxs, int nrows, SCIP_Longint tightness)
Definition: reader_cmin.c:358
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:203
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:155
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:279
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition: scip_prob.c:223
char * token
Definition: reader_cmin.c:63
#define MIN3(x, y, z)
Definition: def.h:221
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1123
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4198
SCIP_RETCODE SCIPinitHeurOptcumulative(SCIP *scip, int nmachines, int njobs, int *machines, SCIP_VAR ***binvars, SCIP_VAR ***vars, int **durations, int **demands, int *capacities)
static SCIP_Longint computeMaxEnergy(int njobs, int *durations, int *demands, int *releasedates, int *deadlinedates, int starttime, int endtime)
Definition: reader_cmin.c:327
SCIP_FILE * SCIPfopen(const char *path, const char *mode)
Definition: fileio.c:140
int linepos
Definition: reader_cmin.c:65
Constraint handler for knapsack constraints of the form , x binary and .
SCIP_RETCODE SCIPcreateConsOptcumulative(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_VAR **binvars, int *durations, int *demands, int capacity, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2822
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
struct SCIP_File SCIP_FILE
Definition: pub_fileio.h:34
char * SCIPfgets(char *s, int size, SCIP_FILE *stream)
Definition: fileio.c:187
static SCIP_Bool isDelimChar(char c)
Definition: reader_cmin.c:123
SCIP_RETCODE SCIPcreateConsSetpart(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_setppc.c:9058
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:322
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:341
SCIP_RETCODE SCIPcreateConsKnapsack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
#define SCIP_CALL(x)
Definition: def.h:358
SCIP_VAR * h
Definition: circlepacking.c:59
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:296
SCIP_RETCODE SCIPcreateConsBasicKnapsack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity)
static SCIP_Bool getNextLine(CMININPUT *cmininput)
Definition: reader_cmin.c:90
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
#define READER_DESC
Definition: reader_cmin.c:41
#define SCIP_Bool
Definition: def.h:69
SCIP_RETCODE SCIPincludeReaderBasic(SCIP *scip, SCIP_READER **readerptr, const char *name, const char *desc, const char *extension, SCIP_READERDATA *readerdata)
Definition: scip_reader.c:180
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip_prob.c:1478
#define MIN(x, y)
Definition: def.h:216
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
Definition: scip_var.c:104
Constraint handler for linear constraints in their most general form, .
heuristic for cumulative scheduling with optional activities
char linebuf[SCIP_MAXSTRLEN]
Definition: reader_cmin.c:62
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
#define SCIP_LONGINT_FORMAT
Definition: def.h:149
#define MAX(x, y)
Definition: def.h:215
static SCIP_RETCODE createCipFormulation(SCIP *scip, int **durations, int **demands, int **costs, int *capacities, int *releasedates, int *deadlinedates, int njobs, int nmachines)
Definition: reader_cmin.c:989
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1724
static SCIP_RETCODE createMipCpFormulation(SCIP *scip, int **durations, int **demands, int **costs, int *capacities, int *releasedates, int *deadlinedates, int njobs, int nmachines)
Definition: reader_cmin.c:775
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1187
static void syntaxError(SCIP *scip, CMININPUT *cmininput, const char *msg)
Definition: reader_cmin.c:72
#define DEFAULT_CIP
Definition: reader_cmin.c:48
#define SCIP_Real
Definition: def.h:157
SCIP_RETCODE SCIPsetReaderRead(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERREAD((*readerread)))
Definition: scip_reader.c:266
#define SCIP_Longint
Definition: def.h:142
#define DEFAULT_DUALREDUCTION
Definition: reader_cmin.c:45
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:119
static SCIP_RETCODE findBestObjectiveValue(SCIP *scip, SCIP_Real *objval)
Definition: reader_cmin.c:183
SCIP_RETCODE SCIPcreateConsBasicSetpart(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars)
Definition: cons_setppc.c:9098
int SCIPfclose(SCIP_FILE *fp)
Definition: fileio.c:219
static SCIP_Bool getNextToken(CMININPUT *cmininput)
Definition: reader_cmin.c:132
char * SCIPstrtok(char *s, const char *delim, char **ptrptr)
Definition: misc.c:10211
#define READER_NAME
Definition: reader_cmin.c:40
constraint handler for cumulative constraints with optional activities
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip_var.c:1530
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:129