Scippy

GCG

Branch-and-Price & Column Generation for Everyone

cons_masterbranch.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* GCG --- Generic Column Generation */
5 /* a Dantzig-Wolfe decomposition based extension */
6 /* of the branch-cut-and-price framework */
7 /* SCIP --- Solving Constraint Integer Programs */
8 /* */
9 /* Copyright (C) 2010-2021 Operations Research, RWTH Aachen University */
10 /* Zuse Institute Berlin (ZIB) */
11 /* */
12 /* This program is free software; you can redistribute it and/or */
13 /* modify it under the terms of the GNU Lesser General Public License */
14 /* as published by the Free Software Foundation; either version 3 */
15 /* of the License, or (at your option) any later version. */
16 /* */
17 /* This program is distributed in the hope that it will be useful, */
18 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
19 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
20 /* GNU Lesser General Public License for more details. */
21 /* */
22 /* You should have received a copy of the GNU Lesser General Public License */
23 /* along with this program; if not, write to the Free Software */
24 /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
25 /* */
26 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
27 
28 /**@file cons_masterbranch.c
29  * @ingroup CONSHDLRS
30  * @brief constraint handler for storing the branching decisions at each node of the tree
31  * @author Gerald Gamrath
32  * @author Martin Bergner
33  * @author Christian Puchert
34  * @author Marcel Schmickerath
35  * @author Erik Muehmer
36  */
37 
38 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
39 /*#define SCIP_DEBUG*/
40 #include <assert.h>
41 #include <string.h>
42 
43 #include "gcg.h"
44 #include "branch_generic.h"
45 #include "cons_masterbranch.h"
46 #include "cons_origbranch.h"
47 #include "relax_gcg.h"
48 #include "pricer_gcg.h"
49 
50 #include "scip/cons_linear.h"
51 
52 /*#define CHECKPROPAGATEDVARS*/
53 
54 /* constraint handler properties */
55 #define CONSHDLR_NAME "masterbranch"
56 #define CONSHDLR_DESC "store branching decision at nodes of the tree constraint handler"
57 #define CONSHDLR_ENFOPRIORITY 0 /**< priority of the constraint handler for constraint enforcing */
58 #define CONSHDLR_CHECKPRIORITY 2000000 /**< priority of the constraint handler for checking feasibility */
59 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
60 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
61  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
62 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
63 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
64 #define CONSHDLR_PROPTIMING SCIP_PROPTIMING_ALWAYS
65 
66 #define EVENTHDLR_NAME "origvarbound"
67 #define EVENTHDLR_DESC "event handler for bound changes on original variables"
68 
69 
70 /** constraint data for masterbranch constraints */
72 {
73  char* name; /**< name of the constraint */
74  int npropvars; /**< number of variables that existed the last time the related node was propagated,
75  used to determine whether the constraint should be repropagated */
76  SCIP_Bool needprop; /**< should the constraint be propagated? */
77  SCIP_NODE* node; /**< the node at which the constraint is sticking */
78  int nactivated; /**< number of times the constraint has been activated so far */
79 
80  SCIP_CONS* parentcons; /**< the masterbranch constraint of the parent node */
81  SCIP_CONS** childconss; /**< array of the masterbranch constraints of child nodes */
82  int nchildconss; /**< number of the masterbranch constraints of child nodes */
83  int maxchildconss; /**< capacity of childconss array */
84  SCIP_CONS* probingtmpcons; /**< pointer to save the last child in the childconss array if it is overwritten in probing mode */
85  SCIP_CONS* origcons; /**< the corresponding origbranch cons in the original program */
86 
87  GCG_BRANCHDATA* branchdata; /**< branching data stored by the branching rule at the corresponding origcons constraint
88  * containing information about the branching restrictions */
89  SCIP_BRANCHRULE* branchrule; /**< branching rule that created the corresponding node in the original problem and imposed
90  * branching restrictions */
91 
92  /* local bound changes on original variables that belong to a unique block */
93  SCIP_VAR** localbndvars; /**< original variables of bound changes stored at the current node */
94  SCIP_BOUNDTYPE* localbndtypes; /**< types of the bound changes stored at the current node */
95  SCIP_Real* localnewbnds; /**< new bounds for the bound changes stored at the current node */
96  SCIP_Real* localoldbnds; /**< old bounds for the bound changes stored at the current node */
97 
98  int* nlocalbndchgstreated; /**< number of bound changes of the nodes on the way from the current node to
99  * the root node that have been treated so far */
100  int maxlocalbndchgstreated; /**< capacity of nlocalbndchgstreated */
101  int nlocalbndchgs; /**< number of bound changes */
102  int maxlocalbndchgs; /**< capacity of corresponding arrays */
103  int nbranchingchgs; /**< number of bound changes due to branching (<= nlocalbndchgs) */
104 
105  /* local bound changes on original variables that have been directly copied to the master problem */
106  SCIP_VAR** copiedvars; /**< original variables on which local bounds were changed */
107  GCG_BOUNDTYPE* copiedvarbndtypes; /**< types of the new local bounds of the coped original variables */
108  SCIP_Real* copiedvarbnds; /**< new lower/upper bounds of the coped original variables */
109  int ncopiedvarbnds; /**< number of new local bounds stored */
110  int maxcopiedvarbnds; /**< size of copiedvars, copiedvarbndtypes, and copiedvarbnds arrays */
111 
112  /* constraints that enforce the branching restrictions on the original problem */
113  SCIP_CONS** origbranchconss; /**< constraints in the original problem that enforce the branching decision */
114  int norigbranchconss; /**< number of constraints in the original problem that enforce the branching decision */
115  int maxorigbranchconss;/**< capacity of origbranchconss array */
116 };
117 
118 /** constraint handler data */
119 struct SCIP_ConshdlrData
120 {
121  /* active masterbranch constraints on the path from the root node to the current node */
122  SCIP_CONS** stack; /**< stack for storing active constraints */
123  int nstack; /**< number of elements on the stack */
124  int maxstacksize; /**< maximum size of the stack */
125 
126  /* global bound changes on the original problem */
127  SCIP_VAR** pendingvars; /**< pricing variables or master variable copies corresponding to pending bound changes (global bound changes) */
128  SCIP_BOUNDTYPE* pendingbndtypes; /**< types of the pending bound changes (global bound changes) */
129  SCIP_Real* pendingnewbnds; /**< new bounds corresponding to pending bound changes (global bound changes) */
130  SCIP_Real* pendingoldbnds; /**< old bounds corresponding to pending bound changes (global bound changes) */
131  int npendingbnds; /**< number of pending bound changes (global bound changes) */
132  SCIP_Bool pendingbndsactivated; /**< were pending bound changes already activated? */
133  int maxpendingbnds; /**< size of the array corresponding to pending bound changes */
134  SCIP_Bool enforceproper; /**< should proper variables be enforced? */
135 
136  /* information needed by applyLocalBndchgsToPricedMastervars */
137  SCIP_VAR*** collectedbndvars; /**< collected original variables of bound changes stored for each block */
138  SCIP_Real** collectedlbnds; /**< collected upper bound changes for each block */
139  SCIP_Real** collectedubnds; /**< collected upper bound changes for each block */
140  int maxblocknum; /**< maximal number of blocks that can be handled by the collected* arrays */
141  int* ncollectedbndvars; /**< number of collected bndvars per block */
142  int* maxcollectedbndvars;/**< capacity of the collected* arrays per block */
143  int** linkingvaridxs; /**< position of linking vars in collectedbndvars */
144  int maxlinkingvaridxs; /**< capacity of linkingvaridxs */
145 };
146 
147 /*
148  * Local methods
149  */
150 
151 /** initialize the consdata data structure */
152 static
153 SCIP_RETCODE initializeConsdata(
154  SCIP* scip, /**< SCIP data structure*/
155  SCIP_CONS* cons /**< constraint for which the consdata is created */
156  )
157 {
158 #ifdef SCIP_DEBUG
159  SCIP_CONS* origcons_parent;
160  SCIP_CONS* parent_origcons;
161 #endif
162 
163  SCIP* origscip;
164  SCIP_CONSDATA* consdata;
165  SCIP_CONSHDLR* conshdlr;
166  SCIP_CONSHDLRDATA* conshdlrdata;
167  SCIP_CONS* origcons;
168 
169  SCIP_DOMCHG* domchg;
170  SCIP_BOUNDCHG* boundchg;
171  SCIP_VAR* boundchgvar;
172 
173  int i;
174 
175  assert(scip != NULL);
176  assert(GCGisMaster(scip));
177  assert(cons != NULL);
178 
179  /* get constraint handler */
180  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
181  assert(conshdlr != NULL);
182  assert(SCIPconsGetHdlr(cons) == conshdlr);
183 
184  /* get constraint handler data */
185  conshdlrdata = SCIPconshdlrGetData(conshdlr);
186  assert(conshdlrdata != NULL);
187 
188  /* get constraint data */
189  consdata = SCIPconsGetData(cons);
190  assert(consdata != NULL);
191 
192  /* get original problem */
193  origscip = GCGmasterGetOrigprob(scip);
194  assert(origscip != NULL);
195 
196  /* get corresponding origbranch constraint in the original problem */
197  origcons = GCGconsOrigbranchGetActiveCons(origscip);
198  assert(origcons != NULL);
199 
200  /* @fixme: There should be an assertion instead; I guess consdata->origcons should be NULL */
201  if( consdata->origcons != origcons ) /*rootnode?*/
202  {
203  SCIPdebugMessage("set root origcons\n");
204  consdata->origcons = origcons;
205  GCGconsOrigbranchSetMastercons(origcons, cons);
206  }
207 
208  /* @fixme: Why should anything else happen? */
209  if( GCGconsOrigbranchGetNChildconss(origcons) == 0 )
210  {
211  consdata->nchildconss = 0;
212  consdata->childconss = NULL;
213  }
214 
215  /*GCGconsOrigbranchSetMastercons(origcons, cons);*/
216 
217 
218 #ifdef SCIP_DEBUG
219  if( consdata->parentcons != NULL )
220  parent_origcons = SCIPconsGetData(consdata->parentcons)->origcons;
221  else
222  parent_origcons = NULL;
223 
224  if( consdata->origcons != NULL )
225  origcons_parent = GCGconsOrigbranchGetParentcons(consdata->origcons);
226  else
227  origcons_parent = NULL;
228 
229  SCIPdebugMessage("cons: %s, origcons: %s, parent: %s => %s\n", SCIPconsGetName(cons), consdata->origcons == NULL? "NULL" : SCIPconsGetName( consdata->origcons ),
230  parent_origcons == NULL? "NULL" : SCIPconsGetName(parent_origcons), origcons_parent == NULL? "NULL" : SCIPconsGetName(origcons_parent) );
231 #endif
232 
233  assert(SCIPgetCurrentNode(scip) == consdata->node || consdata->node == SCIPgetRootNode(scip));
234 /* assert((SCIPgetNNodesLeft(scip)+SCIPgetNNodes(scip) == 1) == (consdata->node == SCIPgetRootNode(scip))); */
235  assert(SCIPnodeGetDepth(GCGconsOrigbranchGetNode(consdata->origcons)) == SCIPnodeGetDepth(consdata->node));
236  assert(consdata->parentcons != NULL || SCIPnodeGetDepth(consdata->node) == 0);
237 
238  assert(consdata->parentcons == NULL ||
239  SCIPconsGetData(consdata->parentcons)->origcons == GCGconsOrigbranchGetParentcons(consdata->origcons));
240 
241  consdata->maxlocalbndchgstreated = SCIPcalcMemGrowSize(scip, conshdlrdata->nstack+1);
242  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->nlocalbndchgstreated, (size_t)consdata->maxlocalbndchgstreated) );
243 
244  /* get all bound changes at the corresponding node in the original problem */
245 
246  domchg = SCIPnodeGetDomchg(GCGconsOrigbranchGetNode(origcons));
247  consdata->nlocalbndchgs = SCIPdomchgGetNBoundchgs(domchg);
248  consdata->nlocalbndchgstreated[conshdlrdata->nstack] = consdata->nlocalbndchgs;
249 
250  if( consdata->nlocalbndchgs > 0 )
251  {
252  consdata->maxlocalbndchgs = SCIPcalcMemGrowSize(scip, consdata->nlocalbndchgs);
253  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->localbndvars, consdata->maxlocalbndchgs) );
254  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->localbndtypes, consdata->maxlocalbndchgs) );
255  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->localnewbnds, consdata->maxlocalbndchgs) );
256  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->localoldbnds, consdata->maxlocalbndchgs) );
257  }
258  else
259  {
260  consdata->maxlocalbndchgs = 0;
261  }
262 
263  consdata->nbranchingchgs = 0;
264 
265  for( i = 0; i < consdata->nlocalbndchgs; ++i )
266  {
267  boundchg = SCIPdomchgGetBoundchg(domchg, i);
268 
269  consdata->localbndvars[i] = SCIPboundchgGetVar(boundchg);
270  consdata->localnewbnds[i] = SCIPboundchgGetNewbound(boundchg);
271  consdata->localbndtypes[i] = SCIPboundchgGetBoundtype(boundchg);
272 
273  if( SCIPboundchgGetBoundchgtype(boundchg) == SCIP_BOUNDCHGTYPE_BRANCHING )
274  {
275  consdata->nbranchingchgs++;
276  assert(consdata->nbranchingchgs == i+1);
277  }
278  }
279 
280  consdata->needprop = TRUE;
281 
282  assert((consdata->parentcons == NULL) == (conshdlrdata->nstack == 0));
283  if( consdata->parentcons != NULL )
284  {
285  SCIP_CONSDATA* parentdata = SCIPconsGetData(consdata->parentcons);
286 
287  assert(consdata->parentcons == conshdlrdata->stack[conshdlrdata->nstack-1]);
288  assert(SCIPconsGetData(conshdlrdata->stack[0])->parentcons == NULL);
289 
290  /* check whether bound changes were added in nodes on the path
291  * to the current node after activation of the parent node
292  */
293  for( i = 1; i < conshdlrdata->nstack; ++i )
294  {
295  int ndomboundchgs;
296  SCIP_CONSDATA* stackconsdata = SCIPconsGetData(conshdlrdata->stack[i]);
297  domchg = SCIPnodeGetDomchg(GCGconsOrigbranchGetNode(stackconsdata->origcons));
298  ndomboundchgs = SCIPdomchgGetNBoundchgs(domchg);
299 
300  assert(ndomboundchgs >= parentdata->nlocalbndchgstreated[i]);
301 
302  if( ndomboundchgs != parentdata->nlocalbndchgstreated[i] )
303  {
304  int diff;
305  int j;
306 
307  diff = ndomboundchgs - parentdata->nlocalbndchgstreated[i];
308 
309  if( consdata->maxlocalbndchgs < consdata->nlocalbndchgs + diff )
310  {
311  int newmaxsize = SCIPcalcMemGrowSize(scip, consdata->nlocalbndchgs + diff);
312  SCIP_CALL(SCIPreallocBlockMemoryArray(scip, &consdata->localbndvars, consdata->maxlocalbndchgs,
313  (size_t) newmaxsize));
314  SCIP_CALL(SCIPreallocBlockMemoryArray(scip, &consdata->localbndtypes, consdata->maxlocalbndchgs,
315  (size_t) newmaxsize));
316  SCIP_CALL(SCIPreallocBlockMemoryArray(scip, &consdata->localnewbnds, consdata->maxlocalbndchgs,
317  (size_t) newmaxsize));
318  SCIP_CALL(SCIPreallocBlockMemoryArray(scip, &consdata->localoldbnds, consdata->maxlocalbndchgs,
319  (size_t) newmaxsize));
320  consdata->maxlocalbndchgs = newmaxsize;
321  }
322 
323  /* add bound changes to the boundchanges array */
324  for( j = 0; j < ndomboundchgs; ++j )
325  {
326  int bndchgindex;
327  SCIP_BOUNDTYPE boundchgtype;
328  SCIP_Real boundchgnewbound;
329 
330  boundchg = SCIPdomchgGetBoundchg(domchg, j);
331  boundchgvar = SCIPboundchgGetVar(boundchg);
332  boundchgtype = SCIPboundchgGetBoundtype(boundchg);
333  boundchgnewbound = SCIPboundchgGetNewbound(boundchg);
334 
335  if( j < stackconsdata->nlocalbndchgstreated[i] )
336  {
337  assert(stackconsdata->localbndvars[j] == boundchgvar
338  && SCIPisEQ(scip, stackconsdata->localnewbnds[j], boundchgnewbound)
339  && stackconsdata->localbndtypes[j] == boundchgtype);
340  continue;
341  }
342  if( j < parentdata->nlocalbndchgstreated[i] )
343  continue;
344 
345  bndchgindex = consdata->nlocalbndchgs + j - parentdata->nlocalbndchgstreated[i];
346 
347  consdata->localbndvars[bndchgindex] = boundchgvar;
348  consdata->localnewbnds[bndchgindex] = boundchgnewbound;
349  consdata->localbndtypes[bndchgindex] = boundchgtype;
350  }
351 
352  consdata->nlocalbndchgs += diff;
353  }
354 
355  consdata->nlocalbndchgstreated[i] = ndomboundchgs;
356  }
357  }
358 
359  return SCIP_OKAY;
360 }
361 
362 /** add a global bound change on the original problem to the pending bound changes array */
363 static
364 SCIP_RETCODE addPendingBndChg(
365  SCIP* scip, /**< SCIP data structure */
366  SCIP_VAR* var, /**< variable on which the bound change is applied (corresponding master variable copy or pricing variable) */
367  SCIP_BOUNDTYPE boundtype, /**< type of the bound (lower or upper) */
368  SCIP_Real oldbound, /**< previous bound value */
369  SCIP_Real newbound /**< new bound value */
370  )
371 {
372  SCIP_CONSHDLR* conshdlr;
373  SCIP_CONSHDLRDATA* conshdlrdata;
374 
375  assert(scip != NULL);
376 
377  /* get constraint handler */
378  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
379  if( conshdlr == NULL )
380  {
381  SCIPerrorMessage("masterbranch constraint handler not found\n");
382  return SCIP_PLUGINNOTFOUND;
383  }
384 
385  /* get constraint handler data */
386  conshdlrdata = SCIPconshdlrGetData(conshdlr);
387  assert(conshdlrdata != NULL);
388  assert((conshdlrdata->npendingbnds > 0) || conshdlrdata->pendingbndsactivated);
389 
390  /* reallocate memory if needed */
391  if( conshdlrdata->npendingbnds >= conshdlrdata->maxpendingbnds )
392  {
393  int newsize = SCIPcalcMemGrowSize(scip, conshdlrdata->npendingbnds+5);
394  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(conshdlrdata->pendingvars), conshdlrdata->maxpendingbnds, newsize) );
395  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(conshdlrdata->pendingbndtypes), conshdlrdata->maxpendingbnds, newsize) );
396  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(conshdlrdata->pendingoldbnds), conshdlrdata->maxpendingbnds, newsize) );
397  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(conshdlrdata->pendingnewbnds), conshdlrdata->maxpendingbnds, newsize) );
398  conshdlrdata->maxpendingbnds = newsize;
399  }
400 
401  /* store pending bound change */
402  conshdlrdata->pendingvars[conshdlrdata->npendingbnds] = var;
403  conshdlrdata->pendingbndtypes[conshdlrdata->npendingbnds] = boundtype;
404  conshdlrdata->pendingoldbnds[conshdlrdata->npendingbnds] = oldbound;
405  conshdlrdata->pendingnewbnds[conshdlrdata->npendingbnds] = newbound;
406  conshdlrdata->npendingbnds++;
407  conshdlrdata->pendingbndsactivated = FALSE;
408 
409  return SCIP_OKAY;
410 }
411 
412 /** For a given global bound change on a pricing variable, check if the global bounds on all corresponding original variables are still the same
413  *
414  * @return TRUE if the variable is in a relevant block AND all variables identical to it have the same bounds
415  */
416 static
418  SCIP* scip, /**< SCIP data structure */
419  SCIP_VAR* bndvar, /**< pricing variable whose new global bound is to be checked */
420  SCIP_BOUNDTYPE bndtype, /**< type of the new global bound */
421  SCIP_Real bound /**< new global bound */
422  )
423 {
424  SCIP_VAR** identvars;
425  int nidentvars;
426  SCIP_Bool identical;
427 
428  assert(GCGvarIsPricing(bndvar));
429 
430  /* get all identical variables */
431  identvars = GCGpricingVarGetOrigvars(bndvar);
432  nidentvars = GCGpricingVarGetNOrigvars(bndvar);
433 
434  identical = TRUE;
435 
436  /* If the variable was not aggregated, there is nothing to check */
437  if( nidentvars > 1 )
438  {
439  int i;
440 
441  /* Check if the bounds of all identical variables are equal to the one of the representative */
442  for( i = 0; i < nidentvars; ++i )
443  {
444  SCIP_Real identbound = bndtype == SCIP_BOUNDTYPE_UPPER ? SCIPvarGetUbGlobal(identvars[i]) : SCIPvarGetLbGlobal(identvars[i]);
445  if( !SCIPisEQ(scip, identbound, bound) )
446  {
447  SCIPerrorMessage("Var <%s> has new local %s bound %g, but identical var <%s> has %g -- don't know how to handle!\n",
448  SCIPvarGetName(bndvar), bndtype == SCIP_BOUNDTYPE_UPPER ? "upper" : "lower",
449  bound, SCIPvarGetName(identvars[i]), identbound);
450  identical = FALSE;
451  }
452  }
453  }
454 
455  return identical;
456 }
457 
458 /** apply global bound changes on original problem variables either
459  * to their copies in the master problem and/or to the corresponding pricing problem variables
460  */
461 static
463  SCIP* scip /* SCIP data structure */
464  )
465 {
466  SCIP* origscip;
467  SCIP_CONSHDLR* conshdlr;
468  SCIP_CONSHDLRDATA* conshdlrdata;
469  int i;
470 
471  assert(scip != NULL);
472  assert(GCGisMaster(scip));
473 
474  /* get constraint handler */
475  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
476  assert(conshdlr != NULL);
477 
478  /* get constraint handler data */
479  conshdlrdata = SCIPconshdlrGetData(conshdlr);
480  assert(conshdlrdata != NULL);
481 
482  /* get original problem */
483  origscip = GCGmasterGetOrigprob(scip);
484  assert(origscip != NULL);
485 
486  if( !conshdlrdata->pendingbndsactivated )
487  {
488  assert(conshdlrdata->npendingbnds > 0);
489  for( i = 0; i < conshdlrdata->npendingbnds; i++ )
490  {
491  /* This should not have an effect on linking variables */
492  assert(GCGvarIsMaster(conshdlrdata->pendingvars[i]) || GCGvarIsPricing(conshdlrdata->pendingvars[i]));
493 
494  if( GCGvarIsMaster(conshdlrdata->pendingvars[i]) )
495  {
496  if( conshdlrdata->pendingbndtypes[i] == SCIP_BOUNDTYPE_LOWER )
497  {
498  if( SCIPisLT(scip, SCIPvarGetLbGlobal(conshdlrdata->pendingvars[i]), conshdlrdata->pendingnewbnds[i]) )
499  {
500  SCIPdebugMessage("Global lower bound of mastervar <%s> set to %g\n", SCIPvarGetName(conshdlrdata->pendingvars[i]),
501  conshdlrdata->pendingnewbnds[i]);
502  SCIP_CALL( SCIPchgVarLbGlobal(scip, conshdlrdata->pendingvars[i], conshdlrdata->pendingnewbnds[i]) );
503  }
504  }
505  else
506  {
507  if( SCIPisGT(scip, SCIPvarGetUbGlobal(conshdlrdata->pendingvars[i]), conshdlrdata->pendingnewbnds[i]) )
508  {
509  SCIPdebugMessage("Global upper bound of mastervar <%s> set to %g\n", SCIPvarGetName(conshdlrdata->pendingvars[i]),
510  conshdlrdata->pendingnewbnds[i]);
511  SCIP_CALL( SCIPchgVarUbGlobal(scip, conshdlrdata->pendingvars[i], conshdlrdata->pendingnewbnds[i]) );
512  }
513  }
514  }
515  else
516  {
517  /* this is a global boundchange on a variable that belongs to a block,
518  * we have to adjust the bound of the corresponding variable in the pricing problem
519  */
520 
521  /* check if all identical variables have the same global bound */
522  if( !checkAggregatedGlobalBounds(origscip, conshdlrdata->pendingvars[i], conshdlrdata->pendingbndtypes[i], conshdlrdata->pendingnewbnds[i]) )
523  continue;
524 
525  if( conshdlrdata->pendingbndtypes[i] == SCIP_BOUNDTYPE_LOWER )
526  {
527  SCIP_CALL( SCIPchgVarLbGlobal(GCGgetPricingprob(origscip, GCGvarGetBlock(conshdlrdata->pendingvars[i]) ),
528  conshdlrdata->pendingvars[i], conshdlrdata->pendingnewbnds[i]) );
529  }
530  else
531  {
532  SCIP_CALL( SCIPchgVarUbGlobal(GCGgetPricingprob(origscip, GCGvarGetBlock(conshdlrdata->pendingvars[i]) ),
533  conshdlrdata->pendingvars[i], conshdlrdata->pendingnewbnds[i]) );
534  }
535  }
536  }
537  conshdlrdata->pendingbndsactivated = TRUE;
538  }
539 
540  return SCIP_OKAY;
541 }
542 
543 /** apply global bound changes on original problem variables to the master problem */
544 static
546  SCIP* scip, /**< SCIP data structure */
547  int* propcount /**< number of applied bound changes */
548  )
549 {
550  SCIP_CONSHDLR* conshdlr;
551  SCIP_CONSHDLRDATA* conshdlrdata;
552  SCIP_VAR** vars;
553  int nvars;
554  int i;
555  int k;
556 
557  assert(scip != NULL);
558  assert(GCGisMaster(scip));
559 
560  /* get constraint handler */
561  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
562  assert(conshdlr != NULL);
563 
564  /* get constraint handler data */
565  conshdlrdata = SCIPconshdlrGetData(conshdlr);
566  assert(conshdlrdata != NULL);
567 
568  /* get master problem variables generated during pricing */
569  vars = GCGmasterGetPricedvars(scip);
570  nvars = GCGmasterGetNPricedvars(scip);
571 
572  assert((conshdlrdata->npendingbnds > 0) || conshdlrdata->pendingbndsactivated);
573 
574  /* iterate over all master variables and apply global bound changes */
575  if( conshdlrdata->npendingbnds > 0 && conshdlrdata->pendingbndsactivated )
576  {
577  for( i = 0; i < nvars; i++ )
578  {
579  SCIP_Bool ismastervarrelevant;
580  SCIP_VAR** origvars;
581  SCIP_HASHMAP* origvals;
582  int norigvars;
583  int blocknr;
584  blocknr = GCGvarGetBlock(vars[i]);
585 
586  /* get the original variables that are contained in the master variable */
587  assert(GCGvarIsMaster(vars[i]));
588  norigvars = GCGmasterVarGetNOrigvars(vars[i]);
589  origvars = GCGmasterVarGetOrigvars(vars[i]);
590  origvals = GCGmasterVarGetOrigvalmap(vars[i]);
591 
592  assert(blocknr < GCGgetNPricingprobs(GCGmasterGetOrigprob(scip)));
593  assert(norigvars >= 0);
594  assert(origvars != NULL || norigvars == 0);
595 
596  /* only look at master variables not globally fixed to zero that belong to a block */
597  ismastervarrelevant = !SCIPisFeasZero(scip, SCIPvarGetUbGlobal(vars[i]));
598  ismastervarrelevant = ismastervarrelevant && (norigvars > 0);
599  ismastervarrelevant = ismastervarrelevant && (blocknr >= 0 || GCGmasterVarIsLinking(vars[i])); /*lint !e613*/
600  if( !ismastervarrelevant )
601  continue;
602 
603  /* iterate over global bound changes on the original variables
604  * that have not yet been checked for the master variables
605  */
606  for( k = 0; k < conshdlrdata->npendingbnds; k++ )
607  {
608  int bndchgblocknr;
609  SCIP_VAR** bndchgorigvars;
610  SCIP_Real val;
611 
612  assert(!GCGvarIsOriginal(conshdlrdata->pendingvars[k]));
613 
614  bndchgblocknr = GCGvarGetBlock(conshdlrdata->pendingvars[k]);
615  if( GCGvarIsMaster(conshdlrdata->pendingvars[k]) )
616  {
617  assert(bndchgblocknr == -1);
618  bndchgorigvars = GCGmasterVarGetOrigvars(conshdlrdata->pendingvars[k]);
619  }
620  else if( GCGvarIsPricing(conshdlrdata->pendingvars[k]) )
621  bndchgorigvars = GCGpricingVarGetOrigvars(conshdlrdata->pendingvars[k]);
622  else
623  {
624  SCIPerrorMessage("Variable %s is not pricing nor master.\n", SCIPvarGetName(conshdlrdata->pendingvars[k]));
625  assert(GCGvarIsMaster(conshdlrdata->pendingvars[k]) || GCGvarIsPricing(conshdlrdata->pendingvars[k]));
626  bndchgorigvars = NULL;
627  }
628  assert(bndchgblocknr < GCGgetNPricingprobs(GCGmasterGetOrigprob(scip)));
629  assert(bndchgorigvars != NULL);
630  assert(origvars != NULL);
631 
632  /* The bound change is only relevant for the master variable if either
633  * - the bound change was performed in the same block as the master variable, or
634  * - the master variable is a copied linking variable and the bound change was performed
635  * in one of the blocks that the variable is linking
636  */
637  if( (bndchgblocknr != blocknr )
638  && !(GCGmasterVarIsLinking(vars[i]) && GCGisLinkingVarInBlock(origvars[0], bndchgblocknr)) )
639  continue;
640 
641  assert(bndchgorigvars[0] != NULL);
642 
643  val = SCIPhashmapGetImageReal(origvals, bndchgorigvars[0]);
644  /* variables belong to the same block -> set origval to 0.0 if not in map */
645  if( val == SCIP_INVALID )
646  val = 0.0;
647 
648  /* if the variable contains a part of the branching variable that violates the bound,
649  * fix the master variable to 0
650  */
651  /* @todo: This is the wrong way to treat bound changes on original variable copies in the master problem;
652  * I think they have already been treated during constraint activation
653  */
654 
655  assert(GCGvarGetBlock(bndchgorigvars[0]) == blocknr || (GCGisLinkingVarInBlock(bndchgorigvars[0], blocknr))); /*lint !e613*/
656 
657  /* new lower bound */
658  if( conshdlrdata->pendingbndtypes[k] == SCIP_BOUNDTYPE_LOWER &&
659  SCIPisFeasLT(scip, val, conshdlrdata->pendingnewbnds[k]) )
660  {
661  SCIP_CALL( SCIPchgVarUbGlobal(scip, vars[i], 0.0) );
662  ++(*propcount);
663  break;
664  }
665  /* new upper bound */
666  if( conshdlrdata->pendingbndtypes[k] == SCIP_BOUNDTYPE_UPPER &&
667  SCIPisFeasGT(scip, val, conshdlrdata->pendingnewbnds[k]) )
668  {
669  SCIP_CALL( SCIPchgVarUbGlobal(scip, vars[i], 0.0) );
670  ++(*propcount);
671  break;
672  }
673  }
674  }
675  conshdlrdata->pendingbndsactivated = TRUE;
676  conshdlrdata->npendingbnds = 0;
677 
678  SCIPdebugMessage("Finished handling of pending global bound changes: %d changed bounds\n", *propcount);
679  }
680 
681  return SCIP_OKAY;
682 }
683 
684 /** reset bound changes on pricing variables (called when a node is deactivated) */
685 static
686 SCIP_RETCODE resetPricingVarBound(
687  SCIP* scip, /**< SCIP data structure */
688  SCIP_VAR* pricingvar, /**< variable on which the bound change should be performed */
689  SCIP_CONSDATA* consdata, /**< constraint data structure */
690  int i, /**< index of the information in the constraint data structure */
691  int blocknr /**< number of the pricing problem */
692  )
693 {
694  SCIP* origscip;
695 
696  assert(scip != NULL);
697  assert(pricingvar != NULL);
698  assert(consdata != NULL);
699  assert(consdata->nactivated >= 1);
700  assert(consdata->localbndvars != NULL);
701  assert(consdata->localbndtypes != NULL);
702  assert(consdata->localnewbnds != NULL);
703  assert(consdata->localoldbnds != NULL);
704 
705  /* get original problem */
706  origscip = GCGmasterGetOrigprob(scip);
707  assert(origscip != NULL);
708 
709  assert(blocknr >= 0 && blocknr < GCGgetNPricingprobs(origscip));
710 
711  /* lower bound was changed */
712  if( consdata->localbndtypes[i] == SCIP_BOUNDTYPE_LOWER )
713  {
714 
715  if( GCGgetNIdenticalBlocks(origscip, blocknr) > 1 || GCGgetNIdenticalBlocks(origscip, blocknr) == 0 )
716  return SCIP_OKAY;
717 
718  assert(SCIPisGE(scip, SCIPvarGetLbLocal(pricingvar), consdata->localnewbnds[i])
719  || SCIPisLE(scip, SCIPvarGetLbLocal(pricingvar), SCIPvarGetLbGlobal(consdata->localbndvars[i])));
720 
721  if( SCIPisEQ(scip, SCIPvarGetLbGlobal(consdata->localbndvars[i]), consdata->localnewbnds[i]) )
722  return SCIP_OKAY;
723 
724  if( SCIPisGT(scip, consdata->localoldbnds[i], consdata->localnewbnds[i]) )
725  return SCIP_OKAY;
726 
727  if( SCIPisGT(scip, SCIPvarGetLbGlobal(consdata->localbndvars[i]), consdata->localoldbnds[i]) )
728  {
729  SCIP_CALL( SCIPchgVarLb(GCGgetPricingprob(origscip, blocknr), pricingvar, SCIPvarGetLbGlobal(consdata->localbndvars[i])) );
730  SCIPdebugMessage("relaxed lower bound of pricing var %s from %g to global bound %g (%s)\n",
731  SCIPvarGetName(pricingvar), consdata->localnewbnds[i], SCIPvarGetLbGlobal(consdata->localbndvars[i]), consdata->name);
732  }
733  else
734  {
735  SCIP_CALL( SCIPchgVarLb(GCGgetPricingprob(origscip, blocknr), pricingvar, consdata->localoldbnds[i]) );
736  SCIPdebugMessage("relaxed lower bound of pricing var %s from %g to %g (%s)\n",
737  SCIPvarGetName(pricingvar), consdata->localnewbnds[i], consdata->localoldbnds[i], consdata->name);
738  }
739  }
740  /* upper bound was changed */
741  else
742  {
743  if( GCGgetNIdenticalBlocks(origscip, blocknr) > 1 || GCGgetNIdenticalBlocks(origscip, blocknr) == 0 )
744  return SCIP_OKAY;
745 
746  assert(SCIPisLE(scip, SCIPvarGetUbLocal(pricingvar), consdata->localnewbnds[i])
747  || SCIPisGE(scip, SCIPvarGetUbLocal(pricingvar), SCIPvarGetUbGlobal(consdata->localbndvars[i])));
748 
749  if( SCIPisEQ(scip, SCIPvarGetUbGlobal(consdata->localbndvars[i]), consdata->localnewbnds[i]) )
750  return SCIP_OKAY;
751 
752  if( SCIPisLT(scip, consdata->localoldbnds[i], consdata->localnewbnds[i]) )
753  return SCIP_OKAY;
754 
755  if( SCIPisLT(scip, SCIPvarGetUbGlobal(consdata->localbndvars[i]), consdata->localoldbnds[i]) )
756  {
757  SCIP_CALL( SCIPchgVarUb(GCGgetPricingprob(origscip, blocknr), pricingvar, SCIPvarGetUbGlobal(consdata->localbndvars[i])) );
758  SCIPdebugMessage("relaxed upper bound of pricing var %s from %g to global bound %g (%s)\n",
759  SCIPvarGetName(pricingvar), consdata->localnewbnds[i], SCIPvarGetUbGlobal(consdata->localbndvars[i]), consdata->name);
760  }
761  else
762  {
763  SCIP_CALL( SCIPchgVarUb(GCGgetPricingprob(origscip, blocknr), pricingvar, consdata->localoldbnds[i]) );
764  SCIPdebugMessage("relaxed upper bound of pricing var %s from %g to %g (%s)\n",
765  SCIPvarGetName(pricingvar), consdata->localnewbnds[i], consdata->localoldbnds[i], consdata->name);
766  }
767  }
768 
769  return SCIP_OKAY;
770 }
771 
772 /** perform bound changes on pricing variables (called when a node is activated) */
773 static
775  SCIP* scip, /**< SCIP data structure */
776  SCIP_VAR* pricingvar, /**< variable on which the bound change should be performed */
777  SCIP_CONSDATA* consdata, /**< constraint data structure */
778  int i, /**< index of the information in the constraint data structure */
779  int blocknr /**< number of the pricing problem */
780  )
781 {
782  SCIP* origscip;
783 
784  assert(scip != NULL);
785  assert(pricingvar != NULL);
786  assert(consdata != NULL);
787  assert(consdata->nactivated >= 1);
788  assert(consdata->localbndvars != NULL);
789  assert(consdata->localbndtypes != NULL);
790  assert(consdata->localnewbnds != NULL);
791  assert(consdata->localoldbnds != NULL);
792 
793  /* get original problem */
794  origscip = GCGmasterGetOrigprob(scip);
795  assert(origscip != NULL);
796 
797  assert(blocknr >= 0 && blocknr < GCGgetNPricingprobs(origscip));
798 
799  /* lower bound was changed */
800  if( consdata->localbndtypes[i] == SCIP_BOUNDTYPE_LOWER )
801  {
802  consdata->localoldbnds[i] = SCIPvarGetLbLocal(pricingvar);
803 
804  if( SCIPisGT(scip, consdata->localnewbnds[i], consdata->localoldbnds[i]) )
805  {
806  SCIP_CALL( SCIPchgVarLb(GCGgetPricingprob(origscip, blocknr), pricingvar, consdata->localnewbnds[i]) );
807  SCIPdebugMessage("tightened lower bound of var %s from %g to %g\n",
808  SCIPvarGetName(pricingvar), consdata->localoldbnds[i], consdata->localnewbnds[i]);
809  }
810  }
811  /* upper bound was changed */
812  else
813  {
814  assert(consdata->localbndtypes[i] == SCIP_BOUNDTYPE_UPPER);
815 
816  consdata->localoldbnds[i] = SCIPvarGetUbLocal(pricingvar);
817 
818  if( SCIPisLT(scip, consdata->localnewbnds[i], consdata->localoldbnds[i]) )
819  {
820  SCIP_CALL( SCIPchgVarUb(GCGgetPricingprob(origscip, blocknr), pricingvar, consdata->localnewbnds[i]) );
821  SCIPdebugMessage("tightened upper bound of var %s from %g to %g\n",
822  SCIPvarGetName(pricingvar), consdata->localoldbnds[i], consdata->localnewbnds[i]);
823  }
824  }
825 
826  return SCIP_OKAY;
827 }
828 
829 /** For a given local bound change on an original variable, check if the bounds on the variables identical to it are the same
830  *
831  * @note If the variable is represented by another one, we check only the representative;
832  * otherwise, we check all variables identical to it
833  *
834  * @return TRUE if the variable is in a relevant block AND all variables identical to it have the same bounds
835  */
836 static
838  SCIP* scip, /**< SCIP data structure */
839  SCIP_VAR** bndvars, /**< all variables whose local bounds were changed */
840  SCIP_Real* bounds, /**< corresponding new local bounds */
841  int nbndvars, /**< number of all variables whose local bounds were changed */
842  SCIP_VAR* bndvar, /**< original variable whose local bound was changed and which is to be checked */
843  SCIP_BOUNDTYPE bndtype, /**< type of the new local bound */
844  SCIP_VAR* pricingvar /**< pricing variable corresponding to the original variable */
845  )
846 {
847  SCIP_VAR** identvars;
848  int nidentvars;
849 
850  assert(GCGvarIsOriginal(bndvar));
851  assert(GCGvarIsPricing(pricingvar));
852 
853  /* get variables with which the original variable was aggregated */
854  identvars = GCGpricingVarGetOrigvars(pricingvar);
855  nidentvars = GCGpricingVarGetNOrigvars(pricingvar);
856 
857  /* First case: The variable is not represented by another one - check the bounds of all variables it represents */
858  if( identvars[0] == bndvar )
859  {
860  SCIP_Bool identical = TRUE;
861 
862  /* If the variable was not aggregated, there is nothing to check */
863  if( nidentvars > 1 )
864  {
865  int i;
866  int j;
867  SCIP_Real* identbounds; /* most recent bounds of all identical variables */
868 
869  SCIP_CALL( SCIPallocBufferArray(scip, &identbounds, nidentvars) );
870  for( j = 0; j < nidentvars; ++j )
871  identbounds[j] = SCIP_INVALID;
872 
873  /* For all variables on which a bound was changed *and* which are identical to the current variable,
874  * get the most recent bound
875  */
876  for( i = 0; i < nbndvars; ++i )
877  {
878  assert(GCGvarIsOriginal(bndvars[i]));
879 
880  if( GCGvarGetBlock(bndvars[i]) < 0 )
881  continue;
882 
883  if( GCGpricingVarGetOrigvars(GCGoriginalVarGetPricingVar(bndvars[i]))[0] == identvars[0] )
884  for( j = 0; j < nidentvars; ++j )
885  if( identvars[j] == bndvars[i] )
886  identbounds[j] = bounds[i];
887  }
888 
889  /* Check if the bounds of all identical variables are equal to the one of the representative */
890  for( j = 1; j < nidentvars; ++j )
891  {
892  if( !SCIPisEQ(scip, identbounds[j], identbounds[0]) )
893  {
894  SCIPerrorMessage("Var <%s> has new local %s bound %g, but identical var <%s> has %g -- don't know how to handle!\n",
895  SCIPvarGetName(bndvar), bndtype == SCIP_BOUNDTYPE_UPPER ? "upper" : "lower",
896  identbounds[0], SCIPvarGetName(identvars[j]), identbounds[j]);
897  identical = FALSE;
898  }
899  }
900 
901  SCIPfreeBufferArray(scip, &identbounds);
902  }
903 
904  return identical;
905  }
906 
907  /* Second case: The variable is represented by another one due to aggregation; check if its representative has the same bound */
908  else
909  {
910  int i;
911  SCIP_Real reprbound;
912  SCIP_Real bound;
913 
914  /* Get the most recent bound for the bound change variable as well as for its representative */
915  reprbound = SCIP_INVALID;
916  bound = SCIP_INVALID;
917  for( i = 0; i < nbndvars; ++i )
918  {
919  assert(GCGvarIsOriginal(bndvars[i]));
920 
921  if( bndvars[i] == identvars[0] )
922  reprbound = bounds[i];
923  else if( bndvars[i] == bndvar )
924  bound = bounds[i];
925  }
926 
927  /* Check if the bounds are equal */
928  if( !SCIPisEQ(scip, bound, reprbound) )
929  {
930  SCIPerrorMessage("Var <%s> has new local %s bound %g, but representative <%s> has %g -- don't know how to handle!\n",
931  SCIPvarGetName(bndvar), bndtype == SCIP_BOUNDTYPE_UPPER ? "upper" : "lower",
932  bound, SCIPvarGetName(identvars[0]), reprbound);
933  }
934 
935  /* Since the block is not relevant, there is no corresponding pricing variable */
936  return FALSE;
937  }
938 }
939 
940 /** apply local bound changes in the original problem to the pricing problems */
941 static
943  SCIP* scip, /* SCIP data structure */
944  SCIP_CONS* cons /* current masterbranch constraint */
945  )
946 {
947  SCIP* origscip;
948  SCIP_CONSDATA* consdata;
949  int i;
950 
951  assert(scip != NULL);
952  assert(GCGisMaster(scip));
953 
954  /* get constraint data */
955  consdata = SCIPconsGetData(cons);
956  assert(consdata != NULL);
957 
958  /* get original problem */
959  origscip = GCGmasterGetOrigprob(scip);
960  assert(origscip != NULL);
961 
962  /* iterate over all local bound changes in the original problem */
963  for( i = 0; i < consdata->nlocalbndchgs; i++ )
964  {
965  int blocknr;
966  assert(GCGvarIsOriginal(consdata->localbndvars[i]));
967  blocknr = GCGvarGetBlock(consdata->localbndvars[i]);
968  assert(blocknr < GCGgetNPricingprobs(origscip));
969 
970  /* if variable belongs to no block, skip it here because the bound changes are treated in the propagation */
971  if( blocknr == -1 )
972  continue;
973 
974  else if( blocknr >= 0 )
975  {
976  if( checkAggregatedLocalBounds(scip, consdata->localbndvars, consdata->localnewbnds, consdata->nlocalbndchgs, consdata->localbndvars[i],
977  consdata->localbndtypes[i], GCGoriginalVarGetPricingVar(consdata->localbndvars[i])) )
978  {
979  SCIPdebugMessage("adjusting bound of pricing var <%s>\n", SCIPvarGetName(consdata->localbndvars[i]));
980  /* set corresponding bound in the pricing problem */
981  SCIP_CALL( tightenPricingVarBound(scip, GCGoriginalVarGetPricingVar(consdata->localbndvars[i]), consdata, i, blocknr) );
982  }
983  }
984 
985  else if( blocknr == -2 )
986  {
987  int j;
988  int npricingprobs;
989  SCIP_VAR** pricingvars;
990  SCIP_Bool aggregated;
991 
992  npricingprobs = GCGgetNPricingprobs(origscip);
993  pricingvars = GCGlinkingVarGetPricingVars(consdata->localbndvars[i]);
994  aggregated = FALSE;
995  /* check the blocks in which the linking variable appears */
996  for( j = 0; j < npricingprobs; ++j )
997  {
998  if( pricingvars[j] == NULL )
999  continue;
1000 
1001  if( !checkAggregatedLocalBounds(scip, consdata->localbndvars, consdata->localnewbnds, consdata->nlocalbndchgs,
1002  consdata->localbndvars[i], consdata->localbndtypes[i], pricingvars[j]) )
1003  aggregated = TRUE;
1004  }
1005  if( aggregated )
1006  continue;
1007 
1008  SCIPdebugMessage("adjusting bound of linking pricing var <%s>\n", SCIPvarGetName(consdata->localbndvars[i]));
1009 
1010  /* set corresponding bound in the pricing problem */
1011  for( j = 0; j < npricingprobs; ++j )
1012  {
1013  if( pricingvars[j] == NULL )
1014  continue;
1015 
1016  SCIP_CALL( tightenPricingVarBound(scip, pricingvars[j], consdata, i, j) );
1017  }
1018  }
1019 
1020  else
1021  {
1022  SCIPerrorMessage("blocknr = %d is not valid! This is a serious error!", GCGvarGetBlock(consdata->localbndvars[i]));
1023  SCIPABORT();
1024  }
1025  }
1026 
1027  return SCIP_OKAY;
1028 }
1029 
1030 /** undo local bound changes in the original problem to the pricing problems */
1031 static
1033  SCIP* scip, /* SCIP data structure */
1034  SCIP_CONS* cons /* current masterbranch constraint */
1035  )
1036 {
1037  SCIP* origscip;
1038  SCIP_CONSDATA* consdata;
1039  int i;
1040 
1041  assert(scip != NULL);
1042  assert(GCGisMaster(scip));
1043 
1044  /* get constraint data */
1045  consdata = SCIPconsGetData(cons);
1046  assert(consdata != NULL);
1047 
1048  /* get original problem */
1049  origscip = GCGmasterGetOrigprob(scip);
1050  assert(origscip != NULL);
1051 
1052  /* iterate over all local bound changes in the original problem */
1053  for( i = consdata->nlocalbndchgs - 1; i >= 0; i-- )
1054  {
1055  int blocknr;
1056  blocknr = GCGvarGetBlock(consdata->localbndvars[i]);
1057  assert(GCGvarIsOriginal(consdata->localbndvars[i]));
1058  assert(blocknr < GCGgetNPricingprobs(origscip));
1059 
1060  /* if variable belongs to no block, local bound in master was set, is reset automatically */
1061  if( blocknr == -1 )
1062  continue;
1063 
1064  else if( blocknr >= 0 )
1065  {
1066  assert(GCGgetPricingprob(origscip, GCGvarGetBlock(consdata->localbndvars[i])) != NULL);
1067 
1068  /* reset corresponding bound in the pricing problem */
1069 
1070  SCIP_CALL( resetPricingVarBound(scip,
1071  GCGoriginalVarGetPricingVar(consdata->localbndvars[i]), consdata, i, blocknr));
1072  }
1073  else if( blocknr == -2 )
1074  {
1075  int j;
1076  SCIP_VAR** pricingvars;
1077  int npricingprobs;
1078 
1079  /* if the variable is linking, we have to perform the same step as above for every existing block*/
1080  assert(GCGoriginalVarIsLinking(consdata->localbndvars[i]));
1081  pricingvars = GCGlinkingVarGetPricingVars(consdata->localbndvars[i]);
1082  npricingprobs = GCGgetNPricingprobs(origscip);
1083 
1084  /* reset corresponding bound in the pricing problem */
1085  /* lower bound was changed */
1086  for( j = 0; j < npricingprobs; ++j )
1087  {
1088  assert(GCGgetPricingprob(origscip, j) != NULL);
1089  if( pricingvars[j] == NULL )
1090  continue;
1091 
1092  assert(GCGgetPricingprob(origscip, j) != NULL);
1093 
1094  /* reset corresponding bound in the pricing problem */
1095  SCIP_CALL( resetPricingVarBound(scip, pricingvars[j], consdata, i, j) );
1096  }
1097  }
1098  else
1099  {
1100  SCIPerrorMessage("blocknr = %d is not valid! This is a serious error!", blocknr);
1101  SCIPABORT();
1102  }
1103  }
1104 
1105  return SCIP_OKAY;
1106 }
1107 
1108 static
1110  SCIP* scip,
1111  SCIP_CONSHDLRDATA *conshdlrdata,
1112  int blocknr,
1113  int minsize
1114  )
1115 {
1116  int oldsize = conshdlrdata->maxcollectedbndvars[blocknr];
1117  if( oldsize < minsize )
1118  {
1119  int newsize = SCIPcalcMemGrowSize(scip, minsize);
1120  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(conshdlrdata->collectedbndvars[blocknr]), oldsize, newsize) );
1121  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(conshdlrdata->collectedlbnds[blocknr]), oldsize, newsize) );
1122  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(conshdlrdata->collectedubnds[blocknr]), oldsize, newsize) );
1123  conshdlrdata->maxcollectedbndvars[blocknr] = newsize;
1124  }
1125  return SCIP_OKAY;
1126 }
1127 
1128 static
1130  SCIP* scip,
1131  SCIP_CONSHDLRDATA *conshdlrdata,
1132  int minsize
1133 )
1134 {
1135  int oldsize = conshdlrdata->maxlinkingvaridxs;
1136  if( oldsize < minsize )
1137  {
1138  int newsize = SCIPcalcMemGrowSize(scip, minsize);
1139  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(conshdlrdata->linkingvaridxs), oldsize, newsize) );
1140  BMSclearMemoryArray(&conshdlrdata->linkingvaridxs[oldsize], (newsize - oldsize));
1141  conshdlrdata->maxlinkingvaridxs = newsize;
1142  }
1143  return SCIP_OKAY;
1144 }
1145 
1146 /** apply local bound changes on the original variables on newly generated master variables */
1147 static
1149  SCIP* scip, /**< SCIP data structure */
1150  SCIP_CONS* cons, /**< current masterbranch constraint */
1151  int* propcount /**< number of applied bound changes */
1152  )
1153 {
1154  SCIP_CONSHDLR *conshdlr;
1155  SCIP_CONSHDLRDATA *conshdlrdata;
1156  SCIP_CONSDATA *consdata;
1157  SCIP_CONSDATA *curconsdata;
1158  SCIP_VAR **vars;
1159  int nvars;
1160 
1161  assert(scip != NULL);
1162  assert(GCGisMaster(scip));
1163 
1164  /* get constraint handler */
1165  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
1166  assert(conshdlr != NULL);
1167 
1168  /* get constraint handler data */
1169  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1170  assert(conshdlrdata != NULL);
1171 
1172  /* get constraint data */
1173  consdata = SCIPconsGetData(cons);
1174  assert(consdata != NULL);
1175 
1176  /* get master problem variables generated during pricing */
1177  vars = GCGmasterGetPricedvars(scip);
1178  nvars = GCGmasterGetNPricedvars(scip);
1179 
1180  if( consdata->npropvars < nvars )
1181  {
1182  SCIP_CONS *curcons;
1183  SCIP_HASHMAP *origvar2idx;
1184  int nbndvars;
1185  int nlocalbndchgs;
1186  int i;
1187  int j;
1188  int k;
1189  SCIP_VAR*** collectedbndvars;
1190  SCIP_Real** collectedlbnds;
1191  SCIP_Real** collectedubnds;
1192  int* ncollectedbndvars;
1193  int hashmapsize;
1194  int nblocks;
1195  int blocknr;
1196  SCIP_VAR *bndvar;
1197  int idx;
1198  SCIP_Real bnd;
1199  SCIP_Bool islinking;
1200  int* linkingvaridxs;
1201  int nlinkingvars;
1202 
1203  nblocks = GCGgetNPricingprobs(GCGmasterGetOrigprob(scip));
1204  nlinkingvars = 0;
1205 
1206  collectedbndvars = conshdlrdata->collectedbndvars;
1207  collectedlbnds = conshdlrdata->collectedlbnds;
1208  collectedubnds = conshdlrdata->collectedubnds;
1209  ncollectedbndvars = conshdlrdata->ncollectedbndvars;
1210 
1211  BMSclearMemoryArray(ncollectedbndvars, conshdlrdata->maxblocknum);
1212 
1213  /* propagate local bound changes on the path from the current node to the root */
1214  curcons = cons;
1215  hashmapsize = 0;
1216  while ( curcons != NULL )
1217  {
1218  curconsdata = SCIPconsGetData(curcons);
1219  assert(curconsdata != NULL);
1220  //if( curconsdata->npropvars == nvars )
1221  // break;
1222  hashmapsize += (conshdlrdata->enforceproper ? curconsdata->nlocalbndchgs : curconsdata->nbranchingchgs);
1223  curcons = curconsdata->parentcons;
1224  }
1225  if( hashmapsize > SCIPgetNVars(GCGmasterGetOrigprob(scip)))
1226  hashmapsize = SCIPgetNVars(GCGmasterGetOrigprob(scip));
1227 
1228  SCIP_CALL(SCIPhashmapCreate(&origvar2idx, SCIPblkmem(scip), hashmapsize));
1229 
1230  curcons = cons;
1231  nbndvars = 0;
1232  while ( curcons != NULL)
1233  {
1234  curconsdata = SCIPconsGetData(curcons);
1235  assert(curconsdata != NULL);
1236  //if( curconsdata->npropvars == nvars )
1237  // break;
1238 
1239  /* propagate all bound changes or only the branching bound changes, depending on the setting for the enforcement of proper variables */
1240  nlocalbndchgs = (conshdlrdata->enforceproper ? curconsdata->nlocalbndchgs : curconsdata->nbranchingchgs);
1241 
1242  /* iterate over bound changes performed at the current node's equivalent in the original tree */
1243  for ( k = 0; k < nlocalbndchgs; ++k )
1244  {
1245  linkingvaridxs = NULL;
1246  bndvar = curconsdata->localbndvars[k];
1247  islinking = GCGoriginalVarIsLinking(bndvar);
1248 
1249  /* get the block the original variable is in */
1250  blocknr = GCGvarGetBlock(bndvar);
1251  assert(GCGvarIsOriginal(bndvar));
1252  assert(blocknr < nblocks);
1253 
1254  if( blocknr >= 0 || islinking)
1255  {
1256  idx = SCIPhashmapGetImageInt(origvar2idx, bndvar);
1257  bnd = curconsdata->localnewbnds[k];
1258 
1259  if( islinking )
1260  {
1261  blocknr = 0;
1262  if( idx < INT_MAX )
1263  {
1264  linkingvaridxs = conshdlrdata->linkingvaridxs[idx];
1265  }
1266  else
1267  {
1268  ensureLinkingvarIndxsSize(scip, conshdlrdata, nlinkingvars + 1);
1269  linkingvaridxs = conshdlrdata->linkingvaridxs[nlinkingvars];
1270  if( linkingvaridxs == NULL )
1271  {
1272  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &linkingvaridxs, conshdlrdata->maxblocknum) );
1273  conshdlrdata->linkingvaridxs[nlinkingvars] = linkingvaridxs;
1274  }
1275  SCIPhashmapInsertInt(origvar2idx, bndvar, nlinkingvars);
1276  ++nlinkingvars;
1277 
1278  for( i = 0; i < nblocks; ++i )
1279  linkingvaridxs[i] = INT_MAX;
1280  }
1281  }
1282 
1283  do
1284  {
1285  assert(blocknr >= 0 && blocknr < GCGgetNPricingprobs(GCGmasterGetOrigprob(scip)));
1286 
1287  if( islinking )
1288  {
1289  if( !GCGisLinkingVarInBlock(bndvar, blocknr) )
1290  continue;
1291 
1292  idx = linkingvaridxs[blocknr];
1293  }
1294 
1295  if( curconsdata->localbndtypes[k] == SCIP_BOUNDTYPE_LOWER )
1296  {
1297  if( idx < INT_MAX )
1298  {
1299  if( collectedlbnds[blocknr][idx] == SCIP_INVALID || collectedlbnds[blocknr][idx] < bnd )
1300  collectedlbnds[blocknr][idx] = bnd;
1301  }
1302  else
1303  {
1304  SCIP_CALL(
1305  ensureCollectedBndvarsSize(scip, conshdlrdata, blocknr, ncollectedbndvars[blocknr] + 1));
1306  if ( islinking )
1307  linkingvaridxs[blocknr] = ncollectedbndvars[blocknr];
1308  else
1309  SCIPhashmapInsertInt(origvar2idx, bndvar, ncollectedbndvars[blocknr]);
1310  collectedbndvars[blocknr][ncollectedbndvars[blocknr]] = bndvar;
1311  collectedlbnds[blocknr][ncollectedbndvars[blocknr]] = bnd;
1312  collectedubnds[blocknr][ncollectedbndvars[blocknr]] = SCIP_INVALID;
1313  ++ncollectedbndvars[blocknr];
1314  ++nbndvars;
1315  }
1316  }
1317  else
1318  {
1319  if( idx < INT_MAX )
1320  {
1321  if( collectedubnds[blocknr][idx] == SCIP_INVALID || collectedubnds[blocknr][idx] > bnd )
1322  collectedubnds[blocknr][idx] = bnd;
1323  }
1324  else
1325  {
1326  SCIP_CALL(
1327  ensureCollectedBndvarsSize(scip, conshdlrdata, blocknr, ncollectedbndvars[blocknr] + 1));
1328  if ( islinking )
1329  linkingvaridxs[blocknr] = ncollectedbndvars[blocknr];
1330  else
1331  SCIPhashmapInsertInt(origvar2idx, bndvar, ncollectedbndvars[blocknr]);
1332  collectedbndvars[blocknr][ncollectedbndvars[blocknr]] = bndvar;
1333  collectedubnds[blocknr][ncollectedbndvars[blocknr]] = bnd;
1334  collectedlbnds[blocknr][ncollectedbndvars[blocknr]] = SCIP_INVALID;
1335  ++ncollectedbndvars[blocknr];
1336  ++nbndvars;
1337  }
1338  }
1339  }
1340  while( islinking && (++blocknr) < nblocks );
1341  }
1342  }
1343  /* proceed with the parent node */
1344  curcons = curconsdata->parentcons;
1345  }
1346 
1347  if( nbndvars > 0 )
1348  {
1349  SCIP_Real lbnd;
1350  SCIP_Real ubnd;
1351  SCIP_HASHMAP* origvals;
1352  SCIP_Real origval;
1353 
1354  /* iterate over all master variables created after the current node was left the last time */
1355  for ( i = consdata->npropvars; i < nvars; i++ )
1356  {
1357  assert(GCGvarIsMaster(vars[i]));
1358  blocknr = GCGvarGetBlock(vars[i]);
1359  assert(blocknr >= 0 && blocknr < GCGgetNPricingprobs(GCGmasterGetOrigprob(scip)));
1360 
1361  /** @todo check if this really works with linking variables */
1362 
1363  /* only look at variables not already fixed to 0 or that belong to no block */
1364  if((SCIPisFeasZero(scip, SCIPvarGetUbLocal(vars[i]))))
1365  continue;
1366 
1367  origvals = GCGmasterVarGetOrigvalmap(vars[i]);
1368 
1369  /* iterate over all original variables whose bound was changed */
1370  for ( j = 0; j < ncollectedbndvars[blocknr]; j++ )
1371  {
1372  bndvar = collectedbndvars[blocknr][j];
1373 
1374  assert(GCGvarGetBlock(bndvar) == blocknr || (GCGoriginalVarIsLinking(bndvar) && GCGisLinkingVarInBlock(bndvar, blocknr)));
1375 
1376  origval = SCIPhashmapGetImageReal(origvals, bndvar);
1377  /* variables belong to the same block -> set origval to 0.0 if not in map */
1378  if( origval == SCIP_INVALID )
1379  origval = 0.0;
1380  lbnd = collectedlbnds[blocknr][j];
1381  ubnd = collectedubnds[blocknr][j];
1382 
1383  /* branching imposes new bound */
1384  if( (lbnd != SCIP_INVALID && SCIPisFeasLT(scip, origval, lbnd))
1385  || (ubnd != SCIP_INVALID && SCIPisFeasGT(scip, origval, ubnd)) )
1386  {
1387  SCIPdebugMessage("Changing upper bound of var %s\n", SCIPvarGetName(vars[i]));
1388  SCIP_CALL(SCIPchgVarUb(scip, vars[i], 0.0));
1389  ++(*propcount);
1390  break;
1391  }
1392  }
1393  }
1394  }
1395  SCIPhashmapFree(&origvar2idx);
1396  }
1397 
1398  SCIPdebugMessage("Finished propagation of newly created variables: %d changed bounds\n", *propcount);
1399 
1400  return SCIP_OKAY;
1401 }
1402 
1403 /** apply local bound changes on original variables that have been directly copied to the master problem */
1404 static
1406  SCIP* scip, /**< SCIP data structure */
1407  SCIP_CONS* cons, /**< current masterbranch constraint */
1408  int* propcount /**< number of applied bound changes */
1409  )
1410 {
1411  SCIP_CONSDATA* consdata;
1412  int i;
1413 
1414  /* get constraint data */
1415  consdata = SCIPconsGetData(cons);
1416  assert(consdata != NULL);
1417 
1418  /* apply local bound changes */
1419  for( i = 0; i < consdata->nlocalbndchgs; i++ )
1420  {
1421  SCIP_VAR* mastervar;
1422 
1423  assert(GCGvarIsOriginal(consdata->localbndvars[i]));
1424 
1425  /** @todo this might lead to an error with linking variables ? */
1426  if( GCGvarGetBlock(consdata->localbndvars[i]) >= 0 )
1427  continue;
1428 
1429  assert(GCGoriginalVarGetNMastervars(consdata->localbndvars[i]) >= 1);
1430 
1431  mastervar = GCGoriginalVarGetMastervars(consdata->localbndvars[i])[0];
1432  assert(GCGvarGetBlock(mastervar) == -1);
1433 
1434  if( consdata->localbndtypes[i] == SCIP_BOUNDTYPE_LOWER )
1435  {
1436  if( SCIPisLT(scip, SCIPvarGetLbLocal(mastervar), consdata->localnewbnds[i]) )
1437  {
1438  SCIP_CALL( SCIPchgVarLb(scip, mastervar, consdata->localnewbnds[i]) );
1439  ++(*propcount);
1440  SCIPdebugMessage("changed lb of copied original var %s locally to %g\n", SCIPvarGetName(consdata->localbndvars[i]), consdata->localnewbnds[i]);
1441  }
1442  }
1443  else
1444  {
1445  if( SCIPisGT(scip, SCIPvarGetUbLocal(mastervar), consdata->localnewbnds[i]) )
1446  {
1447  SCIP_CALL( SCIPchgVarUb(scip, mastervar, consdata->localnewbnds[i]) );
1448  ++(*propcount);
1449  SCIPdebugMessage("changed ub of copied original var %s locally to %g\n", SCIPvarGetName(consdata->localbndvars[i]), consdata->localnewbnds[i]);
1450  }
1451  }
1452  }
1453 
1454  SCIPdebugMessage("Finished propagation of bounds of copied original variables: %d bounds changed.\n", *propcount);
1455 
1456  return SCIP_OKAY;
1457 }
1458 
1459 /*
1460  * Callback methods
1461  */
1462 
1463 
1464 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
1465 static
1466 SCIP_DECL_CONSFREE(consFreeMasterbranch)
1467 {
1468  SCIP_CONSHDLRDATA* conshdlrdata;
1469 
1470  assert(scip != NULL);
1471  assert(conshdlr != NULL);
1472  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1473 
1474  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1475  assert(conshdlrdata != NULL);
1476 
1477  /* free constraint handler storage */
1478  assert(conshdlrdata->stack == NULL);
1479  SCIPfreeMemory(scip, &conshdlrdata);
1480 
1481  return SCIP_OKAY;
1482 }
1483 
1484 
1485 /** initialization method of constraint handler (called after problem was transformed) */
1486 static
1487 SCIP_DECL_CONSINIT(consInitMasterbranch)
1488 { /*lint --e{715}*/
1489  SCIP_CONSHDLRDATA* conshdlrdata;
1490 
1491  assert(scip != NULL);
1492  assert(conshdlr != NULL);
1493  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1494 
1495  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1496  assert(conshdlrdata != NULL);
1497 
1498  /* prepare stack */
1499  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrdata->stack, conshdlrdata->maxstacksize) );
1500  conshdlrdata->nstack = 0;
1501 
1502  /* prepare pending bound changes */
1503  conshdlrdata->npendingbnds = 0;
1504  conshdlrdata->maxpendingbnds = SCIPcalcMemGrowSize(scip, 1);
1505  conshdlrdata->pendingbndsactivated = TRUE;
1506  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(conshdlrdata->pendingvars), conshdlrdata->maxpendingbnds) );
1507  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(conshdlrdata->pendingbndtypes), conshdlrdata->maxpendingbnds) );
1508  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(conshdlrdata->pendingoldbnds), conshdlrdata->maxpendingbnds) );
1509  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(conshdlrdata->pendingnewbnds), conshdlrdata->maxpendingbnds) );
1510 
1511  conshdlrdata->maxblocknum = SCIPcalcMemGrowSize(scip, GCGgetNPricingprobs(GCGmasterGetOrigprob(scip)));
1512  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(conshdlrdata->collectedbndvars), conshdlrdata->maxblocknum) );
1513  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(conshdlrdata->collectedlbnds), conshdlrdata->maxblocknum) );
1514  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(conshdlrdata->collectedubnds), conshdlrdata->maxblocknum) );
1515  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(conshdlrdata->ncollectedbndvars), conshdlrdata->maxblocknum) );
1516  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(conshdlrdata->maxcollectedbndvars), conshdlrdata->maxblocknum) );
1517  BMSclearMemoryArray(conshdlrdata->collectedbndvars, conshdlrdata->maxblocknum);
1518  BMSclearMemoryArray(conshdlrdata->collectedlbnds, conshdlrdata->maxblocknum);
1519  BMSclearMemoryArray(conshdlrdata->collectedubnds, conshdlrdata->maxblocknum);
1520  BMSclearMemoryArray(conshdlrdata->ncollectedbndvars, conshdlrdata->maxblocknum);
1521  BMSclearMemoryArray(conshdlrdata->maxcollectedbndvars, conshdlrdata->maxblocknum);
1522 
1523  conshdlrdata->maxlinkingvaridxs = 0;
1524  conshdlrdata->linkingvaridxs = NULL;
1525 
1526  return SCIP_OKAY;
1527 }
1528 
1529 
1530 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
1531 static
1532 SCIP_DECL_CONSINITSOL(consInitsolMasterbranch)
1533 { /*lint --e{715}*/
1534  SCIP_CONS* cons;
1535  SCIP_CONSHDLRDATA* conshdlrdata;
1536 
1537  assert(scip != NULL);
1538  assert(conshdlr != NULL);
1539  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1540 
1541  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1542  assert(conshdlrdata != NULL);
1543 
1544  /* create masterbranch constraint for the root node */
1545  SCIP_CALL( GCGcreateConsMasterbranch(scip, &cons, "root-masterbranch", NULL, NULL, NULL, NULL, NULL, 0, 0) );
1547 
1548  conshdlrdata->nstack = 1;
1549  conshdlrdata->stack[0] = cons;
1550 
1551  return SCIP_OKAY;
1552 }
1553 
1554 
1555 /** deinitialization method of constraint handler (called before transformed problem is freed) */
1556 static
1557 SCIP_DECL_CONSEXIT(consExitMasterbranch)
1558 { /*lint --e{715}*/
1559  SCIP_CONSHDLRDATA* conshdlrdata;
1560  int i;
1561 
1562  assert(scip != NULL);
1563  assert(conshdlr != NULL);
1564  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1565 
1566  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1567  assert(conshdlrdata != NULL);
1568  assert(conshdlrdata->nstack == 1 || SCIPgetNNodes(scip) == 0);
1569 
1570  /* free stack */
1571  SCIPfreeBlockMemoryArray(scip, &(conshdlrdata->stack), conshdlrdata->maxstacksize);
1572  SCIPfreeBlockMemoryArray(scip, &(conshdlrdata->pendingvars), conshdlrdata->maxpendingbnds);
1573  SCIPfreeBlockMemoryArray(scip, &(conshdlrdata->pendingbndtypes), conshdlrdata->maxpendingbnds);
1574  SCIPfreeBlockMemoryArray(scip, &(conshdlrdata->pendingoldbnds), conshdlrdata->maxpendingbnds);
1575  SCIPfreeBlockMemoryArray(scip, &(conshdlrdata->pendingnewbnds), conshdlrdata->maxpendingbnds);
1576 
1577  for( i = 0; i < conshdlrdata->maxblocknum; ++i )
1578  {
1579  if( conshdlrdata->maxcollectedbndvars[i] > 0)
1580  {
1581  SCIPfreeBlockMemoryArray(scip, &(conshdlrdata->collectedbndvars[i]), conshdlrdata->maxcollectedbndvars[i]);
1582  SCIPfreeBlockMemoryArray(scip, &(conshdlrdata->collectedlbnds[i]), conshdlrdata->maxcollectedbndvars[i]);
1583  SCIPfreeBlockMemoryArray(scip, &(conshdlrdata->collectedubnds[i]), conshdlrdata->maxcollectedbndvars[i]);
1584  }
1585  }
1586  SCIPfreeBlockMemoryArray(scip, &(conshdlrdata->collectedbndvars), conshdlrdata->maxblocknum);
1587  SCIPfreeBlockMemoryArray(scip, &(conshdlrdata->collectedlbnds), conshdlrdata->maxblocknum);
1588  SCIPfreeBlockMemoryArray(scip, &(conshdlrdata->collectedubnds), conshdlrdata->maxblocknum);
1589  SCIPfreeBlockMemoryArray(scip, &(conshdlrdata->ncollectedbndvars), conshdlrdata->maxblocknum);
1590  SCIPfreeBlockMemoryArray(scip, &(conshdlrdata->maxcollectedbndvars), conshdlrdata->maxblocknum);
1591 
1592  for( i = 0; i < conshdlrdata->maxlinkingvaridxs; ++i )
1593  {
1594  if( conshdlrdata->linkingvaridxs[i] != NULL)
1595  SCIPfreeBlockMemoryArray(scip, &(conshdlrdata->linkingvaridxs[i]), conshdlrdata->maxblocknum);
1596  else
1597  break;
1598  }
1599  SCIPfreeBlockMemoryArrayNull(scip, &(conshdlrdata->linkingvaridxs), conshdlrdata->maxlinkingvaridxs);
1600 
1601  return SCIP_OKAY;
1602 }
1603 
1604 
1605 /** constraint activation notification method of constraint handler */
1606 static
1607 SCIP_DECL_CONSACTIVE(consActiveMasterbranch)
1608 {
1609  SCIP* origscip;
1610  SCIP_CONSHDLRDATA* conshdlrdata;
1611  SCIP_CONSDATA* consdata;
1612 
1613  assert(scip != NULL);
1614  assert(conshdlr != NULL);
1615  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1616  assert(cons != NULL);
1617 
1618  /* get constraint handler data */
1619  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1620  assert(conshdlrdata != NULL);
1621  assert(conshdlrdata->stack != NULL);
1622 
1623  /* get constraint data */
1624  consdata = SCIPconsGetData(cons);
1625  assert(consdata != NULL);
1626  assert((consdata->node == NULL) == (consdata->parentcons == NULL));
1627 
1628  /* @fixme: This is a hack */
1629  if( consdata->node == NULL )
1630  {
1631  SCIPdebugMessage("root node not present in masterconsdata!\n");
1632  consdata->node = SCIPgetRootNode(scip);
1633  }
1634 
1635  assert(consdata->node != NULL);
1636 
1637  /* get original problem */
1638  origscip = GCGmasterGetOrigprob(scip);
1639  assert(origscip != NULL);
1640 
1641 
1642  SCIPdebugMessage("Activating ");
1643  /* If the node is activated the first time, we have to initialize the constraint data first */
1644  if( consdata->nactivated == 0 )
1645  {
1646  SCIPdebugPrintf("for the first time\n");
1647  SCIP_CALL( initializeConsdata(scip, cons) );
1648  }
1649  else
1650  SCIPdebugPrintf("\n");
1651 
1652  consdata->nactivated++;
1653 
1654  /* The node has to be repropagated if new variables were created after the node was left the last time
1655  * or if new bound changes on directly transferred variables were found
1656  */
1657  assert(GCGmasterGetNPricedvars(scip) >= consdata->npropvars);
1658  if( GCGmasterGetNPricedvars(scip) > consdata->npropvars || consdata->ncopiedvarbnds > 0 )
1659  {
1660  consdata->needprop = TRUE;
1661  SCIP_CALL( SCIPrepropagateNode(scip, consdata->node) );
1662  }
1663 
1664  if( consdata->nlocalbndchgs - consdata->nlocalbndchgstreated[conshdlrdata->nstack] > 0 )
1665  SCIPdebugMessage("added %d boundchanges from previous nodes!\n", consdata->nlocalbndchgs - consdata->nlocalbndchgstreated[conshdlrdata->nstack]);
1666 
1667  /* put constraint on the stack */
1668  if( conshdlrdata->nstack >= conshdlrdata->maxstacksize )
1669  {
1670  int newsize = SCIPcalcMemGrowSize(scip, conshdlrdata->nstack+1);
1671  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(conshdlrdata->stack), conshdlrdata->maxstacksize, newsize) );
1672 
1673  SCIPdebugMessage("reallocating Memory for stack! %d --> %d\n", conshdlrdata->maxstacksize, newsize);
1674  conshdlrdata->maxstacksize = newsize;
1675  }
1676 
1677  conshdlrdata->stack[conshdlrdata->nstack] = cons;
1678  (conshdlrdata->nstack)++;
1679 
1680  SCIPdebugMessage("Activating masterbranch constraint: <%s> [stack size: %d], needprop = %u.\n",
1681  consdata->name, conshdlrdata->nstack, consdata->needprop);
1682 
1683  /* apply global bound changes in the original problem to the pricing problems */
1684  SCIP_CALL( applyGlobalBndchgsToPricingprobs(scip) );
1685 
1686  /* apply local bound changes in the original problem to the pricing problems */
1687  SCIP_CALL( applyLocalBndchgsToPricingprobs(scip, cons) );
1688 
1689  /* call branching specific activation method */
1690  if( consdata->branchrule != NULL )
1691  {
1692  SCIP_CALL( GCGrelaxBranchActiveMaster(origscip, consdata->branchrule, consdata->branchdata) );
1693  }
1694 
1695  return SCIP_OKAY;
1696 }
1697 
1698 /** constraint deactivation notification method of constraint handler */
1699 static
1700 SCIP_DECL_CONSDEACTIVE(consDeactiveMasterbranch)
1701 {
1702  SCIP_CONSHDLRDATA* conshdlrdata;
1703  SCIP_CONSDATA* consdata;
1704  SCIP* origscip;
1705 
1706  assert(scip != NULL);
1707  assert(conshdlr != NULL);
1708  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1709  assert(cons != NULL);
1710 
1711  /* get constraint handler data */
1712  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1713  assert(conshdlrdata != NULL);
1714  assert(conshdlrdata->stack != NULL || conshdlrdata->nstack == 1);
1715  assert(conshdlrdata->nstack > 0);
1716  assert(conshdlrdata->nstack == 1 || cons == conshdlrdata->stack[conshdlrdata->nstack-1]);
1717 
1718  /* get constraint data */
1719  consdata = SCIPconsGetData(cons);
1720  assert(consdata != NULL);
1721  assert(consdata->nactivated >= 1);
1722 
1723  /* get original problem */
1724  origscip = GCGmasterGetOrigprob(scip);
1725  assert(origscip != NULL);
1726 
1727  if( !conshdlrdata->pendingbndsactivated )
1728  {
1729  SCIPdebugMessage("We need repropagation\n");
1730  consdata->needprop = TRUE;
1731  }
1732 
1733  if( SCIPgetStage(scip) == SCIP_STAGE_SOLVING )
1734  consdata->npropvars = GCGmasterGetNPricedvars(scip);
1735 
1736  /* remove constraint from the stack */
1737  (conshdlrdata->nstack)--;
1738 
1739  SCIPdebugMessage("Deactivating masterbranch constraint: <%s> [stack size: %d].\n",
1740  consdata->name, conshdlrdata->nstack);
1741 
1742  /* undo local bound changes in the original problem to the pricing problems */
1743  SCIP_CALL( undoLocalBndchgsToPricingprobs(scip, cons) );
1744 
1745  /* call branching specific deactivation method */
1746  if( consdata->branchrule != NULL )
1747  {
1748  SCIP_CALL( GCGrelaxBranchDeactiveMaster(origscip, consdata->branchrule, consdata->branchdata) );
1749  }
1750 
1751  return SCIP_OKAY;
1752 }
1753 
1754 
1755 /** frees specific constraint data */
1756 static
1757 SCIP_DECL_CONSDELETE(consDeleteMasterbranch)
1758 {
1759  SCIP* origscip;
1760  SCIP_CONSDATA* parentconsdata;
1761  SCIP_CONSDATA** childconsdatas;
1762  SCIP_CONS** childconss;
1763  int nchildconss;
1764  int i;
1765 
1766  assert(scip != NULL);
1767  assert(conshdlr != NULL);
1768 
1769  assert(cons != NULL);
1770  assert(consdata != NULL);
1771  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1772  assert(*consdata != NULL);
1773 
1774  /* get original problem */
1775  origscip = GCGmasterGetOrigprob(scip);
1776  assert(origscip != NULL);
1777 
1778  SCIPdebugMessage("Deleting masterbranch constraint: <%s>.\n", (*consdata)->name);
1779 
1780  /* remove original branching constraints if not yet done
1781  * (might happen if node is cut off before branching decisions are transferred to the original problem)
1782  */
1783  SCIP_CALL( GCGconsMasterbranchReleaseOrigbranchConss(scip, origscip, cons) );
1784 
1785  /* free arrays with local bound changes on copied original variables */
1786  if( (*consdata)->maxcopiedvarbnds > 0 )
1787  {
1788  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->copiedvars), (*consdata)->maxcopiedvarbnds);
1789  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->copiedvarbndtypes), (*consdata)->maxcopiedvarbnds);
1790  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->copiedvarbnds), (*consdata)->maxcopiedvarbnds);
1791  }
1792 
1793  /* free arrays with local bound changes on original variables belonging to a unique block */
1794  SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->nlocalbndchgstreated, (*consdata)->maxlocalbndchgstreated);
1795  if( (*consdata)->maxlocalbndchgs > 0 )
1796  {
1797  SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->localoldbnds, (*consdata)->maxlocalbndchgs);
1798  SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->localnewbnds, (*consdata)->maxlocalbndchgs);
1799  SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->localbndtypes, (*consdata)->maxlocalbndchgs);
1800  SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->localbndvars, (*consdata)->maxlocalbndchgs);
1801  }
1802 
1803  /* delete branchdata if the corresponding origcons has already been deleted;
1804  * otherwise, it will be deleted by the corresponding origbranch constraint
1805  */
1806  if( (*consdata)->origcons == NULL && (*consdata)->branchdata != NULL )
1807  {
1808  SCIP_CALL( GCGrelaxBranchDataDelete(origscip, (*consdata)->branchrule, &(*consdata)->branchdata) );
1809  (*consdata)->branchdata = NULL;
1810  (*consdata)->branchdata = NULL;
1811  }
1812  else
1813  {
1814  if( (*consdata)->branchdata != NULL )
1815  {
1816  SCIP_CALL( GCGrelaxBranchDataDelete(origscip, (*consdata)->branchrule, &(*consdata)->branchdata) );
1817  (*consdata)->branchdata = NULL;
1818  if( (*consdata)->origcons != NULL )
1819  {
1820  GCGconsOrigbranchSetBranchdata((*consdata)->origcons, NULL);
1821  }
1822  }
1823  }
1824 
1825  /* set the mastercons pointer of the corresponding origcons to NULL */
1826  if( (*consdata)->origcons != NULL )
1827  {
1828  assert(GCGconsOrigbranchGetMastercons((*consdata)->origcons) == cons);
1829  GCGconsOrigbranchSetMastercons((*consdata)->origcons, NULL);
1830  }
1831 
1832  /* remove branching constraints at child nodes */
1833  nchildconss = (*consdata)->nchildconss;
1834  if( nchildconss > 0 )
1835  {
1836  SCIP_CALL( SCIPallocBufferArray(scip, &childconsdatas, nchildconss) );
1837  SCIP_CALL( SCIPallocBufferArray(scip, &childconss, nchildconss) );
1838 
1839  for( i = 0; i < nchildconss; ++i )
1840  {
1841  if( (*consdata)->childconss != NULL && (*consdata)->childconss[i] != NULL )
1842  {
1843  childconsdatas[i] = SCIPconsGetData((*consdata)->childconss[i]);
1844  childconss[i] = (*consdata)->childconss[i];
1845  }
1846  else
1847  {
1848  childconsdatas[i] = NULL;
1849  childconss[i] = NULL;
1850  }
1851  }
1852 
1853  /* delete childnodes */
1854  for( i = 0; i < nchildconss; ++i )
1855  {
1856  SCIPdebugMessage("Deleting %d childnodes\n", nchildconss);
1857 
1858  if( childconss[i] != NULL )
1859  {
1860  /*SCIP_CALL( consDeleteMasterbranch(scip, conshdlr, childcons[i], &childconsdatas[i]) );*/
1861  SCIP_CALL( SCIPreleaseCons(scip, &childconss[i]) );
1862  childconss[i] = NULL;
1863  }
1864  }
1865 
1866  SCIPfreeBufferArray(scip, &childconss);
1867  SCIPfreeBufferArray(scip, &childconsdatas);
1868  }
1869  assert((*consdata)->nchildconss == 0);
1870 
1871  /* set the pointer in the parent node to NULL */
1872  if( (*consdata)->parentcons != NULL )
1873  {
1874  SCIP_Bool isinprobing;
1875 #ifndef NDEBUG
1876  SCIP_Bool childdeleted = FALSE;
1877 #endif
1878 
1879  parentconsdata = SCIPconsGetData((*consdata)->parentcons);
1880 
1881  isinprobing = (SCIPgetStage(scip) <= SCIP_STAGE_SOLVING && SCIPinProbing(scip)) || (SCIPgetStage(origscip) <= SCIP_STAGE_SOLVING && SCIPinProbing(origscip));
1882  if( isinprobing )
1883  parentconsdata->probingtmpcons = NULL;
1884 
1885  for( i = 0; i < parentconsdata->nchildconss; ++i )
1886  {
1887  if( parentconsdata->childconss[i] == cons )
1888  {
1889  parentconsdata->childconss[i] = parentconsdata->childconss[parentconsdata->nchildconss-1];
1890 
1891  parentconsdata->childconss[parentconsdata->nchildconss-1] = NULL;
1892  parentconsdata->nchildconss--;
1893 #ifndef NDEBUG
1894  childdeleted = TRUE;
1895 #endif
1896  break;
1897  }
1898  }
1899  assert(childdeleted || isinprobing);
1900  }
1901 
1902  SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->childconss, (*consdata)->maxchildconss);
1903 
1904  if( (*consdata)->name != NULL )
1905  {
1906  SCIPfreeBlockMemoryArray(scip, &(*consdata)->name, strlen((*consdata)->name)+1);
1907  }
1908 
1909  SCIPfreeBlockMemoryNull(scip, consdata);
1910  *consdata = NULL;
1911 
1912  return SCIP_OKAY;
1913 }
1914 
1915 
1916 /** domain propagation method of constraint handler */
1917 static
1918 SCIP_DECL_CONSPROP(consPropMasterbranch)
1919 { /*lint --e{715}*/
1920  SCIP* origscip;
1921  SCIP_CONSHDLRDATA* conshdlrdata;
1922  SCIP_CONS* cons;
1923  SCIP_CONSDATA* consdata;
1924 
1925  int propcount;
1926 
1927  assert(conshdlr != NULL);
1928  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1929  assert(conshdlrdata != NULL);
1930  assert(conshdlrdata->stack != NULL);
1931 
1932  /* get original problem */
1933  origscip = GCGmasterGetOrigprob(scip);
1934  assert(origscip != NULL);
1935 
1936  *result = SCIP_DIDNOTRUN;
1937 
1938  /* the constraint data of the cons related to the current node */
1939  cons = conshdlrdata->stack[conshdlrdata->nstack-1];
1940  assert(cons != NULL);
1941 
1942  consdata = SCIPconsGetData(cons);
1943  assert(consdata != NULL);
1944 
1945  if( !consdata->needprop && consdata->ncopiedvarbnds == 0 )
1946  {
1947  SCIPdebugMessage("No propagation of masterbranch constraint needed: <%s>, stack size = %d.\n",
1948  consdata->name, conshdlrdata->nstack);
1949 
1950  *result = SCIP_DIDNOTRUN;
1951  return SCIP_OKAY;
1952  }
1953 
1954  SCIPdebugMessage("Starting propagation of masterbranch constraint: <%s>, stack size = %d, newvars = %d, npendingbnds = %d, npropbounds = %d.\n",
1955  consdata->name, conshdlrdata->nstack, GCGmasterGetNPricedvars(scip) - consdata->npropvars, conshdlrdata->npendingbnds, consdata->ncopiedvarbnds);
1956 
1957  *result = SCIP_DIDNOTFIND;
1958 
1959  propcount = 0;
1960 
1961  /* apply global bound changes on original problem variables to the master problem */
1962  SCIP_CALL( applyGlobalBndchgsToPricedMastervars(scip, &propcount) );
1963 
1964  /* apply local bound changes on the original variables on newly generated master variables */
1965  SCIP_CALL( applyLocalBndchgsToPricedMastervars(scip, cons, &propcount) );
1966 
1967  /* apply local bound changes on original variables that have been directly copied to the master problem */
1968  SCIP_CALL( applyLocalBndchgsToCopiedMastervars(scip, cons, &propcount) );
1969 
1970  /* call branching rule specific propagation method */
1971  if( consdata->branchrule != NULL )
1972  {
1973  /** @todo count number of propagations */
1974  SCIP_CALL( GCGrelaxBranchPropMaster(origscip, consdata->branchrule, consdata->branchdata, result) );
1975  }
1976 
1977  if( *result != SCIP_CUTOFF && propcount > 0 )
1978  *result = SCIP_REDUCEDDOM;
1979 
1980  consdata->needprop = FALSE;
1981  consdata->npropvars = GCGmasterGetNPricedvars(scip);
1982 
1983  return SCIP_OKAY;
1984 }
1985 
1986 
1987 /** enforcement method for LP solutions */
1988 static
1989 SCIP_DECL_CONSENFOLP(consEnfolpMasterbranch)
1990 { /*lint --e{715}*/
1991  *result = SCIP_FEASIBLE;
1992 
1993  return SCIP_OKAY;
1994 }
1995 
1996 /** enforcement method for pseudo solutions */
1997 static
1998 SCIP_DECL_CONSENFOPS(consEnfopsMasterbranch)
1999 { /*lint --e{715}*/
2000  *result = SCIP_FEASIBLE;
2001 
2002  return SCIP_OKAY;
2003 }
2004 
2005 /** check method for solutions */
2006 static
2007 SCIP_DECL_CONSCHECK(consCheckMasterbranch)
2008 { /*lint --e{715}*/
2009  *result = SCIP_FEASIBLE;
2010 
2011  return SCIP_OKAY;
2012 }
2013 
2014 /** variable lock method */
2015 static
2016 SCIP_DECL_CONSLOCK(consLockMasterbranch)
2017 { /*lint --e{715}*/
2018  return SCIP_OKAY;
2019 }
2020 
2021 
2022 /*
2023  * Callback methods of event handler
2024  */
2025 
2026 /** solving process initialization method of event handler (called when branch and bound process is about to begin) */
2027 static
2028 SCIP_DECL_EVENTINITSOL(eventInitsolOrigvarbound)
2029 { /*lint --e{715}*/
2030  SCIP_VAR** vars;
2031  int nvars;
2032  int i;
2033 
2034  vars = SCIPgetVars(scip);
2035  nvars = SCIPgetNVars(scip);
2036 
2037  for( i = 0; i < nvars; i++ )
2038  {
2039  SCIP_CALL( SCIPcatchVarEvent(scip, vars[i], SCIP_EVENTTYPE_GBDCHANGED | SCIP_EVENTTYPE_BOUNDCHANGED,
2040  eventhdlr, NULL, NULL) );
2041  }
2042 
2043  return SCIP_OKAY;
2044 }
2045 
2046 /** execution method of event handler */
2047 static
2048 SCIP_DECL_EVENTEXEC(eventExecOrigvarbound)
2049 { /*lint --e{715}*/
2050  SCIP* masterscip;
2051  SCIP_EVENTTYPE eventtype;
2052  SCIP_VAR* var;
2053  SCIP_Real oldbound;
2054  SCIP_Real newbound;
2055  int blocknr;
2056 #ifdef SCIP_DEBUG
2057  SCIP_Bool handled = FALSE;
2058 #endif
2059  SCIP_VAR** mastervars;
2060 #ifndef NDEBUG
2061  int nmastervars;
2062  SCIP_Real* mastervals;
2063 #endif
2064 
2065  /* get master problem */
2066  masterscip = GCGgetMasterprob(scip);
2067  assert(masterscip != NULL);
2068 
2069  /* get event data */
2070  eventtype = SCIPeventGetType(event);
2071  var = SCIPeventGetVar(event);
2072  oldbound = SCIPeventGetOldbound(event);
2073  newbound = SCIPeventGetNewbound(event);
2074 
2075  SCIPdebugMessage("eventexec: eventtype = 0x%x, var = %s, oldbound = %f, newbound = %f\n", (unsigned int) eventtype, SCIPvarGetName(var), oldbound, newbound);
2076 
2077  if( !GCGrelaxIsInitialized(scip) )
2078  {
2079 // assert(SCIPvarGetData(var) == NULL);
2080  SCIPdebugMessage("Ignoring since in presolving / propagating.\n");
2081  return SCIP_OKAY;
2082  }
2083 
2084  assert(GCGvarIsOriginal(var));
2085  blocknr = GCGvarGetBlock(var);
2086 
2087  mastervars = GCGoriginalVarGetMastervars(var);
2088 #ifndef NDEBUG
2089  nmastervars = GCGoriginalVarGetNMastervars(var);
2090  mastervals = GCGoriginalVarGetMastervals(var);
2091 #endif
2092 
2093  /* A global bound change might turn the current relaxation solution invalid */
2094  if( SCIPisRelaxSolValid(scip)
2095  && (((eventtype & SCIP_EVENTTYPE_GLBCHANGED) != 0 && SCIPisFeasLT(scip, SCIPgetRelaxSolVal(scip, var), newbound))
2096  || ((eventtype & SCIP_EVENTTYPE_GUBCHANGED) != 0 && SCIPisFeasGT(scip, SCIPgetRelaxSolVal(scip, var), newbound))) )
2097  {
2098  SCIP_CALL( SCIPmarkRelaxSolInvalid(scip) );
2099  }
2100 
2101  /* deal with variables present in the pricing */
2102  if( blocknr >= 0 && GCGisPricingprobRelevant(scip, blocknr) )
2103  {
2104  SCIPdebugMessage("Pricing var!\n");
2105  if( (eventtype & SCIP_EVENTTYPE_GLBCHANGED) != 0 )
2106  {
2107 #ifdef SCIP_DEBUG
2108  handled = TRUE;
2109 #endif
2110  SCIP_CALL( addPendingBndChg(masterscip, GCGoriginalVarGetPricingVar(var), SCIP_BOUNDTYPE_LOWER, oldbound, newbound) );
2111  }
2112  if( (eventtype & SCIP_EVENTTYPE_GUBCHANGED) != 0 )
2113  {
2114 #ifdef SCIP_DEBUG
2115  handled = TRUE;
2116 #endif
2117  SCIP_CALL( addPendingBndChg(masterscip, GCGoriginalVarGetPricingVar(var), SCIP_BOUNDTYPE_UPPER, oldbound, newbound) );
2118  }
2119  }
2120  /* deal with variables appearing in the master only */
2121  if( blocknr == -1 && SCIPgetStage(masterscip) >= SCIP_STAGE_SOLVING )
2122  {
2123  assert(nmastervars == 1);
2124  assert(mastervals[0] == 1);
2125  assert(mastervars[0] != NULL);
2126 
2127  SCIPdebugMessage("Master var!\n");
2128  if( (eventtype & SCIP_EVENTTYPE_GLBCHANGED) != 0 )
2129  {
2130 #ifdef SCIP_DEBUG
2131  handled = TRUE;
2132 #endif
2133  SCIP_CALL( addPendingBndChg(masterscip, mastervars[0], SCIP_BOUNDTYPE_LOWER, oldbound, newbound) );
2134  }
2135  if( (eventtype & SCIP_EVENTTYPE_GUBCHANGED) != 0 )
2136  {
2137 #ifdef SCIP_DEBUG
2138  handled = TRUE;
2139 #endif
2140  SCIP_CALL( addPendingBndChg(masterscip, mastervars[0], SCIP_BOUNDTYPE_UPPER, oldbound, newbound) );
2141  }
2142  }
2143  /* deal with linking variables */
2144  if( blocknr == -2 )
2145  {
2146  int npricingprobs;
2147  SCIP_VAR** pricingvars;
2148  int i;
2149 
2150  SCIPdebugMessage("Linking var!\n");
2151  pricingvars = GCGlinkingVarGetPricingVars(var);
2152  npricingprobs = GCGgetNPricingprobs(scip);
2153 
2154  assert(nmastervars >= 1);
2155  assert(mastervals[0] == 1);
2156  assert(mastervars[0] != NULL);
2157  assert(GCGvarGetBlock(mastervars[0]) == -1);
2158 
2159  if( (eventtype & SCIP_EVENTTYPE_GLBCHANGED) != 0 )
2160  {
2161  if( SCIPgetStage(masterscip) >= SCIP_STAGE_SOLVING )
2162  {
2163 #ifdef SCIP_DEBUG
2164  handled = TRUE;
2165 #endif
2166  /* add the bound change in the master */
2167  SCIP_CALL( addPendingBndChg(masterscip, mastervars[0], SCIP_BOUNDTYPE_LOWER, oldbound, newbound) );
2168  }
2169 
2170  /* add the bound change to the pricing problems */
2171  for( i = 0; i < npricingprobs; ++i )
2172  {
2173  if( pricingvars[i] == NULL )
2174  continue;
2175 #ifdef SCIP_DEBUG
2176  handled = TRUE;
2177 #endif
2178  SCIP_CALL( addPendingBndChg(masterscip, pricingvars[i], SCIP_BOUNDTYPE_LOWER, oldbound, newbound) );
2179  }
2180  }
2181  if( (eventtype & SCIP_EVENTTYPE_GUBCHANGED) != 0 )
2182  {
2183  if( SCIPgetStage(masterscip) >= SCIP_STAGE_SOLVING )
2184  {
2185 #ifdef SCIP_DEBUG
2186  handled = TRUE;
2187 #endif
2188  /* add the bound change in the master */
2189  SCIP_CALL( addPendingBndChg(masterscip, mastervars[0], SCIP_BOUNDTYPE_UPPER, oldbound, newbound) );
2190  }
2191 
2192  /* add the bound change to the pricing problems */
2193  for( i = 0; i < npricingprobs; ++i )
2194  {
2195  if( pricingvars[i] == NULL )
2196  continue;
2197 #ifdef SCIP_DEBUG
2198  handled = TRUE;
2199 #endif
2200  SCIP_CALL( addPendingBndChg(masterscip, pricingvars[i], SCIP_BOUNDTYPE_UPPER, oldbound, newbound) );
2201  }
2202 
2203  }
2204 
2205  }
2206 #ifdef SCIP_DEBUG
2207  if( !handled )
2208  {
2209  SCIPdebugMessage("Effectively ignoring this change\n");
2210  }
2211 #endif
2212 
2213  return SCIP_OKAY;
2214 }
2215 
2216 
2217 /*
2218  * interface methods
2219  */
2220 
2221 
2222 /** creates the handler for masterbranch constraints and includes it in SCIP */
2224  SCIP* scip /**< SCIP data structure */
2225  )
2226 {
2227  SCIP* origscip;
2228  SCIP_CONSHDLR* conshdlr;
2229  SCIP_CONSHDLRDATA* conshdlrdata;
2230  SCIP_EVENTHDLR* eventhdlr;
2231  SCIP_EVENTHDLRDATA* eventhdlrdata;
2232 
2233  /* get original problem */
2234  origscip = GCGmasterGetOrigprob(scip);
2235  assert(origscip != NULL);
2236 
2237  SCIP_CALL( SCIPallocMemory(scip, &conshdlrdata) );
2238  conshdlrdata->stack = NULL;
2239  conshdlrdata->nstack = 0;
2240  conshdlrdata->maxstacksize = 25;
2241 
2242  /* include constraint handler */
2243  SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC,
2245  consEnfolpMasterbranch, consEnfopsMasterbranch, consCheckMasterbranch, consLockMasterbranch,
2246  conshdlrdata) );
2247  assert(conshdlr != NULL);
2248 
2249  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeMasterbranch) );
2250  SCIP_CALL( SCIPsetConshdlrInit(scip, conshdlr, consInitMasterbranch) );
2251  SCIP_CALL( SCIPsetConshdlrExit(scip, conshdlr, consExitMasterbranch) );
2252  SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolMasterbranch) );
2253  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteMasterbranch) );
2254  SCIP_CALL( SCIPsetConshdlrActive(scip, conshdlr, consActiveMasterbranch) );
2255  SCIP_CALL( SCIPsetConshdlrDeactive(scip, conshdlr, consDeactiveMasterbranch) );
2256  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropMasterbranch, CONSHDLR_PROPFREQ,
2258 
2259  /* create event handler data */
2260  eventhdlrdata = NULL;
2261 
2262  /* include event handler into original SCIP */
2263  SCIP_CALL( SCIPincludeEventhdlrBasic(origscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
2264  eventExecOrigvarbound, eventhdlrdata) );
2265  assert(eventhdlr != NULL);
2266 
2267  /* set non fundamental callbacks via setter functions */
2268  SCIP_CALL( SCIPsetEventhdlrInitsol(origscip, eventhdlr, eventInitsolOrigvarbound) );
2269 
2270  SCIP_CALL( SCIPaddBoolParam(origscip, "relaxing/gcg/enforceproper",
2271  "should propagated bound changes in the original be enforced in the master (only proper vars)?",
2272  &conshdlrdata->enforceproper, FALSE, TRUE, NULL, NULL) );
2273 
2274  return SCIP_OKAY;
2275 }
2276 
2277 /** creates and captures a masterbranch constraint */
2279  SCIP* scip, /**< SCIP data structure */
2280  SCIP_CONS** cons, /**< pointer to hold the created constraint */
2281  const char* name, /**< name of the constraint */
2282  SCIP_NODE* node, /**< node at which the constraint should be created */
2283  SCIP_CONS* parentcons, /**< parent constraint */
2284  SCIP_BRANCHRULE* branchrule, /**< pointer to the branching rule */
2285  GCG_BRANCHDATA* branchdata, /**< branching data */
2286  SCIP_CONS** origbranchconss, /**< original constraints enforcing the branching decision */
2287  int norigbranchconss, /**< number of original constraints */
2288  int maxorigbranchconss /**< capacity of origbranchconss */
2289  )
2290 {
2291  SCIP_CONSHDLR* conshdlr;
2292  SCIP_CONSDATA* consdata;
2293 
2294  assert(scip != NULL);
2295  assert(node != NULL || parentcons == NULL);
2296  if( node != NULL )
2297  assert((parentcons == NULL) == (SCIPnodeGetDepth(node) == 0));
2298  else
2299  assert(parentcons == NULL);
2300 
2301  /* find the masterbranch constraint handler */
2302  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2303  assert(conshdlr != NULL);
2304 
2305  /* create constraint data */
2306  SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
2307 
2308  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(consdata->name), name, strlen(name)+1) );
2309 
2310  consdata->npropvars = 0;
2311  consdata->needprop = TRUE;
2312  consdata->node = node;
2313  consdata->nactivated = 0;
2314 
2315  consdata->parentcons = parentcons;
2316  consdata->childconss = NULL;
2317  consdata->nchildconss = 0;
2318  consdata->maxchildconss = 0;
2319  consdata->probingtmpcons = NULL;
2320  consdata->origcons = NULL;
2321 
2322  consdata->branchdata = branchdata;
2323  consdata->branchrule = branchrule;
2324 
2325  consdata->localbndvars = NULL;
2326  consdata->localbndtypes = NULL;
2327  consdata->localnewbnds = NULL;
2328  consdata->localoldbnds = NULL;
2329  consdata->nlocalbndchgstreated = NULL;
2330  consdata->maxlocalbndchgstreated = 0;
2331  consdata->nlocalbndchgs = 0;
2332  consdata->maxlocalbndchgs = 0;
2333  consdata->nbranchingchgs = 0;
2334 
2335  consdata->copiedvars = NULL;
2336  consdata->copiedvarbndtypes = NULL;
2337  consdata->copiedvarbnds = NULL;
2338  consdata->ncopiedvarbnds = 0;
2339  consdata->maxcopiedvarbnds = 0;
2340 
2341  consdata->maxorigbranchconss = maxorigbranchconss;
2342  consdata->origbranchconss = origbranchconss;
2343  consdata->norigbranchconss = norigbranchconss;
2344 
2345  SCIPdebugMessage("Creating masterbranch constraint with parent %p.\n", (void*) parentcons);
2346 
2347  /* create constraint */
2348  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, FALSE, FALSE, FALSE, FALSE, TRUE,
2349  TRUE, FALSE, FALSE, FALSE, TRUE) );
2350 
2351  /* add the new masterbranch constraint to the parent node's masterbranch constraint data
2352  * (unless the current node is the root node)
2353  */
2354  if( parentcons != NULL )
2355  {
2356  SCIP_CONSDATA* parentdata;
2357 
2358  parentdata = SCIPconsGetData(parentcons);
2359  assert(parentdata != NULL);
2360 
2361  if( SCIPinProbing(scip) || SCIPinProbing(GCGmasterGetOrigprob(scip)) )
2362  {
2363  parentdata->probingtmpcons = *cons;
2364  }
2365  else
2366  {
2367  int newmaxsize;
2368  ++parentdata->nchildconss;
2369  newmaxsize = SCIPcalcMemGrowSize(scip, parentdata->nchildconss);
2370  if( parentdata->nchildconss == 1 )
2371  {
2372  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(parentdata->childconss), newmaxsize) );
2373  parentdata->childconss[0] = NULL;
2374  }
2375  else
2376  {
2377  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(parentdata->childconss), parentdata->maxchildconss, newmaxsize) );
2378  parentdata->childconss[parentdata->nchildconss - 1] = NULL;
2379  }
2380  parentdata->maxchildconss = newmaxsize;
2381 
2382  assert(parentdata->childconss[parentdata->nchildconss - 1] == NULL);
2383  parentdata->childconss[parentdata->nchildconss - 1] = *cons;
2384  }
2385  }
2386 
2387  return SCIP_OKAY;
2388 }
2389 
2390 /** returns the name of the constraint */
2392  SCIP_CONS* cons /**< masterbranch constraint for which the data is requested */
2393  )
2394 {
2395  SCIP_CONSDATA* consdata;
2396 
2397  consdata = SCIPconsGetData(cons);
2398  assert(consdata != NULL);
2399 
2400  return consdata->name;
2401 }
2402 
2403 /** returns the node in the B&B tree at which the given masterbranch constraint is sticking */
2405  SCIP_CONS* cons /**< constraint pointer */
2406  )
2407 {
2408  SCIP_CONSDATA* consdata;
2409 
2410  consdata = SCIPconsGetData(cons);
2411  assert(consdata != NULL);
2412 
2413  return consdata->node;
2414 }
2415 
2416 /** returns the masterbranch constraint of the B&B father of the node at which the
2417  * given masterbranch constraint is sticking
2418  */
2420  SCIP_CONS* cons /**< constraint pointer */
2421  )
2422 {
2423  SCIP_CONSDATA* consdata;
2424 
2425  consdata = SCIPconsGetData(cons);
2426  assert(consdata != NULL);
2427 
2428  return consdata->parentcons;
2429 }
2430 
2431 /** returns the number of masterbranch constraints of the children of the node at which the
2432  * given masterbranch constraint is sticking
2433  */
2435  SCIP_CONS* cons /**< constraint pointer */
2436  )
2437 {
2438  SCIP_CONSDATA* consdata;
2439 
2440  consdata = SCIPconsGetData(cons);
2441  assert(consdata != NULL);
2442 
2443  return consdata->nchildconss;
2444 }
2445 
2446 /** returns a masterbranch constraint of a child of the node at which the
2447  * given masterbranch constraint is sticking
2448  */
2450  SCIP_CONS* cons, /**< constraint pointer */
2451  int childnr /**< index of the child node */
2452  )
2453 {
2454  SCIP_CONSDATA* consdata;
2455 
2456  consdata = SCIPconsGetData(cons);
2457  assert(consdata != NULL);
2458  assert(consdata->childconss != NULL);
2459 
2460  assert(consdata->nchildconss > childnr);
2461 
2462  return consdata->childconss[childnr];
2463 }
2464 
2465 /** returns the origbranch constraint of the node in the original program corresponding to the node
2466  * at which the given masterbranch constraint is sticking
2467  */
2469  SCIP_CONS* cons /**< constraint pointer */
2470  )
2471 {
2472  SCIP_CONSDATA* consdata;
2473 
2474  consdata = SCIPconsGetData(cons);
2475  assert(consdata != NULL);
2476 
2477  return consdata->origcons;
2478 }
2479 
2480 /** sets the origbranch constraint of the node in the master program corresponding to the node
2481  * at which the given masterbranchbranch constraint is sticking
2482  */
2484  SCIP_CONS* cons, /**< constraint pointer */
2485  SCIP_CONS* origcons /**< original branching constraint */
2486  )
2487 {
2488  SCIP_CONSDATA* consdata;
2489 
2490  consdata = SCIPconsGetData(cons);
2491  assert(consdata != NULL);
2492  assert(consdata->origcons == NULL || origcons == NULL);
2493 
2494  consdata->origcons = origcons;
2495 }
2496 
2497 /** returns the branching data for a given masterbranch constraint */
2499  SCIP_CONS* cons /**< constraint pointer */
2500  )
2501 {
2502  SCIP_CONSDATA* consdata;
2503 
2504  consdata = SCIPconsGetData(cons);
2505  assert(consdata != NULL);
2506 
2507  return consdata->branchdata;
2508 }
2509 
2510 /** returns the branching rule of the constraint */
2512  SCIP_CONS* cons /**< masterbranch constraint for which the data is requested */
2513  )
2514 {
2515  SCIP_CONSDATA* consdata;
2516 
2517  consdata = SCIPconsGetData(cons);
2518  assert(consdata != NULL);
2519 
2520  return consdata->branchrule;
2521 }
2522 
2523 /** adds a bound change on an original variable that was directly copied to the master problem */
2525  SCIP* scip, /**< SCIP data structure */
2526  SCIP_CONS* cons, /**< masterbranch constraint to which the bound change is added */
2527  SCIP_VAR* var, /**< variable on which the bound change was performed */
2528  GCG_BOUNDTYPE boundtype, /**< bound type of the bound change */
2529  SCIP_Real newbound /**< new bound of the variable after the bound change */
2530  )
2531 {
2532  SCIP_CONSDATA* consdata;
2533 
2534  assert(scip != NULL);
2535  assert(GCGisMaster(scip));
2536  assert(cons != NULL);
2537  assert(var != NULL);
2538 
2539  /* get constraint data */
2540  consdata = SCIPconsGetData(cons);
2541  assert(consdata != NULL);
2542 
2543  /* realloc the arrays, if needed */
2544  if( consdata->ncopiedvarbnds >= consdata->maxcopiedvarbnds )
2545  {
2546  int newsize = SCIPcalcMemGrowSize(scip, consdata->ncopiedvarbnds+1);
2547  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->copiedvars), consdata->maxcopiedvarbnds, newsize) );
2548  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->copiedvarbndtypes), consdata->maxcopiedvarbnds, newsize) );
2549  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->copiedvarbnds), consdata->maxcopiedvarbnds, newsize) );
2550  consdata->maxcopiedvarbnds = newsize;
2551  }
2552 
2553  SCIPdebugMessage("Bound change on copied original variable stored at masterbranch constraint: <%s>.\n", SCIPconsGetName(cons));
2554 
2555  /* store the new bound change */
2556  consdata->copiedvars[consdata->ncopiedvarbnds] = var;
2557  consdata->copiedvarbndtypes[consdata->ncopiedvarbnds] = boundtype;
2558  consdata->copiedvarbnds[consdata->ncopiedvarbnds] = newbound;
2559  consdata->ncopiedvarbnds++;
2560 
2561  /* mark the corresponding master node to be repropagated */
2562  SCIP_CALL( SCIPrepropagateNode(scip, consdata->node) );
2563 
2564  return SCIP_OKAY;
2565 }
2566 
2567 /** returns the constraints in the original problem that enforce the branching decision */
2569  SCIP_CONS* cons /**< masterbranch constraint for which the data is requested */
2570  )
2571 {
2572  SCIP_CONSDATA* consdata;
2573 
2574  consdata = SCIPconsGetData(cons);
2575  assert(consdata != NULL);
2576 
2577  return consdata->origbranchconss;
2578 }
2579 
2580 /** returns the number of constraints in the original problem that enforce the branching decision */
2582  SCIP_CONS* cons /**< masterbranch constraint for which the data is requested */
2583  )
2584 {
2585  SCIP_CONSDATA* consdata;
2586 
2587  consdata = SCIPconsGetData(cons);
2588  assert(consdata != NULL);
2589 
2590  return consdata->norigbranchconss;
2591 }
2592 
2593 /** releases the constraints in the original problem that enforce the branching decision
2594  * and frees the array holding the constraints
2595  */
2597  SCIP* masterscip, /**< master problem SCIP instance */
2598  SCIP* origscip, /**< original SCIP instance */
2599  SCIP_CONS* cons /**< masterbranch constraint for which the data is freed */
2600  )
2601 {
2602  SCIP_CONSDATA* consdata;
2603 
2604  assert(GCGisMaster(masterscip));
2605  assert(GCGisOriginal(origscip));
2606 
2607  consdata = SCIPconsGetData(cons);
2608  assert(consdata != NULL);
2609 
2610  if( consdata->norigbranchconss > 0 )
2611  {
2612  int c;
2613 
2614  for( c = consdata->norigbranchconss - 1; c >= 0; --c )
2615  {
2616  SCIP_CALL( SCIPreleaseCons(origscip, &consdata->origbranchconss[c]) );
2617  }
2618  SCIPfreeBlockMemoryArray(masterscip, &consdata->origbranchconss, consdata->maxorigbranchconss);
2619  consdata->origbranchconss = NULL;
2620  consdata->norigbranchconss = 0;
2621  consdata->maxorigbranchconss = 0;
2622  }
2623 
2624  return SCIP_OKAY;
2625 }
2626 
2627 /** returns the masterbranch constraint of the current node */
2629  SCIP* scip /**< SCIP data structure */
2630  )
2631 {
2632  SCIP_CONSHDLR* conshdlr;
2633  SCIP_CONSHDLRDATA* conshdlrdata;
2634 
2635  assert(scip != NULL);
2636  assert(GCGisMaster(scip));
2637 
2638  /* get constraint handler */
2639  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2640  assert(conshdlr != NULL);
2641 
2642  /* get constraint handler data */
2643  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2644  assert(conshdlrdata != NULL);
2645  assert(conshdlrdata->stack != NULL);
2646 
2647  if( conshdlrdata->nstack == 0 )
2648  return NULL;
2649 
2650  assert(conshdlrdata->stack[conshdlrdata->nstack-1] != NULL);
2651  return conshdlrdata->stack[conshdlrdata->nstack-1];
2652 }
2653 
2654 /** returns the stack and the number of elements on it */
2656  SCIP* scip, /**< SCIP data structure */
2657  SCIP_CONS*** stack, /**< return value: pointer to the stack */
2658  int* nstackelements /**< return value: pointer to int, for number of elements on the stack */
2659  )
2660 {
2661  SCIP_CONSHDLR* conshdlr;
2662  SCIP_CONSHDLRDATA* conshdlrdata;
2663 
2664  assert(scip != NULL);
2665  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2666  assert(conshdlr != NULL);
2667 
2668  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2669  assert(conshdlrdata != NULL);
2670  assert(conshdlrdata->stack != NULL);
2671 
2672  *stack = conshdlrdata->stack;
2673  *nstackelements = conshdlrdata->nstack;
2674 }
2675 
2676 /** returns the number of elements on the stack */
2678  SCIP* scip /**< SCIP data structure */
2679  )
2680 {
2681  SCIP_CONSHDLR* conshdlr;
2682  SCIP_CONSHDLRDATA* conshdlrdata;
2683 
2684  assert(scip != NULL);
2685  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2686  assert(conshdlr != NULL);
2687 
2688  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2689  assert(conshdlrdata != NULL);
2690  assert(conshdlrdata->stack != NULL);
2691 
2692  return conshdlrdata->nstack;
2693 }
2694 
2695 /** adds initial constraint to root node */
2697  SCIP* scip /**< SCIP data structure */
2698  )
2699 {
2700  SCIP_CONSHDLR* conshdlr;
2701  SCIP_CONSHDLRDATA* conshdlrdata;
2702  SCIP_CONS* cons;
2703 
2704  assert(scip != NULL);
2705  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2706  assert(conshdlr != NULL);
2707 
2708  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2709  assert(conshdlrdata != NULL);
2710  cons = conshdlrdata->stack[0];
2711  conshdlrdata->stack[0] = NULL;
2712  assert(conshdlrdata->nstack == 1);
2713  conshdlrdata->nstack = 0;
2714 
2715  SCIP_CALL( SCIPaddConsNode(scip, SCIPgetRootNode(scip), cons, SCIPgetRootNode(scip)) );
2716  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
2717 
2718  return SCIP_OKAY;
2719 }
2720 
2721 /** check whether the node was generated by generic branching */
2723  SCIP* scip /**< SCIP data structure */
2724  )
2725 {
2726  SCIP_CONS* mastercons;
2727  SCIP_BRANCHRULE* branchrule;
2728 
2729  assert(scip != NULL);
2730  assert(GCGisMaster(scip));
2731 
2732  mastercons = GCGconsMasterbranchGetActiveCons(scip);
2733 
2734  /* @todo: Why might mastercons be NULL? */
2735  if( mastercons == NULL || SCIPnodeGetDepth(GCGconsMasterbranchGetNode(mastercons)) == 0 )
2736  return FALSE;
2737 
2738  branchrule = GCGconsMasterbranchGetBranchrule(mastercons);
2739 
2740  if( branchrule == NULL || strcmp(SCIPbranchruleGetName(branchrule), "generic") != 0 )
2741  return FALSE;
2742 
2743  return TRUE;
2744 }
2745 
2746 /** checks the consistency of the masterbranch constraints in the problem */
2748  SCIP* scip /**< SCIP data structure */
2749  )
2750 {
2751  SCIP_CONSHDLR* conshdlr;
2752  int nconss;
2753 #ifndef NDEBUG
2754  int i;
2755  SCIP_CONS** conss;
2756 #endif
2757 
2758  assert(scip != NULL);
2759  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2760  assert(conshdlr != NULL);
2761 
2762  nconss = SCIPconshdlrGetNConss(conshdlr);
2763 #ifndef NDEBUG
2764  conss = SCIPconshdlrGetConss(conshdlr);
2765 
2766  for( i = 0; i < nconss; i++ )
2767  {
2768  SCIP_CONSDATA* consdata;
2769 #ifdef SCIP_DEBUG
2770  SCIP_CONS* parent_origcons;
2771  SCIP_CONS* origcons_parent;
2772 #endif
2773 
2774  consdata = SCIPconsGetData(conss[i]);
2775  assert(consdata != NULL);
2776 
2777  assert(consdata->probingtmpcons == NULL || SCIPinProbing(scip));
2778  assert(consdata->probingtmpcons == NULL || SCIPconsGetData(consdata->probingtmpcons)->parentcons == conss[i]);
2779  assert(consdata->origcons == NULL || GCGconsOrigbranchGetMastercons(consdata->origcons) == conss[i]);
2780 
2781 #ifdef SCIP_DEBUG
2782  if( consdata->parentcons != NULL )
2783  parent_origcons = SCIPconsGetData(consdata->parentcons)->origcons;
2784  else
2785  parent_origcons = NULL;
2786 
2787  if( consdata->origcons != NULL )
2788  origcons_parent = GCGconsOrigbranchGetParentcons(consdata->origcons);
2789  else
2790  origcons_parent = NULL;
2791 
2792  SCIPdebugMessage("cons: %s (node %p), origcons: %s, parent %s: %s => %s\n",
2793  SCIPconsGetName(conss[i]),
2794  (void*) consdata->node,
2795  consdata->origcons == NULL? "NULL" : SCIPconsGetName(consdata->origcons),
2796  consdata->parentcons == NULL? "NULL" : SCIPconsGetName(consdata->parentcons),
2797  parent_origcons == NULL? "NULL" : SCIPconsGetName(parent_origcons),
2798  origcons_parent == NULL? "NULL" : SCIPconsGetName(origcons_parent) );
2799 #endif
2800  }
2801 #endif
2802 
2803  SCIPdebugMessage("checked consistency of %d masterbranch constraints, all ok!\n", nconss);
2804 }
static SCIP_RETCODE applyLocalBndchgsToCopiedMastervars(SCIP *scip, SCIP_CONS *cons, int *propcount)
#define CONSHDLR_EAGERFREQ
SCIP_CONS * GCGconsMasterbranchGetChildcons(SCIP_CONS *cons, int childnr)
SCIP_Real * pendingnewbnds
SCIP_NODE * GCGconsOrigbranchGetNode(SCIP_CONS *cons)
#define CONSHDLR_PROPFREQ
static SCIP_DECL_CONSDEACTIVE(consDeactiveMasterbranch)
int GCGconsMasterbranchGetNOrigbranchConss(SCIP_CONS *cons)
static SCIP_Bool checkAggregatedGlobalBounds(SCIP *scip, SCIP_VAR *bndvar, SCIP_BOUNDTYPE bndtype, SCIP_Real bound)
int GCGmasterVarGetNOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:886
GCG interface methods.
SCIP_Bool GCGvarIsMaster(SCIP_VAR *var)
Definition: gcgvar.c:150
static SCIP_RETCODE applyLocalBndchgsToPricedMastervars(SCIP *scip, SCIP_CONS *cons, int *propcount)
static SCIP_DECL_CONSFREE(consFreeMasterbranch)
SCIP_CONS * GCGconsMasterbranchGetOrigcons(SCIP_CONS *cons)
void GCGconsMasterbranchSetOrigcons(SCIP_CONS *cons, SCIP_CONS *origcons)
int GCGoriginalVarGetNMastervars(SCIP_VAR *var)
Definition: gcgvar.c:569
SCIP_RETCODE GCGrelaxBranchDataDelete(SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA **branchdata)
Definition: relax_gcg.c:3704
SCIP_CONS ** GCGconsMasterbranchGetOrigbranchConss(SCIP_CONS *cons)
GCG_BRANCHDATA * GCGconsMasterbranchGetBranchdata(SCIP_CONS *cons)
SCIP_RETCODE GCGconsMasterbranchAddCopiedVarBndchg(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, GCG_BOUNDTYPE boundtype, SCIP_Real newbound)
SCIP_VAR ** GCGoriginalVarGetMastervars(SCIP_VAR *var)
Definition: gcgvar.c:587
SCIP_Bool GCGisLinkingVarInBlock(SCIP_VAR *var, int block)
Definition: gcgvar.c:1064
SCIP_HASHMAP * GCGmasterVarGetOrigvalmap(SCIP_VAR *var)
Definition: gcgvar.c:979
SCIP_RETCODE GCGcreateConsMasterbranch(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_NODE *node, SCIP_CONS *parentcons, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata, SCIP_CONS **origbranchconss, int norigbranchconss, int maxorigbranchconss)
static SCIP_DECL_EVENTINITSOL(eventInitsolOrigvarbound)
static SCIP_DECL_CONSLOCK(consLockMasterbranch)
#define CONSHDLR_DELAYPROP
SCIP_RETCODE GCGconsMasterbranchAddRootCons(SCIP *scip)
#define CONSHDLR_PROPTIMING
SCIP_CONS * parentcons
SCIP_VAR ** GCGmasterVarGetOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:908
char * GCGconsMasterbranchGetName(SCIP_CONS *cons)
int GCGvarGetBlock(SCIP_VAR *var)
Definition: gcgvar.c:1033
SCIP_RETCODE GCGrelaxBranchActiveMaster(SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata)
Definition: relax_gcg.c:3586
static SCIP_RETCODE ensureLinkingvarIndxsSize(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int minsize)
SCIP_CONS * origcons
SCIP_Bool GCGvarIsPricing(SCIP_VAR *var)
Definition: gcgvar.c:134
SCIP * GCGgetPricingprob(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:3939
int GCGconsMasterbranchGetNStackelements(SCIP *scip)
SCIP_Bool GCGmasterVarIsLinking(SCIP_VAR *var)
Definition: gcgvar.c:828
SCIP_Real * GCGoriginalVarGetMastervals(SCIP_VAR *var)
Definition: gcgvar.c:605
int GCGconsMasterbranchGetNChildconss(SCIP_CONS *cons)
SCIP_VAR * GCGoriginalVarGetPricingVar(SCIP_VAR *var)
Definition: gcgvar.c:216
void GCGconsOrigbranchSetMastercons(SCIP_CONS *cons, SCIP_CONS *mastercons)
SCIP_CONS ** origbranchconss
int GCGgetNPricingprobs(SCIP *scip)
Definition: relax_gcg.c:3979
static SCIP_RETCODE ensureCollectedBndvarsSize(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int blocknr, int minsize)
#define CONSHDLR_CHECKPRIORITY
SCIP_Bool GCGvarIsOriginal(SCIP_VAR *var)
Definition: gcgvar.c:166
GCG variable pricer.
SCIP_RETCODE GCGrelaxBranchDeactiveMaster(SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata)
Definition: relax_gcg.c:3624
SCIP_NODE * GCGconsMasterbranchGetNode(SCIP_CONS *cons)
static SCIP_RETCODE applyGlobalBndchgsToPricedMastervars(SCIP *scip, int *propcount)
static SCIP_RETCODE undoLocalBndchgsToPricingprobs(SCIP *scip, SCIP_CONS *cons)
SCIP_CONS * GCGconsOrigbranchGetActiveCons(SCIP *scip)
SCIP_Bool pendingbndsactivated
static SCIP_DECL_CONSPROP(consPropMasterbranch)
SCIP * GCGgetMasterprob(SCIP *scip)
Definition: relax_gcg.c:3920
SCIP_VAR ** copiedvars
SCIP_Real ** collectedlbnds
SCIP_BRANCHRULE * GCGconsMasterbranchGetBranchrule(SCIP_CONS *cons)
constraint handler for storing the branching decisions at each node of the tree
int GCGpricingVarGetNOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:997
SCIP_Bool GCGisMaster(SCIP *scip)
Definition: misc.c:675
#define CONSHDLR_ENFOPRIORITY
static SCIP_DECL_CONSDELETE(consDeleteMasterbranch)
int * nlocalbndchgstreated
int GCGconsOrigbranchGetNChildconss(SCIP_CONS *cons)
branching rule based on vanderbeck's generic branching scheme
SCIP_Bool GCGcurrentNodeIsGeneric(SCIP *scip)
constraint handler for storing the branching decisions at each node of the tree
SCIP_RETCODE SCIPincludeConshdlrMasterbranch(SCIP *scip)
SCIP_CONS * probingtmpcons
SCIP_CONS ** childconss
SCIP_Bool GCGisOriginal(SCIP *scip)
Definition: misc.c:665
SCIP_CONS * GCGconsOrigbranchGetParentcons(SCIP_CONS *cons)
SCIP_RETCODE GCGrelaxBranchPropMaster(SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata, SCIP_RESULT *result)
Definition: relax_gcg.c:3662
int GCGgetNIdenticalBlocks(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:4053
SCIP_Real * localnewbnds
static SCIP_DECL_CONSENFOLP(consEnfolpMasterbranch)
static SCIP_RETCODE applyLocalBndchgsToPricingprobs(SCIP *scip, SCIP_CONS *cons)
static SCIP_DECL_CONSINIT(consInitMasterbranch)
SCIP_RETCODE GCGconsMasterbranchReleaseOrigbranchConss(SCIP *masterscip, SCIP *origscip, SCIP_CONS *cons)
#define CONSHDLR_NAME
SCIP * GCGmasterGetOrigprob(SCIP *scip)
static SCIP_DECL_CONSACTIVE(consActiveMasterbranch)
void GCGconsOrigbranchSetBranchdata(SCIP_CONS *cons, GCG_BRANCHDATA *branchdata)
#define EVENTHDLR_DESC
GCG_BOUNDTYPE * copiedvarbndtypes
SCIP_CONS * GCGconsMasterbranchGetParentcons(SCIP_CONS *cons)
SCIP_Bool GCGrelaxIsInitialized(SCIP *scip)
Definition: relax_gcg.c:4958
SCIP_Real * pendingoldbnds
SCIP_BOUNDTYPE * localbndtypes
GCG relaxator.
static SCIP_DECL_CONSCHECK(consCheckMasterbranch)
int GCGmasterGetNPricedvars(SCIP *scip)
SCIP_CONS * GCGconsMasterbranchGetActiveCons(SCIP *scip)
SCIP_VAR ** GCGpricingVarGetOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:1015
static SCIP_RETCODE tightenPricingVarBound(SCIP *scip, SCIP_VAR *pricingvar, SCIP_CONSDATA *consdata, int i, int blocknr)
static SCIP_RETCODE resetPricingVarBound(SCIP *scip, SCIP_VAR *pricingvar, SCIP_CONSDATA *consdata, int i, int blocknr)
SCIP_Real * localoldbnds
#define CONSHDLR_DESC
static SCIP_DECL_CONSINITSOL(consInitsolMasterbranch)
SCIP_BOUNDTYPE * pendingbndtypes
SCIP_Bool needprop
SCIP_Real * copiedvarbnds
GCG_BRANCHDATA * branchdata
SCIP_BRANCHRULE * branchrule
static SCIP_RETCODE addPendingBndChg(SCIP *scip, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_Real oldbound, SCIP_Real newbound)
enum GCG_BoundType GCG_BOUNDTYPE
SCIP_NODE * node
SCIP_Bool GCGoriginalVarIsLinking(SCIP_VAR *var)
Definition: gcgvar.c:182
void GCGconsMasterbranchGetStack(SCIP *scip, SCIP_CONS ***stack, int *nstackelements)
static SCIP_DECL_CONSENFOPS(consEnfopsMasterbranch)
SCIP_VAR *** collectedbndvars
SCIP_VAR ** localbndvars
#define CONSHDLR_NEEDSCONS
void GCGconsMasterbranchCheckConsistency(SCIP *scip)
static SCIP_DECL_CONSEXIT(consExitMasterbranch)
SCIP_Bool GCGisPricingprobRelevant(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:4000
#define EVENTHDLR_NAME
SCIP_VAR ** GCGlinkingVarGetPricingVars(SCIP_VAR *var)
Definition: gcgvar.c:409
static SCIP_DECL_EVENTEXEC(eventExecOrigvarbound)
SCIP_Real ** collectedubnds
SCIP_CONS * GCGconsOrigbranchGetMastercons(SCIP_CONS *cons)
static SCIP_Bool checkAggregatedLocalBounds(SCIP *scip, SCIP_VAR **bndvars, SCIP_Real *bounds, int nbndvars, SCIP_VAR *bndvar, SCIP_BOUNDTYPE bndtype, SCIP_VAR *pricingvar)
static SCIP_RETCODE initializeConsdata(SCIP *scip, SCIP_CONS *cons)
static SCIP_RETCODE applyGlobalBndchgsToPricingprobs(SCIP *scip)
SCIP_VAR ** GCGmasterGetPricedvars(SCIP *scip)