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