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 2002-2022 Zuse Institute Berlin */
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 
33 #include "scip/benderscut_nogood.h"
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 */
68 struct 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 */
82 static
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 */
170 static
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 
233  if( type == SCIP_BENDERSENFOTYPE_LP || type == SCIP_BENDERSENFOTYPE_RELAX )
234  {
235  SCIP_CALL( SCIPaddRow(masterprob, row, FALSE, &infeasible) );
236  assert(!infeasible);
237  }
238  else
239  {
240  assert(type == SCIP_BENDERSENFOTYPE_CHECK || type == SCIP_BENDERSENFOTYPE_PSEUDO);
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) */
276 static
277 SCIP_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 */
297 static
298 SCIP_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",
397  SCIP_CALL( SCIPaddBoolParam(scip, paramname,
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 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
SCIP_Real SCIPgetActivityLinear(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
const char * SCIPbenderscutGetName(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:492
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:365
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:886
SCIP_BENDERSCUTDATA * SCIPbenderscutGetData(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:403
#define SCIP_MAXSTRLEN
Definition: def.h:302
#define BENDERSCUT_LPCUT
const char * SCIPbendersGetName(SCIP_BENDERS *benders)
Definition: benders.c:5904
#define BENDERSCUT_PRIORITY
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1695
SCIP_RETCODE SCIPincludeBenderscutNogood(SCIP *scip, SCIP_BENDERS *benders)
void SCIPbenderscutSetData(SCIP_BENDERSCUT *benderscut, SCIP_BENDERSCUTDATA *benderscutdata)
Definition: benderscut.c:413
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17440
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17284
#define FALSE
Definition: def.h:96
public methods for Benders&#39; decomposition
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10764
#define TRUE
Definition: def.h:95
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE
Definition: type_benders.h:51
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:102
SCIP_Bool SCIPbendersMasterIsNonlinear(SCIP_BENDERS *benders)
Definition: benders.c:6417
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_Longint SCIPbenderscutGetNFound(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:543
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:208
public methods for numerical tolerances
int SCIPbendersGetNCalls(SCIP_BENDERS *benders)
Definition: benders.c:5970
SCIP_RETCODE SCIPsetConsRemovable(SCIP *scip, SCIP_CONS *cons, SCIP_Bool removable)
Definition: scip_cons.c:1420
void SCIPbenderscutSetEnabled(SCIP_BENDERSCUT *benderscut, SCIP_Bool enabled)
Definition: benderscut.c:593
public methods for Benders decomposition
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2778
#define SCIP_DEFAULT_ADDCUTS
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:483
SCIP_RETCODE SCIPsetConsDynamic(SCIP *scip, SCIP_CONS *cons, SCIP_Bool dynamic)
Definition: scip_cons.c:1395
#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:164
#define SCIP_CALL(x)
Definition: def.h:393
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:250
public methods for constraint handler plugins and constraints
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:93
static const char * paramname[]
Definition: lpi_msk.c:5040
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:361
public methods for LP management
SCIP_RETCODE SCIPchgRowLhs(SCIP *scip, SCIP_ROW *row, SCIP_Real lhs)
Definition: scip_lp.c:1583
public methods for cuts and aggregation rows
SCIP * SCIPbendersSubproblem(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:5958
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:2138
int SCIPbendersGetNSubproblems(SCIP_BENDERS *benders)
Definition: benders.c:5948
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2045
public methods for the LP relaxation, rows and columns
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:2000
public methods for Benders&#39; decomposition cuts
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1562
general public methods
public methods for solutions
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1119
public methods for message output
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1955
#define SCIP_Real
Definition: def.h:186
public methods for message handling
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2206
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)
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
public methods for global and local (sub)problems
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1361
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:57