benders_gcg.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-2018 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 email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 /* #define SCIP_DEBUG */
23 #include <assert.h>
24 #include <string.h>
25 
26 #include "benders_gcg.h"
27 
28 #include "gcg.h"
29 
30 #include "relax_gcg.h"
31 #include "scip_misc.h"
32 #include "pub_gcgvar.h"
33 
34 #include "scip/cons_linear.h"
35 #include "scip/pub_var.h"
36 #include "scip/pub_benders.h"
37 #include "scip/bendersdefcuts.h"
38 
39 #define BENDERS_NAME "gcg"
40 #define BENDERS_DESC "Benders' decomposition for the Generic Column Generation package"
41 #define BENDERS_PRIORITY 1000
42 #define BENDERS_CUTLP TRUE
43 #define BENDERS_CUTPSEUDO TRUE
44 #define BENDERS_CUTRELAX TRUE
45 #define BENDERS_SHAREAUXVARS FALSE
47 #define LARGE_VALUE 10000
49 /*
50  * Data structures
51  */
52 
55 {
56  SCIP* origprob;
57  SCIP_SOL* relaxsol;
58 };
59 
60 /*
61  * Local methods
62  */
63 
64 /* returns the objective coefficient for the given variable */
65 static
66 SCIP_Real varGetObj(
67  SCIP_VAR* var
68  )
69 {
70  SCIP_VAR* origvar;
71  assert(var != NULL);
72 
73  origvar = GCGpricingVarGetOrigvars(var)[0];
74 
75  if( GCGoriginalVarIsLinking(origvar) )
76  return 0.0;
77  else
78  return SCIPvarGetObj(origvar);
79 }
80 
81 /* Initializes the objective function for all subproblems. */
82 static
83 SCIP_RETCODE setSubproblemObjs(
84  SCIP_BENDERS* benders,
85  int probnumber
86  )
87 {
88  SCIP* subproblem;
89  SCIP_VAR** probvars;
90  int nprobvars;
91  int i;
92 
93  assert(benders != NULL);
94 
95  /* changing the variable */
96  subproblem = SCIPbendersSubproblem(benders, probnumber);
97  assert(subproblem != NULL);
98 
99  probvars = SCIPgetVars(subproblem);
100  nprobvars = SCIPgetNVars(subproblem);
101 
102  for( i = 0; i < nprobvars; i++ )
103  {
104  assert(GCGvarGetBlock(probvars[i]) == probnumber);
105  assert(GCGoriginalVarIsLinking(GCGpricingVarGetOrigvars(probvars[i])[0]) || (GCGvarGetBlock(GCGpricingVarGetOrigvars(probvars[i])[0]) == probnumber));
106 
107  SCIP_CALL( SCIPchgVarObj(subproblem, probvars[i], varGetObj(probvars[i])));
108 
109  SCIPdebugMessage("pricingobj var <%s> %f\n", SCIPvarGetName(probvars[i]), varGetObj(probvars[i]));
110  }
111 
112  return SCIP_OKAY;
113 }
114 
125 static
127  SCIP* origprob,
128  SCIP* masterprob,
129  SCIP_BENDERS* benders,
130  SCIP_SOL* origsol,
131  SCIP_VAR** vars,
132  SCIP_Real* vals,
134  int nvars,
135  SCIP_Bool* success
136  )
137 {
138  SCIP_VAR** origvars;
139  SCIP_Real val;
140  int norigvars;
141  int i;
142 
143  assert(origprob != NULL);
144  assert(masterprob != NULL);
145  assert(benders != NULL);
146  assert(vars != NULL);
147 
148  (*success) = TRUE;
149 
150  /* looping through all variables to update the values in the original solution */
151  for( i = 0; i < nvars; i++ )
152  {
153  norigvars = GCGpricingVarGetNOrigvars(vars[i]);
154  if( norigvars > 0 )
155  {
156  SCIP_VAR* mastervar;
157 
158  origvars = GCGpricingVarGetOrigvars(vars[i]);
159 
160  /* all variables should be associated with a single original variable. This is because no reformulation has
161  * been performed.
162  * TODO: This appears not to be true. Need to find out why multiple original problem variables are associated
163  * with a pricing variable. Currently the first original variable is used.
164  */
165  /* assert(norigvars == 1); */
166  assert(GCGvarIsPricing(vars[i]));
167 
168  /* for all variables that are from the subproblems, they are set to their bounds if the solution is being
169  * created to identify branching candidates. */
170  if( vals == NULL )
171  {
172  if( SCIPisNegative(origprob, SCIPvarGetObj(origvars[0])) )
173  {
174  val = SCIPvarGetLbGlobal(origvars[0]);
175  if( SCIPisInfinity(origprob, -val) )
176  val = -LARGE_VALUE;
177  }
178  else
179  {
180  val = SCIPvarGetUbGlobal(origvars[0]);
181  if( SCIPisInfinity(origprob, val) )
182  val = LARGE_VALUE;
183  }
184  }
185  else
186  val = vals[i];
187 
188  /* identifying whether the variable is a master problem variable. The variable is a master problem variable if
189  * there is a mapping from the subproblem to the master problem. If a mapping exists, then the variable value
190  * is not updated in the master problem
191  */
192  mastervar = NULL;
193  SCIP_CALL( SCIPgetBendersMasterVar(masterprob, benders, vars[i], &mastervar) );
194  if( SCIPisInfinity(origprob, val) || SCIPisInfinity(origprob, -val) )
195  {
196  (*success) = FALSE;
197  return SCIP_OKAY;
198  }
199 
200  SCIPdebugMsg(masterprob, "setting the value of <%s> (dw variable <%s>) to %g in the original solution.\n",
201  SCIPvarGetName(origvars[0]), SCIPvarGetName(vars[i]), val);
202 
203  /* only update the solution value if the master problem variable does not exist. */
204  if( mastervar == NULL )
205  {
206  SCIP_CALL( SCIPsetSolVal(origprob, origsol, origvars[0], val) );
207  }
208  }
209  }
210 
211  return SCIP_OKAY;
212 }
213 
215 static
217  SCIP* origprob,
218  SCIP* masterprob,
219  SCIP_BENDERS* benders,
220  SCIP_SOL* origsol,
221  SCIP_VAR** vars,
222  SCIP_Real* vals,
223  int nvars
224  )
225 {
226  SCIP_VAR** origvars;
227  int norigvars;
228  int i;
229 
230 #ifndef NDEBUG
231  SCIP_Real* origvals;
232 #endif
233 
234  assert(origprob != NULL);
235  assert(masterprob != NULL);
236  assert(benders != NULL);
237  assert(vars != NULL);
238  assert(vals != NULL);
239 
240  /* looping through all variables to update the values in the original solution */
241  for( i = 0; i < nvars; i++ )
242  {
243  norigvars = GCGmasterVarGetNOrigvars(vars[i]);
244  if( norigvars > 0 )
245  {
246  origvars = GCGmasterVarGetOrigvars(vars[i]);
247 
248 #ifndef NDEBUG
249  origvals = GCGmasterVarGetOrigvals(vars[i]);
250 #endif
251 
252  /* all master variables should be associated with a single original variable. This is because no reformulation has
253  * been performed. */
254  assert(norigvars == 1);
255  assert(origvals[0] == 1.0);
256  assert(GCGvarIsMaster(vars[i]));
257  assert(!SCIPisInfinity(origprob, vals[i]));
258 
259  SCIPdebugMsg(masterprob, "setting the value of <%s> (master variable <%s>) to %g in the original solution.\n",
260  SCIPvarGetName(origvars[0]), SCIPvarGetName(vars[i]), vals[i]);
261 
262  /* only update the solution value of master variables. */
263  SCIP_CALL( SCIPsetSolVal(origprob, origsol, origvars[0], vals[i]) );
264  }
265  }
266  return SCIP_OKAY;
267 }
268 
270 static
272  SCIP* masterprob,
273  SCIP_BENDERS* benders,
274  SCIP_SOL* sol,
275  SCIP_Bool artificial
277  )
278 {
279  SCIP* origprob;
280  SCIP* subproblem;
281  SCIP_BENDERSDATA* bendersdata;
282  SCIP_SOL* origsol;
283  SCIP_SOL* bestsol;
284  SCIP_VAR** vars;
285  SCIP_Real* vals;
286  int nsubproblems;
287  int nvars;
288  int i;
289  SCIP_Bool stored;
290  SCIP_Bool success;
291 
292  assert(masterprob != NULL);
293  assert(benders != NULL);
294 
295  bendersdata = SCIPbendersGetData(benders);
296 
297  assert(bendersdata != NULL);
298 
299  origprob = bendersdata->origprob;
300 
301  success = TRUE;
302 
303  /* creating the original problem */
304  SCIP_CALL( SCIPcreateSol(origprob, &origsol, GCGrelaxGetProbingheur(origprob)) );
305 
306  /* setting the values of the master variables in the original solution */
307 
308  /* getting the variable data for the master variables */
309  SCIP_CALL( SCIPgetVarsData(masterprob, &vars, &nvars, NULL, NULL, NULL, NULL) );
310  assert(vars != NULL);
311 
312  /* getting the best solution from the master problem */
313  SCIP_CALL( SCIPallocBufferArray(masterprob, &vals, nvars) );
314  SCIP_CALL( SCIPgetSolVals(masterprob, sol, nvars, vars, vals) );
315 
316  /* setting the values using the master problem solution */
317  SCIP_CALL( setOriginalProblemMasterValues(origprob, masterprob, benders, origsol, vars, vals, nvars) );
318 
319  /* freeing the values buffer array for use for the pricing problems */
320  SCIPfreeBufferArray(masterprob, &vals);
321 
322  /* setting the values of the subproblem variables in the original solution */
323  nsubproblems = SCIPbendersGetNSubproblems(benders);
324 
325  /* looping through all subproblems */
326  for( i = 0; i < nsubproblems; i++ )
327  {
328  /* it is only possible to use the subproblem solutions if the subproblems are enabled. The subproblems are
329  * disabled if they have been merged into the master problem.
330  */
331  if( SCIPbendersSubproblemIsEnabled(benders, i) )
332  {
333  subproblem = SCIPbendersSubproblem(benders, i);
334 
335  /* getting the variable data for the master variables */
336  SCIP_CALL( SCIPgetVarsData(subproblem, &vars, &nvars, NULL, NULL, NULL, NULL) );
337  assert(vars != NULL);
338 
339  /* getting the best solution from the master problem */
340  bestsol = SCIPgetBestSol(subproblem);
341 #ifdef SCIP_DEBUG
342  SCIP_CALL( SCIPprintSol(subproblem, bestsol, NULL, FALSE) );
343 #endif
344 
345  /* the branching candidates come from the master problem solution. However, we need a full solution to pass to the
346  * original problem to find the branching candidate. So the subproblem variables are set to their bounds, creating
347  * a possibly infeasible solution, but with the fractional master problem variables.
348  *
349  * It may occur that the subproblem has not been solved yet, this can happen if the subproblem is independent.
350  * In this case, an artificial solution is created.
351  */
352  if( artificial || SCIPgetStage(subproblem) == SCIP_STAGE_PROBLEM )
353  {
354  /* setting the values of the subproblem variables to their bounds. */
355  SCIP_CALL( setOriginalProblemPricingValues(origprob, masterprob, benders, origsol, vars, NULL, nvars, &success) );
356  }
357  else
358  {
359  SCIP_CALL( SCIPallocBufferArray(subproblem, &vals, nvars) );
360  SCIP_CALL( SCIPgetSolVals(subproblem, bestsol, nvars, vars, vals) );
361 
362  /* setting the values using the master problem solution */
363  SCIP_CALL( setOriginalProblemPricingValues(origprob, masterprob, benders, origsol, vars, vals, nvars, &success) );
364 
365  /* freeing the values buffer array for use for the pricing problems */
366  SCIPfreeBufferArray(subproblem, &vals);
367 
368  if( !success )
369  break;
370  }
371  }
372  }
373 
374  /* if the values were not set correctly, then the solution is not updated. This should only happen when the timelimit
375  * has been exceeded.
376  */
377  if( !success )
378  {
379  SCIP_CALL( SCIPfreeSol(origprob, &origsol) );
380  return SCIP_OKAY;
381  }
382 
383 #ifdef SCIP_DEBUG
384  SCIPdebugMsg(masterprob, "Original Solution\n");
385  SCIP_CALL( SCIPprintSol(origprob, origsol, NULL, FALSE) );
386 #endif
387 
388  /* if the solution is NULL, then the solution comes from the relaxation. Thus, it should be stored in the
389  * bendersdata. When it is not NULL, then solution comes from a heuristic. So this solution should be passed to the
390  * solution storage. */
391  if( sol != NULL )
392  {
393 #ifdef SCIP_DEBUG
394  SCIP_CALL( SCIPtrySol(origprob, origsol, TRUE, TRUE, TRUE, TRUE, TRUE, &stored) );
395 #else
396  SCIP_CALL( SCIPtrySol(origprob, origsol, FALSE, FALSE, TRUE, TRUE, TRUE, &stored) );
397 #endif
398  if( !stored )
399  {
400  SCIP_CALL( SCIPcheckSolOrig(origprob, origsol, &stored, TRUE, TRUE) );
401  }
402 
406  SCIP_CALL( SCIPfreeSol(origprob, &origsol) );
407 
408  if( stored )
409  SCIPdebugMessage(" updated current best primal feasible solution.\n");
410  }
411  else
412  {
413  if( bendersdata->relaxsol != NULL )
414  {
415  SCIP_CALL( SCIPfreeSol(origprob, &bendersdata->relaxsol) );
416  }
417 
418  bendersdata->relaxsol = origsol;
419  }
420 
421  return SCIP_OKAY;
422 }
423 
425 static
427  SCIP* masterprob,
428  SCIP_BENDERS* benders,
429  int probnumber
430  )
431 {
432  SCIP* subproblem;
433  SCIP_HASHMAP* varmap;
434  SCIP_HASHMAP* consmap;
435  SCIP_VAR** vars;
436  int nvars;
437  int i;
438 
439  assert(masterprob != NULL);
440  assert(benders != NULL);
441 
442  subproblem = SCIPbendersSubproblem(benders, probnumber);
443 
444  /* allocating the memory for the variable and constraint hashmaps */
445  SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(masterprob), SCIPgetNVars(subproblem)) );
446  SCIP_CALL( SCIPhashmapCreate(&consmap, SCIPblkmem(masterprob), SCIPgetNConss(subproblem)) );
447 
448  SCIP_CALL( SCIPmergeBendersSubproblemIntoMaster(masterprob, benders, varmap, consmap, probnumber) );
449 
450  SCIP_CALL( SCIPgetVarsData(subproblem, &vars, &nvars, NULL, NULL, NULL, NULL) );
451  /* copying the variable data from the pricing variables to the newly created master variables */
452  for( i = 0; i < nvars; i++ )
453  {
454  SCIP_VAR* mastervar;
455 
456  mastervar = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[i]);
457  SCIP_CALL( GCGcopyPricingvarDataToMastervar(masterprob, vars[i], mastervar) );
458  }
459 
460  /* freeing the variable and constraint hashmaps */
461  SCIPhashmapFree(&varmap);
462  SCIPhashmapFree(&consmap);
463 
464  return SCIP_OKAY;
465 }
466 
472 static
474  SCIP* masterprob,
475  SCIP_BENDERS* benders,
476  int* mergecands,
477  int npriomergecands,
478  int nmergecands,
479  SCIP_Bool* merged
480  )
481 {
482  int i;
483 
484  assert(masterprob != NULL);
485  assert(benders != NULL);
486 
487  (*merged) = FALSE;
488 
489  /* adding the priority merge candidates. If there are no priority candidates, then the first merge candidate is
490  * added.
491  */
492  for( i = 0; i < npriomergecands; i++ )
493  {
494  SCIP_CALL( mergeSubproblemIntoMaster(masterprob, benders, mergecands[i]) );
495  (*merged) = TRUE;
496  }
497 
498  /* if there were no priority candidates and there is a merge candidate, then only a single merge candidate is
499  * merged.
500  */
501  if( !(*merged) && nmergecands > 0 )
502  {
503  assert(npriomergecands == 0);
504 
505  SCIP_CALL( mergeSubproblemIntoMaster(masterprob, benders, mergecands[0]) );
506  (*merged) = TRUE;
507  }
508 
509  return SCIP_OKAY;
510 }
511 
512 /*
513  * Callback methods for Benders' decomposition
514  */
515 
516 /* TODO: Implement all necessary Benders' decomposition methods. The methods with an #if 0 ... #else #define ... are optional */
517 
519 static
520 SCIP_DECL_BENDERSFREE(bendersFreeGcg)
521 { /*lint --e{715}*/
522  SCIP_BENDERSDATA* bendersdata;
523 
524  assert(scip != NULL);
525  assert(benders != NULL);
526 
527  bendersdata = SCIPbendersGetData(benders);
528 
529  if( bendersdata != NULL )
530  {
531  SCIPfreeMemory(scip, &bendersdata);
532  }
533 
534  return SCIP_OKAY;
535 }
536 
538 static
539 SCIP_DECL_BENDERSINITPRE(bendersInitpreGcg)
540 { /*lint --e{715}*/
541  int nsubproblems;
542  int i;
543 
544  assert(scip != NULL);
545  assert(benders != NULL);
546 
547  nsubproblems = SCIPbendersGetNSubproblems(benders);
548 
549  for( i = 0; i < nsubproblems; i++ )
550  {
551  SCIP_CALL( GCGaddDataAuxiliaryVar(scip, SCIPbendersGetAuxiliaryVar(benders, i), i) );
552  }
553 
554  return SCIP_OKAY;
555 }
556 
558 static
559 SCIP_DECL_BENDERSEXITSOL(bendersExitsolGcg)
560 { /*lint --e{715}*/
561  SCIP_BENDERSDATA* bendersdata;
562 
563  assert(scip != NULL);
564  assert(benders != NULL);
565 
566  bendersdata = SCIPbendersGetData(benders);
567 
568  /* freeing the relaxation solution */
569  if( bendersdata->relaxsol != NULL )
570  {
571  SCIP_CALL( SCIPfreeSol(bendersdata->origprob, &bendersdata->relaxsol) );
572  }
573 
574  return SCIP_OKAY;
575 }
576 
578 static
579 SCIP_DECL_BENDERSGETVAR(bendersGetvarGcg)
580 { /*lint --e{715}*/
581  SCIP_VAR* origvar;
582 
583  assert(scip != NULL);
584  assert(benders != NULL);
585  assert(var != NULL);
586  assert(mappedvar != NULL);
587 
588  /* if there is no corresponding master variable for the input variable, then NULL is returned */
589  (*mappedvar) = NULL;
590 
591  /* if the probnumber is -1, then the master variable is requested.
592  * if the probnumber >= 0, then the subproblem variable is requested. */
593  if( probnumber == -1 )
594  {
595  /* getting the original variable for the given pricing variable */
596  origvar = GCGpricingVarGetOrigvars(var)[0];
597 
598  /* checking whether the original variable is associated with any master problem variables. This is identified by
599  * retrieving the number of master variables for the given original variable
600  * NOTE: previously, only the linking variables were master variables. As such, the following check was to find
601  * only the original variables corresponding to linking variables. Since linking constraints, and their associated
602  * variables, are also added to the master problem, then the previous check is not valid.
603  */
604  if( GCGoriginalVarGetNMastervars(origvar) > 0 )
605  {
606  (*mappedvar) = GCGoriginalVarGetMastervars(origvar)[0];
607  }
608  }
609  else
610  {
611  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
612 
613  /* getting the original variable for the given pricing variable */
614  origvar = GCGmasterVarGetOrigvars(var)[0];
615 
616  /* checking whether the original variable is associated with any master problem variables. This is identified by
617  * retrieving the number of master variables for the given original variable
618  * NOTE: previously, only the linking variables were master variables. As such, the following check was to find
619  * only the original variables corresponding to linking variables. Since linking constraints, and their associated
620  * variables, are also added to the master problem, then the previous check is not valid.
621  */
622  /* checking whether the original variable is associated with any master problem variables. This is identified by
623  * retrieving the number of master variables for the given original variable.
624  *
625  * If the pricing variable is requested, then there are two options. The first is that the pricing variable is a
626  * linking variable. The second is that the pricing variable has been directly copied to the master problem since
627  * it was part of the linking constraints.
628  */
629  if( GCGoriginalVarGetNMastervars(origvar) > 0 )
630  {
631  /* if the original variable is a linking variable, then the linking pricing variable is retrieved */
632  if( GCGoriginalVarIsLinking(origvar) )
633  (*mappedvar) = GCGlinkingVarGetPricingVars(origvar)[probnumber];
634  else
635  (*mappedvar) = GCGoriginalVarGetPricingVar(origvar);
636  }
637  }
638 
639  return SCIP_OKAY;
640 }
641 
643 static
644 SCIP_DECL_BENDERSPOSTSOLVE(bendersPostsolveGcg)
645 { /*lint --e{715}*/
646  SCIP_BENDERSDATA* bendersdata;
647 
648  assert(benders != NULL);
649 
650  bendersdata = SCIPbendersGetData(benders);
651  assert(bendersdata != NULL);
652 
653  (*merged) = FALSE;
654 
655  /* creates a solution to the original problem */
656 #ifdef SCIP_DEBUG
657  SCIPdebugMessage("The master problem solution.\n");
658  SCIP_CALL( SCIPprintSol(scip, sol, NULL, FALSE) );
659 #endif
660 
661  /* if there are merge candidates, then they will be merged into the master problem.
662  * TODO: maybe check to see whether the merge could be avoided
663  */
664  if( nmergecands > 0 )
665  {
666  SCIP_CALL( mergeSubproblemsIntoMaster(scip, benders, mergecands, npriomergecands, nmergecands, merged) );
667  }
668 
669  if( !infeasible && !(*merged) )
670  {
671  /* if the problem was found to be infeasible, then an artificial solution is created. */
672  SCIP_CALL( createOriginalProblemSolution(scip, benders, sol, infeasible) );
673  if( type == SCIP_BENDERSENFOTYPE_LP )
674  SCIP_CALL( GCGrelaxUpdateCurrentSol(bendersdata->origprob) );
675  }
676 
677  return SCIP_OKAY;
678 }
679 
688 static
689 SCIP_DECL_BENDERSCREATESUB(bendersCreatesubGcg)
690 { /*lint --e{715}*/
691  SCIP_BENDERSDATA* bendersdata;
692  SCIP* origprob;
693 
694  assert(scip != NULL);
695  assert(benders != NULL);
696 
697  bendersdata = SCIPbendersGetData(benders);
698  assert(bendersdata != NULL);
699 
700  origprob = bendersdata->origprob;
701 
702  SCIP_CALL( SCIPaddBendersSubproblem(scip, benders, GCGgetPricingprob(origprob, probnumber)) );
703 
704  /* setting the objective coefficients for the subproblems.
705  * This is required because the variables are added to the pricing problems with a zero coefficient. In the DW
706  * context, this is appropriate because the objective coefficients are constantly changing. In the BD context, the
707  * objective coefficients are static, so they only need to be updated once. */
708  SCIP_CALL( setSubproblemObjs(benders, probnumber) );
709 
710 
711  return SCIP_OKAY;
712 }
713 
714 /*
715  * Benders' decomposition specific interface methods
716  */
717 
720  SCIP* scip,
721  SCIP* origprob
722  )
723 {
724  SCIP_BENDERSDATA* bendersdata;
725  SCIP_BENDERS* benders;
726 
727  /* create gcg Benders' decomposition data */
728  SCIP_CALL( SCIPallocMemory(scip, &bendersdata) );
729  bendersdata->origprob = origprob;
730  bendersdata->relaxsol = NULL;
731 
732  benders = NULL;
733 
734  /* include Benders' decomposition */
735  SCIP_CALL( SCIPincludeBendersBasic(scip, &benders, BENDERS_NAME, BENDERS_DESC, BENDERS_PRIORITY,
737  bendersCreatesubGcg, bendersdata) );
738  assert(benders != NULL);
739 
740  /* set non fundamental callbacks via setter functions */
741  SCIP_CALL( SCIPsetBendersFree(scip, benders, bendersFreeGcg) );
742  SCIP_CALL( SCIPsetBendersInitpre(scip, benders, bendersInitpreGcg) );
743  SCIP_CALL( SCIPsetBendersExitsol(scip, benders, bendersExitsolGcg) );
744  SCIP_CALL( SCIPsetBendersPostsolve(scip, benders, bendersPostsolveGcg) );
745 
746  /* including the default cuts for Benders' decomposition */
747  SCIP_CALL( SCIPincludeBendersDefaultCuts(scip, benders) );
748 
749  return SCIP_OKAY;
750 }
751 
754  SCIP_BENDERS* benders
755  )
756 {
757  SCIP_BENDERSDATA* bendersdata;
758 
759  assert(benders != NULL);
760  assert(strcmp(SCIPbendersGetName(benders), BENDERS_NAME) == 0);
761 
762  bendersdata = SCIPbendersGetData(benders);
763 
764  return bendersdata->relaxsol;
765 }
766 
769  SCIP* masterprob
770  )
771 {
772  SCIP_BENDERS* benders;
773  SCIP_BENDERSDATA* bendersdata;
774 
775  assert(masterprob != NULL);
776 
777  benders = SCIPfindBenders(masterprob, BENDERS_NAME);
778  assert(benders != NULL);
779 
780  bendersdata = SCIPbendersGetData(benders);
781  assert(bendersdata != NULL);
782 
783  return bendersdata->origprob;
784 }
static SCIP_RETCODE setSubproblemObjs(SCIP_BENDERS *benders, int probnumber)
Definition: benders_gcg.c:83
#define BENDERS_DESC
Definition: benders_gcg.c:40
static SCIP_DECL_BENDERSPOSTSOLVE(bendersPostsolveGcg)
Definition: benders_gcg.c:644
#define BENDERS_NAME
Definition: benders_gcg.c:39
#define BENDERS_PRIORITY
Definition: benders_gcg.c:41
GCG interface methods.
static SCIP_RETCODE mergeSubproblemIntoMaster(SCIP *masterprob, SCIP_BENDERS *benders, int probnumber)
Definition: benders_gcg.c:426
SCIP * GCGgetPricingprob(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:3857
SCIP * GCGbendersGetOrigprob(SCIP *masterprob)
Definition: benders_gcg.c:768
static SCIP_RETCODE createOriginalProblemSolution(SCIP *masterprob, SCIP_BENDERS *benders, SCIP_SOL *sol, SCIP_Bool artificial)
Definition: benders_gcg.c:271
static SCIP_DECL_BENDERSEXITSOL(bendersExitsolGcg)
Definition: benders_gcg.c:559
SCIP_Bool GCGvarIsMaster(SCIP_VAR *var)
Definition: gcgvar.c:148
SCIP_RETCODE SCIPincludeBendersGcg(SCIP *scip, SCIP *origprob)
Definition: benders_gcg.c:719
static SCIP_DECL_BENDERSCREATESUB(bendersCreatesubGcg)
Definition: benders_gcg.c:689
SCIP_RETCODE GCGrelaxUpdateCurrentSol(SCIP *scip)
Definition: relax_gcg.c:4650
static SCIP_RETCODE setOriginalProblemMasterValues(SCIP *origprob, SCIP *masterprob, SCIP_BENDERS *benders, SCIP_SOL *origsol, SCIP_VAR **vars, SCIP_Real *vals, int nvars)
Definition: benders_gcg.c:216
SCIP_VAR ** GCGpricingVarGetOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:920
static SCIP_DECL_BENDERSFREE(bendersFreeGcg)
Definition: benders_gcg.c:520
SCIP_RETCODE GCGaddDataAuxiliaryVar(SCIP *scip, SCIP_VAR *auxiliaryvar, int probnumber)
Definition: gcgvar.c:1440
various SCIP helper methods
static SCIP_RETCODE setOriginalProblemPricingValues(SCIP *origprob, SCIP *masterprob, SCIP_BENDERS *benders, SCIP_SOL *origsol, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_Bool *success)
Definition: benders_gcg.c:126
SCIP_RETCODE GCGcopyPricingvarDataToMastervar(SCIP *scip, SCIP_VAR *pricingvar, SCIP_VAR *mastervar)
Definition: gcgvar.c:356
GCG relaxator.
SCIP_VAR ** GCGlinkingVarGetPricingVars(SCIP_VAR *var)
Definition: gcgvar.c:391
SCIP_Bool GCGoriginalVarIsLinking(SCIP_VAR *var)
Definition: gcgvar.c:176
#define BENDERS_CUTRELAX
Definition: benders_gcg.c:44
SCIP_Real * GCGmasterVarGetOrigvals(SCIP_VAR *var)
Definition: gcgvar.c:888
int GCGvarGetBlock(SCIP_VAR *var)
Definition: gcgvar.c:936
SCIP_SOL * relaxsol
Definition: benders_gcg.c:57
#define LARGE_VALUE
Definition: benders_gcg.c:47
GCG Benders&#39; decomposition.
static SCIP_DECL_BENDERSGETVAR(bendersGetvarGcg)
Definition: benders_gcg.c:579
static SCIP_DECL_BENDERSINITPRE(bendersInitpreGcg)
Definition: benders_gcg.c:539
SCIP_SOL * SCIPbendersGetRelaxSol(SCIP_BENDERS *benders)
Definition: benders_gcg.c:753
static SCIP_Real varGetObj(SCIP_VAR *var)
Definition: benders_gcg.c:66
SCIP_Bool GCGvarIsPricing(SCIP_VAR *var)
Definition: gcgvar.c:133
public methods for GCG variables
#define BENDERS_CUTPSEUDO
Definition: benders_gcg.c:43
int GCGpricingVarGetNOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:904
int GCGmasterVarGetNOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:846
int GCGoriginalVarGetNMastervars(SCIP_VAR *var)
Definition: gcgvar.c:545
SCIP_VAR ** GCGmasterVarGetOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:866
SCIP_VAR ** GCGoriginalVarGetMastervars(SCIP_VAR *var)
Definition: gcgvar.c:561
#define BENDERS_CUTLP
Definition: benders_gcg.c:42
#define BENDERS_SHAREAUXVARS
Definition: benders_gcg.c:45
SCIP_VAR * GCGoriginalVarGetPricingVar(SCIP_VAR *var)
Definition: gcgvar.c:206
SCIP_HEUR * GCGrelaxGetProbingheur(SCIP *scip)
Definition: relax_gcg.c:4219
static SCIP_RETCODE mergeSubproblemsIntoMaster(SCIP *masterprob, SCIP_BENDERS *benders, int *mergecands, int npriomergecands, int nmergecands, SCIP_Bool *merged)
Definition: benders_gcg.c:473