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