1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 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 benderscut_int.c
17 * @ingroup OTHER_CFILES
18 * @brief Generates a Laporte and Louveaux Benders' decomposition integer cut
19 * @author Stephen J. Maher
20 */
21
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23
24 #include "scip/benderscut_int.h"
25 #include "scip/cons_linear.h"
26 #include "scip/pub_benderscut.h"
27 #include "scip/pub_benders.h"
28 #include "scip/pub_lp.h"
29 #include "scip/pub_message.h"
30 #include "scip/pub_misc.h"
31 #include "scip/pub_paramset.h"
32 #include "scip/pub_var.h"
33 #include "scip/scip_benders.h"
34 #include "scip/scip_cons.h"
35 #include "scip/scip_cut.h"
36 #include "scip/scip_general.h"
37 #include "scip/scip_lp.h"
38 #include "scip/scip_mem.h"
39 #include "scip/scip_message.h"
40 #include "scip/scip_numerics.h"
41 #include "scip/scip_param.h"
42 #include "scip/scip_prob.h"
43 #include "scip/scip_sol.h"
44 #include <string.h>
45
46 #define BENDERSCUT_NAME "integer"
47 #define BENDERSCUT_DESC "Laporte and Louveaux Benders' decomposition integer cut"
48 #define BENDERSCUT_PRIORITY 0
49 #define BENDERSCUT_LPCUT FALSE
50
51 #define SCIP_DEFAULT_ADDCUTS FALSE /** Should cuts be generated, instead of constraints */
52 #define SCIP_DEFAULT_CUTCONSTANT -10000.0
53
54 /*
55 * Data structures
56 */
57
58 /** Benders' decomposition cuts data */
59 struct SCIP_BenderscutData
60 {
61 SCIP_BENDERS* benders; /**< the Benders' decomposition data structure */
62 SCIP_Real cutconstant; /**< the constant for computing the integer cuts */
63 SCIP_Real* subprobconstant; /**< the constant for each subproblem used for computing the integer cuts */
64 SCIP_Bool addcuts; /**< should cuts be generated instead of constraints */
65 SCIP_Bool* firstcut; /**< flag to indicate that the first cut needs to be generated. */
66 int nsubproblems; /**< the number of subproblems for the Benders' decomposition */
67 };
68
69 /** method to call, when the priority of a Benders' decomposition was changed */
70 static
SCIP_DECL_PARAMCHGD(paramChgdBenderscutintConstant)71 SCIP_DECL_PARAMCHGD(paramChgdBenderscutintConstant)
72 { /*lint --e{715}*/
73 SCIP_BENDERSCUTDATA* benderscutdata;
74 int i;
75
76 benderscutdata = (SCIP_BENDERSCUTDATA*)SCIPparamGetData(param);
77 assert(benderscutdata != NULL);
78
79 for( i = 0; i < benderscutdata->nsubproblems; i++ )
80 benderscutdata->subprobconstant[i] = benderscutdata->cutconstant;
81
82 return SCIP_OKAY;
83 }
84
85
86 /** creates the Benders' decomposition cut data */
87 static
createBenderscutData(SCIP * scip,SCIP_BENDERSCUTDATA * benderscutdata)88 SCIP_RETCODE createBenderscutData(
89 SCIP* scip, /**< the SCIP data structure */
90 SCIP_BENDERSCUTDATA* benderscutdata /**< the Benders' cut data */
91 )
92 {
93 int i;
94
95 assert(scip != NULL);
96 assert(benderscutdata != NULL);
97
98 /* allocating the memory for the subproblem constants */
99 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &benderscutdata->subprobconstant, benderscutdata->nsubproblems) );
100 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &benderscutdata->firstcut, benderscutdata->nsubproblems) );
101
102 for( i = 0; i < benderscutdata->nsubproblems; i++ )
103 {
104 benderscutdata->subprobconstant[i] = benderscutdata->cutconstant;
105 benderscutdata->firstcut[i] = TRUE;
106 }
107
108 return SCIP_OKAY;
109 }
110
111 /*
112 * Local methods
113 */
114
115 /** updates the cut constant for the given subproblem based upon the global bounds of the associated auxiliary variable */
116 static
updateSubproblemCutConstant(SCIP * masterprob,SCIP_BENDERS * benders,SCIP_BENDERSCUTDATA * benderscutdata,int probnumber)117 void updateSubproblemCutConstant(
118 SCIP* masterprob, /**< the SCIP instance of the master problem */
119 SCIP_BENDERS* benders, /**< the benders' decomposition structure */
120 SCIP_BENDERSCUTDATA* benderscutdata, /**< the Benders' decomposition cut data */
121 int probnumber /**< the index for the subproblem */
122 )
123 {
124 SCIP_VAR* auxiliaryvar;
125
126 assert(masterprob != NULL);
127 assert(benders != NULL);
128 assert(benderscutdata != NULL);
129
130 auxiliaryvar = SCIPbendersGetAuxiliaryVar(benders, probnumber);
131
132 /* checking if the subproblem lower bound has been updated. If it is has changed, then firstcut is set to TRUE.
133 * Otherwise, the constant remains the same.
134 */
135 if( SCIPisGT(masterprob, SCIPbendersGetSubproblemLowerbound(benders, probnumber),
136 benderscutdata->subprobconstant[probnumber]) )
137 {
138 benderscutdata->subprobconstant[probnumber] = SCIPbendersGetSubproblemLowerbound(benders, probnumber);
139 benderscutdata->firstcut[probnumber] = TRUE;
140 }
141
142 /* updating the cut constant if the auxiliary variable global lower bound is greater than the current constant */
143 if( SCIPisGT(masterprob, SCIPvarGetLbGlobal(auxiliaryvar), benderscutdata->subprobconstant[probnumber]) )
144 benderscutdata->subprobconstant[probnumber] = SCIPvarGetLbGlobal(auxiliaryvar);
145 }
146
147 /** computes a standard Benders' optimality cut from the dual solutions of the LP */
148 static
computeStandardIntegerOptCut(SCIP * masterprob,SCIP_BENDERS * benders,SCIP_SOL * sol,SCIP_CONS * cons,SCIP_ROW * row,SCIP_Real cutconstant,int probnumber,SCIP_Bool addcut,SCIP_Bool * success)149 SCIP_RETCODE computeStandardIntegerOptCut(
150 SCIP* masterprob, /**< the SCIP instance of the master problem */
151 SCIP_BENDERS* benders, /**< the benders' decomposition structure */
152 SCIP_SOL* sol, /**< primal CIP solution */
153 SCIP_CONS* cons, /**< the constraint for the generated cut, can be NULL */
154 SCIP_ROW* row, /**< the row for the generated cut, can be NULL */
155 SCIP_Real cutconstant, /**< the constant value in the integer optimality cut */
156 int probnumber, /**< the number of the pricing problem */
157 SCIP_Bool addcut, /**< indicates whether a cut is created instead of a constraint */
158 SCIP_Bool* success /**< was the cut generation successful? */
159 )
160 {
161 SCIP_VAR** vars;
162 int nvars;
163 SCIP_Real subprobobj; /* the objective function value of the subproblem */
164 SCIP_Real lhs; /* the left hand side of the cut */
165 int i;
166 SCIPdebug( SCIP* subproblem; )
167
168 #ifndef NDEBUG
169 SCIP_Real verifyobj = 0;
170 #endif
171
172 assert(masterprob != NULL);
173 assert(benders != NULL);
174 assert(cons != NULL || addcut);
175 assert(row != NULL || !addcut);
176
177 (*success) = FALSE;
178
179 /* getting the best solution from the subproblem */
180
181 subprobobj = SCIPbendersGetSubproblemObjval(benders, probnumber);
182
183 SCIPdebug( subproblem = SCIPbendersSubproblem(benders, probnumber); )
184 SCIPdebug( SCIPdebugMsg(masterprob, "Subproblem %d - Objective Value: Stored - %g Orig Obj - %g Cut constant - %g\n",
185 probnumber, SCIPbendersGetSubproblemObjval(benders, probnumber), SCIPgetSolOrigObj(subproblem, SCIPgetBestSol(subproblem))*(int)SCIPgetObjsense(subproblem),
186 cutconstant); )
187
188 nvars = SCIPgetNVars(masterprob);
189 vars = SCIPgetVars(masterprob);
190
191 /* adding the subproblem objective function value to the lhs */
192 if( addcut )
193 lhs = SCIProwGetLhs(row);
194 else
195 lhs = SCIPgetLhsLinear(masterprob, cons);
196
197 /* looping over all master problem variables to update the coefficients in the computed cut. */
198 for( i = 0; i < nvars; i++ )
199 {
200 SCIP_VAR* subprobvar;
201 SCIP_Real coef;
202
203 SCIP_CALL( SCIPgetBendersSubproblemVar(masterprob, benders, vars[i], &subprobvar, probnumber) );
204
205 /* if there is a corresponding subproblem variable, then the variable will not be NULL. */
206 if( subprobvar != NULL )
207 {
208 /* if the variable is on its upper bound, then the subproblem objective value is added to the cut */
209 if( SCIPisFeasEQ(masterprob, SCIPgetSolVal(masterprob, sol, vars[i]), 1.0) )
210 {
211 coef = -(subprobobj - cutconstant);
212 lhs -= (subprobobj - cutconstant);
213 }
214 else
215 coef = (subprobobj - cutconstant);
216
217 /* adding the variable to the cut. The coefficient is the subproblem objective value */
218 if( addcut )
219 {
220 SCIP_CALL( SCIPaddVarToRow(masterprob, row, vars[i], coef) );
221 }
222 else
223 {
224 SCIP_CALL( SCIPaddCoefLinear(masterprob, cons, vars[i], coef) );
225 }
226 }
227 }
228
229 lhs += subprobobj;
230
231 /* if the bound becomes infinite, then the cut generation terminates. */
232 if( SCIPisInfinity(masterprob, lhs) || SCIPisInfinity(masterprob, -lhs) )
233 {
234 (*success) = FALSE;
235 SCIPdebugMsg(masterprob, "Infinite bound when generating integer optimality cut.\n");
236 return SCIP_OKAY;
237 }
238
239 /* Update the lhs of the cut */
240 if( addcut )
241 {
242 SCIP_CALL( SCIPchgRowLhs(masterprob, row, lhs) );
243 }
244 else
245 {
246 SCIP_CALL( SCIPchgLhsLinear(masterprob, cons, lhs) );
247 }
248
249 #ifndef NDEBUG
250 if( addcut )
251 lhs = SCIProwGetLhs(row);
252 else
253 lhs = SCIPgetLhsLinear(masterprob, cons);
254 verifyobj += lhs;
255
256 if( addcut )
257 verifyobj -= SCIPgetRowSolActivity(masterprob, row, sol);
258 else
259 verifyobj -= SCIPgetActivityLinear(masterprob, cons, sol);
260 #endif
261
262 assert(SCIPisFeasEQ(masterprob, verifyobj, subprobobj));
263
264 (*success) = TRUE;
265
266 return SCIP_OKAY;
267 }
268
269
270 /** adds the auxiliary variable to the generated cut. If this is the first optimality cut for the subproblem, then the
271 * auxiliary variable is first created and added to the master problem.
272 */
273 static
addAuxiliaryVariableToCut(SCIP * masterprob,SCIP_BENDERS * benders,SCIP_CONS * cons,SCIP_ROW * row,int probnumber,SCIP_Bool addcut)274 SCIP_RETCODE addAuxiliaryVariableToCut(
275 SCIP* masterprob, /**< the SCIP instance of the master problem */
276 SCIP_BENDERS* benders, /**< the benders' decomposition structure */
277 SCIP_CONS* cons, /**< the constraint for the generated cut, can be NULL */
278 SCIP_ROW* row, /**< the row for the generated cut, can be NULL */
279 int probnumber, /**< the number of the pricing problem */
280 SCIP_Bool addcut /**< indicates whether a cut is created instead of a constraint */
281 )
282 {
283 SCIP_VAR* auxiliaryvar;
284
285 assert(masterprob != NULL);
286 assert(benders != NULL);
287 assert(cons != NULL || addcut);
288 assert(row != NULL || !addcut);
289
290 auxiliaryvar = SCIPbendersGetAuxiliaryVar(benders, probnumber);
291
292 /* adding the auxiliary variable to the generated cut */
293 if( addcut )
294 {
295 SCIP_CALL( SCIPaddVarToRow(masterprob, row, auxiliaryvar, 1.0) );
296 }
297 else
298 {
299 SCIP_CALL( SCIPaddCoefLinear(masterprob, cons, auxiliaryvar, 1.0) );
300 }
301
302 return SCIP_OKAY;
303 }
304
305
306 /** generates and applies Benders' cuts */
307 static
generateAndApplyBendersIntegerCuts(SCIP * masterprob,SCIP_BENDERS * benders,SCIP_BENDERSCUT * benderscut,SCIP_SOL * sol,int probnumber,SCIP_BENDERSENFOTYPE type,SCIP_RESULT * result,SCIP_Bool initcons)308 SCIP_RETCODE generateAndApplyBendersIntegerCuts(
309 SCIP* masterprob, /**< the SCIP instance of the master problem */
310 SCIP_BENDERS* benders, /**< the benders' decomposition */
311 SCIP_BENDERSCUT* benderscut, /**< the benders' decomposition cut method */
312 SCIP_SOL* sol, /**< primal CIP solution */
313 int probnumber, /**< the number of the pricing problem */
314 SCIP_BENDERSENFOTYPE type, /**< the enforcement type calling this function */
315 SCIP_RESULT* result, /**< the result from solving the subproblems */
316 SCIP_Bool initcons /**< is this function called to generate the initial constraint */
317 )
318 {
319 SCIP_BENDERSCUTDATA* benderscutdata;
320 SCIP_CONSHDLR* consbenders;
321 SCIP_CONS* cons;
322 SCIP_ROW* row;
323 char cutname[SCIP_MAXSTRLEN];
324 SCIP_Bool optimal;
325 SCIP_Bool addcut;
326 SCIP_Bool success;
327
328 assert(masterprob != NULL);
329 assert(benders != NULL);
330 assert(benderscut != NULL);
331 assert(result != NULL);
332
333 row = NULL;
334 cons = NULL;
335
336 success = FALSE;
337
338 /* retrieving the Benders' cut data */
339 benderscutdata = SCIPbenderscutGetData(benderscut);
340
341 /* if the cuts are generated prior to the solving stage, then rows can not be generated. So constraints must be added
342 * to the master problem.
343 */
344 if( SCIPgetStage(masterprob) < SCIP_STAGE_INITSOLVE )
345 addcut = FALSE;
346 else
347 addcut = benderscutdata->addcuts;
348
349 /* retrieving the Benders' decomposition constraint handler */
350 consbenders = SCIPfindConshdlr(masterprob, "benders");
351
352 /* checking the optimality of the original problem with a comparison between the auxiliary variable and the
353 * objective value of the subproblem
354 */
355 optimal = FALSE;
356 SCIP_CALL( SCIPcheckBendersSubproblemOptimality(masterprob, benders, sol, probnumber, &optimal) );
357
358 if( optimal )
359 {
360 (*result) = SCIP_FEASIBLE;
361 SCIPdebugMsg(masterprob, "No <%s> cut added. Current Master Problem Obj: %g\n", BENDERSCUT_NAME,
362 SCIPgetSolOrigObj(masterprob, NULL)*(int)SCIPgetObjsense(masterprob));
363 return SCIP_OKAY;
364 }
365
366 /* checking whether the subproblem constant is less than the auxiliary variable global lower bound */
367 updateSubproblemCutConstant(masterprob, benders, benderscutdata, probnumber);
368
369 /* if no integer cuts have been previously generated and the bound on the auxiliary variable is -infinity,
370 * then an initial lower bounding cut is added
371 */
372 if( benderscutdata->firstcut[probnumber]
373 && SCIPisInfinity(masterprob, -SCIPvarGetLbGlobal(SCIPbendersGetAuxiliaryVar(benders, probnumber))) )
374 {
375 benderscutdata->firstcut[probnumber] = FALSE;
376 SCIP_CALL( generateAndApplyBendersIntegerCuts(masterprob, benders, benderscut, sol, probnumber, type, result,
377 TRUE) );
378 }
379
380 /* setting the name of the generated cut */
381 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "integeroptcut_%d_%" SCIP_LONGINT_FORMAT, probnumber,
382 SCIPbenderscutGetNFound(benderscut) );
383
384 /* creating an empty row or constraint for the Benders' cut */
385 if( addcut )
386 {
387 SCIP_CALL( SCIPcreateEmptyRowConshdlr(masterprob, &row, consbenders, cutname, 0.0, SCIPinfinity(masterprob), FALSE,
388 FALSE, TRUE) );
389 }
390 else
391 {
392 SCIP_CALL( SCIPcreateConsBasicLinear(masterprob, &cons, cutname, 0, NULL, NULL, 0.0, SCIPinfinity(masterprob)) );
393 SCIP_CALL( SCIPsetConsDynamic(masterprob, cons, TRUE) );
394 SCIP_CALL( SCIPsetConsRemovable(masterprob, cons, TRUE) );
395 }
396
397 if( initcons )
398 {
399 SCIP_Real lhs;
400
401 /* adding the subproblem objective function value to the lhs */
402 if( addcut )
403 lhs = SCIProwGetLhs(row);
404 else
405 lhs = SCIPgetLhsLinear(masterprob, cons);
406
407 lhs += benderscutdata->subprobconstant[probnumber];
408
409 /* if the bound becomes infinite, then the cut generation terminates. */
410 if( SCIPisInfinity(masterprob, lhs) || SCIPisInfinity(masterprob, -lhs) )
411 {
412 success = FALSE;
413 SCIPdebugMsg(masterprob, "Infinite bound when generating integer optimality cut.\n");
414 }
415
416 /* Update the lhs of the cut */
417 if( addcut )
418 {
419 SCIP_CALL( SCIPchgRowLhs(masterprob, row, lhs) );
420 }
421 else
422 {
423 SCIP_CALL( SCIPchgLhsLinear(masterprob, cons, lhs) );
424 }
425 }
426 else
427 {
428 /* computing the coefficients of the optimality cut */
429 SCIP_CALL( computeStandardIntegerOptCut(masterprob, benders, sol, cons, row,
430 benderscutdata->subprobconstant[probnumber], probnumber, addcut, &success) );
431 }
432
433 /* if success is FALSE, then there was an error in generating the integer optimality cut. No cut will be added to
434 * the master problem. Otherwise, the constraint is added to the master problem.
435 */
436 if( !success )
437 {
438 (*result) = SCIP_DIDNOTFIND;
439 SCIPdebugMsg(masterprob, "Error in generating Benders' integer optimality cut for problem %d.\n", probnumber);
440 }
441 else
442 {
443 /* adding the auxiliary variable to the optimality cut */
444 SCIP_CALL( addAuxiliaryVariableToCut(masterprob, benders, cons, row, probnumber, addcut) );
445
446 /* adding the constraint to the master problem */
447 if( addcut )
448 {
449 SCIP_Bool infeasible;
450
451 if( type == SCIP_BENDERSENFOTYPE_LP || type == SCIP_BENDERSENFOTYPE_RELAX )
452 {
453 SCIP_CALL( SCIPaddRow(masterprob, row, FALSE, &infeasible) );
454 assert(!infeasible);
455 }
456 else
457 {
458 assert(type == SCIP_BENDERSENFOTYPE_CHECK || type == SCIP_BENDERSENFOTYPE_PSEUDO);
459 SCIP_CALL( SCIPaddPoolCut(masterprob, row) );
460 }
461
462 #ifdef SCIP_DEBUG
463 SCIP_CALL( SCIPprintRow(masterprob, row, NULL) );
464 SCIPinfoMessage(masterprob, NULL, ";\n");
465 #endif
466
467 (*result) = SCIP_SEPARATED;
468 }
469 else
470 {
471 SCIP_CALL( SCIPaddCons(masterprob, cons) );
472
473 SCIPdebugPrintCons(masterprob, cons, NULL);
474
475 (*result) = SCIP_CONSADDED;
476 }
477 }
478
479 if( addcut )
480 {
481 /* release the row */
482 SCIP_CALL( SCIPreleaseRow(masterprob, &row) );
483 }
484 else
485 {
486 /* release the constraint */
487 SCIP_CALL( SCIPreleaseCons(masterprob, &cons) );
488 }
489
490 return SCIP_OKAY;
491 }
492
493 /*
494 * Callback methods of Benders' decomposition cuts
495 */
496
497 /** destructor of Benders' decomposition cuts to free user data (called when SCIP is exiting) */
498 static
SCIP_DECL_BENDERSCUTFREE(benderscutFreeInt)499 SCIP_DECL_BENDERSCUTFREE(benderscutFreeInt)
500 { /*lint --e{715}*/
501 SCIP_BENDERSCUTDATA* benderscutdata;
502
503 assert( benderscut != NULL );
504 assert( strcmp(SCIPbenderscutGetName(benderscut), BENDERSCUT_NAME) == 0 );
505
506 /* free Benders' cut data */
507 benderscutdata = SCIPbenderscutGetData(benderscut);
508 assert( benderscutdata != NULL );
509
510 SCIPfreeBlockMemory(scip, &benderscutdata);
511
512 SCIPbenderscutSetData(benderscut, NULL);
513
514 return SCIP_OKAY;
515 }
516
517
518 /** initialization method of Benders' decomposition cuts (called after problem was transformed) */
519 static
SCIP_DECL_BENDERSCUTINIT(benderscutInitInt)520 SCIP_DECL_BENDERSCUTINIT(benderscutInitInt)
521 { /*lint --e{715}*/
522 SCIP_BENDERSCUTDATA* benderscutdata;
523
524 assert( benderscut != NULL );
525 assert( strcmp(SCIPbenderscutGetName(benderscut), BENDERSCUT_NAME) == 0 );
526
527 /* free Benders' cut data */
528 benderscutdata = SCIPbenderscutGetData(benderscut);
529 assert( benderscutdata != NULL );
530
531 benderscutdata->nsubproblems = SCIPbendersGetNSubproblems(benderscutdata->benders);
532 SCIP_CALL( createBenderscutData(scip, benderscutdata) );
533
534 return SCIP_OKAY;
535 }
536
537 /** deinitialization method of Benders' decomposition cuts (called before transformed problem is freed) */
538 static
SCIP_DECL_BENDERSCUTEXIT(benderscutExitInt)539 SCIP_DECL_BENDERSCUTEXIT(benderscutExitInt)
540 { /*lint --e{715}*/
541 SCIP_BENDERSCUTDATA* benderscutdata;
542
543 assert( benderscut != NULL );
544 assert( strcmp(SCIPbenderscutGetName(benderscut), BENDERSCUT_NAME) == 0 );
545
546 /* free Benders' cut data */
547 benderscutdata = SCIPbenderscutGetData(benderscut);
548 assert( benderscutdata != NULL );
549
550 SCIPfreeBlockMemoryArray(scip, &benderscutdata->firstcut, benderscutdata->nsubproblems);
551 SCIPfreeBlockMemoryArray(scip, &benderscutdata->subprobconstant, benderscutdata->nsubproblems);
552
553 return SCIP_OKAY;
554 }
555
556 /** execution method of Benders' decomposition cuts */
557 static
SCIP_DECL_BENDERSCUTEXEC(benderscutExecInt)558 SCIP_DECL_BENDERSCUTEXEC(benderscutExecInt)
559 { /*lint --e{715}*/
560 SCIP* subproblem;
561
562 assert(scip != NULL);
563 assert(benders != NULL);
564 assert(benderscut != NULL);
565 assert(result != NULL);
566
567 subproblem = SCIPbendersSubproblem(benders, probnumber);
568
569 if( subproblem == NULL )
570 {
571 SCIPdebugMsg(scip, "The subproblem %d is set to NULL. The <%s> Benders' decomposition cut can not be executed.\n",
572 probnumber, BENDERSCUT_NAME);
573
574 (*result) = SCIP_DIDNOTRUN;
575 return SCIP_OKAY;
576 }
577
578 /* it is only possible to generate the Laporte and Louveaux cuts for pure binary master problems */
579 if( SCIPgetNBinVars(scip) != (SCIPgetNVars(scip) - SCIPbendersGetNSubproblems(benders))
580 && (!SCIPbendersMasterIsNonlinear(benders)
581 || SCIPgetNBinVars(scip) != (SCIPgetNVars(scip) - SCIPbendersGetNSubproblems(benders) - 1)) )
582 {
583 SCIPinfoMessage(scip, NULL, "The integer optimality cuts can only be applied to problems with a "
584 "pure binary master problem. The integer optimality cuts will be disabled.\n");
585
586 SCIPbenderscutSetEnabled(benderscut, FALSE);
587
588 return SCIP_OKAY;
589 }
590
591 /* the integer subproblem could terminate early if the auxiliary variable value is much greater than the optimal
592 * solution. As such, it is only necessary to generate a cut if the subproblem is OPTIMAL */
593 if( SCIPgetStatus(subproblem) == SCIP_STATUS_OPTIMAL )
594 {
595 /* generating a cut for a given subproblem */
596 SCIP_CALL( generateAndApplyBendersIntegerCuts(scip, benders, benderscut, sol, probnumber, type, result, FALSE) );
597 }
598
599 return SCIP_OKAY;
600 }
601
602
603 /*
604 * Benders' decomposition cuts specific interface methods
605 */
606
607 /** creates the int Benders' decomposition cuts and includes it in SCIP */
SCIPincludeBenderscutInt(SCIP * scip,SCIP_BENDERS * benders)608 SCIP_RETCODE SCIPincludeBenderscutInt(
609 SCIP* scip, /**< SCIP data structure */
610 SCIP_BENDERS* benders /**< Benders' decomposition */
611 )
612 {
613 SCIP_BENDERSCUTDATA* benderscutdata;
614 SCIP_BENDERSCUT* benderscut;
615 char paramname[SCIP_MAXSTRLEN];
616
617 assert(benders != NULL);
618
619 /* create int Benders' decomposition cuts data */
620 SCIP_CALL( SCIPallocBlockMemory(scip, &benderscutdata) );
621 benderscutdata->benders = benders;
622
623 benderscut = NULL;
624
625 /* include Benders' decomposition cuts */
626 SCIP_CALL( SCIPincludeBenderscutBasic(scip, benders, &benderscut, BENDERSCUT_NAME, BENDERSCUT_DESC,
627 BENDERSCUT_PRIORITY, BENDERSCUT_LPCUT, benderscutExecInt, benderscutdata) );
628
629 assert(benderscut != NULL);
630
631 /* set non fundamental callbacks via setter functions */
632 SCIP_CALL( SCIPsetBenderscutFree(scip, benderscut, benderscutFreeInt) );
633 SCIP_CALL( SCIPsetBenderscutInit(scip, benderscut, benderscutInitInt) );
634 SCIP_CALL( SCIPsetBenderscutExit(scip, benderscut, benderscutExitInt) );
635
636 /* add int Benders' decomposition cuts parameters */
637 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/benderscut/%s/cutsconstant",
638 SCIPbendersGetName(benders), BENDERSCUT_NAME);
639 SCIP_CALL( SCIPaddRealParam(scip, paramname,
640 "the constant term of the integer Benders' cuts.",
641 &benderscutdata->cutconstant, FALSE, SCIP_DEFAULT_CUTCONSTANT, -SCIPinfinity(scip), SCIPinfinity(scip),
642 paramChgdBenderscutintConstant, (SCIP_PARAMDATA*)benderscutdata) );
643
644 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/benderscut/%s/addcuts",
645 SCIPbendersGetName(benders), BENDERSCUT_NAME);
646 SCIP_CALL( SCIPaddBoolParam(scip, paramname,
647 "should cuts be generated and added to the cutpool instead of global constraints directly added to the problem.",
648 &benderscutdata->addcuts, FALSE, SCIP_DEFAULT_ADDCUTS, NULL, NULL) );
649
650 return SCIP_OKAY;
651 }
652