Solving Constraint Integer Programs

Parsing the input format and creating the problem

In the data directory you find a few data files which contain each one binpacking problem. These data files have the following structure. In the first line the name of the instance is stated. In the second line you find three integer numbers. The first one gives you the capacity \(\kappa\), the second the number of items, and the last integer states the value of a known feasible solution. This means an upper bound on the number of needed bins. The remaining lines give the size for each item.

For parsing that data, we implemented a reader plugin for SCIP. A reader has several callback methods and at least one interface methods (the one including the reader into SCIP). For our purpose we only implemented the READERREAD callback and the interface method which adds the reader plugin to SCIP.

The SCIPincludeReaderBpa() interface method

The interface method SCIPincludeReaderBpa() is called to add the reader plugin to SCIP (see cmain.c). This means SCIP gets informed that this reader is available for reading input files. Therefore, the function SCIPincludeReader() is called within this method which passes all necessary information of the reader to SCIP. This information includes the name of the reader, a description, and the file extension for which the file reader is in charge. In our case we selected the file extension "bpa". This means that all files which have this file extension are passed to our reader for parsing. Besides these information the call SCIPincludeReader() also passes for each callback of the reader a function pointers (some of them might be NULL pointers). These function pointers are used by SCIP to run the reader. For more information about all available reader callbacks we refer to the How to add file readers tutorial. In the remaining section we restrict ourself to the callback READERREAD which is the only one we implemented for the binpacking example. All other callbacks are not required for this example.

The READERREAD callback method

The READERREAD callback is in charge of parsing a file and creating the problem. To see the list of arguments this functions gets see the file type_reader.h in the source of SCIP. The following arguments are of interest in our case. First of all the SCIP pointer, the file name, and the SCIP_RESULT pointer. The SCIP pointer gives us the current environment. The file name states the file which we should open and parse. Last but not least, the SCIP_RESULT pointer is required to tell SCIP if the parsing process was successfully or not. Note that in type_reader.h you also find a list of allowable result values for the SCIP_RESULT pointer and the SCIP_RETCODE which is the return value of this function.

Parsing the problem

The file can be opened and parsed with your favorite methods. In this case we are using the functionality provided by SCIP since this has some nice side effects. We are using the function SCIPfopen() which can besides standard 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 in the source of SCIP. Parsing the data out of the file is not that hard. Please look at the code and comments therein for more details.

Creating the problem

After parsing the file the final task for the reader is to create the problem. In our case, we pass the collected data to the main problem data plugin. For this, we use the interface methods SCIPprobdataCreate() which is provided by the problem data plugin (see probdata_binpacking.c). After that, the reader sets the result value for the SCIP_RESULT pointer to SCIP_SUCCESS and returns with a proper SCIP_RETCODE.