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-2020 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 "nlpi/exprinterpret.h"
25 #include "nlpi/pub_expr.h"
26 #include "scip/benderscut_opt.h"
27 #include "scip/cons_linear.h"
28 #include "scip/pub_benderscut.h"
29 #include "scip/pub_benders.h"
30 #include "scip/pub_lp.h"
31 #include "scip/pub_nlp.h"
32 #include "scip/pub_message.h"
33 #include "scip/pub_misc.h"
34 #include "scip/pub_misc_linear.h"
35 #include "scip/pub_var.h"
36 #include "scip/scip.h"
37 #include <string.h>
38 
39 #define BENDERSCUT_NAME "optimality"
40 #define BENDERSCUT_DESC "Standard Benders' decomposition optimality cut"
41 #define BENDERSCUT_PRIORITY 5000
42 #define BENDERSCUT_LPCUT TRUE
43 
44 #define SCIP_DEFAULT_ADDCUTS FALSE /** Should cuts be generated, instead of constraints */
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 };
55 
56 
57 /*
58  * Local methods
59  */
60 
61 /** in the case of numerical troubles, the LP is resolved with solution polishing activated */
62 static
64  SCIP* subproblem, /**< the SCIP data structure */
65  SCIP_Bool* success /**< TRUE is the resolving of the LP was successful */
66  )
67 {
68  int oldpolishing;
69  SCIP_Bool lperror;
70  SCIP_Bool cutoff;
71 
72  assert(subproblem != NULL);
73  assert(SCIPinProbing(subproblem));
74 
75  (*success) = FALSE;
76 
77  /* setting the solution polishing parameter */
78  SCIP_CALL( SCIPgetIntParam(subproblem, "lp/solutionpolishing", &oldpolishing) );
79  SCIP_CALL( SCIPsetIntParam(subproblem, "lp/solutionpolishing", 2) );
80 
81  /* resolving the probing LP */
82  SCIP_CALL( SCIPsolveProbingLP(subproblem, -1, &lperror, &cutoff) );
83 
84  if( SCIPgetLPSolstat(subproblem) == SCIP_LPSOLSTAT_OPTIMAL )
85  (*success) = TRUE;
86 
87  /* resetting the solution polishing parameter */
88  SCIP_CALL( SCIPsetIntParam(subproblem, "lp/solutionpolishing", oldpolishing) );
89 
90  return SCIP_OKAY;
91 }
92 
93 /** verifying the activity of the cut when master variables are within epsilon of their upper or lower bounds
94  *
95  * When setting up the Benders' decomposition subproblem, master variables taking values that are within epsilon
96  * greater than their upper bound or less than their lower bound are set to their upper and lower bounds respectively.
97  * As such, there can be a difference between the subproblem dual solution objective and the optimality cut activity,
98  * when computed using the master problem solution directly. This check is to verify whether this difference is an
99  * actual error or due to the violation of the upper and lower bounds when setting up the Benders' decomposition
100  * subproblem.
101  */
102 static
104  SCIP* masterprob, /**< the SCIP data structure */
105  SCIP_SOL* sol, /**< the master problem solution */
106  SCIP_VAR** vars, /**< pointer to array of variables in the generated cut with non-zero coefficient */
107  SCIP_Real* vals, /**< pointer to array of coefficients of the variables in the generated cut */
108  SCIP_Real lhs, /**< the left hand side of the cut */
109  SCIP_Real checkobj, /**< the objective of the subproblem computed from the dual solution */
110  int nvars, /**< the number of variables in the cut */
111  SCIP_Bool* valid /**< returns true is the cut is valid */
112  )
113 {
114  SCIP_Real verifyobj;
115  int i;
116 
117  assert(masterprob != NULL);
118  assert(vars != NULL);
119  assert(vals != NULL);
120 
121  /* initialising the verify objective with the left hand side of the optimality cut */
122  verifyobj = lhs;
123 
124  /* computing the activity of the cut from the master solution and the constraint values */
125  for( i = 0; i < nvars; i++ )
126  {
127  SCIP_Real solval;
128 
129  solval = SCIPgetSolVal(masterprob, sol, vars[i]);
130 
131  /* checking whether the solution value is less than or greater than the variable bounds */
132  if( !SCIPisLT(masterprob, solval, SCIPvarGetUbLocal(vars[i])) )
133  solval = SCIPvarGetUbLocal(vars[i]);
134  else if( !SCIPisGT(masterprob, solval, SCIPvarGetLbLocal(vars[i])) )
135  solval = SCIPvarGetLbLocal(vars[i]);
136 
137  verifyobj -= solval*vals[i];
138  }
139 
140  (*valid) = SCIPisFeasEQ(masterprob, checkobj, verifyobj);
141 
142  return SCIP_OKAY;
143 }
144 
145 /** when solving NLP subproblems, numerical issues are addressed by tightening the feasibility tolerance */
146 static
148  SCIP* subproblem, /**< the SCIP data structure */
149  SCIP_Real multiplier, /**< the amount by which to decrease the tolerance */
150  SCIP_Bool* success /**< TRUE is the resolving of the LP was successful */
151  )
152 {
153  SCIP_NLPSOLSTAT nlpsolstat;
154 #ifdef SCIP_DEBUG
155  SCIP_NLPTERMSTAT nlptermstat;
156 #endif
157 #ifdef SCIP_MOREDEBUG
158  SCIP_SOL* nlpsol;
159 #endif
160  SCIP_Real feastol;
161  SCIP_Real objtol;
162 
163  assert(subproblem != NULL);
164  assert(SCIPinProbing(subproblem));
165 
166  (*success) = FALSE;
167 
168 #ifdef SCIP_MOREDEBUG
170 #endif
171 
172  SCIP_CALL( SCIPsetNLPIntPar(subproblem, SCIP_NLPPAR_ITLIM, INT_MAX) );
173 
174  /* getting the feasibility tolerance currently used for the NLP */
175  SCIP_CALL( SCIPgetNLPRealPar(subproblem, SCIP_NLPPAR_FEASTOL, &feastol) );
176  SCIP_CALL( SCIPgetNLPRealPar(subproblem, SCIP_NLPPAR_RELOBJTOL, &objtol) );
177 
178  /* setting the feasibility tolerance to 0.01x the current tolerance */
179  SCIP_CALL( SCIPsetNLPRealPar(subproblem, SCIP_NLPPAR_FEASTOL, feastol*multiplier) );
180  SCIP_CALL( SCIPsetNLPRealPar(subproblem, SCIP_NLPPAR_RELOBJTOL, objtol*multiplier) );
181 
182  SCIP_CALL( SCIPsolveNLP(subproblem) );
183 
184  nlpsolstat = SCIPgetNLPSolstat(subproblem);
185 #ifdef SCIP_DEBUG
186  nlptermstat = SCIPgetNLPTermstat(subproblem);
187  SCIPdebugMsg(subproblem, "NLP solstat %d termstat %d\n", nlpsolstat, nlptermstat);
188 #endif
189 
190  if( nlpsolstat == SCIP_NLPSOLSTAT_LOCOPT || nlpsolstat == SCIP_NLPSOLSTAT_GLOBOPT
191  || nlpsolstat == SCIP_NLPSOLSTAT_FEASIBLE )
192  {
193 #ifdef SCIP_MOREDEBUG
194  SCIP_CALL( SCIPcreateNLPSol(subproblem, &nlpsol, NULL) );
195  SCIP_CALL( SCIPprintSol(subproblem, nlpsol, NULL, FALSE) );
196  SCIP_CALL( SCIPfreeSol(subproblem, &nlpsol) );
197 #endif
198 
199  (*success) = TRUE;
200  }
201 
202  /* resetting the feasibility tolerance to 0.01x the current tolerance */
203  SCIP_CALL( SCIPsetNLPRealPar(subproblem, SCIP_NLPPAR_FEASTOL, feastol) );
204 
205  return SCIP_OKAY;
206 }
207 
208 /** adds a variable and value to the constraint/row arrays */
209 static
211  SCIP* masterprob, /**< the SCIP instance of the master problem */
212  SCIP_VAR*** vars, /**< pointer to the array of variables in the generated cut with non-zero coefficient */
213  SCIP_Real** vals, /**< pointer to the array of coefficients of the variables in the generated cut */
214  SCIP_VAR* addvar, /**< the variable that will be added to the array */
215  SCIP_Real addval, /**< the value that will be added to the array */
216  int* nvars, /**< the number of variables in the variable array */
217  int* varssize /**< the length of the variable size */
218  )
219 {
220  assert(masterprob != NULL);
221  assert(vars != NULL);
222  assert(*vars != NULL);
223  assert(vals != NULL);
224  assert(*vals != NULL);
225  assert(addvar != NULL);
226  assert(nvars != NULL);
227  assert(varssize != NULL);
228 
229  if( *nvars >= *varssize )
230  {
231  *varssize = SCIPcalcMemGrowSize(masterprob, *varssize + 1);
232  SCIP_CALL( SCIPreallocBufferArray(masterprob, vars, *varssize) );
233  SCIP_CALL( SCIPreallocBufferArray(masterprob, vals, *varssize) );
234  }
235  assert(*nvars < *varssize);
236 
237  (*vars)[*nvars] = addvar;
238  (*vals)[*nvars] = addval;
239  (*nvars)++;
240 
241  return SCIP_OKAY;
242 }
243 
244 /** returns the variable solution either from the NLP or from the primal vals array */
245 static
247  SCIP_VAR* var, /**< the variable for which the solution is requested */
248  SCIP_Real* primalvals, /**< the primal solutions for the NLP, can be NULL */
249  SCIP_HASHMAP* var2idx /**< mapping from variable of the subproblem to the index in the dual arrays, can be NULL */
250  )
251 {
252  SCIP_Real varsol;
253  int idx;
254 
255  assert(var != NULL);
256  assert((primalvals == NULL && var2idx == NULL) || (primalvals != NULL && var2idx != NULL));
257 
258  if( var2idx != NULL && primalvals != NULL )
259  {
260  assert(SCIPhashmapExists(var2idx, (void*)var) );
261  idx = SCIPhashmapGetImageInt(var2idx, (void*)var);
262  varsol = primalvals[idx];
263  }
264  else
265  varsol = SCIPvarGetNLPSol(var);
266 
267  return varsol;
268 }
269 
270 /** computes a standard Benders' optimality cut from the dual solutions of the LP */
271 static
273  SCIP* masterprob, /**< the SCIP instance of the master problem */
274  SCIP* subproblem, /**< the SCIP instance of the subproblem */
275  SCIP_BENDERS* benders, /**< the benders' decomposition structure */
276  SCIP_VAR*** vars, /**< pointer to array of variables in the generated cut with non-zero coefficient */
277  SCIP_Real** vals, /**< pointer to array of coefficients of the variables in the generated cut */
278  SCIP_Real* lhs, /**< the left hand side of the cut */
279  SCIP_Real* rhs, /**< the right hand side of the cut */
280  int* nvars, /**< the number of variables in the cut */
281  int* varssize, /**< the number of variables in the array */
282  SCIP_Real* checkobj, /**< stores the objective function computed from the dual solution */
283  SCIP_Bool* success /**< was the cut generation successful? */
284  )
285 {
286  SCIP_VAR** subvars;
287  SCIP_VAR** fixedvars;
288  int nsubvars;
289  int nfixedvars;
290  SCIP_Real dualsol;
291  SCIP_Real addval;
292  int nrows;
293  int i;
294 
295  (*checkobj) = 0;
296 
297  assert(masterprob != NULL);
298  assert(subproblem != NULL);
299  assert(benders != NULL);
300  assert(vars != NULL);
301  assert(*vars != NULL);
302  assert(vals != NULL);
303  assert(*vals != NULL);
304 
305  (*success) = FALSE;
306 
307  /* looping over all LP rows and setting the coefficients of the cut */
308  nrows = SCIPgetNLPRows(subproblem);
309  for( i = 0; i < nrows; i++ )
310  {
311  SCIP_ROW* lprow;
312 
313  lprow = SCIPgetLPRows(subproblem)[i];
314  assert(lprow != NULL);
315 
316  dualsol = SCIProwGetDualsol(lprow);
317  assert( !SCIPisInfinity(subproblem, dualsol) && !SCIPisInfinity(subproblem, -dualsol) );
318 
319  if( SCIPisZero(subproblem, dualsol) )
320  continue;
321 
322  if( dualsol > 0.0 )
323  addval = dualsol*SCIProwGetLhs(lprow);
324  else
325  addval = dualsol*SCIProwGetRhs(lprow);
326 
327  (*lhs) += addval;
328 
329  /* if the bound becomes infinite, then the cut generation terminates. */
330  if( SCIPisInfinity(masterprob, (*lhs)) || SCIPisInfinity(masterprob, -(*lhs))
331  || SCIPisInfinity(masterprob, addval) || SCIPisInfinity(masterprob, -addval))
332  {
333  (*success) = FALSE;
334  SCIPdebugMsg(masterprob, "Infinite bound when generating optimality cut. lhs = %g addval = %g.\n", (*lhs), addval);
335  return SCIP_OKAY;
336  }
337  }
338 
339  nsubvars = SCIPgetNVars(subproblem);
340  subvars = SCIPgetVars(subproblem);
341  nfixedvars = SCIPgetNFixedVars(subproblem);
342  fixedvars = SCIPgetFixedVars(subproblem);
343 
344  /* looping over all variables to update the coefficients in the computed cut. */
345  for( i = 0; i < nsubvars + nfixedvars; i++ )
346  {
347  SCIP_VAR* var;
348  SCIP_VAR* mastervar;
349  SCIP_Real redcost;
350 
351  if( i < nsubvars )
352  var = subvars[i];
353  else
354  var = fixedvars[i - nsubvars];
355 
356  /* retrieving the master problem variable for the given subproblem variable. */
357  SCIP_CALL( SCIPgetBendersMasterVar(masterprob, benders, var, &mastervar) );
358 
359  redcost = SCIPgetVarRedcost(subproblem, var);
360 
361  (*checkobj) += SCIPvarGetUnchangedObj(var)*SCIPvarGetSol(var, TRUE);
362 
363  /* checking whether the subproblem variable has a corresponding master variable. */
364  if( mastervar != NULL )
365  {
366  SCIP_Real coef;
367 
368  coef = -1.0*(SCIPvarGetObj(var) + redcost);
369 
370  if( !SCIPisZero(masterprob, coef) )
371  {
372  /* adding the variable to the storage */
373  SCIP_CALL( addVariableToArray(masterprob, vars, vals, mastervar, coef, nvars, varssize) );
374  }
375  }
376  else
377  {
378  if( !SCIPisZero(subproblem, redcost) )
379  {
380  addval = 0;
381 
382  if( SCIPisPositive(subproblem, redcost) )
383  addval = redcost*SCIPvarGetLbLocal(var);
384  else if( SCIPisNegative(subproblem, redcost) )
385  addval = redcost*SCIPvarGetUbLocal(var);
386 
387  (*lhs) += addval;
388 
389  /* if the bound becomes infinite, then the cut generation terminates. */
390  if( SCIPisInfinity(masterprob, (*lhs)) || SCIPisInfinity(masterprob, -(*lhs))
391  || SCIPisInfinity(masterprob, addval) || SCIPisInfinity(masterprob, -addval))
392  {
393  (*success) = FALSE;
394  SCIPdebugMsg(masterprob, "Infinite bound when generating optimality cut.\n");
395  return SCIP_OKAY;
396  }
397  }
398  }
399  }
400 
401  assert(SCIPisInfinity(masterprob, (*rhs)));
402  /* the rhs should be infinite. If it changes, then there is an error */
403  if( !SCIPisInfinity(masterprob, (*rhs)) )
404  {
405  (*success) = FALSE;
406  SCIPdebugMsg(masterprob, "RHS is not infinite. rhs = %g.\n", (*rhs));
407  return SCIP_OKAY;
408  }
409 
410  (*success) = TRUE;
411 
412  return SCIP_OKAY;
413 }
414 
415 /** computes a standard Benders' optimality cut from the dual solutions of the NLP */
416 static
418  SCIP* masterprob, /**< the SCIP instance of the master problem */
419  SCIP* subproblem, /**< the SCIP instance of the subproblem */
420  SCIP_BENDERS* benders, /**< the benders' decomposition structure */
421  SCIP_VAR*** vars, /**< pointer to array of variables in the generated cut with non-zero coefficient */
422  SCIP_Real** vals, /**< pointer to array of coefficients of the variables in the generated cut */
423  SCIP_Real* lhs, /**< the left hand side of the cut */
424  SCIP_Real* rhs, /**< the right hand side of the cut */
425  int* nvars, /**< the number of variables in the cut */
426  int* varssize, /**< the number of variables in the array */
427  SCIP_Real objective, /**< the objective function of the subproblem */
428  SCIP_Real* primalvals, /**< the primal solutions for the NLP, can be NULL */
429  SCIP_Real* consdualvals, /**< dual variables for the constraints, can be NULL */
430  SCIP_Real* varlbdualvals, /**< the dual variables for the variable lower bounds, can be NULL */
431  SCIP_Real* varubdualvals, /**< the dual variables for the variable upper bounds, can be NULL */
432  SCIP_HASHMAP* row2idx, /**< mapping between the row in the subproblem to the index in the dual array, can be NULL */
433  SCIP_HASHMAP* var2idx, /**< mapping from variable of the subproblem to the index in the dual arrays, can be NULL */
434  SCIP_Real* checkobj, /**< stores the objective function computed from the dual solution */
435  SCIP_Bool* success /**< was the cut generation successful? */
436  )
437 {
438  SCIP_EXPRINT* exprinterpreter;
439  SCIP_VAR** subvars;
440  SCIP_VAR** fixedvars;
441  int nsubvars;
442  int nfixedvars;
443  SCIP_Real dirderiv;
444  SCIP_Real dualsol;
445  int nrows;
446  int idx;
447  int i;
448 
449  (*checkobj) = 0;
450 
451  assert(masterprob != NULL);
452  assert(subproblem != NULL);
453  assert(benders != NULL);
454  assert(SCIPisNLPConstructed(subproblem));
455  assert(SCIPgetNLPSolstat(subproblem) <= SCIP_NLPSOLSTAT_FEASIBLE || consdualvals != NULL);
456  assert(SCIPhasNLPSolution(subproblem) || consdualvals != NULL);
457 
458  (*success) = FALSE;
459 
460  if( !(primalvals == NULL && consdualvals == NULL && varlbdualvals == NULL && varubdualvals == NULL
461  && row2idx == NULL && var2idx == NULL)
462  && !(primalvals != NULL && consdualvals != NULL && varlbdualvals != NULL && varubdualvals != NULL
463  && row2idx != NULL && var2idx != NULL) )
464  {
465  SCIPerrorMessage("The optimality cut must generated from either a SCIP instance or all of the dual solutions and indices must be supplied");
466  (*success) = FALSE;
467 
468  return SCIP_ERROR;
469  }
470 
471  nsubvars = SCIPgetNNLPVars(subproblem);
472  subvars = SCIPgetNLPVars(subproblem);
473  nfixedvars = SCIPgetNFixedVars(subproblem);
474  fixedvars = SCIPgetFixedVars(subproblem);
475 
476  /* our optimality cut implementation assumes that SCIP did not modify the objective function and sense,
477  * that is, that the objective function value of the NLP corresponds to the value of the auxiliary variable
478  * if that wouldn't be the case, then the scaling and offset may have to be considered when adding the
479  * auxiliary variable to the cut (cons/row)?
480  */
481  assert(SCIPgetTransObjoffset(subproblem) == 0.0);
482  assert(SCIPgetTransObjscale(subproblem) == 1.0);
483  assert(SCIPgetObjsense(subproblem) == SCIP_OBJSENSE_MINIMIZE);
484 
485  (*lhs) = objective;
486  assert(!SCIPisInfinity(subproblem, REALABS(*lhs)));
487 
488  (*rhs) = SCIPinfinity(masterprob);
489 
490  dirderiv = 0.0;
491 
492  SCIP_CALL( SCIPexprintCreate(SCIPblkmem(subproblem), &exprinterpreter) );
493 
494  /* looping over all NLP rows and setting the corresponding coefficients of the cut */
495  nrows = SCIPgetNNLPNlRows(subproblem);
496  for( i = 0; i < nrows; i++ )
497  {
498  SCIP_NLROW* nlrow;
499 
500  nlrow = SCIPgetNLPNlRows(subproblem)[i];
501  assert(nlrow != NULL);
502 
503  if( row2idx != NULL && consdualvals != NULL )
504  {
505  assert(SCIPhashmapExists(row2idx, (void*)nlrow) );
506  idx = SCIPhashmapGetImageInt(row2idx, (void*)nlrow);
507  dualsol = consdualvals[idx];
508  }
509  else
510  dualsol = SCIPnlrowGetDualsol(nlrow);
511  assert( !SCIPisInfinity(subproblem, dualsol) && !SCIPisInfinity(subproblem, -dualsol) );
512 
513  if( SCIPisZero(subproblem, dualsol) )
514  continue;
515 
516  SCIP_CALL( SCIPaddNlRowGradientBenderscutOpt(masterprob, subproblem, benders, nlrow, exprinterpreter,
517  -dualsol, primalvals, var2idx, &dirderiv, vars, vals, nvars, varssize) );
518  }
519 
520  SCIP_CALL( SCIPexprintFree(&exprinterpreter) );
521 
522  /* looping over all variable bounds and updating the corresponding coefficients of the cut; compute checkobj */
523  for( i = 0; i < nsubvars; i++ )
524  {
525  SCIP_VAR* var;
526  SCIP_VAR* mastervar;
527  SCIP_Real coef;
528 
529  var = subvars[i];
530 
531  (*checkobj) += SCIPvarGetObj(var) * getNlpVarSol(var, primalvals, var2idx);
532 
533  /* retrieving the master problem variable for the given subproblem variable. */
534  SCIP_CALL( SCIPgetBendersMasterVar(masterprob, benders, var, &mastervar) );
535 
536  if( var2idx != NULL && varubdualvals != NULL && varlbdualvals != NULL )
537  {
538  assert(SCIPhashmapExists(var2idx, (void*)var) );
539  idx = SCIPhashmapGetImageInt(var2idx, (void*)var);
540  dualsol = varubdualvals[idx] - varlbdualvals[idx];
541  }
542  else
543  dualsol = SCIPgetNLPVarsUbDualsol(subproblem)[i] - SCIPgetNLPVarsLbDualsol(subproblem)[i];
544 
545  /* checking whether the subproblem variable has a corresponding master variable. */
546  if( mastervar == NULL || dualsol == 0.0 )
547  continue;
548 
549  coef = -dualsol;
550 
551  /* adding the variable to the storage */
552  SCIP_CALL( addVariableToArray(masterprob, vars, vals, mastervar, coef, nvars, varssize) );
553 
554  dirderiv += coef * getNlpVarSol(var, primalvals, var2idx);
555  }
556 
557  for( i = 0; i < nfixedvars; i++ )
558  *checkobj += SCIPvarGetUnchangedObj(fixedvars[i]) * getNlpVarSol(fixedvars[i], primalvals, var2idx);
559 
560  *lhs += dirderiv;
561 
562  /* if the side became infinite or dirderiv was infinite, then the cut generation terminates. */
563  if( SCIPisInfinity(masterprob, *lhs) || SCIPisInfinity(masterprob, -*lhs)
564  || SCIPisInfinity(masterprob, dirderiv) || SCIPisInfinity(masterprob, -dirderiv))
565  {
566  (*success) = FALSE;
567  SCIPdebugMsg(masterprob, "Infinite bound when generating optimality cut. lhs = %g dirderiv = %g.\n", lhs, dirderiv);
568  return SCIP_OKAY;
569  }
570 
571  (*success) = TRUE;
572 
573  return SCIP_OKAY;
574 }
575 
576 
577 /** Adds the auxiliary variable to the generated cut. If this is the first optimality cut for the subproblem, then the
578  * auxiliary variable is first created and added to the master problem.
579  */
580 static
582  SCIP* masterprob, /**< the SCIP instance of the master problem */
583  SCIP_BENDERS* benders, /**< the benders' decomposition structure */
584  SCIP_VAR** vars, /**< the variables in the generated cut with non-zero coefficient */
585  SCIP_Real* vals, /**< the coefficients of the variables in the generated cut */
586  int* nvars, /**< the number of variables in the cut */
587  int probnumber /**< the number of the pricing problem */
588  )
589 {
590  SCIP_VAR* auxiliaryvar;
591 
592  assert(masterprob != NULL);
593  assert(benders != NULL);
594  assert(vars != NULL);
595  assert(vals != NULL);
596 
597  auxiliaryvar = SCIPbendersGetAuxiliaryVar(benders, probnumber);
598 
599  vars[(*nvars)] = auxiliaryvar;
600  vals[(*nvars)] = 1.0;
601  (*nvars)++;
602 
603  return SCIP_OKAY;
604 }
605 
606 
607 /*
608  * Callback methods of Benders' decomposition cuts
609  */
610 
611 /** destructor of Benders' decomposition cuts to free user data (called when SCIP is exiting) */
612 static
613 SCIP_DECL_BENDERSCUTFREE(benderscutFreeOpt)
614 { /*lint --e{715}*/
615  SCIP_BENDERSCUTDATA* benderscutdata;
616 
617  assert( benderscut != NULL );
618  assert( strcmp(SCIPbenderscutGetName(benderscut), BENDERSCUT_NAME) == 0 );
619 
620  /* free Benders' cut data */
621  benderscutdata = SCIPbenderscutGetData(benderscut);
622  assert( benderscutdata != NULL );
623 
624  SCIPfreeBlockMemory(scip, &benderscutdata);
625 
626  SCIPbenderscutSetData(benderscut, NULL);
627 
628  return SCIP_OKAY;
629 }
630 
631 
632 /** execution method of Benders' decomposition cuts */
633 static
634 SCIP_DECL_BENDERSCUTEXEC(benderscutExecOpt)
635 { /*lint --e{715}*/
636  SCIP* subproblem;
637  SCIP_BENDERSCUTDATA* benderscutdata;
638  SCIP_Bool nlprelaxation;
639  SCIP_Bool addcut;
640  char cutname[SCIP_MAXSTRLEN];
641 
642  assert(scip != NULL);
643  assert(benders != NULL);
644  assert(benderscut != NULL);
645  assert(result != NULL);
646  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
647 
648  /* retrieving the Benders' cut data */
649  benderscutdata = SCIPbenderscutGetData(benderscut);
650 
651  /* if the cuts are generated prior to the solving stage, then rows can not be generated. So constraints must be
652  * added to the master problem.
653  */
655  addcut = FALSE;
656  else
657  addcut = benderscutdata->addcuts;
658 
659  /* setting the name of the generated cut */
660  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "optimalitycut_%d_%d", probnumber,
661  SCIPbenderscutGetNFound(benderscut) );
662 
663  subproblem = SCIPbendersSubproblem(benders, probnumber);
664 
665  if( subproblem == NULL )
666  {
667  SCIPdebugMsg(scip, "The subproblem %d is set to NULL. The <%s> Benders' decomposition cut can not be executed.\n",
668  probnumber, BENDERSCUT_NAME);
669 
670  (*result) = SCIP_DIDNOTRUN;
671  return SCIP_OKAY;
672  }
673 
674  /* setting a flag to indicate whether the NLP relaxation should be used to generate cuts */
675  nlprelaxation = SCIPisNLPConstructed(subproblem) && SCIPgetNNlpis(subproblem);
676 
677  /* only generate optimality cuts if the subproblem LP or NLP is optimal,
678  * since we use the dual solution of the LP/NLP to construct the optimality cut
679  */
680  if( SCIPgetStage(subproblem) == SCIP_STAGE_SOLVING &&
681  ((!nlprelaxation && SCIPgetLPSolstat(subproblem) == SCIP_LPSOLSTAT_OPTIMAL) ||
682  (nlprelaxation && SCIPgetNLPSolstat(subproblem) <= SCIP_NLPSOLSTAT_FEASIBLE)) )
683  {
684  /* generating a cut for a given subproblem */
685  SCIP_CALL( SCIPgenerateAndApplyBendersOptCut(scip, subproblem, benders, benderscut, sol, probnumber, cutname,
686  SCIPbendersGetSubproblemObjval(benders, probnumber), NULL, NULL, NULL, NULL, NULL, NULL, type, addcut,
687  FALSE, result) );
688 
689  /* if it was not possible to generate a cut, this could be due to numerical issues. So the solution to the LP is
690  * resolved and the generation of the cut is reattempted. For NLPs, we do not have such a polishing yet.
691  */
692  if( (*result) == SCIP_DIDNOTFIND )
693  {
694  SCIP_Bool success;
695 
696  SCIPdebugMsg(scip, "Numerical trouble generating optimality cut for subproblem %d.", probnumber);
697 
698  if( !nlprelaxation )
699  {
700  SCIPdebugMsg(scip, "Attempting to polish the LP solution to find an alternative dual extreme point.\n");
701 
702  SCIP_CALL( polishSolution(subproblem, &success) );
703 
704  /* only attempt to generate a cut if the solution polishing was successful */
705  if( success )
706  {
707  SCIP_CALL( SCIPgenerateAndApplyBendersOptCut(scip, subproblem, benders, benderscut, sol, probnumber, cutname,
708  SCIPbendersGetSubproblemObjval(benders, probnumber), NULL, NULL, NULL, NULL, NULL, NULL, type, addcut,
709  FALSE, result) );
710  }
711  }
712  else
713  {
714  SCIP_Real multiplier = 0.01;
715 
716  SCIPdebugMsg(scip, "Attempting to resolve the NLP with a tighter feasibility tolerance to find an "
717  "alternative dual extreme point.\n");
718 
719  while( multiplier > 1e-06 && (*result) == SCIP_DIDNOTFIND )
720  {
721  SCIP_CALL( resolveNLPWithTighterFeastol(subproblem, multiplier, &success) );
722 
723  if( success )
724  {
725  SCIP_CALL( SCIPgenerateAndApplyBendersOptCut(scip, subproblem, benders, benderscut, sol, probnumber, cutname,
726  SCIPbendersGetSubproblemObjval(benders, probnumber), NULL, NULL, NULL, NULL, NULL, NULL, type, addcut,
727  FALSE, result) );
728  }
729 
730  multiplier *= 0.1;
731  }
732  }
733  }
734  }
735 
736  return SCIP_OKAY;
737 }
738 
739 
740 /*
741  * Benders' decomposition cuts specific interface methods
742  */
743 
744 /** creates the opt Benders' decomposition cuts and includes it in SCIP */
746  SCIP* scip, /**< SCIP data structure */
747  SCIP_BENDERS* benders /**< Benders' decomposition */
748  )
749 {
750  SCIP_BENDERSCUTDATA* benderscutdata;
751  SCIP_BENDERSCUT* benderscut;
753 
754  assert(benders != NULL);
755 
756  /* create opt Benders' decomposition cuts data */
757  SCIP_CALL( SCIPallocBlockMemory(scip, &benderscutdata) );
758 
759  benderscut = NULL;
760 
761  /* include Benders' decomposition cuts */
763  BENDERSCUT_PRIORITY, BENDERSCUT_LPCUT, benderscutExecOpt, benderscutdata) );
764 
765  assert(benderscut != NULL);
766 
767  /* setting the non fundamental callbacks via setter functions */
768  SCIP_CALL( SCIPsetBenderscutFree(scip, benderscut, benderscutFreeOpt) );
769 
770  /* add opt Benders' decomposition cuts parameters */
771  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/benderscut/%s/addcuts",
773  SCIP_CALL( SCIPaddBoolParam(scip, paramname,
774  "should cuts be generated and added to the cutpool instead of global constraints directly added to the problem.",
775  &benderscutdata->addcuts, FALSE, SCIP_DEFAULT_ADDCUTS, NULL, NULL) );
776 
777  return SCIP_OKAY;
778 }
779 
780 /** Generates a classical Benders' optimality cut using the dual solutions from the subproblem or the input arrays. If
781  * the dual solutions are input as arrays, then a mapping between the array indices and the rows/variables is required.
782  * This method can also be used to generate a feasibility cut, if a problem to minimise the infeasibilities has been solved
783  * to generate the dual solutions
784  */
786  SCIP* masterprob, /**< the SCIP instance of the master problem */
787  SCIP* subproblem, /**< the SCIP instance of the pricing problem */
788  SCIP_BENDERS* benders, /**< the benders' decomposition */
789  SCIP_BENDERSCUT* benderscut, /**< the benders' decomposition cut method */
790  SCIP_SOL* sol, /**< primal CIP solution */
791  int probnumber, /**< the number of the pricing problem */
792  char* cutname, /**< the name for the cut to be generated */
793  SCIP_Real objective, /**< the objective function of the subproblem */
794  SCIP_Real* primalvals, /**< the primal solutions for the NLP, can be NULL */
795  SCIP_Real* consdualvals, /**< dual variables for the constraints, can be NULL */
796  SCIP_Real* varlbdualvals, /**< the dual variables for the variable lower bounds, can be NULL */
797  SCIP_Real* varubdualvals, /**< the dual variables for the variable upper bounds, can be NULL */
798  SCIP_HASHMAP* row2idx, /**< mapping between the row in the subproblem to the index in the dual array, can be NULL */
799  SCIP_HASHMAP* var2idx, /**< mapping from variable of the subproblem to the index in the dual arrays, can be NULL */
800  SCIP_BENDERSENFOTYPE type, /**< the enforcement type calling this function */
801  SCIP_Bool addcut, /**< should the Benders' cut be added as a cut or constraint */
802  SCIP_Bool feasibilitycut, /**< is this called for the generation of a feasibility cut */
803  SCIP_RESULT* result /**< the result from solving the subproblems */
804  )
805 {
806  SCIP_CONSHDLR* consbenders;
807  SCIP_CONS* cons;
808  SCIP_ROW* row;
809  SCIP_VAR** vars;
810  SCIP_Real* vals;
811  SCIP_Real lhs;
812  SCIP_Real rhs;
813  int nvars;
814  int varssize;
815  int nmastervars;
816  SCIP_Bool optimal;
817  SCIP_Bool success;
818 
819  SCIP_Real checkobj;
820  SCIP_Real verifyobj;
821 
822  assert(masterprob != NULL);
823  assert(subproblem != NULL);
824  assert(benders != NULL);
825  assert(benderscut != NULL);
826  assert(result != NULL);
827  assert((primalvals == NULL && consdualvals == NULL && varlbdualvals == NULL && varubdualvals == NULL
828  && row2idx == NULL && var2idx == NULL)
829  || (primalvals != NULL && consdualvals != NULL && varlbdualvals != NULL && varubdualvals != NULL
830  && row2idx != NULL && var2idx != NULL));
831 
832  row = NULL;
833  cons = NULL;
834 
835  /* retrieving the Benders' decomposition constraint handler */
836  consbenders = SCIPfindConshdlr(masterprob, "benders");
837 
838  /* checking the optimality of the original problem with a comparison between the auxiliary variable and the
839  * objective value of the subproblem */
840  if( feasibilitycut )
841  optimal = FALSE;
842  else
843  {
844  SCIP_CALL( SCIPcheckBendersSubproblemOptimality(masterprob, benders, sol, probnumber, &optimal) );
845  }
846 
847  if( optimal )
848  {
849  (*result) = SCIP_FEASIBLE;
850  SCIPdebugMsg(masterprob, "No cut added for subproblem %d\n", probnumber);
851  return SCIP_OKAY;
852  }
853 
854  /* allocating memory for the variable and values arrays */
855  nmastervars = SCIPgetNVars(masterprob) + SCIPgetNFixedVars(masterprob);
856  SCIP_CALL( SCIPallocClearBufferArray(masterprob, &vars, nmastervars) );
857  SCIP_CALL( SCIPallocClearBufferArray(masterprob, &vals, nmastervars) );
858  lhs = 0.0;
859  rhs = SCIPinfinity(masterprob);
860  nvars = 0;
861  varssize = nmastervars;
862 
863  if( SCIPisNLPConstructed(subproblem) && SCIPgetNNlpis(subproblem) )
864  {
865  /* computing the coefficients of the optimality cut */
866  SCIP_CALL( computeStandardNLPOptimalityCut(masterprob, subproblem, benders, &vars, &vals, &lhs, &rhs, &nvars,
867  &varssize, objective, primalvals, consdualvals, varlbdualvals, varubdualvals, row2idx,
868  var2idx, &checkobj, &success) );
869  }
870  else
871  {
872  /* computing the coefficients of the optimality cut */
873  SCIP_CALL( computeStandardLPOptimalityCut(masterprob, subproblem, benders, &vars, &vals, &lhs, &rhs, &nvars,
874  &varssize, &checkobj, &success) );
875  }
876 
877  /* if success is FALSE, then there was an error in generating the optimality cut. No cut will be added to the master
878  * problem. Otherwise, the constraint is added to the master problem.
879  */
880  if( !success )
881  {
882  (*result) = SCIP_DIDNOTFIND;
883  SCIPdebugMsg(masterprob, "Error in generating Benders' optimality cut for problem %d.\n", probnumber);
884  }
885  else
886  {
887  /* creating an empty row or constraint for the Benders' cut */
888  if( addcut )
889  {
890  SCIP_CALL( SCIPcreateEmptyRowConshdlr(masterprob, &row, consbenders, cutname, lhs, rhs, FALSE, FALSE, TRUE) );
891  SCIP_CALL( SCIPaddVarsToRow(masterprob, row, nvars, vars, vals) );
892  }
893  else
894  {
895  SCIP_CALL( SCIPcreateConsBasicLinear(masterprob, &cons, cutname, nvars, vars, vals, lhs, rhs) );
896  SCIP_CALL( SCIPsetConsDynamic(masterprob, cons, TRUE) );
897  SCIP_CALL( SCIPsetConsRemovable(masterprob, cons, TRUE) );
898  }
899 
900  /* computing the objective function from the cut activity to verify the accuracy of the constraint */
901  verifyobj = 0.0;
902  if( addcut )
903  {
904  verifyobj += SCIProwGetLhs(row) - SCIPgetRowSolActivity(masterprob, row, sol);
905  }
906  else
907  {
908  verifyobj += SCIPgetLhsLinear(masterprob, cons) - SCIPgetActivityLinear(masterprob, cons, sol);
909  }
910 
911  /* it is possible that numerics will cause the generated cut to be invalid. This cut should not be added to the
912  * master problem, since its addition could cut off feasible solutions. The success flag is set of false, indicating
913  * that the Benders' cut could not find a valid cut.
914  */
915  if( !feasibilitycut && !SCIPisFeasEQ(masterprob, checkobj, verifyobj) )
916  {
917  SCIP_Bool valid;
918 
919  /* the difference in the checkobj and verifyobj could be due to the setup tolerances. This is checked, and if
920  * so, then the generated cut is still valid
921  */
922  SCIP_CALL( checkSetupTolerances(masterprob, sol, vars, vals, lhs, checkobj, nvars, &valid) );
923 
924  if( !valid )
925  {
926  success = FALSE;
927  SCIPdebugMsg(masterprob, "The objective function and cut activity are not equal (%g != %g).\n", checkobj,
928  verifyobj);
929 
930 #ifdef SCIP_DEBUG
931  /* we only need to abort if cut strengthen is not used. If cut strengthen has been used in this round and the
932  * cut could not be generated, then another subproblem solving round will be executed
933  */
934  if( !SCIPbendersInStrengthenRound(benders) )
935  {
936 #ifdef SCIP_MOREDEBUG
937  int i;
938 
939  for( i = 0; i < nvars; i++ )
940  printf("<%s> %g %g\n", SCIPvarGetName(vars[i]), vals[i], SCIPgetSolVal(masterprob, sol, vars[i]));
941 #endif
942  SCIPABORT();
943  }
944 #endif
945  }
946  }
947 
948  if( success )
949  {
950  /* adding the auxiliary variable to the optimality cut */
951  if( !feasibilitycut )
952  {
953  SCIP_CALL( addAuxiliaryVariableToCut(masterprob, benders, vars, vals, &nvars, probnumber) );
954  }
955 
956  /* adding the constraint to the master problem */
957  if( addcut )
958  {
959  SCIP_Bool infeasible;
960 
961  /* adding the auxiliary variable coefficient to the row */
962  if( !feasibilitycut )
963  {
964  SCIP_CALL( SCIPaddVarToRow(masterprob, row, vars[nvars - 1], vals[nvars - 1]) );
965  }
966 
967  if( type == SCIP_BENDERSENFOTYPE_LP || type == SCIP_BENDERSENFOTYPE_RELAX )
968  {
969  SCIP_CALL( SCIPaddRow(masterprob, row, FALSE, &infeasible) );
970  assert(!infeasible);
971  }
972  else
973  {
974  assert(type == SCIP_BENDERSENFOTYPE_CHECK || type == SCIP_BENDERSENFOTYPE_PSEUDO);
975  SCIP_CALL( SCIPaddPoolCut(masterprob, row) );
976  }
977 
978  (*result) = SCIP_SEPARATED;
979  }
980  else
981  {
982  /* adding the auxiliary variable coefficient to the constraint */
983  if( !feasibilitycut )
984  {
985  SCIP_CALL( SCIPaddCoefLinear(masterprob, cons, vars[nvars - 1], vals[nvars - 1]) );
986  }
987 
988  SCIPdebugPrintCons(masterprob, cons, NULL);
989 
990  SCIP_CALL( SCIPaddCons(masterprob, cons) );
991 
992  (*result) = SCIP_CONSADDED;
993  }
994 
995  /* storing the data that is used to create the cut */
996  SCIP_CALL( SCIPstoreBendersCut(masterprob, benders, vars, vals, lhs, rhs, nvars) );
997  }
998  else
999  {
1000  (*result) = SCIP_DIDNOTFIND;
1001  SCIPdebugMsg(masterprob, "Error in generating Benders' optimality cut for problem %d.\n", probnumber);
1002  }
1003 
1004  /* releasing the row or constraint */
1005  if( addcut )
1006  {
1007  /* release the row */
1008  SCIP_CALL( SCIPreleaseRow(masterprob, &row) );
1009  }
1010  else
1011  {
1012  /* release the constraint */
1013  SCIP_CALL( SCIPreleaseCons(masterprob, &cons) );
1014  }
1015  }
1016 
1017  SCIPfreeBufferArray(masterprob, &vals);
1018  SCIPfreeBufferArray(masterprob, &vars);
1019 
1020  return SCIP_OKAY;
1021 }
1022 
1023 
1024 /** 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
1025  *
1026  * Only computes gradient w.r.t. master problem variables.
1027  * Computes also the directional derivative, that is, mult times gradient times solution.
1028  */
1030  SCIP* masterprob, /**< the SCIP instance of the master problem */
1031  SCIP* subproblem, /**< the SCIP instance of the subproblem */
1032  SCIP_BENDERS* benders, /**< the benders' decomposition structure */
1033  SCIP_NLROW* nlrow, /**< nonlinear row */
1034  SCIP_EXPRINT* exprint, /**< expressions interpreter */
1035  SCIP_Real mult, /**< multiplier */
1036  SCIP_Real* primalvals, /**< the primal solutions for the NLP, can be NULL */
1037  SCIP_HASHMAP* var2idx, /**< mapping from variable of the subproblem to the index in the dual arrays, can be NULL */
1038  SCIP_Real* dirderiv, /**< storage to add directional derivative */
1039  SCIP_VAR*** vars, /**< pointer to array of variables in the generated cut with non-zero coefficient */
1040  SCIP_Real** vals, /**< pointer to array of coefficients of the variables in the generated cut */
1041  int* nvars, /**< the number of variables in the cut */
1042  int* varssize /**< the number of variables in the array */
1043  )
1044 {
1045  SCIP_EXPRTREE* tree;
1046  SCIP_VAR* var;
1047  SCIP_VAR* mastervar;
1048  SCIP_Real coef;
1049  int i;
1050 
1051  assert(masterprob != NULL);
1052  assert(subproblem != NULL);
1053  assert(benders != NULL);
1054  assert(nlrow != NULL);
1055  assert(exprint != NULL);
1056  assert((primalvals == NULL && var2idx == NULL) || (primalvals != NULL && var2idx != NULL));
1057  assert(mult != 0.0);
1058  assert(dirderiv != NULL);
1059  assert(vars != NULL);
1060  assert(vals != NULL);
1061 
1062  /* linear part */
1063  for( i = 0; i < SCIPnlrowGetNLinearVars(nlrow); i++ )
1064  {
1065  var = SCIPnlrowGetLinearVars(nlrow)[i];
1066  assert(var != NULL);
1067 
1068  /* retrieving the master problem variable for the given subproblem variable. */
1069  SCIP_CALL( SCIPgetBendersMasterVar(masterprob, benders, var, &mastervar) );
1070  if( mastervar == NULL )
1071  continue;
1072 
1073  coef = mult * SCIPnlrowGetLinearCoefs(nlrow)[i];
1074 
1075  /* adding the variable to the storage */
1076  SCIP_CALL( addVariableToArray(masterprob, vars, vals, mastervar, coef, nvars, varssize) );
1077 
1078  *dirderiv += coef * getNlpVarSol(var, primalvals, var2idx);
1079  }
1080 
1081  /* quadratic part */
1082  for( i = 0; i < SCIPnlrowGetNQuadElems(nlrow); i++ )
1083  {
1084  SCIP_VAR* var1;
1085  SCIP_VAR* var2;
1086  SCIP_VAR* mastervar1;
1087  SCIP_VAR* mastervar2;
1088  SCIP_Real coef1;
1089  SCIP_Real coef2;
1090 
1091  assert(SCIPnlrowGetQuadElems(nlrow)[i].idx1 < SCIPnlrowGetNQuadVars(nlrow));
1092  assert(SCIPnlrowGetQuadElems(nlrow)[i].idx2 < SCIPnlrowGetNQuadVars(nlrow));
1093 
1094  var1 = SCIPnlrowGetQuadVars(nlrow)[SCIPnlrowGetQuadElems(nlrow)[i].idx1];
1095  var2 = SCIPnlrowGetQuadVars(nlrow)[SCIPnlrowGetQuadElems(nlrow)[i].idx2];
1096 
1097  /* retrieving the master problem variables for the given subproblem variables. */
1098  SCIP_CALL( SCIPgetBendersMasterVar(masterprob, benders, var1, &mastervar1) );
1099  SCIP_CALL( SCIPgetBendersMasterVar(masterprob, benders, var2, &mastervar2) );
1100 
1101  coef1 = mult * SCIPnlrowGetQuadElems(nlrow)[i].coef * getNlpVarSol(var2, primalvals, var2idx);
1102  coef2 = mult * SCIPnlrowGetQuadElems(nlrow)[i].coef * getNlpVarSol(var1, primalvals, var2idx);
1103 
1104  /* adding the variable to the storage */
1105  if( mastervar1 != NULL )
1106  {
1107  SCIP_CALL( addVariableToArray(masterprob, vars, vals, mastervar1, coef1, nvars, varssize) );
1108  }
1109  if( mastervar2 != NULL )
1110  {
1111  SCIP_CALL( addVariableToArray(masterprob, vars, vals, mastervar2, coef2, nvars, varssize) );
1112  }
1113 
1114  if( mastervar1 != NULL )
1115  *dirderiv += coef1 * getNlpVarSol(var1, primalvals, var2idx);
1116 
1117  if( mastervar2 != NULL )
1118  *dirderiv += coef2 * getNlpVarSol(var2, primalvals, var2idx);
1119  }
1120 
1121  /* tree part */
1122  tree = SCIPnlrowGetExprtree(nlrow);
1123  if( tree != NULL )
1124  {
1125  SCIP_Real* treegrad;
1126  SCIP_Real* x;
1127  SCIP_Real val;
1128 
1129  SCIP_CALL( SCIPallocBufferArray(subproblem, &x, SCIPexprtreeGetNVars(tree)) );
1130  SCIP_CALL( SCIPallocBufferArray(subproblem, &treegrad, SCIPexprtreeGetNVars(tree)) );
1131 
1132  /* compile expression tree, if not done before */
1133  if( SCIPexprtreeGetInterpreterData(tree) == NULL )
1134  {
1135  SCIP_CALL( SCIPexprintCompile(exprint, tree) );
1136  }
1137 
1138  /* sets the solution value */
1139  for( i = 0; i < SCIPexprtreeGetNVars(tree); ++i )
1140  x[i] = getNlpVarSol(SCIPexprtreeGetVars(tree)[i], primalvals, var2idx);
1141 
1142  SCIP_CALL( SCIPexprintGrad(exprint, tree, x, TRUE, &val, treegrad) );
1143 
1144  /* update corresponding gradient entry */
1145  for( i = 0; i < SCIPexprtreeGetNVars(tree); ++i )
1146  {
1147  var = SCIPexprtreeGetVars(tree)[i];
1148  assert(var != NULL);
1149 
1150  /* retrieving the master problem variable for the given subproblem variable. */
1151  SCIP_CALL( SCIPgetBendersMasterVar(masterprob, benders, var, &mastervar) );
1152  if( mastervar == NULL )
1153  continue;
1154 
1155  coef = mult * treegrad[i];
1156 
1157  /* adding the variable to the storage */
1158  SCIP_CALL( addVariableToArray(masterprob, vars, vals, mastervar, coef, nvars, varssize) );
1159 
1160  *dirderiv += coef * getNlpVarSol(var, primalvals, var2idx);
1161  }
1162 
1163  SCIPfreeBufferArray(subproblem, &treegrad);
1164  SCIPfreeBufferArray(subproblem, &x);
1165  }
1166 
1167  return SCIP_OKAY;
1168 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:977
SCIP_VAR * SCIPbendersGetAuxiliaryVar(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6130
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPaddNlRowGradientBenderscutOpt(SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_NLROW *nlrow, SCIP_EXPRINT *exprint, SCIP_Real mult, SCIP_Real *primalvals, SCIP_HASHMAP *var2idx, SCIP_Real *dirderiv, SCIP_VAR ***vars, SCIP_Real **vals, int *nvars, int *varssize)
enum SCIP_NlpTermStat SCIP_NLPTERMSTAT
Definition: type_nlpi.h:84
SCIP_EXPRTREE * SCIPnlrowGetExprtree(SCIP_NLROW *nlrow)
Definition: nlp.c:3370
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
Definition: lp.c:17161
internal miscellaneous methods for linear constraints
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
methods to interpret (evaluate) an expression tree "fast"
#define BENDERSCUT_LPCUT
int SCIPgetNLPRows(SCIP *scip)
Definition: scip_lp.c:596
struct SCIP_BenderscutData SCIP_BENDERSCUTDATA
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:113
SCIP_Real SCIPgetVarRedcost(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1868
SCIP_EXPORT SCIP_Real SCIPvarGetNLPSol(SCIP_VAR *var)
Definition: var.c:18054
#define SCIP_MAXSTRLEN
Definition: def.h:273
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1353
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPnlrowGetDualsol(SCIP_NLROW *nlrow)
Definition: nlp.c:3451
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1986
static SCIP_Real getNlpVarSol(SCIP_VAR *var, SCIP_Real *primalvals, SCIP_HASHMAP *var2idx)
int SCIPbendersGetNSubproblems(SCIP_BENDERS *benders)
Definition: benders.c:5938
#define FALSE
Definition: def.h:73
SCIP_Longint SCIPbenderscutGetNFound(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:534
public methods for Benders&#39; decomposition
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17515
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE
Definition: type_benders.h:42
SCIP_EXPORT SCIP_RETCODE SCIPexprintGrad(SCIP_EXPRINT *exprint, SCIP_EXPRTREE *tree, SCIP_Real *varvals, SCIP_Bool new_varvals, SCIP_Real *val, SCIP_Real *gradient)
Generates a standard Benders&#39; decomposition optimality cut.
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)
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
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_Real SCIPbendersGetSubproblemObjval(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6169
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_RETCODE SCIPcheckBendersSubproblemOptimality(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol, int probnumber, SCIP_Bool *optimal)
Definition: scip_benders.c:883
SCIP_RETCODE SCIPstoreBendersCut(SCIP *scip, SCIP_BENDERS *benders, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, int nvars)
#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:123
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:93
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_RETCODE SCIPcreateNLPSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:390
SCIP_VAR ** x
Definition: circlepacking.c:54
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
#define BENDERSCUT_NAME
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
Definition: scip_lp.c:575
SCIP_RETCODE SCIPsolveNLP(SCIP *scip)
Definition: scip_nlp.c:596
SCIP_RETCODE SCIPincludeBenderscutOpt(SCIP *scip, SCIP_BENDERS *benders)
public methods for expressions, expression trees, expression graphs, and related stuff ...
int SCIPnlrowGetNQuadVars(SCIP_NLROW *nlrow)
Definition: nlp.c:3282
SCIP_RETCODE SCIPsetConsRemovable(SCIP *scip, SCIP_CONS *cons, SCIP_Bool removable)
Definition: scip_cons.c:1411
SCIP_RETCODE SCIPgetBendersMasterVar(SCIP *scip, SCIP_BENDERS *benders, SCIP_VAR *var, SCIP_VAR **mappedvar)
Definition: scip_benders.c:651
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3220
const char * SCIPbenderscutGetName(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:483
SCIP * SCIPbendersSubproblem(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:5948
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3362
SCIP_Real coef
Definition: type_expr.h:104
SCIP_Bool SCIPhasNLPSolution(SCIP *scip)
Definition: scip_nlp.c:714
#define BENDERSCUT_DESC
SCIP_EXPORT SCIP_Real SCIPvarGetSol(SCIP_VAR *var, SCIP_Bool getlpval)
Definition: var.c:13026
SCIP_NLROW ** SCIPgetNLPNlRows(SCIP *scip)
Definition: scip_nlp.c:417
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17017
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:1337
SCIP_VAR ** SCIPgetFixedVars(SCIP *scip)
Definition: scip_prob.c:2260
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
enum SCIP_NlpSolStat SCIP_NLPSOLSTAT
Definition: type_nlpi.h:69
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1508
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1941
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:88
static SCIP_RETCODE addAuxiliaryVariableToCut(SCIP *masterprob, SCIP_BENDERS *benders, SCIP_VAR **vars, SCIP_Real *vals, int *nvars, int probnumber)
int SCIPnlrowGetNQuadElems(SCIP_NLROW *nlrow)
Definition: nlp.c:3329
void SCIPbenderscutSetData(SCIP_BENDERSCUT *benderscut, SCIP_BENDERSCUTDATA *benderscutdata)
Definition: benderscut.c:404
int SCIPgetNFixedVars(SCIP *scip)
Definition: scip_prob.c:2303
SCIP_EXPORT SCIP_RETCODE SCIPexprintFree(SCIP_EXPRINT **exprint)
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_OBJSENSE SCIPgetObjsense(SCIP *scip)
Definition: scip_prob.c:1223
#define REALABS(x)
Definition: def.h:187
int SCIPexprtreeGetNVars(SCIP_EXPRTREE *tree)
Definition: expr.c:8614
#define SCIP_CALL(x)
Definition: def.h:364
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)
int SCIPnlrowGetNLinearVars(SCIP_NLROW *nlrow)
Definition: nlp.c:3252
int SCIPgetNNLPNlRows(SCIP *scip)
Definition: scip_nlp.c:439
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_QUADELEM * SCIPnlrowGetQuadElems(SCIP_NLROW *nlrow)
Definition: nlp.c:3339
SCIP_Real * SCIPgetNLPVarsLbDualsol(SCIP *scip)
Definition: scip_nlp.c:345
SCIP_Real SCIPgetTransObjoffset(SCIP *scip)
Definition: scip_prob.c:1365
SCIP_EXPORT SCIP_RETCODE SCIPexprintCreate(BMS_BLKMEM *blkmem, SCIP_EXPRINT **exprint)
SCIP_RETCODE SCIPsetNLPIntPar(SCIP *scip, SCIP_NLPPARAM type, int ival)
Definition: scip_nlp.c:798
public methods for NLP management
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:260
SCIP_Real * SCIPgetNLPVarsUbDualsol(SCIP *scip)
Definition: scip_nlp.c:367
static SCIP_RETCODE polishSolution(SCIP *subproblem, SCIP_Bool *success)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:130
SCIP_Real SCIPinfinity(SCIP *scip)
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:70
SCIP_VAR ** SCIPgetNLPVars(SCIP *scip)
Definition: scip_nlp.c:277
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip_nlp.c:210
static const char * paramname[]
Definition: lpi_msk.c:4958
int SCIPgetNNlpis(SCIP *scip)
Definition: scip_nlp.c:132
SCIP_EXPRINTDATA * SCIPexprtreeGetInterpreterData(SCIP_EXPRTREE *tree)
Definition: expr.c:8659
SCIP_Real SCIPgetTransObjscale(SCIP *scip)
Definition: scip_prob.c:1388
SCIP_NLPSOLSTAT SCIPgetNLPSolstat(SCIP *scip)
Definition: scip_nlp.c:619
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17141
SCIP_EXPORT SCIP_Real SCIPvarGetUnchangedObj(SCIP_VAR *var)
Definition: var.c:17525
public methods for LP management
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPgetActivityLinear(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
SCIP_VAR ** SCIPexprtreeGetVars(SCIP_EXPRTREE *tree)
Definition: nlp.c:103
Constraint handler for linear constraints in their most general form, .
SCIP_Real * SCIPnlrowGetLinearCoefs(SCIP_NLROW *nlrow)
Definition: nlp.c:3272
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17723
public methods for Benders&#39; decomposition cuts
SCIP_RETCODE SCIPsetBenderscutFree(SCIP *scip, SCIP_BENDERSCUT *benderscut, SCIP_DECL_BENDERSCUTFREE((*benderscutfree)))
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17733
SCIP_NLPTERMSTAT SCIPgetNLPTermstat(SCIP *scip)
Definition: scip_nlp.c:641
#define SCIP_DEFAULT_ADDCUTS
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:221
static SCIP_DECL_BENDERSCUTFREE(benderscutFreeOpt)
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1641
static SCIP_RETCODE resolveNLPWithTighterFeastol(SCIP *subproblem, SCIP_Real multiplier, SCIP_Bool *success)
SCIP_RETCODE SCIPsetNLPRealPar(SCIP *scip, SCIP_NLPPARAM type, SCIP_Real dval)
Definition: scip_nlp.c:854
public methods for message output
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10590
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1767
#define SCIP_Real
Definition: def.h:163
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_BENDERSCUTDATA * SCIPbenderscutGetData(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:394
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_BENDERSCUTEXEC(benderscutExecOpt)
SCIP_VAR ** SCIPnlrowGetQuadVars(SCIP_NLROW *nlrow)
Definition: nlp.c:3292
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2764
SCIP_RETCODE SCIPgetNLPRealPar(SCIP *scip, SCIP_NLPPARAM type, SCIP_Real *dval)
Definition: scip_nlp.c:826
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:332
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17151
SCIP_VAR ** SCIPnlrowGetLinearVars(SCIP_NLROW *nlrow)
Definition: nlp.c:3262
SCIP_Bool SCIPbendersInStrengthenRound(SCIP_BENDERS *benders)
Definition: benders.c:6417
const char * SCIPbendersGetName(SCIP_BENDERS *benders)
Definition: benders.c:5894
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_lp.c:1667
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
SCIP_RETCODE SCIPsetConsDynamic(SCIP *scip, SCIP_CONS *cons, SCIP_Bool dynamic)
Definition: scip_cons.c:1386
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
#define SCIPABORT()
Definition: def.h:336
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:497
SCIP_EXPORT SCIP_RETCODE SCIPexprintCompile(SCIP_EXPRINT *exprint, SCIP_EXPRTREE *tree)
SCIP callable library.
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:810
int SCIPgetNNLPVars(SCIP *scip)
Definition: scip_nlp.c:299
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition: scip_lp.c:2084