Scippy

SCIP

Solving Constraint Integer Programs

reader_scflp.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_scflp.c
17  * @brief SCFLP reader file reader
18  * @author Stephen J. Maher
19  *
20  * This file implements the reader/parser used to read the CAP input data and builds a SCFLP instance. For more details
21  * see \ref SCFLP_READER.
22  *
23  * @page SCFLP_READER Parsing the input format
24  *
25  * In the <code>data</code> directory you find a few data files which contain each one CAP problem. These data
26  * files have the following structure:
27  * - The first line specifies the number of facilities (n) and the number of customers (m).
28  * - The next n lines specifies for each facility the setup cost and propduction capacity.
29  * - The following lines state the parameters for each of the customers.
30  * - First, the demand of customer is given.
31  * - The next set of lines states the transportation cost from each facility to the customer. Each line contains 7
32  * facilities, so there are ceil(n/7) lines for the transportation costs for each customer.
33  *
34  * For parsing that data, we implemented a reader plugin for \SCIP. A reader has several callback methods and at least
35  * one interface methods (the one including the reader into \SCIP). For our purpose we only implemented the \ref
36  * READERREAD callback and the interface method which adds the reader plugin to \SCIP.
37  *
38  * @section SCFLP_READERINCLUDE The SCIPincludeReaderScflp() interface method
39  *
40  * The interface method <code>SCIPincludeReaderScflp()</code> is called to add the reader plugin to \SCIP (see
41  * cmain.c). This means \SCIP gets informed that this reader is available for reading input files. Therefore, the
42  * function <code>SCIPincludeReader()</code> is called within this method which passes all necessary information of the
43  * reader to SCIP. This information includes the name of the reader, a description, and the file extension for which the
44  * file reader is in charge. In our case we selected the file extension "cap". This means that all files which have
45  * this file extension are passed to our reader for parsing. Besides these information the call
46  * <code>SCIPincludeReader()</code> also passes for each callback of the reader a function pointers
47  * (some of them might be NULL pointers). These function
48  * pointers are used by \SCIP to run the reader. For more information about all available reader callbacks we refer to
49  * the \ref READER "How to add file readers" tutorial. In the remaining section
50  * we restrict ourself to the callback <code>READERREAD</code> which is the only one we implemented for the SCFLP
51  * example. All other callbacks are not required for this example.
52  *
53  * @section SCFLP_READERREAD The READERREAD callback method
54  *
55  * The READERREAD callback is in charge of parsing a file and creating the problem. To see the list of arguments this
56  * functions gets see the file type_reader.h in the source of \SCIP. The following arguments are of interest in our
57  * case. First of all the \SCIP pointer, the file name, and the SCIP_RESULT pointer. The \SCIP pointer gives us the
58  * current environment. The file name states the file which we should open and parse. Last but not least, the SCIP_RESULT
59  * pointer is required to tell \SCIP if the parsing process was successfully or
60  * not. Note that in type_reader.h you also find a list of allowable result values for the SCIP_RESULT pointer and the
61  * <code>SCIP_RETCODE</code> which is the return value of this function.
62  *
63  * In the READERREAD callback, the scenarios for the stochastic program are generated. A scenario represents a different
64  * realisation of demand for each customer. The scenarios are generated by sampling demands from a normal distribution
65  * with a mean given by the deterministic demand and the standard deviation sampled from a uniform distribution with the
66  * range [0.1*mean, 0.3*mean]. The number of scenarios can be set using a runtime parameter.
67  *
68  * @subsection SCFLP_PARSING Parsing the problem
69  *
70  * The file can be opened and parsed with your favorite methods. In this case we are using the functionality provided by
71  * \SCIP since this has some nice side effects. We are using the function SCIPfopen() which can besides standard
72  * files also handle files which are packed. To find all files related to the parsing of a file, we refer to the file pub_misc.h
73  * in the source of SCIP. Parsing the data out of the file is not that hard. Please look at the code and comments
74  * therein for more details.
75  *
76  * @subsection SCFLP_CREATING Creating the problem
77  *
78  * After parsing the file the final task for the reader is to create the problem. In our case, we pass the collected data
79  * to the \ref probdata_scflp.h "main problem data plugin". For this, we use the interface methods
80  * SCIPprobdataCreate() which is provided by the
81  * problem data plugin (see probdata_scflp.c). After that, the reader sets the result value for the SCIP_RESULT
82  * pointer to <code>SCIP_SUCCESS</code> and returns with a proper <code>SCIP_RETCODE</code>.
83  */
84 
85 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
86 
87 #include <assert.h>
88 #include <string.h>
89 #include <math.h>
90 #include <stdlib.h>
91 
92 #include "probdata_scflp.h"
93 #include "reader_scflp.h"
94 
95 /**@name Reader properties
96  *
97  * @{
98  */
99 
100 #define READER_NAME "scflpreader"
101 #define READER_DESC "file reader for CAP data format and creates a SCFLP instance"
102 #define READER_EXTENSION "cap"
103 
104 
105 #define DEFAULT_USEBENDERS FALSE
106 #define DEFAULT_NUMSCENARIOS 250
107 #define DEFAULT_RANDOMSEED 1
108 
109 #define MAXNCOSTS 7
110 
111 struct SCIP_ReaderData
112 {
113  SCIP_Bool usebenders; /**< should Benders' decomposition be used to solve the problem */
114  int nscenarios; /**< the number of scenarios */
115  int randomseed; /**< the random seed used to generate the scenarios */
116 };
117 
118 /**@} */
119 
120 /** generates a normally distributed random number */
121 static
123  SCIP_RANDNUMGEN* randomgen, /**< the random number generator */
124  SCIP_Real mean, /**< the mean of the normal distribution */
125  SCIP_Real stdDev, /**< the standard deviation of the normal distribution */
126  SCIP_Real* spare, /**< the spare value that has been collected */
127  SCIP_Bool* hasspare /**< whether a spare value exists */
128  )
129 {
130  SCIP_Real u;
131  SCIP_Real v;
132  SCIP_Real s;
133 
134  /* if a spare exists, then it is returned */
135  if( (*hasspare) )
136  {
137  (*hasspare) = FALSE;
138  return mean + stdDev * (*spare);
139  }
140 
141  (*hasspare) = TRUE;
142  do {
143  u = SCIPrandomGetReal(randomgen, 0.0, 1.0);
144  v = SCIPrandomGetReal(randomgen, 0.0, 1.0);
145  s = u * u + v * v;
146  }
147  while( (s >= 1.0) || (s == 0.0) );
148 
149  s = sqrt(-2.0 * log(s) / s);
150  (*spare) = v * s;
151 
152  return mean + stdDev * u * s;
153 }
154 
155 
156 /** creates the reader data */
157 static
159  SCIP* scip, /**< SCIP data structure */
160  SCIP_READERDATA** readerdata /**< pointer to store the reader data */
161  )
162 {
163  assert(scip != NULL);
164  assert(readerdata != NULL);
165 
166  SCIP_CALL( SCIPallocBlockMemory(scip, readerdata) );
167  (*readerdata)->usebenders = TRUE;
168 
169  return SCIP_OKAY;
170 }
171 
172 /** frees the reader data */
173 static
175  SCIP* scip, /**< SCIP data structure */
176  SCIP_READERDATA** readerdata /**< pointer to store the reader data */
177  )
178 {
179  assert(scip != NULL);
180  assert(readerdata != NULL);
181  assert(*readerdata != NULL);
182 
183  SCIPfreeBlockMemory(scip, readerdata);
184 
185  return SCIP_OKAY;
186 }
187 
188 
189 /**@name Callback methods
190  *
191  * @{
192  */
193 
194 /** destructor of reader to free user data (called when SCIP is exiting)*/
195 static
196 SCIP_DECL_READERFREE(readerFreeScflp)
197 {
198  SCIP_READERDATA* readerdata;
199 
200  assert(scip != NULL);
201  assert(reader != NULL);
202 
203  readerdata = SCIPreaderGetData(reader);
204 
205  SCIP_CALL( readerdataFree(scip, &readerdata) );
206 
207  return SCIP_OKAY;
208 }
209 
210 
211 /** problem reading method of reader */
212 static
213 SCIP_DECL_READERREAD(readerReadScflp)
214 { /*lint --e{715}*/
215  SCIP_READERDATA* readerdata;
216 
217  SCIP_RANDNUMGEN* randomgen;
218 
219  SCIP_FILE* file;
220  SCIP_Bool error;
221 
222  char name[SCIP_MAXSTRLEN];
223  char buffer[SCIP_MAXSTRLEN];
224  SCIP_Real* fixedcost;
225  SCIP_Real* capacity;
226  SCIP_Real* detdemands;
227  SCIP_Real** demands;
228  SCIP_Real** costs;
229  int nfacilities;
230  int ncustomers;
231  int nscenarios;
232 
233  SCIP_Real facilitycost;
234  SCIP_Real facilitycap;
235  SCIP_Real demand;
236  int facility;
237  int customer;
238  int ncostlines; /* this is the number of lines that have facility costs */
239 
240  int nread;
241  int lineno;
242  int i;
243  int j;
244 
245  readerdata = SCIPreaderGetData(reader);
246 
247  /* creating the random number generator */
248  SCIP_CALL( SCIPcreateRandom(scip, &randomgen, readerdata->randomseed, FALSE) );
249 
250  nscenarios = readerdata->nscenarios;
251 
252  *result = SCIP_DIDNOTRUN;
253 
254  /* open file */
255  file = SCIPfopen(filename, "r");
256  if( file == NULL )
257  {
258  SCIPerrorMessage("cannot open file <%s> for reading\n", filename);
259  SCIPprintSysError(filename);
260  return SCIP_NOFILE;
261  }
262 
263  lineno = 0;
264  sprintf(name, "SCFLP");
265 
266  nfacilities = 0;
267  ncustomers = 0;
268 
269  /* read problem name */
270  if( !SCIPfeof(file) )
271  {
272  if( SCIPfgets(buffer, (int)sizeof(buffer), file) == NULL )
273  return SCIP_READERROR;
274 
275  /* parse dimension line */
276  nread = sscanf(buffer, " %d %d\n", &nfacilities, &ncustomers);
277  if( nread == 0 )
278  {
279  SCIPwarningMessage(scip, "invalid input line %d in file <%s>: <%s>\n", lineno, filename, buffer);
280  return SCIP_READERROR;
281  }
282 
283  SCIPdebugMsg(scip, "number of facilities = <%d> number of customers = <%d>\n", nfacilities, ncustomers);
284  }
285 
286  /* computing the number of customer cost lines */
287  ncostlines = SCIPceil(scip, (SCIP_Real)nfacilities/MAXNCOSTS);
288 
289  /* allocate buffer memory for storing the demand and the transport cost temporarily */
290  SCIP_CALL( SCIPallocBufferArray(scip, &capacity, nfacilities) );
291  SCIP_CALL( SCIPallocBufferArray(scip, &fixedcost, nfacilities) );
292 
293  for( i = 0; i < nfacilities; i++ )
294  {
295  capacity[i] = 0.0;
296  fixedcost[i] = 0.0;
297  }
298 
299  error = FALSE;
300 
301  /* read facility data */
302  facility = 0;
303  while( !SCIPfeof(file) && !error && facility < nfacilities )
304  {
305  if( SCIPfgets(buffer, (int)sizeof(buffer), file) == NULL )
306  break;
307 
308  /* parse dimension line */
309  nread = sscanf(buffer, " %lf %lf\n", &facilitycap, &facilitycost);
310  if( nread < 2 )
311  {
312  SCIPwarningMessage(scip, "invalid input line %d in file <%s>: <%s>\n", lineno, filename, buffer);
313  error = TRUE;
314  break;
315  }
316 
317  SCIPdebugMsg(scip, "facility %d capacity = <%f>, fixed cost = <%f>\n", facility, facilitycap, facilitycost);
318  capacity[facility] = facilitycap;
319  fixedcost[facility] = facilitycost;
320  facility++;
321  assert(facility <= nfacilities);
322  }
323 
324  /* allocate buffer memory for storing the demand and the transport cost temporarily */
325  SCIP_CALL( SCIPallocBufferArray(scip, &detdemands, ncustomers) );
326  SCIP_CALL( SCIPallocBufferArray(scip, &demands, ncustomers) );
327  SCIP_CALL( SCIPallocBufferArray(scip, &costs, ncustomers) );
328 
329  /* TODO: convert the 2D arrays into contiguous arrays. This has benefits from a memory management point of view. */
330  for( i = 0; i < ncustomers; i++ )
331  {
332  SCIP_CALL( SCIPallocBufferArray(scip, &costs[i], nfacilities) );
333  SCIP_CALL( SCIPallocBufferArray(scip, &demands[i], nscenarios) );
334 
335  for( j = 0; j < nfacilities; j++ )
336  costs[i][j] = 0.0;
337 
338  for( j = 0; j < nscenarios; j++ )
339  demands[i][j] = 0.0;
340 
341  detdemands[i] = 0.0;
342  }
343 
344  /* parse demands and costs */
345 
346  lineno = 0;
347  customer = 0;
348  facility = 0;
349  while( !SCIPfeof(file) && !error )
350  {
351  /* get next line */
352  if( SCIPfgets(buffer, (int)sizeof(buffer), file) == NULL )
353  break;
354 
355  if( lineno == 0 )
356  {
357  /* parse the line */
358  nread = sscanf(buffer, " %lf\n", &demand);
359  if( nread == 0 )
360  {
361  SCIPwarningMessage(scip, "invalid input line %d in file <%s>: <%s>\n", lineno, filename, buffer);
362  error = TRUE;
363  break;
364  }
365 
366  SCIPdebugMsg(scip, "customer %d demand <%f>\n", customer, demand);
367  detdemands[customer] = demand;
368  }
369  else if( lineno <= ncostlines )
370  {
371  SCIP_Real tmpcosts[MAXNCOSTS];
372  /* parse the line */
373  nread = sscanf(buffer, " %lf %lf %lf %lf %lf %lf %lf\n", &tmpcosts[0], &tmpcosts[1], &tmpcosts[2],
374  &tmpcosts[3], &tmpcosts[4], &tmpcosts[5], &tmpcosts[6]);
375 
376  if( nread == 0 )
377  {
378  SCIPwarningMessage(scip, "invalid input line %d in file <%s>: <%s>\n", lineno, filename, buffer);
379  error = TRUE;
380  break;
381  }
382 
383  for( i = 0; i < nread; i++ )
384  {
385  SCIPdebugMsg(scip, "(%d, %d) found cost <%e>\n", customer, facility, tmpcosts[i]);
386  costs[customer][facility] = tmpcosts[i]/demand;
387  facility++;
388  }
389  }
390 
391  if( lineno == ncostlines )
392  {
393  lineno = 0;
394  facility = 0;
395  customer++;
396  }
397  else
398  lineno++;
399  }
400 
401  /* if there has been no error in reading the data, then we generate the scenarios */
402  if( !error )
403  {
404  SCIP_Real mean;
405  SCIP_Real stdDev;
406  SCIP_Real spare;
407  SCIP_Bool hasspare;
408 
409  /* creating the scenario data */
410  for( i = 0; i < ncustomers; i++ )
411  {
412  mean = detdemands[i];
413  stdDev = SCIPrandomGetReal(randomgen, 0.1*mean, 0.2*mean);
414  hasspare = FALSE;
415  for( j = 0; j < nscenarios; j++ )
416  {
417  demands[i][j] = SCIPround(scip, generateGaussianNoise(randomgen, mean, stdDev, &spare, &hasspare));
418 
419  SCIPdebugMsg(scip, "Scenario %d: customer %d demand <%f>\n", j, i, demands[i][j]);
420  }
421  }
422 
423  /* create a new problem in SCIP */
424  SCIP_CALL( SCIPprobdataCreate(scip, name, costs, demands, capacity, fixedcost, ncustomers, nfacilities,
425  nscenarios, readerdata->usebenders) );
426  }
427 
428  (void)SCIPfclose(file);
429 
430  for( i = ncustomers - 1; i >= 0; i-- )
431  {
432  SCIPfreeBufferArray(scip, &demands[i]);
433  SCIPfreeBufferArray(scip, &costs[i]);
434  }
435 
436  SCIPfreeBufferArray(scip, &costs);
437  SCIPfreeBufferArray(scip, &demands);
438  SCIPfreeBufferArray(scip, &detdemands);
439 
440  SCIPfreeBufferArray(scip, &fixedcost);
441  SCIPfreeBufferArray(scip, &capacity);
442 
443  /* freeing the random number generator */
444  SCIPfreeRandom(scip, &randomgen);
445 
446  if( error )
447  return SCIP_READERROR;
448 
449  *result = SCIP_SUCCESS;
450 
451  return SCIP_OKAY;
452 }
453 
454 /**@} */
455 
456 
457 /**@name Interface methods
458  *
459  * @{
460  */
461 
462 /** includes the scflp file reader in SCIP */
464  SCIP* scip /**< SCIP data structure */
465  )
466 {
467  SCIP_READERDATA* readerdata;
468  SCIP_READER* reader;
469 
470  /* create scflp reader data */
471  readerdata = NULL;
472 
473  SCIP_CALL( readerdataCreate(scip, &readerdata) );
474 
475  /* include scflp reader */
477  assert(reader != NULL);
478 
479  SCIP_CALL( SCIPsetReaderFree(scip, reader, readerFreeScflp) );
480  SCIP_CALL( SCIPsetReaderRead(scip, reader, readerReadScflp) );
481 
483  "reading/" READER_NAME "/usebenders", "Should Benders' decomposition be used to solve the problem?",
484  &readerdata->usebenders, FALSE, DEFAULT_USEBENDERS, NULL, NULL) );
485 
487  "reading/" READER_NAME "/numscenarios",
488  "the number of scenarios that will be randomly generated",
489  &readerdata->nscenarios, FALSE, DEFAULT_NUMSCENARIOS, 1, INT_MAX, NULL, NULL) );
490 
492  "reading/" READER_NAME "/randomseed",
493  "the random seed used to generate the scenarios",
494  &readerdata->randomseed, FALSE, DEFAULT_RANDOMSEED, 1, INT_MAX, NULL, NULL) );
495 
496  return SCIP_OKAY;
497 }
498 
499 /**@} */
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
#define NULL
Definition: def.h:246
#define MAXNCOSTS
Definition: reader_scflp.c:109
#define DEFAULT_USEBENDERS
Definition: reader_scflp.c:105
#define SCIP_MAXSTRLEN
Definition: def.h:267
#define READER_EXTENSION
Definition: reader_scflp.c:102
static SCIP_DECL_READERREAD(readerReadScflp)
Definition: reader_scflp.c:213
#define FALSE
Definition: def.h:72
#define DEFAULT_RANDOMSEED
Definition: reader_scflp.c:107
static SCIP_Real generateGaussianNoise(SCIP_RANDNUMGEN *randomgen, SCIP_Real mean, SCIP_Real stdDev, SCIP_Real *spare, SCIP_Bool *hasspare)
Definition: reader_scflp.c:122
#define TRUE
Definition: def.h:71
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
SCIP_RETCODE SCIPprobdataCreate(SCIP *scip, const char *probname, int *demands, SCIP_Real *rints, SCIP_Real *rexts, int ntypes, SCIP_Real width, SCIP_Real height)
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
#define READER_DESC
Definition: reader_scflp.c:101
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:203
#define SCIPdebugMsg
Definition: scip_message.h:88
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_FILE * SCIPfopen(const char *path, const char *mode)
Definition: fileio.c:140
SCIP_READERDATA * SCIPreaderGetData(SCIP_READER *reader)
Definition: reader.c:482
#define SCIPerrorMessage
Definition: pub_message.h:45
SCFLP problem reader file reader.
#define READER_NAME
Definition: reader_scflp.c:100
SCIPInterval sqrt(const SCIPInterval &x)
int SCIPfeof(SCIP_FILE *stream)
Definition: fileio.c:214
struct SCIP_File SCIP_FILE
Definition: pub_fileio.h:34
char * SCIPfgets(char *s, int size, SCIP_FILE *stream)
Definition: fileio.c:187
#define SCIP_CALL(x)
Definition: def.h:358
Problem data for Stochastic Capacitated Facility Location problem.
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
struct SCIP_ReaderData SCIP_READERDATA
Definition: type_reader.h:37
#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 SCIPincludeReaderScflp(SCIP *scip)
Definition: reader_scflp.c:463
void SCIPprintSysError(const char *message)
Definition: misc.c:10162
static SCIP_RETCODE readerdataFree(SCIP *scip, SCIP_READERDATA **readerdata)
Definition: reader_scflp.c:174
static SCIP_DECL_READERFREE(readerFreeScflp)
Definition: reader_scflp.c:196
static SCIP_RETCODE readerdataCreate(SCIP *scip, SCIP_READERDATA **readerdata)
Definition: reader_scflp.c:158
SCIPInterval log(const SCIPInterval &x)
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:9630
#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 DEFAULT_NUMSCENARIOS
Definition: reader_scflp.c:106
int SCIPfclose(SCIP_FILE *fp)
Definition: fileio.c:219
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPround(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPsetReaderFree(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERFREE((*readerfree)))
Definition: scip_reader.c:242
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