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 && row2idx == NULL && var2idx == NULL)
461  && !(primalvals != NULL && consdualvals != NULL && varlbdualvals != NULL && varubdualvals != NULL && row2idx != NULL && var2idx != NULL) ) /*lint !e845*/
462  {
463  SCIPerrorMessage("The optimality cut must generated from either a SCIP instance or all of the dual solutions and indices must be supplied");
464  (*success) = FALSE;
465 
466  return SCIP_ERROR;
467  }
468 
469  nsubvars = SCIPgetNNLPVars(subproblem);
470  subvars = SCIPgetNLPVars(subproblem);
471  nfixedvars = SCIPgetNFixedVars(subproblem);
472  fixedvars = SCIPgetFixedVars(subproblem);
473 
474  /* our optimality cut implementation assumes that SCIP did not modify the objective function and sense,
475  * that is, that the objective function value of the NLP corresponds to the value of the auxiliary variable
476  * if that wouldn't be the case, then the scaling and offset may have to be considered when adding the
477  * auxiliary variable to the cut (cons/row)?
478  */
479  assert(SCIPgetTransObjoffset(subproblem) == 0.0);
480  assert(SCIPgetTransObjscale(subproblem) == 1.0);
481  assert(SCIPgetObjsense(subproblem) == SCIP_OBJSENSE_MINIMIZE);
482 
483  (*lhs) = objective;
484  assert(!SCIPisInfinity(subproblem, REALABS(*lhs)));
485 
486  (*rhs) = SCIPinfinity(masterprob);
487 
488  dirderiv = 0.0;
489 
490  SCIP_CALL( SCIPexprintCreate(SCIPblkmem(subproblem), &exprinterpreter) );
491 
492  /* looping over all NLP rows and setting the corresponding coefficients of the cut */
493  nrows = SCIPgetNNLPNlRows(subproblem);
494  for( i = 0; i < nrows; i++ )
495  {
496  SCIP_NLROW* nlrow;
497 
498  nlrow = SCIPgetNLPNlRows(subproblem)[i];
499  assert(nlrow != NULL);
500 
501  if( row2idx != NULL && consdualvals != NULL )
502  {
503  assert(SCIPhashmapExists(row2idx, (void*)nlrow) );
504  idx = SCIPhashmapGetImageInt(row2idx, (void*)nlrow);
505  dualsol = consdualvals[idx];
506  }
507  else
508  dualsol = SCIPnlrowGetDualsol(nlrow);
509  assert( !SCIPisInfinity(subproblem, dualsol) && !SCIPisInfinity(subproblem, -dualsol) );
510 
511  if( SCIPisZero(subproblem, dualsol) )
512  continue;
513 
514  SCIP_CALL( SCIPaddNlRowGradientBenderscutOpt(masterprob, subproblem, benders, nlrow, exprinterpreter,
515  -dualsol, primalvals, var2idx, &dirderiv, vars, vals, nvars, varssize) );
516  }
517 
518  SCIP_CALL( SCIPexprintFree(&exprinterpreter) );
519 
520  /* looping over all variable bounds and updating the corresponding coefficients of the cut; compute checkobj */
521  for( i = 0; i < nsubvars; i++ )
522  {
523  SCIP_VAR* var;
524  SCIP_VAR* mastervar;
525  SCIP_Real coef;
526 
527  var = subvars[i];
528 
529  (*checkobj) += SCIPvarGetObj(var) * getNlpVarSol(var, primalvals, var2idx);
530 
531  /* retrieving the master problem variable for the given subproblem variable. */
532  SCIP_CALL( SCIPgetBendersMasterVar(masterprob, benders, var, &mastervar) );
533 
534  if( var2idx != NULL && varubdualvals != NULL && varlbdualvals != NULL )
535  {
536  assert(SCIPhashmapExists(var2idx, (void*)var) );
537  idx = SCIPhashmapGetImageInt(var2idx, (void*)var);
538  dualsol = varubdualvals[idx] - varlbdualvals[idx];
539  }
540  else
541  dualsol = SCIPgetNLPVarsUbDualsol(subproblem)[i] - SCIPgetNLPVarsLbDualsol(subproblem)[i];
542 
543  /* checking whether the subproblem variable has a corresponding master variable. */
544  if( mastervar == NULL || dualsol == 0.0 )
545  continue;
546 
547  coef = -dualsol;
548 
549  /* adding the variable to the storage */
550  SCIP_CALL( addVariableToArray(masterprob, vars, vals, mastervar, coef, nvars, varssize) );
551 
552  dirderiv += coef * getNlpVarSol(var, primalvals, var2idx);
553  }
554 
555  for( i = 0; i < nfixedvars; i++ )
556  *checkobj += SCIPvarGetUnchangedObj(fixedvars[i]) * getNlpVarSol(fixedvars[i], primalvals, var2idx);
557 
558  *lhs += dirderiv;
559 
560  /* if the side became infinite or dirderiv was infinite, then the cut generation terminates. */
561  if( SCIPisInfinity(masterprob, *lhs) || SCIPisInfinity(masterprob, -*lhs)
562  || SCIPisInfinity(masterprob, dirderiv) || SCIPisInfinity(masterprob, -dirderiv))
563  {
564  (*success) = FALSE;
565  SCIPdebugMsg(masterprob, "Infinite bound when generating optimality cut. lhs = %g dirderiv = %g.\n", lhs, dirderiv);
566  return SCIP_OKAY;
567  }
568 
569  (*success) = TRUE;
570 
571  return SCIP_OKAY;
572 }
573 
574 
575 /** Adds the auxiliary variable to the generated cut. If this is the first optimality cut for the subproblem, then the
576  * auxiliary variable is first created and added to the master problem.
577  */
578 static
580  SCIP* masterprob, /**< the SCIP instance of the master problem */
581  SCIP_BENDERS* benders, /**< the benders' decomposition structure */
582  SCIP_VAR** vars, /**< the variables in the generated cut with non-zero coefficient */
583  SCIP_Real* vals, /**< the coefficients of the variables in the generated cut */
584  int* nvars, /**< the number of variables in the cut */
585  int probnumber /**< the number of the pricing problem */
586  )
587 {
588  SCIP_VAR* auxiliaryvar;
589 
590  assert(masterprob != NULL);
591  assert(benders != NULL);
592  assert(vars != NULL);
593  assert(vals != NULL);
594 
595  auxiliaryvar = SCIPbendersGetAuxiliaryVar(benders, probnumber);
596 
597  vars[(*nvars)] = auxiliaryvar;
598  vals[(*nvars)] = 1.0;
599  (*nvars)++;
600 
601  return SCIP_OKAY;
602 }
603 
604 
605 /*
606  * Callback methods of Benders' decomposition cuts
607  */
608 
609 /** destructor of Benders' decomposition cuts to free user data (called when SCIP is exiting) */
610 static
611 SCIP_DECL_BENDERSCUTFREE(benderscutFreeOpt)
612 { /*lint --e{715}*/
613  SCIP_BENDERSCUTDATA* benderscutdata;
614 
615  assert( benderscut != NULL );
616  assert( strcmp(SCIPbenderscutGetName(benderscut), BENDERSCUT_NAME) == 0 );
617 
618  /* free Benders' cut data */
619  benderscutdata = SCIPbenderscutGetData(benderscut);
620  assert( benderscutdata != NULL );
621 
622  SCIPfreeBlockMemory(scip, &benderscutdata);
623 
624  SCIPbenderscutSetData(benderscut, NULL);
625 
626  return SCIP_OKAY;
627 }
628 
629 
630 /** execution method of Benders' decomposition cuts */
631 static
632 SCIP_DECL_BENDERSCUTEXEC(benderscutExecOpt)
633 { /*lint --e{715}*/
634  SCIP* subproblem;
635  SCIP_BENDERSCUTDATA* benderscutdata;
636  SCIP_Bool nlprelaxation;
637  SCIP_Bool addcut;
638  char cutname[SCIP_MAXSTRLEN];
639 
640  assert(scip != NULL);
641  assert(benders != NULL);
642  assert(benderscut != NULL);
643  assert(result != NULL);
644  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
645 
646  /* retrieving the Benders' cut data */
647  benderscutdata = SCIPbenderscutGetData(benderscut);
648 
649  /* if the cuts are generated prior to the solving stage, then rows can not be generated. So constraints must be
650  * added to the master problem.
651  */
653  addcut = FALSE;
654  else
655  addcut = benderscutdata->addcuts;
656 
657  /* setting the name of the generated cut */
658  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "optimalitycut_%d_%" SCIP_LONGINT_FORMAT, probnumber,
659  SCIPbenderscutGetNFound(benderscut) );
660 
661  subproblem = SCIPbendersSubproblem(benders, probnumber);
662 
663  if( subproblem == NULL )
664  {
665  SCIPdebugMsg(scip, "The subproblem %d is set to NULL. The <%s> Benders' decomposition cut can not be executed.\n",
666  probnumber, BENDERSCUT_NAME);
667 
668  (*result) = SCIP_DIDNOTRUN;
669  return SCIP_OKAY;
670  }
671 
672  /* setting a flag to indicate whether the NLP relaxation should be used to generate cuts */
673  nlprelaxation = SCIPisNLPConstructed(subproblem) && SCIPgetNNlpis(subproblem);
674 
675  /* only generate optimality cuts if the subproblem LP or NLP is optimal,
676  * since we use the dual solution of the LP/NLP to construct the optimality cut
677  */
678  if( SCIPgetStage(subproblem) == SCIP_STAGE_SOLVING &&
679  ((!nlprelaxation && SCIPgetLPSolstat(subproblem) == SCIP_LPSOLSTAT_OPTIMAL) ||
680  (nlprelaxation && SCIPgetNLPSolstat(subproblem) <= SCIP_NLPSOLSTAT_FEASIBLE)) )
681  {
682  /* generating a cut for a given subproblem */
683  SCIP_CALL( SCIPgenerateAndApplyBendersOptCut(scip, subproblem, benders, benderscut, sol, probnumber, cutname,
684  SCIPbendersGetSubproblemObjval(benders, probnumber), NULL, NULL, NULL, NULL, NULL, NULL, type, addcut,
685  FALSE, result) );
686 
687  /* if it was not possible to generate a cut, this could be due to numerical issues. So the solution to the LP is
688  * resolved and the generation of the cut is reattempted. For NLPs, we do not have such a polishing yet.
689  */
690  if( (*result) == SCIP_DIDNOTFIND )
691  {
692  SCIP_Bool success;
693 
694  SCIPdebugMsg(scip, "Numerical trouble generating optimality cut for subproblem %d.", probnumber);
695 
696  if( !nlprelaxation )
697  {
698  SCIPdebugMsg(scip, "Attempting to polish the LP solution to find an alternative dual extreme point.\n");
699 
700  SCIP_CALL( polishSolution(subproblem, &success) );
701 
702  /* only attempt to generate a cut if the solution polishing was successful */
703  if( success )
704  {
705  SCIP_CALL( SCIPgenerateAndApplyBendersOptCut(scip, subproblem, benders, benderscut, sol, probnumber, cutname,
706  SCIPbendersGetSubproblemObjval(benders, probnumber), NULL, NULL, NULL, NULL, NULL, NULL, type, addcut,
707  FALSE, result) );
708  }
709  }
710  else
711  {
712  SCIP_Real multiplier = 0.01;
713 
714  SCIPdebugMsg(scip, "Attempting to resolve the NLP with a tighter feasibility tolerance to find an "
715  "alternative dual extreme point.\n");
716 
717  while( multiplier > 1e-06 && (*result) == SCIP_DIDNOTFIND )
718  {
719  SCIP_CALL( resolveNLPWithTighterFeastol(subproblem, multiplier, &success) );
720 
721  if( success )
722  {
723  SCIP_CALL( SCIPgenerateAndApplyBendersOptCut(scip, subproblem, benders, benderscut, sol, probnumber, cutname,
724  SCIPbendersGetSubproblemObjval(benders, probnumber), NULL, NULL, NULL, NULL, NULL, NULL, type, addcut,
725  FALSE, result) );
726  }
727 
728  multiplier *= 0.1;
729  }
730  }
731  }
732  }
733 
734  return SCIP_OKAY;
735 }
736 
737 
738 /*
739  * Benders' decomposition cuts specific interface methods
740  */
741 
742 /** creates the opt Benders' decomposition cuts and includes it in SCIP */
744  SCIP* scip, /**< SCIP data structure */
745  SCIP_BENDERS* benders /**< Benders' decomposition */
746  )
747 {
748  SCIP_BENDERSCUTDATA* benderscutdata;
749  SCIP_BENDERSCUT* benderscut;
751 
752  assert(benders != NULL);
753 
754  /* create opt Benders' decomposition cuts data */
755  SCIP_CALL( SCIPallocBlockMemory(scip, &benderscutdata) );
756 
757  benderscut = NULL;
758 
759  /* include Benders' decomposition cuts */
761  BENDERSCUT_PRIORITY, BENDERSCUT_LPCUT, benderscutExecOpt, benderscutdata) );
762 
763  assert(benderscut != NULL);
764 
765  /* setting the non fundamental callbacks via setter functions */
766  SCIP_CALL( SCIPsetBenderscutFree(scip, benderscut, benderscutFreeOpt) );
767 
768  /* add opt Benders' decomposition cuts parameters */
769  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/benderscut/%s/addcuts",
771  SCIP_CALL( SCIPaddBoolParam(scip, paramname,
772  "should cuts be generated and added to the cutpool instead of global constraints directly added to the problem.",
773  &benderscutdata->addcuts, FALSE, SCIP_DEFAULT_ADDCUTS, NULL, NULL) );
774 
775  return SCIP_OKAY;
776 }
777 
778 /** Generates a classical Benders' optimality cut using the dual solutions from the subproblem or the input arrays. If
779  * the dual solutions are input as arrays, then a mapping between the array indices and the rows/variables is required.
780  * This method can also be used to generate a feasibility cut, if a problem to minimise the infeasibilities has been solved
781  * to generate the dual solutions
782  */
784  SCIP* masterprob, /**< the SCIP instance of the master problem */
785  SCIP* subproblem, /**< the SCIP instance of the pricing problem */
786  SCIP_BENDERS* benders, /**< the benders' decomposition */
787  SCIP_BENDERSCUT* benderscut, /**< the benders' decomposition cut method */
788  SCIP_SOL* sol, /**< primal CIP solution */
789  int probnumber, /**< the number of the pricing problem */
790  char* cutname, /**< the name for the cut to be generated */
791  SCIP_Real objective, /**< the objective function of the subproblem */
792  SCIP_Real* primalvals, /**< the primal solutions for the NLP, can be NULL */
793  SCIP_Real* consdualvals, /**< dual variables for the constraints, can be NULL */
794  SCIP_Real* varlbdualvals, /**< the dual variables for the variable lower bounds, can be NULL */
795  SCIP_Real* varubdualvals, /**< the dual variables for the variable upper bounds, can be NULL */
796  SCIP_HASHMAP* row2idx, /**< mapping between the row in the subproblem to the index in the dual array, can be NULL */
797  SCIP_HASHMAP* var2idx, /**< mapping from variable of the subproblem to the index in the dual arrays, can be NULL */
798  SCIP_BENDERSENFOTYPE type, /**< the enforcement type calling this function */
799  SCIP_Bool addcut, /**< should the Benders' cut be added as a cut or constraint */
800  SCIP_Bool feasibilitycut, /**< is this called for the generation of a feasibility cut */
801  SCIP_RESULT* result /**< the result from solving the subproblems */
802  )
803 {
804  SCIP_CONSHDLR* consbenders;
805  SCIP_CONS* cons;
806  SCIP_ROW* row;
807  SCIP_VAR** vars;
808  SCIP_Real* vals;
809  SCIP_Real lhs;
810  SCIP_Real rhs;
811  int nvars;
812  int varssize;
813  int nmastervars;
814  SCIP_Bool optimal;
815  SCIP_Bool success;
816 
817  SCIP_Real checkobj;
818  SCIP_Real verifyobj;
819 
820  assert(masterprob != NULL);
821  assert(subproblem != NULL);
822  assert(benders != NULL);
823  assert(benderscut != NULL);
824  assert(result != NULL);
825  assert((primalvals == NULL && consdualvals == NULL && varlbdualvals == NULL && varubdualvals == NULL
826  && row2idx == NULL && var2idx == NULL)
827  || (primalvals != NULL && consdualvals != NULL && varlbdualvals != NULL && varubdualvals != NULL
828  && row2idx != NULL && var2idx != NULL));
829 
830  row = NULL;
831  cons = NULL;
832 
833  /* retrieving the Benders' decomposition constraint handler */
834  consbenders = SCIPfindConshdlr(masterprob, "benders");
835 
836  /* checking the optimality of the original problem with a comparison between the auxiliary variable and the
837  * objective value of the subproblem */
838  if( feasibilitycut )
839  optimal = FALSE;
840  else
841  {
842  SCIP_CALL( SCIPcheckBendersSubproblemOptimality(masterprob, benders, sol, probnumber, &optimal) );
843  }
844 
845  if( optimal )
846  {
847  (*result) = SCIP_FEASIBLE;
848  SCIPdebugMsg(masterprob, "No cut added for subproblem %d\n", probnumber);
849  return SCIP_OKAY;
850  }
851 
852  /* allocating memory for the variable and values arrays */
853  nmastervars = SCIPgetNVars(masterprob) + SCIPgetNFixedVars(masterprob);
854  SCIP_CALL( SCIPallocClearBufferArray(masterprob, &vars, nmastervars) );
855  SCIP_CALL( SCIPallocClearBufferArray(masterprob, &vals, nmastervars) );
856  lhs = 0.0;
857  rhs = SCIPinfinity(masterprob);
858  nvars = 0;
859  varssize = nmastervars;
860 
861  if( SCIPisNLPConstructed(subproblem) && SCIPgetNNlpis(subproblem) )
862  {
863  /* computing the coefficients of the optimality cut */
864  SCIP_CALL( computeStandardNLPOptimalityCut(masterprob, subproblem, benders, &vars, &vals, &lhs, &rhs, &nvars,
865  &varssize, objective, primalvals, consdualvals, varlbdualvals, varubdualvals, row2idx,
866  var2idx, &checkobj, &success) );
867  }
868  else
869  {
870  /* computing the coefficients of the optimality cut */
871  SCIP_CALL( computeStandardLPOptimalityCut(masterprob, subproblem, benders, &vars, &vals, &lhs, &rhs, &nvars,
872  &varssize, &checkobj, &success) );
873  }
874 
875  /* if success is FALSE, then there was an error in generating the optimality cut. No cut will be added to the master
876  * problem. Otherwise, the constraint is added to the master problem.
877  */
878  if( !success )
879  {
880  (*result) = SCIP_DIDNOTFIND;
881  SCIPdebugMsg(masterprob, "Error in generating Benders' optimality cut for problem %d.\n", probnumber);
882  }
883  else
884  {
885  /* creating an empty row or constraint for the Benders' cut */
886  if( addcut )
887  {
888  SCIP_CALL( SCIPcreateEmptyRowConshdlr(masterprob, &row, consbenders, cutname, lhs, rhs, FALSE, FALSE, TRUE) );
889  SCIP_CALL( SCIPaddVarsToRow(masterprob, row, nvars, vars, vals) );
890  }
891  else
892  {
893  SCIP_CALL( SCIPcreateConsBasicLinear(masterprob, &cons, cutname, nvars, vars, vals, lhs, rhs) );
894  SCIP_CALL( SCIPsetConsDynamic(masterprob, cons, TRUE) );
895  SCIP_CALL( SCIPsetConsRemovable(masterprob, cons, TRUE) );
896  }
897 
898  /* computing the objective function from the cut activity to verify the accuracy of the constraint */
899  verifyobj = 0.0;
900  if( addcut )
901  {
902  verifyobj += SCIProwGetLhs(row) - SCIPgetRowSolActivity(masterprob, row, sol);
903  }
904  else
905  {
906  verifyobj += SCIPgetLhsLinear(masterprob, cons) - SCIPgetActivityLinear(masterprob, cons, sol);
907  }
908 
909  /* it is possible that numerics will cause the generated cut to be invalid. This cut should not be added to the
910  * master problem, since its addition could cut off feasible solutions. The success flag is set of false, indicating
911  * that the Benders' cut could not find a valid cut.
912  */
913  if( !feasibilitycut && !SCIPisFeasEQ(masterprob, checkobj, verifyobj) )
914  {
915  SCIP_Bool valid;
916 
917  /* the difference in the checkobj and verifyobj could be due to the setup tolerances. This is checked, and if
918  * so, then the generated cut is still valid
919  */
920  SCIP_CALL( checkSetupTolerances(masterprob, sol, vars, vals, lhs, checkobj, nvars, &valid) );
921 
922  if( !valid )
923  {
924  success = FALSE;
925  SCIPdebugMsg(masterprob, "The objective function and cut activity are not equal (%g != %g).\n", checkobj,
926  verifyobj);
927 
928 #ifdef SCIP_DEBUG
929  /* we only need to abort if cut strengthen is not used. If cut strengthen has been used in this round and the
930  * cut could not be generated, then another subproblem solving round will be executed
931  */
932  if( !SCIPbendersInStrengthenRound(benders) )
933  {
934 #ifdef SCIP_MOREDEBUG
935  int i;
936 
937  for( i = 0; i < nvars; i++ )
938  printf("<%s> %g %g\n", SCIPvarGetName(vars[i]), vals[i], SCIPgetSolVal(masterprob, sol, vars[i]));
939 #endif
940  SCIPABORT();
941  }
942 #endif
943  }
944  }
945 
946  if( success )
947  {
948  /* adding the auxiliary variable to the optimality cut */
949  if( !feasibilitycut )
950  {
951  SCIP_CALL( addAuxiliaryVariableToCut(masterprob, benders, vars, vals, &nvars, probnumber) );
952  }
953 
954  /* adding the constraint to the master problem */
955  if( addcut )
956  {
957  SCIP_Bool infeasible;
958 
959  /* adding the auxiliary variable coefficient to the row */
960  if( !feasibilitycut )
961  {
962  SCIP_CALL( SCIPaddVarToRow(masterprob, row, vars[nvars - 1], vals[nvars - 1]) );
963  }
964 
965  if( type == SCIP_BENDERSENFOTYPE_LP || type == SCIP_BENDERSENFOTYPE_RELAX )
966  {
967  SCIP_CALL( SCIPaddRow(masterprob, row, FALSE, &infeasible) );
968  assert(!infeasible);
969  }
970  else
971  {
972  assert(type == SCIP_BENDERSENFOTYPE_CHECK || type == SCIP_BENDERSENFOTYPE_PSEUDO);
973  SCIP_CALL( SCIPaddPoolCut(masterprob, row) );
974  }
975 
976  (*result) = SCIP_SEPARATED;
977  }
978  else
979  {
980  /* adding the auxiliary variable coefficient to the constraint */
981  if( !feasibilitycut )
982  {
983  SCIP_CALL( SCIPaddCoefLinear(masterprob, cons, vars[nvars - 1], vals[nvars - 1]) );
984  }
985 
986  SCIPdebugPrintCons(masterprob, cons, NULL);
987 
988  SCIP_CALL( SCIPaddCons(masterprob, cons) );
989 
990  (*result) = SCIP_CONSADDED;
991  }
992 
993  /* storing the data that is used to create the cut */
994  SCIP_CALL( SCIPstoreBendersCut(masterprob, benders, vars, vals, lhs, rhs, nvars) );
995  }
996  else
997  {
998  (*result) = SCIP_DIDNOTFIND;
999  SCIPdebugMsg(masterprob, "Error in generating Benders' optimality cut for problem %d.\n", probnumber);
1000  }
1001 
1002  /* releasing the row or constraint */
1003  if( addcut )
1004  {
1005  /* release the row */
1006  SCIP_CALL( SCIPreleaseRow(masterprob, &row) );
1007  }
1008  else
1009  {
1010  /* release the constraint */
1011  SCIP_CALL( SCIPreleaseCons(masterprob, &cons) );
1012  }
1013  }
1014 
1015  SCIPfreeBufferArray(masterprob, &vals);
1016  SCIPfreeBufferArray(masterprob, &vars);
1017 
1018  return SCIP_OKAY;
1019 }
1020 
1021 
1022 /** 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
1023  *
1024  * Only computes gradient w.r.t. master problem variables.
1025  * Computes also the directional derivative, that is, mult times gradient times solution.
1026  */
1028  SCIP* masterprob, /**< the SCIP instance of the master problem */
1029  SCIP* subproblem, /**< the SCIP instance of the subproblem */
1030  SCIP_BENDERS* benders, /**< the benders' decomposition structure */
1031  SCIP_NLROW* nlrow, /**< nonlinear row */
1032  SCIP_EXPRINT* exprint, /**< expressions interpreter */
1033  SCIP_Real mult, /**< multiplier */
1034  SCIP_Real* primalvals, /**< the primal solutions for the NLP, can be NULL */
1035  SCIP_HASHMAP* var2idx, /**< mapping from variable of the subproblem to the index in the dual arrays, can be NULL */
1036  SCIP_Real* dirderiv, /**< storage to add directional derivative */
1037  SCIP_VAR*** vars, /**< pointer to array of variables in the generated cut with non-zero coefficient */
1038  SCIP_Real** vals, /**< pointer to array of coefficients of the variables in the generated cut */
1039  int* nvars, /**< the number of variables in the cut */
1040  int* varssize /**< the number of variables in the array */
1041  )
1042 {
1043  SCIP_EXPRTREE* tree;
1044  SCIP_VAR* var;
1045  SCIP_VAR* mastervar;
1046  SCIP_Real coef;
1047  int i;
1048 
1049  assert(masterprob != NULL);
1050  assert(subproblem != NULL);
1051  assert(benders != NULL);
1052  assert(nlrow != NULL);
1053  assert(exprint != NULL);
1054  assert((primalvals == NULL && var2idx == NULL) || (primalvals != NULL && var2idx != NULL));
1055  assert(mult != 0.0);
1056  assert(dirderiv != NULL);
1057  assert(vars != NULL);
1058  assert(vals != NULL);
1059 
1060  /* linear part */
1061  for( i = 0; i < SCIPnlrowGetNLinearVars(nlrow); i++ )
1062  {
1063  var = SCIPnlrowGetLinearVars(nlrow)[i];
1064  assert(var != NULL);
1065 
1066  /* retrieving the master problem variable for the given subproblem variable. */
1067  SCIP_CALL( SCIPgetBendersMasterVar(masterprob, benders, var, &mastervar) );
1068  if( mastervar == NULL )
1069  continue;
1070 
1071  coef = mult * SCIPnlrowGetLinearCoefs(nlrow)[i];
1072 
1073  /* adding the variable to the storage */
1074  SCIP_CALL( addVariableToArray(masterprob, vars, vals, mastervar, coef, nvars, varssize) );
1075 
1076  *dirderiv += coef * getNlpVarSol(var, primalvals, var2idx);
1077  }
1078 
1079  /* quadratic part */
1080  for( i = 0; i < SCIPnlrowGetNQuadElems(nlrow); i++ )
1081  {
1082  SCIP_VAR* var1;
1083  SCIP_VAR* var2;
1084  SCIP_VAR* mastervar1;
1085  SCIP_VAR* mastervar2;
1086  SCIP_Real coef1;
1087  SCIP_Real coef2;
1088 
1089  assert(SCIPnlrowGetQuadElems(nlrow)[i].idx1 < SCIPnlrowGetNQuadVars(nlrow));
1090  assert(SCIPnlrowGetQuadElems(nlrow)[i].idx2 < SCIPnlrowGetNQuadVars(nlrow));
1091 
1092  var1 = SCIPnlrowGetQuadVars(nlrow)[SCIPnlrowGetQuadElems(nlrow)[i].idx1];
1093  var2 = SCIPnlrowGetQuadVars(nlrow)[SCIPnlrowGetQuadElems(nlrow)[i].idx2];
1094 
1095  /* retrieving the master problem variables for the given subproblem variables. */
1096  SCIP_CALL( SCIPgetBendersMasterVar(masterprob, benders, var1, &mastervar1) );
1097  SCIP_CALL( SCIPgetBendersMasterVar(masterprob, benders, var2, &mastervar2) );
1098 
1099  coef1 = mult * SCIPnlrowGetQuadElems(nlrow)[i].coef * getNlpVarSol(var2, primalvals, var2idx);
1100  coef2 = mult * SCIPnlrowGetQuadElems(nlrow)[i].coef * getNlpVarSol(var1, primalvals, var2idx);
1101 
1102  /* adding the variable to the storage */
1103  if( mastervar1 != NULL )
1104  {
1105  SCIP_CALL( addVariableToArray(masterprob, vars, vals, mastervar1, coef1, nvars, varssize) );
1106  }
1107  if( mastervar2 != NULL )
1108  {
1109  SCIP_CALL( addVariableToArray(masterprob, vars, vals, mastervar2, coef2, nvars, varssize) );
1110  }
1111 
1112  if( mastervar1 != NULL )
1113  *dirderiv += coef1 * getNlpVarSol(var1, primalvals, var2idx);
1114 
1115  if( mastervar2 != NULL )
1116  *dirderiv += coef2 * getNlpVarSol(var2, primalvals, var2idx);
1117  }
1118 
1119  /* tree part */
1120  tree = SCIPnlrowGetExprtree(nlrow);
1121  if( tree != NULL )
1122  {
1123  SCIP_Real* treegrad;
1124  SCIP_Real* x;
1125  SCIP_Real val;
1126 
1127  SCIP_CALL( SCIPallocBufferArray(subproblem, &x, SCIPexprtreeGetNVars(tree)) );
1128  SCIP_CALL( SCIPallocBufferArray(subproblem, &treegrad, SCIPexprtreeGetNVars(tree)) );
1129 
1130  /* compile expression tree, if not done before */
1131  if( SCIPexprtreeGetInterpreterData(tree) == NULL )
1132  {
1133  SCIP_CALL( SCIPexprintCompile(exprint, tree) );
1134  }
1135 
1136  /* sets the solution value */
1137  for( i = 0; i < SCIPexprtreeGetNVars(tree); ++i )
1138  x[i] = getNlpVarSol(SCIPexprtreeGetVars(tree)[i], primalvals, var2idx);
1139 
1140  SCIP_CALL( SCIPexprintGrad(exprint, tree, x, TRUE, &val, treegrad) );
1141 
1142  /* update corresponding gradient entry */
1143  for( i = 0; i < SCIPexprtreeGetNVars(tree); ++i )
1144  {
1145  var = SCIPexprtreeGetVars(tree)[i];
1146  assert(var != NULL);
1147 
1148  /* retrieving the master problem variable for the given subproblem variable. */
1149  SCIP_CALL( SCIPgetBendersMasterVar(masterprob, benders, var, &mastervar) );
1150  if( mastervar == NULL )
1151  continue;
1152 
1153  coef = mult * treegrad[i];
1154 
1155  /* adding the variable to the storage */
1156  SCIP_CALL( addVariableToArray(masterprob, vars, vals, mastervar, coef, nvars, varssize) );
1157 
1158  *dirderiv += coef * getNlpVarSol(var, primalvals, var2idx);
1159  }
1160 
1161  SCIPfreeBufferArray(subproblem, &treegrad);
1162  SCIPfreeBufferArray(subproblem, &x);
1163  }
1164 
1165  return SCIP_OKAY;
1166 }
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:6141
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:17174
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:5949
#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:6180
#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:3221
const char * SCIPbenderscutGetName(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:483
SCIP * SCIPbendersSubproblem(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:5959
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3363
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:8616
#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:8661
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:17154
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:10604
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:17164
SCIP_VAR ** SCIPnlrowGetLinearVars(SCIP_NLROW *nlrow)
Definition: nlp.c:3262
SCIP_Bool SCIPbendersInStrengthenRound(SCIP_BENDERS *benders)
Definition: benders.c:6428
const char * SCIPbendersGetName(SCIP_BENDERS *benders)
Definition: benders.c:5905
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:503
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