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