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