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-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 email to 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 
183  /* allocate buffer memory for storing the weights and ids temporary */
184  SCIP_CALL( SCIPallocBufferArray(scip, &weights, nitems) );
185  SCIP_CALL( SCIPallocBufferArray(scip, &ids, nitems) );
186 
187  /* pasre weights */
188  nweights = 0;
189  error = FALSE;
190 
191  while( !SCIPfeof(file) && !error )
192  {
193  /* get next line */
194  if( SCIPfgets(buffer, (int)sizeof(buffer), file) == NULL )
195  break;
196  lineno++;
197 
198  /* parse the line */
199  nread = sscanf(buffer, "%d\n", &weight);
200  if( nread == 0 )
201  {
202  SCIPwarningMessage(scip, "invalid input line %d in file <%s>: <%s>\n", lineno, filename, buffer);
203  error = TRUE;
204  break;
205  }
206 
207  SCIPdebugMsg(scip, "found weight %d <%d>\n", nweights, weight);
208  weights[nweights] = weight;
209  ids[nweights] = nweights;
210  nweights++;
211 
212  if( nweights == nitems )
213  break;
214  }
215 
216  if( nweights < nitems )
217  {
218  SCIPwarningMessage(scip, "set nitems from <%d> to <%d> since the file <%s> only contains <%d> weights\n", nitems, weights, filename, weights);
219  nitems = nweights;
220  }
221 
222  if( !error )
223  {
224  /* create a new problem in SCIP */
225  SCIP_CALL( SCIPprobdataCreate(scip, name, ids, weights, nitems, (SCIP_Longint)capacity) );
226  }
227 
228  (void)SCIPfclose(file);
229  SCIPfreeBufferArray(scip, &ids);
230  SCIPfreeBufferArray(scip, &weights);
231 
232  if( error )
233  return SCIP_READERROR;
234 
235  *result = SCIP_SUCCESS;
236 
237  return SCIP_OKAY;
238 }
239 
240 /**@} */
241 
242 
243 /**@name Interface methods
244  *
245  * @{
246  */
247 
248 /** includes the bpa file reader in SCIP */
250  SCIP* scip /**< SCIP data structure */
251  )
252 {
253  SCIP_READERDATA* readerdata;
254  SCIP_READER* reader;
255 
256  /* create binpacking reader data */
257  readerdata = NULL;
258 
259  /* include binpacking reader */
261  assert(reader != NULL);
262 
263  SCIP_CALL( SCIPsetReaderRead(scip, reader, readerReadBpa) );
264 
265  return SCIP_OKAY;
266 }
267 
268 /**@} */
#define SCIP_MAXSTRLEN
Definition: def.h:259
SCIP_RETCODE SCIPincludeReaderBpa(SCIP *scip)
Definition: reader_bpa.c:249
#define FALSE
Definition: def.h:64
#define TRUE
Definition: def.h:63
#define READER_EXTENSION
Definition: reader_bpa.c:96
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPprobdataCreate(SCIP *scip, const char *probname, int *ids, SCIP_Longint *weights, int nitems, SCIP_Longint capacity)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
Constraint handler for the set partitioning / packing / covering constraints .
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip.c:1267
#define SCIPdebugMsg
Definition: scip.h:455
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:350
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
struct SCIP_ReaderData SCIP_READERDATA
Definition: type_reader.h:37
#define SCIP_Bool
Definition: def.h:61
SCIP_RETCODE SCIPincludeReaderBasic(SCIP *scip, SCIP_READER **readerptr, const char *name, const char *desc, const char *extension, SCIP_READERDATA *readerdata)
Definition: scip.c:5264
void SCIPprintSysError(const char *message)
Definition: misc.c:9920
Problem data for binpacking problem.
Binpacking problem reader file reader.
static SCIP_DECL_READERREAD(readerReadBpa)
Definition: reader_bpa.c:108
SCIP_RETCODE SCIPsetReaderRead(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERREAD((*readerread)))
Definition: scip.c:5350
#define SCIP_Longint
Definition: def.h:134
#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