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