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