Scippy

SCIP

Solving Constraint Integer Programs

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