Scippy

SCIP

Solving Constraint Integer Programs

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-2024 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 SCIP_DEFAULT_ADDCUTS
#define BENDERSCUT_LPCUT
static SCIP_RETCODE generateAndApplyBendersNogoodCut(SCIP *masterprob, SCIP_BENDERS *benders, SCIP_BENDERSCUT *benderscut, SCIP_SOL *sol, SCIP_BENDERSENFOTYPE type, SCIP_RESULT *result)
#define BENDERSCUT_PRIORITY
#define BENDERSCUT_DESC
#define BENDERSCUT_NAME
static SCIP_DECL_BENDERSCUTEXEC(benderscutExecNogood)
static SCIP_RETCODE computeNogoodCut(SCIP *masterprob, SCIP_BENDERS *benders, SCIP_SOL *sol, SCIP_CONS *cons, SCIP_ROW *row, SCIP_Bool addcut)
static SCIP_DECL_BENDERSCUTFREE(benderscutFreeNogood)
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:267
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
#define SCIP_CALL(x)
Definition: def.h:374
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)
Definition: scip_general.c:498
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
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,...)
Definition: scip_message.c:208
#define SCIPdebugMsg
Definition: scip_message.h:78
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:5924
int SCIPbendersGetNSubproblems(SCIP_BENDERS *benders)
Definition: benders.c:5968
SCIP * SCIPbendersSubproblem(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:5978
SCIP_Bool SCIPbendersMasterIsNonlinear(SCIP_BENDERS *benders)
Definition: benders.c:6437
int SCIPbendersGetNCalls(SCIP_BENDERS *benders)
Definition: benders.c:5990
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, SCIP_DECL_BENDERSCUTFREE((*benderscutfree)))
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:1217
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:17599
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
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)
Definition: pub_message.h:102
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
@ SCIP_BENDERSENFOTYPE_RELAX
Definition: type_benders.h:47
@ SCIP_BENDERSENFOTYPE_LP
Definition: type_benders.h:46
@ SCIP_BENDERSENFOTYPE_CHECK
Definition: type_benders.h:49
@ SCIP_BENDERSENFOTYPE_PSEUDO
Definition: type_benders.h:48
enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE
Definition: type_benders.h:51
struct SCIP_BenderscutData SCIP_BENDERSCUTDATA
@ 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
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_STAGE_INITSOLVE
Definition: type_set.h:52
@ SCIP_STATUS_INFEASIBLE
Definition: type_stat.h:62