Solving Constraint Integer Programs

Parsing the input format

In the data directory you find a few data files which contain each one CAP problem. These data files have the following structure:

  • The first line specifies the number of facilities (n) and the number of customers (m).
  • The next n lines specifies for each facility the setup cost and propduction capacity.
  • The following lines state the parameters for each of the customers.
    • First, the demand of customer is given.
    • The next set of lines states the transportation cost from each facility to the customer. Each line contains 7 facilities, so there are ceil(n/7) lines for the transportation costs for each customer.

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 SCIPincludeReaderScflp() interface method

The interface method SCIPincludeReaderScflp() 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 "cap". 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 SCFLP 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.

In the READERREAD callback, the scenarios for the stochastic program are generated. A scenario represents a different realisation of demand for each customer. The scenarios are generated by sampling demands from a normal distribution with a mean given by the deterministic demand and the standard deviation sampled from a uniform distribution with the range [0.1*mean, 0.3*mean]. The number of scenarios can be set using a runtime parameter.

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_scflp.c). After that, the reader sets the result value for the SCIP_RESULT pointer to SCIP_SUCCESS and returns with a proper SCIP_RETCODE.