1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 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_rpa.c
17 * @brief Ringpacking problem reader
18 * @author Benjamin Mueller
19 *
20 * This file implements the reader/parser used to read the ringpacking input data. For more details see \ref RINGPACKING_READER.
21 *
22 * @page RINGPACKING_READER Parsing the input format and creating the problem
23 *
24 * In the <code>data</code> directory you find a few data files which contain each one ringpacking problem. They have
25 * the following structure. In the first line the name of the instance is stated. In the second line you find three
26 * integer numbers. The first one gives you the number of different ring types \f$T\f$, the second and third the width
27 * and height of the rectangles, respectively. The remaining lines each contain one integer and two floats which
28 * together specify one ring type. The integer gives the demand and the floats correspond to the inner and outer radius
29 * of the respective type.
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 RINGPACKING_READERINCLUDE The SCIPincludeReaderRpa() interface method
36 *
37 * The interface method <code>SCIPincludeReaderRpa()</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 "rpa". 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 pointers are used by \SCIP to run the reader. For more
45 * information about all available reader callbacks we refer to the \ref READER "How to add file readers" tutorial. In
46 * the remaining section we restrict ourself to the callback <code>READERREAD</code> which is the only one we
47 * implemented for the ringpacking example. All other callbacks are not required for this example.
48 *
49 * @section RINGPACKING_READERREAD The READERREAD callback method
50 *
51 * The READERREAD callback is in charge of parsing a file and creating the problem. To see the list of arguments this
52 * functions gets to see the file type_reader.h in the source of \SCIP. The following arguments are of interest in our
53 * case. First of all the \SCIP pointer, the file name, and the SCIP_RESULT pointer. The \SCIP pointer gives us the
54 * current environment. The file name states the file which we should open and parse. Last but not least, the SCIP_RESULT
55 * pointer is required to tell \SCIP if the parsing process was successfully or not. Note that in type_reader.h you also
56 * find a list of allowable result values for the SCIP_RESULT pointer and the <code>SCIP_RETCODE</code> which is the
57 * return value of this function.
58 *
59 * @subsection RINGPACKING_PARSING Parsing the problem
60 *
61 * The file can be opened and parsed with your favorite methods. In this case we are using the functionality provided by
62 * \SCIP since this has some nice side effects. We are using the function SCIPfopen() which can besides standard
63 * 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
64 * in the source of SCIP. Parsing the data out of the file is not that hard. Please look at the code and comments
65 * therein for more details.
66 *
67 * @subsection RINGPACKING_CREATING Creating the problem
68 *
69 * After parsing the file the final task for the reader is to create the problem. In our case, we pass the collected data
70 * to the \ref probdata_rpa.h "main problem data plugin". For this, we use the interface methods
71 * SCIPprobdataCreate() which is provided by the
72 * problem data plugin (see probdata_rpa.c). After that, the reader sets the result value for the SCIP_RESULT
73 * pointer to <code>SCIP_SUCCESS</code> and returns with a proper <code>SCIP_RETCODE</code>.
74 *
75 */
76
77 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
78
79 #include <assert.h>
80 #include <string.h>
81
82 #include "reader_rpa.h"
83 #include "probdata_rpa.h"
84
85 /**@name Reader properties
86 *
87 * @{
88 */
89
90 #define READER_NAME "rpareader"
91 #define READER_DESC "file reader for ringpacking data format"
92 #define READER_EXTENSION "rpa"
93
94 /**@} */
95
96 /* default values of parameters */
97 #define DEFAULT_VERIFICATION_NLPTILIMSOFT 1e+20 /**< soft time limit for each verification NLP */
98 #define DEFAULT_VERIFICATION_NLPNODELIMSOFT 100L /**< soft node limit for each verification NLP */
99 #define DEFAULT_VERIFICATION_HEURTILIMSOFT 1e+20 /**< soft time limit for heuristic verification */
100 #define DEFAULT_VERIFICATION_HEURITERLIMSOFT 100 /**< soft iteration limit for each heuristic verification */
101 #define DEFAULT_VERIFICATION_TOTALTILIMSOFT 1e+20 /**< total time limit for all verification problems during the enumeration */
102
103
104 /**@name Callback methods
105 *
106 * @{
107 */
108
109 /** problem reading method of reader */
110 static
SCIP_DECL_READERREAD(readerReadRpa)111 SCIP_DECL_READERREAD(readerReadRpa)
112 { /*lint --e{715}*/
113 SCIP_FILE* file;
114 SCIP_Real* rints;
115 SCIP_Real* rexts;
116 int* demands;
117 SCIP_Bool error;
118 char name[SCIP_MAXSTRLEN];
119 char buffer[SCIP_MAXSTRLEN];
120 SCIP_Real width;
121 SCIP_Real height;
122 SCIP_Real r_int;
123 SCIP_Real r_ext;
124 int demand;
125 int ntypes;
126 int nread;
127 int lineno;
128 int i;
129
130 *result = SCIP_DIDNOTRUN;
131 width = -1.0;
132 height = -1.0;
133
134 /* open file */
135 file = SCIPfopen(filename, "r");
136 if( file == NULL )
137 {
138 SCIPerrorMessage("cannot open file <%s> for reading\n", filename);
139 SCIPprintSysError(filename);
140 return SCIP_NOFILE;
141 }
142
143 lineno = 0;
144 sprintf(name, "++ uninitialized ++");
145 ntypes = 0;
146
147 /* read problem dimension */
148 if( !SCIPfeof(file) )
149 {
150 /* get next line */
151 if( SCIPfgets(buffer, (int)sizeof(buffer), file) == NULL )
152 return SCIP_READERROR;
153 lineno++;
154
155 /* parse instance name line */
156 nread = sscanf(buffer, "%s", name);
157 if( nread != 1 )
158 {
159 SCIPwarningMessage(scip, "invalid input line %d in file <%s>: <%s>\n", lineno, filename, buffer);
160 return SCIP_READERROR;
161 }
162
163 /* get next line */
164 if( SCIPfgets(buffer, (int)sizeof(buffer), file) == NULL )
165 return SCIP_READERROR;
166 lineno++;
167
168 /* parse dimension line */
169 nread = sscanf(buffer, "%d %" SCIP_REAL_FORMAT " %" SCIP_REAL_FORMAT "\n", &ntypes, &width, &height);
170 if( nread < 3 )
171 {
172 SCIPwarningMessage(scip, "invalid input line %d in file <%s>: <%s>\n", lineno, filename, buffer);
173 return SCIP_READERROR;
174 }
175 }
176
177 SCIPdebugMessage("instance name = %s\n", name);
178 SCIPdebugMessage("width = %e height = %e\n", MAX(width,height), MIN(width,height));
179
180 /* allocate buffer memory for storing the demands, rints, rexts */
181 SCIP_CALL( SCIPallocBufferArray(scip, &demands, ntypes) );
182 SCIP_CALL( SCIPallocBufferArray(scip, &rints, ntypes) );
183 SCIP_CALL( SCIPallocBufferArray(scip, &rexts, ntypes) );
184
185 /* ring types */
186 r_int = 0.0;
187 r_ext = 0.0;
188 demand = 0;
189 i = 0;
190 error = FALSE;
191
192 while( !SCIPfeof(file) && !error )
193 {
194 /* get next line */
195 if( SCIPfgets(buffer, (int)sizeof(buffer), file) == NULL )
196 break;
197 lineno++;
198
199 /* parse the line */
200 nread = sscanf(buffer, "%d %" SCIP_REAL_FORMAT " %" SCIP_REAL_FORMAT "\n", &demand, &r_int, &r_ext);
201 if( nread == 0 )
202 {
203 SCIPwarningMessage(scip, "invalid input line %d in file <%s>: <%s>\n", lineno, filename, buffer);
204 error = TRUE;
205 break;
206 }
207
208 if( r_int > r_ext )
209 {
210 SCIPwarningMessage(scip, "invalid input line %d in file <%s>: internal radius is greater than the external one\n", lineno, filename);
211 error = TRUE;
212 break;
213 }
214
215 if( demand <= 0 )
216 {
217 SCIPwarningMessage(scip, "invalid input line %d in file <%s>: demand has to be positive\n", lineno, filename);
218 error = TRUE;
219 break;
220 }
221
222 demands[i] = demand;
223 rints[i] = r_int;
224 rexts[i] = r_ext;
225 ++i;
226
227 if( i == ntypes )
228 break;
229 }
230
231 if( i < ntypes )
232 {
233 SCIPwarningMessage(scip, "found %d different types of rings, needed %d\n", i, ntypes);
234 error = TRUE;
235 }
236
237 if( !SCIPisPositive(scip, width) || !SCIPisPositive(scip, height) )
238 {
239 SCIPwarningMessage(scip, "non-positive width and height = (%f, %f)!\n", width, height);
240 error = TRUE;
241 }
242
243 if( !error )
244 {
245 /* sort rings by their external radii */
246 SCIPsortDownRealRealInt(rexts, rints, demands, ntypes);
247
248 /* create and set problem data */
249 SCIP_CALL( SCIPprobdataCreate(scip, filename, demands, rints, rexts, ntypes, MAX(width,height), MIN(width,height)) );
250 SCIP_CALL( SCIPprobdataSetupProblem(scip) );
251 }
252
253 (void)SCIPfclose(file);
254 SCIPfreeBufferArray(scip, &rints);
255 SCIPfreeBufferArray(scip, &rexts);
256 SCIPfreeBufferArray(scip, &demands);
257
258 if( error )
259 return SCIP_READERROR;
260
261 *result = SCIP_SUCCESS;
262
263 return SCIP_OKAY;
264 }
265
266 /**@} */
267
268
269 /**@name Interface methods
270 *
271 * @{
272 */
273
274 /** includes the rpa file reader in SCIP */
SCIPincludeReaderRpa(SCIP * scip)275 SCIP_RETCODE SCIPincludeReaderRpa(
276 SCIP* scip /**< SCIP data structure */
277 )
278 {
279 SCIP_READERDATA* readerdata;
280 SCIP_READER* reader;
281
282 /* create ringpacking reader data */
283 readerdata = NULL;
284
285 /* include ringpacking reader */
286 SCIP_CALL( SCIPincludeReaderBasic(scip, &reader, READER_NAME, READER_DESC, READER_EXTENSION, readerdata) );
287 assert(reader != NULL);
288
289 /* add soft verification parameters */
290 SCIP_CALL( SCIPaddRealParam(scip, "ringpacking/verification/nlptilimsoft", "soft time limit for verification NLP",
291 NULL, FALSE, DEFAULT_VERIFICATION_NLPTILIMSOFT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
292
293 SCIP_CALL( SCIPaddLongintParam(scip, "ringpacking/verification/nlpnodelimsoft",
294 "soft node limit for verification NLP", NULL, FALSE,
295 DEFAULT_VERIFICATION_NLPNODELIMSOFT, 0L, SCIP_LONGINT_MAX, NULL, NULL) );
296
297 SCIP_CALL( SCIPaddRealParam(scip, "ringpacking/verification/heurtilimsoft",
298 "soft time limit for heuristic verification", NULL, FALSE,
299 DEFAULT_VERIFICATION_HEURTILIMSOFT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
300
301 SCIP_CALL( SCIPaddIntParam(scip, "ringpacking/verification/heuriterlimsoft",
302 "soft iteration limit for heuristic verification", NULL, FALSE,
303 DEFAULT_VERIFICATION_HEURITERLIMSOFT, 0, INT_MAX, NULL, NULL) );
304
305 SCIP_CALL( SCIPaddRealParam(scip, "ringpacking/verification/totaltilimsoft",
306 "total time limit for all verification problems during the enumeration", NULL, FALSE,
307 DEFAULT_VERIFICATION_TOTALTILIMSOFT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
308
309 SCIP_CALL( SCIPsetReaderRead(scip, reader, readerReadRpa) );
310
311 return SCIP_OKAY;
312 }
313
314 /**@} */
315