Scippy

SCIP

Solving Constraint Integer Programs

reader_bpa.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_bpa.c
17  * @brief Binpacking problem reader file reader
18  * @author Timo Berthold
19  * @author Stefan Heinz
20  *
21  * This file implements the reader/parser used to read the binpacking input data. For more details see \ref BINPACKING_READER.
22  *
23  * @page BINPACKING_READER Parsing the input format and creating the problem
24  *
25  * In the <code>data</code> directory you find a few data files which contain each one binpacking problem. These data
26  * files have the following structure. In the first line the name of the instance is stated. In the second line you find
27  * three integer numbers. The first one gives you the capacity \f$\kappa\f$, the second the number of items, and the
28  * last integer states the value of a known feasible solution. This means an upper bound on the number of needed
29  * bins. The remaining lines give the size for each item.
30  *
31  * For parsing that data, we implemented a reader plugin for \SCIP. A reader has several callback methods and at least
32  * one interface methods (the one including the reader into \SCIP). For our purpose we only implemented the \ref
33  * READERREAD "READERREAD" callback and the interface method which adds the reader plugin to \SCIP.
34  *
35  * @section BINPACKING_READERINCLUDE The SCIPincludeReaderBpa() interface method
36  *
37  * The interface method <code>SCIPincludeReaderBpa()</code> is called to add the reader plugin to \SCIP (see
38  * cmain.c). This means \SCIP gets informed that this reader is available for reading input files. Therefore, the
39  * function <code>SCIPincludeReader()</code> is called within this method which passes all necessary information of the
40  * reader to SCIP. This information includes the name of the reader, a description, and the file extension for which the
41  * file reader is in charge. In our case we selected the file extension "bpa". This means that all files which have
42  * this file extension are passed to our reader for parsing. Besides these information the call
43  * <code>SCIPincludeReader()</code> also passes for each callback of the reader a function pointers
44  * (some of them might be NULL pointers). These function
45  * pointers are used by \SCIP to run the reader. For more information about all available reader callbacks we refer to
46  * the \ref READER "How to add file readers" tutorial. In the remaining section
47  * we restrict ourself to the callback <code>READERREAD</code> which is the only one we implemented for the binpacking
48  * example. All other callbacks are not required for this example.
49  *
50  * @section BINPACKING_READERREAD The READERREAD callback method
51  *
52  * The READERREAD callback is in charge of parsing a file and creating the problem. To see the list of arguments this
53  * functions gets see the file type_reader.h in the source of \SCIP. The following arguments are of interest in our
54  * case. First of all the \SCIP pointer, the file name, and the SCIP_RESULT pointer. The \SCIP pointer gives us the
55  * current environment. The file name states the file which we should open and parse. Last but not least, the SCIP_RESULT
56  * pointer is required to tell \SCIP if the parsing process was successfully or
57  * not. Note that in type_reader.h you also find a list of allowable result values for the SCIP_RESULT pointer and the
58  * <code>SCIP_RETCODE</code> which is the return value of this function.
59  *
60  * @subsection BINPACKING_PARSING Parsing the problem
61  *
62  * The file can be opened and parsed with your favorite methods. In this case we are using the functionality provided by
63  * \SCIP since this has some nice side effects. We are using the function SCIPfopen() which can besides standard
64  * 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
65  * in the source of SCIP. Parsing the data out of the file is not that hard. Please look at the code and comments
66  * therein for more details.
67  *
68  * @subsection BINPACKING_CREATING Creating the problem
69  *
70  * After parsing the file the final task for the reader is to create the problem. In our case, we pass the collected data
71  * to the \ref probdata_binpacking.h "main problem data plugin". For this, we use the interface methods
72  * SCIPprobdataCreate() which is provided by the
73  * problem data plugin (see probdata_binpacking.c). After that, the reader sets the result value for the SCIP_RESULT
74  * pointer to <code>SCIP_SUCCESS</code> and returns with a proper <code>SCIP_RETCODE</code>.
75  *
76  *
77  */
78 
79 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
80 
81 #include <assert.h>
82 #include <string.h>
83 
84 #include "scip/cons_setppc.h"
85 
86 #include "probdata_binpacking.h"
87 #include "reader_bpa.h"
88 
89 /**@name Reader properties
90  *
91  * @{
92  */
93 
94 #define READER_NAME "bpareader"
95 #define READER_DESC "file reader for binpacking data format"
96 #define READER_EXTENSION "bpa"
97 
98 /**@} */
99 
100 
101 /**@name Callback methods
102  *
103  * @{
104  */
105 
106 /** problem reading method of reader */
107 static
108 SCIP_DECL_READERREAD(readerReadBpa)
109 { /*lint --e{715}*/
110  SCIP_FILE* file;
111  SCIP_Longint* weights;
112  int* ids;
113  SCIP_Bool error;
114 
115  char name[SCIP_MAXSTRLEN];
116  char format[16];
117  char buffer[SCIP_MAXSTRLEN];
118  int capacity;
119  int nitems;
120  int bestsolvalue;
121  int nread;
122  int weight;
123  int nweights;
124  int lineno;
125 
126  *result = SCIP_DIDNOTRUN;
127 
128  /* open file */
129  file = SCIPfopen(filename, "r");
130  if( file == NULL )
131  {
132  SCIPerrorMessage("cannot open file <%s> for reading\n", filename);
133  SCIPprintSysError(filename);
134  return SCIP_NOFILE;
135  }
136 
137  lineno = 0;
138  sprintf(name, "++ uninitialized ++");
139 
140  /* read problem name */
141  if( !SCIPfeof(file) )
142  {
143  /* get next line */
144  if( SCIPfgets(buffer, (int)sizeof(buffer), file) == NULL )
145  return SCIP_READERROR;
146  lineno++;
147 
148  /* parse dimension line */
149  sprintf(format, "%%%ds\n", SCIP_MAXSTRLEN);
150  nread = sscanf(buffer, format, name);
151  if( nread == 0 )
152  {
153  SCIPwarningMessage(scip, "invalid input line %d in file <%s>: <%s>\n", lineno, filename, buffer);
154  return SCIP_READERROR;
155  }
156 
157  SCIPdebugMsg(scip, "problem name <%s>\n", name);
158  }
159 
160  capacity = 0;
161  nitems = 0;
162 
163  /* read problem dimension */
164  if( !SCIPfeof(file) )
165  {
166  /* get next line */
167  if( SCIPfgets(buffer, (int)sizeof(buffer), file) == NULL )
168  return SCIP_READERROR;
169  lineno++;
170 
171  /* parse dimension line */
172  nread = sscanf(buffer, "%d %d %d\n", &capacity, &nitems, &bestsolvalue);
173  if( nread < 2 )
174  {
175  SCIPwarningMessage(scip, "invalid input line %d in file <%s>: <%s>\n", lineno, filename, buffer);
176  return SCIP_READERROR;
177  }
178 
179  SCIPdebugMsg(scip, "capacity = <%d>, number of items = <%d>, best known solution = <%d>\n", capacity, nitems, bestsolvalue);
180  }
181 
182  /* allocate buffer memory for storing the weights and ids temporary */
183  SCIP_CALL( SCIPallocBufferArray(scip, &weights, nitems) );
184  SCIP_CALL( SCIPallocBufferArray(scip, &ids, nitems) );
185 
186  /* pasre weights */
187  nweights = 0;
188  error = FALSE;
189 
190  while( !SCIPfeof(file) && !error )
191  {
192  /* get next line */
193  if( SCIPfgets(buffer, (int)sizeof(buffer), file) == NULL )
194  break;
195  lineno++;
196 
197  /* parse the line */
198  nread = sscanf(buffer, "%d\n", &weight);
199  if( nread == 0 )
200  {
201  SCIPwarningMessage(scip, "invalid input line %d in file <%s>: <%s>\n", lineno, filename, buffer);
202  error = TRUE;
203  break;
204  }
205 
206  SCIPdebugMsg(scip, "found weight %d <%d>\n", nweights, weight);
207  weights[nweights] = weight;
208  ids[nweights] = nweights;
209  nweights++;
210 
211  if( nweights == nitems )
212  break;
213  }
214 
215  if( nweights < nitems )
216  {
217  SCIPwarningMessage(scip, "set nitems from <%d> to <%d> since the file <%s> only contains <%d> weights\n", nitems, weights, filename, weights);
218  nitems = nweights;
219  }
220 
221  if( !error )
222  {
223  /* create a new problem in SCIP */
224  SCIP_CALL( SCIPprobdataCreate(scip, name, ids, weights, nitems, (SCIP_Longint)capacity) );
225  }
226 
227  (void)SCIPfclose(file);
228  SCIPfreeBufferArray(scip, &ids);
229  SCIPfreeBufferArray(scip, &weights);
230 
231  if( error )
232  return SCIP_READERROR;
233 
234  *result = SCIP_SUCCESS;
235 
236  return SCIP_OKAY;
237 }
238 
239 /**@} */
240 
241 
242 /**@name Interface methods
243  *
244  * @{
245  */
246 
247 /** includes the bpa file reader in SCIP */
249  SCIP* scip /**< SCIP data structure */
250  )
251 {
252  SCIP_READERDATA* readerdata;
253  SCIP_READER* reader;
254 
255  /* create binpacking reader data */
256  readerdata = NULL;
257 
258  /* include binpacking reader */
260  assert(reader != NULL);
261 
262  SCIP_CALL( SCIPsetReaderRead(scip, reader, readerReadBpa) );
263 
264  return SCIP_OKAY;
265 }
266 
267 /**@} */
#define NULL
Definition: def.h:253
#define SCIP_MAXSTRLEN
Definition: def.h:274
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:122
SCIP_RETCODE SCIPincludeReaderBpa(SCIP *scip)
Definition: reader_bpa.c:248
SCIP_RETCODE SCIPsetReaderRead(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERREAD((*readerread)))
Definition: scip_reader.c:185
#define FALSE
Definition: def.h:73
#define TRUE
Definition: def.h:72
#define READER_EXTENSION
Definition: reader_bpa.c:96
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
SCIP_RETCODE SCIPprobdataCreate(SCIP *scip, const char *probname, int *demands, SCIP_Real *rints, SCIP_Real *rexts, int ntypes, SCIP_Real width, SCIP_Real height)
Constraint handler for the set partitioning / packing / covering constraints .
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_FILE * SCIPfopen(const char *path, const char *mode)
Definition: fileio.c:140
#define SCIPerrorMessage
Definition: pub_message.h:45
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:365
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
struct SCIP_ReaderData SCIP_READERDATA
Definition: type_reader.h:39
#define SCIP_Bool
Definition: def.h:70
Problem data for binpacking problem.
SCIP_RETCODE SCIPincludeReaderBasic(SCIP *scip, SCIP_READER **readerptr, const char *name, const char *desc, const char *extension, SCIP_READERDATA *readerdata)
Definition: scip_reader.c:99
Binpacking problem reader file reader.
static SCIP_DECL_READERREAD(readerReadBpa)
Definition: reader_bpa.c:108
void SCIPprintSysError(const char *message)
Definition: misc.c:10172
#define SCIP_Longint
Definition: def.h:149
#define READER_NAME
Definition: reader_bpa.c:94
int SCIPfclose(SCIP_FILE *fp)
Definition: fileio.c:219
#define READER_DESC
Definition: reader_bpa.c:95