Scippy

SCIP

Solving Constraint Integer Programs

benderscut_feasalt.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_feasalt.c
17  * @brief Alternative feasibility cuts for Benders' decomposition
18  * @author Stephen J. Maher
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <assert.h>
24 #include <string.h>
25 
26 #include "nlpi/exprinterpret.h"
27 #include "nlpi/pub_expr.h"
28 #include "nlpi/nlpi.h"
30 #include "scip/benderscut_opt.h"
31 #include "scip/cons_linear.h"
32 #include "scip/pub_benderscut.h"
33 #include "scip/pub_benders.h"
34 #include "scip/pub_lp.h"
35 #include "scip/pub_message.h"
36 #include "scip/pub_misc.h"
37 #include "scip/pub_misc_linear.h"
38 #include "scip/pub_nlp.h"
39 #include "scip/pub_var.h"
40 #include "scip/scip_benders.h"
41 #include "scip/scip_cons.h"
42 #include "scip/scip_general.h"
43 #include "scip/scip_lp.h"
44 #include "scip/scip_mem.h"
45 #include "scip/scip_message.h"
46 #include "scip/scip_nlp.h"
47 #include "scip/scip_nonlinear.h"
48 #include "scip/scip_numerics.h"
49 #include "scip/scip_param.h"
50 #include "scip/scip_prob.h"
51 #include "scip/scip_solvingstats.h"
52 #include "scip/scip_timing.h"
53 #include "scip/scip_var.h"
54 
55 #define BENDERSCUT_NAME "feasalt"
56 #define BENDERSCUT_DESC "Alternative feasibility cuts for Benders' decomposition"
57 #define BENDERSCUT_PRIORITY 10001
58 #define BENDERSCUT_LPCUT TRUE
59 
60 #define SCIP_DEFAULT_DISPLAYFREQ 20
61 #define SLACKVAR_NAME "##bendersslackvar" /** the name for the Benders' slack variables added to each
62  * constraints in the subproblems */
63 
64 struct SCIP_BenderscutData
65 {
66  SCIP_NLPI* nlpi; /**< nlpi used to create the nlpi problem */
67  SCIP_NLPIPROBLEM* nlpiprob; /**< nlpi problem representing the convex NLP relaxation */
68  SCIP_HASHMAP* var2idx; /**< mapping the variable to the index in the NLPI problem */
69  SCIP_HASHMAP* row2idx; /**< mapping the rows to the index in the NLPI problem */
70  SCIP_VAR** nlpivars; /**< the variables in the NLPI problem */
71  SCIP_NLROW** nlpirows; /**< the rows in the NLPI problem */
72  int nlpinvars; /**< the number of variables in the NPLI problem */
73  int nlpinrows; /**< the number of rows in the NLPI problem */
74  int nlpinslackvars; /**< the number of slack variables in the NLPI problem */
75  int nlpiprobsubprob; /**< the index of the subproblem that the nonlinear problem belongs to */
76 
77  SCIP_Real* slackvarlbs; /**< an array of zeros for the slack variable lower bounds*/
78  SCIP_Real* slackvarubs; /**< an array of infinity for the slack variable upper bounds*/
79  int* slackvarinds; /**< array of indices for the slack variables */
80 };
81 
82 /*
83  * Local methods
84  */
85 
86 /** frees the non linear problem */
87 static
89  SCIP* scip, /**< the SCIP data structure */
90  SCIP_BENDERSCUT* benderscut /**< the Benders' decomposition structure */
91  )
92 {
93  SCIP_BENDERSCUTDATA* benderscutdata;
94 
95  assert(scip != NULL);
96  assert(benderscut != NULL);
97 
98  benderscutdata = SCIPbenderscutGetData(benderscut);
99  assert(benderscutdata != NULL);
100 
101  if( benderscutdata->nlpiprob != NULL )
102  {
103  assert(benderscutdata->nlpi != NULL);
104 
105  SCIPfreeBlockMemoryArray(scip, &benderscutdata->slackvarinds, benderscutdata->nlpinvars);
106  SCIPfreeBlockMemoryArray(scip, &benderscutdata->slackvarubs, benderscutdata->nlpinvars);
107  SCIPfreeBlockMemoryArray(scip, &benderscutdata->slackvarlbs, benderscutdata->nlpinvars);
108  SCIPfreeBlockMemoryArray(scip, &benderscutdata->nlpirows, benderscutdata->nlpinrows);
109  SCIPfreeBlockMemoryArray(scip, &benderscutdata->nlpivars, benderscutdata->nlpinvars);
110  SCIPhashmapFree(&benderscutdata->row2idx);
111  SCIPhashmapFree(&benderscutdata->var2idx);
112 
113  SCIP_CALL( SCIPnlpiFreeProblem(benderscutdata->nlpi, &benderscutdata->nlpiprob) );
114 
115  benderscutdata->nlpinslackvars = 0;
116  benderscutdata->nlpinrows = 0;
117  benderscutdata->nlpinvars = 0;
118 
119  benderscutdata->nlpi = NULL;
120  }
121 
122  return SCIP_OKAY;
123 }
124 
125 /** solves the auxiliary feasibility subproblem.
126  *
127  * @note: the variable fixings need to be setup before calling this function
128  */
129 static
131  SCIP* scip, /**< SCIP data structure */
132  SCIP_BENDERSCUTDATA* benderscutdata, /**< Benders' cut data */
133  SCIP_Bool* success /**< returns whether solving the feasibility problem was successful */
134  )
135 {
136  SCIP_Real timelimit;
137  SCIP_NLPSOLSTAT nlpsolstat;
138 
139  assert(scip != NULL);
140  assert(benderscutdata != NULL);
141 
142  (*success) = TRUE;
143 
144  /* setting the time limit */
145  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
146  if( !SCIPisInfinity(scip, timelimit) )
147  {
148  timelimit -= SCIPgetSolvingTime(scip);
149  if( timelimit <= 0.0 )
150  {
151  SCIPdebugMsg(scip, "skip NLP solve; no time left\n");
152  return SCIP_OKAY;
153  }
154  }
155  SCIP_CALL( SCIPnlpiSetRealPar(benderscutdata->nlpi, benderscutdata->nlpiprob, SCIP_NLPPAR_TILIM, timelimit) );
156 
157 #ifdef SCIP_MOREDEBUG
158  SCIP_CALL( SCIPnlpiSetIntPar(benderscutdata->nlpi, benderscutdata->nlpiprob, SCIP_NLPPAR_VERBLEVEL, 1) );
159 #endif
160 
161  SCIP_CALL( SCIPnlpiSolve(benderscutdata->nlpi, benderscutdata->nlpiprob) );
162  SCIPdebugMsg(scip, "NLP solstat = %d\n", SCIPnlpiGetSolstat(benderscutdata->nlpi, benderscutdata->nlpiprob));
163 
164  nlpsolstat = SCIPnlpiGetSolstat(benderscutdata->nlpi, benderscutdata->nlpiprob);
165 
166  /* if the feasibility NLP is not feasible, then it is not possible to generate a Benders' cut. This is also an error,
167  * since the NLP should always be feasible. In debug mode, an ABORT will be thrown.
168  */
169  if( nlpsolstat > SCIP_NLPSOLSTAT_FEASIBLE )
170  (*success) = FALSE;
171 
172  return SCIP_OKAY;
173 }
174 
175 /** builds the non-linear problem to resolve to generate a cut for the infeasible subproblem */
176 static
178  SCIP* masterprob, /**< the SCIP instance of the master problem */
179  SCIP* subproblem, /**< the SCIP instance of the pricing problem */
180  SCIP_BENDERSCUT* benderscut /**< the benders' decomposition cut method */
181  )
182 {
183  SCIP_BENDERSCUTDATA* benderscutdata;
184  SCIP_Real* obj;
185  int i;
186 
187  assert(masterprob != NULL);
188 
189  benderscutdata = SCIPbenderscutGetData(benderscut);
190  assert(benderscutdata != NULL);
191 
192  /* first freeing the non-linear problem if it exists */
193  SCIP_CALL( freeNonlinearProblem(masterprob, benderscut) );
194 
195  assert(benderscutdata->nlpi == NULL);
196  assert(benderscutdata->nlpiprob == NULL);
197 
198  benderscutdata->nlpinvars = SCIPgetNVars(subproblem);
199  benderscutdata->nlpinrows = SCIPgetNNLPNlRows(subproblem);
200  benderscutdata->nlpi = SCIPgetNlpis(subproblem)[0];
201  assert(benderscutdata->nlpi != NULL);
202 
203  SCIP_CALL( SCIPnlpiCreateProblem(benderscutdata->nlpi, &benderscutdata->nlpiprob, "benders-feascutalt-nlp") );
204  SCIP_CALL( SCIPhashmapCreate(&benderscutdata->var2idx, SCIPblkmem(masterprob), benderscutdata->nlpinvars) );
205  SCIP_CALL( SCIPhashmapCreate(&benderscutdata->row2idx, SCIPblkmem(masterprob), benderscutdata->nlpinrows) );
206 
207  SCIP_CALL( SCIPduplicateBlockMemoryArray(masterprob, &benderscutdata->nlpivars, SCIPgetVars(subproblem),
208  benderscutdata->nlpinvars) ); /*lint !e666*/
209  SCIP_CALL( SCIPduplicateBlockMemoryArray(masterprob, &benderscutdata->nlpirows, SCIPgetNLPNlRows(subproblem),
210  benderscutdata->nlpinrows) ); /*lint !e666*/
211 
212  SCIP_CALL( SCIPcreateNlpiProb(subproblem, benderscutdata->nlpi, SCIPgetNLPNlRows(subproblem), benderscutdata->nlpinrows,
213  benderscutdata->nlpiprob, benderscutdata->var2idx, benderscutdata->row2idx, NULL, SCIPinfinity(subproblem), FALSE,
214  FALSE) );
215 
216  /* storing the slack variable bounds and indices */
217  SCIP_CALL( SCIPallocBufferArray(masterprob, &obj, benderscutdata->nlpinvars) );
218 
219  SCIP_CALL( SCIPallocBlockMemoryArray(masterprob, &benderscutdata->slackvarlbs, benderscutdata->nlpinvars) );
220  SCIP_CALL( SCIPallocBlockMemoryArray(masterprob, &benderscutdata->slackvarubs, benderscutdata->nlpinvars) );
221  SCIP_CALL( SCIPallocBlockMemoryArray(masterprob, &benderscutdata->slackvarinds, benderscutdata->nlpinvars) );
222  benderscutdata->nlpinslackvars = 0;
223  for( i = 0; i < benderscutdata->nlpinvars; i++ )
224  {
225  if( strstr(SCIPvarGetName(benderscutdata->nlpivars[i]), SLACKVAR_NAME) )
226  {
227  benderscutdata->slackvarlbs[benderscutdata->nlpinslackvars] = 0.0;
228  benderscutdata->slackvarubs[benderscutdata->nlpinslackvars] = SCIPinfinity(subproblem);
229  benderscutdata->slackvarinds[benderscutdata->nlpinslackvars] = SCIPhashmapGetImageInt(benderscutdata->var2idx,
230  (void*)benderscutdata->nlpivars[i]);
231 
232  obj[benderscutdata->nlpinslackvars] = 1.0;
233 
234  benderscutdata->nlpinslackvars++;
235  }
236  }
237 
238  /* setting the objective function */
239  SCIP_CALL( SCIPnlpiSetObjective(benderscutdata->nlpi, benderscutdata->nlpiprob, benderscutdata->nlpinslackvars,
240  benderscutdata->slackvarinds, obj, 0, NULL, NULL, NULL, 0.0) );
241 
242  /* unfixing the slack variables */
243  SCIP_CALL( SCIPnlpiChgVarBounds(benderscutdata->nlpi, benderscutdata->nlpiprob, benderscutdata->nlpinslackvars,
244  benderscutdata->slackvarinds, benderscutdata->slackvarlbs, benderscutdata->slackvarubs) );
245 
246  SCIPfreeBufferArray(masterprob, &obj);
247 
248  return SCIP_OKAY;
249 }
250 
251 /** updates the non-linear problem that is resolved to generate a cut for the infeasible subproblem */
252 static
254  SCIP* subproblem, /**< the SCIP instance of the pricing problem */
255  SCIP_BENDERSCUT* benderscut /**< the benders' decomposition cut method */
256  )
257 {
258  SCIP_BENDERSCUTDATA* benderscutdata;
259 
260  assert(subproblem != NULL);
261  assert(benderscut != NULL);
262 
263  benderscutdata = SCIPbenderscutGetData(benderscut);
264  assert(benderscutdata != NULL);
265  assert(benderscutdata->nlpi != NULL);
266  assert(benderscutdata->nlpiprob != NULL);
267  assert(benderscutdata->var2idx != NULL);
268  assert(benderscutdata->row2idx != NULL);
269 
270  /* setting the variable bounds to that from the current subproblem */
271  SCIP_CALL( SCIPupdateNlpiProb(subproblem, benderscutdata->nlpi, benderscutdata->nlpiprob, benderscutdata->var2idx,
272  benderscutdata->nlpivars, benderscutdata->nlpinvars, SCIPinfinity(subproblem)) );
273 
274  /* unfixing the slack variables */
275  SCIP_CALL( SCIPnlpiChgVarBounds(benderscutdata->nlpi, benderscutdata->nlpiprob, benderscutdata->nlpinslackvars,
276  benderscutdata->slackvarinds, benderscutdata->slackvarlbs, benderscutdata->slackvarubs) );
277 
278  return SCIP_OKAY;
279 }
280 
281 /** generates and applies Benders' cuts */
282 static
284  SCIP* masterprob, /**< the SCIP instance of the master problem */
285  SCIP* subproblem, /**< the SCIP instance of the pricing problem */
286  SCIP_BENDERS* benders, /**< the benders' decomposition */
287  SCIP_BENDERSCUT* benderscut, /**< the benders' decomposition cut method */
288  SCIP_SOL* sol, /**< primal CIP solution */
289  int probnumber, /**< the number of the pricing problem */
290  SCIP_BENDERSENFOTYPE type, /**< the enforcement type calling this function */
291  SCIP_RESULT* result /**< the result from solving the subproblems */
292  )
293 {
294  SCIP_BENDERSCUTDATA* benderscutdata;
295  SCIP_Real* primalvals;
296  SCIP_Real* consdualvals;
297  SCIP_Real* varlbdualvals;
298  SCIP_Real* varubdualvals;
299  SCIP_Real obj;
300  char cutname[SCIP_MAXSTRLEN];
301  SCIP_Bool success;
302 #ifdef SCIP_EVENMOREDEBUG
303  int i;
304 #endif
305 
306  assert(masterprob != NULL);
307  assert(subproblem != NULL);
308  assert(benders != NULL);
309  assert(result != NULL);
310 
311  benderscutdata = SCIPbenderscutGetData(benderscut);
312  assert(benderscutdata != NULL);
313 
314  /* creating or updating the NLPI problem */
315  if( benderscutdata->nlpiprob == NULL || benderscutdata->nlpiprobsubprob != probnumber )
316  {
317  SCIP_CALL( createAuxiliaryNonlinearSubproblem(masterprob, subproblem, benderscut) );
318  benderscutdata->nlpiprobsubprob = probnumber;
319  }
320  else
321  {
322  SCIP_CALL( updateAuxiliaryNonlinearSubproblem(subproblem, benderscut) );
323  }
324 
325  /* solving the NLPI problem to get the minimum infeasible solution */
326  SCIP_CALL( solveFeasibilityNonlinearSubproblem(subproblem, benderscutdata, &success) );
327 
328  if( !success )
329  {
330  (*result) = SCIP_DIDNOTFIND;
331  SCIPdebugMsg(masterprob, "Error in generating Benders' feasibility cut for problem %d. "
332  "The feasibility subproblem failed to solve with a feasible solution.\n", probnumber);
333  return SCIP_OKAY;
334  }
335 
336  /* getting the solution from the NLPI problem */
337  SCIP_CALL( SCIPnlpiGetSolution(benderscutdata->nlpi, benderscutdata->nlpiprob, &primalvals, &consdualvals,
338  &varlbdualvals, &varubdualvals, &obj) );
339 
340 #ifdef SCIP_EVENMOREDEBUG
341  SCIPdebugMsg(masterprob, "NLP Feasibility problem solution.\n");
342  SCIPdebugMsg(masterprob, "Objective: %g.\n", obj);
343  for( i = 0; i < benderscutdata->nlpinvars; i++ )
344  {
345  int varindex;
346  SCIP_Real solval;
347  if( SCIPhashmapExists(benderscutdata->var2idx, benderscutdata->nlpivars[i]) )
348  {
349  varindex = SCIPhashmapGetImageInt(benderscutdata->var2idx, benderscutdata->nlpivars[i]);
350  solval = primalvals[varindex];
351 
352  if( !SCIPisZero(masterprob, solval) )
353  {
354  SCIPdebugMsg(masterprob, "%s (obj: %g): %20g\n", SCIPvarGetName(benderscutdata->nlpivars[i]),
355  SCIPvarGetObj(benderscutdata->nlpivars[i]), solval);
356  }
357  }
358  }
359 #endif
360 
361  /* setting the name of the generated cut */
362  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "altfeasibilitycut_%d_%d", probnumber,
363  SCIPbenderscutGetNFound(benderscut) );
364 
365  /* generating a Benders' decomposition cut using the classical optimality cut methods */
366  SCIP_CALL( SCIPgenerateAndApplyBendersOptCut(masterprob, subproblem, benders, benderscut,
367  sol, probnumber, cutname, obj, primalvals, consdualvals, varlbdualvals, varubdualvals, benderscutdata->row2idx,
368  benderscutdata->var2idx, type, FALSE, TRUE, result) );
369 
370  if( (*result) == SCIP_CONSADDED )
371  {
372  if( SCIPisInfinity(masterprob, -SCIPgetDualbound(masterprob))
373  && SCIPbenderscutGetNFound(benderscut) % SCIP_DEFAULT_DISPLAYFREQ == 0 )
374  {
375  if( SCIPgetStage(masterprob) == SCIP_STAGE_SOLVING )
376  {
379  "Benders' Decomposition: Master problem LP is infeasible. Added %d feasibility cuts.\n",
380  SCIPbenderscutGetNFound(benderscut));
381  }
382  }
383  SCIPdebugMsg(masterprob, "Constraints %s has been added to the master problem.\n", cutname);
384  }
385 
386  return SCIP_OKAY;
387 }
388 
389 /*
390  * Callback methods of Benders' decomposition cuts
391  */
392 
393 /** deinitialization method of Benders' decomposition cuts (called before transformed problem is freed) */
394 static
395 SCIP_DECL_BENDERSCUTEXIT(benderscutExitFeasalt)
396 { /*lint --e{715}*/
397  assert( benderscut != NULL );
398  assert( strcmp(SCIPbenderscutGetName(benderscut), BENDERSCUT_NAME) == 0 );
399 
400  /* freeing the non-linear problem information */
401  SCIP_CALL( freeNonlinearProblem(scip, benderscut) );
402 
403  return SCIP_OKAY;
404 }
405 
406 /** destructor of the Benders' decomposition cut to free user data (called when SCIP is exiting) */
407 static
408 SCIP_DECL_BENDERSCUTFREE(benderscutFreeFeasalt)
409 { /*lint --e{715}*/
410  SCIP_BENDERSCUTDATA* benderscutdata;
411 
412  assert(scip != NULL);
413  assert(benderscut != NULL);
414 
415  benderscutdata = SCIPbenderscutGetData(benderscut);
416  assert(benderscutdata != NULL);
417 
418  SCIPfreeBlockMemory(scip, &benderscutdata);
419 
420  return SCIP_OKAY;
421 }
422 
423 /** execution method of Benders' decomposition cuts */
424 static
425 SCIP_DECL_BENDERSCUTEXEC(benderscutExecFeasalt)
426 { /*lint --e{715}*/
427  SCIP* subproblem;
428  SCIP_Bool nlprelaxation;
429 
430  assert(scip != NULL);
431  assert(benders != NULL);
432  assert(benderscut != NULL);
433  assert(result != NULL);
434  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
435 
436  subproblem = SCIPbendersSubproblem(benders, probnumber);
437 
438  /* setting a flag to indicate whether the NLP relaxation should be used to generate cuts */
439  nlprelaxation = SCIPisNLPConstructed(subproblem) && SCIPgetNNlpis(subproblem)
441 
442  /* only generate feasibility cuts if the subproblem LP or NLP is infeasible,
443  * since we use the farkas proof from the LP or the dual solution of the NLP to construct the feasibility cut
444  */
445  if( SCIPgetStage(subproblem) == SCIP_STAGE_SOLVING &&
446  (nlprelaxation && (SCIPgetNLPSolstat(subproblem) == SCIP_NLPSOLSTAT_LOCINFEASIBLE || SCIPgetNLPSolstat(subproblem) == SCIP_NLPSOLSTAT_GLOBINFEASIBLE)) )
447  {
448  /* generating a cut for a given subproblem */
449  SCIP_CALL( generateAndApplyBendersCuts(scip, subproblem, benders, benderscut, sol, probnumber, type, result) );
450  }
451 
452  return SCIP_OKAY;
453 }
454 
455 
456 /*
457  * Benders' decomposition cuts specific interface methods
458  */
459 
460 /** creates the Alternative Feasibility Benders' decomposition cuts and includes it in SCIP */
462  SCIP* scip, /**< SCIP data structure */
463  SCIP_BENDERS* benders /**< Benders' decomposition */
464  )
465 {
466  SCIP_BENDERSCUT* benderscut;
467  SCIP_BENDERSCUTDATA* benderscutdata;
468 
469  assert(benders != NULL);
470 
471  benderscut = NULL;
472 
473  SCIP_CALL( SCIPallocBlockMemory(scip, &benderscutdata) );
474  BMSclearMemory(benderscutdata);
475  benderscutdata->nlpiprobsubprob = -1;
476 
477  /* include Benders' decomposition cuts */
479  BENDERSCUT_PRIORITY, BENDERSCUT_LPCUT, benderscutExecFeasalt, benderscutdata) );
480 
481  /* set non fundamental callbacks via setter functions */
482  SCIP_CALL( SCIPsetBenderscutFree(scip, benderscut, benderscutFreeFeasalt) );
483  SCIP_CALL( SCIPsetBenderscutExit(scip, benderscut, benderscutExitFeasalt) );
484 
485  assert(benderscut != NULL);
486 
487  return SCIP_OKAY;
488 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
SCIP_RETCODE SCIPprintDisplayLine(SCIP *scip, FILE *file, SCIP_VERBLEVEL verblevel, SCIP_Bool endline)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:80
internal miscellaneous methods for linear constraints
public methods for SCIP parameter handling
methods to interpret (evaluate) an expression tree "fast"
#define BENDERSCUT_NAME
struct SCIP_BenderscutData SCIP_BENDERSCUTDATA
public methods for memory management
SCIP_NLPI ** SCIPgetNlpis(SCIP *scip)
Definition: scip_nlp.c:119
#define SCIP_MAXSTRLEN
Definition: def.h:273
internal methods for NLPI solver interfaces
public methods for timing
SCIP_RETCODE SCIPnlpiCreateProblem(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM **problem, const char *name)
Definition: nlpi.c:212
#define BENDERSCUT_DESC
SCIP_RETCODE SCIPnlpiChgVarBounds(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, int nvars, const int *indices, const SCIP_Real *lbs, const SCIP_Real *ubs)
Definition: nlpi.c:326
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1986
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:360
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
int SCIPbendersGetNSubproblems(SCIP_BENDERS *benders)
Definition: benders.c:5938
#define FALSE
Definition: def.h:73
SCIP_Longint SCIPbenderscutGetNFound(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:534
public methods for Benders&#39; decomposition
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17515
#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
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)
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_RETCODE SCIPnlpiSetRealPar(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_NLPPARAM type, SCIP_Real dval)
Definition: nlpi.c:672
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
#define BENDERSCUT_PRIORITY
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
public methods for SCIP variables
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
public methods for numerical tolerances
SCIP_RETCODE SCIPnlpiSetObjective(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, int nlins, const int *lininds, const SCIP_Real *linvals, int nquadelems, const SCIP_QUADELEM *quadelems, const int *exprvaridxs, const SCIP_EXPRTREE *exprtree, const SCIP_Real constant)
Definition: nlpi.c:301
public methods for expressions, expression trees, expression graphs, and related stuff ...
public methods for querying solving statistics
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3220
SCIP_RETCODE SCIPsetBenderscutExit(SCIP *scip, SCIP_BENDERSCUT *benderscut, SCIP_DECL_BENDERSCUTEXIT((*benderscutexit)))
const char * SCIPbenderscutGetName(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:483
SCIP * SCIPbendersSubproblem(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:5948
static SCIP_DECL_BENDERSCUTEXIT(benderscutExitFeasalt)
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3362
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:92
static SCIP_RETCODE solveFeasibilityNonlinearSubproblem(SCIP *scip, SCIP_BENDERSCUTDATA *benderscutdata, SCIP_Bool *success)
SCIP_NLROW ** SCIPgetNLPNlRows(SCIP *scip)
Definition: scip_nlp.c:417
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17017
public methods for Benders decomposition
SCIP_RETCODE SCIPnlpiGetSolution(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_Real **primalvalues, SCIP_Real **consdualvalues, SCIP_Real **varlbdualvalues, SCIP_Real **varubdualvalues, SCIP_Real *objval)
Definition: nlpi.c:538
enum SCIP_NlpSolStat SCIP_NLPSOLSTAT
Definition: type_nlpi.h:69
public methods for nonlinear functions
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1941
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
#define BENDERSCUT_LPCUT
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_NLPSOLSTAT SCIPnlpiGetSolstat(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem)
Definition: nlpi.c:512
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_RETCODE SCIPcreateNlpiProb(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLROW **nlrows, int nnlrows, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2idx, SCIP_HASHMAP *nlrow2idx, SCIP_Real *nlscore, SCIP_Real cutoffbound, SCIP_Bool setobj, SCIP_Bool onlyconvex)
#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 SCIPgetNNLPNlRows(SCIP *scip)
Definition: scip_nlp.c:439
public methods for constraint handler plugins and constraints
public methods for NLP management
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:298
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_BENDERSSUBTYPE SCIPbendersGetSubproblemType(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6291
SCIP_Real SCIPinfinity(SCIP *scip)
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:70
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3013
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip_nlp.c:210
int SCIPgetNNlpis(SCIP *scip)
Definition: scip_nlp.c:132
SCIP_NLPSOLSTAT SCIPgetNLPSolstat(SCIP *scip)
Definition: scip_nlp.c:619
SCIP_RETCODE SCIPnlpiSetIntPar(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_NLPPARAM type, int ival)
Definition: nlpi.c:637
public methods for LP management
SCIP_RETCODE SCIPnlpiSolve(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem)
Definition: nlpi.c:498
Constraint handler for linear constraints in their most general form, .
#define BMSclearMemory(ptr)
Definition: memory.h:121
public methods for the LP relaxation, rows and columns
public methods for nonlinear relaxations
public methods for Benders&#39; decomposition cuts
SCIP_RETCODE SCIPsetBenderscutFree(SCIP *scip, SCIP_BENDERSCUT *benderscut, SCIP_DECL_BENDERSCUTFREE((*benderscutfree)))
general public methods
SCIP_RETCODE SCIPupdateNlpiProb(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2nlpiidx, SCIP_VAR **nlpivars, int nlpinvars, SCIP_Real cutoffbound)
SCIP_RETCODE SCIPnlpiFreeProblem(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM **problem)
Definition: nlpi.c:225
public methods for message output
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10590
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3047
#define SCIP_Real
Definition: def.h:163
Alternative feasibility cuts for Benders&#39; decomposition.
public methods for message handling
SCIP_BENDERSCUTDATA * SCIPbenderscutGetData(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:394
static SCIP_DECL_BENDERSCUTEXEC(benderscutExecFeasalt)
static SCIP_RETCODE createAuxiliaryNonlinearSubproblem(SCIP *masterprob, SCIP *subproblem, SCIP_BENDERSCUT *benderscut)
#define SLACKVAR_NAME
SCIP_RETCODE SCIPincludeBenderscutFeasalt(SCIP *scip, SCIP_BENDERS *benders)
static SCIP_RETCODE freeNonlinearProblem(SCIP *scip, SCIP_BENDERSCUT *benderscut)
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
static SCIP_RETCODE updateAuxiliaryNonlinearSubproblem(SCIP *subproblem, SCIP_BENDERSCUT *benderscut)
public methods for global and local (sub)problems
SCIP_Real SCIPgetDualbound(SCIP *scip)
#define SCIP_DEFAULT_DISPLAYFREQ
static SCIP_DECL_BENDERSCUTFREE(benderscutFreeFeasalt)
static SCIP_RETCODE generateAndApplyBendersCuts(SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_BENDERSCUT *benderscut, SCIP_SOL *sol, int probnumber, SCIP_BENDERSENFOTYPE type, SCIP_RESULT *result)