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-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file benderscut_opt.c
17  * @ingroup OTHER_CFILES
18  * @brief Generates a standard Benders' decomposition optimality cut
19  * @author Stephen J. Maher
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include "scip/pub_expr.h"
25 #include "scip/benderscut_opt.h"
26 #include "scip/cons_linear.h"
27 #include "scip/pub_benderscut.h"
28 #include "scip/pub_benders.h"
29 #include "scip/pub_lp.h"
30 #include "scip/pub_nlp.h"
31 #include "scip/pub_message.h"
32 #include "scip/pub_misc.h"
33 #include "scip/pub_misc_linear.h"
34 #include "scip/pub_var.h"
35 #include "scip/scip.h"
36 #include <string.h>
37 
38 #define BENDERSCUT_NAME "optimality"
39 #define BENDERSCUT_DESC "Standard Benders' decomposition optimality cut"
40 #define BENDERSCUT_PRIORITY 5000
41 #define BENDERSCUT_LPCUT TRUE
42 
43 #define SCIP_DEFAULT_ADDCUTS FALSE /** Should cuts be generated, instead of constraints */
44 #define SCIP_DEFAULT_CALCMIR TRUE /** Should the mixed integer rounding procedure be used for the cut */
45 
46 /*
47  * Data structures
48  */
49 
50 /** Benders' decomposition cuts data */
51 struct SCIP_BenderscutData
52 {
53  SCIP_Bool addcuts; /**< should cuts be generated instead of constraints */
54  SCIP_Bool calcmir; /**< should the mixed integer rounding procedure be applied to cuts */
55 };
56 
57 
58 /*
59  * Local methods
60  */
61 
62 /** in the case of numerical troubles, the LP is resolved with solution polishing activated */
63 static
65  SCIP* subproblem, /**< the SCIP data structure */
66  SCIP_Bool* success /**< TRUE is the resolving of the LP was successful */
67  )
68 {
69  int oldpolishing;
70  SCIP_Bool lperror;
71  SCIP_Bool cutoff;
72 
73  assert(subproblem != NULL);
74  assert(SCIPinProbing(subproblem));
75 
76  (*success) = FALSE;
77 
78  /* setting the solution polishing parameter */
79  SCIP_CALL( SCIPgetIntParam(subproblem, "lp/solutionpolishing", &oldpolishing) );
80  SCIP_CALL( SCIPsetIntParam(subproblem, "lp/solutionpolishing", 2) );
81 
82  /* resolving the probing LP */
83  SCIP_CALL( SCIPsolveProbingLP(subproblem, -1, &lperror, &cutoff) );
84 
85  if( SCIPgetLPSolstat(subproblem) == SCIP_LPSOLSTAT_OPTIMAL )
86  (*success) = TRUE;
87 
88  /* resetting the solution polishing parameter */
89  SCIP_CALL( SCIPsetIntParam(subproblem, "lp/solutionpolishing", oldpolishing) );
90 
91  return SCIP_OKAY;
92 }
93 
94 /** verifying the activity of the cut when master variables are within epsilon of their upper or lower bounds
95  *
96  * When setting up the Benders' decomposition subproblem, master variables taking values that are within epsilon
97  * greater than their upper bound or less than their lower bound are set to their upper and lower bounds respectively.
98  * As such, there can be a difference between the subproblem dual solution objective and the optimality cut activity,
99  * when computed using the master problem solution directly. This check is to verify whether this difference is an
100  * actual error or due to the violation of the upper and lower bounds when setting up the Benders' decomposition
101  * subproblem.
102  */
103 static
105  SCIP* masterprob, /**< the SCIP data structure */
106  SCIP_SOL* sol, /**< the master problem solution */
107  SCIP_VAR** vars, /**< pointer to array of variables in the generated cut with non-zero coefficient */
108  SCIP_Real* vals, /**< pointer to array of coefficients of the variables in the generated cut */
109  SCIP_Real lhs, /**< the left hand side of the cut */
110  SCIP_Real checkobj, /**< the objective of the subproblem computed from the dual solution */
111  int nvars, /**< the number of variables in the cut */
112  SCIP_Bool* valid /**< returns true is the cut is valid */
113  )
114 {
115  SCIP_Real verifyobj;
116  int i;
117 
118  assert(masterprob != NULL);
119  assert(vars != NULL);
120  assert(vals != NULL);
121 
122  /* initialising the verify objective with the left hand side of the optimality cut */
123  verifyobj = lhs;
124 
125  /* computing the activity of the cut from the master solution and the constraint values */
126  for( i = 0; i < nvars; i++ )
127  {
128  SCIP_Real solval;
129 
130  solval = SCIPgetSolVal(masterprob, sol, vars[i]);
131 
132  /* checking whether the solution value is less than or greater than the variable bounds */
133  if( !SCIPisLT(masterprob, solval, SCIPvarGetUbLocal(vars[i])) )
134  solval = SCIPvarGetUbLocal(vars[i]);
135  else if( !SCIPisGT(masterprob, solval, SCIPvarGetLbLocal(vars[i])) )
136  solval = SCIPvarGetLbLocal(vars[i]);
137 
138  verifyobj -= solval*vals[i];
139  }
140 
141  (*valid) = SCIPisFeasEQ(masterprob, checkobj, verifyobj);
142 
143  return SCIP_OKAY;
144 }
145 
146 /** when solving NLP subproblems, numerical issues are addressed by tightening the feasibility tolerance */
147 static
149  SCIP* subproblem, /**< the SCIP data structure */
150  SCIP_Real multiplier, /**< the amount by which to decrease the tolerance */
151  SCIP_Bool* success /**< TRUE is the resolving of the LP was successful */
152  )
153 {
154  SCIP_NLPSOLSTAT nlpsolstat;
155 #ifdef SCIP_DEBUG
156  SCIP_NLPTERMSTAT nlptermstat;
157 #endif
158  SCIP_NLPPARAM nlpparam = SCIP_NLPPARAM_DEFAULT(subproblem); /*lint !e446*/
159 #ifdef SCIP_MOREDEBUG
160  SCIP_SOL* nlpsol;
161 #endif
162 
163  assert(subproblem != NULL);
164  assert(SCIPinProbing(subproblem));
165 
166  (*success) = FALSE;
167 
168  /* reduce the default feasibility and optimality tolerance by given factor (typically 0.01) */
169  nlpparam.feastol *= multiplier;
170  nlpparam.opttol *= multiplier;
171 
172  SCIP_CALL( SCIPsolveNLPParam(subproblem, nlpparam) );
173 
174  nlpsolstat = SCIPgetNLPSolstat(subproblem);
175 #ifdef SCIP_DEBUG
176  nlptermstat = SCIPgetNLPTermstat(subproblem);
177  SCIPdebugMsg(subproblem, "NLP solstat %d termstat %d\n", nlpsolstat, nlptermstat);
178 #endif
179 
180  if( nlpsolstat == SCIP_NLPSOLSTAT_LOCOPT || nlpsolstat == SCIP_NLPSOLSTAT_GLOBOPT
181  || nlpsolstat == SCIP_NLPSOLSTAT_FEASIBLE )
182  {
183 #ifdef SCIP_MOREDEBUG
184  SCIP_CALL( SCIPcreateNLPSol(subproblem, &nlpsol, NULL) );
185  SCIP_CALL( SCIPprintSol(subproblem, nlpsol, NULL, FALSE) );
186  SCIP_CALL( SCIPfreeSol(subproblem, &nlpsol) );
187 #endif
188 
189  (*success) = TRUE;
190  }
191 
192  return SCIP_OKAY;
193 }
194 
195 /** adds a variable and value to the constraint/row arrays */
196 static
198  SCIP* masterprob, /**< the SCIP instance of the master problem */
199  SCIP_VAR*** vars, /**< pointer to the array of variables in the generated cut with non-zero coefficient */
200  SCIP_Real** vals, /**< pointer to the array of coefficients of the variables in the generated cut */
201  SCIP_VAR* addvar, /**< the variable that will be added to the array */
202  SCIP_Real addval, /**< the value that will be added to the array */
203  int* nvars, /**< the number of variables in the variable array */
204  int* varssize /**< the length of the variable size */
205  )
206 {
207  assert(masterprob != NULL);
208  assert(vars != NULL);
209  assert(*vars != NULL);
210  assert(vals != NULL);
211  assert(*vals != NULL);
212  assert(addvar != NULL);
213  assert(nvars != NULL);
214  assert(varssize != NULL);
215 
216  if( *nvars >= *varssize )
217  {
218  *varssize = SCIPcalcMemGrowSize(masterprob, *varssize + 1);
219  SCIP_CALL( SCIPreallocBufferArray(masterprob, vars, *varssize) );
220  SCIP_CALL( SCIPreallocBufferArray(masterprob, vals, *varssize) );
221  }
222  assert(*nvars < *varssize);
223 
224  (*vars)[*nvars] = addvar;
225  (*vals)[*nvars] = addval;
226  (*nvars)++;
227 
228  return SCIP_OKAY;
229 }
230 
231 /** returns the variable solution either from the NLP or from the primal vals array */
232 static
234  SCIP_VAR* var, /**< the variable for which the solution is requested */
235  SCIP_Real* primalvals, /**< the primal solutions for the NLP, can be NULL */
236  SCIP_HASHMAP* var2idx /**< mapping from variable of the subproblem to the index in the dual arrays, can be NULL */
237  )
238 {
239  SCIP_Real varsol;
240  int idx;
241 
242  assert(var != NULL);
243  assert((primalvals == NULL && var2idx == NULL) || (primalvals != NULL && var2idx != NULL));
244 
245  if( var2idx != NULL && primalvals != NULL )
246  {
247  assert(SCIPhashmapExists(var2idx, (void*)var) );
248  idx = SCIPhashmapGetImageInt(var2idx, (void*)var);
249  varsol = primalvals[idx];
250  }
251  else
252  varsol = SCIPvarGetNLPSol(var);
253 
254  return varsol;
255 }
256 
257 /** calculates a MIR cut from the coefficients of the standard optimality cut */
258 static
260  SCIP* masterprob, /**< the SCIP instance of the master problem */
261  SCIP_SOL* sol, /**< primal CIP solution */
262  SCIP_VAR** vars, /**< pointer to array of variables in the generated cut with non-zero coefficient */
263  SCIP_Real* vals, /**< pointer to array of coefficients of the variables in the generated cut */
264  SCIP_Real lhs, /**< the left hand side of the cut */
265  SCIP_Real rhs, /**< the right hand side of the cut */
266  int nvars, /**< the number of variables in the cut */
267  SCIP_Real* cutcoefs, /**< the coefficients of the MIR cut */
268  int* cutinds, /**< the variable indices of the MIR cut */
269  SCIP_Real* cutrhs, /**< the RHS of the MIR cut */
270  int* cutnnz, /**< the number of non-zeros in the cut */
271  SCIP_Bool* success /**< was the MIR cut successfully computed? */
272  )
273 {
274  SCIP_AGGRROW* aggrrow;
275  SCIP_Real* rowvals;
276  int* rowinds;
277 
278  SCIP_Real cutefficacy;
279  int cutrank;
280  SCIP_Bool cutislocal;
281 
282  SCIP_Bool cutsuccess;
283 
284  int i;
285 
286  /* creating the aggregation row. There will be only a single row in this aggregation, since it is only used to
287  * compute the MIR coefficients
288  */
289  SCIP_CALL( SCIPaggrRowCreate(masterprob, &aggrrow) );
290 
291  /* retrieving the indices for the variables in the optimality cut. All of the values must be negated, since the
292  * aggregation row requires a RHS, where the optimality cut is computed with an LHS
293  */
294  SCIP_CALL( SCIPallocBufferArray(masterprob, &rowvals, nvars) );
295  SCIP_CALL( SCIPallocBufferArray(masterprob, &rowinds, nvars) );
296 
297  assert(SCIPisInfinity(masterprob, rhs));
298  assert(!SCIPisInfinity(masterprob, lhs));
299  for( i = 0; i < nvars; i++ )
300  {
301  rowinds[i] = SCIPvarGetProbindex(vars[i]);
302  rowvals[i] = -vals[i];
303  }
304 
305  /* adding the optimality cut to the aggregation row */
306  SCIP_CALL( SCIPaggrRowAddCustomCons(masterprob, aggrrow, rowinds, rowvals, nvars, -lhs, 1.0, 1, FALSE) );
307 
308  /* calculating a flow cover for the optimality cut */
309  SCIP_CALL( SCIPcalcFlowCover(masterprob, sol, TRUE, 0.9999, FALSE, aggrrow, cutcoefs, cutrhs, cutinds, cutnnz,
310  &cutefficacy, NULL, &cutislocal, &cutsuccess) );
311  (*success) = cutsuccess;
312 
313  /* calculating the MIR coefficients for the optimality cut */
314  SCIP_CALL( SCIPcalcMIR(masterprob, sol, TRUE, 0.9999, TRUE, FALSE, FALSE, NULL, NULL, 0.001, 0.999, 1.0, aggrrow,
315  cutcoefs, cutrhs, cutinds, cutnnz, &cutefficacy, &cutrank, &cutislocal, &cutsuccess) );
316  (*success) = ((*success) || cutsuccess);
317 
318  /* the cut is only successful if the efficacy is high enough */
319  (*success) = (*success) && SCIPisEfficacious(masterprob, cutefficacy);
320 
321  /* try to tighten the coefficients of the cut */
322  if( (*success) )
323  {
324  SCIP_Bool redundant;
325  int nchgcoefs;
326 
327  redundant = SCIPcutsTightenCoefficients(masterprob, FALSE, cutcoefs, cutrhs, cutinds, cutnnz, &nchgcoefs);
328 
329  (*success) = !redundant;
330  }
331 
332  /* freeing the local memory */
333  SCIPfreeBufferArray(masterprob, &rowinds);
334  SCIPfreeBufferArray(masterprob, &rowvals);
335  SCIPaggrRowFree(masterprob, &aggrrow);
336 
337  return SCIP_OKAY;
338 }
339 
340 /** computes a standard Benders' optimality cut from the dual solutions of the LP */
341 static
343  SCIP* masterprob, /**< the SCIP instance of the master problem */
344  SCIP* subproblem, /**< the SCIP instance of the subproblem */
345  SCIP_BENDERS* benders, /**< the benders' decomposition structure */
346  SCIP_VAR*** vars, /**< pointer to array of variables in the generated cut with non-zero coefficient */
347  SCIP_Real** vals, /**< pointer to array of coefficients of the variables in the generated cut */
348  SCIP_Real* lhs, /**< the left hand side of the cut */
349  SCIP_Real* rhs, /**< the right hand side of the cut */
350  int* nvars, /**< the number of variables in the cut */
351  int* varssize, /**< the number of variables in the array */
352  SCIP_Real* checkobj, /**< stores the objective function computed from the dual solution */
353  SCIP_Bool* success /**< was the cut generation successful? */
354  )
355 {
356  SCIP_VAR** subvars;
357  SCIP_VAR** fixedvars;
358  int nsubvars;
359  int nfixedvars;
360  SCIP_Real dualsol;
361  SCIP_Real addval;
362  int nrows;
363  int i;
364 
365  (*checkobj) = 0;
366 
367  assert(masterprob != NULL);
368  assert(subproblem != NULL);
369  assert(benders != NULL);
370  assert(vars != NULL);
371  assert(*vars != NULL);
372  assert(vals != NULL);
373  assert(*vals != NULL);
374 
375  (*success) = FALSE;
376 
377  /* looping over all LP rows and setting the coefficients of the cut */
378  nrows = SCIPgetNLPRows(subproblem);
379  for( i = 0; i < nrows; i++ )
380  {
381  SCIP_ROW* lprow;
382 
383  lprow = SCIPgetLPRows(subproblem)[i];
384  assert(lprow != NULL);
385 
386  dualsol = SCIProwGetDualsol(lprow);
387  assert( !SCIPisInfinity(subproblem, dualsol) && !SCIPisInfinity(subproblem, -dualsol) );
388 
389  if( SCIPisZero(subproblem, dualsol) )
390  continue;
391 
392  if( dualsol > 0.0 )
393  addval = dualsol*SCIProwGetLhs(lprow);
394  else
395  addval = dualsol*SCIProwGetRhs(lprow);
396 
397  (*lhs) += addval;
398 
399  /* if the bound becomes infinite, then the cut generation terminates. */
400  if( SCIPisInfinity(masterprob, (*lhs)) || SCIPisInfinity(masterprob, -(*lhs))
401  || SCIPisInfinity(masterprob, addval) || SCIPisInfinity(masterprob, -addval))
402  {
403  (*success) = FALSE;
404  SCIPdebugMsg(masterprob, "Infinite bound when generating optimality cut. lhs = %g addval = %g.\n", (*lhs), addval);
405  return SCIP_OKAY;
406  }
407  }
408 
409  nsubvars = SCIPgetNVars(subproblem);
410  subvars = SCIPgetVars(subproblem);
411  nfixedvars = SCIPgetNFixedVars(subproblem);
412  fixedvars = SCIPgetFixedVars(subproblem);
413 
414  /* looping over all variables to update the coefficients in the computed cut. */
415  for( i = 0; i < nsubvars + nfixedvars; i++ )
416  {
417  SCIP_VAR* var;
418  SCIP_VAR* mastervar;
419  SCIP_Real redcost;
420 
421  if( i < nsubvars )
422  var = subvars[i];
423  else
424  var = fixedvars[i - nsubvars];
425 
426  /* retrieving the master problem variable for the given subproblem variable. */
427  SCIP_CALL( SCIPgetBendersMasterVar(masterprob, benders, var, &mastervar) );
428 
429  redcost = SCIPgetVarRedcost(subproblem, var);
430 
431  (*checkobj) += SCIPvarGetUnchangedObj(var)*SCIPvarGetSol(var, TRUE);
432 
433  /* checking whether the subproblem variable has a corresponding master variable. */
434  if( mastervar != NULL )
435  {
436  SCIP_Real coef;
437 
438  coef = -1.0*(SCIPvarGetObj(var) + redcost);
439 
440  if( !SCIPisZero(masterprob, coef) )
441  {
442  /* adding the variable to the storage */
443  SCIP_CALL( addVariableToArray(masterprob, vars, vals, mastervar, coef, nvars, varssize) );
444  }
445  }
446  else
447  {
448  if( !SCIPisZero(subproblem, redcost) )
449  {
450  addval = 0;
451 
452  if( SCIPisPositive(subproblem, redcost) )
453  addval = redcost*SCIPvarGetLbLocal(var);
454  else if( SCIPisNegative(subproblem, redcost) )
455  addval = redcost*SCIPvarGetUbLocal(var);
456 
457  (*lhs) += addval;
458 
459  /* if the bound becomes infinite, then the cut generation terminates. */
460  if( SCIPisInfinity(masterprob, (*lhs)) || SCIPisInfinity(masterprob, -(*lhs))
461  || SCIPisInfinity(masterprob, addval) || SCIPisInfinity(masterprob, -addval))
462  {
463  (*success) = FALSE;
464  SCIPdebugMsg(masterprob, "Infinite bound when generating optimality cut.\n");
465  return SCIP_OKAY;
466  }
467  }
468  }
469  }
470 
471  assert(SCIPisInfinity(masterprob, (*rhs)));
472  /* the rhs should be infinite. If it changes, then there is an error */
473  if( !SCIPisInfinity(masterprob, (*rhs)) )
474  {
475  (*success) = FALSE;
476  SCIPdebugMsg(masterprob, "RHS is not infinite. rhs = %g.\n", (*rhs));
477  return SCIP_OKAY;
478  }
479 
480  (*success) = TRUE;
481 
482  return SCIP_OKAY;
483 }
484 
485 /** computes a standard Benders' optimality cut from the dual solutions of the NLP */
486 static
488  SCIP* masterprob, /**< the SCIP instance of the master problem */
489  SCIP* subproblem, /**< the SCIP instance of the subproblem */
490  SCIP_BENDERS* benders, /**< the benders' decomposition structure */
491  SCIP_VAR*** vars, /**< pointer to array of variables in the generated cut with non-zero coefficient */
492  SCIP_Real** vals, /**< pointer to array of coefficients of the variables in the generated cut */
493  SCIP_Real* lhs, /**< the left hand side of the cut */
494  SCIP_Real* rhs, /**< the right hand side of the cut */
495  int* nvars, /**< the number of variables in the cut */
496  int* varssize, /**< the number of variables in the array */
497  SCIP_Real objective, /**< the objective function of the subproblem */
498  SCIP_Real* primalvals, /**< the primal solutions for the NLP, can be NULL */
499  SCIP_Real* consdualvals, /**< dual variables for the constraints, can be NULL */
500  SCIP_Real* varlbdualvals, /**< the dual variables for the variable lower bounds, can be NULL */
501  SCIP_Real* varubdualvals, /**< the dual variables for the variable upper bounds, can be NULL */
502  SCIP_HASHMAP* row2idx, /**< mapping between the row in the subproblem to the index in the dual array, can be NULL */
503  SCIP_HASHMAP* var2idx, /**< mapping from variable of the subproblem to the index in the dual arrays, can be NULL */
504  SCIP_Real* checkobj, /**< stores the objective function computed from the dual solution */
505  SCIP_Bool* success /**< was the cut generation successful? */
506  )
507 {
508  SCIP_VAR** subvars;
509  SCIP_VAR** fixedvars;
510  int nsubvars;
511  int nfixedvars;
512  SCIP_Real dirderiv;
513  SCIP_Real dualsol;
514  int nrows;
515  int idx;
516  int i;
517 
518  (*checkobj) = 0;
519 
520  assert(masterprob != NULL);
521  assert(subproblem != NULL);
522  assert(benders != NULL);
523  assert(SCIPisNLPConstructed(subproblem));
524  assert(SCIPgetNLPSolstat(subproblem) <= SCIP_NLPSOLSTAT_FEASIBLE || consdualvals != NULL);
525  assert(SCIPhasNLPSolution(subproblem) || consdualvals != NULL);
526 
527  (*success) = FALSE;
528 
529  if( !(primalvals == NULL && consdualvals == NULL && varlbdualvals == NULL && varubdualvals == NULL && row2idx == NULL && var2idx == NULL)
530  && !(primalvals != NULL && consdualvals != NULL && varlbdualvals != NULL && varubdualvals != NULL && row2idx != NULL && var2idx != NULL) ) /*lint !e845*/
531  {
532  SCIPerrorMessage("The optimality cut must generated from either a SCIP instance or all of the dual solutions and indices must be supplied");
533  (*success) = FALSE;
534 
535  return SCIP_ERROR;
536  }
537 
538  nsubvars = SCIPgetNNLPVars(subproblem);
539  subvars = SCIPgetNLPVars(subproblem);
540  nfixedvars = SCIPgetNFixedVars(subproblem);
541  fixedvars = SCIPgetFixedVars(subproblem);
542 
543  /* our optimality cut implementation assumes that SCIP did not modify the objective function and sense,
544  * that is, that the objective function value of the NLP corresponds to the value of the auxiliary variable
545  * if that wouldn't be the case, then the scaling and offset may have to be considered when adding the
546  * auxiliary variable to the cut (cons/row)?
547  */
548  assert(SCIPgetTransObjoffset(subproblem) == 0.0);
549  assert(SCIPgetTransObjscale(subproblem) == 1.0);
550  assert(SCIPgetObjsense(subproblem) == SCIP_OBJSENSE_MINIMIZE);
551 
552  (*lhs) = objective;
553  assert(!SCIPisInfinity(subproblem, REALABS(*lhs)));
554 
555  (*rhs) = SCIPinfinity(masterprob);
556 
557  dirderiv = 0.0;
558 
559  /* looping over all NLP rows and setting the corresponding coefficients of the cut */
560  nrows = SCIPgetNNLPNlRows(subproblem);
561  for( i = 0; i < nrows; i++ )
562  {
563  SCIP_NLROW* nlrow;
564 
565  nlrow = SCIPgetNLPNlRows(subproblem)[i];
566  assert(nlrow != NULL);
567 
568  if( row2idx != NULL && consdualvals != NULL )
569  {
570  assert(SCIPhashmapExists(row2idx, (void*)nlrow) );
571  idx = SCIPhashmapGetImageInt(row2idx, (void*)nlrow);
572  dualsol = consdualvals[idx];
573  }
574  else
575  dualsol = SCIPnlrowGetDualsol(nlrow);
576  assert( !SCIPisInfinity(subproblem, dualsol) && !SCIPisInfinity(subproblem, -dualsol) );
577 
578  if( SCIPisZero(subproblem, dualsol) )
579  continue;
580 
581  SCIP_CALL( SCIPaddNlRowGradientBenderscutOpt(masterprob, subproblem, benders, nlrow,
582  -dualsol, primalvals, var2idx, &dirderiv, vars, vals, nvars, varssize) );
583  }
584 
585  /* looping over sub- and fixed variables to compute checkobj */
586  for( i = 0; i < nsubvars; i++ )
587  (*checkobj) += SCIPvarGetObj(subvars[i]) * getNlpVarSol(subvars[i], primalvals, var2idx);
588 
589  for( i = 0; i < nfixedvars; i++ )
590  *checkobj += SCIPvarGetUnchangedObj(fixedvars[i]) * getNlpVarSol(fixedvars[i], primalvals, var2idx);
591 
592  *lhs += dirderiv;
593 
594  /* if the side became infinite or dirderiv was infinite, then the cut generation terminates. */
595  if( SCIPisInfinity(masterprob, *lhs) || SCIPisInfinity(masterprob, -*lhs)
596  || SCIPisInfinity(masterprob, dirderiv) || SCIPisInfinity(masterprob, -dirderiv))
597  {
598  (*success) = FALSE;
599  SCIPdebugMsg(masterprob, "Infinite bound when generating optimality cut. lhs = %g dirderiv = %g.\n", *lhs, dirderiv);
600  return SCIP_OKAY;
601  }
602 
603  (*success) = TRUE;
604 
605  return SCIP_OKAY;
606 }
607 
608 
609 /** Adds the auxiliary variable to the generated cut. If this is the first optimality cut for the subproblem, then the
610  * auxiliary variable is first created and added to the master problem.
611  */
612 static
614  SCIP* masterprob, /**< the SCIP instance of the master problem */
615  SCIP_BENDERS* benders, /**< the benders' decomposition structure */
616  SCIP_VAR** vars, /**< the variables in the generated cut with non-zero coefficient */
617  SCIP_Real* vals, /**< the coefficients of the variables in the generated cut */
618  int* nvars, /**< the number of variables in the cut */
619  int probnumber /**< the number of the pricing problem */
620  )
621 {
622  SCIP_VAR* auxiliaryvar;
623 
624  assert(masterprob != NULL);
625  assert(benders != NULL);
626  assert(vars != NULL);
627  assert(vals != NULL);
628 
629  auxiliaryvar = SCIPbendersGetAuxiliaryVar(benders, probnumber);
630 
631  vars[(*nvars)] = auxiliaryvar;
632  vals[(*nvars)] = 1.0;
633  (*nvars)++;
634 
635  return SCIP_OKAY;
636 }
637 
638 
639 /*
640  * Callback methods of Benders' decomposition cuts
641  */
642 
643 /** destructor of Benders' decomposition cuts to free user data (called when SCIP is exiting) */
644 static
645 SCIP_DECL_BENDERSCUTFREE(benderscutFreeOpt)
646 { /*lint --e{715}*/
647  SCIP_BENDERSCUTDATA* benderscutdata;
648 
649  assert( benderscut != NULL );
650  assert( strcmp(SCIPbenderscutGetName(benderscut), BENDERSCUT_NAME) == 0 );
651 
652  /* free Benders' cut data */
653  benderscutdata = SCIPbenderscutGetData(benderscut);
654  assert( benderscutdata != NULL );
655 
656  SCIPfreeBlockMemory(scip, &benderscutdata);
657 
658  SCIPbenderscutSetData(benderscut, NULL);
659 
660  return SCIP_OKAY;
661 }
662 
663 
664 /** execution method of Benders' decomposition cuts */
665 static
666 SCIP_DECL_BENDERSCUTEXEC(benderscutExecOpt)
667 { /*lint --e{715}*/
668  SCIP* subproblem;
669  SCIP_BENDERSCUTDATA* benderscutdata;
670  SCIP_Bool nlprelaxation;
671  SCIP_Bool addcut;
672  char cutname[SCIP_MAXSTRLEN];
673 
674  assert(scip != NULL);
675  assert(benders != NULL);
676  assert(benderscut != NULL);
677  assert(result != NULL);
678  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
679 
680  /* retrieving the Benders' cut data */
681  benderscutdata = SCIPbenderscutGetData(benderscut);
682 
683  /* if the cuts are generated prior to the solving stage, then rows can not be generated. So constraints must be
684  * added to the master problem.
685  */
687  addcut = FALSE;
688  else
689  addcut = benderscutdata->addcuts;
690 
691  /* setting the name of the generated cut */
692  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "optimalitycut_%d_%" SCIP_LONGINT_FORMAT, probnumber,
693  SCIPbenderscutGetNFound(benderscut) );
694 
695  subproblem = SCIPbendersSubproblem(benders, probnumber);
696 
697  if( subproblem == NULL )
698  {
699  SCIPdebugMsg(scip, "The subproblem %d is set to NULL. The <%s> Benders' decomposition cut can not be executed.\n",
700  probnumber, BENDERSCUT_NAME);
701 
702  (*result) = SCIP_DIDNOTRUN;
703  return SCIP_OKAY;
704  }
705 
706  /* setting a flag to indicate whether the NLP relaxation should be used to generate cuts */
707  nlprelaxation = SCIPisNLPConstructed(subproblem) && SCIPgetNNlpis(subproblem);
708 
709  /* only generate optimality cuts if the subproblem LP or NLP is optimal,
710  * since we use the dual solution of the LP/NLP to construct the optimality cut
711  */
712  if( SCIPgetStage(subproblem) == SCIP_STAGE_SOLVING &&
713  ((!nlprelaxation && SCIPgetLPSolstat(subproblem) == SCIP_LPSOLSTAT_OPTIMAL) ||
714  (nlprelaxation && SCIPgetNLPSolstat(subproblem) <= SCIP_NLPSOLSTAT_FEASIBLE)) )
715  {
716  /* generating a cut for a given subproblem */
717  SCIP_CALL( SCIPgenerateAndApplyBendersOptCut(scip, subproblem, benders, benderscut, sol, probnumber, cutname,
718  SCIPbendersGetSubproblemObjval(benders, probnumber), NULL, NULL, NULL, NULL, NULL, NULL, type, addcut,
719  FALSE, result) );
720 
721  /* if it was not possible to generate a cut, this could be due to numerical issues. So the solution to the LP is
722  * resolved and the generation of the cut is reattempted. For NLPs, we do not have such a polishing yet.
723  */
724  if( (*result) == SCIP_DIDNOTFIND )
725  {
726  SCIP_Bool success;
727 
728  SCIPdebugMsg(scip, "Numerical trouble generating optimality cut for subproblem %d.\n", probnumber);
729 
730  if( !nlprelaxation )
731  {
732  SCIPdebugMsg(scip, "Attempting to polish the LP solution to find an alternative dual extreme point.\n");
733 
734  SCIP_CALL( polishSolution(subproblem, &success) );
735 
736  /* only attempt to generate a cut if the solution polishing was successful */
737  if( success )
738  {
739  SCIP_CALL( SCIPgenerateAndApplyBendersOptCut(scip, subproblem, benders, benderscut, sol, probnumber, cutname,
740  SCIPbendersGetSubproblemObjval(benders, probnumber), NULL, NULL, NULL, NULL, NULL, NULL, type, addcut,
741  FALSE, result) );
742  }
743  }
744  else
745  {
746  SCIP_Real multiplier = 0.01;
747 
748  SCIPdebugMsg(scip, "Attempting to resolve the NLP with a tighter feasibility tolerance to find an "
749  "alternative dual extreme point.\n");
750 
751  while( multiplier > 1e-06 && (*result) == SCIP_DIDNOTFIND )
752  {
753  SCIP_CALL( resolveNLPWithTighterFeastol(subproblem, multiplier, &success) );
754 
755  if( success )
756  {
757  SCIP_CALL( SCIPgenerateAndApplyBendersOptCut(scip, subproblem, benders, benderscut, sol, probnumber, cutname,
758  SCIPbendersGetSubproblemObjval(benders, probnumber), NULL, NULL, NULL, NULL, NULL, NULL, type, addcut,
759  FALSE, result) );
760  }
761 
762  multiplier *= 0.1;
763  }
764  }
765  }
766  }
767 
768  return SCIP_OKAY;
769 }
770 
771 
772 /*
773  * Benders' decomposition cuts specific interface methods
774  */
775 
776 /** creates the opt Benders' decomposition cuts and includes it in SCIP */
778  SCIP* scip, /**< SCIP data structure */
779  SCIP_BENDERS* benders /**< Benders' decomposition */
780  )
781 {
782  SCIP_BENDERSCUTDATA* benderscutdata;
783  SCIP_BENDERSCUT* benderscut;
785 
786  assert(benders != NULL);
787 
788  /* create opt Benders' decomposition cuts data */
789  SCIP_CALL( SCIPallocBlockMemory(scip, &benderscutdata) );
790 
791  benderscut = NULL;
792 
793  /* include Benders' decomposition cuts */
795  BENDERSCUT_PRIORITY, BENDERSCUT_LPCUT, benderscutExecOpt, benderscutdata) );
796 
797  assert(benderscut != NULL);
798 
799  /* setting the non fundamental callbacks via setter functions */
800  SCIP_CALL( SCIPsetBenderscutFree(scip, benderscut, benderscutFreeOpt) );
801 
802  /* add opt Benders' decomposition cuts parameters */
803  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/benderscut/%s/addcuts",
805  SCIP_CALL( SCIPaddBoolParam(scip, paramname,
806  "should cuts be generated and added to the cutpool instead of global constraints directly added to the problem.",
807  &benderscutdata->addcuts, FALSE, SCIP_DEFAULT_ADDCUTS, NULL, NULL) );
808 
809  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/benderscut/%s/mir",
811  SCIP_CALL( SCIPaddBoolParam(scip, paramname,
812  "should the mixed integer rounding procedure be applied to cuts",
813  &benderscutdata->calcmir, FALSE, SCIP_DEFAULT_CALCMIR, NULL, NULL) );
814 
815  return SCIP_OKAY;
816 }
817 
818 /** Generates a classical Benders' optimality cut using the dual solutions from the subproblem or the input arrays. If
819  * the dual solutions are input as arrays, then a mapping between the array indices and the rows/variables is required.
820  * As a cut strengthening approach, when an optimality cut is being generated (i.e. not for feasibility cuts) a MIR
821  * procedure is performed on the row. This procedure attempts to find a stronger constraint, if this doesn't happen,
822  * then the original constraint is added to SCIP.
823  *
824  * This method can also be used to generate a feasibility cut, if a problem to minimise the infeasibilities has been solved
825  * to generate the dual solutions
826  */
828  SCIP* masterprob, /**< the SCIP instance of the master problem */
829  SCIP* subproblem, /**< the SCIP instance of the pricing problem */
830  SCIP_BENDERS* benders, /**< the benders' decomposition */
831  SCIP_BENDERSCUT* benderscut, /**< the benders' decomposition cut method */
832  SCIP_SOL* sol, /**< primal CIP solution */
833  int probnumber, /**< the number of the pricing problem */
834  char* cutname, /**< the name for the cut to be generated */
835  SCIP_Real objective, /**< the objective function of the subproblem */
836  SCIP_Real* primalvals, /**< the primal solutions for the NLP, can be NULL */
837  SCIP_Real* consdualvals, /**< dual variables for the constraints, can be NULL */
838  SCIP_Real* varlbdualvals, /**< the dual variables for the variable lower bounds, can be NULL */
839  SCIP_Real* varubdualvals, /**< the dual variables for the variable upper bounds, can be NULL */
840  SCIP_HASHMAP* row2idx, /**< mapping between the row in the subproblem to the index in the dual array, can be NULL */
841  SCIP_HASHMAP* var2idx, /**< mapping from variable of the subproblem to the index in the dual arrays, can be NULL */
842  SCIP_BENDERSENFOTYPE type, /**< the enforcement type calling this function */
843  SCIP_Bool addcut, /**< should the Benders' cut be added as a cut or constraint */
844  SCIP_Bool feasibilitycut, /**< is this called for the generation of a feasibility cut */
845  SCIP_RESULT* result /**< the result from solving the subproblems */
846  )
847 {
848  SCIP_CONSHDLR* consbenders;
849  SCIP_CONS* cons;
850  SCIP_ROW* row;
851  SCIP_VAR** vars;
852  SCIP_Real* vals;
853  SCIP_Real lhs;
854  SCIP_Real rhs;
855  int nvars;
856  int varssize;
857  int nmastervars;
858  SCIP_Bool calcmir;
859  SCIP_Bool optimal;
860  SCIP_Bool success;
861  SCIP_Bool mirsuccess;
862 
863  SCIP_Real checkobj;
864  SCIP_Real verifyobj;
865 
866  assert(masterprob != NULL);
867  assert(subproblem != NULL);
868  assert(benders != NULL);
869  assert(benderscut != NULL);
870  assert(result != NULL);
871  assert((primalvals == NULL && consdualvals == NULL && varlbdualvals == NULL && varubdualvals == NULL
872  && row2idx == NULL && var2idx == NULL)
873  || (primalvals != NULL && consdualvals != NULL && varlbdualvals != NULL && varubdualvals != NULL
874  && row2idx != NULL && var2idx != NULL));
875 
876  row = NULL;
877  cons = NULL;
878 
879  calcmir = SCIPbenderscutGetData(benderscut)->calcmir && SCIPgetStage(masterprob) >= SCIP_STAGE_INITSOLVE && SCIPgetSubscipDepth(masterprob) == 0;
880  success = FALSE;
881  mirsuccess = FALSE;
882 
883  /* retrieving the Benders' decomposition constraint handler */
884  consbenders = SCIPfindConshdlr(masterprob, "benders");
885 
886  /* checking the optimality of the original problem with a comparison between the auxiliary variable and the
887  * objective value of the subproblem */
888  if( feasibilitycut )
889  optimal = FALSE;
890  else
891  {
892  SCIP_CALL( SCIPcheckBendersSubproblemOptimality(masterprob, benders, sol, probnumber, &optimal) );
893  }
894 
895  if( optimal )
896  {
897  (*result) = SCIP_FEASIBLE;
898  SCIPdebugMsg(masterprob, "No cut added for subproblem %d\n", probnumber);
899  return SCIP_OKAY;
900  }
901 
902  /* allocating memory for the variable and values arrays */
903  nmastervars = SCIPgetNVars(masterprob) + SCIPgetNFixedVars(masterprob);
904  SCIP_CALL( SCIPallocClearBufferArray(masterprob, &vars, nmastervars) );
905  SCIP_CALL( SCIPallocClearBufferArray(masterprob, &vals, nmastervars) );
906  lhs = 0.0;
907  rhs = SCIPinfinity(masterprob);
908  nvars = 0;
909  varssize = nmastervars;
910 
911  if( SCIPisNLPConstructed(subproblem) && SCIPgetNNlpis(subproblem) )
912  {
913  /* computing the coefficients of the optimality cut */
914  SCIP_CALL( computeStandardNLPOptimalityCut(masterprob, subproblem, benders, &vars, &vals, &lhs, &rhs, &nvars,
915  &varssize, objective, primalvals, consdualvals, varlbdualvals, varubdualvals, row2idx,
916  var2idx, &checkobj, &success) );
917  }
918  else
919  {
920  /* computing the coefficients of the optimality cut */
921  SCIP_CALL( computeStandardLPOptimalityCut(masterprob, subproblem, benders, &vars, &vals, &lhs, &rhs, &nvars,
922  &varssize, &checkobj, &success) );
923  }
924 
925  /* if success is FALSE, then there was an error in generating the optimality cut. No cut will be added to the master
926  * problem. Otherwise, the constraint is added to the master problem.
927  */
928  if( !success )
929  {
930  (*result) = SCIP_DIDNOTFIND;
931  SCIPdebugMsg(masterprob, "Error in generating Benders' optimality cut for problem %d.\n", probnumber);
932  }
933  else
934  {
935  /* initially a row/constraint is created for the optimality cut using the master variables and coefficients
936  * computed in computeStandardLPOptimalityCut. At this stage, the auxiliary variable is not added since the
937  * activity of the row/constraint in its current form is used to determine the validity of the optimality cut.
938  */
939  if( addcut )
940  {
941  SCIP_CALL( SCIPcreateEmptyRowConshdlr(masterprob, &row, consbenders, cutname, lhs, rhs, FALSE, FALSE, TRUE) );
942  SCIP_CALL( SCIPaddVarsToRow(masterprob, row, nvars, vars, vals) );
943  }
944  else
945  {
946  SCIP_CALL( SCIPcreateConsBasicLinear(masterprob, &cons, cutname, nvars, vars, vals, lhs, rhs) );
947  SCIP_CALL( SCIPsetConsDynamic(masterprob, cons, TRUE) );
948  SCIP_CALL( SCIPsetConsRemovable(masterprob, cons, TRUE) );
949  }
950 
951  /* computing the objective function from the cut activity to verify the accuracy of the constraint */
952  verifyobj = 0.0;
953  if( addcut )
954  {
955  verifyobj += SCIProwGetLhs(row) - SCIPgetRowSolActivity(masterprob, row, sol);
956  }
957  else
958  {
959  verifyobj += SCIPgetLhsLinear(masterprob, cons) - SCIPgetActivityLinear(masterprob, cons, sol);
960  }
961 
962  if( feasibilitycut && verifyobj < SCIPfeastol(masterprob) )
963  {
964  success = FALSE;
965  SCIPdebugMsg(masterprob, "The violation of the feasibility cut (%g) is too small. Skipping feasibility cut.\n", verifyobj);
966  }
967 
968  /* it is possible that numerics will cause the generated cut to be invalid. This cut should not be added to the
969  * master problem, since its addition could cut off feasible solutions. The success flag is set of false, indicating
970  * that the Benders' cut could not find a valid cut.
971  */
972  if( !feasibilitycut && !SCIPisFeasEQ(masterprob, checkobj, verifyobj) )
973  {
974  SCIP_Bool valid;
975 
976  /* the difference in the checkobj and verifyobj could be due to the setup tolerances. This is checked, and if
977  * so, then the generated cut is still valid
978  */
979  SCIP_CALL( checkSetupTolerances(masterprob, sol, vars, vals, lhs, checkobj, nvars, &valid) );
980 
981  if( !valid )
982  {
983  success = FALSE;
984  SCIPdebugMsg(masterprob, "The objective function and cut activity are not equal (%g != %g).\n", checkobj,
985  verifyobj);
986 
987 #ifdef SCIP_DEBUG
988  /* we only need to abort if cut strengthen is not used. If cut strengthen has been used in this round and the
989  * cut could not be generated, then another subproblem solving round will be executed
990  */
991  if( !SCIPbendersInStrengthenRound(benders) )
992  {
993 #ifdef SCIP_MOREDEBUG
994  int i;
995 
996  for( i = 0; i < nvars; i++ )
997  printf("<%s> %g %g\n", SCIPvarGetName(vars[i]), vals[i], SCIPgetSolVal(masterprob, sol, vars[i]));
998 #endif
999  SCIPABORT();
1000  }
1001 #endif
1002  }
1003  }
1004 
1005  if( success )
1006  {
1007  /* adding the auxiliary variable to the optimality cut. The auxiliary variable is added to the vars and vals
1008  * arrays prior to the execution of the MIR procedure. This is necessary because the MIR procedure must be
1009  * executed on the complete cut, not just the row/constraint without the auxiliary variable.
1010  */
1011  if( !feasibilitycut )
1012  {
1013  SCIP_CALL( addAuxiliaryVariableToCut(masterprob, benders, vars, vals, &nvars, probnumber) );
1014  }
1015 
1016  /* performing the MIR procedure. If the procedure is successful, then the vars and vals arrays are no longer
1017  * needed for creating the optimality cut. These are superseeded with the cutcoefs and cutinds arrays. In the
1018  * case that the MIR procedure is successful, the row/constraint that has been created previously is destroyed
1019  * and the MIR cut is added in its place
1020  */
1021  if( calcmir )
1022  {
1023  SCIP_Real* cutcoefs;
1024  int* cutinds;
1025  SCIP_Real cutrhs;
1026  int cutnnz;
1027 
1028  /* allocating memory to compute the MIR cut */
1029  SCIP_CALL( SCIPallocBufferArray(masterprob, &cutcoefs, nvars) );
1030  SCIP_CALL( SCIPallocBufferArray(masterprob, &cutinds, nvars) );
1031 
1032  SCIP_CALL( computeMIRForOptimalityCut(masterprob, sol, vars, vals, lhs, rhs, nvars, cutcoefs,
1033  cutinds, &cutrhs, &cutnnz, &mirsuccess) );
1034 
1035  /* if the MIR cut was computed successfully, then the current row/constraint needs to be destroyed and
1036  * replaced with the updated coefficients
1037  */
1038  if( mirsuccess )
1039  {
1040  SCIP_VAR** mastervars;
1041  int i;
1042 
1043  mastervars = SCIPgetVars(masterprob);
1044 
1045  if( addcut )
1046  {
1047  SCIP_CALL( SCIPreleaseRow(masterprob, &row) );
1048 
1049  SCIP_CALL( SCIPcreateEmptyRowConshdlr(masterprob, &row, consbenders, cutname,
1050  -SCIPinfinity(masterprob), cutrhs, FALSE, FALSE, TRUE) );
1051 
1052  for( i = 0; i < cutnnz; i++)
1053  {
1054  SCIP_CALL( SCIPaddVarToRow(masterprob, row, mastervars[cutinds[i]], cutcoefs[i]) );
1055  }
1056  }
1057  else
1058  {
1059  SCIP_CALL( SCIPreleaseCons(masterprob, &cons) );
1060 
1061  SCIP_CALL( SCIPcreateConsBasicLinear(masterprob, &cons, cutname, 0, NULL, NULL,
1062  -SCIPinfinity(masterprob), cutrhs) );
1063  SCIP_CALL( SCIPsetConsDynamic(masterprob, cons, TRUE) );
1064  SCIP_CALL( SCIPsetConsRemovable(masterprob, cons, TRUE) );
1065 
1066  for( i = 0; i < cutnnz; i++ )
1067  {
1068  SCIP_CALL( SCIPaddCoefLinear(masterprob, cons, mastervars[cutinds[i]], cutcoefs[i]) );
1069  }
1070  }
1071  }
1072 
1073  /* freeing the memory required to compute the MIR cut */
1074  SCIPfreeBufferArray(masterprob, &cutinds);
1075  SCIPfreeBufferArray(masterprob, &cutcoefs);
1076  }
1077 
1078  /* adding the constraint to the master problem */
1079  if( addcut )
1080  {
1081  SCIP_Bool infeasible;
1082 
1083  /* adding the auxiliary variable coefficient to the row. This is only added if the MIR procedure is not
1084  * successful. If the MIR procedure was successful, then the auxiliary variable is already included in the
1085  * row
1086  */
1087  if( !feasibilitycut && !mirsuccess )
1088  {
1089  SCIP_CALL( SCIPaddVarToRow(masterprob, row, vars[nvars - 1], vals[nvars - 1]) );
1090  }
1091 
1092  if( type == SCIP_BENDERSENFOTYPE_LP || type == SCIP_BENDERSENFOTYPE_RELAX )
1093  {
1094  SCIP_CALL( SCIPaddRow(masterprob, row, FALSE, &infeasible) );
1095  assert(!infeasible);
1096  }
1097  else
1098  {
1099  assert(type == SCIP_BENDERSENFOTYPE_CHECK || type == SCIP_BENDERSENFOTYPE_PSEUDO);
1100  SCIP_CALL( SCIPaddPoolCut(masterprob, row) );
1101  }
1102 
1103  (*result) = SCIP_SEPARATED;
1104  }
1105  else
1106  {
1107  /* adding the auxiliary variable coefficient to the row. This is only added if the MIR procedure is not
1108  * successful. If the MIR procedure was successful, then the auxiliary variable is already included in the
1109  * constraint.
1110  */
1111  if( !feasibilitycut && !mirsuccess )
1112  {
1113  SCIP_CALL( SCIPaddCoefLinear(masterprob, cons, vars[nvars - 1], vals[nvars - 1]) );
1114  }
1115 
1116  SCIPdebugPrintCons(masterprob, cons, NULL);
1117 
1118  SCIP_CALL( SCIPaddCons(masterprob, cons) );
1119 
1120  (*result) = SCIP_CONSADDED;
1121  }
1122 
1123  /* storing the data that is used to create the cut */
1124  SCIP_CALL( SCIPstoreBendersCut(masterprob, benders, vars, vals, lhs, rhs, nvars) );
1125  }
1126  else
1127  {
1128  (*result) = SCIP_DIDNOTFIND;
1129  SCIPdebugMsg(masterprob, "Error in generating Benders' %s cut for problem %d.\n", feasibilitycut ? "feasibility" : "optimality", probnumber);
1130  }
1131 
1132  /* releasing the row or constraint */
1133  if( addcut )
1134  {
1135  /* release the row */
1136  SCIP_CALL( SCIPreleaseRow(masterprob, &row) );
1137  }
1138  else
1139  {
1140  /* release the constraint */
1141  SCIP_CALL( SCIPreleaseCons(masterprob, &cons) );
1142  }
1143  }
1144 
1145  SCIPfreeBufferArray(masterprob, &vals);
1146  SCIPfreeBufferArray(masterprob, &vars);
1147 
1148  return SCIP_OKAY;
1149 }
1150 
1151 
1152 /** adds the gradient of a nonlinear row in the current NLP solution of a subproblem to a linear row or constraint in the master problem
1153  *
1154  * Only computes gradient w.r.t. master problem variables.
1155  * Computes also the directional derivative, that is, mult times gradient times solution.
1156  */
1158  SCIP* masterprob, /**< the SCIP instance of the master problem */
1159  SCIP* subproblem, /**< the SCIP instance of the subproblem */
1160  SCIP_BENDERS* benders, /**< the benders' decomposition structure */
1161  SCIP_NLROW* nlrow, /**< nonlinear row */
1162  SCIP_Real mult, /**< multiplier */
1163  SCIP_Real* primalvals, /**< the primal solutions for the NLP, can be NULL */
1164  SCIP_HASHMAP* var2idx, /**< mapping from variable of the subproblem to the index in the dual arrays, can be NULL */
1165  SCIP_Real* dirderiv, /**< storage to add directional derivative */
1166  SCIP_VAR*** vars, /**< pointer to array of variables in the generated cut with non-zero coefficient */
1167  SCIP_Real** vals, /**< pointer to array of coefficients of the variables in the generated cut */
1168  int* nvars, /**< the number of variables in the cut */
1169  int* varssize /**< the number of variables in the array */
1170  )
1171 {
1172  SCIP_EXPR* expr;
1173  SCIP_VAR* var;
1174  SCIP_VAR* mastervar;
1175  SCIP_Real coef;
1176  int i;
1177 
1178  assert(masterprob != NULL);
1179  assert(subproblem != NULL);
1180  assert(benders != NULL);
1181  assert(nlrow != NULL);
1182  assert((primalvals == NULL && var2idx == NULL) || (primalvals != NULL && var2idx != NULL));
1183  assert(mult != 0.0);
1184  assert(dirderiv != NULL);
1185  assert(vars != NULL);
1186  assert(vals != NULL);
1187 
1188  /* linear part */
1189  for( i = 0; i < SCIPnlrowGetNLinearVars(nlrow); i++ )
1190  {
1191  var = SCIPnlrowGetLinearVars(nlrow)[i];
1192  assert(var != NULL);
1193 
1194  /* retrieving the master problem variable for the given subproblem variable. */
1195  SCIP_CALL( SCIPgetBendersMasterVar(masterprob, benders, var, &mastervar) );
1196  if( mastervar == NULL )
1197  continue;
1198 
1199  coef = mult * SCIPnlrowGetLinearCoefs(nlrow)[i];
1200 
1201  /* adding the variable to the storage */
1202  SCIP_CALL( addVariableToArray(masterprob, vars, vals, mastervar, coef, nvars, varssize) );
1203 
1204  *dirderiv += coef * getNlpVarSol(var, primalvals, var2idx);
1205  }
1206 
1207  /* expression part */
1208  expr = SCIPnlrowGetExpr(nlrow);
1209  if( expr != NULL )
1210  {
1211  SCIP_SOL* primalsol;
1212  SCIP_EXPRITER* it;
1213 
1214  /* create primalsol, either from primalvals, or pointing to NLP solution */
1215  if( primalvals != NULL )
1216  {
1217  SCIP_CALL( SCIPcreateSol(subproblem, &primalsol, NULL) );
1218 
1219  /* TODO would be better to change primalvals to a SCIP_SOL and do this once for the whole NLP instead of repeating it for each expr */
1220  for( i = 0; i < SCIPhashmapGetNEntries(var2idx); ++i )
1221  {
1222  SCIP_HASHMAPENTRY* entry;
1223  entry = SCIPhashmapGetEntry(var2idx, i);
1224  if( entry == NULL )
1225  continue;
1226  SCIP_CALL( SCIPsetSolVal(subproblem, primalsol, (SCIP_VAR*) SCIPhashmapEntryGetOrigin(entry), primalvals[SCIPhashmapEntryGetImageInt(entry)]) );
1227  }
1228  }
1229  else
1230  {
1231  SCIP_CALL( SCIPcreateNLPSol(subproblem, &primalsol, NULL) );
1232  }
1233 
1234  /* eval gradient */
1235  SCIP_CALL( SCIPevalExprGradient(subproblem, expr, primalsol, 0L) );
1236 
1237  assert(SCIPexprGetDerivative(expr) != SCIP_INVALID); /* TODO this should be a proper check&abort */ /*lint !e777*/
1238 
1239  SCIP_CALL( SCIPfreeSol(subproblem, &primalsol) );
1240 
1241  /* update corresponding gradient entry */
1242  SCIP_CALL( SCIPcreateExpriter(subproblem, &it) );
1244  for( ; !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) ) /*lint !e441*/ /*lint !e440*/
1245  {
1246  if( !SCIPisExprVar(subproblem, expr) )
1247  continue;
1248 
1249  var = SCIPgetVarExprVar(expr);
1250  assert(var != NULL);
1251 
1252  /* retrieving the master problem variable for the given subproblem variable. */
1253  SCIP_CALL( SCIPgetBendersMasterVar(masterprob, benders, var, &mastervar) );
1254  if( mastervar == NULL )
1255  continue;
1256 
1257  assert(SCIPexprGetDerivative(expr) != SCIP_INVALID); /*lint !e777*/
1258  coef = mult * SCIPexprGetDerivative(expr);
1259 
1260  /* adding the variable to the storage */
1261  SCIP_CALL( addVariableToArray(masterprob, vars, vals, mastervar, coef, nvars, varssize) );
1262 
1263  *dirderiv += coef * getNlpVarSol(var, primalvals, var2idx);
1264  }
1265  SCIPfreeExpriter(&it);
1266  }
1267 
1268  return SCIP_OKAY;
1269 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
Definition: scip_lp.c:596
SCIP_Real SCIPgetActivityLinear(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
int SCIPgetNNLPNlRows(SCIP *scip)
Definition: scip_nlp.c:332
void SCIPaggrRowFree(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition: cuts.c:1686
const char * SCIPbenderscutGetName(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:483
SCIP_RETCODE SCIPexpriterInit(SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_TYPE type, SCIP_Bool allowrevisit)
Definition: expriter.c:491
enum SCIP_NlpTermStat SCIP_NLPTERMSTAT
Definition: type_nlpi.h:185
SCIP_Real SCIPfeastol(SCIP *scip)
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)
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip_nlp.c:101
SCIP_Real SCIPbendersGetSubproblemObjval(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6170
internal miscellaneous methods for linear constraints
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
#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)
SCIP_Real opttol
Definition: type_nlpi.h:61
struct SCIP_BenderscutData SCIP_BENDERSCUTDATA
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:117
SCIP_BENDERSCUTDATA * SCIPbenderscutGetData(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:394
SCIP_RETCODE SCIPgetBendersMasterVar(SCIP *scip, SCIP_BENDERS *benders, SCIP_VAR *var, SCIP_VAR **mappedvar)
Definition: scip_benders.c:651
#define SCIP_MAXSTRLEN
Definition: def.h:293
const char * SCIPbendersGetName(SCIP_BENDERS *benders)
Definition: benders.c:5895
#define SCIP_DEFAULT_CALCMIR
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:130
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1686
SCIP_Real SCIPgetVarRedcost(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1861
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17966
SCIP_NLPSOLSTAT SCIPgetNLPSolstat(SCIP *scip)
Definition: scip_nlp.c:532
SCIP_Real feastol
Definition: type_nlpi.h:60
void SCIPbenderscutSetData(SCIP_BENDERSCUT *benderscut, SCIP_BENDERSCUTDATA *benderscutdata)
Definition: benderscut.c:404
void * SCIPhashmapEntryGetOrigin(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3500
SCIP_VAR ** SCIPnlrowGetLinearVars(SCIP_NLROW *nlrow)
Definition: nlp.c:1774
SCIP_Real SCIPvarGetSol(SCIP_VAR *var, SCIP_Bool getlpval)
Definition: var.c:13256
static SCIP_Real getNlpVarSol(SCIP_VAR *var, SCIP_Real *primalvals, SCIP_HASHMAP *var2idx)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17225
#define FALSE
Definition: def.h:87
public methods for Benders&#39; decomposition
int SCIPgetSubscipDepth(SCIP *scip)
Definition: scip_copy.c:2591
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE
Definition: type_benders.h:42
Generates a standard Benders&#39; decomposition optimality cut.
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17600
int SCIPnlrowGetNLinearVars(SCIP_NLROW *nlrow)
Definition: nlp.c:1764
static SCIP_RETCODE addVariableToArray(SCIP *masterprob, SCIP_VAR ***vars, SCIP_Real **vals, SCIP_VAR *addvar, SCIP_Real addval, int *nvars, int *varssize)
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
#define BENDERSCUT_PRIORITY
static SCIP_RETCODE computeStandardNLPOptimalityCut(SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_VAR ***vars, SCIP_Real **vals, SCIP_Real *lhs, SCIP_Real *rhs, int *nvars, int *varssize, SCIP_Real objective, SCIP_Real *primalvals, SCIP_Real *consdualvals, SCIP_Real *varlbdualvals, SCIP_Real *varubdualvals, SCIP_HASHMAP *row2idx, SCIP_HASHMAP *var2idx, SCIP_Real *checkobj, SCIP_Bool *success)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:93
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
Definition: lp.c:17245
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_Longint SCIPbenderscutGetNFound(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:534
SCIP_RETCODE SCIPevalExprGradient(SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag)
Definition: scip_expr.c:1656
#define BENDERSCUT_NAME
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
public functions to work with algebraic expressions
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3363
int SCIPgetNNlpis(SCIP *scip)
Definition: scip_nlpi.c:190
int SCIPgetNFixedVars(SCIP *scip)
Definition: scip_prob.c:2307
SCIP_VAR ** SCIPgetFixedVars(SCIP *scip)
Definition: scip_prob.c:2264
int SCIPgetNNLPVars(SCIP *scip)
Definition: scip_nlp.c:192
SCIP_NLPTERMSTAT SCIPgetNLPTermstat(SCIP *scip)
Definition: scip_nlp.c:554
#define BENDERSCUT_DESC
SCIP_RETCODE SCIPsetConsRemovable(SCIP *scip, SCIP_CONS *cons, SCIP_Bool removable)
Definition: scip_cons.c:1411
static SCIP_RETCODE computeStandardLPOptimalityCut(SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_VAR ***vars, SCIP_Real **vals, SCIP_Real *lhs, SCIP_Real *rhs, int *nvars, int *varssize, SCIP_Real *checkobj, SCIP_Bool *success)
#define SCIPerrorMessage
Definition: pub_message.h:55
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2768
SCIP_Real SCIPexprGetDerivative(SCIP_EXPR *expr)
Definition: expr.c:3898
int SCIPhashmapGetNEntries(SCIP_HASHMAP *hashmap)
Definition: misc.c:3481
SCIP_HASHMAPENTRY * SCIPhashmapGetEntry(SCIP_HASHMAP *hashmap, int entryidx)
Definition: misc.c:3489
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
enum SCIP_NlpSolStat SCIP_NLPSOLSTAT
Definition: type_nlpi.h:159
SCIP_VAR * SCIPgetVarExprVar(SCIP_EXPR *expr)
Definition: expr_var.c:403
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip_cut.c:126
SCIP_RETCODE SCIPsetConsDynamic(SCIP *scip, SCIP_CONS *cons, SCIP_Bool dynamic)
Definition: scip_cons.c:1386
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17251
static SCIP_RETCODE addAuxiliaryVariableToCut(SCIP *masterprob, SCIP_BENDERS *benders, SCIP_VAR **vars, SCIP_Real *vals, int *nvars, int probnumber)
SCIP_Real SCIPnlrowGetDualsol(SCIP_NLROW *nlrow)
Definition: nlp.c:1876
#define NULL
Definition: lpi_spx1.cpp:155
#define REALABS(x)
Definition: def.h:201
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:260
int SCIPgetNLPRows(SCIP *scip)
Definition: scip_lp.c:617
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:810
SCIP_NLROW ** SCIPgetNLPNlRows(SCIP *scip)
Definition: scip_nlp.c:310
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17235
static SCIP_RETCODE checkSetupTolerances(SCIP *masterprob, SCIP_SOL *sol, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real checkobj, int nvars, SCIP_Bool *valid)
SCIP_RETCODE SCIPaggrRowAddCustomCons(SCIP *scip, SCIP_AGGRROW *aggrrow, int *inds, SCIP_Real *vals, int len, SCIP_Real rhs, SCIP_Real weight, int rank, SCIP_Bool local)
Definition: cuts.c:2004
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:241
SCIP_RETCODE SCIPcreateExpriter(SCIP *scip, SCIP_EXPRITER **iterator)
Definition: scip_expr.c:2300
public methods for NLP management
SCIP_RETCODE SCIPstoreBendersCut(SCIP *scip, SCIP_BENDERS *benders, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, int nvars)
SCIP_RETCODE SCIPgenerateAndApplyBendersOptCut(SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_BENDERSCUT *benderscut, SCIP_SOL *sol, int probnumber, char *cutname, SCIP_Real objective, SCIP_Real *primalvals, SCIP_Real *consdualvals, SCIP_Real *varlbdualvals, SCIP_Real *varubdualvals, SCIP_HASHMAP *row2idx, SCIP_HASHMAP *var2idx, SCIP_BENDERSENFOTYPE type, SCIP_Bool addcut, SCIP_Bool feasibilitycut, SCIP_RESULT *result)
SCIP_RETCODE SCIPcalcMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real scale, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
Definition: cuts.c:3792
static SCIP_RETCODE polishSolution(SCIP *subproblem, SCIP_Bool *success)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1212
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:84
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
SCIP_Bool SCIPcutsTightenCoefficients(SCIP *scip, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, int *nchgcoefs)
Definition: cuts.c:1462
static const char * paramname[]
Definition: lpi_msk.c:4998
SCIP_RETCODE SCIPaddNlRowGradientBenderscutOpt(SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_NLROW *nlrow, SCIP_Real mult, SCIP_Real *primalvals, SCIP_HASHMAP *var2idx, SCIP_Real *dirderiv, SCIP_VAR ***vars, SCIP_Real **vals, int *nvars, int *varssize)
SCIP_Real SCIPvarGetNLPSol(SCIP_VAR *var)
Definition: var.c:18297
SCIP_RETCODE SCIPcalcFlowCover(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool allowlocal, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
Definition: cuts.c:7329
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:352
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:478
SCIP_Real SCIPvarGetUnchangedObj(SCIP_VAR *var)
Definition: var.c:17768
public methods for LP management
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:976
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17758
static SCIP_RETCODE computeMIRForOptimalityCut(SCIP *masterprob, SCIP_SOL *sol, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, int nvars, SCIP_Real *cutcoefs, int *cutinds, SCIP_Real *cutrhs, int *cutnnz, SCIP_Bool *success)
SCIP_EXPR * SCIPexpriterGetNext(SCIP_EXPRITER *iterator)
Definition: expriter.c:848
SCIP * SCIPbendersSubproblem(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:5949
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:2129
SCIP_RETCODE SCIPcheckBendersSubproblemOptimality(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol, int probnumber, SCIP_Bool *optimal)
Definition: scip_benders.c:883
int SCIPbendersGetNSubproblems(SCIP_BENDERS *benders)
Definition: benders.c:5939
SCIP_Real SCIPgetTransObjscale(SCIP *scip)
Definition: scip_prob.c:1388
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:88
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1990
void SCIPfreeExpriter(SCIP_EXPRITER **iterator)
Definition: scip_expr.c:2314
public methods for Benders&#39; decomposition cuts
SCIP_Real * SCIPnlrowGetLinearCoefs(SCIP_NLROW *nlrow)
Definition: nlp.c:1784
SCIP_RETCODE SCIPsolveNLPParam(SCIP *scip, SCIP_NLPPARAM param)
Definition: scip_nlp.c:503
SCIP_Bool SCIPhasNLPSolution(SCIP *scip)
Definition: scip_nlp.c:629
SCIP_Bool SCIPbendersInStrengthenRound(SCIP_BENDERS *benders)
Definition: benders.c:6418
SCIP_Real SCIPgetTransObjoffset(SCIP *scip)
Definition: scip_prob.c:1365
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1553
#define SCIP_DEFAULT_ADDCUTS
SCIP_RETCODE SCIPcreateNLPSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:389
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_BENDERSCUTFREE(benderscutFreeOpt)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
static SCIP_RETCODE resolveNLPWithTighterFeastol(SCIP *subproblem, SCIP_Real multiplier, SCIP_Bool *success)
public methods for message output
SCIP_RETCODE SCIPincludeBenderscutOpt(SCIP *scip, SCIP_BENDERS *benders)
SCIP_Bool SCIPisExprVar(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1421
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1945
#define SCIP_NLPPARAM_DEFAULT(scip)
Definition: type_nlpi.h:117
#define SCIP_Real
Definition: def.h:177
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_lp.c:1712
#define SCIP_INVALID
Definition: def.h:197
int SCIPhashmapEntryGetImageInt(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3520
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition: cuts.c:1654
static SCIP_DECL_BENDERSCUTEXEC(benderscutExecOpt)
SCIP_RETCODE SCIPsetBenderscutFree(SCIP *scip, SCIP_BENDERSCUT *benderscut, SCIP_DECL_BENDERSCUTFREE((*benderscutfree)))
SCIP_OBJSENSE SCIPgetObjsense(SCIP *scip)
Definition: scip_prob.c:1223
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
SCIP_Bool SCIPexpriterIsEnd(SCIP_EXPRITER *iterator)
Definition: expriter.c:959
SCIPallocBlockMemory(scip, subsol))
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3221
SCIP_RETCODE SCIPcreateEmptyRowConshdlr(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1382
SCIP_VAR * SCIPbendersGetAuxiliaryVar(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6131
#define SCIPABORT()
Definition: def.h:356
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetNLPVars(SCIP *scip)
Definition: scip_nlp.c:170
SCIP callable library.
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
SCIP_EXPR * SCIPnlrowGetExpr(SCIP_NLROW *nlrow)
Definition: nlp.c:1794
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:319
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:119
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1766