Stochastic Capacitated Facility Location Problem

Version

0.9

Author

Stephen J. Maher

This is an example of using the Benders' decomposition framework of SCIP to solve the stochastic capacitated facility location problem (abbreviated to SCFLP). The instances used for this problem are taken from the OR-Library CAP instances. These instances describe the deterministic capacitated facility location problem. The customer demands of the deterministic problem are used as the mean of the normal distribution in the stochastic program.

To use the Benders' decomposition framework to solve the SCFLP instances requires the implementation of two plugins:

• a problem reader which parses the data from the CAP instance files and provides it to the probdata plugin in a convenient format to build the problem within SCIP.
• a problem data structure which builds the problem and stores the global information. The storage of global information is not absolutely necessary in this example, but it can be useful in post processing of the solutions and checking their correctness.

The SCFLP example formulates the problem as the determinstic equivalent, which can be solved directly by SCIP and by Benders' decomposition. Initially, we will describe how to build the deterministic equivalent problem. Second, we will describe how to build the problem so that the Benders' decomposition framework can be used.

1. Problem description
2. Parsing the input format
3. Solving the deterministic equivalent using SCIP
   • Directly as a monolithic MIP
   • Applying Benders' decomposition

Installation

See the Install file