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 (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
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)) );
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 */
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 */
287  assert(reader != NULL);
288 
289  /* add soft verification parameters */
290  SCIP_CALL( SCIPaddRealParam(scip, "ringpacking/verification/nlptilimsoft", "soft time limit for verification NLP",
292 
293  SCIP_CALL( SCIPaddLongintParam(scip, "ringpacking/verification/nlpnodelimsoft",
294  "soft node limit for verification NLP", NULL, FALSE,
296 
297  SCIP_CALL( SCIPaddRealParam(scip, "ringpacking/verification/heurtilimsoft",
298  "soft time limit for heuristic verification", NULL, FALSE,
300 
301  SCIP_CALL( SCIPaddIntParam(scip, "ringpacking/verification/heuriterlimsoft",
302  "soft iteration limit for heuristic verification", NULL, FALSE,
304 
305  SCIP_CALL( SCIPaddRealParam(scip, "ringpacking/verification/totaltilimsoft",
306  "total time limit for all verification problems during the enumeration", NULL, FALSE,
308 
309  SCIP_CALL( SCIPsetReaderRead(scip, reader, readerReadRpa) );
310 
311  return SCIP_OKAY;
312 }
313 
314 /**@} */
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
#define SCIP_MAXSTRLEN
Definition: def.h:279
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:123
Problem data for ringpacking problem.
SCIP_RETCODE SCIPsetReaderRead(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERREAD((*readerread)))
Definition: scip_reader.c:186
#define FALSE
Definition: def.h:73
#define READER_EXTENSION
Definition: reader_rpa.c:92
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
#define DEFAULT_VERIFICATION_HEURTILIMSOFT
Definition: reader_rpa.c:99
#define DEFAULT_VERIFICATION_TOTALTILIMSOFT
Definition: reader_rpa.c:101
SCIP_RETCODE SCIPincludeReaderRpa(SCIP *scip)
Definition: reader_rpa.c:275
#define SCIPdebugMessage
Definition: pub_message.h:87
#define SCIP_LONGINT_MAX
Definition: def.h:149
#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)
#define SCIP_REAL_FORMAT
Definition: def.h:166
SCIP_FILE * SCIPfopen(const char *path, const char *mode)
Definition: fileio.c:144
#define SCIPerrorMessage
Definition: pub_message.h:55
int SCIPfeof(SCIP_FILE *stream)
Definition: fileio.c:218
struct SCIP_File SCIP_FILE
Definition: pub_fileio.h:34
char * SCIPfgets(char *s, int size, SCIP_FILE *stream)
Definition: fileio.c:191
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_EXPORT void SCIPsortDownRealRealInt(SCIP_Real *realarray1, SCIP_Real *realarray2, int *intarray, int len)
#define SCIP_CALL(x)
Definition: def.h:370
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
struct SCIP_ReaderData SCIP_READERDATA
Definition: type_reader.h:44
#define SCIP_Bool
Definition: def.h:70
#define DEFAULT_VERIFICATION_NLPTILIMSOFT
Definition: reader_rpa.c:97
#define MAX(x, y)
Definition: tclique_def.h:83
SCIP_RETCODE SCIPincludeReaderBasic(SCIP *scip, SCIP_READER **readerptr, const char *name, const char *desc, const char *extension, SCIP_READERDATA *readerdata)
Definition: scip_reader.c:100
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:130
#define SCIP_REAL_MAX
Definition: def.h:164
#define DEFAULT_VERIFICATION_HEURITERLIMSOFT
Definition: reader_rpa.c:100
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:74
#define SCIP_Real
Definition: def.h:163
void SCIPprintSysError(const char *message)
Definition: misc.c:10513
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:102
#define READER_DESC
Definition: reader_rpa.c:91
static SCIP_DECL_READERREAD(readerReadRpa)
Definition: reader_rpa.c:111
#define DEFAULT_VERIFICATION_NLPNODELIMSOFT
Definition: reader_rpa.c:98
int SCIPfclose(SCIP_FILE *fp)
Definition: fileio.c:223
#define READER_NAME
Definition: reader_rpa.c:90
SCIP_RETCODE SCIPprobdataSetupProblem(SCIP *scip)