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-2018 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 
241  int nread;
242  int lineno;
243  int i;
244  int j;
245 
246  readerdata = SCIPreaderGetData(reader);
247 
248  /* creating the random number generator */
249  SCIP_CALL( SCIPcreateRandom(scip, &randomgen, readerdata->randomseed, FALSE) );
250 
251  nscenarios = readerdata->nscenarios;
252 
253  *result = SCIP_DIDNOTRUN;
254 
255  /* open file */
256  file = SCIPfopen(filename, "r");
257  if( file == NULL )
258  {
259  SCIPerrorMessage("cannot open file <%s> for reading\n", filename);
260  SCIPprintSysError(filename);
261  return SCIP_NOFILE;
262  }
263 
264  lineno = 0;
265  sprintf(name, "SCFLP");
266 
267  nfacilities = 0;
268  ncustomers = 0;
269 
270  /* read problem name */
271  if( !SCIPfeof(file) )
272  {
273  if( SCIPfgets(buffer, (int)sizeof(buffer), file) == NULL )
274  return SCIP_READERROR;
275 
276  /* parse dimension line */
277  nread = sscanf(buffer, " %d %d\n", &nfacilities, &ncustomers);
278  if( nread == 0 )
279  {
280  SCIPwarningMessage(scip, "invalid input line %d in file <%s>: <%s>\n", lineno, filename, buffer);
281  return SCIP_READERROR;
282  }
283 
284  SCIPdebugMsg(scip, "number of facilities = <%d> number of customers = <%d>\n", nfacilities, ncustomers);
285  }
286 
287  /* computing the number of customer cost lines */
288  ncostlines = SCIPceil(scip, (SCIP_Real)nfacilities/MAXNCOSTS);
289 
290 
291  /* allocate buffer memory for storing the demand and the transport cost temporarily */
292  SCIP_CALL( SCIPallocBufferArray(scip, &capacity, nfacilities) );
293  SCIP_CALL( SCIPallocBufferArray(scip, &fixedcost, nfacilities) );
294 
295  for( i = 0; i < nfacilities; i++ )
296  {
297  capacity[i] = 0.0;
298  fixedcost[i] = 0.0;
299  }
300 
301  error = FALSE;
302 
303  /* read facility data */
304  facility = 0;
305  while( !SCIPfeof(file) && !error && facility < nfacilities )
306  {
307  if( SCIPfgets(buffer, (int)sizeof(buffer), file) == NULL )
308  break;
309 
310  /* parse dimension line */
311  nread = sscanf(buffer, " %lf %lf\n", &facilitycap, &facilitycost);
312  if( nread < 2 )
313  {
314  SCIPwarningMessage(scip, "invalid input line %d in file <%s>: <%s>\n", lineno, filename, buffer);
315  error = TRUE;
316  break;
317  }
318 
319  SCIPdebugMsg(scip, "facility %d capacity = <%f>, fixed cost = <%f>\n", facility, facilitycap, facilitycost);
320  capacity[facility] = facilitycap;
321  fixedcost[facility] = facilitycost;
322  facility++;
323  assert(facility <= nfacilities);
324  }
325 
326 
327  /* allocate buffer memory for storing the demand and the transport cost temporarily */
328  SCIP_CALL( SCIPallocBufferArray(scip, &detdemands, ncustomers) );
329  SCIP_CALL( SCIPallocBufferArray(scip, &demands, ncustomers) );
330  SCIP_CALL( SCIPallocBufferArray(scip, &costs, ncustomers) );
331 
332  /* TODO: convert the 2D arrays into contiguous arrays. This has benefits from a memory management point of view. */
333  for( i = 0; i < ncustomers; i++ )
334  {
335  SCIP_CALL( SCIPallocBufferArray(scip, &costs[i], nfacilities) );
336  SCIP_CALL( SCIPallocBufferArray(scip, &demands[i], nscenarios) );
337 
338  for( j = 0; j < nfacilities; j++ )
339  costs[i][j] = 0.0;
340 
341  for( j = 0; j < nscenarios; j++ )
342  demands[i][j] = 0.0;
343 
344  detdemands[i] = 0.0;
345  }
346 
347  /* parse demands and costs */
348 
349  lineno = 0;
350  customer = 0;
351  facility = 0;
352  while( !SCIPfeof(file) && !error )
353  {
354  /* get next line */
355  if( SCIPfgets(buffer, (int)sizeof(buffer), file) == NULL )
356  break;
357 
358  if( lineno == 0 )
359  {
360  /* parse the line */
361  nread = sscanf(buffer, " %lf\n", &demand);
362  if( nread == 0 )
363  {
364  SCIPwarningMessage(scip, "invalid input line %d in file <%s>: <%s>\n", lineno, filename, buffer);
365  error = TRUE;
366  break;
367  }
368 
369  SCIPdebugMsg(scip, "customer %d demand <%f>\n", customer, demand);
370  detdemands[customer] = demand;
371  }
372  else if( lineno <= ncostlines )
373  {
374  SCIP_Real tmpcosts[MAXNCOSTS];
375  /* parse the line */
376  nread = sscanf(buffer, " %lf %lf %lf %lf %lf %lf %lf\n", &tmpcosts[0], &tmpcosts[1], &tmpcosts[2],
377  &tmpcosts[3], &tmpcosts[4], &tmpcosts[5], &tmpcosts[6]);
378 
379  if( nread == 0 )
380  {
381  SCIPwarningMessage(scip, "invalid input line %d in file <%s>: <%s>\n", lineno, filename, buffer);
382  error = TRUE;
383  break;
384  }
385 
386  for( i = 0; i < nread; i++ )
387  {
388  SCIPdebugMsg(scip, "(%d, %d) found cost <%e>\n", customer, facility, tmpcosts[i]);
389  costs[customer][facility] = tmpcosts[i]/demand;
390  facility++;
391  }
392  }
393 
394  if( lineno == ncostlines )
395  {
396  lineno = 0;
397  facility = 0;
398  customer++;
399  }
400  else
401  lineno++;
402  }
403 
404  /* if there has been no error in reading the data, then we generate the scenarios */
405  if( !error )
406  {
407  SCIP_Real mean;
408  SCIP_Real stdDev;
409  SCIP_Real spare;
410  SCIP_Bool hasspare;
411 
412  /* creating the scenario data */
413  for( i = 0; i < ncustomers; i++ )
414  {
415  mean = detdemands[i];
416  stdDev = SCIPrandomGetReal(randomgen, 0.1*mean, 0.2*mean);
417  hasspare = FALSE;
418  for( j = 0; j < nscenarios; j++ )
419  {
420  demands[i][j] = SCIPround(scip, generateGaussianNoise(randomgen, mean, stdDev, &spare, &hasspare));
421 
422  SCIPdebugMsg(scip, "Scenario %d: customer %d demand <%f>\n", j, i, demands[i][j]);
423  }
424  }
425 
426  /* create a new problem in SCIP */
427  SCIP_CALL( SCIPprobdataCreate(scip, name, costs, demands, capacity, fixedcost, ncustomers, nfacilities,
428  nscenarios, readerdata->usebenders) );
429  }
430 
431  (void)SCIPfclose(file);
432 
433  for( i = ncustomers - 1; i >= 0; i-- )
434  {
435  SCIPfreeBufferArray(scip, &demands[i]);
436  SCIPfreeBufferArray(scip, &costs[i]);
437  }
438 
439  SCIPfreeBufferArray(scip, &costs);
440  SCIPfreeBufferArray(scip, &demands);
441  SCIPfreeBufferArray(scip, &detdemands);
442 
443  SCIPfreeBufferArray(scip, &fixedcost);
444  SCIPfreeBufferArray(scip, &capacity);
445 
446  /* freeing the random number generator */
447  SCIPfreeRandom(scip, &randomgen);
448 
449  if( error )
450  return SCIP_READERROR;
451 
452  *result = SCIP_SUCCESS;
453 
454  return SCIP_OKAY;
455 }
456 
457 /**@} */
458 
459 
460 /**@name Interface methods
461  *
462  * @{
463  */
464 
465 /** includes the scflp file reader in SCIP */
467  SCIP* scip /**< SCIP data structure */
468  )
469 {
470  SCIP_READERDATA* readerdata;
471  SCIP_READER* reader;
472 
473  /* create scflp reader data */
474  readerdata = NULL;
475 
476  SCIP_CALL( readerdataCreate(scip, &readerdata) );
477 
478  /* include scflp reader */
480  assert(reader != NULL);
481 
482  SCIP_CALL( SCIPsetReaderFree(scip, reader, readerFreeScflp) );
483  SCIP_CALL( SCIPsetReaderRead(scip, reader, readerReadScflp) );
484 
486  "reading/" READER_NAME "/usebenders", "Should Benders' decomposition be used to solve the problem?",
487  &readerdata->usebenders, FALSE, DEFAULT_USEBENDERS, NULL, NULL) );
488 
490  "reading/" READER_NAME "/numscenarios",
491  "the number of scenarios that will be randomly generated",
492  &readerdata->nscenarios, FALSE, DEFAULT_NUMSCENARIOS, 1, INT_MAX, NULL, NULL) );
493 
495  "reading/" READER_NAME "/randomseed",
496  "the random seed used to generate the scenarios",
497  &readerdata->randomseed, FALSE, DEFAULT_RANDOMSEED, 1, INT_MAX, NULL, NULL) );
498 
499  return SCIP_OKAY;
500 }
501 
502 /**@} */
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
#define NULL
Definition: def.h:239
#define MAXNCOSTS
Definition: reader_scflp.c:109
#define DEFAULT_USEBENDERS
Definition: reader_scflp.c:105
#define SCIP_MAXSTRLEN
Definition: def.h:260
#define READER_EXTENSION
Definition: reader_scflp.c:102
static SCIP_DECL_READERREAD(readerReadScflp)
Definition: reader_scflp.c:213
#define FALSE
Definition: def.h:65
#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:64
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:351
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:62
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:466
void SCIPprintSysError(const char *message)
Definition: misc.c:9926
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:9394
#define SCIP_Real
Definition: def.h:150
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