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-2022 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
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
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
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
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 */
328  && (!SCIPbendersMasterIsNonlinear(benders)
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 */
358  SCIP* scip, /**< SCIP data structure */
359  SCIP_BENDERS* benders /**< Benders' decomposition */
360  )
361 {
362  SCIP_BENDERSCUTDATA* benderscutdata;
363  SCIP_BENDERSCUT* benderscut;
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 */
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",
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 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_Real SCIPgetActivityLinear(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
const char * SCIPbenderscutGetName(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:483
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)
static SCIP_DECL_BENDERSCUTEXEC(benderscutExecNogood)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for SCIP parameter handling
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
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)
struct SCIP_BenderscutData SCIP_BENDERSCUTDATA
public methods for memory management
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
SCIP_BENDERSCUTDATA * SCIPbenderscutGetData(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:394
#define SCIP_MAXSTRLEN
Definition: def.h:293
#define BENDERSCUT_LPCUT
const char * SCIPbendersGetName(SCIP_BENDERS *benders)
Definition: benders.c:5895
#define BENDERSCUT_PRIORITY
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1686
SCIP_RETCODE SCIPincludeBenderscutNogood(SCIP *scip, SCIP_BENDERS *benders)
void SCIPbenderscutSetData(SCIP_BENDERSCUT *benderscut, SCIP_BENDERSCUTDATA *benderscutdata)
Definition: benderscut.c:404
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17431
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17225
#define FALSE
Definition: def.h:87
public methods for Benders&#39; decomposition
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE
Definition: type_benders.h:42
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:93
SCIP_Bool SCIPbendersMasterIsNonlinear(SCIP_BENDERS *benders)
Definition: benders.c:6408
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_Longint SCIPbenderscutGetNFound(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:534
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
public methods for numerical tolerances
int SCIPbendersGetNCalls(SCIP_BENDERS *benders)
Definition: benders.c:5961
SCIP_RETCODE SCIPsetConsRemovable(SCIP *scip, SCIP_CONS *cons, SCIP_Bool removable)
Definition: scip_cons.c:1411
void SCIPbenderscutSetEnabled(SCIP_BENDERSCUT *benderscut, SCIP_Bool enabled)
Definition: benderscut.c:584
public methods for Benders decomposition
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2768
#define SCIP_DEFAULT_ADDCUTS
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:474
SCIP_RETCODE SCIPsetConsDynamic(SCIP *scip, SCIP_CONS *cons, SCIP_Bool dynamic)
Definition: scip_cons.c:1386
#define BENDERSCUT_NAME
static SCIP_RETCODE computeNogoodCut(SCIP *masterprob, SCIP_BENDERS *benders, SCIP_SOL *sol, SCIP_CONS *cons, SCIP_ROW *row, SCIP_Bool addcut)
#define BENDERSCUT_DESC
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:241
public methods for constraint handler plugins and constraints
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:84
static const char * paramname[]
Definition: lpi_msk.c:4998
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:352
public methods for LP management
SCIP_RETCODE SCIPchgRowLhs(SCIP *scip, SCIP_ROW *row, SCIP_Real lhs)
Definition: scip_lp.c:1574
public methods for cuts and aggregation rows
SCIP * SCIPbendersSubproblem(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:5949
Constraint handler for linear constraints in their most general form, .
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition: scip_lp.c:2129
int SCIPbendersGetNSubproblems(SCIP_BENDERS *benders)
Definition: benders.c:5939
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2035
public methods for the LP relaxation, rows and columns
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1990
public methods for Benders&#39; decomposition cuts
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1553
general public methods
public methods for solutions
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
public methods for message output
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1945
#define SCIP_Real
Definition: def.h:177
public methods for message handling
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2197
SCIP_RETCODE SCIPsetBenderscutFree(SCIP *scip, SCIP_BENDERSCUT *benderscut, SCIP_DECL_BENDERSCUTFREE((*benderscutfree)))
static SCIP_DECL_BENDERSCUTFREE(benderscutFreeNogood)
Generates a no-good cut for solutions that are integer infeasible.
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
SCIPallocBlockMemory(scip, subsol))
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:1382
public methods for global and local (sub)problems
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
static SCIP_RETCODE generateAndApplyBendersNogoodCut(SCIP *masterprob, SCIP_BENDERS *benders, SCIP_BENDERSCUT *benderscut, SCIP_SOL *sol, SCIP_BENDERSENFOTYPE type, SCIP_RESULT *result)
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
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:48