SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
benderscut_nogood.c
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-2025 Zuse Institute Berlin (ZIB) */
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 benderscut_nogood.c
26 * @ingroup OTHER_CFILES
27 * @brief Generates a no good cut for integer solutions that are infeasible for the subproblems
28 * @author Stephen J. Maher
29 */
30
31/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32
34#include "scip/cons_linear.h"
35#include "scip/pub_benderscut.h"
36#include "scip/pub_benders.h"
37#include "scip/pub_lp.h"
38#include "scip/pub_message.h"
39#include "scip/pub_misc.h"
40#include "scip/pub_var.h"
41#include "scip/scip_benders.h"
42#include "scip/scip_cons.h"
43#include "scip/scip_cut.h"
44#include "scip/scip_general.h"
45#include "scip/scip_lp.h"
46#include "scip/scip_mem.h"
47#include "scip/scip_message.h"
48#include "scip/scip_numerics.h"
49#include "scip/scip_param.h"
50#include "scip/scip_prob.h"
51#include "scip/scip_sol.h"
52#include <string.h>
53
54#define BENDERSCUT_NAME "nogood"
55#define BENDERSCUT_DESC "no good Benders' decomposition integer cut"
56#define BENDERSCUT_PRIORITY 500
57#define BENDERSCUT_LPCUT FALSE
58
59
60
61#define SCIP_DEFAULT_ADDCUTS FALSE /** Should cuts be generated, instead of constraints */
62
63/*
64 * Data structures
65 */
66
67/** Benders' decomposition cuts data */
68struct SCIP_BenderscutData
69{
70 SCIP_BENDERS* benders; /**< the Benders' decomposition data structure */
71 int curriter; /**< the current Benders' decomposition subproblem solve iteration */
72 SCIP_Bool addcuts; /**< should cuts be generated instead of constraints */
73 SCIP_Bool cutadded; /**< has a cut been added in the current iteration. Only one cut per round */
74};
75
76
77/*
78 * Local methods
79 */
80
81/** compute no good cut */
82static
84 SCIP* masterprob, /**< the SCIP instance of the master problem */
85 SCIP_BENDERS* benders, /**< the benders' decomposition structure */
86 SCIP_SOL* sol, /**< primal CIP solution */
87 SCIP_CONS* cons, /**< the constraint for the generated cut, can be NULL */
88 SCIP_ROW* row, /**< the row for the generated cut, can be NULL */
89 SCIP_Bool addcut /**< indicates whether a cut is created instead of a constraint */
90 )
91{
92 SCIP_VAR** vars;
93 int nvars;
94 SCIP_Real lhs;
95 int i;
96#ifndef NDEBUG
97 SCIP_Real verifycons;
98#endif
99
100 assert(masterprob != NULL);
101 assert(benders != NULL);
102 assert(cons != NULL || addcut);
103 assert(row != NULL || !addcut);
104
105 nvars = SCIPgetNVars(masterprob);
106 vars = SCIPgetVars(masterprob);
107
108 /* adding the subproblem objective function value to the lhs */
109 if( addcut )
110 lhs = SCIProwGetLhs(row);
111 else
112 lhs = SCIPgetLhsLinear(masterprob, cons);
113
114 /* adding the violation to the lhs */
115 lhs += 1.0;
116
117 /* looping over all master problem variables to update the coefficients in the computed cut. */
118 for( i = 0; i < nvars; i++ )
119 {
120 SCIP_Real coef;
121
122 if( !SCIPvarIsBinary(vars[i]) )
123 continue;
124
125 /* if the variable is on its upper bound, then the subproblem objective value is added to the cut */
126 if( SCIPisFeasEQ(masterprob, SCIPgetSolVal(masterprob, sol, vars[i]), 1.0) )
127 {
128 coef = -1.0;
129 lhs -= 1.0;
130 }
131 else
132 coef = 1.0;
133
134 /* adding the variable to the cut. The coefficient is the subproblem objective value */
135 if( addcut )
136 {
137 SCIP_CALL( SCIPaddVarToRow(masterprob, row, vars[i], coef) );
138 }
139 else
140 {
141 SCIP_CALL( SCIPaddCoefLinear(masterprob, cons, vars[i], coef) );
142 }
143 }
144
145 /* Update the lhs of the cut */
146 if( addcut )
147 {
148 SCIP_CALL( SCIPchgRowLhs(masterprob, row, lhs) );
149 }
150 else
151 {
152 SCIP_CALL( SCIPchgLhsLinear(masterprob, cons, lhs) );
153 }
154
155#ifndef NDEBUG
156 if( addcut )
157 verifycons = SCIPgetRowSolActivity(masterprob, row, sol);
158 else
159 verifycons = SCIPgetActivityLinear(masterprob, cons, sol);
160#endif
161
162 assert(SCIPisFeasEQ(masterprob, verifycons, lhs - 1));
163
164 return SCIP_OKAY;
165}
166
167
168
169/** generates and applies Benders' cuts */
170static
172 SCIP* masterprob, /**< the SCIP instance of the master problem */
173 SCIP_BENDERS* benders, /**< the benders' decomposition */
174 SCIP_BENDERSCUT* benderscut, /**< the benders' decomposition cut method */
175 SCIP_SOL* sol, /**< primal CIP solution */
176 SCIP_BENDERSENFOTYPE type, /**< the enforcement type calling this function */
177 SCIP_RESULT* result /**< the result from solving the subproblems */
178 )
179{
180 SCIP_BENDERSCUTDATA* benderscutdata;
181 SCIP_CONSHDLR* consbenders;
182 SCIP_CONS* cons;
183 SCIP_ROW* row;
184 char cutname[SCIP_MAXSTRLEN];
185 SCIP_Bool addcut;
186
187 assert(masterprob != NULL);
188 assert(benders != NULL);
189 assert(benderscut != NULL);
190 assert(result != NULL);
191
192 row = NULL;
193 cons = NULL;
194
195 /* retrieving the Benders' cut data */
196 benderscutdata = SCIPbenderscutGetData(benderscut);
197
198 /* if the cuts are generated prior to the solving stage, then rows can not be generated. So constraints must be
199 * added to the master problem.
200 */
201 if( SCIPgetStage(masterprob) < SCIP_STAGE_INITSOLVE )
202 addcut = FALSE;
203 else
204 addcut = benderscutdata->addcuts;
205
206 /* retrieving the Benders' decomposition constraint handler */
207 consbenders = SCIPfindConshdlr(masterprob, "benders");
208
209 /* setting the name of the generated cut */
210 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "nogoodcut_%" SCIP_LONGINT_FORMAT, SCIPbenderscutGetNFound(benderscut) );
211
212 /* creating an empty row or constraint for the Benders' cut */
213 if( addcut )
214 {
215 SCIP_CALL( SCIPcreateEmptyRowConshdlr(masterprob, &row, consbenders, cutname, 0.0, SCIPinfinity(masterprob), FALSE,
216 FALSE, TRUE) );
217 }
218 else
219 {
220 SCIP_CALL( SCIPcreateConsBasicLinear(masterprob, &cons, cutname, 0, NULL, NULL, 0.0, SCIPinfinity(masterprob)) );
221 SCIP_CALL( SCIPsetConsDynamic(masterprob, cons, TRUE) );
222 SCIP_CALL( SCIPsetConsRemovable(masterprob, cons, TRUE) );
223 }
224
225 /* computing the coefficients of the optimality cut */
226 SCIP_CALL( computeNogoodCut(masterprob, benders, sol, cons, row, addcut) );
227
228 /* adding the constraint to the master problem */
229 if( addcut )
230 {
231 SCIP_Bool infeasible;
232
234 {
235 SCIP_CALL( SCIPaddRow(masterprob, row, FALSE, &infeasible) );
236 assert(!infeasible);
237 }
238 else
239 {
241 SCIP_CALL( SCIPaddPoolCut(masterprob, row) );
242 }
243
244#ifdef SCIP_DEBUG
245 SCIP_CALL( SCIPprintRow(masterprob, row, NULL) );
246 SCIPinfoMessage(masterprob, NULL, ";\n");
247#endif
248
249 /* release the row */
250 SCIP_CALL( SCIPreleaseRow(masterprob, &row) );
251
252 (*result) = SCIP_SEPARATED;
253 }
254 else
255 {
256 SCIP_CALL( SCIPaddCons(masterprob, cons) );
257
258 SCIPdebugPrintCons(masterprob, cons, NULL);
259
260 SCIP_CALL( SCIPreleaseCons(masterprob, &cons) );
261
262 (*result) = SCIP_CONSADDED;
263 }
264
265 /* updating the cut added flag */
266 benderscutdata->cutadded = TRUE;
267
268 return SCIP_OKAY;
269}
270
271/*
272 * Callback methods of Benders' decomposition cuts
273 */
274
275/** destructor of Benders' decomposition cuts to free user data (called when SCIP is exiting) */
276static
277SCIP_DECL_BENDERSCUTFREE(benderscutFreeNogood)
278{ /*lint --e{715}*/
279 SCIP_BENDERSCUTDATA* benderscutdata;
280
281 assert( benderscut != NULL );
282 assert( strcmp(SCIPbenderscutGetName(benderscut), BENDERSCUT_NAME) == 0 );
283
284 /* free Benders' cut data */
285 benderscutdata = SCIPbenderscutGetData(benderscut);
286 assert( benderscutdata != NULL );
287
288 SCIPfreeBlockMemory(scip, &benderscutdata);
289
290 SCIPbenderscutSetData(benderscut, NULL);
291
292 return SCIP_OKAY;
293}
294
295
296/** execution method of Benders' decomposition cuts */
297static
298SCIP_DECL_BENDERSCUTEXEC(benderscutExecNogood)
299{ /*lint --e{715}*/
300 SCIP* subproblem;
301 SCIP_BENDERSCUTDATA* benderscutdata;
302
303 assert(scip != NULL);
304 assert(benders != NULL);
305 assert(benderscut != NULL);
306 assert(result != NULL);
307
308 subproblem = SCIPbendersSubproblem(benders, probnumber);
309
310 if( subproblem == NULL )
311 {
312 SCIPdebugMsg(scip, "The subproblem %d is set to NULL. The <%s> Benders' decomposition cut can not be executed.\n",
313 probnumber, BENDERSCUT_NAME);
314
315 (*result) = SCIP_DIDNOTRUN;
316 return SCIP_OKAY;
317 }
318
319 benderscutdata = SCIPbenderscutGetData(benderscut);
320 assert(benderscutdata != NULL);
321
322 /* if the curriter is less than the number of Benders' decomposition calls, then we are in a new round.
323 * So the cutadded flag must be set to FALSE
324 */
325 if( benderscutdata->curriter < SCIPbendersGetNCalls(benders) )
326 {
327 benderscutdata->curriter = SCIPbendersGetNCalls(benders);
328 benderscutdata->cutadded = FALSE;
329 }
330
331 /* if a cut has been added in this Benders' decomposition call, then no more must be added */
332 if( benderscutdata->cutadded )
333 return SCIP_OKAY;
334
335 /* it is only possible to generate the no-good cut for pure binary master problems */
337 && (!SCIPbendersMasterIsNonlinear(benders)
339 {
340 SCIPinfoMessage(scip, NULL, "The no-good cuts can only be applied to problems with a pure binary master problem. "
341 "The no-good Benders' decomposition cuts will be disabled.\n");
342
343 SCIPbenderscutSetEnabled(benderscut, FALSE);
344
345 return SCIP_OKAY;
346 }
347
348 /* We can not rely on complete recourse for the subproblems. As such, the subproblems may be feasible for the LP, but
349 * infeasible for the IP. As such, if one subproblem is infeasible, then a no good cut is generated.
350 */
351 if( SCIPgetStatus(subproblem) == SCIP_STATUS_INFEASIBLE )
352 {
353 /* generating a cut */
354 SCIP_CALL( generateAndApplyBendersNogoodCut(scip, benders, benderscut, sol, type, result) );
355 }
356
357 return SCIP_OKAY;
358}
359
360
361/*
362 * Benders' decomposition cuts specific interface methods
363 */
364
365/** creates the nogood Benders' decomposition cuts and includes it in SCIP */
367 SCIP* scip, /**< SCIP data structure */
368 SCIP_BENDERS* benders /**< Benders' decomposition */
369 )
370{
371 SCIP_BENDERSCUTDATA* benderscutdata;
372 SCIP_BENDERSCUT* benderscut;
374
375 assert(benders != NULL);
376
377 /* create nogood Benders' decomposition cuts data */
378 SCIP_CALL( SCIPallocBlockMemory(scip, &benderscutdata) );
379 benderscutdata->benders = benders;
380 benderscutdata->curriter = -1;
381 benderscutdata->cutadded = FALSE;
382
383 benderscut = NULL;
384
385 /* include Benders' decomposition cuts */
387 BENDERSCUT_PRIORITY, BENDERSCUT_LPCUT, benderscutExecNogood, benderscutdata) );
388
389 assert(benderscut != NULL);
390
391 /* set non fundamental callbacks via setter functions */
392 SCIP_CALL( SCIPsetBenderscutFree(scip, benderscut, benderscutFreeNogood) );
393
394 /* add nogood Benders' decomposition cuts parameters */
395 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/benderscut/%s/addcuts",
398 "should cuts be generated and added to the cutpool instead of global constraints directly added to the problem.",
399 &benderscutdata->addcuts, FALSE, SCIP_DEFAULT_ADDCUTS, NULL, NULL) );
400
401 return SCIP_OKAY;
402}
#define BENDERSCUT_LPCUT
#define BENDERSCUT_PRIORITY
#define BENDERSCUT_DESC
#define BENDERSCUT_NAME
#define SCIP_DEFAULT_ADDCUTS
static SCIP_RETCODE generateAndApplyBendersNogoodCut(SCIP *masterprob, SCIP_BENDERS *benders, SCIP_BENDERSCUT *benderscut, SCIP_SOL *sol, SCIP_BENDERSENFOTYPE type, SCIP_RESULT *result)
static SCIP_RETCODE computeNogoodCut(SCIP *masterprob, SCIP_BENDERS *benders, SCIP_SOL *sol, SCIP_CONS *cons, SCIP_ROW *row, SCIP_Bool addcut)
Generates a no-good cut for solutions that are integer infeasible.
Constraint handler for linear constraints in their most general form, .
#define NULL
Definition def.h:266
#define SCIP_MAXSTRLEN
Definition def.h:287
#define SCIP_Bool
Definition def.h:91
#define SCIP_Real
Definition def.h:172
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define SCIP_LONGINT_FORMAT
Definition def.h:164
#define SCIP_CALL(x)
Definition def.h:373
SCIP_RETCODE SCIPincludeBenderscutNogood(SCIP *scip, SCIP_BENDERS *benders)
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
SCIP_Real SCIPgetActivityLinear(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
Definition scip_prob.c:1992
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:2770
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition scip_prob.c:1947
int SCIPgetNBinVars(SCIP *scip)
Definition scip_prob.c:2037
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
#define SCIPdebugMsg
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:57
const char * SCIPbendersGetName(SCIP_BENDERS *benders)
Definition benders.c:5946
int SCIPbendersGetNSubproblems(SCIP_BENDERS *benders)
Definition benders.c:5990
SCIP * SCIPbendersSubproblem(SCIP_BENDERS *benders, int probnumber)
Definition benders.c:6000
SCIP_Bool SCIPbendersMasterIsNonlinear(SCIP_BENDERS *benders)
Definition benders.c:6459
int SCIPbendersGetNCalls(SCIP_BENDERS *benders)
Definition benders.c:6012
SCIP_RETCODE SCIPincludeBenderscutBasic(SCIP *scip, SCIP_BENDERS *benders, SCIP_BENDERSCUT **benderscutptr, const char *name, const char *desc, int priority, SCIP_Bool islpcut, SCIP_DECL_BENDERSCUTEXEC((*benderscutexec)), SCIP_BENDERSCUTDATA *benderscutdata)
SCIP_RETCODE SCIPsetBenderscutFree(SCIP *scip, SCIP_BENDERSCUT *benderscut,)
void SCIPbenderscutSetData(SCIP_BENDERSCUT *benderscut, SCIP_BENDERSCUTDATA *benderscutdata)
Definition benderscut.c:413
const char * SCIPbenderscutGetName(SCIP_BENDERSCUT *benderscut)
Definition benderscut.c:492
SCIP_BENDERSCUTDATA * SCIPbenderscutGetData(SCIP_BENDERSCUT *benderscut)
Definition benderscut.c:403
SCIP_Longint SCIPbenderscutGetNFound(SCIP_BENDERSCUT *benderscut)
Definition benderscut.c:543
void SCIPbenderscutSetEnabled(SCIP_BENDERSCUT *benderscut, SCIP_Bool enabled)
Definition benderscut.c:593
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition scip_cons.c:941
SCIP_RETCODE SCIPsetConsDynamic(SCIP *scip, SCIP_CONS *cons, SCIP_Bool dynamic)
Definition scip_cons.c:1450
SCIP_RETCODE SCIPsetConsRemovable(SCIP *scip, SCIP_CONS *cons, SCIP_Bool removable)
Definition scip_cons.c:1475
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition scip_cons.c:1174
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition scip_cut.c:361
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition scip_cut.c:250
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition lp.c:17292
SCIP_RETCODE SCIPchgRowLhs(SCIP *scip, SCIP_ROW *row, SCIP_Real lhs)
Definition scip_lp.c:1583
SCIP_RETCODE SCIPcreateEmptyRowConshdlr(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition scip_lp.c:1391
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition scip_lp.c:1701
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition scip_lp.c:2212
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition scip_lp.c:1562
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition scip_lp.c:2144
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1213
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition var.c:17619
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10880
return SCIP_OKAY
static SCIP_SOL * sol
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
static SCIP_VAR ** vars
static const char * paramname[]
Definition lpi_msk.c:5096
public methods for Benders' decomposition
public methods for Benders' decomposition cuts
public methods for LP management
public methods for message output
#define SCIPdebugPrintCons(x, y, z)
public data structures and miscellaneous methods
public methods for problem variables
public methods for Benders decomposition
public methods for constraint handler plugins and constraints
public methods for cuts and aggregation rows
general public methods
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for solutions
struct SCIP_Benders SCIP_BENDERS
@ SCIP_BENDERSENFOTYPE_RELAX
@ SCIP_BENDERSENFOTYPE_LP
@ SCIP_BENDERSENFOTYPE_CHECK
@ SCIP_BENDERSENFOTYPE_PSEUDO
enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE
struct SCIP_Benderscut SCIP_BENDERSCUT
#define SCIP_DECL_BENDERSCUTEXEC(x)
struct SCIP_BenderscutData SCIP_BENDERSCUTDATA
#define SCIP_DECL_BENDERSCUTFREE(x)
struct SCIP_Cons SCIP_CONS
Definition type_cons.h:63
struct SCIP_Conshdlr SCIP_CONSHDLR
Definition type_cons.h:62
struct SCIP_Row SCIP_ROW
Definition type_lp.h:104
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_CONSADDED
Definition type_result.h:52
@ SCIP_SEPARATED
Definition type_result.h:49
enum SCIP_Result SCIP_RESULT
Definition type_result.h:61
enum SCIP_Retcode SCIP_RETCODE
struct Scip SCIP
Definition type_scip.h:39
@ SCIP_STAGE_INITSOLVE
Definition type_set.h:52
struct SCIP_Sol SCIP_SOL
Definition type_sol.h:57
@ SCIP_STATUS_INFEASIBLE
Definition type_stat.h:62
struct SCIP_Var SCIP_VAR
Definition type_var.h:119