Scippy

SCIP

Solving Constraint Integer Programs

benderscut_opt.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-2018 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_opt.c
17  * @brief Generates a standard Benders' decomposition optimality cut
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_opt.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_misc_linear.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_probing.h"
43 #include "scip/scip_var.h"
44 #include <string.h>
45 
46 #define BENDERSCUT_NAME "optimality"
47 #define BENDERSCUT_DESC "Standard Benders' decomposition optimality cut"
48 #define BENDERSCUT_PRIORITY 5000
49 #define BENDERSCUT_LPCUT TRUE
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_Bool addcuts; /**< should cuts be generated instead of constraints */
61 };
62 
63 
64 /*
65  * Local methods
66  */
67 
68 /** in the case of numerical troubles, the LP is resolved with solution polishing activated */
69 static
71  SCIP* subproblem, /**< the SCIP data structure */
72  SCIP_Bool* success /**< TRUE is the resolving of the LP was successful */
73  )
74 {
75  int oldpolishing;
76  SCIP_Bool lperror;
77  SCIP_Bool cutoff;
78 
79  assert(subproblem != NULL);
80  assert(SCIPinProbing(subproblem));
81 
82  (*success) = FALSE;
83 
84  /* setting the solution polishing parameter */
85  SCIP_CALL( SCIPgetIntParam(subproblem, "lp/solutionpolishing", &oldpolishing) );
86  SCIP_CALL( SCIPsetIntParam(subproblem, "lp/solutionpolishing", 2) );
87 
88  /* resolving the probing LP */
89  SCIP_CALL( SCIPsolveProbingLP(subproblem, -1, &lperror, &cutoff) );
90 
91  if( SCIPgetLPSolstat(subproblem) == SCIP_LPSOLSTAT_OPTIMAL )
92  (*success) = TRUE;
93 
94  /* resetting the solution polishing parameter */
95  SCIP_CALL( SCIPsetIntParam(subproblem, "lp/solutionpolishing", oldpolishing) );
96 
97  return SCIP_OKAY;
98 }
99 
100 /** computes a standard Benders' optimality cut from the dual solutions of the LP */
101 static
103  SCIP* masterprob, /**< the SCIP instance of the master problem */
104  SCIP* subproblem, /**< the SCIP instance of the subproblem */
105  SCIP_BENDERS* benders, /**< the benders' decomposition structure */
106  SCIP_SOL* sol, /**< primal CIP solution */
107  SCIP_CONS* cons, /**< the constraint for the generated cut, can be NULL */
108  SCIP_ROW* row, /**< the row for the generated cut, can be NULL */
109  SCIP_Bool addcut, /**< indicates whether a cut is created instead of a constraint */
110  SCIP_Bool* success /**< was the cut generation successful? */
111  )
112 {
113  SCIP_VAR** vars;
114  SCIP_VAR** fixedvars;
115  SCIP_CONS** conss;
116  int nvars;
117  int nfixedvars;
118  int nconss;
119  SCIP_Real dualsol;
120  SCIP_Real addval;
121  SCIP_Real lhs;
122  SCIP_Real rhs;
123  int i;
124 
125  SCIP_Real verifyobj = 0;
126  SCIP_Real checkobj = 0;
127 
128  assert(masterprob != NULL);
129  assert(subproblem != NULL);
130  assert(benders != NULL);
131  assert(cons != NULL || addcut);
132  assert(row != NULL || !addcut);
133 
134  (*success) = FALSE;
135 
136  nvars = SCIPgetNVars(subproblem);
137  vars = SCIPgetVars(subproblem);
138  nfixedvars = SCIPgetNFixedVars(subproblem);
139  fixedvars = SCIPgetFixedVars(subproblem);
140 
141  nconss = SCIPgetNConss(subproblem);
142  conss = SCIPgetConss(subproblem);
143 
144  /* looping over all constraints and setting the coefficients of the cut */
145  for( i = 0; i < nconss; i++ )
146  {
147  SCIP_Bool conssuccess;
148  addval = 0;
149 
150  SCIPconsGetDualsol(subproblem, conss[i], &dualsol, &conssuccess);
151  if( !conssuccess )
152  {
153  (*success) = FALSE;
154  SCIPdebugMsg(masterprob, "Error when generating optimality cut.\n");
155  return SCIP_OKAY;
156  }
157 
158  assert( !SCIPisInfinity(subproblem, dualsol) && !SCIPisInfinity(subproblem, -dualsol) );
159 
160  if( SCIPisZero(subproblem, dualsol) )
161  continue;
162 
163  if( addcut )
164  lhs = SCIProwGetLhs(row);
165  else
166  lhs = SCIPgetLhsLinear(masterprob, cons);
167 
168  if( SCIPisPositive(subproblem, dualsol) )
169  addval = dualsol*SCIPconsGetLhs(subproblem, conss[i], &conssuccess);
170  else if( SCIPisNegative(subproblem, dualsol) )
171  addval = dualsol*SCIPconsGetRhs(subproblem, conss[i], &conssuccess);
172 
173  if( !conssuccess )
174  {
175  (*success) = FALSE;
176  SCIPdebugMsg(masterprob, "Error when generating optimality cut.\n");
177  return SCIP_OKAY;
178  }
179 
180  lhs += addval;
181 
182  /* if the bound becomes infinite, then the cut generation terminates. */
183  if( SCIPisInfinity(masterprob, lhs) || SCIPisInfinity(masterprob, -lhs)
184  || SCIPisInfinity(masterprob, addval) || SCIPisInfinity(masterprob, -addval))
185  {
186  (*success) = FALSE;
187  SCIPdebugMsg(masterprob, "Infinite bound when generating optimality cut. lhs = %g addval = %g.\n", lhs, addval);
188  return SCIP_OKAY;
189  }
190 
191  /* Update the lhs of the cut */
192  if( addcut )
193  {
194  SCIP_CALL( SCIPchgRowLhs(masterprob, row, lhs) );
195  }
196  else
197  {
198  SCIP_CALL( SCIPchgLhsLinear(masterprob, cons, lhs) );
199  }
200  }
201 
202  /* looping over all variables to update the coefficients in the computed cut. */
203  for( i = 0; i < nvars + nfixedvars; i++ )
204  {
205  SCIP_VAR* var;
206  SCIP_VAR* mastervar;
207  SCIP_Real redcost;
208 
209  if( i < nvars )
210  var = vars[i];
211  else
212  var = fixedvars[i - nvars];
213 
214  /* retrieving the master problem variable for the given subproblem variable. */
215  SCIP_CALL( SCIPgetBendersMasterVar(masterprob, benders, var, &mastervar) );
216 
217  redcost = SCIPgetVarRedcost(subproblem, var);
218 
219  checkobj += SCIPvarGetUnchangedObj(var)*SCIPvarGetSol(var, TRUE);
220 
221  /* checking whether the subproblem variable has a corresponding master variable. */
222  if( mastervar != NULL )
223  {
224  SCIP_Real coef;
225 
226  coef = -1.0*(SCIPvarGetObj(var) + redcost);
227 
228  if( addcut )
229  {
230  SCIP_CALL( SCIPaddVarToRow(masterprob, row, mastervar, coef) );
231  }
232  else
233  {
234  SCIP_CALL( SCIPaddCoefLinear(masterprob, cons, mastervar, coef) );
235  }
236  }
237  else
238  {
239  if( !SCIPisZero(subproblem, redcost) )
240  {
241  addval = 0;
242 
243  /* get current lhs of the subproblem cut */
244  if( addcut )
245  lhs = SCIProwGetLhs(row);
246  else
247  lhs = SCIPgetLhsLinear(masterprob, cons);
248 
249  if( SCIPisPositive(subproblem, redcost) )
250  addval = redcost*SCIPvarGetLbLocal(var);
251  else if( SCIPisNegative(subproblem, redcost) )
252  addval = redcost*SCIPvarGetUbLocal(var);
253 
254  lhs += addval;
255 
256  /* if the bound becomes infinite, then the cut generation terminates. */
257  if( SCIPisInfinity(masterprob, lhs) || SCIPisInfinity(masterprob, -lhs)
258  || SCIPisInfinity(masterprob, addval) || SCIPisInfinity(masterprob, -addval))
259  {
260  (*success) = FALSE;
261  SCIPdebugMsg(masterprob, "Infinite bound when generating optimality cut.\n");
262  return SCIP_OKAY;
263  }
264 
265  /* Update lhs */
266  if( addcut )
267  {
268  SCIP_CALL( SCIPchgRowLhs(masterprob, row, lhs) );
269  }
270  else
271  {
272  SCIP_CALL( SCIPchgLhsLinear(masterprob, cons, lhs) );
273  }
274  }
275  }
276  }
277 
278  /* checking whether the RHS is infinity */
279  if( addcut )
280  rhs = SCIProwGetRhs(row);
281  else
282  rhs = SCIPgetRhsLinear(masterprob, cons);
283 
284  assert(SCIPisInfinity(masterprob, rhs));
285  /* the rhs should be infinite. If it changes, then there is an error */
286  if( !SCIPisInfinity(masterprob, rhs) )
287  {
288  (*success) = FALSE;
289  SCIPdebugMsg(masterprob, "RHS is not infinite. rhs = %g.\n", rhs);
290  return SCIP_OKAY;
291  }
292 
293  if( addcut )
294  lhs = SCIProwGetLhs(row);
295  else
296  lhs = SCIPgetLhsLinear(masterprob, cons);
297  verifyobj += lhs;
298 
299  if( addcut )
300  verifyobj -= SCIPgetRowSolActivity(masterprob, row, sol);
301  else
302  verifyobj -= SCIPgetActivityLinear(masterprob, cons, sol);
303 
304  /* it is possible that numerics will cause the generated cut to be invalid. This cut should not be added to the
305  * master problem, since its addition could cut off feasible solutions. The success flag is set of false, indicating
306  * that the Benders' cut could not find a valid cut.
307  */
308  if( !SCIPisFeasEQ(masterprob, checkobj, verifyobj) )
309  {
310  (*success) = FALSE;
311  SCIPdebugMsg(masterprob, "The objective function and cut activity are not equal (%g != %g).\n", checkobj,
312  verifyobj);
313 #ifdef SCIP_DEBUG
314  SCIPABORT();
315 #endif
316  return SCIP_OKAY;
317  }
318 
319  (*success) = TRUE;
320 
321  return SCIP_OKAY;
322 }
323 
324 
325 /** Adds the auxiliary variable to the generated cut. If this is the first optimality cut for the subproblem, then the
326  * auxiliary variable is first created and added to the master problem.
327  */
328 static
330  SCIP* masterprob, /**< the SCIP instance of the master problem */
331  SCIP_BENDERS* benders, /**< the benders' decomposition structure */
332  SCIP_CONS* cons, /**< the constraint for the generated cut, can be NULL */
333  SCIP_ROW* row, /**< the row for the generated cut, can be NULL */
334  int probnumber, /**< the number of the pricing problem */
335  SCIP_Bool addcut /**< indicates whether a cut is created instead of a constraint */
336  )
337 {
338  SCIP_VAR* auxiliaryvar;
339 
340  assert(masterprob != NULL);
341  assert(benders != NULL);
342  assert(cons != NULL || addcut);
343  assert(row != NULL || !addcut);
344 
345  auxiliaryvar = SCIPbendersGetAuxiliaryVar(benders, probnumber);
346 
347  /* adding the auxiliary variable to the generated cut */
348  if( addcut )
349  {
350  SCIP_CALL( SCIPaddVarToRow(masterprob, row, auxiliaryvar, 1.0) );
351  }
352  else
353  {
354  SCIP_CALL( SCIPaddCoefLinear(masterprob, cons, auxiliaryvar, 1.0) );
355  }
356 
357  return SCIP_OKAY;
358 }
359 
360 
361 /** generates and applies Benders' cuts */
362 static
364  SCIP* masterprob, /**< the SCIP instance of the master problem */
365  SCIP* subproblem, /**< the SCIP instance of the pricing problem */
366  SCIP_BENDERS* benders, /**< the benders' decomposition */
367  SCIP_BENDERSCUT* benderscut, /**< the benders' decomposition cut method */
368  SCIP_SOL* sol, /**< primal CIP solution */
369  int probnumber, /**< the number of the pricing problem */
370  SCIP_BENDERSENFOTYPE type, /**< the enforcement type calling this function */
371  SCIP_RESULT* result /**< the result from solving the subproblems */
372  )
373 {
374  SCIP_BENDERSCUTDATA* benderscutdata;
375  SCIP_CONSHDLR* consbenders;
376  SCIP_CONS* cons;
377  SCIP_ROW* row;
378  char cutname[SCIP_MAXSTRLEN];
379  SCIP_Bool optimal;
380  SCIP_Bool addcut;
381  SCIP_Bool success;
382 
383  assert(masterprob != NULL);
384  assert(subproblem != NULL);
385  assert(benders != NULL);
386  assert(benderscut != NULL);
387  assert(result != NULL);
388  assert(SCIPgetStatus(subproblem) == SCIP_STATUS_OPTIMAL || SCIPgetLPSolstat(subproblem) == SCIP_LPSOLSTAT_OPTIMAL);
389 
390  row = NULL;
391  cons = NULL;
392 
393  /* retrieving the Benders' cut data */
394  benderscutdata = SCIPbenderscutGetData(benderscut);
395 
396  /* if the cuts are generated prior to the solving stage, then rows can not be generated. So constraints must be
397  * added to the master problem.
398  */
399  if( SCIPgetStage(masterprob) < SCIP_STAGE_INITSOLVE )
400  addcut = FALSE;
401  else
402  addcut = benderscutdata->addcuts;
403 
404  /* retrieving the Benders' decomposition constraint handler */
405  consbenders = SCIPfindConshdlr(masterprob, "benders");
406 
407  /* checking the optimality of the original problem with a comparison between the auxiliary variable and the
408  * objective value of the subproblem */
409  SCIP_CALL( SCIPcheckBendersSubproblemOptimality(masterprob, benders, sol, probnumber, &optimal) );
410 
411  if( optimal )
412  {
413  (*result) = SCIP_FEASIBLE;
414  SCIPdebugMsg(masterprob, "No cut added for subproblem %d\n", probnumber);
415  return SCIP_OKAY;
416  }
417 
418  /* setting the name of the generated cut */
419  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "optimalitycut_%d_%d", probnumber,
420  SCIPbenderscutGetNFound(benderscut) );
421 
422  /* creating an empty row or constraint for the Benders' cut */
423  if( addcut )
424  {
425  SCIP_CALL( SCIPcreateEmptyRowCons(masterprob, &row, consbenders, cutname, 0.0, SCIPinfinity(masterprob), FALSE,
426  FALSE, TRUE) );
427  }
428  else
429  {
430  SCIP_CALL( SCIPcreateConsBasicLinear(masterprob, &cons, cutname, 0, NULL, NULL, 0.0, SCIPinfinity(masterprob)) );
431  SCIP_CALL( SCIPsetConsDynamic(masterprob, cons, TRUE) );
432  SCIP_CALL( SCIPsetConsRemovable(masterprob, cons, TRUE) );
433  }
434 
435  /* computing the coefficients of the optimality cut */
436  SCIP_CALL( computeStandardOptimalityCut(masterprob, subproblem, benders, sol, cons, row, addcut, &success) );
437 
438  /* if success is FALSE, then there was an error in generating the optimality cut. No cut will be added to the master
439  * problem. Otherwise, the constraint is added to the master problem.
440  */
441  if( !success )
442  {
443  (*result) = SCIP_DIDNOTFIND;
444  SCIPdebugMsg(masterprob, "Error in generating Benders' optimality cut for problem %d.\n", probnumber);
445  }
446  else
447  {
448  /* adding the auxiliary variable to the optimality cut */
449  SCIP_CALL( addAuxiliaryVariableToCut(masterprob, benders, cons, row, probnumber, addcut) );
450 
451  /* adding the constraint to the master problem */
452  if( addcut )
453  {
454  SCIP_Bool infeasible;
455 
456  if( type == SCIP_BENDERSENFOTYPE_LP || type == SCIP_BENDERSENFOTYPE_RELAX )
457  {
458  SCIP_CALL( SCIPaddRow(masterprob, row, FALSE, &infeasible) );
459  assert(!infeasible);
460  }
461  else
462  {
463  assert(type == SCIP_BENDERSENFOTYPE_CHECK || type == SCIP_BENDERSENFOTYPE_PSEUDO);
464  SCIP_CALL( SCIPaddPoolCut(masterprob, row) );
465  }
466 
467  /* storing the generated cut */
468  SCIP_CALL( SCIPstoreBenderscutCut(masterprob, benderscut, row) );
469 
470  (*result) = SCIP_SEPARATED;
471  }
472  else
473  {
474  SCIP_CALL( SCIPaddCons(masterprob, cons) );
475 
476  SCIPdebugPrintCons(masterprob, cons, NULL);
477 
478  /* storing the generated cut */
479  SCIP_CALL( SCIPstoreBenderscutCons(masterprob, benderscut, cons) );
480 
481  (*result) = SCIP_CONSADDED;
482  }
483  }
484 
485  if( addcut )
486  {
487  /* release the row */
488  SCIP_CALL( SCIPreleaseRow(masterprob, &row) );
489  }
490  else
491  {
492  /* release the constraint */
493  SCIP_CALL( SCIPreleaseCons(masterprob, &cons) );
494  }
495 
496  return SCIP_OKAY;
497 }
498 
499 /*
500  * Callback methods of Benders' decomposition cuts
501  */
502 
503 /** destructor of Benders' decomposition cuts to free user data (called when SCIP is exiting) */
504 static
505 SCIP_DECL_BENDERSCUTFREE(benderscutFreeOpt)
506 { /*lint --e{715}*/
507  SCIP_BENDERSCUTDATA* benderscutdata;
508 
509  assert( benderscut != NULL );
510  assert( strcmp(SCIPbenderscutGetName(benderscut), BENDERSCUT_NAME) == 0 );
511 
512  /* free Benders' cut data */
513  benderscutdata = SCIPbenderscutGetData(benderscut);
514  assert( benderscutdata != NULL );
515 
516  SCIPfreeBlockMemory(scip, &benderscutdata);
517 
518  SCIPbenderscutSetData(benderscut, NULL);
519 
520  return SCIP_OKAY;
521 }
522 
523 
524 /** execution method of Benders' decomposition cuts */
525 static
526 SCIP_DECL_BENDERSCUTEXEC(benderscutExecOpt)
527 { /*lint --e{715}*/
528  SCIP* subproblem;
529 
530  assert(scip != NULL);
531  assert(benders != NULL);
532  assert(benderscut != NULL);
533  assert(result != NULL);
534  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
535 
536  subproblem = SCIPbendersSubproblem(benders, probnumber);
537 
538  /* only generate optimality cuts if the subproblem is optimal */
539  if( SCIPgetStatus(subproblem) == SCIP_STATUS_OPTIMAL ||
540  (SCIPgetStage(subproblem) == SCIP_STAGE_SOLVING && SCIPgetLPSolstat(subproblem) == SCIP_LPSOLSTAT_OPTIMAL) )
541  {
542  /* generating a cut for a given subproblem */
543  SCIP_CALL( generateAndApplyBendersCuts(scip, subproblem, benders, benderscut,
544  sol, probnumber, type, result) );
545 
546  /* if it was not possible to generate a cut, this could be due to numerical issues. So the solution to the LP is
547  * resolved and the generation of the cut is reattempted
548  */
549  if( (*result) == SCIP_DIDNOTFIND )
550  {
551  SCIP_Bool success;
552 
553  SCIPinfoMessage(scip, NULL, "Numerical trouble generating optimality cut for subproblem %d. Attempting to "
554  "polish the LP solution to find an alternative dual extreme point.\n", probnumber);
555 
556  SCIP_CALL( polishSolution(subproblem, &success) );
557 
558  /* only attempt to generate a cut if the solution polishing was successful */
559  if( success )
560  {
561  SCIP_CALL( generateAndApplyBendersCuts(scip, subproblem, benders, benderscut,
562  sol, probnumber, type, result) );
563  }
564  }
565  }
566 
567  return SCIP_OKAY;
568 }
569 
570 
571 /*
572  * Benders' decomposition cuts specific interface methods
573  */
574 
575 /** creates the opt Benders' decomposition cuts and includes it in SCIP */
577  SCIP* scip, /**< SCIP data structure */
578  SCIP_BENDERS* benders /**< Benders' decomposition */
579  )
580 {
581  SCIP_BENDERSCUTDATA* benderscutdata;
582  SCIP_BENDERSCUT* benderscut;
583  char paramname[SCIP_MAXSTRLEN];
584 
585  assert(benders != NULL);
586 
587  /* create opt Benders' decomposition cuts data */
588  SCIP_CALL( SCIPallocBlockMemory(scip, &benderscutdata) );
589 
590  benderscut = NULL;
591 
592  /* include Benders' decomposition cuts */
594  BENDERSCUT_PRIORITY, BENDERSCUT_LPCUT, benderscutExecOpt, benderscutdata) );
595 
596  assert(benderscut != NULL);
597 
598  /* setting the non fundamental callbacks via setter functions */
599  SCIP_CALL( SCIPsetBenderscutFree(scip, benderscut, benderscutFreeOpt) );
600 
601  /* add opt Benders' decomposition cuts parameters */
602  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/benderscut/%s/addcuts",
604  SCIP_CALL( SCIPaddBoolParam(scip, paramname,
605  "should cuts be generated and added to the cutpool instead of global constraints directly added to the problem.",
606  &benderscutdata->addcuts, FALSE, SCIP_DEFAULT_ADDCUTS, NULL, NULL) );
607 
608  return SCIP_OKAY;
609 }
SCIP_RETCODE SCIPstoreBenderscutCut(SCIP *scip, SCIP_BENDERSCUT *benderscut, SCIP_ROW *cut)
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:489
SCIP_Real SCIPconsGetLhs(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: misc_linear.c:102
#define NULL
Definition: def.h:239
static SCIP_RETCODE addAuxiliaryVariableToCut(SCIP *masterprob, SCIP_BENDERS *benders, SCIP_CONS *cons, SCIP_ROW *row, int probnumber, SCIP_Bool addcut)
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)
internal miscellaneous methods for linear constraints
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:412
#define BENDERSCUT_LPCUT
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:954
SCIP_BENDERSCUTDATA * SCIPbenderscutGetData(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:400
SCIP_RETCODE SCIPgetBendersMasterVar(SCIP *scip, SCIP_BENDERS *benders, SCIP_VAR *var, SCIP_VAR **mappedvar)
Definition: scip_benders.c:703
#define SCIP_MAXSTRLEN
Definition: def.h:260
const char * SCIPbendersGetName(SCIP_BENDERS *benders)
Definition: benders.c:4194
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1602
SCIP_Real SCIPgetVarRedcost(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1866
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPconsGetRhs(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: misc_linear.c:38
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17399
void SCIPbenderscutSetData(SCIP_BENDERSCUT *benderscut, SCIP_BENDERSCUTDATA *benderscutdata)
Definition: benderscut.c:410
SCIP_Real SCIPvarGetSol(SCIP_VAR *var, SCIP_Bool getlpval)
Definition: var.c:12734
static SCIP_RETCODE computeStandardOptimalityCut(SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_SOL *sol, SCIP_CONS *cons, SCIP_ROW *row, SCIP_Bool addcut, SCIP_Bool *success)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:16869
#define FALSE
Definition: def.h:65
public methods for Benders&#39; decomposition
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10017
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:64
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE
Definition: type_benders.h:42
Generates a standard Benders&#39; decomposition optimality cut.
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
SCIP_CONS ** SCIPgetConss(SCIP *scip)
Definition: scip_prob.c:3140
#define BENDERSCUT_PRIORITY
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:83
public methods for SCIP variables
#define SCIPdebugMsg
Definition: scip_message.h:88
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_Longint SCIPbenderscutGetNFound(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:540
#define BENDERSCUT_NAME
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:279
public methods for numerical tolerances
int SCIPgetNFixedVars(SCIP *scip)
Definition: scip_prob.c:2361
SCIP_VAR ** SCIPgetFixedVars(SCIP *scip)
Definition: scip_prob.c:2318
#define BENDERSCUT_DESC
SCIP_RETCODE SCIPsetConsRemovable(SCIP *scip, SCIP_CONS *cons, SCIP_Bool removable)
Definition: scip_cons.c:1488
public methods for Benders decomposition
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2822
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:519
SCIP_RETCODE SCIPsetConsDynamic(SCIP *scip, SCIP_CONS *cons, SCIP_Bool dynamic)
Definition: scip_cons.c:1463
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:341
#define SCIP_CALL(x)
Definition: def.h:351
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:866
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:16879
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:294
public methods for constraint handler plugins and constraints
static SCIP_RETCODE polishSolution(SCIP *subproblem, SCIP_Bool *success)
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:62
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:226
void SCIPconsGetDualsol(SCIP *scip, SCIP_CONS *cons, SCIP_Real *dualsol, SCIP_Bool *success)
Definition: misc_linear.c:347
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:1336
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:405
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:578
SCIP_Real SCIPvarGetUnchangedObj(SCIP_VAR *var)
Definition: var.c:17201
public methods for LP management
SCIP_RETCODE SCIPchgRowLhs(SCIP *scip, SCIP_ROW *row, SCIP_Real lhs)
Definition: scip_lp.c:1495
public methods for cuts and aggregation rows
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17191
SCIP_RETCODE SCIPstoreBenderscutCons(SCIP *scip, SCIP_BENDERSCUT *benderscut, SCIP_CONS *cons)
SCIP * SCIPbendersSubproblem(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:4248
Constraint handler for linear constraints in their most general form, .
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition: scip_lp.c:2045
SCIP_RETCODE SCIPcheckBendersSubproblemOptimality(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol, int probnumber, SCIP_Bool *optimal)
Definition: scip_benders.c:934
int SCIPbendersGetNSubproblems(SCIP_BENDERS *benders)
Definition: benders.c:4238
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:152
public methods for the LP relaxation, rows and columns
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:2044
public methods for Benders&#39; decomposition cuts
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1474
#define SCIP_DEFAULT_ADDCUTS
general public methods
static SCIP_DECL_BENDERSCUTFREE(benderscutFreeOpt)
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3094
public methods for the probing mode
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1187
public methods for message output
SCIP_RETCODE SCIPincludeBenderscutOpt(SCIP *scip, SCIP_BENDERS *benders)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1999
#define SCIP_Real
Definition: def.h:150
public methods for message handling
static SCIP_RETCODE generateAndApplyBendersCuts(SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_BENDERSCUT *benderscut, SCIP_SOL *sol, int probnumber, SCIP_BENDERSENFOTYPE type, SCIP_RESULT *result)
static SCIP_DECL_BENDERSCUTEXEC(benderscutExecOpt)
SCIP_RETCODE SCIPsetBenderscutFree(SCIP *scip, SCIP_BENDERSCUT *benderscut, SCIP_DECL_BENDERSCUTFREE((*benderscutfree)))
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17409
SCIP_VAR * SCIPbendersGetAuxiliaryVar(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:4392
#define SCIPABORT()
Definition: def.h:323
public methods for global and local (sub)problems
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:129