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-2022 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 scipopt.org. */
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 TRUE
106 #define DEFAULT_NUMSCENARIOS 250
107 #define DEFAULT_RANDOMSEED 1
108 #define DEFAULT_QUADCOSTS FALSE /**< should the problem be formulated with quadratic costs */
109 
110 
111 #define MAXNCOSTS 7
112 
113 struct SCIP_ReaderData
114 {
115  SCIP_Bool usebenders; /**< should Benders' decomposition be used to solve the problem */
116  int nscenarios; /**< the number of scenarios */
117  int randomseed; /**< the random seed used to generate the scenarios */
118  SCIP_Bool quadcosts; /**< should the problem be formulated with quadratic costs */
119 };
120 
121 /**@} */
122 
123 /** generates a normally distributed random number */
124 static
126  SCIP_RANDNUMGEN* randomgen, /**< the random number generator */
127  SCIP_Real mean, /**< the mean of the normal distribution */
128  SCIP_Real stdDev, /**< the standard deviation of the normal distribution */
129  SCIP_Real* spare, /**< the spare value that has been collected */
130  SCIP_Bool* hasspare /**< whether a spare value exists */
131  )
132 {
133  SCIP_Real u;
134  SCIP_Real v;
135  SCIP_Real s;
136 
137  /* if a spare exists, then it is returned */
138  if( (*hasspare) )
139  {
140  (*hasspare) = FALSE;
141  return mean + stdDev * (*spare);
142  }
143 
144  (*hasspare) = TRUE;
145  do {
146  u = SCIPrandomGetReal(randomgen, 0.0, 1.0);
147  v = SCIPrandomGetReal(randomgen, 0.0, 1.0);
148  s = u * u + v * v;
149  }
150  while( (s >= 1.0) || (s == 0.0) );
151 
152  s = sqrt(-2.0 * log(s) / s);
153  (*spare) = v * s;
154 
155  return mean + stdDev * u * s;
156 }
157 
158 
159 /** creates the reader data */
160 static
162  SCIP* scip, /**< SCIP data structure */
163  SCIP_READERDATA** readerdata /**< pointer to store the reader data */
164  )
165 {
166  assert(scip != NULL);
167  assert(readerdata != NULL);
168 
169  SCIP_CALL( SCIPallocBlockMemory(scip, readerdata) );
170  (*readerdata)->usebenders = TRUE;
171 
172  return SCIP_OKAY;
173 }
174 
175 /** frees the reader data */
176 static
178  SCIP* scip, /**< SCIP data structure */
179  SCIP_READERDATA** readerdata /**< pointer to store the reader data */
180  )
181 {
182  assert(scip != NULL);
183  assert(readerdata != NULL);
184  assert(*readerdata != NULL);
185 
186  SCIPfreeBlockMemory(scip, readerdata);
187 
188  return SCIP_OKAY;
189 }
190 
191 
192 /**@name Callback methods
193  *
194  * @{
195  */
196 
197 /** destructor of reader to free user data (called when SCIP is exiting)*/
198 static
199 SCIP_DECL_READERFREE(readerFreeScflp)
200 {
201  SCIP_READERDATA* readerdata;
202 
203  assert(scip != NULL);
204  assert(reader != NULL);
205 
206  readerdata = SCIPreaderGetData(reader);
207 
208  SCIP_CALL( readerdataFree(scip, &readerdata) );
209 
210  return SCIP_OKAY;
211 }
212 
213 
214 /** problem reading method of reader */
215 static
216 SCIP_DECL_READERREAD(readerReadScflp)
217 { /*lint --e{715}*/
218  SCIP_READERDATA* readerdata;
219 
220  SCIP_RANDNUMGEN* randomgen;
221 
222  SCIP_FILE* file;
223  SCIP_Bool error;
224 
225  char name[SCIP_MAXSTRLEN];
226  char buffer[SCIP_MAXSTRLEN];
227  SCIP_Real* fixedcost;
228  SCIP_Real* capacity;
229  SCIP_Real* detdemands;
230  SCIP_Real** demands;
231  SCIP_Real** costs;
232  int nfacilities;
233  int ncustomers;
234  int nscenarios;
235 
236  SCIP_Real facilitycost;
237  SCIP_Real facilitycap;
238  SCIP_Real demand;
239  int facility;
240  int customer;
241  int ncostlines; /* this is the number of lines that have facility costs */
242 
243  int nread;
244  int lineno;
245  int i;
246  int j;
247 
248  readerdata = SCIPreaderGetData(reader);
249 
250  /* creating the random number generator */
251  SCIP_CALL( SCIPcreateRandom(scip, &randomgen, readerdata->randomseed, FALSE) );
252 
253  nscenarios = readerdata->nscenarios;
254 
255  *result = SCIP_DIDNOTRUN;
256 
257  /* open file */
258  file = SCIPfopen(filename, "r");
259  if( file == NULL )
260  {
261  SCIPerrorMessage("cannot open file <%s> for reading\n", filename);
262  SCIPprintSysError(filename);
263  return SCIP_NOFILE;
264  }
265 
266  lineno = 0;
267  sprintf(name, "SCFLP");
268 
269  nfacilities = 0;
270  ncustomers = 0;
271 
272  /* read problem name */
273  if( !SCIPfeof(file) )
274  {
275  if( SCIPfgets(buffer, (int)sizeof(buffer), file) == NULL )
276  return SCIP_READERROR;
277 
278  /* parse dimension line */
279  nread = sscanf(buffer, " %d %d\n", &nfacilities, &ncustomers);
280  if( nread == 0 )
281  {
282  SCIPwarningMessage(scip, "invalid input line %d in file <%s>: <%s>\n", lineno, filename, buffer);
283  return SCIP_READERROR;
284  }
285 
286  SCIPdebugMsg(scip, "number of facilities = <%d> number of customers = <%d>\n", nfacilities, ncustomers);
287  }
288 
289  /* computing the number of customer cost lines */
290  ncostlines = SCIPceil(scip, (SCIP_Real)nfacilities/MAXNCOSTS);
291 
292  /* allocate buffer memory for storing the demand and the transport cost temporarily */
293  SCIP_CALL( SCIPallocBufferArray(scip, &capacity, nfacilities) );
294  SCIP_CALL( SCIPallocBufferArray(scip, &fixedcost, nfacilities) );
295 
296  for( i = 0; i < nfacilities; i++ )
297  {
298  capacity[i] = 0.0;
299  fixedcost[i] = 0.0;
300  }
301 
302  error = FALSE;
303 
304  /* read facility data */
305  facility = 0;
306  while( !SCIPfeof(file) && !error && facility < nfacilities )
307  {
308  if( SCIPfgets(buffer, (int)sizeof(buffer), file) == NULL )
309  break;
310 
311  /* parse dimension line */
312  nread = sscanf(buffer, " %lf %lf\n", &facilitycap, &facilitycost);
313  if( nread < 2 )
314  {
315  SCIPwarningMessage(scip, "invalid input line %d in file <%s>: <%s>\n", lineno, filename, buffer);
316  error = TRUE;
317  break;
318  }
319 
320  SCIPdebugMsg(scip, "facility %d capacity = <%f>, fixed cost = <%f>\n", facility, facilitycap, facilitycost);
321  capacity[facility] = facilitycap;
322  fixedcost[facility] = facilitycost;
323  facility++;
324  assert(facility <= nfacilities);
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, readerdata->quadcosts) );
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 
500  "reading/" READER_NAME "/quadcosts", "should the problem be formulated with quadratic costs",
501  &readerdata->quadcosts, FALSE, DEFAULT_QUADCOSTS, NULL, NULL) );
502 
503  return SCIP_OKAY;
504 }
505 
506 /**@} */
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
#define MAXNCOSTS
Definition: reader_scflp.c:111
#define DEFAULT_USEBENDERS
Definition: reader_scflp.c:105
#define SCIP_MAXSTRLEN
Definition: def.h:293
#define READER_EXTENSION
Definition: reader_scflp.c:102
static SCIP_DECL_READERREAD(readerReadScflp)
Definition: reader_scflp.c:216
#define FALSE
Definition: def.h:87
#define DEFAULT_RANDOMSEED
Definition: reader_scflp.c:107
#define DEFAULT_QUADCOSTS
Definition: reader_scflp.c:108
static SCIP_Real generateGaussianNoise(SCIP_RANDNUMGEN *randomgen, SCIP_Real mean, SCIP_Real stdDev, SCIP_Real *spare, SCIP_Bool *hasspare)
Definition: reader_scflp.c:125
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
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 READER_DESC
Definition: reader_scflp.c:101
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:111
#define SCIPdebugMsg
Definition: scip_message.h:69
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:74
SCIP_FILE * SCIPfopen(const char *path, const char *mode)
Definition: fileio.c:144
SCIP_READERDATA * SCIPreaderGetData(SCIP_READER *reader)
Definition: reader.c:483
#define SCIPerrorMessage
Definition: pub_message.h:55
SCFLP problem reader file reader.
#define READER_NAME
Definition: reader_scflp.c:100
int SCIPfeof(SCIP_FILE *stream)
Definition: fileio.c:218
struct SCIP_File SCIP_FILE
Definition: pub_fileio.h:34
char * SCIPfgets(char *s, int size, SCIP_FILE *stream)
Definition: fileio.c:191
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:384
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:115
struct SCIP_ReaderData SCIP_READERDATA
Definition: type_reader.h:44
#define SCIP_Bool
Definition: def.h:84
SCIP_RETCODE SCIPincludeReaderBasic(SCIP *scip, SCIP_READER **readerptr, const char *name, const char *desc, const char *extension, SCIP_READERDATA *readerdata)
Definition: scip_reader.c:100
SCIP_RETCODE SCIPincludeReaderScflp(SCIP *scip)
Definition: reader_scflp.c:466
void SCIPprintSysError(const char *message)
Definition: misc.c:10664
static SCIP_RETCODE readerdataFree(SCIP *scip, SCIP_READERDATA **readerdata)
Definition: reader_scflp.c:177
static SCIP_DECL_READERFREE(readerFreeScflp)
Definition: reader_scflp.c:199
static SCIP_RETCODE readerdataCreate(SCIP *scip, SCIP_READERDATA **readerdata)
Definition: reader_scflp.c:161
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10025
#define SCIP_Real
Definition: def.h:177
SCIP_RETCODE SCIPsetReaderRead(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERREAD((*readerread)))
Definition: scip_reader.c:186
#define DEFAULT_NUMSCENARIOS
Definition: reader_scflp.c:106
SCIPallocBlockMemory(scip, subsol))
int SCIPfclose(SCIP_FILE *fp)
Definition: fileio.c:223
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:162
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:48