Scippy

SCIP

Solving Constraint Integer Programs

benderscut_int.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_int.c
17  * @brief Generates a Laporte and Louveaux Benders' decomposition integer 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_int.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_paramset.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 "integer"
45 #define BENDERSCUT_DESC "Laporte and Louveaux Benders' decomposition integer cut"
46 #define BENDERSCUT_PRIORITY 0
47 #define BENDERSCUT_LPCUT FALSE
48 
49 #define SCIP_DEFAULT_ADDCUTS FALSE /** Should cuts be generated, instead of constraints */
50 #define SCIP_DEFAULT_CUTCONSTANT -10000.0
51 
52 /*
53  * Data structures
54  */
55 
56 /** Benders' decomposition cuts data */
57 struct SCIP_BenderscutData
58 {
59  SCIP_BENDERS* benders; /**< the Benders' decomposition data structure */
60  SCIP_Real cutconstant; /**< the constant for computing the integer cuts */
61  SCIP_Real* subprobconstant; /**< the constant for each subproblem used for computing the integer cuts */
62  SCIP_Bool addcuts; /**< should cuts be generated instead of constraints */
63  SCIP_Bool* firstcut; /**< flag to indicate that the first cut needs to be generated. */
64  int nsubproblems; /**< the number of subproblems for the Benders' decomposition */
65 };
66 
67 /** method to call, when the priority of a Benders' decomposition was changed */
68 static
69 SCIP_DECL_PARAMCHGD(paramChgdBenderscutintConstant)
70 { /*lint --e{715}*/
71  SCIP_BENDERSCUTDATA* benderscutdata;
72  int i;
73 
74  benderscutdata = (SCIP_BENDERSCUTDATA*)SCIPparamGetData(param);
75  assert(benderscutdata != NULL);
76 
77  for( i = 0; i < benderscutdata->nsubproblems; i++ )
78  benderscutdata->subprobconstant[i] = benderscutdata->cutconstant;
79 
80  return SCIP_OKAY;
81 }
82 
83 
84 /** creates the Benders' decomposition cut data */
85 static
87  SCIP* scip, /**< the SCIP data structure */
88  SCIP_BENDERSCUTDATA* benderscutdata /**< the Benders' cut data */
89  )
90 {
91  int i;
92 
93  assert(scip != NULL);
94  assert(benderscutdata != NULL);
95 
96  /* allocating the memory for the subproblem constants */
97  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &benderscutdata->subprobconstant, benderscutdata->nsubproblems) );
98  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &benderscutdata->firstcut, benderscutdata->nsubproblems) );
99 
100  for( i = 0; i < benderscutdata->nsubproblems; i++ )
101  {
102  benderscutdata->subprobconstant[i] = benderscutdata->cutconstant;
103  benderscutdata->firstcut[i] = TRUE;
104  }
105 
106  return SCIP_OKAY;
107 }
108 
109 /*
110  * Local methods
111  */
112 
113 /** computes a standard Benders' optimality cut from the dual solutions of the LP */
114 static
116  SCIP* masterprob, /**< the SCIP instance of the master problem */
117  SCIP_BENDERS* benders, /**< the benders' decomposition structure */
118  SCIP_SOL* sol, /**< primal CIP solution */
119  SCIP_CONS* cons, /**< the constraint for the generated cut, can be NULL */
120  SCIP_ROW* row, /**< the row for the generated cut, can be NULL */
121  SCIP_Real cutconstant, /**< the constant value in the integer optimality cut */
122  int probnumber, /**< the number of the pricing problem */
123  SCIP_Bool addcut, /**< indicates whether a cut is created instead of a constraint */
124  SCIP_Bool* success /**< was the cut generation successful? */
125  )
126 {
127  SCIP_VAR** vars;
128  int nvars;
129  SCIP_Real subprobobj; /* the objective function value of the subproblem */
130  SCIP_Real lhs; /* the left hand side of the cut */
131  int i;
132  SCIP* subproblem;
133  SCIP_SOL* subprobsol;
134 
135 #ifndef NDEBUG
136  SCIP_Real verifyobj = 0;
137 #endif
138 
139  assert(masterprob != NULL);
140  assert(benders != NULL);
141  assert(cons != NULL || addcut);
142  assert(row != NULL || !addcut);
143 
144  (*success) = FALSE;
145 
146  /* getting the best solution from the subproblem */
147 
148 #ifdef SCIP_DEBUG
149  subproblem = SCIPbendersSubproblem(benders, probnumber);
150  subprobsol = SCIPgetBestSol(subproblem);
151 #endif
152 
153  subprobobj = SCIPbendersGetSubproblemObjval(benders, probnumber);
154 
155  SCIPdebugMsg(masterprob, "Subproblem %d - Objective Value: Stored - %g Orig Obj - %g\n", probnumber,
156  SCIPbendersGetSubproblemObjval(benders, probnumber),
157  SCIPgetSolOrigObj(subproblem, subprobsol)*(int)SCIPgetObjsense(subproblem));
158 
159  nvars = SCIPgetNVars(masterprob);
160  vars = SCIPgetVars(masterprob);
161 
162  /* adding the subproblem objective function value to the lhs */
163  if( addcut )
164  lhs = SCIProwGetLhs(row);
165  else
166  lhs = SCIPgetLhsLinear(masterprob, cons);
167 
168  /* looping over all master problem variables to update the coefficients in the computed cut. */
169  for( i = 0; i < nvars; i++ )
170  {
171  SCIP_VAR* subprobvar;
172  SCIP_Real coef;
173 
174  SCIP_CALL( SCIPgetBendersSubproblemVar(masterprob, benders, vars[i], &subprobvar, probnumber) );
175 
176  /* if there is a corresponding subproblem variable, then the variable will not be NULL. */
177  if( subprobvar != NULL )
178  {
179  /* if the variable is on its upper bound, then the subproblem objective value is added to the cut */
180  if( SCIPisFeasEQ(masterprob, SCIPgetSolVal(masterprob, sol, vars[i]), 1.0) )
181  {
182  coef = -(subprobobj - cutconstant);
183  lhs -= (subprobobj - cutconstant);
184  }
185  else
186  coef = (subprobobj - cutconstant);
187 
188  /* adding the variable to the cut. The coefficient is the subproblem objective value */
189  if( addcut )
190  {
191  SCIP_CALL( SCIPaddVarToRow(masterprob, row, vars[i], coef) );
192  }
193  else
194  {
195  SCIP_CALL( SCIPaddCoefLinear(masterprob, cons, vars[i], coef) );
196  }
197  }
198  }
199 
200  lhs += subprobobj;
201 
202  /* if the bound becomes infinite, then the cut generation terminates. */
203  if( SCIPisInfinity(masterprob, lhs) || SCIPisInfinity(masterprob, -lhs) )
204  {
205  (*success) = FALSE;
206  SCIPdebugMsg(masterprob, "Infinite bound when generating integer optimality cut.\n");
207  return SCIP_OKAY;
208  }
209 
210  /* Update the lhs of the cut */
211  if( addcut )
212  {
213  SCIP_CALL( SCIPchgRowLhs(masterprob, row, lhs) );
214  }
215  else
216  {
217  SCIP_CALL( SCIPchgLhsLinear(masterprob, cons, lhs) );
218  }
219 
220 #ifndef NDEBUG
221  if( addcut )
222  lhs = SCIProwGetLhs(row);
223  else
224  lhs = SCIPgetLhsLinear(masterprob, cons);
225  verifyobj += lhs;
226 
227  if( addcut )
228  verifyobj -= SCIPgetRowSolActivity(masterprob, row, sol);
229  else
230  verifyobj -= SCIPgetActivityLinear(masterprob, cons, sol);
231 #endif
232 
233  assert(SCIPisFeasEQ(masterprob, verifyobj, subprobobj));
234 
235  (*success) = TRUE;
236 
237  return SCIP_OKAY;
238 }
239 
240 
241 /** adds the auxiliary variable to the generated cut. If this is the first optimality cut for the subproblem, then the
242  * auxiliary variable is first created and added to the master problem.
243  */
244 static
246  SCIP* masterprob, /**< the SCIP instance of the master problem */
247  SCIP_BENDERS* benders, /**< the benders' decomposition structure */
248  SCIP_CONS* cons, /**< the constraint for the generated cut, can be NULL */
249  SCIP_ROW* row, /**< the row for the generated cut, can be NULL */
250  int probnumber, /**< the number of the pricing problem */
251  SCIP_Bool addcut /**< indicates whether a cut is created instead of a constraint */
252  )
253 {
254  SCIP_VAR* auxiliaryvar;
255 
256  assert(masterprob != NULL);
257  assert(benders != NULL);
258  assert(cons != NULL || addcut);
259  assert(row != NULL || !addcut);
260 
261  auxiliaryvar = SCIPbendersGetAuxiliaryVar(benders, probnumber);
262 
263  /* adding the auxiliary variable to the generated cut */
264  if( addcut )
265  {
266  SCIP_CALL( SCIPaddVarToRow(masterprob, row, auxiliaryvar, 1.0) );
267  }
268  else
269  {
270  SCIP_CALL( SCIPaddCoefLinear(masterprob, cons, auxiliaryvar, 1.0) );
271  }
272 
273  return SCIP_OKAY;
274 }
275 
276 
277 /** generates and applies Benders' cuts */
278 static
280  SCIP* masterprob, /**< the SCIP instance of the master problem */
281  SCIP_BENDERS* benders, /**< the benders' decomposition */
282  SCIP_BENDERSCUT* benderscut, /**< the benders' decomposition cut method */
283  SCIP_SOL* sol, /**< primal CIP solution */
284  int probnumber, /**< the number of the pricing problem */
285  SCIP_BENDERSENFOTYPE type, /**< the enforcement type calling this function */
286  SCIP_RESULT* result, /**< the result from solving the subproblems */
287  SCIP_Bool initcons /**< is this function called to generate the initial constraint */
288  )
289 {
290  SCIP_BENDERSCUTDATA* benderscutdata;
291  SCIP_CONSHDLR* consbenders;
292  SCIP_CONS* cons;
293  SCIP_ROW* row;
294  char cutname[SCIP_MAXSTRLEN];
295  SCIP_Bool optimal;
296  SCIP_Bool addcut;
297  SCIP_Bool success;
298 
299  assert(masterprob != NULL);
300  assert(benders != NULL);
301  assert(benderscut != NULL);
302  assert(result != NULL);
303 
304  row = NULL;
305  cons = NULL;
306 
307  success = FALSE;
308 
309  /* retrieving the Benders' cut data */
310  benderscutdata = SCIPbenderscutGetData(benderscut);
311 
312  /* if the cuts are generated prior to the solving stage, then rows can not be generated. So constraints must be added
313  * to the master problem.
314  */
315  if( SCIPgetStage(masterprob) < SCIP_STAGE_INITSOLVE )
316  addcut = FALSE;
317  else
318  addcut = benderscutdata->addcuts;
319 
320  /* retrieving the Benders' decomposition constraint handler */
321  consbenders = SCIPfindConshdlr(masterprob, "benders");
322 
323  /* checking the optimality of the original problem with a comparison between the auxiliary variable and the
324  * objective value of the subproblem
325  */
326  optimal = FALSE;
327  SCIP_CALL( SCIPcheckBendersSubproblemOptimality(masterprob, benders, sol, probnumber, &optimal) );
328 
329  if( optimal )
330  {
331  (*result) = SCIP_FEASIBLE;
332  SCIPdebugMsg(masterprob, "No <%s> cut added. Current Master Problem Obj: %g\n", BENDERSCUT_NAME,
333  SCIPgetSolOrigObj(masterprob, NULL)*(int)SCIPgetObjsense(masterprob));
334  return SCIP_OKAY;
335  }
336 
337  /* checking if the subproblem lower bound has been updated. If it is has changed, then firstcut is set to TRUE.
338  * Otherwise, the constant remains the same.
339  */
340  if( SCIPisLT(masterprob, benderscutdata->subprobconstant[probnumber],
341  SCIPbendersGetSubproblemLowerbound(benders, probnumber)) )
342  {
343  benderscutdata->subprobconstant[probnumber] = SCIPbendersGetSubproblemLowerbound(benders, probnumber);
344  benderscutdata->firstcut[probnumber] = TRUE;
345  }
346 
347  /* if no integer cuts have been previously generated, then an initial lower bounding cut is added */
348  if( benderscutdata->firstcut[probnumber] )
349  {
350  benderscutdata->firstcut[probnumber] = FALSE;
351  SCIP_CALL( generateAndApplyBendersIntegerCuts(masterprob, benders, benderscut, sol, probnumber, type, result,
352  TRUE) );
353  }
354 
355  /* setting the name of the generated cut */
356  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "integeroptcut_%d_%d", probnumber,
357  SCIPbenderscutGetNFound(benderscut) );
358 
359  /* creating an empty row or constraint for the Benders' cut */
360  if( addcut )
361  {
362  SCIP_CALL( SCIPcreateEmptyRowCons(masterprob, &row, consbenders, cutname, 0.0, SCIPinfinity(masterprob), FALSE,
363  FALSE, TRUE) );
364  }
365  else
366  {
367  SCIP_CALL( SCIPcreateConsBasicLinear(masterprob, &cons, cutname, 0, NULL, NULL, 0.0, SCIPinfinity(masterprob)) );
368  SCIP_CALL( SCIPsetConsDynamic(masterprob, cons, TRUE) );
369  SCIP_CALL( SCIPsetConsRemovable(masterprob, cons, TRUE) );
370  }
371 
372  if( initcons )
373  {
374  SCIP_Real lhs;
375 
376  /* adding the subproblem objective function value to the lhs */
377  if( addcut )
378  lhs = SCIProwGetLhs(row);
379  else
380  lhs = SCIPgetLhsLinear(masterprob, cons);
381 
382  lhs += benderscutdata->subprobconstant[probnumber];
383 
384  /* if the bound becomes infinite, then the cut generation terminates. */
385  if( SCIPisInfinity(masterprob, lhs) || SCIPisInfinity(masterprob, -lhs) )
386  {
387  success = FALSE;
388  SCIPdebugMsg(masterprob, "Infinite bound when generating integer optimality cut.\n");
389  }
390 
391  /* Update the lhs of the cut */
392  if( addcut )
393  {
394  SCIP_CALL( SCIPchgRowLhs(masterprob, row, lhs) );
395  }
396  else
397  {
398  SCIP_CALL( SCIPchgLhsLinear(masterprob, cons, lhs) );
399  }
400  }
401  else
402  {
403  /* computing the coefficients of the optimality cut */
404  SCIP_CALL( computeStandardIntegerOptCut(masterprob, benders, sol, cons, row,
405  benderscutdata->subprobconstant[probnumber], probnumber, addcut, &success) );
406  }
407 
408  /* if success is FALSE, then there was an error in generating the integer optimality cut. No cut will be added to
409  * the master problem. Otherwise, the constraint is added to the master problem.
410  */
411  if( !success )
412  {
413  (*result) = SCIP_DIDNOTFIND;
414  SCIPdebugMsg(masterprob, "Error in generating Benders' integer optimality cut for problem %d.\n", probnumber);
415  }
416  else
417  {
418  /* adding the auxiliary variable to the optimality cut */
419  SCIP_CALL( addAuxiliaryVariableToCut(masterprob, benders, cons, row, probnumber, addcut) );
420 
421  /* adding the constraint to the master problem */
422  if( addcut )
423  {
424  SCIP_Bool infeasible;
425 
426  if( type == SCIP_BENDERSENFOTYPE_LP || type == SCIP_BENDERSENFOTYPE_RELAX )
427  {
428  SCIP_CALL( SCIPaddRow(masterprob, row, FALSE, &infeasible) );
429  assert(!infeasible);
430  }
431  else
432  {
433  assert(type == SCIP_BENDERSENFOTYPE_CHECK || type == SCIP_BENDERSENFOTYPE_PSEUDO);
434  SCIP_CALL( SCIPaddPoolCut(masterprob, row) );
435  }
436 
437 #ifdef SCIP_DEBUG
438  SCIP_CALL( SCIPprintRow(masterprob, row, NULL) );
439  SCIPinfoMessage(masterprob, NULL, ";\n");
440 #endif
441 
442  (*result) = SCIP_SEPARATED;
443  }
444  else
445  {
446  SCIP_CALL( SCIPaddCons(masterprob, cons) );
447 
448  SCIPdebugPrintCons(masterprob, cons, NULL);
449 
450  (*result) = SCIP_CONSADDED;
451  }
452  }
453 
454  if( addcut )
455  {
456  /* release the row */
457  SCIP_CALL( SCIPreleaseRow(masterprob, &row) );
458  }
459  else
460  {
461  /* release the constraint */
462  SCIP_CALL( SCIPreleaseCons(masterprob, &cons) );
463  }
464 
465  return SCIP_OKAY;
466 }
467 
468 /*
469  * Callback methods of Benders' decomposition cuts
470  */
471 
472 /** destructor of Benders' decomposition cuts to free user data (called when SCIP is exiting) */
473 static
474 SCIP_DECL_BENDERSCUTFREE(benderscutFreeInt)
475 { /*lint --e{715}*/
476  SCIP_BENDERSCUTDATA* benderscutdata;
477 
478  assert( benderscut != NULL );
479  assert( strcmp(SCIPbenderscutGetName(benderscut), BENDERSCUT_NAME) == 0 );
480 
481  /* free Benders' cut data */
482  benderscutdata = SCIPbenderscutGetData(benderscut);
483  assert( benderscutdata != NULL );
484 
485  SCIPfreeBlockMemory(scip, &benderscutdata);
486 
487  SCIPbenderscutSetData(benderscut, NULL);
488 
489  return SCIP_OKAY;
490 }
491 
492 
493 /** initialization method of Benders' decomposition cuts (called after problem was transformed) */
494 static
495 SCIP_DECL_BENDERSCUTINIT(benderscutInitInt)
496 { /*lint --e{715}*/
497  SCIP_BENDERSCUTDATA* benderscutdata;
498 
499  assert( benderscut != NULL );
500  assert( strcmp(SCIPbenderscutGetName(benderscut), BENDERSCUT_NAME) == 0 );
501 
502  /* free Benders' cut data */
503  benderscutdata = SCIPbenderscutGetData(benderscut);
504  assert( benderscutdata != NULL );
505 
506  benderscutdata->nsubproblems = SCIPbendersGetNSubproblems(benderscutdata->benders);
507  SCIP_CALL( createBenderscutData(scip, benderscutdata) );
508 
509  return SCIP_OKAY;
510 }
511 
512 /** deinitialization method of Benders' decomposition cuts (called before transformed problem is freed) */
513 static
514 SCIP_DECL_BENDERSCUTEXIT(benderscutExitInt)
515 { /*lint --e{715}*/
516  SCIP_BENDERSCUTDATA* benderscutdata;
517 
518  assert( benderscut != NULL );
519  assert( strcmp(SCIPbenderscutGetName(benderscut), BENDERSCUT_NAME) == 0 );
520 
521  /* free Benders' cut data */
522  benderscutdata = SCIPbenderscutGetData(benderscut);
523  assert( benderscutdata != NULL );
524 
525  SCIPfreeBlockMemoryArray(scip, &benderscutdata->firstcut, benderscutdata->nsubproblems);
526  SCIPfreeBlockMemoryArray(scip, &benderscutdata->subprobconstant, benderscutdata->nsubproblems);
527 
528  return SCIP_OKAY;
529 }
530 
531 /** execution method of Benders' decomposition cuts */
532 static
533 SCIP_DECL_BENDERSCUTEXEC(benderscutExecInt)
534 { /*lint --e{715}*/
535  assert(scip != NULL);
536  assert(benders != NULL);
537  assert(benderscut != NULL);
538  assert(result != NULL);
539 
540  /* it is only possible to generate the Laporte and Louveaux cuts for pure binary master problems */
542  {
543  SCIPinfoMessage(scip, NULL, "The integer optimality cuts can only be applied to problems with a "
544  "pure binary master problem. The integer optimality cuts will be disabled.\n");
545 
546  SCIPbenderscutSetEnabled(benderscut, FALSE);
547 
548  return SCIP_OKAY;
549  }
550 
551  /* the integer subproblem could terminate early if the auxiliary variable value is much greater than the optimal
552  * solution. As such, it is only necessary to generate a cut if the subproblem is OPTIMAL */
553  if( SCIPgetStatus(SCIPbendersSubproblem(benders, probnumber)) == SCIP_STATUS_OPTIMAL )
554  {
555  /* generating a cut for a given subproblem */
556  SCIP_CALL( generateAndApplyBendersIntegerCuts(scip, benders, benderscut, sol, probnumber, type, result, FALSE) );
557  }
558 
559  return SCIP_OKAY;
560 }
561 
562 
563 /*
564  * Benders' decomposition cuts specific interface methods
565  */
566 
567 /** creates the int Benders' decomposition cuts and includes it in SCIP */
569  SCIP* scip, /**< SCIP data structure */
570  SCIP_BENDERS* benders /**< Benders' decomposition */
571  )
572 {
573  SCIP_BENDERSCUTDATA* benderscutdata;
574  SCIP_BENDERSCUT* benderscut;
575  char paramname[SCIP_MAXSTRLEN];
576 
577  assert(benders != NULL);
578 
579  /* create int Benders' decomposition cuts data */
580  SCIP_CALL( SCIPallocBlockMemory(scip, &benderscutdata) );
581  benderscutdata->benders = benders;
582 
583  benderscut = NULL;
584 
585  /* include Benders' decomposition cuts */
587  BENDERSCUT_PRIORITY, BENDERSCUT_LPCUT, benderscutExecInt, benderscutdata) );
588 
589  assert(benderscut != NULL);
590 
591  /* set non fundamental callbacks via setter functions */
592  SCIP_CALL( SCIPsetBenderscutFree(scip, benderscut, benderscutFreeInt) );
593  SCIP_CALL( SCIPsetBenderscutInit(scip, benderscut, benderscutInitInt) );
594  SCIP_CALL( SCIPsetBenderscutExit(scip, benderscut, benderscutExitInt) );
595 
596  /* add int Benders' decomposition cuts parameters */
597  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/benderscut/%s/cutsconstant",
599  SCIP_CALL( SCIPaddRealParam(scip, paramname,
600  "the constant term of the integer Benders' cuts.",
601  &benderscutdata->cutconstant, FALSE, SCIP_DEFAULT_CUTCONSTANT, -SCIPinfinity(scip), SCIPinfinity(scip),
602  paramChgdBenderscutintConstant, (SCIP_PARAMDATA*)benderscutdata) );
603 
604  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/benderscut/%s/addcuts",
606  SCIP_CALL( SCIPaddBoolParam(scip, paramname,
607  "should cuts be generated and added to the cutpool instead of global constraints directly added to the problem.",
608  &benderscutdata->addcuts, FALSE, SCIP_DEFAULT_ADDCUTS, NULL, NULL) );
609 
610  return SCIP_OKAY;
611 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
Generates a Laporte and Louveaux Benders&#39; decomposition integer cut.
SCIP_RETCODE SCIPincludeBenderscutInt(SCIP *scip, SCIP_BENDERS *benders)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:116
SCIP_Real SCIPgetActivityLinear(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
const char * SCIPbenderscutGetName(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:508
#define NULL
Definition: def.h:246
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)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:99
SCIP_Real SCIPbendersGetSubproblemObjval(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:4428
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:411
static SCIP_RETCODE generateAndApplyBendersIntegerCuts(SCIP *masterprob, SCIP_BENDERS *benders, SCIP_BENDERSCUT *benderscut, SCIP_SOL *sol, int probnumber, SCIP_BENDERSENFOTYPE type, SCIP_RESULT *result, SCIP_Bool initcons)
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
static SCIP_DECL_BENDERSCUTFREE(benderscutFreeInt)
SCIP_BENDERSCUTDATA * SCIPbenderscutGetData(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:419
static SCIP_DECL_PARAMCHGD(paramChgdBenderscutintConstant)
SCIP_PARAMDATA * SCIPparamGetData(SCIP_PARAM *param)
Definition: paramset.c:661
#define SCIP_MAXSTRLEN
Definition: def.h:267
const char * SCIPbendersGetName(SCIP_BENDERS *benders)
Definition: benders.c:4191
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1607
#define BENDERSCUT_NAME
struct SCIP_ParamData SCIP_PARAMDATA
Definition: type_paramset.h:76
void SCIPbenderscutSetData(SCIP_BENDERSCUT *benderscut, SCIP_BENDERSCUTDATA *benderscutdata)
Definition: benderscut.c:429
static SCIP_RETCODE createBenderscutData(SCIP *scip, SCIP_BENDERSCUTDATA *benderscutdata)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:16959
#define FALSE
Definition: def.h:72
public methods for Benders&#39; decomposition
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10253
#define TRUE
Definition: def.h:71
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE
Definition: type_benders.h:42
static SCIP_RETCODE addAuxiliaryVariableToCut(SCIP *masterprob, SCIP_BENDERS *benders, SCIP_CONS *cons, SCIP_ROW *row, int probnumber, SCIP_Bool addcut)
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
#define BENDERSCUT_PRIORITY
#define BENDERSCUT_DESC
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:83
SCIP_RETCODE SCIPgetBendersSubproblemVar(SCIP *scip, SCIP_BENDERS *benders, SCIP_VAR *var, SCIP_VAR **mappedvar, int probnumber)
Definition: scip_benders.c:739
#define SCIPdebugMsg
Definition: scip_message.h:88
SCIP_Longint SCIPbenderscutGetNFound(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:559
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
#define BENDERSCUT_LPCUT
public methods for numerical tolerances
public methods for handling parameter settings
SCIP_RETCODE SCIPsetConsRemovable(SCIP *scip, SCIP_CONS *cons, SCIP_Bool removable)
Definition: scip_cons.c:1488
void SCIPbenderscutSetEnabled(SCIP_BENDERSCUT *benderscut, SCIP_Bool enabled)
Definition: benderscut.c:695
public methods for Benders decomposition
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2822
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:518
static SCIP_RETCODE computeStandardIntegerOptCut(SCIP *masterprob, SCIP_BENDERS *benders, SCIP_SOL *sol, SCIP_CONS *cons, SCIP_ROW *row, SCIP_Real cutconstant, int probnumber, SCIP_Bool addcut, SCIP_Bool *success)
SCIP_RETCODE SCIPsetConsDynamic(SCIP *scip, SCIP_CONS *cons, SCIP_Bool dynamic)
Definition: scip_cons.c:1463
#define SCIP_CALL(x)
Definition: def.h:358
SCIP_RETCODE SCIPsetBenderscutExit(SCIP *scip, SCIP_BENDERSCUT *benderscut, SCIP_DECL_BENDERSCUTEXIT((*benderscutexit)))
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_DECL_BENDERSCUTEXEC(benderscutExecInt)
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:69
static SCIP_DECL_BENDERSCUTINIT(benderscutInitInt)
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
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
#define SCIP_DEFAULT_ADDCUTS
SCIP * SCIPbendersSubproblem(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:4245
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1493
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:2050
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:4235
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2089
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 SCIPsetBenderscutInit(SCIP *scip, SCIP_BENDERSCUT *benderscut, SCIP_DECL_BENDERSCUTINIT((*benderscutinit)))
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1474
general public methods
SCIP_Real SCIPbendersGetSubproblemLowerbound(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:4748
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2362
public methods for solutions
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1187
public methods for message output
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1999
#define SCIP_Real
Definition: def.h:157
public methods for message handling
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2099
SCIP_RETCODE SCIPsetBenderscutFree(SCIP *scip, SCIP_BENDERSCUT *benderscut, SCIP_DECL_BENDERSCUTFREE((*benderscutfree)))
SCIP_OBJSENSE SCIPgetObjsense(SCIP *scip)
Definition: scip_prob.c:1281
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
static SCIP_DECL_BENDERSCUTEXIT(benderscutExitInt)
#define SCIP_DEFAULT_CUTCONSTANT
SCIP_VAR * SCIPbendersGetAuxiliaryVar(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:4389
public methods for global and local (sub)problems
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1410
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:211
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