The probdata_scflp.c is used to store the global problem data and build the monolithic MIP and decomposed problems. First, the structure of the problem data is describe. This is followed by a description of how to solve the problem directly using SCIP or using Benders' decomposition.

The global problem data

The problem data is accessible in all plugins. The function SCIPgetProbData() returns the pointer to that structure. We use this data structure to store all the information of the SCFLP. Since this structure is not visible in the other plugins, we implemented setter and getter functions to access this data. The problem data structure SCIP_ProbData is shown below.

 ** @brief Problem data which is accessible in all places
 *
 *   This problem data is used to store the input of the cap instance, all variables which are created, and all
 *   constraints. In addition, the probdata stores the data structures for the decomposed problem. This permits the
 *   use of Benders' decomposition to solve the stochastic program.
 *
struct SCIP_ProbData
{
   SCIP**                subproblems;        **< the Benders' decomposition subproblems * SCIP_VAR**
   SCIP_VAR**            facilityvars;       **< all variables representing facilities *
   SCIP_VAR***           subfacilityvars;    **< duplicates of the facility variables in the subproblems *
   SCIP_VAR****          customervars;       **< all variables representing the satisfaction of demand per scenario *
   SCIP_CONS***          capconss;           **< capacity constraints per facility per scenario *
   SCIP_CONS***          demandconss;        **< demand constraints per customer per scenario *
   SCIP_CONS*            sufficientcap;      **< ensuring sufficient capacity is provided to satisfy demand (relatively complete recourse) *
   SCIP_Real**           costs;              **< the transportation costs to a customer from a facility *
   SCIP_Real**           demands;            **< the customer demands per scenario *
   SCIP_Real*            capacity;           **< the capacity of each facility *
   SCIP_Real*            fixedcost;          **< the fixed cost of opening each facility *
   int                   ncustomers;         **< the number of customers *
   int                   nfacilities;        **< the number of facilities *
   int                   nscenarios;         **< the number of scenarios *
   SCIP_Bool             usebenders;         **< whether Benders' decomposition is used *
};

The function SCIPprobdataCreate() manages the creation of the SCFLP instance in SCIP. There are two types of formulations that can be produced in this example. The first is the monolithic deterministic equivalent. The second is the reformulated problem that decomposes the stochastic problem by scenarios. This alternative formulations is solved using Benders' decomposition. Depending on the solution method, some members of SCIP_ProbData will be unused. For example, subproblems and subfacilityvars are only used when Benders' decomposition is applied to solve the SCFLP.

The probdata_scflp.c also provide interface methods to the global problem data. A list of all interface methods can be found in probdata_scflp.h.

Directly solving the deterministic equivalent using SCIP

Within probdata_scflp.c, both the monolithic determinstic equivalent or the decomposed problem can be built within SCIP. The monolithic deterministic equivalent involve a since SCIP instances that is solved directly as a MIP. The problem that is build in SCIP is given in The deterministic equivalent.

Solving the SCFLP using Benders' decomposition

The model that is used to build the decomposed problem is given in Applying Benders' decomposition to the SCFLP. In this example, the default Benders' decomposition plugin is used to employ the Benders' decomposition framework, see src/scip/benders_default.h. Before calling SCIPcreateBendersDefault() to invoke the Benders' decomposition framework, the SCIP instances for the master problem and the subproblems must be created.

The SCIP instance for the master problem includes only the first stage variables (the facility variables \(x_{i}\)) and the first stage constraints. Note, the auxiliary variables are not added to the master problem by the user, nor are any Benders' decomposition cuts.

For each subproblem \(s\), the SCIP instance is formulated with the second stage variables (the customer variables \(y^{s}_{ij}\)) and the second stage constraints. Also, the first stage variables are created for each scenario. These variables are copies of the master variables from the master SCIP instances and must be created by calling SCIPcreateVarBasic() or SCIPcreateVar(). The master problem variable copies that are created in the subproblem SCIP instances must have an objective coefficient of 0.0. This is inline with the classical application of Benders' decomposition.

IMPORTANT: the master variables that are created for the subproblem SCIP instances must have the same name as the corresponding master variables in the master problem SCIP instance. This is because the mapping between the master and subproblem variables relies on the variable names. This mapping is used for setting up the subproblems to evaluate solutions from the master problem and generating Benders' cuts.

Once the master and subproblem SCIP instances are created, the Benders' decomposition is invoked by calling the interface function SCIPcreateBendersDefault(). The parameters for this function are a SCIP instance for the master problem, an array of SCIP instances for the subproblems and the number of subproblems.

The Benders' decomposition framework involves the use of constraint handlers within SCIP, src/scip/cons_benders.h and src/scip/cons_benderslp.h. In order to solve the master problem by adding Benders' cuts, src/scip/cons_benders.h and src/scip/cons_benderslp.h must be activated. This is done by setting the parameter "constraints/benders/active" and "constraints/benderslp/active" to TRUE.

NOTE: it is not necessary to activate src/scip/cons_benderslp.h. The purpose of this constraint handler is to generate Benders' decomposition cut from solutions to the LP relaxation in the root node. These solutions are fractional, since the enforcement priority of benderslp is higher than the integer constraint handler. The benderslp constraint handler allows the user to employ the multi-phase algorithm of McDaniel and Devine (1977).

McDaniel D, Devine M. A modified Benders’ partitioning algorithm for mixed integer programming. Management Science 1977;24(2):312–9