probdata_scflp.c
Go to the documentation of this file.
29 * This file handles the main problem data used in that project. For more details see \ref SCFLP_PROBLEMDATA page.
33 * The probdata_scflp.c is used to store the global problem data and build the monolithic MIP and decomposed problems.
34 * First, the structure of the problem data is describe. This is followed by a description of how to solve the problem
39 * The problem data is accessible in all plugins. The function SCIPgetProbData() returns the pointer to that structure.
40 * We use this data structure to store all the information of the SCFLP. Since this structure is not visible in the
41 * other plugins, we implemented setter and getter functions to access this data. The problem data structure
47 * * This problem data is used to store the input of the cap instance, all variables which are created, and all
48 * * constraints. In addition, the probdata stores the data structures for the decomposed problem. This permits the
56 * SCIP_VAR**** customervars; **< all variables representing the satisfaction of demand per scenario *
59 * SCIP_CONS* sufficientcap; **< ensuring sufficient capacity is provided to satisfy demand (relatively complete recourse) *
71 * The function SCIPprobdataCreate() manages the creation of the SCFLP instance in SCIP. There are two types of
72 * formulations that can be produced in this example. The first is the monolithic deterministic equivalent. The second
73 * is the reformulated problem that decomposes the stochastic problem by scenarios. This alternative formulations is
74 * solved using Benders' decomposition. Depending on the solution method, some members of SCIP_ProbData will be unused.
75 * For example, subproblems and subfacilityvars are only used when Benders' decomposition is applied to solve the SCFLP.
77 * The probdata_scflp.c also provide interface methods to the global problem data. A list of all interface methods can be
82 * Within probdata_scflp.c, both the monolithic determinstic equivalent or the decomposed problem can be built within
83 * SCIP. The monolithic deterministic equivalent involve a since SCIP instances that is solved directly as a MIP. The
88 * The model that is used to build the decomposed problem is given in \ref SCFLP_BENDERSMODEL. In this example, the
89 * default Benders' decomposition plugin is used to employ the Benders' decomposition framework, see
90 * src/scip/benders_default.h. Before calling SCIPcreateBendersDefault() to invoke the Benders' decomposition framework,
93 * The SCIP instance for the master problem includes only the first stage variables (the facility variables \f$x_{i}\f$)
94 * and the first stage constraints. Note, the auxiliary variables are not added to the master problem by the user, nor
97 * For each subproblem \f$s\f$, the SCIP instance is formulated with the second stage variables (the customer variables
98 * \f$y^{s}_{ij}\f$) and the second stage constraints. Also, the first stage variables are created for each scenario.
99 * These variables are copies of the master variables from the master SCIP instances and must be created by calling
100 * SCIPcreateVarBasic() or SCIPcreateVar(). The master problem variable copies that are created in the subproblem SCIP
101 * instances must have an objective coefficient of 0.0. This is inline with the classical application of Benders'
104 * IMPORTANT: the master variables that are created for the subproblem SCIP instances must have the same name as the
105 * corresponding master variables in the master problem SCIP instance. This is because the mapping between the master
106 * and subproblem variables relies on the variable names. This mapping is used for setting up the subproblems to
109 * Once the master and subproblem SCIP instances are created, the Benders' decomposition is invoked by calling the
110 * interface function SCIPcreateBendersDefault(). The parameters for this function are a SCIP instance for the master
113 * The Benders' decomposition framework involves the use of constraint handlers within SCIP, src/scip/cons_benders.h and
114 * src/scip/cons_benderslp.h. In order to solve the master problem by adding Benders' cuts, src/scip/cons_benders.h and
115 * src/scip/cons_benderslp.h must be activated. This is done by setting the parameter "constraints/benders/active" and
118 * NOTE: it is not necessary to activate src/scip/cons_benderslp.h. The purpose of this constraint handler is to
119 * generate Benders' decomposition cut from solutions to the LP relaxation in the root node. These solutions are
120 * fractional, since the enforcement priority of benderslp is higher than the integer constraint handler. The benderslp
121 * constraint handler allows the user to employ the multi-phase algorithm of McDaniel and Devine (1977).
123 * McDaniel D, Devine M. A modified Benders’ partitioning algorithm for mixed integer programming. Management Science
127 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
140 * This problem data is used to store the input of the SCFLP, all variables which are created, and all constraints.
147 SCIP_VAR**** customervars; /**< all variables representing the satisfaction of demand per scenario */
150 SCIP_CONS* sufficientcap; /**< ensuring sufficient capacity is provided to satisfy demand (relatively complete recourse) */
219 SCIP_CALL( SCIPcreateConsBasicLinear(scip, sufficientcap, name, 0, NULL, NULL, maxdemand, SCIPinfinity(scip)) );
229 SCIP_CALL( SCIPcreateConsBasicLinear(scip, &cons, name, 0, NULL, NULL, -SCIPinfinity(scip), 0.0) );
243 SCIP_CALL( SCIPcreateConsBasicLinear(scip, &cons, name, 0, NULL, NULL, demands[i][j], SCIPinfinity(scip)) );
278 /* if the quadratic costs are used, then the customer coefficient is zero and the quadratic costs are scaled
303 /* if the quadratic costs are used, then variables representing the square of the customer supply
309 SCIP_CALL( SCIPcreateVarBasic(scip, &sqrvar, name, 0.0, SCIPinfinity(scip), coeff, SCIP_VARTYPE_CONTINUOUS) );
315 SCIP_CALL( SCIPcreateConsQuadraticNonlinear(scip, &cons, name, 1, &sqrvar, &minusone, 1, &var, &var,
352 SCIPmessagePrintVerbInfo(SCIPgetMessagehdlr(scip), SCIPgetVerbLevel(scip), SCIP_VERBLEVEL_NORMAL,
368 SCIP_CALL( SCIPcreateConsBasicLinear(scip, sufficientcap, name, 0, NULL, NULL, maxdemand, SCIPinfinity(scip)) );
387 SCIPmessagePrintVerbInfo(SCIPgetMessagehdlr(scip), SCIPgetVerbLevel(scip), SCIP_VERBLEVEL_NORMAL,
428 SCIPmessagePrintVerbInfo(SCIPgetMessagehdlr(scip), SCIPgetVerbLevel(scip), SCIP_VERBLEVEL_NORMAL,
437 SCIP_CALL( SCIPcreateConsBasicLinear(subproblems[j], &cons, name, 0, NULL, NULL, -SCIPinfinity(subproblems[j]), 0.0) );
451 SCIP_CALL( SCIPcreateConsBasicLinear(subproblems[j], &cons, name, 0, NULL, NULL, demands[i][j], SCIPinfinity(subproblems[j])) );
464 SCIP_CALL( SCIPcreateVarBasic(subproblems[j], &var, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_CONTINUOUS) );
472 SCIP_CALL( SCIPaddCoefLinear(subproblems[j], capconss[i][j], subfacilityvars[i][j], -capacity[i]) );
485 /* if the quadratic costs are used, then the customer coefficient is zero and the quadratic costs are scaled
494 SCIP_CALL( SCIPcreateVarBasic(subproblems[k], &var, name, 0.0, SCIPinfinity(subproblems[k]), custcoeff,
511 /* if the quadratic costs are used, then variables representing the square of the customer supply
518 SCIP_CALL( SCIPcreateVarBasic(subproblems[k], &sqrvar, name, 0.0, SCIPinfinity(subproblems[k]), coeff, SCIP_VARTYPE_CONTINUOUS) );
524 SCIP_CALL( SCIPcreateConsQuadraticNonlinear(subproblems[k], &cons, name, 1, &sqrvar, &minusone, 1, &var, &var, &one, -SCIPinfinity(subproblems[k]), 0.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE) );
536 SCIPmessagePrintVerbInfo(SCIPgetMessagehdlr(scip), SCIPgetVerbLevel(scip), SCIP_VERBLEVEL_NORMAL,
537 "%d subproblems have been created.\neach subproblem has %d continuous variables and %d constraint\n\n",
579 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*probdata)->subproblems, subproblems, nscenarios) );
583 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*probdata)->subfacilityvars[i], subfacilityvars[i], nscenarios) );
587 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*probdata)->facilityvars, facilityvars, nfacilities) );
593 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*probdata)->customervars[i][j], customervars[i][j],
600 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*probdata)->capconss[i], capconss[i], nscenarios) );
604 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*probdata)->demandconss[i], demandconss[i], nscenarios) );
609 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*probdata)->demands[i], demands[i], nscenarios) );
613 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*probdata)->costs[i], costs[i], nfacilities) );
615 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*probdata)->capacity, capacity, nfacilities) );
616 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*probdata)->fixedcost, fixedcost, nfacilities) );
856 /* if quadratic costs are used, then the costs are scaled by 10,000. The user must be informed about this scaling */
886 SCIP_CALL( createMasterproblem(scip, facilityvars, &sufficientcap, capacity, fixedcost, demands, ncustomers,
888 SCIP_CALL( createSubproblems(scip, subproblems, facilityvars, subfacilityvars, customervars, capconss,
889 demandconss, costs, demands, capacity, fixedcost, ncustomers, nfacilities, nscenarios, quadcosts) );
904 SCIP_CALL( createOriginalproblem(scip, facilityvars, customervars, capconss, demandconss, &sufficientcap, costs,
909 SCIP_CALL( probdataCreate(scip, &probdata, subproblems, facilityvars, subfacilityvars, customervars, capconss,
910 demandconss, sufficientcap, costs, demands, capacity, fixedcost, ncustomers, nfacilities, nscenarios,
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
Definition: cons_linear.c:18040
Definition: struct_scip.h:68
SCIP_RETCODE SCIPprobdataCreate(SCIP *scip, const char *probname, SCIP_Real **costs, SCIP_Real **demands, SCIP_Real *capacity, SCIP_Real *fixedcost, int ncustomers, int nfacilities, int nscenarios, SCIP_Bool usebenders, SCIP_Bool quadcosts)
Definition: probdata_scflp.c:798
Definition: struct_var.h:207
SCIP_RETCODE SCIPcreateBendersDefault(SCIP *scip, SCIP **subproblems, int nsubproblems)
Definition: benders_default.c:485
Definition: type_var.h:62
int SCIPprobdataGetNCustomers(SCIP_PROBDATA *probdata)
Definition: probdata_scflp.c:957
SCIP_RETCODE SCIPsetProbData(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: scip_prob.c:1022
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition: scip_var.c:194
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
Definition: cons_linear.c:18192
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition: scip_prob.c:180
int SCIPprobdataGetNFacilities(SCIP_PROBDATA *probdata)
Definition: probdata_scflp.c:947
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
Definition: scip_prob.c:1250
static SCIP_RETCODE createSubproblems(SCIP *scip, SCIP **subproblems, SCIP_VAR **facilityvars, SCIP_VAR ***subfacilityvars, SCIP_VAR ****customervars, SCIP_CONS ***capconss, SCIP_CONS ***demandconss, SCIP_Real **costs, SCIP_Real **demands, SCIP_Real *capacity, SCIP_Real *fixedcost, int ncustomers, int nfacilities, int nscenarios, SCIP_Bool quadcosts)
Definition: probdata_scflp.c:395
Definition: struct_cons.h:46
void SCIPmessagePrintVerbInfo(SCIP_MESSAGEHDLR *messagehdlr, SCIP_VERBLEVEL verblevel, SCIP_VERBLEVEL msgverblevel, const char *formatstr,...)
Definition: message.c:678
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:429
SCIP_RETCODE SCIPcreateConsQuadraticNonlinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nquadterms, SCIP_VAR **quadvars1, SCIP_VAR **quadvars2, SCIP_Real *quadcoefs, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable)
Definition: cons_nonlinear.c:11219
Definition: type_retcode.h:42
Problem data for Stochastic Capacitated Facility Location problem.
static SCIP_RETCODE createOriginalproblem(SCIP *scip, SCIP_VAR **facilityvars, SCIP_VAR ****customervars, SCIP_CONS ***capconss, SCIP_CONS ***demandconss, SCIP_CONS **sufficientcap, SCIP_Real **costs, SCIP_Real **demands, SCIP_Real *capacity, SCIP_Real *fixedcost, int ncustomers, int nfacilities, int nscenarios, SCIP_Bool quadcosts)
Definition: probdata_scflp.c:173
Definition: type_message.h:53
SCIP_RETCODE SCIPsetProbTrans(SCIP *scip, SCIP_DECL_PROBTRANS((*probtrans)))
Definition: scip_prob.c:221
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
Definition: scipdefplugins.c:37
static SCIP_RETCODE probdataFree(SCIP *scip, SCIP_PROBDATA **probdata)
Definition: probdata_scflp.c:630
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:487
SCIP_VAR ** SCIPprobdataGetFacilityVars(SCIP_PROBDATA *probdata)
Definition: probdata_scflp.c:967
static SCIP_DECL_PROBDELTRANS(probdeltransScflp)
Definition: probdata_scflp.c:782
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1119
static SCIP_RETCODE probdataCreate(SCIP *scip, SCIP_PROBDATA **probdata, SCIP **subproblems, SCIP_VAR **facilityvars, SCIP_VAR ***subfacilityvars, SCIP_VAR ****customervars, SCIP_CONS ***capconss, SCIP_CONS ***demandconss, SCIP_CONS *sufficientcap, SCIP_Real **costs, SCIP_Real **demands, SCIP_Real *capacity, SCIP_Real *fixedcost, int ncustomers, int nfacilities, int nscenarios, SCIP_Bool usebenders, SCIP_Bool quadcosts)
Definition: probdata_scflp.c:546
static SCIP_RETCODE createMasterproblem(SCIP *scip, SCIP_VAR **facilityvars, SCIP_CONS **sufficientcap, SCIP_Real *capacity, SCIP_Real *fixedcost, SCIP_Real **demands, int ncustomers, int nfacilities, int nscenarios)
Definition: probdata_scflp.c:333
SCIP_RETCODE SCIPsetProbDeltrans(SCIP *scip, SCIP_DECL_PROBDELTRANS((*probdeltrans)))
Definition: scip_prob.c:242
SCIP_RETCODE SCIPsetProbDelorig(SCIP *scip, SCIP_DECL_PROBDELORIG((*probdelorig)))
Definition: scip_prob.c:200
Definition: type_prob.h:48
Definition: objbenders.h:43
default SCIP plugins
SCIP callable library.
Definition: type_var.h:67