Scippy

SCIP

Solving Constraint Integer Programs

objbenders.cpp
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-2020 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 scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file objbenders.cpp
17  * @brief C++ wrapper for the Benders' decomposition plugins
18  * @author Stephen J. Maher
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <cassert>
24 
25 #include "objbenders.h"
26 
27 
28 
29 
30 /*
31  * Data structures
32  */
33 
34 /** Benders' decomposition data */
35 struct SCIP_BendersData
36 {
37  scip::ObjBenders* objbenders; /**< the Benders' decomposition object */
38  SCIP_Bool deleteobject; /**< should the Benders' decomposition object be deleted when benders is freed? */
39 };
40 
41 
42 
43 
44 /*
45  * Callback methods of the Benders' decomposition framework
46  */
47 
48 extern "C"
49 {
50 
51 /** copy method for Benders' decomposition plugins (called when SCIP copies plugins) */
52 static
53 SCIP_DECL_BENDERSCOPY(bendersCopyObj)
54 { /*lint --e{715}*/
55  SCIP_BENDERSDATA* bendersdata;
56 
57  assert(scip != NULL);
58 
59  bendersdata = SCIPbendersGetData(benders);
60  assert(bendersdata != NULL);
61  assert(bendersdata->objbenders != NULL);
62  assert(bendersdata->objbenders->scip_ != scip);
63 
64  if( bendersdata->objbenders->iscloneable() )
65  {
66  scip::ObjBenders* newobjbenders;
67  newobjbenders = dynamic_cast<scip::ObjBenders*> (bendersdata->objbenders->clone(scip));
68 
69  /* call include method of Benders' decomposition object */
70  SCIP_CALL( SCIPincludeObjBenders(scip, newobjbenders, TRUE) );
71  }
72 
73  return SCIP_OKAY;
74 }
75 
76 /** destructor of Benders' decomposition to free user data (called when SCIP is exiting) */
77 static
78 SCIP_DECL_BENDERSFREE(bendersFreeObj)
79 { /*lint --e{715}*/
80  SCIP_BENDERSDATA* bendersdata;
81 
82  bendersdata = SCIPbendersGetData(benders);
83  assert(bendersdata != NULL);
84  assert(bendersdata->objbenders != NULL);
85  assert(bendersdata->objbenders->scip_ == scip);
86 
87  /* call virtual method of benders object */
88  SCIP_CALL( bendersdata->objbenders->scip_free(scip, benders) );
89 
90  /* free benders object */
91  if( bendersdata->deleteobject )
92  delete bendersdata->objbenders;
93 
94  /* free benders data */
95  delete bendersdata;
96  SCIPbendersSetData(benders, NULL); /*lint !e64*/
97 
98  return SCIP_OKAY;
99 }
100 
101 
102 /** initialization method of Benders' decomposition (called after problem was transformed) */
103 static
104 SCIP_DECL_BENDERSINIT(bendersInitObj)
105 { /*lint --e{715}*/
106  SCIP_BENDERSDATA* bendersdata;
107 
108  bendersdata = SCIPbendersGetData(benders);
109  assert(bendersdata != NULL);
110  assert(bendersdata->objbenders != NULL);
111  assert(bendersdata->objbenders->scip_ == scip);
112 
113  /* call virtual method of benders object */
114  SCIP_CALL( bendersdata->objbenders->scip_init(scip, benders) );
115 
116  return SCIP_OKAY;
117 }
118 
119 
120 /** deinitialization method of Benders' decomposition (called before transformed problem is freed) */
121 static
122 SCIP_DECL_BENDERSEXIT(bendersExitObj)
123 { /*lint --e{715}*/
124  SCIP_BENDERSDATA* bendersdata;
125 
126  bendersdata = SCIPbendersGetData(benders);
127  assert(bendersdata != NULL);
128  assert(bendersdata->objbenders != NULL);
129 
130  /* call virtual method of benders object */
131  SCIP_CALL( bendersdata->objbenders->scip_exit(scip, benders) );
132 
133  return SCIP_OKAY;
134 }
135 
136 
137 /** presolving initialization method of Benders' decomposition (called when presolving is about to begin) */
138 static
139 SCIP_DECL_BENDERSINITPRE(bendersInitpreObj)
140 { /*lint --e{715}*/
141  SCIP_BENDERSDATA* bendersdata;
142 
143  bendersdata = SCIPbendersGetData(benders);
144  assert(bendersdata != NULL);
145  assert(bendersdata->objbenders != NULL);
146 
147  /* call virtual method of benders object */
148  SCIP_CALL( bendersdata->objbenders->scip_initpre(scip, benders) );
149 
150  return SCIP_OKAY;
151 }
152 
153 
154 /** presolving deinitialization method of Benders' decomposition (called after presolving has been finished) */
155 static
156 SCIP_DECL_BENDERSEXITPRE(bendersExitpreObj)
157 { /*lint --e{715}*/
158  SCIP_BENDERSDATA* bendersdata;
159 
160  bendersdata = SCIPbendersGetData(benders);
161  assert(bendersdata != NULL);
162  assert(bendersdata->objbenders != NULL);
163 
164  /* call virtual method of benders object */
165  SCIP_CALL( bendersdata->objbenders->scip_exitpre(scip, benders) );
166 
167  return SCIP_OKAY;
168 }
169 
170 
171 /** solving process initialization method of Benders' decomposition (called when branch and bound process is about to begin) */
172 static
173 SCIP_DECL_BENDERSINITSOL(bendersInitsolObj)
174 { /*lint --e{715}*/
175  SCIP_BENDERSDATA* bendersdata;
176 
177  bendersdata = SCIPbendersGetData(benders);
178  assert(bendersdata != NULL);
179  assert(bendersdata->objbenders != NULL);
180 
181  /* call virtual method of benders object */
182  SCIP_CALL( bendersdata->objbenders->scip_initsol(scip, benders) );
183 
184  return SCIP_OKAY;
185 }
186 
187 
188 /** solving process deinitialization method of Benders' decomposition (called before branch and bound process data is freed) */
189 static
190 SCIP_DECL_BENDERSEXITSOL(bendersExitsolObj)
191 { /*lint --e{715}*/
192  SCIP_BENDERSDATA* bendersdata;
193 
194  bendersdata = SCIPbendersGetData(benders);
195  assert(bendersdata != NULL);
196  assert(bendersdata->objbenders != NULL);
197 
198  /* call virtual method of benders object */
199  SCIP_CALL( bendersdata->objbenders->scip_exitsol(scip, benders) );
200 
201  return SCIP_OKAY;
202 }
203 
204 
205 /** method that is called to create the subproblem and register it with the Benders' decomposition structure. */
206 static
207 SCIP_DECL_BENDERSCREATESUB(bendersCreatesubObj)
208 { /*lint --e{715}*/
209  SCIP_BENDERSDATA* bendersdata;
210 
211  bendersdata = SCIPbendersGetData(benders);
212  assert(bendersdata != NULL);
213  assert(bendersdata->objbenders != NULL);
214 
215  /* call virtual method of benders object */
216  SCIP_CALL( bendersdata->objbenders->scip_createsub(scip, benders, probnumber) );
217 
218  return SCIP_OKAY;
219 }
220 
221 
222 /** methods called prior to solving the subproblems */
223 static
224 SCIP_DECL_BENDERSPRESUBSOLVE(bendersPresubsolveObj)
225 { /*lint --e{715}*/
226  SCIP_BENDERSDATA* bendersdata;
227 
228  bendersdata = SCIPbendersGetData(benders);
229  assert(bendersdata != NULL);
230  assert(bendersdata->objbenders != NULL);
231 
232  /* call virtual method of benders object */
233  SCIP_CALL( bendersdata->objbenders->scip_presubsolve(scip, benders, sol, type, checkint, infeasible, auxviol,
234  skipsolve, result) );
235 
236  return SCIP_OKAY;
237 }
238 
239 
240 /** method called to solve the convex relaxation of an individual subproblem of the Benders' decomposition */
241 static
242 SCIP_DECL_BENDERSSOLVESUBCONVEX(bendersSolvesubconvexObj)
243 { /*lint --e{715}*/
244  SCIP_BENDERSDATA* bendersdata;
245 
246  bendersdata = SCIPbendersGetData(benders);
247  assert(bendersdata != NULL);
248  assert(bendersdata->objbenders != NULL);
249 
250  /* call virtual method of benders object */
251  SCIP_CALL( bendersdata->objbenders->scip_solvesubconvex(scip, benders, sol, probnumber, onlyconvexcheck, objective,
252  result) );
253 
254  return SCIP_OKAY;
255 }
256 
257 
258 /** method called to solve an individual subproblem of the Benders' decomposition */
259 static
260 SCIP_DECL_BENDERSSOLVESUB(bendersSolvesubObj)
261 { /*lint --e{715}*/
262  SCIP_BENDERSDATA* bendersdata;
263 
264  bendersdata = SCIPbendersGetData(benders);
265  assert(bendersdata != NULL);
266  assert(bendersdata->objbenders != NULL);
267 
268  /* call virtual method of benders object */
269  SCIP_CALL( bendersdata->objbenders->scip_solvesub(scip, benders, sol, probnumber, objective, result) );
270 
271  return SCIP_OKAY;
272 }
273 
274 
275 /** method called after the subproblems are solved in the Benders' decomposition algorithm */
276 static
277 SCIP_DECL_BENDERSPOSTSOLVE(bendersPostsolveObj)
278 { /*lint --e{715}*/
279  SCIP_BENDERSDATA* bendersdata;
280 
281  bendersdata = SCIPbendersGetData(benders);
282  assert(bendersdata != NULL);
283  assert(bendersdata->objbenders != NULL);
284 
285  /* call virtual method of benders object */
286  SCIP_CALL( bendersdata->objbenders->scip_postsolve(scip, benders, sol, type, mergecands, npriomergecands,
287  nmergecands, checkint, infeasible, merged) );
288 
289  return SCIP_OKAY;
290 }
291 
292 
293 /** frees an individual subproblem. Called in each iteration of the Benders' decomposition algorithm */
294 static
295 SCIP_DECL_BENDERSFREESUB(bendersFreesubObj)
296 { /*lint --e{715}*/
297  SCIP_BENDERSDATA* bendersdata;
298 
299  bendersdata = SCIPbendersGetData(benders);
300  assert(bendersdata != NULL);
301  assert(bendersdata->objbenders != NULL);
302 
303  /* call virtual method of benders object */
304  SCIP_CALL( bendersdata->objbenders->scip_freesub(scip, benders, probnumber) );
305 
306  return SCIP_OKAY;
307 }
308 
309 
310 /** callback method to retrieve the master (subproblem) variable corresponding to the input subproblem (master) variable */
311 static
312 SCIP_DECL_BENDERSGETVAR(bendersGetvarObj)
313 { /*lint --e{715}*/
314  SCIP_BENDERSDATA* bendersdata;
315 
316  bendersdata = SCIPbendersGetData(benders);
317  assert(bendersdata != NULL);
318  assert(bendersdata->objbenders != NULL);
319 
320  /* call virtual method of benders object */
321  SCIP_CALL( bendersdata->objbenders->scip_getvar(scip, benders, var, mappedvar, probnumber) );
322 
323  return SCIP_OKAY;
324 }
325 
326 
327 }
328 
329 
330 /*
331  * Benders' decomposition specific interface methods
332  */
333 
334 /** creates the Benders' decomposition for the given Benders' decomposition object and includes it in SCIP */
336  SCIP* scip, /**< SCIP data structure */
337  scip::ObjBenders* objbenders, /**< Benders' decomposition object */
338  SCIP_Bool deleteobject /**< should the Benders' decomposition object be deleted when benders is freed? */
339  )
340 {
341  SCIP_BENDERSDATA* bendersdata;
342 
343  assert(scip != NULL);
344  assert(objbenders != NULL);
345  assert(objbenders->scip_ == scip);
346 
347  /* create obj Benders' decomposition data */
348  bendersdata = new SCIP_BENDERSDATA;
349  bendersdata->objbenders = objbenders;
350  bendersdata->deleteobject = deleteobject;
351 
352  /* include Benders' decomposition */
353  SCIP_CALL( SCIPincludeBenders(scip, objbenders->scip_name_, objbenders->scip_desc_,
354  objbenders->scip_priority_, objbenders->scip_cutlp_, objbenders->scip_cutpseudo_,
355  objbenders->scip_cutrelax_, objbenders->scip_shareauxvars_, bendersCopyObj, bendersFreeObj, bendersInitObj,
356  bendersExitObj, bendersInitpreObj, bendersExitpreObj, bendersInitsolObj, bendersExitsolObj, bendersGetvarObj,
357  bendersCreatesubObj, bendersPresubsolveObj, bendersSolvesubconvexObj, bendersSolvesubObj, bendersPostsolveObj,
358  bendersFreesubObj, bendersdata) ); /*lint !e429*/
359 
360  return SCIP_OKAY; /*lint !e429*/
361 }
362 
363 /** returns the benders object of the given name, or 0 if not existing */
365  SCIP* scip, /**< SCIP data structure */
366  const char* name /**< name of Benders' decomposition */
367  )
368 {
369  SCIP_BENDERS* benders;
370  SCIP_BENDERSDATA* bendersdata;
371 
372  benders = SCIPfindBenders(scip, name);
373  if( benders == NULL )
374  return 0;
375 
376  bendersdata = SCIPbendersGetData(benders);
377  assert(bendersdata != NULL);
378 
379  return bendersdata->objbenders;
380 }
381 
382 /** returns the benders object for the given Benders' decomposition */
384  SCIP* scip, /**< SCIP data structure */
385  SCIP_BENDERS* benders /**< Benders' decomposition */
386  )
387 {
388  SCIP_BENDERSDATA* bendersdata;
389 
390  assert(scip != NULL);
391  bendersdata = SCIPbendersGetData(benders);
392  assert(bendersdata != NULL);
393 
394  return bendersdata->objbenders;
395 }
void SCIPbendersSetData(SCIP_BENDERS *benders, SCIP_BENDERSDATA *bendersdata)
Definition: benders.c:5731
static SCIP_DECL_BENDERSEXITSOL(bendersExitsolObj)
Definition: objbenders.cpp:190
scip::ObjBenders * SCIPgetObjBenders(SCIP *scip, SCIP_BENDERS *benders)
Definition: objbenders.cpp:383
static SCIP_DECL_BENDERSSOLVESUB(bendersSolvesubObj)
Definition: objbenders.cpp:260
static SCIP_DECL_BENDERSPOSTSOLVE(bendersPostsolveObj)
Definition: objbenders.cpp:277
static SCIP_DECL_BENDERSFREE(bendersFreeObj)
Definition: objbenders.cpp:78
SCIP_RETCODE SCIPincludeObjBenders(SCIP *scip, scip::ObjBenders *objbenders, SCIP_Bool deleteobject)
Definition: objbenders.cpp:335
const SCIP_Bool scip_shareauxvars_
Definition: objbenders.h:74
C++ wrapper for Benders&#39; decomposition.
char * scip_name_
Definition: objbenders.h:56
static SCIP_DECL_BENDERSGETVAR(bendersGetvarObj)
Definition: objbenders.cpp:312
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPincludeBenders(SCIP *scip, const char *name, const char *desc, int priority, SCIP_Bool cutlp, SCIP_Bool cutpseudo, SCIP_Bool cutrelax, SCIP_Bool shareauxvars, SCIP_DECL_BENDERSCOPY((*benderscopy)), SCIP_DECL_BENDERSFREE((*bendersfree)), SCIP_DECL_BENDERSINIT((*bendersinit)), SCIP_DECL_BENDERSEXIT((*bendersexit)), SCIP_DECL_BENDERSINITPRE((*bendersinitpre)), SCIP_DECL_BENDERSEXITPRE((*bendersexitpre)), SCIP_DECL_BENDERSINITSOL((*bendersinitsol)), SCIP_DECL_BENDERSEXITSOL((*bendersexitsol)), SCIP_DECL_BENDERSGETVAR((*bendersgetvar)), SCIP_DECL_BENDERSCREATESUB((*benderscreatesub)), SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve)), SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex)), SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub)), SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve)), SCIP_DECL_BENDERSFREESUB((*bendersfreesub)), SCIP_BENDERSDATA *bendersdata)
Definition: scip_benders.c:67
static SCIP_DECL_BENDERSEXIT(bendersExitObj)
Definition: objbenders.cpp:122
static SCIP_DECL_BENDERSINITSOL(bendersInitsolObj)
Definition: objbenders.cpp:173
C++ wrapper for Benders&#39; decomposition plugins.
Definition: objbenders.h:47
SCIP_BENDERS * SCIPfindBenders(SCIP *scip, const char *name)
Definition: scip_benders.c:484
static SCIP_DECL_BENDERSPRESUBSOLVE(bendersPresubsolveObj)
Definition: objbenders.cpp:224
char * scip_desc_
Definition: objbenders.h:59
SCIP_BENDERSDATA * SCIPbendersGetData(SCIP_BENDERS *benders)
Definition: benders.c:5721
#define NULL
Definition: lpi_spx1.cpp:155
struct SCIP_BendersData SCIP_BENDERSDATA
Definition: type_benders.h:73
const int scip_priority_
Definition: objbenders.h:62
#define SCIP_CALL(x)
Definition: def.h:364
scip::ObjBenders * SCIPfindObjBenders(SCIP *scip, const char *name)
Definition: objbenders.cpp:364
static SCIP_DECL_BENDERSSOLVESUBCONVEX(bendersSolvesubconvexObj)
Definition: objbenders.cpp:242
#define SCIP_Bool
Definition: def.h:70
static SCIP_DECL_BENDERSCREATESUB(bendersCreatesubObj)
Definition: objbenders.cpp:207
static SCIP_DECL_BENDERSINITPRE(bendersInitpreObj)
Definition: objbenders.cpp:139
const SCIP_Bool scip_cutpseudo_
Definition: objbenders.h:68
static SCIP_DECL_BENDERSEXITPRE(bendersExitpreObj)
Definition: objbenders.cpp:156
const SCIP_Bool scip_cutlp_
Definition: objbenders.h:65
static SCIP_DECL_BENDERSFREESUB(bendersFreesubObj)
Definition: objbenders.cpp:295
static SCIP_DECL_BENDERSINIT(bendersInitObj)
Definition: objbenders.cpp:104
const SCIP_Bool scip_cutrelax_
Definition: objbenders.h:71
static SCIP_DECL_BENDERSCOPY(bendersCopyObj)
Definition: objbenders.cpp:53