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-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file benderscut_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 "scip/pub_expr.h"
28 #include "scip/benderscut_opt.h"
29 #include "scip/cons_linear.h"
30 #include "scip/pub_benderscut.h"
31 #include "scip/pub_benders.h"
32 #include "scip/pub_lp.h"
33 #include "scip/pub_message.h"
34 #include "scip/pub_misc.h"
35 #include "scip/pub_misc_linear.h"
36 #include "scip/pub_nlp.h"
37 #include "scip/pub_var.h"
38 #include "scip/scip_benders.h"
39 #include "scip/scip_cons.h"
40 #include "scip/scip_general.h"
41 #include "scip/scip_lp.h"
42 #include "scip/scip_mem.h"
43 #include "scip/scip_message.h"
44 #include "scip/scip_nlp.h"
45 #include "scip/scip_nlpi.h"
46 #include "scip/scip_numerics.h"
47 #include "scip/scip_param.h"
48 #include "scip/scip_prob.h"
49 #include "scip/scip_solvingstats.h"
50 #include "scip/scip_timing.h"
51 #include "scip/scip_var.h"
52 
53 #define BENDERSCUT_NAME "feasalt"
54 #define BENDERSCUT_DESC "Alternative feasibility cuts for Benders' decomposition"
55 #define BENDERSCUT_PRIORITY 10001
56 #define BENDERSCUT_LPCUT TRUE
57 
58 #define SCIP_DEFAULT_DISPLAYFREQ 20
59 #define SLACKVAR_NAME "##bendersslackvar" /** the name for the Benders' slack variables added to each
60  * constraints in the subproblems */
61 
62 struct SCIP_BenderscutData
63 {
64  SCIP_NLPI* nlpi; /**< nlpi used to create the nlpi problem */
65  SCIP_NLPIPROBLEM* nlpiprob; /**< nlpi problem representing the convex NLP relaxation */
66  SCIP_HASHMAP* var2idx; /**< mapping the variable to the index in the NLPI problem */
67  SCIP_HASHMAP* row2idx; /**< mapping the rows to the index in the NLPI problem */
68  SCIP_VAR** nlpivars; /**< the variables in the NLPI problem */
69  SCIP_NLROW** nlpirows; /**< the rows in the NLPI problem */
70  int nlpinvars; /**< the number of variables in the NPLI problem */
71  int nlpinrows; /**< the number of rows in the NLPI problem */
72  int nlpinslackvars; /**< the number of slack variables in the NLPI problem */
73  int nlpiprobsubprob; /**< the index of the subproblem that the nonlinear problem belongs to */
74 
75  SCIP_Real* slackvarlbs; /**< an array of zeros for the slack variable lower bounds*/
76  SCIP_Real* slackvarubs; /**< an array of infinity for the slack variable upper bounds*/
77  int* slackvarinds; /**< array of indices for the slack variables */
78 };
79 
80 /*
81  * Local methods
82  */
83 
84 /** frees the non linear problem */
85 static
87  SCIP* masterprob, /**< the SCIP instance of the master problem */
88  SCIP* subproblem, /**< the SCIP instance of the pricing problem */
89  SCIP_BENDERSCUT* benderscut /**< the Benders' decomposition structure */
90  )
91 {
92  SCIP_BENDERSCUTDATA* benderscutdata;
93 
94  assert(masterprob != NULL);
95  assert(subproblem != 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(masterprob, &benderscutdata->slackvarinds, benderscutdata->nlpinvars);
106  SCIPfreeBlockMemoryArray(masterprob, &benderscutdata->slackvarubs, benderscutdata->nlpinvars);
107  SCIPfreeBlockMemoryArray(masterprob, &benderscutdata->slackvarlbs, benderscutdata->nlpinvars);
108  SCIPfreeBlockMemoryArray(masterprob, &benderscutdata->nlpirows, benderscutdata->nlpinrows);
109  SCIPfreeBlockMemoryArray(masterprob, &benderscutdata->nlpivars, benderscutdata->nlpinvars);
110  SCIPhashmapFree(&benderscutdata->row2idx);
111  SCIPhashmapFree(&benderscutdata->var2idx);
112 
113  SCIP_CALL( SCIPfreeNlpiProblem(subproblem, 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_NLPSOLSTAT nlpsolstat;
137 
138  assert(scip != NULL);
139  assert(benderscutdata != NULL);
140 
141  (*success) = TRUE;
142 
143  SCIP_CALL( SCIPsolveNlpi(scip, benderscutdata->nlpi, benderscutdata->nlpiprob, .iterlimit = 3000) ); /*lint !e666*/
144  SCIPdebugMsg(scip, "NLP solstat = %d\n", SCIPgetNlpiSolstat(scip, benderscutdata->nlpi, benderscutdata->nlpiprob));
145 
146  nlpsolstat = SCIPgetNlpiSolstat(scip, benderscutdata->nlpi, benderscutdata->nlpiprob);
147 
148  /* if the feasibility NLP is not feasible, then it is not possible to generate a Benders' cut. This is also an error,
149  * since the NLP should always be feasible. In debug mode, an ABORT will be thrown.
150  */
151  if( nlpsolstat > SCIP_NLPSOLSTAT_FEASIBLE )
152  (*success) = FALSE;
153 
154  return SCIP_OKAY;
155 }
156 
157 /** builds the non-linear problem to resolve to generate a cut for the infeasible subproblem */
158 static
160  SCIP* masterprob, /**< the SCIP instance of the master problem */
161  SCIP* subproblem, /**< the SCIP instance of the pricing problem */
162  SCIP_BENDERSCUT* benderscut /**< the benders' decomposition cut method */
163  )
164 {
165  SCIP_BENDERSCUTDATA* benderscutdata;
166  SCIP_Real* obj;
167  int i;
168 
169  assert(masterprob != NULL);
170 
171  benderscutdata = SCIPbenderscutGetData(benderscut);
172  assert(benderscutdata != NULL);
173 
174  /* first freeing the non-linear problem if it exists */
175  SCIP_CALL( freeNonlinearProblem(masterprob, subproblem, benderscut) );
176 
177  assert(benderscutdata->nlpi == NULL);
178  assert(benderscutdata->nlpiprob == NULL);
179 
180  benderscutdata->nlpinvars = SCIPgetNVars(subproblem);
181  benderscutdata->nlpinrows = SCIPgetNNLPNlRows(subproblem);
182  benderscutdata->nlpi = SCIPgetNlpis(subproblem)[0];
183  assert(benderscutdata->nlpi != NULL);
184 
185  SCIP_CALL( SCIPhashmapCreate(&benderscutdata->var2idx, SCIPblkmem(masterprob), benderscutdata->nlpinvars) );
186  SCIP_CALL( SCIPhashmapCreate(&benderscutdata->row2idx, SCIPblkmem(masterprob), benderscutdata->nlpinrows) );
187 
188  SCIP_CALL( SCIPduplicateBlockMemoryArray(masterprob, &benderscutdata->nlpivars, SCIPgetVars(subproblem),
189  benderscutdata->nlpinvars) ); /*lint !e666*/
190  SCIP_CALL( SCIPduplicateBlockMemoryArray(masterprob, &benderscutdata->nlpirows, SCIPgetNLPNlRows(subproblem),
191  benderscutdata->nlpinrows) ); /*lint !e666*/
192 
193  SCIP_CALL( SCIPcreateNlpiProblemFromNlRows(subproblem, benderscutdata->nlpi, &benderscutdata->nlpiprob, "benders-feascutalt-nlp",
194  SCIPgetNLPNlRows(subproblem), benderscutdata->nlpinrows, benderscutdata->var2idx, benderscutdata->row2idx, NULL, SCIPinfinity(subproblem), FALSE,
195  FALSE) );
196 
197  /* storing the slack variable bounds and indices */
198  SCIP_CALL( SCIPallocBufferArray(masterprob, &obj, benderscutdata->nlpinvars) );
199 
200  SCIP_CALL( SCIPallocBlockMemoryArray(masterprob, &benderscutdata->slackvarlbs, benderscutdata->nlpinvars) );
201  SCIP_CALL( SCIPallocBlockMemoryArray(masterprob, &benderscutdata->slackvarubs, benderscutdata->nlpinvars) );
202  SCIP_CALL( SCIPallocBlockMemoryArray(masterprob, &benderscutdata->slackvarinds, benderscutdata->nlpinvars) );
203  benderscutdata->nlpinslackvars = 0;
204  for( i = 0; i < benderscutdata->nlpinvars; i++ )
205  {
206  if( strstr(SCIPvarGetName(benderscutdata->nlpivars[i]), SLACKVAR_NAME) )
207  {
208  benderscutdata->slackvarlbs[benderscutdata->nlpinslackvars] = 0.0;
209  benderscutdata->slackvarubs[benderscutdata->nlpinslackvars] = SCIPinfinity(subproblem);
210  benderscutdata->slackvarinds[benderscutdata->nlpinslackvars] = SCIPhashmapGetImageInt(benderscutdata->var2idx,
211  (void*)benderscutdata->nlpivars[i]);
212 
213  obj[benderscutdata->nlpinslackvars] = 1.0;
214 
215  benderscutdata->nlpinslackvars++;
216  }
217  }
218 
219  /* setting the objective function */
220  SCIP_CALL( SCIPsetNlpiObjective(subproblem, benderscutdata->nlpi, benderscutdata->nlpiprob, benderscutdata->nlpinslackvars,
221  benderscutdata->slackvarinds, obj, NULL, 0.0) );
222 
223  /* unfixing the slack variables */
224  SCIP_CALL( SCIPchgNlpiVarBounds(subproblem, benderscutdata->nlpi, benderscutdata->nlpiprob, benderscutdata->nlpinslackvars,
225  benderscutdata->slackvarinds, benderscutdata->slackvarlbs, benderscutdata->slackvarubs) );
226 
227  SCIPfreeBufferArray(masterprob, &obj);
228 
229  return SCIP_OKAY;
230 }
231 
232 /** updates the non-linear problem that is resolved to generate a cut for the infeasible subproblem */
233 static
235  SCIP* subproblem, /**< the SCIP instance of the pricing problem */
236  SCIP_BENDERSCUT* benderscut /**< the benders' decomposition cut method */
237  )
238 {
239  SCIP_BENDERSCUTDATA* benderscutdata;
240 
241  assert(subproblem != NULL);
242  assert(benderscut != NULL);
243 
244  benderscutdata = SCIPbenderscutGetData(benderscut);
245  assert(benderscutdata != NULL);
246  assert(benderscutdata->nlpi != NULL);
247  assert(benderscutdata->nlpiprob != NULL);
248  assert(benderscutdata->var2idx != NULL);
249  assert(benderscutdata->row2idx != NULL);
250 
251  /* setting the variable bounds to that from the current subproblem */
252  SCIP_CALL( SCIPupdateNlpiProblem(subproblem, benderscutdata->nlpi, benderscutdata->nlpiprob, benderscutdata->var2idx,
253  benderscutdata->nlpivars, benderscutdata->nlpinvars, SCIPinfinity(subproblem)) );
254 
255  /* unfixing the slack variables */
256  SCIP_CALL( SCIPchgNlpiVarBounds(subproblem, benderscutdata->nlpi, benderscutdata->nlpiprob, benderscutdata->nlpinslackvars,
257  benderscutdata->slackvarinds, benderscutdata->slackvarlbs, benderscutdata->slackvarubs) );
258 
259  return SCIP_OKAY;
260 }
261 
262 /** generates and applies Benders' cuts */
263 static
265  SCIP* masterprob, /**< the SCIP instance of the master problem */
266  SCIP* subproblem, /**< the SCIP instance of the pricing problem */
267  SCIP_BENDERS* benders, /**< the benders' decomposition */
268  SCIP_BENDERSCUT* benderscut, /**< the benders' decomposition cut method */
269  SCIP_SOL* sol, /**< primal CIP solution */
270  int probnumber, /**< the number of the pricing problem */
271  SCIP_BENDERSENFOTYPE type, /**< the enforcement type calling this function */
272  SCIP_RESULT* result /**< the result from solving the subproblems */
273  )
274 {
275  SCIP_BENDERSCUTDATA* benderscutdata;
276  SCIP_Real* primalvals;
277  SCIP_Real* consdualvals;
278  SCIP_Real* varlbdualvals;
279  SCIP_Real* varubdualvals;
280  SCIP_Real obj;
281  char cutname[SCIP_MAXSTRLEN];
282  SCIP_Bool success;
283 #ifdef SCIP_EVENMOREDEBUG
284  int i;
285 #endif
286 
287  assert(masterprob != NULL);
288  assert(subproblem != NULL);
289  assert(benders != NULL);
290  assert(result != NULL);
291 
292  benderscutdata = SCIPbenderscutGetData(benderscut);
293  assert(benderscutdata != NULL);
294 
295  /* creating or updating the NLPI problem */
296  if( benderscutdata->nlpiprob == NULL || benderscutdata->nlpiprobsubprob != probnumber )
297  {
298  SCIP_CALL( createAuxiliaryNonlinearSubproblem(masterprob, subproblem, benderscut) );
299  benderscutdata->nlpiprobsubprob = probnumber;
300  }
301  else
302  {
303  SCIP_CALL( updateAuxiliaryNonlinearSubproblem(subproblem, benderscut) );
304  }
305 
306  /* solving the NLPI problem to get the minimum infeasible solution */
307  SCIP_CALL( solveFeasibilityNonlinearSubproblem(subproblem, benderscutdata, &success) );
308 
309  if( !success )
310  {
311  (*result) = SCIP_DIDNOTFIND;
312  SCIPdebugMsg(masterprob, "Error in generating Benders' feasibility cut for problem %d. "
313  "The feasibility subproblem failed to solve with a feasible solution.\n", probnumber);
314  return SCIP_OKAY;
315  }
316 
317  /* getting the solution from the NLPI problem */
318  SCIP_CALL( SCIPgetNlpiSolution(subproblem, benderscutdata->nlpi, benderscutdata->nlpiprob, &primalvals, &consdualvals,
319  &varlbdualvals, &varubdualvals, &obj) );
320 
321 #ifdef SCIP_EVENMOREDEBUG
322  SCIPdebugMsg(masterprob, "NLP Feasibility problem solution.\n");
323  SCIPdebugMsg(masterprob, "Objective: %g.\n", obj);
324  for( i = 0; i < benderscutdata->nlpinvars; i++ )
325  {
326  int varindex;
327  SCIP_Real solval;
328  if( SCIPhashmapExists(benderscutdata->var2idx, benderscutdata->nlpivars[i]) )
329  {
330  varindex = SCIPhashmapGetImageInt(benderscutdata->var2idx, benderscutdata->nlpivars[i]);
331  solval = primalvals[varindex];
332 
333  if( !SCIPisZero(masterprob, solval) )
334  {
335  SCIPdebugMsg(masterprob, "%s (obj: %g): %20g\n", SCIPvarGetName(benderscutdata->nlpivars[i]),
336  SCIPvarGetObj(benderscutdata->nlpivars[i]), solval);
337  }
338  }
339  }
340 #endif
341 
342  /* setting the name of the generated cut */
343  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "altfeasibilitycut_%d_%" SCIP_LONGINT_FORMAT, probnumber,
344  SCIPbenderscutGetNFound(benderscut) );
345 
346  /* generating a Benders' decomposition cut using the classical optimality cut methods */
347  SCIP_CALL( SCIPgenerateAndApplyBendersOptCut(masterprob, subproblem, benders, benderscut,
348  sol, probnumber, cutname, obj, primalvals, consdualvals, varlbdualvals, varubdualvals, benderscutdata->row2idx,
349  benderscutdata->var2idx, type, FALSE, TRUE, result) );
350 
351  if( (*result) == SCIP_CONSADDED )
352  {
353  if( SCIPisInfinity(masterprob, -SCIPgetDualbound(masterprob))
354  && SCIPbenderscutGetNFound(benderscut) % SCIP_DEFAULT_DISPLAYFREQ == 0 )
355  {
356  if( SCIPgetStage(masterprob) == SCIP_STAGE_SOLVING )
357  {
360  "Benders' Decomposition: Master problem LP is infeasible. Added %" SCIP_LONGINT_FORMAT " feasibility cuts.\n",
361  SCIPbenderscutGetNFound(benderscut));
362  }
363  }
364  SCIPdebugMsg(masterprob, "Constraint <%s> has been added to the master problem.\n", cutname);
365  }
366 
367  return SCIP_OKAY;
368 }
369 
370 /*
371  * Callback methods of Benders' decomposition cuts
372  */
373 
374 /** deinitialization method of Benders' decomposition cuts (called before transformed problem is freed) */
375 static
376 SCIP_DECL_BENDERSCUTEXIT(benderscutExitFeasalt)
377 { /*lint --e{715}*/
378  assert( benderscut != NULL );
379  assert( strcmp(SCIPbenderscutGetName(benderscut), BENDERSCUT_NAME) == 0 );
380 
381  return SCIP_OKAY;
382 }
383 
384 /** destructor of the Benders' decomposition cut to free user data (called when SCIP is exiting) */
385 static
386 SCIP_DECL_BENDERSCUTFREE(benderscutFreeFeasalt)
387 { /*lint --e{715}*/
388  SCIP_BENDERSCUTDATA* benderscutdata;
389 
390  assert(scip != NULL);
391  assert(benderscut != NULL);
392 
393  benderscutdata = SCIPbenderscutGetData(benderscut);
394  assert(benderscutdata != NULL);
395 
396  SCIPfreeBlockMemory(scip, &benderscutdata);
397 
398  return SCIP_OKAY;
399 }
400 
401 /** execution method of Benders' decomposition cuts */
402 static
403 SCIP_DECL_BENDERSCUTEXEC(benderscutExecFeasalt)
404 { /*lint --e{715}*/
405  SCIP* subproblem;
406  SCIP_Bool nlprelaxation;
407 
408  assert(scip != NULL);
409  assert(benders != NULL);
410  assert(benderscut != NULL);
411  assert(result != NULL);
412  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
413 
414  subproblem = SCIPbendersSubproblem(benders, probnumber);
415 
416  /* setting a flag to indicate whether the NLP relaxation should be used to generate cuts */
417  nlprelaxation = SCIPisNLPConstructed(subproblem) && SCIPgetNNlpis(subproblem)
419 
420  /* only generate feasibility cuts if the subproblem LP or NLP is infeasible,
421  * since we use the farkas proof from the LP or the dual solution of the NLP to construct the feasibility cut
422  */
423  if( SCIPgetStage(subproblem) == SCIP_STAGE_SOLVING &&
424  (nlprelaxation && (SCIPgetNLPSolstat(subproblem) == SCIP_NLPSOLSTAT_LOCINFEASIBLE || SCIPgetNLPSolstat(subproblem) == SCIP_NLPSOLSTAT_GLOBINFEASIBLE)) )
425  {
426  /* generating a cut for a given subproblem */
427  SCIP_CALL( generateAndApplyBendersCuts(scip, subproblem, benders, benderscut, sol, probnumber, type, result) );
428 
429  /* TODO this was in benderscutExitFeasalt, but freeNonlinearProblem now needs subproblem, which didn't seem to be easily available there */
430  /* freeing the non-linear problem information */
431  SCIP_CALL( freeNonlinearProblem(scip, subproblem, benderscut) );
432  }
433 
434  return SCIP_OKAY;
435 }
436 
437 
438 /*
439  * Benders' decomposition cuts specific interface methods
440  */
441 
442 /** creates the Alternative Feasibility Benders' decomposition cuts and includes it in SCIP */
444  SCIP* scip, /**< SCIP data structure */
445  SCIP_BENDERS* benders /**< Benders' decomposition */
446  )
447 {
448  SCIP_BENDERSCUT* benderscut;
449  SCIP_BENDERSCUTDATA* benderscutdata;
450 
451  assert(benders != NULL);
452 
453  benderscut = NULL;
454 
455  SCIP_CALL( SCIPallocBlockMemory(scip, &benderscutdata) );
456  BMSclearMemory(benderscutdata);
457  benderscutdata->nlpiprobsubprob = -1;
458 
459  /* include Benders' decomposition cuts */
461  BENDERSCUT_PRIORITY, BENDERSCUT_LPCUT, benderscutExecFeasalt, benderscutdata) );
462 
463  /* set non fundamental callbacks via setter functions */
464  SCIP_CALL( SCIPsetBenderscutFree(scip, benderscut, benderscutFreeFeasalt) );
465  SCIP_CALL( SCIPsetBenderscutExit(scip, benderscut, benderscutExitFeasalt) );
466 
467  assert(benderscut != NULL);
468 
469  return SCIP_OKAY;
470 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:101
int SCIPgetNNLPNlRows(SCIP *scip)
Definition: scip_nlp.c:332
const char * SCIPbenderscutGetName(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:483
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)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip_nlp.c:101
internal miscellaneous methods for linear constraints
public methods for SCIP parameter handling
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
#define BENDERSCUT_NAME
struct SCIP_BenderscutData SCIP_BENDERSCUTDATA
public methods for memory management
SCIP_BENDERSCUTDATA * SCIPbenderscutGetData(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:394
#define SCIP_MAXSTRLEN
Definition: def.h:293
public methods for timing
SCIP_NLPSOLSTAT SCIPgetNLPSolstat(SCIP *scip)
Definition: scip_nlp.c:532
#define BENDERSCUT_DESC
SCIP_RETCODE SCIPprintDisplayLine(SCIP *scip, FILE *file, SCIP_VERBLEVEL verblevel, SCIP_Bool endline)
#define FALSE
Definition: def.h:87
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
public methods for Benders&#39; decomposition
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE
Definition: type_benders.h:42
Generates a standard Benders&#39; decomposition optimality cut.
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
SCIP_NLPI ** SCIPgetNlpis(SCIP *scip)
Definition: scip_nlpi.c:177
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
#define BENDERSCUT_PRIORITY
public methods for SCIP variables
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_Longint SCIPbenderscutGetNFound(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:534
public methods for numerical tolerances
public functions to work with algebraic expressions
public methods for querying solving statistics
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3363
int SCIPgetNNlpis(SCIP *scip)
Definition: scip_nlpi.c:190
static SCIP_DECL_BENDERSCUTEXIT(benderscutExitFeasalt)
public methods for NLPI solver interfaces
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:96
SCIP_BENDERSSUBTYPE SCIPbendersGetSubproblemType(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6292
static SCIP_RETCODE solveFeasibilityNonlinearSubproblem(SCIP *scip, SCIP_BENDERSCUTDATA *benderscutdata, SCIP_Bool *success)
public methods for Benders decomposition
SCIP_RETCODE SCIPupdateNlpiProblem(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2nlpiidx, SCIP_VAR **nlpivars, int nlpinvars, SCIP_Real cutoffbound)
Definition: scip_nlpi.c:720
enum SCIP_NlpSolStat SCIP_NLPSOLSTAT
Definition: type_nlpi.h:159
SCIP_Real SCIPgetDualbound(SCIP *scip)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
#define BENDERSCUT_LPCUT
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17251
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3048
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_RETCODE SCIPsetBenderscutExit(SCIP *scip, SCIP_BENDERSCUT *benderscut, SCIP_DECL_BENDERSCUTEXIT((*benderscutexit)))
SCIP_NLROW ** SCIPgetNLPNlRows(SCIP *scip)
Definition: scip_nlp.c:310
static SCIP_RETCODE freeNonlinearProblem(SCIP *masterprob, SCIP *subproblem, SCIP_BENDERSCUT *benderscut)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
public methods for constraint handler plugins and constraints
public methods for NLP management
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)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:84
public methods for LP management
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17758
SCIP_RETCODE SCIPincludeBenderscutFeasalt(SCIP *scip, SCIP_BENDERS *benders)
SCIP * SCIPbendersSubproblem(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:5949
Constraint handler for linear constraints in their most general form, .
SCIP_RETCODE SCIPcreateNlpiProblemFromNlRows(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM **nlpiprob, const char *name, SCIP_NLROW **nlrows, int nnlrows, SCIP_HASHMAP *var2idx, SCIP_HASHMAP *nlrow2idx, SCIP_Real *nlscore, SCIP_Real cutoffbound, SCIP_Bool setobj, SCIP_Bool onlyconvex)
Definition: scip_nlpi.c:434
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
#define SCIPsolveNlpi(scip, nlpi,...)
Definition: scip_nlpi.h:199
#define BMSclearMemory(ptr)
Definition: memory.h:122
int SCIPbendersGetNSubproblems(SCIP_BENDERS *benders)
Definition: benders.c:5939
public methods for the LP relaxation, rows and columns
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1990
public methods for nonlinear relaxation
public methods for Benders&#39; decomposition cuts
general public methods
public methods for message output
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1945
#define SCIP_Real
Definition: def.h:177
Alternative feasibility cuts for Benders&#39; decomposition.
public methods for message handling
static SCIP_DECL_BENDERSCUTEXEC(benderscutExecFeasalt)
static SCIP_RETCODE createAuxiliaryNonlinearSubproblem(SCIP *masterprob, SCIP *subproblem, SCIP_BENDERSCUT *benderscut)
SCIP_RETCODE SCIPsetBenderscutFree(SCIP *scip, SCIP_BENDERSCUT *benderscut, SCIP_DECL_BENDERSCUTFREE((*benderscutfree)))
#define SLACKVAR_NAME
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIPallocBlockMemory(scip, subsol))
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3221
static SCIP_RETCODE updateAuxiliaryNonlinearSubproblem(SCIP *subproblem, SCIP_BENDERSCUT *benderscut)
public methods for global and local (sub)problems
#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)