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