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_nogood.c
17 * @ingroup OTHER_CFILES
18 * @brief Generates a no good cut for integer solutions that are infeasible for the subproblems
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_nogood.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_var.h"
32 #include "scip/scip_benders.h"
33 #include "scip/scip_cons.h"
34 #include "scip/scip_cut.h"
35 #include "scip/scip_general.h"
36 #include "scip/scip_lp.h"
37 #include "scip/scip_mem.h"
38 #include "scip/scip_message.h"
39 #include "scip/scip_numerics.h"
40 #include "scip/scip_param.h"
41 #include "scip/scip_prob.h"
42 #include "scip/scip_sol.h"
43 #include <string.h>
44
45 #define BENDERSCUT_NAME "nogood"
46 #define BENDERSCUT_DESC "no good Benders' decomposition integer cut"
47 #define BENDERSCUT_PRIORITY 500
48 #define BENDERSCUT_LPCUT FALSE
49
50
51
52 #define SCIP_DEFAULT_ADDCUTS FALSE /** Should cuts be generated, instead of constraints */
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 int curriter; /**< the current Benders' decomposition subproblem solve iteration */
63 SCIP_Bool addcuts; /**< should cuts be generated instead of constraints */
64 SCIP_Bool cutadded; /**< has a cut been added in the current iteration. Only one cut per round */
65 };
66
67
68 /*
69 * Local methods
70 */
71
72 /** compute no good cut */
73 static
computeNogoodCut(SCIP * masterprob,SCIP_BENDERS * benders,SCIP_SOL * sol,SCIP_CONS * cons,SCIP_ROW * row,SCIP_Bool addcut)74 SCIP_RETCODE computeNogoodCut(
75 SCIP* masterprob, /**< the SCIP instance of the master problem */
76 SCIP_BENDERS* benders, /**< the benders' decomposition structure */
77 SCIP_SOL* sol, /**< primal CIP solution */
78 SCIP_CONS* cons, /**< the constraint for the generated cut, can be NULL */
79 SCIP_ROW* row, /**< the row for the generated cut, can be NULL */
80 SCIP_Bool addcut /**< indicates whether a cut is created instead of a constraint */
81 )
82 {
83 SCIP_VAR** vars;
84 int nvars;
85 SCIP_Real lhs;
86 int i;
87 #ifndef NDEBUG
88 SCIP_Real verifycons;
89 #endif
90
91 assert(masterprob != NULL);
92 assert(benders != NULL);
93 assert(cons != NULL || addcut);
94 assert(row != NULL || !addcut);
95
96 nvars = SCIPgetNVars(masterprob);
97 vars = SCIPgetVars(masterprob);
98
99 /* adding the subproblem objective function value to the lhs */
100 if( addcut )
101 lhs = SCIProwGetLhs(row);
102 else
103 lhs = SCIPgetLhsLinear(masterprob, cons);
104
105 /* adding the violation to the lhs */
106 lhs += 1.0;
107
108 /* looping over all master problem variables to update the coefficients in the computed cut. */
109 for( i = 0; i < nvars; i++ )
110 {
111 SCIP_Real coef;
112
113 if( !SCIPvarIsBinary(vars[i]) )
114 continue;
115
116 /* if the variable is on its upper bound, then the subproblem objective value is added to the cut */
117 if( SCIPisFeasEQ(masterprob, SCIPgetSolVal(masterprob, sol, vars[i]), 1.0) )
118 {
119 coef = -1.0;
120 lhs -= 1.0;
121 }
122 else
123 coef = 1.0;
124
125 /* adding the variable to the cut. The coefficient is the subproblem objective value */
126 if( addcut )
127 {
128 SCIP_CALL( SCIPaddVarToRow(masterprob, row, vars[i], coef) );
129 }
130 else
131 {
132 SCIP_CALL( SCIPaddCoefLinear(masterprob, cons, vars[i], coef) );
133 }
134 }
135
136 /* Update the lhs of the cut */
137 if( addcut )
138 {
139 SCIP_CALL( SCIPchgRowLhs(masterprob, row, lhs) );
140 }
141 else
142 {
143 SCIP_CALL( SCIPchgLhsLinear(masterprob, cons, lhs) );
144 }
145
146 #ifndef NDEBUG
147 if( addcut )
148 verifycons = SCIPgetRowSolActivity(masterprob, row, sol);
149 else
150 verifycons = SCIPgetActivityLinear(masterprob, cons, sol);
151 #endif
152
153 assert(SCIPisFeasEQ(masterprob, verifycons, lhs - 1));
154
155 return SCIP_OKAY;
156 }
157
158
159
160 /** generates and applies Benders' cuts */
161 static
generateAndApplyBendersNogoodCut(SCIP * masterprob,SCIP_BENDERS * benders,SCIP_BENDERSCUT * benderscut,SCIP_SOL * sol,SCIP_BENDERSENFOTYPE type,SCIP_RESULT * result)162 SCIP_RETCODE generateAndApplyBendersNogoodCut(
163 SCIP* masterprob, /**< the SCIP instance of the master problem */
164 SCIP_BENDERS* benders, /**< the benders' decomposition */
165 SCIP_BENDERSCUT* benderscut, /**< the benders' decomposition cut method */
166 SCIP_SOL* sol, /**< primal CIP solution */
167 SCIP_BENDERSENFOTYPE type, /**< the enforcement type calling this function */
168 SCIP_RESULT* result /**< the result from solving the subproblems */
169 )
170 {
171 SCIP_BENDERSCUTDATA* benderscutdata;
172 SCIP_CONSHDLR* consbenders;
173 SCIP_CONS* cons;
174 SCIP_ROW* row;
175 char cutname[SCIP_MAXSTRLEN];
176 SCIP_Bool addcut;
177
178 assert(masterprob != NULL);
179 assert(benders != NULL);
180 assert(benderscut != NULL);
181 assert(result != NULL);
182
183 row = NULL;
184 cons = NULL;
185
186 /* retrieving the Benders' cut data */
187 benderscutdata = SCIPbenderscutGetData(benderscut);
188
189 /* if the cuts are generated prior to the solving stage, then rows can not be generated. So constraints must be
190 * added to the master problem.
191 */
192 if( SCIPgetStage(masterprob) < SCIP_STAGE_INITSOLVE )
193 addcut = FALSE;
194 else
195 addcut = benderscutdata->addcuts;
196
197 /* retrieving the Benders' decomposition constraint handler */
198 consbenders = SCIPfindConshdlr(masterprob, "benders");
199
200 /* setting the name of the generated cut */
201 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "nogoodcut_%" SCIP_LONGINT_FORMAT, SCIPbenderscutGetNFound(benderscut) );
202
203 /* creating an empty row or constraint for the Benders' cut */
204 if( addcut )
205 {
206 SCIP_CALL( SCIPcreateEmptyRowConshdlr(masterprob, &row, consbenders, cutname, 0.0, SCIPinfinity(masterprob), FALSE,
207 FALSE, TRUE) );
208 }
209 else
210 {
211 SCIP_CALL( SCIPcreateConsBasicLinear(masterprob, &cons, cutname, 0, NULL, NULL, 0.0, SCIPinfinity(masterprob)) );
212 SCIP_CALL( SCIPsetConsDynamic(masterprob, cons, TRUE) );
213 SCIP_CALL( SCIPsetConsRemovable(masterprob, cons, TRUE) );
214 }
215
216 /* computing the coefficients of the optimality cut */
217 SCIP_CALL( computeNogoodCut(masterprob, benders, sol, cons, row, addcut) );
218
219 /* adding the constraint to the master problem */
220 if( addcut )
221 {
222 SCIP_Bool infeasible;
223
224 if( type == SCIP_BENDERSENFOTYPE_LP || type == SCIP_BENDERSENFOTYPE_RELAX )
225 {
226 SCIP_CALL( SCIPaddRow(masterprob, row, FALSE, &infeasible) );
227 assert(!infeasible);
228 }
229 else
230 {
231 assert(type == SCIP_BENDERSENFOTYPE_CHECK || type == SCIP_BENDERSENFOTYPE_PSEUDO);
232 SCIP_CALL( SCIPaddPoolCut(masterprob, row) );
233 }
234
235 #ifdef SCIP_DEBUG
236 SCIP_CALL( SCIPprintRow(masterprob, row, NULL) );
237 SCIPinfoMessage(masterprob, NULL, ";\n");
238 #endif
239
240 /* release the row */
241 SCIP_CALL( SCIPreleaseRow(masterprob, &row) );
242
243 (*result) = SCIP_SEPARATED;
244 }
245 else
246 {
247 SCIP_CALL( SCIPaddCons(masterprob, cons) );
248
249 SCIPdebugPrintCons(masterprob, cons, NULL);
250
251 SCIP_CALL( SCIPreleaseCons(masterprob, &cons) );
252
253 (*result) = SCIP_CONSADDED;
254 }
255
256 /* updating the cut added flag */
257 benderscutdata->cutadded = TRUE;
258
259 return SCIP_OKAY;
260 }
261
262 /*
263 * Callback methods of Benders' decomposition cuts
264 */
265
266 /** destructor of Benders' decomposition cuts to free user data (called when SCIP is exiting) */
267 static
SCIP_DECL_BENDERSCUTFREE(benderscutFreeNogood)268 SCIP_DECL_BENDERSCUTFREE(benderscutFreeNogood)
269 { /*lint --e{715}*/
270 SCIP_BENDERSCUTDATA* benderscutdata;
271
272 assert( benderscut != NULL );
273 assert( strcmp(SCIPbenderscutGetName(benderscut), BENDERSCUT_NAME) == 0 );
274
275 /* free Benders' cut data */
276 benderscutdata = SCIPbenderscutGetData(benderscut);
277 assert( benderscutdata != NULL );
278
279 SCIPfreeBlockMemory(scip, &benderscutdata);
280
281 SCIPbenderscutSetData(benderscut, NULL);
282
283 return SCIP_OKAY;
284 }
285
286
287 /** execution method of Benders' decomposition cuts */
288 static
SCIP_DECL_BENDERSCUTEXEC(benderscutExecNogood)289 SCIP_DECL_BENDERSCUTEXEC(benderscutExecNogood)
290 { /*lint --e{715}*/
291 SCIP* subproblem;
292 SCIP_BENDERSCUTDATA* benderscutdata;
293
294 assert(scip != NULL);
295 assert(benders != NULL);
296 assert(benderscut != NULL);
297 assert(result != NULL);
298
299 subproblem = SCIPbendersSubproblem(benders, probnumber);
300
301 if( subproblem == NULL )
302 {
303 SCIPdebugMsg(scip, "The subproblem %d is set to NULL. The <%s> Benders' decomposition cut can not be executed.\n",
304 probnumber, BENDERSCUT_NAME);
305
306 (*result) = SCIP_DIDNOTRUN;
307 return SCIP_OKAY;
308 }
309
310 benderscutdata = SCIPbenderscutGetData(benderscut);
311 assert(benderscutdata != NULL);
312
313 /* if the curriter is less than the number of Benders' decomposition calls, then we are in a new round.
314 * So the cutadded flag must be set to FALSE
315 */
316 if( benderscutdata->curriter < SCIPbendersGetNCalls(benders) )
317 {
318 benderscutdata->curriter = SCIPbendersGetNCalls(benders);
319 benderscutdata->cutadded = FALSE;
320 }
321
322 /* if a cut has been added in this Benders' decomposition call, then no more must be added */
323 if( benderscutdata->cutadded )
324 return SCIP_OKAY;
325
326 /* it is only possible to generate the no-good cut for pure binary master problems */
327 if( SCIPgetNBinVars(scip) != (SCIPgetNVars(scip) - SCIPbendersGetNSubproblems(benders))
328 && (!SCIPbendersMasterIsNonlinear(benders)
329 || SCIPgetNBinVars(scip) != (SCIPgetNVars(scip) - SCIPbendersGetNSubproblems(benders) - 1)) )
330 {
331 SCIPinfoMessage(scip, NULL, "The no-good cuts can only be applied to problems with a pure binary master problem. "
332 "The no-good Benders' decomposition cuts will be disabled.\n");
333
334 SCIPbenderscutSetEnabled(benderscut, FALSE);
335
336 return SCIP_OKAY;
337 }
338
339 /* We can not rely on complete recourse for the subproblems. As such, the subproblems may be feasible for the LP, but
340 * infeasible for the IP. As such, if one subproblem is infeasible, then a no good cut is generated.
341 */
342 if( SCIPgetStatus(subproblem) == SCIP_STATUS_INFEASIBLE )
343 {
344 /* generating a cut */
345 SCIP_CALL( generateAndApplyBendersNogoodCut(scip, benders, benderscut, sol, type, result) );
346 }
347
348 return SCIP_OKAY;
349 }
350
351
352 /*
353 * Benders' decomposition cuts specific interface methods
354 */
355
356 /** creates the nogood Benders' decomposition cuts and includes it in SCIP */
SCIPincludeBenderscutNogood(SCIP * scip,SCIP_BENDERS * benders)357 SCIP_RETCODE SCIPincludeBenderscutNogood(
358 SCIP* scip, /**< SCIP data structure */
359 SCIP_BENDERS* benders /**< Benders' decomposition */
360 )
361 {
362 SCIP_BENDERSCUTDATA* benderscutdata;
363 SCIP_BENDERSCUT* benderscut;
364 char paramname[SCIP_MAXSTRLEN];
365
366 assert(benders != NULL);
367
368 /* create nogood Benders' decomposition cuts data */
369 SCIP_CALL( SCIPallocBlockMemory(scip, &benderscutdata) );
370 benderscutdata->benders = benders;
371 benderscutdata->curriter = -1;
372 benderscutdata->cutadded = FALSE;
373
374 benderscut = NULL;
375
376 /* include Benders' decomposition cuts */
377 SCIP_CALL( SCIPincludeBenderscutBasic(scip, benders, &benderscut, BENDERSCUT_NAME, BENDERSCUT_DESC,
378 BENDERSCUT_PRIORITY, BENDERSCUT_LPCUT, benderscutExecNogood, benderscutdata) );
379
380 assert(benderscut != NULL);
381
382 /* set non fundamental callbacks via setter functions */
383 SCIP_CALL( SCIPsetBenderscutFree(scip, benderscut, benderscutFreeNogood) );
384
385 /* add nogood Benders' decomposition cuts parameters */
386 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/benderscut/%s/addcuts",
387 SCIPbendersGetName(benders), BENDERSCUT_NAME);
388 SCIP_CALL( SCIPaddBoolParam(scip, paramname,
389 "should cuts be generated and added to the cutpool instead of global constraints directly added to the problem.",
390 &benderscutdata->addcuts, FALSE, SCIP_DEFAULT_ADDCUTS, NULL, NULL) );
391
392 return SCIP_OKAY;
393 }
394