Scippy

SCIP

Solving Constraint Integer Programs

benders_default.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2018 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file benders_default.c
17  * @brief default Benders' decomposition plugin
18  * @author Stephen J. Maher
19  *
20  * The default Benders' decomposition plugin is provided to simplify the interaction the Benders' decomposition
21  * framework within SCIP. This plugin is included in the SCIP package by default. Using the default Benders'
22  * decomposition plugin, a problem can be solved by Benders' decomposition by calling
23  *
24  * SCIPcreateBendersDefault(master problem, array of subproblems, number of subproblems)
25  *
26  * where "master problem" is a SCIP instance of the master problem, "array of subproblems" is an array of SCIP instances
27  * that are the Benders' decomposition subproblems and "number of subproblems" is an integer indicating the number of
28  * subproblems for this decomposition.
29  *
30  * A key feature of the default Benders' decomposition plugin is the automatic generation of the variable mapping
31  * between the variables of the master problem and the subproblems.
32  *
33  * In the traditional application of Benders' decomposition, master problem variables are fixed to a solution value and
34  * modify the RHS of the second stage constraints. The implementation within SCIP requires that a variable is created
35  * in the subproblem for every master problem variable that appears in the subproblem constraints. This variable MUST
36  * have the same name as the corresponding variable in the master problem. This name is used to automatically generate
37  * the mapping between the master problem and the corresponding subproblem variables.
38  *
39  */
40 
41 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
42 
43 #include "scip/benders_default.h"
44 #include "scip/bendersdefcuts.h"
45 #include "scip/pub_benders.h"
46 #include "scip/pub_message.h"
47 #include "scip/pub_misc.h"
48 #include "scip/pub_var.h"
49 #include "scip/scip_benders.h"
50 #include "scip/scip_copy.h"
51 #include "scip/scip_mem.h"
52 #include "scip/scip_param.h"
53 #include "scip/scip_prob.h"
54 
55 #define BENDERS_NAME "default"
56 #define BENDERS_DESC "default implementation of Benders' decomposition"
57 #define BENDERS_PRIORITY 0
58 #define BENDERS_CUTLP TRUE /**< should Benders' cut be generated for LP solutions */
59 #define BENDERS_CUTPSEUDO TRUE /**< should Benders' cut be generated for pseudo solutions */
60 #define BENDERS_CUTRELAX TRUE /**< should Benders' cut be generated for relaxation solutions */
61 #define BENDERS_SHAREAUXVARS FALSE /**< should this Benders' share the highest priority Benders' aux vars */
62 
63 
64 /*
65  * Data structures
66  */
67 
68 /** Benders' decomposition data */
69 struct SCIP_BendersData
70 {
71  SCIP** subproblems; /**< the Benders' decomposition subproblems */
72  SCIP_HASHMAP* mastervartosubindex;/**< hash map from the master variable to an index for the subproblemn variables */
73  SCIP_HASHMAP* subvartomastervar; /**< hashmap from the subproblem variable to the master variable */
74  SCIP_VAR*** subproblemvars; /**< the subproblem variables corresponding to master problem variables */
75  int nmastervars; /**< the number of variables in the master problem */
76  int nsubproblems; /**< the number of subproblems */
77  SCIP_Bool created; /**< flag to indicate that the Benders' decomposition Data was created */
78 };
79 
80 
81 
82 
83 /*
84  * Local methods
85  */
86 
87 /** creates the Benders' decomposition data */
88 static
90  SCIP* scip, /**< SCIP data structure */
91  SCIP** subproblems, /**< the Benders' decomposition subproblems */
92  SCIP_BENDERSDATA** bendersdata, /**< the Benders' decomposition data */
93  int nsubproblems /**< the number of subproblems in the Benders' decomposition */
94  )
95 {
96  int i;
97 
98  assert(scip != NULL);
99  assert(subproblems != NULL);
100 
101  (*bendersdata)->nsubproblems = nsubproblems;
102 
103  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*bendersdata)->subproblems, nsubproblems) );
104 
105  /* Copying the subproblem to the Benders' decomposition data. */
106  for( i = 0; i < nsubproblems; i++ )
107  (*bendersdata)->subproblems[i] = subproblems[i];
108 
109  (*bendersdata)->created = TRUE;
110 
111  return SCIP_OKAY;
112 }
113 
114 
115 /** Creates the variable mappings between the master problem and the corresponding variable in the subproblem.
116  *
117  * TODO: add the functionality to allow the user to provide an array of hashmaps for mapping between the master problem
118  * variables and the corresponding subproblem variables.
119  * TODO: check for uniqueness of names in this function.
120  */
121 static
123  SCIP* scip, /**< SCIP data structure */
124  SCIP_BENDERS* benders /**< the Benders' decomposition structure */
125  )
126 {
127  SCIP_BENDERSDATA* bendersdata;
128  SCIP_VAR** vars;
129  int nsubproblems;
130  int nvars;
131  char varname[SCIP_MAXSTRLEN];
132  int i;
133  int j;
134 
135  assert(scip != NULL);
136  assert(benders != NULL);
137 
138  bendersdata = SCIPbendersGetData(benders);
139  assert(bendersdata != NULL);
140 
141  nsubproblems = bendersdata->nsubproblems;
142 
143  /* getting the master problem variable data */
144  vars = SCIPgetVars(scip);
145  nvars = SCIPgetNVars(scip);
146 
147  bendersdata->nmastervars = nvars;
148 
149  /* creating the hashmaps for the mapping between the master variables and the sub variables */
150  SCIP_CALL( SCIPhashmapCreate(&bendersdata->mastervartosubindex, SCIPblkmem(scip), nvars) );
151  SCIP_CALL( SCIPhashmapCreate(&bendersdata->subvartomastervar, SCIPblkmem(scip), nvars*nsubproblems) );
152  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &bendersdata->subproblemvars, nsubproblems) );
153  for( i = 0; i < nsubproblems; i++ )
154  {
155  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &bendersdata->subproblemvars[i], nvars) );
156  }
157 
158  /* this loop stores a mapping between the master problem variables and their counterpart in the subproblems. For each
159  * master problem variable, the variable name is used to search for any corresponding variables in each of the
160  * subproblems. If a corresponding variable exists, then a mapping is inserted into subvartomastervar and
161  * mastervartosubvar hashmaps
162  */
163  for( i = 0; i < nvars; i++ )
164  {
165  SCIP_VAR* origvar;
166  SCIP_VAR* subvar;
167  SCIP_Real scalar;
168  SCIP_Real constant;
169  const char* origvarname;
170  int charcount = SCIPgetSubscipDepth(scip)*2;
171 
172  /* getting the original variable for the master variable
173  * NOTE: This retrieved variable is the original variable. It may be a bug in regards to other parts of the code.
174  * The process maps the subproblem variable to the original master variable. It was original supposed to be a
175  * mapping between the subproblem variables and the transformed master variable.
176  */
177  origvar = vars[i];
178  scalar = 1.0;
179  constant = 0.0;
180  SCIP_CALL( SCIPvarGetOrigvarSum(&origvar, &scalar, &constant) );
181 
182  /* retrieving the var name */
183  origvarname = SCIPvarGetName(origvar);
184  (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "%s", &origvarname[charcount]);
185 
186  /* retrieving the subproblem variable for the given master variable */
187  for( j = 0; j < nsubproblems; j++ )
188  {
189  /* find the corresponding subproblem variable for a given master problem variable using the variable name. */
190  subvar = SCIPfindVar(bendersdata->subproblems[j], varname);
191 
192  /* adding the subvariable to master variable mapping into the hash map */
193  if( subvar != NULL )
194  {
195  SCIP_CALL( SCIPhashmapInsert(bendersdata->subvartomastervar, subvar, origvar) );
196  }
197 
198  /* storing the subproblem variable */
199  bendersdata->subproblemvars[j][i] = subvar;
200  }
201 
202  /* storing the mapping of the master variable to the variable index */
203  SCIP_CALL( SCIPhashmapInsert(bendersdata->mastervartosubindex, vars[i], (void*)(size_t) i) );
204  }
205 
206  return SCIP_OKAY;
207 }
208 
209 
210 
211 /*
212  * Callback methods for Benders' decomposition
213  */
214 
215 /** copy method for Benders' decomposition plugins (called when SCIP copies plugins) */
216 static
217 SCIP_DECL_BENDERSCOPY(bendersCopyDefault)
218 { /*lint --e{715}*/
219  SCIP_BENDERSDATA* bendersdata; /* the source Benders' decomposition data */
220 
221  assert(scip != NULL);
222  assert(benders != NULL);
223 
224  bendersdata = SCIPbendersGetData(benders);
225 
226  /* including the Benders' decomposition in the target SCIP.
227  * NOTE: this method uses the same subproblems as the main SCIP. In a parallel setting, this will not be thread safe.
228  * It would be cleaner to copy the subproblems also.
229  */
231 
232  /* if the Benders' decomposition is active, then it must be created in the copy */
233  if( SCIPbendersIsActive(benders) )
234  {
235  SCIP_CALL( SCIPcreateBendersDefault(scip, bendersdata->subproblems, bendersdata->nsubproblems) );
236  }
237 
238  return SCIP_OKAY;
239 }
240 
241 /** destructor of Benders' decomposition to free user data (called when SCIP is exiting) */
242 /**! [SnippetBendersFreeDefault] */
243 static
244 SCIP_DECL_BENDERSFREE(bendersFreeDefault)
245 { /*lint --e{715}*/
246  SCIP_BENDERSDATA* bendersdata;
247  int i;
248 
249  assert(scip != NULL);
250  assert(benders != NULL);
251 
252  bendersdata = SCIPbendersGetData(benders);
253 
254  assert(bendersdata != NULL);
255 
256  if( bendersdata->created )
257  {
258  for( i = bendersdata->nsubproblems - 1; i >= 0; i-- )
259  SCIPfreeBlockMemoryArray(scip, &bendersdata->subproblemvars[i], bendersdata->nmastervars);
260  SCIPfreeBlockMemoryArray(scip, &bendersdata->subproblemvars, bendersdata->nsubproblems);
261 
262  /* free hash map */
263  SCIPhashmapFree(&bendersdata->subvartomastervar);
264  SCIPhashmapFree(&bendersdata->mastervartosubindex);
265 
266  SCIPfreeBlockMemoryArray(scip, &bendersdata->subproblems, bendersdata->nsubproblems);
267  }
268 
269  SCIPfreeBlockMemory(scip, &bendersdata);
270 
271  return SCIP_OKAY;
272 }
273 /**! [SnippetBendersFreeDefault] */
274 
275 
276 /** initialization method of Benders' decomposition (called after problem was transformed) */
277 static
278 SCIP_DECL_BENDERSINIT(bendersInitDefault)
279 { /*lint --e{715}*/
280  assert(scip != NULL);
281  assert(benders != NULL);
282 
283  /* creating the variable mappings */
285 
286  return SCIP_OKAY;
287 }
288 
289 
290 /** mapping method between the master problem variables and the subproblem variables of Benders' decomposition */
291 /**! [SnippetBendersGetvarDefault] */
292 static
293 SCIP_DECL_BENDERSGETVAR(bendersGetvarDefault)
294 { /*lint --e{715}*/
295  SCIP_BENDERSDATA* bendersdata;
296  SCIP_VAR* origvar;
297  SCIP_Real scalar;
298  SCIP_Real constant;
299 
300  assert(scip != NULL);
301  assert(benders != NULL);
302  assert(var != NULL);
303  assert(mappedvar != NULL);
304 
305  bendersdata = SCIPbendersGetData(benders);
306 
307  if( probnumber == -1 )
308  {
309  origvar = var;
310  /* The variable needs to be transformed back into an original variable. If the variable is already original, then
311  * this function just returns the same variable
312  */
313  SCIP_CALL( SCIPvarGetOrigvarSum(&origvar, &scalar, &constant) );
314 
315  /* using the original variable, the master variable can be retrieved from the hash map */
316  (*mappedvar) = (SCIP_VAR*) SCIPhashmapGetImage(bendersdata->subvartomastervar, origvar);
317 
318  if( (*mappedvar) == NULL )
319  (*mappedvar) = (SCIP_VAR*) SCIPhashmapGetImage(bendersdata->subvartomastervar, var);
320  }
321  else
322  {
323  int masterindex;
324  /* The variable needs to be transformed back into an original variable. If the variable is already original, then
325  * this function just returns the same variable
326  */
327 
328  /* we are requesting the subproblem variable for a master problem variable
329  * The master problem variable is a transformed variable. The original variable is not required.
330  * NOTE: Currently the original variable is being used. This may not be correct and should be the transformed
331  * variable.
332  */
333  masterindex = (int)(size_t) SCIPhashmapGetImage(bendersdata->mastervartosubindex, var);
334  (*mappedvar) = bendersdata->subproblemvars[probnumber][masterindex];
335  }
336 
337  return SCIP_OKAY;
338 }
339 /**! [SnippetBendersGetvarDefault] */
340 
341 /** the method for creating the Benders' decomposition subproblem. This method is called during the initialisation stage
342  * (after the master problem was transformed)
343  *
344  * This method must create the SCIP instance for the subproblem and add the required variables and constraints. In
345  * addition, the settings required for the solving the problem must be set here. However, some settings will be
346  * overridden by the standard solving method included in the Benders' decomposition framework. If a special solving
347  * method is desired, the user can implement the bendersSolvesubDefault callback.
348  */
349 static
350 SCIP_DECL_BENDERSCREATESUB(bendersCreatesubDefault)
351 { /*lint --e{715}*/
352  SCIP_BENDERSDATA* bendersdata;
353 
354  assert(scip != NULL);
355  assert(benders != NULL);
356 
357  bendersdata = SCIPbendersGetData(benders);
358  assert(bendersdata != NULL);
359 
360  /* adding the subproblem to the Benders' decomposition structure */
361  SCIP_CALL( SCIPaddBendersSubproblem(scip, benders, bendersdata->subproblems[probnumber]) );
362 
363  return SCIP_OKAY;
364 }
365 
366 
367 
368 /*
369  * Benders' decomposition specific interface methods
370  */
371 
372 /** Creates a default Benders' decomposition algorithm and activates it in SCIP
373  *
374  * @note Every variable that appears in the subproblem constraints must be created in the corresponding subproblem with
375  * the same name as in the master problem.
376  *
377  * @note The default Benders' decomposition implementation relies on unique variable names in the master problem and in
378  * each of the subproblems. This is required because a variable mapping is made between the master problem variables and
379  * the counterparts in the subproblems. This mapping is created using the variable names.
380  */
382  SCIP* scip, /**< SCIP data structure */
383  SCIP** subproblems, /**< the Benders' decomposition subproblems */
384  int nsubproblems /**< the number of subproblems in the Benders' decomposition */
385  )
386 {
387  SCIP_BENDERS* benders;
388  SCIP_BENDERSDATA* bendersdata;
389  int maxrestarts;
390 
391  assert(scip != NULL);
392  assert(subproblems != NULL);
393  assert(nsubproblems > 0);
394 
395  benders = SCIPfindBenders(scip, BENDERS_NAME);
396  bendersdata = SCIPbendersGetData(benders);
397 
398  /* turning restarts off */
399  SCIP_CALL( SCIPgetIntParam(scip, "presolving/maxrestarts", &maxrestarts) );
400  if( SCIPisParamFixed(scip, "presolving/maxrestarts") && maxrestarts != 0)
401  {
402  SCIPerrorMessage("The number of restarts is fixed to %d. The default Benders' decomposition requires the number"
403  " of restarts to be 0.", maxrestarts);
404  return SCIP_ERROR;
405  }
406  else
407  {
408  SCIP_CALL( SCIPsetIntParam(scip, "presolving/maxrestarts", 0) );
409  SCIP_CALL( SCIPfixParam(scip, "presolving/maxrestarts") );
410  }
411 
412  SCIP_CALL( createBendersData(scip, subproblems, &bendersdata, nsubproblems) );
413 
414  SCIP_CALL( SCIPactivateBenders(scip, benders, nsubproblems) );
415 
416  return SCIP_OKAY;
417 }
418 
419 /** creates the default Benders' decomposition and includes it in SCIP */
421  SCIP* scip /**< SCIP data structure */
422  )
423 {
424  SCIP_BENDERSDATA* bendersdata;
425  SCIP_BENDERS* benders;
426 
427  /* create default Benders' decomposition data */
428  bendersdata = NULL;
429 
430  SCIP_CALL( SCIPallocBlockMemory(scip, &bendersdata) );
431  bendersdata->created = FALSE;
432 
433  benders = NULL;
434 
435  /* include Benders' decomposition */
437  BENDERS_CUTPSEUDO, BENDERS_CUTRELAX, BENDERS_SHAREAUXVARS, bendersGetvarDefault, bendersCreatesubDefault,
438  bendersdata) );
439  assert(benders != NULL);
440 
441  /* set non fundamental callbacks via setter functions */
442  SCIP_CALL( SCIPsetBendersCopy(scip, benders, bendersCopyDefault) );
443  SCIP_CALL( SCIPsetBendersFree(scip, benders, bendersFreeDefault) );
444  SCIP_CALL( SCIPsetBendersInit(scip, benders, bendersInitDefault) );
445 
446  /* OPTIONAL: including the default cuts for Benders' decomposition */
447  SCIP_CALL( SCIPincludeBendersDefaultCuts(scip, benders) );
448 
449  return SCIP_OKAY;
450 }
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:116
#define NULL
Definition: def.h:239
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:99
public methods for SCIP parameter handling
#define BENDERS_CUTLP
public methods for memory management
static SCIP_DECL_BENDERSINIT(bendersInitDefault)
#define SCIP_MAXSTRLEN
Definition: def.h:260
#define FALSE
Definition: def.h:65
SCIP_RETCODE SCIPsetBendersInit(SCIP *scip, SCIP_BENDERS *benders, SCIP_DECL_BENDERSINIT((*bendersinit)))
Definition: scip_benders.c:312
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2793
public methods for Benders&#39; decomposition
int SCIPgetSubscipDepth(SCIP *scip)
Definition: scip_copy.c:2354
SCIP_RETCODE SCIPcreateBendersDefault(SCIP *scip, SCIP **subproblems, int nsubproblems)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10017
#define TRUE
Definition: def.h:64
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define BENDERS_CUTRELAX
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
SCIP_RETCODE SCIPincludeBendersDefault(SCIP *scip)
#define BENDERS_DESC
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2931
#define BENDERS_PRIORITY
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
static SCIP_DECL_BENDERSFREE(bendersFreeDefault)
SCIP_VAR * SCIPfindVar(SCIP *scip, const char *name)
Definition: scip_prob.c:2737
#define BENDERS_SHAREAUXVARS
public methods for Benders decomposition
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:291
static SCIP_RETCODE createVariableMappings(SCIP *scip, SCIP_BENDERS *benders)
static SCIP_DECL_BENDERSCREATESUB(bendersCreatesubDefault)
SCIP_RETCODE SCIPincludeBendersDefaultCuts(SCIP *scip, SCIP_BENDERS *benders)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:128
SCIP_BENDERSDATA * SCIPbendersGetData(SCIP_BENDERS *benders)
Definition: benders.c:4030
SCIP_RETCODE SCIPincludeBendersBasic(SCIP *scip, SCIP_BENDERS **bendersptr, const char *name, const char *desc, int priority, SCIP_Bool cutlp, SCIP_Bool cutpseudo, SCIP_Bool cutrelax, SCIP_Bool shareauxvars, SCIP_DECL_BENDERSGETVAR((*bendersgetvar)), SCIP_DECL_BENDERSCREATESUB((*benderscreatesub)), SCIP_BENDERSDATA *bendersdata)
Definition: scip_benders.c:218
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16729
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2826
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:341
struct SCIP_BendersData SCIP_BENDERSDATA
Definition: type_benders.h:63
public methods for problem copies
#define SCIP_CALL(x)
Definition: def.h:351
#define BENDERS_CUTPSEUDO
static SCIP_DECL_BENDERSCOPY(bendersCopyDefault)
SCIP_BENDERS * SCIPfindBenders(SCIP *scip, const char *name)
Definition: scip_benders.c:536
SCIP_Bool SCIPbendersIsActive(SCIP_BENDERS *benders)
Definition: benders.c:1932
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:62
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:578
SCIP_RETCODE SCIPsetBendersCopy(SCIP *scip, SCIP_BENDERS *benders, SCIP_DECL_BENDERSCOPY((*benderscopy)))
Definition: scip_benders.c:264
SCIP_RETCODE SCIPfixParam(SCIP *scip, const char *name)
Definition: scip_param.c:439
SCIP_RETCODE SCIPaddBendersSubproblem(SCIP *scip, SCIP_BENDERS *benders, SCIP *subproblem)
Definition: scip_benders.c:784
SCIP_RETCODE SCIPvarGetOrigvarSum(SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: var.c:12253
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:2044
public methods for message output
SCIP_RETCODE SCIPsetBendersFree(SCIP *scip, SCIP_BENDERS *benders, SCIP_DECL_BENDERSFREE((*bendersfree)))
Definition: scip_benders.c:288
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1999
#define SCIP_Real
Definition: def.h:150
default Benders&#39; decomposition plugin
static SCIP_RETCODE createBendersData(SCIP *scip, SCIP **subproblems, SCIP_BENDERSDATA **bendersdata, int nsubproblems)
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:2874
SCIP_RETCODE SCIPactivateBenders(SCIP *scip, SCIP_BENDERS *benders, int nsubproblems)
Definition: scip_benders.c:598
public methods for global and local (sub)problems
#define BENDERS_NAME
static SCIP_DECL_BENDERSGETVAR(bendersGetvarDefault)