branch_generic.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 
36 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
37 
38 /*#define SCIP_DEBUG*/
39 
40 #include "branch_generic.h"
41 #include "relax_gcg.h"
42 #include "cons_masterbranch.h"
43 #include "cons_origbranch.h"
44 #include "pricer_gcg.h"
45 #include "scip/cons_linear.h"
46 #include "type_branchgcg.h"
47 #include "gcg.h"
48 #include "cons_integralorig.h"
49 #include "gcgsort.h"
50 
51 #include "scip/nodesel_bfs.h"
52 #include "scip/nodesel_dfs.h"
53 #include "scip/nodesel_estimate.h"
54 #include "scip/nodesel_hybridestim.h"
55 #include "scip/nodesel_restartdfs.h"
56 #include "scip/branch_allfullstrong.h"
57 #include "scip/branch_fullstrong.h"
58 #include "scip/branch_inference.h"
59 #include "scip/branch_mostinf.h"
60 #include "scip/branch_leastinf.h"
61 #include "scip/branch_pscost.h"
62 #include "scip/branch_random.h"
63 #include "scip/branch_relpscost.h"
64 
65 #include <assert.h>
66 #include <string.h>
67 
68 
69 #define BRANCHRULE_NAME "generic"
70 #define BRANCHRULE_DESC "generic branching rule by Vanderbeck"
71 #define BRANCHRULE_PRIORITY -100
72 #define BRANCHRULE_MAXDEPTH -1
73 #define BRANCHRULE_MAXBOUNDDIST 1.0
74 
75 
76 #define EVENTHDLR_NAME "genericbranchvaradd"
77 #define EVENTHDLR_DESC "event handler for adding a new generated mastervar into the right branching constraints by using Vanderbecks generic branching scheme"
78 
81 {
82  GCG_COMPSEQUENCE** C; /* !!! sort of each C[i] = S is important !!! */
84  int Csize;
85  SCIP_Real lhs;
86  SCIP_CONS* mastercons;
88  int consSsize;
90  int nvars;
91 };
92 
94 struct GCG_Record
95 {
97  int recordsize;
99 };
100 typedef struct GCG_Record GCG_RECORD;
101 
102 /*
103  * Callback methods
104  */
105 
106 /* define not used callback as NULL*/
107 #define branchFreeGeneric NULL
108 #define branchExitGeneric NULL
109 #define branchInitsolGeneric NULL
110 #define branchExitsolGeneric NULL
111 
112 
115 static
117  SCIP_VAR* mastervar,
118  SCIP_VAR* origvar
119  )
120 {
121  int i;
122  SCIP_VAR** origvars;
123  SCIP_Real* origvals;
124  int norigvars;
125 
126  assert(mastervar != NULL);
127  assert(origvar != NULL);
128 
129  origvars = GCGmasterVarGetOrigvars(mastervar);
130  norigvars = GCGmasterVarGetNOrigvars(mastervar);
131  origvals = GCGmasterVarGetOrigvals(mastervar);
132 
133  for( i = 0; i < norigvars; ++i )
134  {
135  if( origvars[i] == origvar )
136  {
137  return origvals[i];
138  }
139  }
140 
141  return 0.0;
142 }
143 
145 static
146 SCIP_RETCODE addVarToMasterbranch(
147  SCIP* scip,
148  SCIP_VAR* mastervar,
149  GCG_BRANCHDATA* branchdata,
150  SCIP_Bool* added
151 )
152 {
153  int p;
154 
155  SCIP_Bool varinS = TRUE;
156 
157  assert(scip != NULL);
158  assert(mastervar != NULL);
159  assert(branchdata != NULL);
160  assert(added != NULL);
161 
162  *added = FALSE;
163 
164  if( ( GCGvarGetBlock(mastervar) == -1 && GCGbranchGenericBranchdataGetConsblocknr(branchdata) != -1 ) || !GCGisMasterVarInBlock(mastervar, GCGbranchGenericBranchdataGetConsblocknr(branchdata)) )
165  return SCIP_OKAY;
166 
167  SCIPdebugMessage("consSsize = %d\n", GCGbranchGenericBranchdataGetConsSsize(branchdata));
168 
169  for( p = 0; p < GCGbranchGenericBranchdataGetConsSsize(branchdata); ++p )
170  {
171  SCIP_Real generatorentry;
172 
173  generatorentry = getGeneratorEntry(mastervar, GCGbranchGenericBranchdataGetConsS(branchdata)[p].component);
174 
175  if( GCGbranchGenericBranchdataGetConsS(branchdata)[p].sense == GCG_COMPSENSE_GE )
176  {
177  if( SCIPisLT(scip, generatorentry, GCGbranchGenericBranchdataGetConsS(branchdata)[p].bound) )
178  {
179  varinS = FALSE;
180  break;
181  }
182  }
183  else
184  {
185  if( SCIPisGE(scip, generatorentry, GCGbranchGenericBranchdataGetConsS(branchdata)[p].bound) )
186  {
187  varinS = FALSE;
188  break;
189  }
190  }
191  }
192 
193  if( varinS )
194  {
195  SCIPdebugMessage("mastervar is added\n");
196  SCIP_CALL( SCIPaddCoefLinear(scip, GCGbranchGenericBranchdataGetMastercons(branchdata), mastervar, 1.0) );
197  *added = TRUE;
198  }
199 
200  return SCIP_OKAY;
201 }
202 
204 static
206  SCIP* scip,
207  SCIP_NODE* node,
208  GCG_BRANCHDATA* branchdata
209 )
210 {
211  char name[SCIP_MAXSTRLEN];
212 
213  assert(scip != NULL);
214  assert(node != NULL);
215  assert(branchdata->consblocknr == -3);
216  assert(branchdata->consSsize == 1);
217 
218  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "directchild(%d, %g) sense = %d", branchdata->consSsize, branchdata->consS[0].bound, branchdata->consS[0].sense);
219 
220  /* create constraint for child */
221  if( branchdata->consS[0].sense == GCG_COMPSENSE_GE )
222  {
223  SCIP_CALL( SCIPcreateConsLinear(scip, &(branchdata->mastercons), name, 0, NULL, NULL, branchdata->consS[0].bound, SCIPinfinity(scip), TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE) );
224  } else
225  {
226  SCIP_CALL( SCIPcreateConsLinear(scip, &(branchdata->mastercons), name, 0, NULL, NULL, -SCIPinfinity(scip), branchdata->consS[0].bound-1, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE) );
227  }
228  assert(GCGvarIsMaster(branchdata->consS[0].component));
229  SCIP_CALL( SCIPaddCoefLinear(scip, branchdata->mastercons, branchdata->consS[0].component, 1.0) );
230 
231  /* add constraint to the master problem that enforces the branching decision */
232  SCIP_CALL( SCIPaddConsNode(scip, node, branchdata->mastercons, NULL) );
233 
234  return SCIP_OKAY;
235 }
236 
238 static
239 SCIP_RETCODE createBranchingCons(
240  SCIP* scip,
241  SCIP_NODE* node,
242  GCG_BRANCHDATA* branchdata
243 )
244 {
245  char name[SCIP_MAXSTRLEN];
246 
247  assert(scip != NULL);
248  assert(node != NULL);
249  assert(branchdata != NULL);
250 
251  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "child(%d, %g)", branchdata->consSsize, branchdata->lhs);
252 
253  assert(branchdata->mastercons == NULL);
254 
255  /* create constraint for child */
256  SCIP_CALL( SCIPcreateConsLinear(scip, &(branchdata->mastercons), name, 0, NULL, NULL,
257  branchdata->lhs, SCIPinfinity(scip), TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE) );
258 
259  SCIP_CALL( SCIPaddConsNode(scip, node, branchdata->mastercons, NULL) );
260 
261  return SCIP_OKAY;
262 }
264 static
265 SCIP_DECL_EVENTINITSOL(eventInitsolGenericbranchvaradd)
266 { /*lint --e{715}*/
267  assert(scip != NULL);
268  assert(eventhdlr != NULL);
269  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
270 
271  /* notify SCIP that your event handler wants to react on the event type */
272  SCIP_CALL( SCIPcatchEvent( scip, SCIP_EVENTTYPE_VARADDED, eventhdlr, NULL, NULL) );
273 
274  return SCIP_OKAY;
275 }
276 
278 static
279 SCIP_DECL_EVENTEXITSOL(eventExitsolGenericbranchvaradd)
280 { /*lint --e{715}*/
281  assert(scip != NULL);
282  assert(eventhdlr != NULL);
283  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
284 
285  /* notify SCIP that your event handler wants to drop the event type */
286  SCIP_CALL( SCIPdropEvent( scip, SCIP_EVENTTYPE_VARADDED, eventhdlr, NULL, -1) );
287 
288  return SCIP_OKAY;
289 }
290 
292 static
293 SCIP_DECL_EVENTEXEC(eventExecGenericbranchvaradd)
294 { /*lint --e{715}*/
295  SCIP* origscip;
296  SCIP_CONS* masterbranchcons;
297  SCIP_CONS* parentcons;
298  SCIP_VAR* mastervar;
299  SCIP_VAR** allorigvars;
300  SCIP_VAR** mastervars;
301  GCG_BRANCHDATA* branchdata;
302  int allnorigvars;
303  int nmastervars;
304 
305  assert(eventhdlr != NULL);
306  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
307  assert(event != NULL);
308  assert(scip != NULL);
309  assert(SCIPeventGetType(event) == SCIP_EVENTTYPE_VARADDED);
310 
311  mastervar = SCIPeventGetVar(event);
312  if( !GCGvarIsMaster(mastervar) )
313  return SCIP_OKAY;
314 
315  origscip = GCGmasterGetOrigprob(scip);
316  assert(origscip != NULL);
317 
318  /* SCIPdebugMessage("exec method of event_genericbranchvaradd\n"); */
319 
320  masterbranchcons = GCGconsMasterbranchGetActiveCons(scip);
321  assert(masterbranchcons != NULL);
322 
323  /* if branch rule is not generic, abort */
325  return SCIP_OKAY;
326 
327  SCIP_CALL( SCIPgetVarsData(origscip, &allorigvars, &allnorigvars, NULL, NULL, NULL, NULL) );
328  SCIP_CALL( SCIPgetVarsData(scip, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
329 
330  parentcons = masterbranchcons;
331  branchdata = GCGconsMasterbranchGetBranchdata(parentcons);
332 
333 
334  if( GCGvarIsMaster(mastervar) && GCGconsMasterbranchGetBranchrule(parentcons) != NULL )
335  {
336  SCIP_Bool added = FALSE;
337  SCIPdebugMessage("Mastervar <%s>\n", SCIPvarGetName(mastervar));
338  while( parentcons != NULL && branchdata != NULL
339  && GCGbranchGenericBranchdataGetConsS(branchdata) != NULL && GCGbranchGenericBranchdataGetConsSsize(branchdata) > 0 )
340  {
341  if( GCGconsMasterbranchGetBranchrule(parentcons) == NULL || strcmp(SCIPbranchruleGetName(GCGconsMasterbranchGetBranchrule(parentcons)), "generic") != 0 )
342  break;
343 
344  assert(branchdata != NULL);
345 
346 
347  if( (GCGbranchGenericBranchdataGetConsblocknr(branchdata) != GCGvarGetBlock(mastervar) && GCGvarGetBlock(mastervar) != -1 )
348  || (GCGvarGetBlock(mastervar) == -1 && !GCGmasterVarIsLinking(mastervar)) )
349  {
350  parentcons = GCGconsMasterbranchGetParentcons(parentcons);
351 
352  if( parentcons != NULL )
353  branchdata = GCGconsMasterbranchGetBranchdata(parentcons);
354 
355  continue;
356  }
357 
358  SCIP_CALL( addVarToMasterbranch(scip, mastervar, branchdata, &added) );
359 
360  parentcons = GCGconsMasterbranchGetParentcons(parentcons);
361  branchdata = GCGconsMasterbranchGetBranchdata(parentcons);
362  }
363  }
364 
365  return SCIP_OKAY;
366 }
367 
368 
369 /*
370  * branching specific interface methods
371  */
372 
374 static
375 SCIP_RETCODE InitIndexSet(
376  SCIP* scip,
377  SCIP_VAR** F,
378  int Fsize,
379  SCIP_VAR*** IndexSet,
380  int* IndexSetSize
381  )
382 {
383  int i;
384 
385  assert( scip != NULL);
386  assert( F != NULL);
387  assert( Fsize > 0);
388  assert( IndexSet != NULL);
389  assert( IndexSetSize != NULL);
390 
391  *IndexSet = NULL;
392  *IndexSetSize = 0;
393 
394 
395  for( i = 0; i < Fsize; ++i )
396  {
397  int j;
398  SCIP_VAR** origvars = GCGmasterVarGetOrigvars(F[i]);
399  int norigvars = GCGmasterVarGetNOrigvars(F[i]);
400 
401  if( *IndexSetSize == 0 && norigvars > 0 )
402  {
403  /* TODO: allocate memory for norigvars although there might be slots for continuous variables which are not needed? */
404  SCIP_CALL( SCIPallocMemoryArray(scip, IndexSet, 1) );
405  for( j = 0; j < norigvars; ++j )
406  {
407  if( SCIPvarGetType(origvars[j]) > SCIP_VARTYPE_INTEGER )
408  continue;
409 
410  if( *IndexSetSize > 0 )
411  SCIP_CALL( SCIPreallocMemoryArray(scip, IndexSet, *IndexSetSize + 1) );
412 
413  (*IndexSet)[*IndexSetSize] = origvars[j];
414  ++(*IndexSetSize);
415  }
416  }
417  else
418  {
419  for( j = 0; j < norigvars; ++j )
420  {
421  int k;
422  int oldsize = *IndexSetSize;
423 
424  if( SCIPvarGetType(origvars[j]) > SCIP_VARTYPE_INTEGER )
425  continue;
426 
427  for( k = 0; k < oldsize; ++k )
428  {
429  /* if variable already in union */
430  if( (*IndexSet)[k] == origvars[j] )
431  {
432  break;
433  }
434  if( k == oldsize-1 )
435  {
436  /* add variable to the end */
437  ++(*IndexSetSize);
438  SCIP_CALL( SCIPreallocMemoryArray(scip, IndexSet, *IndexSetSize) );
439  (*IndexSet)[*IndexSetSize-1] = origvars[j];
440  }
441  }
442  }
443  }
444  }
445 
446  return SCIP_OKAY;
447 }
448 
456 static
457 SCIP_Real GetMedian(
458  SCIP* scip,
459  SCIP_Real* array,
460  int arraysize,
461  SCIP_Real min
462  )
463 {
464  SCIP_Real Median;
465  SCIP_Real swap;
466  int l;
467  int r;
468  int i;
469  int MedianIndex;
470  SCIP_Real arithmMiddle;
471 
472  assert(scip != NULL);
473  assert(array != NULL);
474  assert(arraysize > 0);
475 
476  r = arraysize -1;
477  l = 0;
478  arithmMiddle = 0;
479 
480  if( arraysize & 1 )
481  MedianIndex = arraysize/2;
482  else
483  MedianIndex = arraysize/2 -1;
484 
485  while( l < r-1 )
486  {
487  int j = r;
488  Median = array[MedianIndex];
489  i = l;
490 
491  do
492  {
493  while( SCIPisLT(scip, array[i], Median) )
494  ++i;
495  while( SCIPisGT(scip, array[j], Median) )
496  --j;
497  if( i <=j )
498  {
499  swap = array[i];
500  array[i] = array[j];
501  array[j] = swap;
502  ++i;
503  --j;
504  }
505  } while( i <=j );
506  if( j < MedianIndex )
507  l = i;
508  if( i > MedianIndex )
509  r = j;
510  }
511  Median = array[MedianIndex];
512 
513  if( SCIPisEQ(scip, Median, min) )
514  {
515  for( i=0; i<arraysize; ++i )
516  arithmMiddle += 1.0*array[i]/arraysize;
517 
518  Median = SCIPceil(scip, arithmMiddle);
519  }
520 
521  return Median;
522 }
523 
525 static
527 {
528  SCIP* origprob = (SCIP *) userdata;
529  GCG_STRIP* strip1;
530  GCG_STRIP* strip2;
531  SCIP_VAR* mastervar1;
532  SCIP_VAR* mastervar2;
533  SCIP_VAR** origvars;
534  int norigvars;
535  int i;
536 
537  strip1 = (GCG_STRIP*) elem1;
538  strip2 = (GCG_STRIP*) elem2;
539 
540  mastervar1 = strip1->mastervar;
541  mastervar2 = strip2->mastervar;
542 
543  assert(mastervar1 != NULL);
544  assert(mastervar2 != NULL);
545 
546  if( GCGvarGetBlock(mastervar1) == -1 )
547  {
548  SCIPdebugMessage("linkingvar\n");
549  assert(GCGmasterVarIsLinking(mastervar1));
550  }
551  if( GCGvarGetBlock(mastervar2) == -1 )
552  {
553  SCIPdebugMessage("linkingvar\n");
554  assert(GCGmasterVarIsLinking(mastervar2));
555  }
556 
557  origvars = SCIPgetVars(origprob);
558  norigvars = SCIPgetNVars(origprob);
559 
560  for( i = 0; i < norigvars; ++i )
561  {
562  if( SCIPvarGetType(origvars[i]) > SCIP_VARTYPE_INTEGER )
563  continue;
564 
565  if( SCIPisFeasGT(origprob, getGeneratorEntry(mastervar1, origvars[i]), getGeneratorEntry(mastervar2, origvars[i])) )
566  return -1;
567 
568  if( SCIPisFeasLT(origprob, getGeneratorEntry(mastervar1, origvars[i]), getGeneratorEntry(mastervar2, origvars[i])) )
569  return 1;
570  }
571 
572  return 0;
573 }
574 
578 static
579 SCIP_RETCODE LexicographicSort(
580  SCIP* scip,
581  GCG_STRIP** array,
582  int arraysize
583  )
584 {
585 
586  assert(array != NULL);
587  assert(arraysize > 0);
588 
589  SCIPdebugMessage("Lexicographic sorting\n");
590 
591  GCGsortPtr((void**)array, ptrcomp, scip, arraysize );
592 
593  return SCIP_OKAY;
594 }
595 
596 
598 static
600  SCIP* scip,
601  SCIP_VAR* mastervar1,
602  SCIP_VAR* mastervar2,
603  GCG_COMPSEQUENCE** C,
604  int NBoundsequences,
605  int* sequencesizes,
606  int p
607  )
608 {
609  SCIP_Real ivalue;
610  int j;
611  int k;
612  int Nupper;
613  int Nlower;
614  int returnvalue;
615  GCG_COMPSEQUENCE** CopyC;
616  SCIP_VAR* origvar;
617  int* newsequencesizes;
618  GCG_STRIP* strip1;
619  GCG_STRIP* strip2;
620 
621  k = 0;
622  Nupper = 0;
623  Nlower = 0;
624  newsequencesizes = NULL;
625  strip1 = NULL;
626  strip2 = NULL;
627 
628  /* lexicographic Order? */
629  if( C == NULL || NBoundsequences <= 1 )
630  {
631  SCIP_CALL_ABORT( SCIPallocBuffer(scip, &strip1) );
632  SCIP_CALL_ABORT( SCIPallocBuffer(scip, &strip2) );
633 
634  strip1->scip = scip;
635  strip2->scip = scip;
636  strip1->C = NULL;
637  strip2->C = NULL;
638  strip1->Csize = 0;
639  strip2->Csize = 0;
640  strip1->sequencesizes = NULL;
641  strip2->sequencesizes = NULL;
642  strip1->mastervar = mastervar1;
643  strip2->mastervar = mastervar2;
644 
645  returnvalue = (*ptrcomp)(scip, strip1, strip2);
646 
647  SCIPfreeBuffer(scip, &strip1);
648  SCIPfreeBuffer(scip, &strip2);
649 
650  return returnvalue;
651  }
652 
653  assert(C != NULL);
654  assert(NBoundsequences > 0);
655 
656  /* find i which is in all S in C on position p */
657  while( sequencesizes[k] < p )
658  {
659  ++k;
660  assert(k < NBoundsequences);
661  }
662  origvar = C[k][p-1].component;
663  assert(origvar != NULL);
664  assert(SCIPvarGetType(origvar) <= SCIP_VARTYPE_INTEGER);
665  ivalue = C[k][p-1].bound;
666 
667  /* calculate subset of C */
668  for( j=0; j< NBoundsequences; ++j )
669  {
670  if( sequencesizes[j] >= p )
671  {
672  assert(C[j][p-1].component == origvar);
673  if( C[j][p-1].sense == GCG_COMPSENSE_GE )
674  ++Nupper;
675  else
676  ++Nlower;
677  }
678  }
679 
680  if( SCIPisGE(scip, getGeneratorEntry(mastervar1, origvar), ivalue) && SCIPisGE(scip, getGeneratorEntry(mastervar2, origvar), ivalue) )
681  {
682  k = 0;
683  SCIP_CALL_ABORT( SCIPallocMemoryArray(scip, &CopyC, Nupper) );
684  SCIP_CALL_ABORT( SCIPallocMemoryArray(scip, &newsequencesizes, Nupper) );
685  for( j = 0; j < NBoundsequences; ++j )
686  {
687  if( sequencesizes[j] >= p )
688  assert(C[j][p-1].component == origvar);
689 
690  if( sequencesizes[j] >= p && C[j][p-1].sense == GCG_COMPSENSE_GE )
691  {
692  int l;
693  CopyC[k] = NULL;
694  SCIP_CALL_ABORT( SCIPallocMemoryArray(scip, &(CopyC[k]), sequencesizes[j]) ); /*lint !e866*/
695  for( l = 0; l < sequencesizes[j]; ++l )
696  {
697  CopyC[k][l] = C[j][l];
698  }
699  newsequencesizes[k] = sequencesizes[j];
700  ++k;
701  }
702  }
703 
704  if( k != Nupper )
705  {
706  SCIPdebugMessage("k = %d, Nupper+1 =%d\n", k, Nupper+1);
707  }
708 
709  if( Nupper != 0 )
710  assert( k == Nupper );
711 
712  returnvalue = ILOcomp(scip, mastervar1, mastervar2, CopyC, Nupper, newsequencesizes, p+1);
713 
714  for( j=0; j< Nupper; ++j )
715  {
716  SCIPfreeMemoryArray(scip, &(CopyC[j]) );
717  }
718  SCIPfreeMemoryArray(scip, &newsequencesizes);
719  SCIPfreeMemoryArray(scip, &CopyC);
720 
721  return returnvalue;
722  }
723 
724 
725  if( SCIPisLT(scip, getGeneratorEntry(mastervar1, origvar), ivalue) && SCIPisLT(scip, getGeneratorEntry(mastervar2, origvar), ivalue) )
726  {
727  SCIP_CALL_ABORT( SCIPallocMemoryArray(scip, &CopyC, Nlower) );
728  SCIP_CALL_ABORT( SCIPallocMemoryArray(scip, &newsequencesizes, Nlower) );
729 
730  k = 0;
731  for( j = 0; j < NBoundsequences; ++j )
732  {
733  if( sequencesizes[j] >= p )
734  assert(C[j][p-1].component == origvar);
735 
736  if( sequencesizes[j] >= p && C[j][p-1].sense != GCG_COMPSENSE_GE )
737  {
738  int l;
739  CopyC[k] = NULL;
740  SCIP_CALL_ABORT( SCIPallocMemoryArray(scip, &(CopyC[k]), sequencesizes[j]) ); /*lint !e866*/
741  for( l = 0; l < sequencesizes[j]; ++l )
742  {
743  CopyC[k][l] = C[j][l];
744  }
745  newsequencesizes[k] = sequencesizes[j];
746  ++k;
747  }
748  }
749 
750  if( k != Nlower )
751  {
752  SCIPdebugMessage("k = %d, Nlower+1 =%d\n", k, Nlower+1);
753  }
754 
755  if( Nlower != 0 )
756  assert( k == Nlower);
757 
758  returnvalue = ILOcomp( scip, mastervar1, mastervar2, CopyC, Nlower, newsequencesizes, p+1);
759 
760  for( j = 0; j < Nlower; ++j )
761  {
762 
763  SCIPfreeMemoryArray(scip, &(CopyC[j]) );
764  }
765  SCIPfreeMemoryArray(scip, &newsequencesizes);
766  SCIPfreeMemoryArray(scip, &CopyC);
767 
768  return returnvalue;
769  }
770  if( SCIPisGT(scip, getGeneratorEntry(mastervar1, origvar), getGeneratorEntry(mastervar2, origvar)) )
771  return 1;
772  else
773  return -1;
774 }
775 
777 static
779 {
780  GCG_STRIP* strip1;
781  GCG_STRIP* strip2;
782  int returnvalue;
783 
784  strip1 = (GCG_STRIP*) elem1;
785  strip2 = (GCG_STRIP*) elem2;
786 
787  returnvalue = ILOcomp(strip1->scip, strip1->mastervar, strip2->mastervar, strip1->C, strip1->Csize, strip1->sequencesizes, 1);
788 
789  return returnvalue;
790 }
791 
793 static
795  SCIP* scip,
796  GCG_STRIP** array,
797  int arraysize,
798  GCG_COMPSEQUENCE** C,
799  int NBoundsequences,
800  int* sequencesizes
801  )
802 {
803  int i;
804 
805  SCIPdebugMessage("Induced Lexicographic sorting\n");
806 
807  if( NBoundsequences == 0 )
808  return LexicographicSort( scip, array, arraysize );
809  assert( C!= NULL );
810 
811  assert(arraysize > 0);
812  if( arraysize <= 1 )
813  return SCIP_OKAY;
814 
815  assert(array != NULL);
816  for( i = 0; i < arraysize; ++i )
817  {
818  array[i]->scip = scip;
819  array[i]->Csize = NBoundsequences;
820  array[i]->sequencesizes = sequencesizes;
821  array[i]->C = C;
822  }
823 
824  SCIPsortPtr((void**)array, ptrilocomp, arraysize);
825 
826  return SCIP_OKAY;
827 }
828 
830 static
831 SCIP_RETCODE partition(
832  SCIP* scip,
833  SCIP_VAR** J,
834  int* Jsize,
835  SCIP_Longint* priority,
836  SCIP_VAR** F,
837  int Fsize,
838  SCIP_VAR** origvar,
839  SCIP_Real* median
840  )
841 {
842  int j;
843  int l;
844  SCIP_Real min;
845  SCIP_Real* compvalues;
846 
847  do
848  {
849  SCIP_Longint maxPriority = SCIP_LONGINT_MIN;
850  min = SCIPinfinity(scip);
851 
852  /* max-min priority */
853  for ( j = 0; j < *Jsize; ++j )
854  {
855  assert(SCIPvarGetType(J[j]) <= SCIP_VARTYPE_INTEGER);
856 
857  if ( priority[j] > maxPriority )
858  {
859  maxPriority = priority[j];
860  *origvar = J[j];
861  }
862  }
863  SCIP_CALL( SCIPallocBufferArray(scip, &compvalues, Fsize) );
864  for ( l = 0; l < Fsize; ++l )
865  {
866  compvalues[l] = getGeneratorEntry(F[l], *origvar);
867  if ( SCIPisLT(scip, compvalues[l], min) )
868  min = compvalues[l];
869  }
870  *median = GetMedian(scip, compvalues, Fsize, min);
871  SCIPfreeBufferArray(scip, &compvalues);
872 
873  assert(!SCIPisInfinity(scip, min));
874 
875  if ( !SCIPisEQ(scip, *median, 0.0) )
876  {
877  SCIPdebugMessage("median = %g\n", *median);
878  SCIPdebugMessage("min = %g\n", min);
879  SCIPdebugMessage("Jsize = %d\n", *Jsize);
880  }
881 
882  if ( SCIPisEQ(scip, *median, min) )
883  {
884  /* here with max-min priority */
885  for ( j = 0; j < *Jsize; ++j )
886  {
887  if ( *origvar == J[j] )
888  {
889  assert(priority[j] == 0);
890  J[j] = J[*Jsize - 1];
891  priority[j] = priority[*Jsize - 1];
892  break;
893  }
894  }
895  if( j < *Jsize )
896  *Jsize = *Jsize-1;
897  }
898  assert(*Jsize >= 0);
899 
900  }while ( SCIPisEQ(scip, *median, min) && *Jsize > 0);
901 
902  return SCIP_OKAY;
903 }
904 
906 static
907 SCIP_RETCODE addToRecord(
908  SCIP* scip,
909  GCG_RECORD* record,
910  GCG_COMPSEQUENCE* S,
911  int Ssize
912 )
913 {
914  int i;
915 
916  SCIPdebugMessage("recordsize=%d, Ssize=%d\n", record->recordsize, Ssize);
917 
918  SCIP_CALL( SCIPreallocMemoryArray(scip, &(record->record), (size_t)record->recordsize+1) );
919  SCIP_CALL( SCIPreallocMemoryArray(scip, &(record->sequencesizes), (size_t)record->recordsize+1) );
920 
921  SCIP_CALL( SCIPallocMemoryArray(scip, &(record->record[record->recordsize]), Ssize) ); /*lint !e866*/
922  for( i=0; i<Ssize;++i )
923  {
924  record->record[record->recordsize][i].component = S[i].component;
925  record->record[record->recordsize][i].sense = S[i].sense;
926  record->record[record->recordsize][i].bound = S[i].bound;
927  }
928 
929  record->sequencesizes[record->recordsize] = Ssize; /* +1 ? */
930 
931  record->recordsize++;
932 
933  return SCIP_OKAY;
934 }
935 
936 
938 static
939 SCIP_RETCODE Separate(
940  SCIP* scip,
941  SCIP_VAR** F,
942  int Fsize,
943  SCIP_VAR** IndexSet,
944  int IndexSetSize,
945  GCG_COMPSEQUENCE* S,
946  int Ssize,
948  )
949 {
950  int j;
951  int k;
952  int l;
953  int Jsize;
954  SCIP_VAR** J;
955  SCIP_Real median;
956  int Fupper;
957  int Flower;
958  SCIP_Longint* priority;
959  SCIP_VAR* origvar;
960  SCIP_VAR** copyF;
961  GCG_COMPSEQUENCE* upperLowerS;
962  GCG_COMPSEQUENCE* upperS;
963  SCIP_Real* alpha;
964  SCIP_Real* compvalues;
965  SCIP_Real muF;
966  SCIP_Bool found;
967 
968  assert(scip != NULL);
969  assert((Fsize == 0) == (F == NULL));
970  assert((IndexSetSize == 0) == (IndexSet == NULL));
971 
972  Jsize = 0;
973  Fupper = 0;
974  Flower = 0;
975  found = FALSE;
976  priority = NULL;
977  compvalues = NULL;
978  J = NULL;
979  origvar = NULL;
980  copyF = NULL;
981  upperLowerS = NULL;
982  upperS = NULL;
983  alpha = NULL;
984 
985  SCIPdebugMessage("Separate with ");
986 
987  /* if there are no fractional columns or potential columns, return */
988  if( Fsize == 0 || IndexSetSize == 0 )
989  {
990  SCIPdebugPrintf("nothing, no fractional columns\n");
991  return SCIP_OKAY;
992  }
993 
994  assert( F != NULL );
995  assert( IndexSet != NULL );
996 
997  muF = 0.0;
998  for( j = 0; j < Fsize; ++j )
999  muF += SCIPgetSolVal(GCGgetMasterprob(scip), NULL, F[j]);
1000 
1001  SCIPdebugPrintf("Fsize = %d; Ssize = %d, IndexSetSize = %d, nuF=%.6g \n", Fsize, Ssize, IndexSetSize, muF);
1002 
1003  /* detect fractional alpha_i */
1004  SCIP_CALL( SCIPallocBufferArray(scip, &alpha, IndexSetSize) );
1005 
1006  for( k = 0; k < IndexSetSize; ++k )
1007  {
1008  GCG_COMPSEQUENCE* copyS;
1009  SCIP_Real min;
1010  min = SCIPinfinity(scip);
1011 
1012  origvar = IndexSet[k];
1013  copyS = NULL;
1014  alpha[k] = 0.0;
1015 
1016  if( SCIPvarGetType(origvar) > SCIP_VARTYPE_INTEGER )
1017  continue;
1018 
1019  SCIP_CALL( SCIPallocBufferArray(scip, &compvalues, Fsize) );
1020  for( l=0; l<Fsize; ++l )
1021  {
1022  compvalues[l] = getGeneratorEntry(F[l], origvar);
1023  if( SCIPisLT(scip, compvalues[l], min) )
1024  min = compvalues[l];
1025  }
1026 
1027  median = GetMedian(scip, compvalues, Fsize, min);
1028  SCIPfreeBufferArray(scip, &compvalues);
1029  compvalues = NULL;
1030 
1031  for( j = 0; j < Fsize; ++j )
1032  {
1033  SCIP_Real generatorentry;
1034 
1035  generatorentry = getGeneratorEntry(F[j], origvar);
1036 
1037  if( SCIPisGE(scip, generatorentry, median) )
1038  {
1039  alpha[k] += SCIPgetSolVal(GCGgetMasterprob(scip), NULL, F[j]);
1040  }
1041  }
1042 
1043  if( SCIPisGT(scip, alpha[k], 0.0) && SCIPisLT(scip, alpha[k], muF) )
1044  {
1045  ++Jsize;
1046  }
1047 
1048  if( !SCIPisFeasIntegral(scip, alpha[k]) )
1049  {
1050  SCIPdebugMessage("alpha[%d] = %g\n", k, alpha[k]);
1051  found = TRUE;
1052 
1053  /* ********************************** *
1054  * add the current pair to record *
1055  * ********************************** */
1056 
1057  /* copy S */
1058  SCIP_CALL( SCIPallocMemoryArray(scip, &copyS, (size_t)Ssize+1) );
1059 
1060  for( l = 0; l < Ssize; ++l )
1061  {
1062  copyS[l] = S[l];
1063  }
1064 
1065  /* create temporary array to compute median */
1066  SCIP_CALL( SCIPallocBufferArray(scip, &compvalues, Fsize) );
1067 
1068  for( l = 0; l < Fsize; ++l )
1069  {
1070  compvalues[l] = getGeneratorEntry(F[l], origvar);
1071 
1072  if( SCIPisLT(scip, compvalues[l], min) )
1073  min = compvalues[l];
1074  }
1075 
1076  assert( SCIPisEQ(scip, median, GetMedian(scip, compvalues, Fsize, min)));
1077  median = GetMedian(scip, compvalues, Fsize, min);
1078  SCIPfreeBufferArray(scip, &compvalues);
1079  compvalues = NULL;
1080 
1081  SCIPdebugMessage("new median is %g, comp=%s, Ssize=%d\n", median, SCIPvarGetName(origvar), Ssize);
1082 
1083  /* add last bound change to the copy of S */
1084  copyS[Ssize].component = origvar;
1085  copyS[Ssize].sense = GCG_COMPSENSE_GE;
1086  copyS[Ssize].bound = median;
1087 
1088  /* add identified sequence to record */
1089  SCIP_CALL( addToRecord(scip, record, copyS, Ssize+1) );
1090 
1091 
1092  /* ********************************** *
1093  * end adding to record *
1094  * ********************************** */
1095  SCIPfreeMemoryArrayNull(scip, &copyS);
1096  }
1097  }
1098 
1099  if( found )
1100  {
1101  SCIPfreeBufferArrayNull(scip, &alpha);
1102 
1103  SCIPdebugMessage("one S found with size %d\n", record->sequencesizes[record->recordsize-1]);
1104 
1105  return SCIP_OKAY;
1106  }
1107 
1108 
1109  /* ********************************** *
1110  * discriminating components *
1111  * ********************************** */
1112 
1114  SCIP_CALL( SCIPallocMemoryArray(scip, &J, Jsize) );
1115  j=0;
1116  for( k = 0; k < IndexSetSize; ++k )
1117  {
1118  if( SCIPisGT(scip, alpha[k], 0.0) && SCIPisLT(scip, alpha[k], muF) )
1119  {
1120  J[j] = IndexSet[k];
1121  ++j;
1122  }
1123  }
1124  assert( j == Jsize );
1125 
1126  /* ********************************** *
1127  * compute priority (max-min) *
1128  * ********************************** */
1129 
1130  SCIP_CALL( SCIPallocMemoryArray(scip, &priority, Jsize) );
1131 
1132  for( j = 0; j < Jsize; ++j )
1133  {
1134  SCIP_Longint maxcomp;
1135  SCIP_Longint mincomp;
1136 
1137  maxcomp = SCIP_LONGINT_MIN;
1138  mincomp = SCIP_LONGINT_MAX;
1139 
1140  origvar = J[j];
1141 
1142  for( l = 0; l < Fsize; ++l )
1143  {
1144  SCIP_Longint generatorentry;
1145 
1146  assert(SCIPisIntegral(scip, getGeneratorEntry(F[l], origvar)));
1147 
1148  generatorentry = (SCIP_Longint) (getGeneratorEntry(F[l], origvar) + 0.5);
1149 
1150  if( generatorentry > maxcomp )
1151  maxcomp = generatorentry;
1152 
1153  if( generatorentry < mincomp )
1154  mincomp = generatorentry;
1155  }
1156 
1157  priority[j] = maxcomp -mincomp;
1158  }
1159 
1160  SCIP_CALL( partition(scip, J, &Jsize, priority, F, Fsize, &origvar, &median) );
1161 
1163  SCIP_CALL( SCIPallocMemoryArray(scip, &upperLowerS, (size_t)Ssize+1) );
1164  SCIP_CALL( SCIPallocMemoryArray(scip, &upperS, (size_t)Ssize+1) );
1165 
1166  for( l = 0; l < Ssize; ++l )
1167  {
1168  upperLowerS[l] = S[l];
1169  upperS[l] = S[l];
1170  }
1171 
1172  upperLowerS[Ssize].component = origvar;/* i; */
1173  upperS[Ssize].component = origvar;
1174  upperLowerS[Ssize].sense = GCG_COMPSENSE_LT;
1175  upperS[Ssize].sense = GCG_COMPSENSE_GE;
1176  upperLowerS[Ssize].bound = median;
1177  upperS[Ssize].bound = median;
1178 
1179  for( k = 0; k < Fsize; ++k )
1180  {
1181  if( SCIPisGE(scip, getGeneratorEntry(F[k], origvar), median) )
1182  ++Fupper;
1183  else
1184  ++Flower;
1185  }
1186 
1187  /* ********************************** *
1188  * choose smallest partition *
1189  * ********************************** */
1190 
1191  SCIP_CALL( SCIPallocMemoryArray(scip, &copyF, Fsize) );
1192 
1193  if( Flower > 0 )
1194  {
1195  j = 0;
1196 
1197  for( k = 0; k < Fsize; ++k )
1198  {
1199  if( SCIPisLT(scip, getGeneratorEntry(F[k], origvar), median) )
1200  {
1201  copyF[j] = F[k];
1202  ++j;
1203  }
1204  }
1205 
1206  /*Fsize = Flower;*/
1207  assert(j < Fsize+1);
1208 
1209  if( Jsize == 0 && J != NULL )
1210  {
1211  SCIPfreeMemoryArrayNull(scip, &J);
1212  }
1213 
1214  SCIP_CALL( Separate( scip, copyF, Flower, J, Jsize, upperLowerS, Ssize+1, record) );
1215  }
1216 
1217  if( Fupper > 0 )
1218  {
1219  upperLowerS[Ssize].sense = GCG_COMPSENSE_GE;
1220  j = 0;
1221 
1222  for( k = 0; k < Fsize; ++k )
1223  {
1224  if( SCIPisGE(scip, getGeneratorEntry(F[k], origvar), median) )
1225  {
1226  copyF[j] = F[k];
1227  ++j;
1228  }
1229  }
1230 
1231  /*Fsize = Fupper;*/
1232  assert(j < Fsize+1);
1233 
1234  if( Jsize == 0 && J != NULL )
1235  {
1236  SCIPfreeMemoryArrayNull(scip, &J);
1237  }
1238 
1239  SCIP_CALL( Separate( scip, copyF, Fupper, J, Jsize, upperS, Ssize+1, record) );
1240  }
1241 
1242  SCIPfreeMemoryArrayNull(scip, &copyF);
1243  SCIPfreeMemoryArrayNull(scip, &upperLowerS);
1244  SCIPfreeMemoryArrayNull(scip, &upperS);
1245  SCIPfreeMemoryArray(scip, &priority);
1246  SCIPfreeMemoryArrayNull(scip, &J);
1247  SCIPfreeBufferArray(scip, &alpha);
1248 
1249  return SCIP_OKAY;
1250 }
1251 
1253 static
1254 SCIP_RETCODE ChoseS(
1255  SCIP* scip,
1256  GCG_RECORD** record,
1257  GCG_COMPSEQUENCE** S,
1258  int* Ssize
1259  )
1260 {
1261  int minSizeOfMaxPriority; /* needed if the last comp priority is equal to the one in other bound sequences */
1262  SCIP_Longint maxPriority;
1263  int i;
1264  int Index;
1265 
1266  minSizeOfMaxPriority = INT_MAX;
1267  maxPriority = SCIP_LONGINT_MIN;
1268  Index = -1;
1269 
1270  SCIPdebugMessage("Chose S \n");
1271 
1272  assert((*record)->recordsize > 0);
1273 
1274  for( i = 0; i < (*record)->recordsize; ++i )
1275  {
1276  assert((*record)->sequencesizes != NULL );
1277  assert((*record)->sequencesizes[i] > 0);
1278 
1279  if( maxPriority <= 1 ) /* later by pseudocosts e.g. */
1280  {
1281  if( maxPriority < 1 )
1282  {
1283  maxPriority = 1; /* only choose here first smallest S */
1284  minSizeOfMaxPriority = (*record)->sequencesizes[i];
1285  Index = i;
1286  }
1287  else if( (*record)->sequencesizes[i] < minSizeOfMaxPriority )
1288  {
1289  minSizeOfMaxPriority = (*record)->sequencesizes[i];
1290  Index = i;
1291  }
1292  }
1293  }
1294  assert(maxPriority > SCIP_LONGINT_MIN);
1295  assert(minSizeOfMaxPriority < INT_MAX);
1296  assert(Index >= 0);
1297 
1298  *Ssize = minSizeOfMaxPriority;
1299  SCIP_CALL( SCIPallocMemoryArray(scip, S, *Ssize) );
1300 
1301  for( i = 0; i < *Ssize; ++i )
1302  {
1303  (*S)[i] = (*record)->record[Index][i];
1304  }
1305 
1306  assert(S!=NULL);
1307  assert(*S!=NULL);
1308 
1309  /* free record */
1310  for( i = 0; i < (*record)->recordsize; ++i )
1311  {
1312  SCIPfreeMemoryArray(scip, &((*record)->record[i]) );
1313  }
1314  SCIPfreeMemoryArray(scip, &((*record)->record) );
1315 
1316  SCIPdebugMessage("with size %d \n", *Ssize);
1317 
1318  assert(*S!=NULL);
1319 
1320  return SCIP_OKAY;
1321 }
1322 
1325 static
1327  int Csize,
1328  int p,
1329  SCIP_VAR* origvar,
1330  int* sequencesizes,
1331  GCG_COMPSEQUENCE** C,
1332  GCG_COMPSEQUENCE** CopyC,
1333  int* newsequencesizes,
1334  GCG_COMPSENSE sense
1335  )
1336 {
1337  int j;
1338  int k;
1339 
1340  for( k = 0, j = 0; j < Csize; ++j )
1341  {
1342  if ( sequencesizes[j] >= p )
1343  assert(C[j][p-1].component == origvar);
1344 
1345  if ( sequencesizes[j] >= p && C[j][p-1].sense == sense )
1346  {
1347  CopyC[k] = C[j];
1348  newsequencesizes[k] = sequencesizes[j];
1349  ++k;
1350  }
1351  }
1352 
1353  return k;
1354 }
1355 
1357 static
1359  SCIP* scip,
1360  int Fsize,
1361  GCG_COMPSENSE isense,
1362  double ivalue,
1363  SCIP_VAR* origvar,
1364  SCIP_VAR** F
1365  )
1366 {
1367  int j;
1368  SCIP_Real alpha_i = 0.0;
1369 
1370  for ( j = 0; j < Fsize; ++j )
1371  {
1372  SCIP_Real generatorentry;
1373 
1374  generatorentry = getGeneratorEntry(F[j], origvar);
1375 
1376  if ( (isense == GCG_COMPSENSE_GE && SCIPisGE(scip, generatorentry, ivalue)) ||
1377  (isense == GCG_COMPSENSE_LT && SCIPisLT(scip, generatorentry, ivalue)) )
1378  {
1379  alpha_i += SCIPgetSolVal(GCGgetMasterprob(scip), NULL, F[j]);
1380  }
1381  }
1382 
1383  return alpha_i;
1384 }
1385 
1387 static
1388 SCIP_RETCODE Explore(
1389  SCIP* scip,
1390  GCG_COMPSEQUENCE** C,
1391  int Csize,
1392  int* sequencesizes,
1393  int p,
1394  SCIP_VAR** F,
1395  int Fsize,
1396  SCIP_VAR** IndexSet,
1397  int IndexSetSize,
1398  GCG_COMPSEQUENCE** S,
1399  int* Ssize,
1400  GCG_RECORD* record
1401  )
1402 {
1403  int j;
1404  int k;
1405  SCIP_Real ivalue;
1406  GCG_COMPSENSE isense;
1407  SCIP_Real median;
1408  int Fupper;
1409  int Flower;
1410  int Cupper;
1411  int Clower;
1412  int lowerSsize;
1413  SCIP_VAR** copyF;
1414  GCG_COMPSEQUENCE* copyS;
1415  GCG_COMPSEQUENCE* lowerS;
1416  GCG_COMPSEQUENCE** CopyC;
1417  int* newsequencesizes;
1418  SCIP_VAR* origvar;
1419  SCIP_Real alpha_i;
1420  SCIP_Real muF;
1421  SCIP_Bool found;
1422 
1423  k = 0;
1424  muF = 0;
1425  Fupper = 0;
1426  Flower = 0;
1427  Cupper = 0;
1428  Clower = 0;
1429  newsequencesizes = NULL;
1430  copyF = NULL;
1431  CopyC = NULL;
1432  copyS = NULL;
1433  lowerS = NULL;
1434  found = FALSE;
1435 
1436  SCIPdebugMessage("Explore\n");
1437 
1438  SCIPdebugMessage("with Fsize = %d, Csize = %d, Ssize = %d, p = %d\n", Fsize, Csize, *Ssize, p);
1439 
1440  /* *************************************** *
1441  * if C=Ø, call separate and return that *
1442  * *************************************** */
1443 
1444  if( C == NULL || Fsize==0 || IndexSetSize==0 || Csize == 0 )
1445  {
1446  /* SCIPdebugMessage("go to Separate\n"); */
1447  assert(S != NULL);
1448 
1449  SCIP_CALL( Separate( scip, F, Fsize, IndexSet, IndexSetSize, *S, *Ssize, record) );
1450 
1451  if( *Ssize > 0 && *S != NULL )
1452  {
1453  SCIPfreeMemoryArrayNull(scip, S);
1454  *S = NULL;
1455  *Ssize = 0;
1456  }
1457  return SCIP_OKAY;
1458  }
1459 
1460  assert(C != NULL);
1461  assert(Csize > 0);
1462  assert(F != NULL);
1463  assert(IndexSet != NULL);
1464  assert(sequencesizes != NULL);
1465 
1466  /* ******************************************* *
1467  * find i which is in all S in C on position p *
1468  * ******************************************* */
1469 
1470  while( sequencesizes[k] < p )
1471  {
1472  /* SCIPdebugMessage("sequencesizes[%d] = %d\n", k, sequencesizes[k]); */
1473  ++k;
1474 
1475  if( k >= Csize )
1476  {
1477  SCIPdebugMessage("no %dth element bounded\n", p);
1478  assert(S != NULL);
1479  SCIP_CALL( Separate( scip, F, Fsize, IndexSet, IndexSetSize, *S, *Ssize, record) );
1480 
1481  if( *Ssize > 0 && *S != NULL )
1482  {
1483  SCIPfreeMemoryArrayNull(scip, S);
1484  *S = NULL;
1485  *Ssize = 0;
1486  }
1487 
1488  return SCIP_OKAY;
1489  }
1490 
1491  assert( k < Csize );
1492  }
1493 
1494  origvar = C[k][p-1].component;
1495  isense = C[k][p-1].sense;
1496  ivalue = C[k][p-1].bound;
1497 
1498  assert(origvar != NULL);
1499  assert(SCIPvarGetType(origvar) <= SCIP_VARTYPE_INTEGER);
1500 
1501  SCIPdebugMessage("orivar = %s; ivalue = %g\n", SCIPvarGetName(origvar), ivalue);
1502 
1503  for( j = 0; j < Fsize; ++j )
1504  {
1505  muF += SCIPgetSolVal(GCGgetMasterprob(scip), NULL, F[j]);
1506  }
1507 
1508  SCIPdebugMessage("muF = %g\n", muF);
1509 
1510  /* ******************************************* *
1511  * compute alpha_i *
1512  * ******************************************* */
1513 
1514  alpha_i = computeAlpha(scip, Fsize, isense, ivalue, origvar, F);
1515 
1516  SCIPdebugMessage("alpha(%s) = %g\n", SCIPvarGetName(origvar), alpha_i);
1517 
1518  /* ******************************************* *
1519  * if f > 0, add pair to record *
1520  * ******************************************* */
1521 
1522  if( !SCIPisFeasIntegral(scip, alpha_i) )
1523  {
1524  int l;
1525 
1526  found = TRUE;
1527  SCIPdebugMessage("fractional alpha(%s) = %g\n", SCIPvarGetName(origvar), alpha_i);
1528 
1529  /* ******************************************* *
1530  * add to record *
1531  * ******************************************* */
1532 
1533  SCIP_CALL( SCIPallocMemoryArray(scip, &copyS, (size_t)*Ssize+1) );
1534  for( l = 0; l < *Ssize; ++l )
1535  {
1536  copyS[l] = (*S)[l];
1537  }
1538  copyS[*Ssize].component = origvar;
1539  copyS[*Ssize].sense = isense;
1540  copyS[*Ssize].bound = ivalue;
1541  SCIP_CALL( addToRecord(scip, record, copyS, *Ssize+1) );
1542  }
1543 
1544  if( found )
1545  {
1546  SCIPdebugMessage("found fractional alpha\n");
1547  SCIPfreeMemoryArrayNull(scip, &copyS);
1548  return SCIP_OKAY;
1549  }
1550 
1551  /* add bound to the end of S */
1552  ++(*Ssize);
1553  assert(S != NULL );
1554 
1555  SCIP_CALL( SCIPreallocMemoryArray(scip, S, *Ssize) );
1556 
1557  median = ivalue;
1558  (*S)[*Ssize-1].component = origvar;
1559  (*S)[*Ssize-1].sense = GCG_COMPSENSE_GE;
1560  (*S)[*Ssize-1].bound = median;
1561 
1562  SCIP_CALL( SCIPallocMemoryArray(scip, &lowerS, *Ssize) );
1563 
1564  for( k = 0; k < *Ssize-1; ++k )
1565  {
1566  lowerS[k].component = (*S)[k].component;
1567  lowerS[k].sense = (*S)[k].sense;
1568  lowerS[k].bound = (*S)[k].bound;
1569  }
1570 
1571  lowerSsize = *Ssize;
1572  lowerS[lowerSsize-1].component = origvar;
1573  lowerS[lowerSsize-1].sense = GCG_COMPSENSE_LT;
1574  lowerS[lowerSsize-1].bound = median;
1575 
1576  for( k = 0; k < Fsize; ++k )
1577  {
1578  if( SCIPisGE(scip, getGeneratorEntry(F[k], origvar), median) )
1579  ++Fupper;
1580  else
1581  ++Flower;
1582  }
1583 
1584  /* calculate subset of C */
1585  for( j = 0; j < Csize; ++j )
1586  {
1587  if( sequencesizes[j] >= p )
1588  {
1589  if( C[j][p-1].sense == GCG_COMPSENSE_GE )
1590  {
1591  ++Cupper;
1592  }
1593  else
1594  {
1595  ++Clower;
1596  assert( C[j][p-1].sense == GCG_COMPSENSE_LT );
1597  }
1598  }
1599  }
1600 
1601  SCIPdebugMessage("Cupper = %d, Clower = %d\n", Cupper, Clower);
1602 
1603  if( SCIPisLE(scip, alpha_i, 0.0) && Fupper != 0 )
1604  Flower = INT_MAX;
1605  if( SCIPisEQ(scip, alpha_i, muF) && Flower != 0 )
1606  Fupper = INT_MAX;
1607 
1608  if( Fupper > 0 && Fupper != INT_MAX )
1609  {
1610  SCIPdebugMessage("chose upper bound Fupper = %d, Cupper = %d\n", Fupper, Cupper);
1611 
1612  SCIP_CALL( SCIPallocMemoryArray(scip, &copyF, Fupper) );
1613  for( j = 0, k = 0; k < Fsize; ++k )
1614  {
1615  if( SCIPisGE(scip, getGeneratorEntry(F[k], origvar), median) )
1616  {
1617  copyF[j] = F[k];
1618  ++j;
1619  }
1620  }
1621 
1622  /* new C */
1623  if( Fupper > 0 )
1624  {
1625  SCIP_CALL( SCIPallocMemoryArray(scip, &CopyC, Cupper) );
1626  SCIP_CALL( SCIPallocMemoryArray(scip, &newsequencesizes, Cupper) );
1627  k = computeNewSequence(Csize, p, origvar, sequencesizes, C, CopyC, newsequencesizes, GCG_COMPSENSE_GE);
1628  if( k != Cupper )
1629  {
1630  SCIPdebugMessage("k = %d, p = %d\n", k, p);
1631  }
1632  assert(k == Cupper);
1633  }
1634  else
1635  {
1636  CopyC = NULL;
1637  }
1638 
1639  SCIP_CALL( Explore( scip, CopyC, Cupper, newsequencesizes, p+1, copyF, Fupper, IndexSet, IndexSetSize, S, Ssize, record) );
1640  SCIPfreeMemoryArrayNull(scip, &copyF);
1641  copyF = NULL;
1642  }
1643 
1644  if( Flower > 0 && Flower != INT_MAX )
1645  {
1646  SCIPdebugMessage("chose lower bound Flower = %d Clower = %d\n", Flower, Clower);
1647 
1648  assert( copyF == NULL );
1649  SCIP_CALL( SCIPallocMemoryArray(scip, &copyF, Flower) );
1650 
1651  j = 0;
1652  for( k = 0; k < Fsize; ++k )
1653  {
1654  if( SCIPisLT(scip, getGeneratorEntry(F[k], origvar), median) )
1655  {
1656  copyF[j] = F[k];
1657  ++j;
1658  }
1659  }
1660 
1661  /* new C */
1662  if( Flower > 0 )
1663  {
1664  SCIPfreeMemoryArrayNull(scip, &CopyC);
1665  SCIPfreeMemoryArrayNull(scip, &newsequencesizes);
1666 
1667  SCIP_CALL( SCIPallocMemoryArray(scip, &CopyC, Clower) );
1668  SCIP_CALL( SCIPallocMemoryArray(scip, &newsequencesizes, Clower) );
1669  k = computeNewSequence(Csize, p, origvar, sequencesizes, C, CopyC, newsequencesizes, GCG_COMPSENSE_LT);
1670  if( k != Clower )
1671  {
1672  SCIPdebugMessage("k = %d, p = %d\n", k, p);
1673  }
1674  assert(k == Clower);
1675  }
1676  else
1677  {
1678  CopyC = NULL;
1679  }
1680 
1681  SCIP_CALL( Explore( scip, CopyC, Clower, newsequencesizes, p+1, copyF, Flower, IndexSet, IndexSetSize, &lowerS, &lowerSsize, record) );
1682  SCIPfreeMemoryArrayNull(scip, &copyF);
1683  }
1684 
1685  SCIPfreeMemoryArrayNull(scip, &copyS);
1686  SCIPfreeMemoryArrayNull(scip, &lowerS);
1687  SCIPfreeMemoryArrayNull(scip, &CopyC);
1688  SCIPfreeMemoryArrayNull(scip, &newsequencesizes);
1689 
1690  if( *Ssize > 0 && *S != NULL )
1691  {
1692  SCIPfreeMemoryArrayNull(scip, S);
1693 
1694  *Ssize = 0;
1695  }
1696 
1697  return SCIP_OKAY;
1698 }
1699 
1702 static
1704  SCIP* scip,
1705  SCIP_VAR** F ,
1706  int Fsize,
1707  GCG_COMPSEQUENCE** S,
1708  int* Ssize,
1709  GCG_COMPSEQUENCE** C,
1710  int Csize,
1711  int* CompSizes,
1712  int blocknr,
1713  SCIP_BRANCHRULE* branchrule,
1714  SCIP_RESULT* result,
1715  int** checkedblocks,
1716  int* ncheckedblocks,
1717  GCG_STRIP**** checkedblockssortstrips,
1718  int** checkedblocksnsortstrips
1719  )
1720 {
1721  int i;
1722  SCIP_VAR** IndexSet;
1723  SCIP_VAR** mastervars;
1724  int IndexSetSize;
1725  GCG_RECORD* record;
1726  int exploreSsize;
1727  GCG_COMPSEQUENCE* exploreS;
1728  GCG_STRIP** strips;
1729  int nstrips;
1730  int nmastervars;
1731 
1732  assert(Fsize > 0);
1733  assert(F != NULL);
1734  IndexSetSize = 0;
1735  exploreSsize = 0;
1736  exploreS = NULL;
1737  record = NULL;
1738  IndexSet = NULL;
1739  strips = NULL;
1740  nstrips = 0;
1741 
1742  SCIPdebugMessage("Calling Separate\n");
1743 
1744  SCIP_CALL( SCIPallocBuffer(scip, &record) );
1745  record->recordsize = 0;
1746  record->record = NULL;
1747  record->sequencesizes = NULL;
1748 
1749  /* calculate IndexSet */
1750  SCIP_CALL( InitIndexSet(scip, F, Fsize, &IndexSet, &IndexSetSize) );
1751  assert(IndexSetSize > 0);
1752  assert(IndexSet != NULL);
1753 
1754  /* rootnode? */
1755  if( Csize<=0 )
1756  SCIP_CALL( Separate( scip, F, Fsize, IndexSet, IndexSetSize, NULL, 0, record) );
1757  else
1758  {
1759  assert( C!=NULL );
1760  SCIP_CALL( Explore( scip, C, Csize, CompSizes, 1, F, Fsize, IndexSet, IndexSetSize, &exploreS, &exploreSsize, record) );
1761 
1762  SCIPfreeMemoryArrayNull(scip, &exploreS);
1763  }
1764 
1765  assert(record != NULL);
1766 
1767  if( record->recordsize <= 0 )
1768  {
1769  SCIP_CALL( SCIPgetVarsData(GCGgetMasterprob(scip), &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
1770 
1771  ++(*ncheckedblocks);
1772  assert((*ncheckedblocks) <= GCGgetNPricingprobs(scip)+1);
1773 
1774  if( (*ncheckedblocks) > 1 )
1775  {
1776  SCIP_CALL( SCIPreallocBufferArray(scip, checkedblocks, *ncheckedblocks) );
1777  SCIP_CALL( SCIPreallocBufferArray(scip, checkedblockssortstrips, *ncheckedblocks) );
1778  SCIP_CALL( SCIPreallocBufferArray(scip, checkedblocksnsortstrips, *ncheckedblocks) );
1779  }
1780  else
1781  {
1782  SCIP_CALL( SCIPallocBufferArray(scip, checkedblocks, *ncheckedblocks) );
1783  SCIP_CALL( SCIPallocBufferArray(scip, checkedblockssortstrips, *ncheckedblocks) );
1784  SCIP_CALL( SCIPallocBufferArray(scip, checkedblocksnsortstrips, *ncheckedblocks) );
1785  }
1786 
1787  (*checkedblocks)[(*ncheckedblocks)-1] = blocknr;
1788 
1789  for( i=0; i<nmastervars; ++i )
1790  {
1791  if( GCGisMasterVarInBlock(mastervars[i], blocknr) )
1792  {
1793  ++nstrips;
1794 
1795  SCIP_CALL( SCIPreallocBufferArray(scip, &strips, nstrips) );
1796 
1797  assert(strips != NULL);
1798 
1799  SCIP_CALL( SCIPallocBuffer(scip, &(strips[nstrips-1])) ); /*lint !e866*/
1800  assert(strips[nstrips-1] != NULL);
1801 
1802  strips[nstrips-1]->C = NULL;
1803  strips[nstrips-1]->mastervar = mastervars[i];
1804  strips[nstrips-1]->Csize = 0;
1805  strips[nstrips-1]->sequencesizes = NULL;
1806  strips[nstrips-1]->scip = NULL;
1807  }
1808  }
1809 
1810  SCIP_CALL( InducedLexicographicSort(scip, strips, nstrips, C, Csize, CompSizes) );
1811 
1812  (*checkedblocksnsortstrips)[(*ncheckedblocks)-1] = nstrips;
1813 
1814  SCIP_CALL( SCIPallocBufferArray(scip, &((*checkedblockssortstrips)[(*ncheckedblocks)-1]), nstrips) ); /*lint !e866*/
1815 
1816  /* sort the direct copied origvars at the end */
1817 
1818  for( i = 0; i < nstrips; ++i )
1819  {
1820  assert(strips != NULL);
1821 
1822  SCIP_CALL( SCIPallocBuffer(scip, &(*checkedblockssortstrips[*ncheckedblocks-1][i])) ); /*lint !e866*/
1823  *checkedblockssortstrips[*ncheckedblocks-1][i] = strips[i];
1824  }
1825 
1826  for( i=0; i<nstrips; ++i )
1827  {
1828  assert(strips != NULL);
1829  SCIPfreeBuffer(scip, &(strips[i]));
1830  strips[i] = NULL;
1831  }
1832  SCIPfreeBufferArrayNull(scip, &strips);
1833 
1834  /*choose new block */
1835  SCIP_CALL( GCGbranchGenericInitbranch(GCGgetMasterprob(scip), branchrule, result, checkedblocks, ncheckedblocks, checkedblockssortstrips, checkedblocksnsortstrips) );
1836 
1837  }
1838  else
1839  {
1840  if( ncheckedblocks != NULL && (*ncheckedblocks) > 0 )
1841  {
1842  SCIPfreeBufferArray(scip, checkedblocks);
1843 
1844  for( i = (*ncheckedblocks) - 1; i >= 0; --i )
1845  {
1846  int j;
1847 
1848  for( j = (*checkedblocksnsortstrips)[i] - 1; j >= 0; --j )
1849  {
1850  SCIPfreeBuffer(scip, &((*checkedblockssortstrips)[i][j]) );
1851  }
1852 
1853  SCIPfreeBufferArray(scip, &((*checkedblockssortstrips)[i]) );
1854  }
1855 
1856  SCIPfreeBufferArray(scip, checkedblockssortstrips);
1857  SCIPfreeBufferArray(scip, checkedblocksnsortstrips);
1858  *ncheckedblocks = 0;
1859  }
1860  }
1861 
1862  if( record->recordsize > 0 )
1863  {
1864  SCIP_CALL( ChoseS( scip, &record, S, Ssize) );
1865  assert(*S != NULL);
1866  }
1867 
1868 
1869  SCIPfreeMemoryArray(scip, &IndexSet);
1870  if( record != NULL )
1871  {
1872  SCIPfreeMemoryArrayNull(scip, &record->record);
1873  SCIPfreeMemoryArrayNull(scip, &record->sequencesizes);
1874  SCIPfreeBuffer(scip, &record);
1875  }
1876  return SCIP_OKAY;
1877 }
1878 
1880 static
1881 GCG_DECL_BRANCHDATADELETE(branchDataDeleteGeneric)
1882 {
1883  assert(scip != NULL);
1884  assert(branchdata != NULL);
1885 
1886  if( *branchdata == NULL )
1887  {
1888  SCIPdebugMessage("branchDataDeleteGeneric: cannot delete empty branchdata\n");
1889 
1890  return SCIP_OKAY;
1891  }
1892 
1893  if( (*branchdata)->mastercons != NULL )
1894  {
1895  SCIPdebugMessage("branchDataDeleteGeneric: child blocknr %d, %s\n", (*branchdata)->consblocknr,
1896  SCIPconsGetName((*branchdata)->mastercons) );
1897  }
1898  else
1899  {
1900  SCIPdebugMessage("branchDataDeleteGeneric: child blocknr %d, empty mastercons\n", (*branchdata)->consblocknr);
1901  }
1902 
1903  /* release constraint that enforces the branching decision */
1904  if( (*branchdata)->mastercons != NULL )
1905  {
1906  SCIP_CALL( SCIPreleaseCons(GCGgetMasterprob(scip), &(*branchdata)->mastercons) );
1907  (*branchdata)->mastercons = NULL;
1908  }
1909 
1910  if( (*branchdata)->consS != NULL && (*branchdata)->consSsize > 0 )
1911  {
1912  SCIPfreeBlockMemoryArrayNull(scip, &((*branchdata)->consS), (*branchdata)->consSsize);
1913  (*branchdata)->consS = NULL;
1914  (*branchdata)->consSsize = 0;
1915  }
1916 
1917  SCIPfreeBlockMemoryNull(scip, branchdata);
1918  *branchdata = NULL;
1919 
1920  return SCIP_OKAY;
1921 }
1922 
1925 static
1927  SCIP* scip,
1928  SCIP_Real lhs,
1929  GCG_COMPSEQUENCE* childS,
1930  int childSsize,
1931  SCIP_CONS* parentcons,
1932  int childBlocknr
1933  )
1934 {
1935  int i;
1936  int nchildren;
1937 
1938  nchildren = GCGconsMasterbranchGetNChildconss(parentcons);
1939  assert(nchildren>0);
1940 
1941  for( i=0; i<nchildren; ++i )
1942  {
1943  SCIP_CONS* childcons;
1944  GCG_BRANCHDATA* branchdata;
1945  SCIP_Bool same;
1946  int j;
1947 
1948  same = TRUE;
1949  childcons = GCGconsMasterbranchGetChildcons(parentcons, i);
1950  if( childcons == NULL )
1951  continue;
1952 
1953  if( GCGconsMasterbranchGetBranchrule(childcons) != NULL && strcmp(SCIPbranchruleGetName(GCGconsMasterbranchGetBranchrule(childcons)), "generic") != 0 )
1954  continue;
1955 
1956  branchdata = GCGconsMasterbranchGetBranchdata(childcons);
1957  assert(branchdata != NULL);
1958 
1959  if( childBlocknr != branchdata->consblocknr || childSsize != branchdata->consSsize || !SCIPisEQ(scip, lhs, branchdata->lhs) )
1960  continue;
1961 
1962  assert(childSsize > 0 && branchdata->consSsize > 0);
1963 
1964  for( j=0; j< childSsize; ++j )
1965  {
1966  if( childS[j].component != branchdata->consS[j].component
1967  || childS[j].sense != branchdata->consS[j].sense
1968  || !SCIPisEQ(scip, childS[j].bound, branchdata->consS[j].bound) )
1969  {
1970  same = FALSE;
1971  break;
1972  }
1973  }
1974 
1975  if( same )
1976  {
1977  SCIPdebugMessage("child pruned \n");
1978  return TRUE;
1979  }
1980  }
1981  return FALSE;
1982 }
1983 
1986 static
1988  SCIP* scip,
1989  SCIP_Real lhs,
1990  GCG_COMPSEQUENCE* childS,
1991  int childSsize,
1992  SCIP_CONS* masterbranchcons,
1993  int childBlocknr
1994  )
1995 {
1996  SCIP_CONS* cons;
1997 
1998  SCIPdebugMessage("Prune by dominance\n");
1999  cons = GCGconsMasterbranchGetParentcons(masterbranchcons);
2000 
2001  if( cons == NULL )
2002  {
2003  SCIPdebugMessage("cons == NULL, not pruned\n");
2004  return FALSE;
2005  }
2006  while( cons != NULL )
2007  {
2008  GCG_BRANCHDATA* parentdata;
2009  SCIP_Bool ispruned;
2010 
2011  parentdata = GCGconsMasterbranchGetBranchdata(cons);
2012  if( parentdata == NULL )
2013  {
2014  /* root node: check children for pruning */
2015  return checkchildconsS(scip, lhs, childS, childSsize, cons, childBlocknr);
2016  }
2017  if( strcmp(SCIPbranchruleGetName(GCGconsMasterbranchGetBranchrule(cons)), "generic") != 0 )
2018  return checkchildconsS(scip, lhs, childS, childSsize, cons, childBlocknr);
2019 
2020  ispruned = checkchildconsS(scip, lhs, childS, childSsize, cons, childBlocknr);
2021 
2022  if( ispruned )
2023  {
2024  return TRUE;
2025  }
2026 
2027  cons = GCGconsMasterbranchGetParentcons(cons);
2028  }
2029 
2030  SCIPdebugMessage("child not pruned\n");
2031  return FALSE;
2032 }
2033 
2035 static
2036 SCIP_RETCODE initNodeBranchdata(
2037  SCIP* scip,
2038  GCG_BRANCHDATA** nodebranchdata,
2039  int blocknr
2040  )
2041 {
2042  SCIP_CALL( SCIPallocBlockMemory(scip, nodebranchdata) );
2043 
2044  (*nodebranchdata)->consblocknr = blocknr;
2045  (*nodebranchdata)->mastercons = NULL;
2046  (*nodebranchdata)->consS = NULL;
2047  (*nodebranchdata)->C = NULL;
2048  (*nodebranchdata)->sequencesizes = NULL;
2049  (*nodebranchdata)->Csize = 0;
2050  (*nodebranchdata)->consSsize = 0;
2051  (*nodebranchdata)->nvars = 0;
2052 
2053  return SCIP_OKAY;
2054 }
2055 
2057 static
2059  SCIP* scip,
2060  SCIP_BRANCHRULE* branchrule,
2061  GCG_COMPSEQUENCE* S,
2062  int Ssize,
2063  int blocknr,
2064  SCIP_CONS* masterbranchcons,
2065  SCIP_RESULT* result
2066  )
2067 {
2068 #ifdef SCIP_DEBUG
2069  SCIP_Real identicalcontrol = 0;
2070 #endif
2071  SCIP* masterscip;
2072  int i;
2073  int p;
2074  SCIP_Real pL;
2075  SCIP_Real L;
2076  SCIP_Real lhsSum;
2077  int nmastervars;
2078  int nmastervars2;
2079  int ncopymastervars;
2080  int nbranchcands;
2081  int nchildnodes;
2082  SCIP_VAR** mastervars;
2083  SCIP_VAR** mastervars2;
2084  SCIP_VAR** branchcands;
2085  SCIP_VAR** copymastervars;
2086 
2087  assert(scip != NULL);
2088  assert(Ssize > 0);
2089  assert(S != NULL);
2090 
2091  lhsSum = 0;
2092  nchildnodes = 0;
2093  L = 0;
2094 
2095  pL = GCGgetNIdenticalBlocks(scip, blocknr);
2096  SCIPdebugMessage("Vanderbeck branching rule Node creation for blocknr %d with %.1f identical blocks \n", blocknr, pL);
2097 
2098 
2099  /* get variable data of the master problem */
2100  masterscip = GCGgetMasterprob(scip);
2101  assert(masterscip != NULL);
2102  SCIP_CALL( SCIPgetVarsData(masterscip, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
2103  nmastervars2 = nmastervars;
2104  assert(nmastervars >= 0);
2105 
2106  SCIP_CALL( SCIPduplicateMemoryArray(scip, &copymastervars, mastervars, nmastervars) );
2107  SCIP_CALL( SCIPduplicateMemoryArray(scip, &mastervars2, mastervars, nmastervars) );
2108 
2109  SCIP_CALL( SCIPgetLPBranchCands(masterscip, &branchcands, NULL, NULL, &nbranchcands, NULL, NULL) );
2110 
2111  SCIPdebugMessage("Vanderbeck branching rule: creating %d nodes\n", Ssize+1);
2112 
2113  for( p=0; p<Ssize+1; ++p )
2114  {
2115  GCG_BRANCHDATA* branchchilddata;
2116  SCIP_NODE* child;
2117  SCIP_CONS* childcons;
2118  int k;
2119 
2120  SCIP_Real lhs;
2121  branchchilddata = NULL;
2122 
2123  /* allocate branchdata for child and store information */
2124  SCIP_CALL( initNodeBranchdata(scip, &branchchilddata, blocknr) );
2125 
2126  if( p == Ssize )
2127  {
2128  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(branchchilddata->consS), Ssize) );
2129  branchchilddata->consSsize = Ssize;
2130  }
2131  else
2132  {
2133  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(branchchilddata->consS), (size_t)p+1) );
2134  branchchilddata->consSsize = p+1;
2135  }
2136  for( k = 0; k <= p; ++k )
2137  {
2138  GCG_COMPSEQUENCE compBound;
2139 
2140  if( k == Ssize )
2141  {
2142  assert( p == Ssize );
2143  compBound = S[k-1];
2144  branchchilddata->consS[k-1] = compBound;
2145  }
2146  else
2147  {
2148  compBound = S[k];
2149  if( k >= p )
2150  {
2151  if( S[p].sense == GCG_COMPSENSE_GE )
2152  compBound.sense = GCG_COMPSENSE_LT;
2153  else
2154  compBound.sense = GCG_COMPSENSE_GE;
2155  }
2156  branchchilddata->consS[k] = compBound;
2157  }
2158  }
2159 
2160  /* last node? */
2161  if( p == Ssize )
2162  {
2163  lhs = pL;
2164  }
2165  else
2166  {
2167  /* calculate mu */
2168  SCIP_Real mu = 0.0;
2169 
2170  ncopymastervars = nmastervars2;
2171  for( i = 0; i < ncopymastervars; ++i )
2172  {
2173  SCIP_VAR* swap;
2174 
2175  if( i >= nmastervars2 )
2176  break;
2177 
2178  if( GCGisMasterVarInBlock(mastervars2[i], blocknr) )
2179  {
2180  SCIP_Real generator_i = getGeneratorEntry(mastervars2[i], S[p].component);
2181 
2182  if( (S[p].sense == GCG_COMPSENSE_GE && SCIPisGE(scip, generator_i, S[p].bound)) ||
2183  (S[p].sense == GCG_COMPSENSE_LT && SCIPisLT(scip, generator_i, S[p].bound) ) )
2184  {
2185  mu += SCIPgetSolVal(masterscip, NULL, mastervars2[i]);
2186  }
2187  else if( ncopymastervars > 0 )
2188  {
2189  swap = mastervars2[i];
2190  mastervars2[i] = mastervars2[nmastervars2-1];
2191  mastervars2[nmastervars2-1] = swap;
2192  --nmastervars2;
2193  --i;
2194  }
2195  }
2196  else if( nmastervars2 > 0 )
2197  {
2198  swap = mastervars2[i];
2199  mastervars2[i] = mastervars2[nmastervars2-1];
2200  mastervars2[nmastervars2-1] = swap;
2201  --nmastervars2;
2202  --i;
2203  }
2204  }
2205 
2206  if( p == Ssize-1 ) /*lint !e866 !e850*/
2207  {
2208  L = SCIPceil(scip, mu);
2209  SCIPdebugMessage("mu = %g, \n", mu);
2210  assert(!SCIPisFeasIntegral(scip,mu));
2211  }
2212  else
2213  {
2214  L = mu;
2215  SCIPdebugMessage("mu = %g should be integer, \n", mu);
2216  assert(SCIPisFeasIntegral(scip,mu));
2217  }
2218  lhs = pL-L+1;
2219  }
2220  SCIPdebugMessage("pL = %g \n", pL);
2221  pL = L;
2222 
2223  branchchilddata->lhs = lhs;
2224  SCIPdebugMessage("L = %g, \n", L);
2225  SCIPdebugMessage("lhs set to %g \n", lhs);
2226  assert(SCIPisFeasIntegral(scip, lhs));
2227  lhsSum += lhs;
2228 
2229 
2230  if( masterbranchcons == NULL || !pruneChildNodeByDominanceGeneric(scip, lhs, branchchilddata->consS, branchchilddata->consSsize, masterbranchcons, blocknr) )
2231  {
2232  if( masterbranchcons != NULL )
2233  {
2234  char childname[SCIP_MAXSTRLEN];
2235  ++nchildnodes;
2236 
2237  assert(branchchilddata != NULL);
2238 
2239  /* define names for origbranch constraints */
2240  (void) SCIPsnprintf(childname, SCIP_MAXSTRLEN, "node(%d, %d) (last comp=%s %s %g) >= %g", blocknr, p+1,
2241  SCIPvarGetName(branchchilddata->consS[branchchilddata->consSsize-1].component),
2242  branchchilddata->consS[branchchilddata->consSsize-1].sense == GCG_COMPSENSE_GE? ">=": "<",
2243  branchchilddata->consS[branchchilddata->consSsize-1].bound,
2244  branchchilddata->lhs);
2245 
2246  SCIP_CALL( SCIPcreateChild(masterscip, &child, 0.0, SCIPgetLocalTransEstimate(masterscip)) );
2247  SCIP_CALL( GCGcreateConsMasterbranch(masterscip, &childcons, childname, child,
2248  GCGconsMasterbranchGetActiveCons(masterscip), branchrule, branchchilddata, NULL, 0) );
2249  SCIP_CALL( SCIPaddConsNode(masterscip, child, childcons, NULL) );
2250 
2251  SCIP_CALL( createBranchingCons(masterscip, child, branchchilddata) );
2252 
2253  /* release constraints */
2254  SCIP_CALL( SCIPreleaseCons(masterscip, &childcons) );
2255  }
2256  }
2257  else
2258  {
2259  SCIPfreeBlockMemoryArrayNull(scip, &(branchchilddata->consS), branchchilddata->consSsize);
2260  SCIPfreeBlockMemoryNull(scip, &branchchilddata);
2261  }
2262  }
2263  SCIPdebugMessage("lhsSum = %g\n", lhsSum);
2264 
2265 #ifdef SCIP_DEBUG
2266  SCIP_CALL( SCIPgetVarsData(masterscip, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
2267 
2268  for( i = 0; i < nmastervars; ++i )
2269  {
2270  SCIP_VAR* mastervar = mastervars[i];
2271 
2272  if( GCGisMasterVarInBlock(mastervar, blocknr) )
2273  {
2274  identicalcontrol += SCIPgetSolVal(masterscip, NULL, mastervar);
2275  }
2276 
2277  }
2278  if( !SCIPisEQ(scip, identicalcontrol, GCGgetNIdenticalBlocks(scip, blocknr)) )
2279  {
2280  SCIPdebugMessage("width of the block is only %g\n", identicalcontrol);
2281  }
2282 
2283  assert( SCIPisEQ(scip, identicalcontrol, GCGgetNIdenticalBlocks(scip, blocknr)) );
2284 #endif
2285 
2286  assert( SCIPisEQ(scip, lhsSum, 1.0*(GCGgetNIdenticalBlocks(scip, blocknr) + Ssize)) );
2287 
2288  SCIPfreeMemoryArray(scip, &mastervars2);
2289  SCIPfreeMemoryArray(scip, &copymastervars);
2290 
2291  if( nchildnodes <= 0 )
2292  {
2293  SCIPdebugMessage("node cut off, since all childnodes have been pruned\n");
2294 
2295  *result = SCIP_CUTOFF;
2296  }
2297 
2298  return SCIP_OKAY;
2299 }
2300 
2302 static
2304  SCIP* scip,
2305  SCIP_VAR* mastervar,
2306  SCIP_BRANCHRULE* branchrule
2307  )
2308 {
2309  SCIP* masterscip;
2310  GCG_BRANCHDATA* branchupchilddata;
2311  GCG_BRANCHDATA* branchdownchilddata;
2312  SCIP_NODE* upchild;
2313  SCIP_NODE* downchild;
2314  SCIP_CONS* upchildcons;
2315  SCIP_CONS* downchildcons;
2316  char upchildname[SCIP_MAXSTRLEN];
2317  char downchildname[SCIP_MAXSTRLEN];
2318  int bound;
2319 
2320  masterscip = GCGgetMasterprob(scip);
2321  assert(masterscip != NULL);
2322 
2323  bound = (int) (SCIPceil( scip, SCIPgetSolVal(masterscip, NULL, mastervar)) + 0.5); /*lint -e524*/
2324 
2325  /* allocate branchdata for child and store information */
2326  SCIP_CALL( initNodeBranchdata(scip, &branchupchilddata, -3) );
2327  SCIP_CALL( initNodeBranchdata(scip, &branchdownchilddata, -3) );
2328 
2329  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(branchupchilddata->consS), 1) ); /*lint !e506*/
2330  branchupchilddata->consSsize = 1;
2331 
2332  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(branchdownchilddata->consS), 1) ); /*lint !e506*/
2333  branchdownchilddata->consSsize = 1;
2334 
2335  branchupchilddata->consS[0].component = mastervar;
2336  branchupchilddata->consS[0].sense = GCG_COMPSENSE_GE;
2337  branchupchilddata->consS[0].bound = bound;
2338 
2339  branchdownchilddata->consS[0].component = mastervar;
2340  branchdownchilddata->consS[0].sense = GCG_COMPSENSE_LT;
2341  branchdownchilddata->consS[0].bound = bound;
2342 
2343 
2344  assert(branchupchilddata != NULL);
2345  assert(branchdownchilddata != NULL);
2346 
2347  (void) SCIPsnprintf(upchildname, SCIP_MAXSTRLEN, "node(-3, %f) direct up on comp=%s", branchupchilddata->consS[0].bound,
2348  SCIPvarGetName(branchupchilddata->consS[branchupchilddata->consSsize-1].component));
2349  (void) SCIPsnprintf(downchildname, SCIP_MAXSTRLEN, "node(-3, %f) direct up on comp=%s", branchdownchilddata->consS[0].bound,
2350  SCIPvarGetName(branchdownchilddata->consS[branchdownchilddata->consSsize-1].component));
2351 
2352  SCIP_CALL( SCIPcreateChild(masterscip, &upchild, 0.0, SCIPgetLocalTransEstimate(masterscip)) );
2353  SCIP_CALL( GCGcreateConsMasterbranch(masterscip, &upchildcons, upchildname, upchild,
2354  GCGconsMasterbranchGetActiveCons(masterscip), branchrule, branchupchilddata, NULL, 0) );
2355  SCIP_CALL( SCIPaddConsNode(masterscip, upchild, upchildcons, NULL) );
2356 
2357  SCIP_CALL( SCIPcreateChild(masterscip, &downchild, 0.0, SCIPgetLocalTransEstimate(masterscip)) );
2358  SCIP_CALL( GCGcreateConsMasterbranch(masterscip, &downchildcons, downchildname, downchild,
2359  GCGconsMasterbranchGetActiveCons(masterscip), branchrule, branchdownchilddata, NULL, 0) );
2360  SCIP_CALL( SCIPaddConsNode(masterscip, downchild, downchildcons, NULL) );
2361 
2362  /* create branching constraint in master */
2363  SCIP_CALL( createDirectBranchingCons(masterscip, upchild, branchupchilddata) );
2364  SCIP_CALL( createDirectBranchingCons(masterscip, downchild, branchdownchilddata) );
2365 
2366  /* release constraints */
2367  SCIP_CALL( SCIPreleaseCons(masterscip, &upchildcons) );
2368  SCIP_CALL( SCIPreleaseCons(masterscip, &downchildcons) );
2369 
2370  return SCIP_OKAY;
2371 }
2372 
2375  SCIP* masterscip,
2376  SCIP_BRANCHRULE* branchrule,
2377  SCIP_RESULT* result,
2378  int** checkedblocks,
2379  int* ncheckedblocks,
2380  GCG_STRIP**** checkedblockssortstrips,
2381  int** checkedblocksnsortstrips
2382  )
2383 {
2384  SCIP* origscip;
2385  SCIP_VAR** branchcands;
2386  SCIP_VAR** allorigvars;
2387  SCIP_VAR** mastervars;
2388  int nmastervars;
2389  SCIP_CONS* masterbranchcons;
2390  int nbranchcands;
2391  GCG_BRANCHDATA* branchdata;
2392  SCIP_VAR* mastervar;
2393  SCIP_Real mastervarValue;
2394  GCG_COMPSEQUENCE* S;
2395  GCG_COMPSEQUENCE** C;
2396  SCIP_VAR** F;
2397  int Ssize;
2398  int Fsize;
2399  int* sequencesizes;
2400  int blocknr;
2401  int i;
2402  int j;
2403  int allnorigvars;
2404 #ifndef NDEBUG
2405  SCIP_Bool foundblocknr = FALSE;
2406 #endif
2407 
2408  SCIP_Bool discretization;
2409 
2410  blocknr = -2;
2411  Ssize = 0;
2412  Fsize = 0;
2413  branchdata = NULL;
2414  S = NULL;
2415  C = NULL;
2416  F = NULL;
2417  sequencesizes = NULL;
2418 
2419  assert(masterscip != NULL);
2420 
2421  SCIPdebugMessage("get information for Vanderbecks generic branching\n");
2422 
2423  origscip = GCGmasterGetOrigprob(masterscip);
2424 
2425  SCIP_CALL( SCIPgetBoolParam(origscip, "relaxing/gcg/discretization", &discretization) );
2426 
2427  assert(origscip != NULL);
2428  SCIP_CALL( SCIPgetLPBranchCands(masterscip, &branchcands, NULL, NULL, &nbranchcands, NULL, NULL) );
2429 
2430  SCIP_CALL( SCIPgetVarsData(origscip, &allorigvars, &allnorigvars, NULL, NULL, NULL, NULL) );
2431  SCIP_CALL( SCIPgetVarsData(masterscip, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
2432 
2433  /* in case original problem contains continuous variables, there are no branching cands */
2434  assert(nbranchcands > 0 || (discretization && SCIPgetNContVars(origscip) > 0));
2435  mastervar = NULL;
2436 
2438  for( i = 0; i < nbranchcands && (!discretization || SCIPgetNContVars(origscip) == 0); ++i )
2439  {
2440  int k;
2441  mastervar = branchcands[i];
2442  assert(GCGvarIsMaster(mastervar));
2443 
2444  /* if we have a master variable, we branch on it */
2445  if( GCGvarGetBlock(mastervar) == -1 )
2446  {
2447  assert(!GCGmasterVarIsArtificial(mastervar));
2448 #ifndef NDEBUG
2449  foundblocknr = TRUE;
2450 #endif
2451  blocknr = -1;
2452  break;
2453  }
2454 
2455  /* else, check if the candidate is in an unchecked block */
2456  for( j = 0; j < GCGgetNPricingprobs(origscip); ++j )
2457  {
2458  SCIP_Bool checked = FALSE;
2459  for( k = 0; ncheckedblocks != NULL && k < (*ncheckedblocks); ++k )
2460  {
2461  /* if the block has been checked, no need to check master variable */
2462  if( (*checkedblocks)[k] == j )
2463  {
2464  checked = TRUE;
2465  break;
2466  }
2467  }
2468 
2469  if( checked )
2470  continue;
2471  /* else the block has not been checked and the variable is in it , we have a candidate */
2472  else if( GCGisMasterVarInBlock(mastervar, j) )
2473  {
2474 #ifndef NDEBUG
2475  foundblocknr = TRUE;
2476 #endif
2477  blocknr = j;
2478  break;
2479  }
2480  }
2481  }
2482  assert(foundblocknr || blocknr == -1 || (discretization && SCIPgetNContVars(origscip) > 0));
2483  assert(i <= nbranchcands); /* else all blocks has been checked and we can observe an integer solution */
2484 
2485  /* in case of continuous origvar look for "fractional" blocks using the representation (currentorigsol) in the original problem */
2486  if(discretization && SCIPgetNContVars(origscip) > 0)
2487  {
2488  int norigvars;
2489  SCIP_VAR** origvars;
2490  SCIP_VAR* origvar;
2491 
2492  norigvars = SCIPgetNVars(origscip);
2493  origvars = SCIPgetVars(origscip);
2494 
2495  nbranchcands = SCIPgetNVars(masterscip);
2496  branchcands = SCIPgetVars(masterscip);
2497 
2498  assert(nbranchcands > 0);
2499 
2500  for( i = 0; i < norigvars; ++i )
2501  {
2502  int k;
2503  SCIP_Bool checked;
2504  origvar = origvars[i];
2505 
2506  if( SCIPvarGetType(origvar) > SCIP_VARTYPE_INTEGER )
2507  continue;
2508 
2509  if( SCIPisIntegral(origscip, SCIPgetSolVal(origscip, GCGrelaxGetCurrentOrigSol(origscip), origvar)) )
2510  continue;
2511 
2512  blocknr = GCGgetBlockRepresentative(origscip, GCGvarGetBlock(origvar));
2513 
2514  SCIPdebugMessage("Variable %s belonging to block %d with representative %d is not integral!\n", SCIPvarGetName(origvar), GCGvarGetBlock(origvar), blocknr);
2515 
2516  if( blocknr == -1 )
2517  {
2518  assert(GCGoriginalVarGetNMastervars(origvar) == 1);
2519  mastervar = GCGoriginalVarGetMastervars(origvar)[0];
2520  break;
2521  }
2522 
2523  checked = FALSE;
2524  for( k = 0; ncheckedblocks != NULL && k < (*ncheckedblocks); ++k )
2525  {
2526  /* if the block has been checked, no need to check master variable */
2527  if( (*checkedblocks)[k] == blocknr )
2528  {
2529  checked = TRUE;
2530  break;
2531  }
2532  }
2533 
2534  if( checked )
2535  {
2536  continue;
2537  }
2538  else
2539  {
2540  break;
2541  }
2542  }
2543  }
2544 
2545  if( blocknr < -1 )
2546  {
2547  SCIP_Bool rays;
2548 
2549  SCIPdebugMessage("Generic branching rule could not find variables to branch on!\n");
2550 
2551  SCIP_CALL( GCGpricerExistRays(masterscip, &rays) );
2552 
2553  if( rays )
2554  SCIPwarningMessage(masterscip, "Generic branching is not compatible with unbounded problems!\n");
2555 
2556  return SCIP_ERROR;
2557  }
2558 
2559  /* a special case; branch on copy of an origvar directly */
2560  if( blocknr == -1 )
2561  {
2562  assert(!GCGmasterVarIsLinking(mastervar));
2563  SCIPdebugMessage("branching on master variable\n");
2564  SCIP_CALL( branchDirectlyOnMastervar(origscip, mastervar, branchrule) );
2565  return SCIP_OKAY;
2566  }
2567 
2568  masterbranchcons = GCGconsMasterbranchGetActiveCons(masterscip);
2569  SCIPdebugMessage("branching in block %d \n", blocknr);
2570 
2571  /* calculate F and the strips */
2572  for( i = 0; i < nbranchcands; ++i )
2573  {
2574  mastervar = branchcands[i];
2575  assert(GCGvarIsMaster(mastervar));
2576 
2577  if( GCGisMasterVarInBlock(mastervar, blocknr) )
2578  {
2579  mastervarValue = SCIPgetSolVal(masterscip, NULL, mastervar);
2580  if( !SCIPisFeasIntegral(masterscip, mastervarValue) )
2581  {
2582 
2583  SCIP_CALL( SCIPreallocMemoryArray(origscip, &F, (size_t)Fsize+1) );
2584 
2585  F[Fsize] = mastervar;
2586  ++Fsize;
2587  }
2588  }
2589  }
2590 
2591  /* old data to regard? */
2592  if( masterbranchcons != NULL && GCGconsMasterbranchGetBranchdata(masterbranchcons) != NULL )
2593  {
2594  /* calculate C */
2595  int c;
2596  int Csize = 0;
2597  SCIP_CONS* parentcons = masterbranchcons;
2598 
2599  while( parentcons != NULL && GCGconsMasterbranchGetBranchrule(parentcons) != NULL
2600  && strcmp(SCIPbranchruleGetName(GCGconsMasterbranchGetBranchrule(parentcons)), "generic") == 0)
2601  {
2602  branchdata = GCGconsMasterbranchGetBranchdata(parentcons);
2603  if( branchdata == NULL )
2604  {
2605  SCIPdebugMessage("branchdata is NULL\n");
2606  break;
2607  }
2608  if( branchdata->consS == NULL || branchdata->consSsize == 0 )
2609  break;
2610  if( branchdata->consblocknr != blocknr )
2611  {
2612  parentcons = GCGconsMasterbranchGetParentcons(parentcons);
2613  continue;
2614  }
2615 
2616  if( Csize == 0 )
2617  {
2618  assert(branchdata != NULL);
2619  assert(branchdata->consSsize > 0);
2620  Csize = 1;
2621  SCIP_CALL( SCIPallocMemoryArray(origscip, &C, Csize) );
2622  SCIP_CALL( SCIPallocMemoryArray(origscip, &sequencesizes, Csize) );
2623  assert(sequencesizes != NULL);
2624  C[0] = NULL;
2625  SCIP_CALL( SCIPallocMemoryArray(origscip, &(C[0]), branchdata->consSsize) );
2626  for( i = 0; i < branchdata->consSsize; ++i )
2627  {
2628  C[0][i] = branchdata->consS[i];
2629  }
2630  sequencesizes[0] = branchdata->consSsize;
2631  parentcons = GCGconsMasterbranchGetParentcons(parentcons);
2632  }
2633  else
2634  {
2635  /* S not yet in C ? */
2636  SCIP_Bool SinC = FALSE;
2637  for( c = 0; c < Csize && !SinC; ++c )
2638  {
2639  SinC = TRUE;
2640  assert(sequencesizes != NULL);
2641  if( branchdata->consSsize == sequencesizes[c] )
2642  {
2643  for( i = 0; i < branchdata->consSsize; ++i )
2644  {
2645  assert(C != NULL);
2646  if( branchdata->consS[i].component != C[c][i].component || branchdata->consS[i].sense != C[c][i].sense || !SCIPisEQ(origscip, branchdata->consS[i].bound, C[c][i].bound) )
2647  {
2648  SinC = FALSE;
2649  break;
2650  }
2651  }
2652  }
2653  else
2654  SinC = FALSE;
2655  }
2656  if( !SinC )
2657  {
2658  ++Csize;
2659  SCIP_CALL( SCIPreallocMemoryArray(origscip, &C, Csize) );
2660  SCIP_CALL( SCIPreallocMemoryArray(origscip, &sequencesizes, Csize) );
2661  assert(sequencesizes != NULL);
2662  C[Csize-1] = NULL;
2663  SCIP_CALL( SCIPallocMemoryArray(origscip, &(C[Csize-1]), branchdata->consSsize) ); /*lint !e866*/
2664 
2666  for( i = 0; i < branchdata->consSsize; ++i )
2667  {
2668  C[Csize-1][i] = branchdata->consS[i];
2669  }
2670  sequencesizes[Csize-1] = branchdata->consSsize;
2671  }
2672  parentcons = GCGconsMasterbranchGetParentcons(parentcons);
2673  }
2674  }
2675 
2676  if( C != NULL )
2677  {
2678  SCIPdebugMessage("Csize = %d\n", Csize);
2679 
2680  for( i = 0; i < Csize; ++i )
2681  {
2682  assert(sequencesizes != NULL);
2683 
2684  for( c = 0; c < sequencesizes[i]; ++c )
2685  {
2686  SCIPdebugMessage("C[%d][%d].component = %s\n", i, c, SCIPvarGetName(C[i][c].component) );
2687  SCIPdebugMessage("C[%d][%d].sense = %d\n", i, c, C[i][c].sense);
2688  SCIPdebugMessage("C[%d][%d].bound = %.6g\n", i, c, C[i][c].bound);
2689  }
2690  }
2691  /* SCIP_CALL( InducedLexicographicSort(scip, F, Fsize, C, Csize, sequencesizes) ); */
2692  SCIP_CALL( ChooseSeparateMethod(origscip, F, Fsize, &S, &Ssize, C, Csize, sequencesizes, blocknr, branchrule, result, checkedblocks,
2693  ncheckedblocks, checkedblockssortstrips, checkedblocksnsortstrips) );
2694  }
2695  else
2696  {
2697  SCIPdebugMessage("C == NULL\n");
2698  /* SCIP_CALL( InducedLexicographicSort( scip, F, Fsize, NULL, 0, NULL ) ); */
2699  SCIP_CALL( ChooseSeparateMethod( origscip, F, Fsize, &S, &Ssize, NULL, 0, NULL, blocknr, branchrule, result,
2700  checkedblocks, ncheckedblocks, checkedblockssortstrips, checkedblocksnsortstrips) );
2701  }
2702  if( sequencesizes != NULL )
2703  {
2704  assert(Csize > 0);
2705  SCIPfreeMemoryArray(origscip, &sequencesizes);
2706  }
2707  for( i = 0; i < Csize; ++i )
2708  {
2709  assert(C != NULL );
2710  SCIPfreeMemoryArrayNull(origscip, &(C[i]));
2711  }
2712  if( C != NULL )
2713  {
2714  assert( Csize > 0);
2715  SCIPfreeMemoryArrayNull(origscip, &C);
2716  }
2717  }
2718  else
2719  {
2720  SCIPdebugMessage("root node\n");
2721  /* SCIP_CALL( InducedLexicographicSort( scip, F, Fsize, NULL, 0, NULL ) ); */
2722  SCIP_CALL( ChooseSeparateMethod( origscip, F, Fsize, &S, &Ssize, NULL, 0, NULL, blocknr, branchrule, result, checkedblocks,
2723  ncheckedblocks, checkedblockssortstrips, checkedblocksnsortstrips) );
2724  }
2725 
2726  /* create the |S|+1 child nodes in the branch-and-bound tree */
2727  if( S != NULL && Ssize > 0 )
2728  {
2729  SCIP_CALL( createChildNodesGeneric(origscip, branchrule, S, Ssize, blocknr, masterbranchcons, result) );
2730  }
2731 
2732  SCIPdebugMessage("free F\n");
2733  SCIPfreeMemoryArray(origscip, &F);
2734  SCIPfreeMemoryArrayNull(origscip, &S);
2735 
2736  return SCIP_OKAY;
2737 }
2738 
2739 /* from branch_master */
2740 static
2742  SCIP* scip
2743  )
2744 {
2745  SCIP_CALL( SCIPincludeNodeselBfs(scip) );
2746  SCIP_CALL( SCIPincludeNodeselDfs(scip) );
2747  SCIP_CALL( SCIPincludeNodeselEstimate(scip) );
2748  SCIP_CALL( SCIPincludeNodeselHybridestim(scip) );
2749  SCIP_CALL( SCIPincludeNodeselRestartdfs(scip) );
2750  SCIP_CALL( SCIPincludeBranchruleAllfullstrong(scip) );
2751  SCIP_CALL( SCIPincludeBranchruleFullstrong(scip) );
2752  SCIP_CALL( SCIPincludeBranchruleInference(scip) );
2753  SCIP_CALL( SCIPincludeBranchruleMostinf(scip) );
2754  SCIP_CALL( SCIPincludeBranchruleLeastinf(scip) );
2755  SCIP_CALL( SCIPincludeBranchrulePscost(scip) );
2756  SCIP_CALL( SCIPincludeBranchruleRandom(scip) );
2757  SCIP_CALL( SCIPincludeBranchruleRelpscost(scip) );
2758  return SCIP_OKAY;
2759 }
2761 static
2762 SCIP_DECL_BRANCHCOPY(branchCopyGeneric)
2763 {
2764  assert(branchrule != NULL);
2765  assert(scip != NULL);
2766  SCIP_CALL( GCGincludeMasterCopyPlugins(scip) );
2767  return SCIP_OKAY;
2768 }
2769 
2771 static
2772 GCG_DECL_BRANCHACTIVEMASTER(branchActiveMasterGeneric)
2773 {
2774 
2775  SCIP_VAR** mastervars;
2776  int nmastervars;
2777  int i;
2778  int nvarsadded;
2779 
2780  assert(scip != NULL);
2781  assert(GCGisMaster(scip));
2782  assert(branchdata != NULL);
2783  assert(branchdata->mastercons != NULL);
2784 
2785  SCIPdebugMessage("branchActiveMasterGeneric: Block %d, Ssize %d\n", branchdata->consblocknr, branchdata->consSsize);
2786 
2787  if( branchdata->nvars >= SCIPgetNVars(scip) )
2788  return SCIP_OKAY;
2789 
2790  nmastervars = SCIPgetNVars(scip);
2791  mastervars = SCIPgetVars(scip);
2792  nvarsadded = 0;
2793 
2794  for( i = branchdata->nvars; i < nmastervars; ++i )
2795  {
2796  SCIP_Bool added = FALSE;
2797  assert(mastervars[i] != NULL);
2798  assert(GCGvarIsMaster(mastervars[i]));
2799 
2800  SCIP_CALL( addVarToMasterbranch(scip, mastervars[i], branchdata, &added) );
2801  if( added )
2802  ++nvarsadded;
2803 
2804  }
2805  SCIPdebugMessage("%d/%d vars added with lhs=%g\n", nvarsadded, nmastervars-branchdata->nvars, branchdata->lhs);
2806  branchdata->nvars = nmastervars;
2807 
2808  return SCIP_OKAY;
2809 }
2810 
2812 static
2813 GCG_DECL_BRANCHDEACTIVEMASTER(branchDeactiveMasterGeneric)
2814 {
2815  assert(scip != NULL);
2816  assert(GCGisMaster(scip));
2817  assert(branchdata != NULL);
2818  assert(branchdata->mastercons != NULL);
2819 
2820  SCIPdebugMessage("branchDeactiveMasterGeneric: Block %d, Ssize %d\n", branchdata->consblocknr, branchdata->consSsize);
2821 
2822  /* set number of variables since last call */
2823  branchdata->nvars = SCIPgetNVars(scip);
2824  return SCIP_OKAY;
2825 }
2826 
2827 
2828 
2830 static
2831 GCG_DECL_BRANCHPROPMASTER(branchPropMasterGeneric)
2832 {
2833  assert(scip != NULL);
2834  assert(branchdata != NULL);
2835  assert(branchdata->mastercons != NULL);
2836  assert(branchdata->consS != NULL);
2837 
2838  /* SCIPdebugMessage("branchPropMasterGeneric: Block %d ,Ssize %d)\n", branchdata->consblocknr, branchdata->consSsize); */
2839  *result = SCIP_DIDNOTFIND;
2840  return SCIP_OKAY;
2841 }
2842 
2844 static
2845 SCIP_DECL_BRANCHEXECLP(branchExeclpGeneric)
2846 { /*lint --e{715}*/
2847  SCIP* origscip;
2848  SCIP_Bool discretization;
2849 
2850  int* checkedblocks;
2851  int ncheckedblocks;
2852  GCG_STRIP*** checkedblockssortstrips;
2853  int* checkedblocksnsortstrips;
2854 
2855  assert(branchrule != NULL);
2856  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
2857  assert(scip != NULL);
2858  assert(result != NULL);
2859 
2860  origscip = GCGmasterGetOrigprob(scip);
2861  assert(origscip != NULL);
2862 
2863  SCIPdebugMessage("Execrel method of Vanderbecks generic branching\n");
2864 
2865  *result = SCIP_DIDNOTRUN;
2866 
2867  /* the branching scheme only works for the discretization approach */
2868  SCIP_CALL( SCIPgetBoolParam(origscip, "relaxing/gcg/discretization", &discretization) );
2869  if( !discretization )
2870  {
2871  SCIPdebugMessage("Generic branching only for discretization approach\n");
2872  return SCIP_OKAY;
2873  }
2874 
2875  if( GCGisMasterSetCovering(origscip) || GCGisMasterSetPartitioning(origscip) )
2876  {
2877  SCIPdebugMessage("Generic branching executed on a set covering or set partitioning problem\n");
2878  }
2879 
2880  if( GCGrelaxIsOrigSolFeasible(origscip) )
2881  {
2882  SCIPdebugMessage("node cut off, since origsol was feasible, solval = %f\n",
2883  SCIPgetSolOrigObj(origscip, GCGrelaxGetCurrentOrigSol(origscip)));
2884 
2885  *result = SCIP_DIDNOTFIND;
2886  return SCIP_OKAY;
2887  }
2888 
2889  *result = SCIP_BRANCHED;
2890 
2891  checkedblocks = NULL;
2892  ncheckedblocks = 0;
2893  checkedblockssortstrips = NULL;
2894  checkedblocksnsortstrips = NULL;
2895 
2896  SCIP_CALL( GCGbranchGenericInitbranch(scip, branchrule, result, &checkedblocks, &ncheckedblocks, &checkedblockssortstrips, &checkedblocksnsortstrips) );
2897 
2898  return SCIP_OKAY;
2899 }
2900 
2902 static
2903 SCIP_DECL_BRANCHEXECEXT(branchExecextGeneric)
2904 { /*lint --e{715}*/
2905  SCIPdebugMessage("Execext method of generic branching\n");
2906 
2907  *result = SCIP_DIDNOTRUN;
2908 
2909  return SCIP_OKAY;
2910 }
2911 
2916 static
2917 SCIP_DECL_BRANCHEXECPS(branchExecpsGeneric)
2918 { /*lint --e{715}*/
2919  assert(branchrule != NULL);
2920  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
2921  assert(scip != NULL);
2922  assert(result != NULL);
2923 
2924  SCIPdebugMessage("Execps method of Vanderbecks generic branching\n");
2925 
2926  if( SCIPisStopped(scip) )
2927  {
2928  SCIPwarningMessage(scip, "No branching could be created, solving process cannot be restarted...\n" );
2929 
2930  *result = SCIP_DIDNOTRUN;
2931  return SCIP_OKAY;
2932  }
2933  else
2934  {
2935  SCIPerrorMessage("This method is not implemented, aborting since we cannot recover!\n");
2936  SCIPdialogMessage(scip, NULL, "Due to numerical issues, the problem could not be solved.\n");
2937  SCIPdialogMessage(scip, NULL, "You can try to disable discretization and aggregation and resolve the problem.\n");
2938 
2939  *result = SCIP_DIDNOTRUN;
2940  return SCIP_ERROR;
2941  }
2942 }
2943 
2945 static
2946 SCIP_DECL_BRANCHINIT(branchInitGeneric)
2947 {
2948  SCIP* origscip;
2949 
2950  origscip = GCGmasterGetOrigprob(scip);
2951  assert(branchrule != NULL);
2952  assert(origscip != NULL);
2953 
2954  SCIPdebugMessage("Init method of Vanderbecks generic branching\n");
2955 
2956  SCIP_CALL( GCGrelaxIncludeBranchrule(origscip, branchrule, branchActiveMasterGeneric,
2957  branchDeactiveMasterGeneric, branchPropMasterGeneric, NULL, branchDataDeleteGeneric) );
2958 
2959  return SCIP_OKAY;
2960 }
2961 
2964  SCIP* scip
2965  )
2966 {
2967  SCIP_BRANCHRULEDATA* branchruledata;
2968  SCIP_BRANCHRULE* branchrule;
2969 
2970  /* create branching rule data */
2971  branchruledata = NULL;
2972 
2973  SCIPdebugMessage("Include method of Vanderbecks generic branching\n");
2974 
2975  /* include branching rule */
2976  SCIP_CALL( SCIPincludeBranchrule(scip, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
2977  BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchCopyGeneric,
2979  branchExitsolGeneric, branchExeclpGeneric, branchExecextGeneric, branchExecpsGeneric,
2980  branchruledata) );
2981 
2982  /* include event handler for adding generated mastervars to the branching constraints */
2983  SCIP_CALL( SCIPincludeEventhdlr(scip, EVENTHDLR_NAME, EVENTHDLR_DESC,
2984  NULL, NULL, NULL, NULL, eventInitsolGenericbranchvaradd, eventExitsolGenericbranchvaradd,
2985  NULL, eventExecGenericbranchvaradd,
2986  NULL) );
2987 
2988  branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME);
2989  assert(branchrule != NULL);
2990 
2991  SCIP_CALL( GCGconsIntegralorigAddBranchrule(scip, branchrule) );
2992 
2993  return SCIP_OKAY;
2994 }
2995 
2998  SCIP* scip,
2999  GCG_BRANCHDATA** branchdata
3000  )
3001 {
3002  assert(scip != NULL);
3003  assert(branchdata != NULL);
3004 
3005  SCIP_CALL( SCIPallocBlockMemory(scip, branchdata) );
3006  (*branchdata)->consS = NULL;
3007  (*branchdata)->consSsize = 0;
3008  (*branchdata)->sequencesizes = 0;
3009  (*branchdata)->C = NULL;
3010  (*branchdata)->mastercons = NULL;
3011  (*branchdata)->consblocknr = -2;
3012 
3013  return SCIP_OKAY;
3014 }
3015 
3018  GCG_BRANCHDATA* branchdata
3019  )
3020 {
3021  assert(branchdata != NULL);
3022  return branchdata->consS;
3023 }
3024 
3027  GCG_BRANCHDATA* branchdata
3028  )
3029 {
3030  assert(branchdata != NULL);
3031  return branchdata->consSsize;
3032 }
3033 
3036  GCG_BRANCHDATA* branchdata
3037  )
3038 {
3039  assert(branchdata != NULL);
3040  return branchdata->consblocknr;
3041 }
3042 
3045  GCG_BRANCHDATA* branchdata
3046  )
3047 {
3048  assert(branchdata != NULL);
3049  return branchdata->mastercons;
3050 }
3051 
3054  SCIP_BRANCHRULE* branchrule
3055 )
3056 {
3057  return (branchrule != NULL) && (strcmp(BRANCHRULE_NAME, SCIPbranchruleGetName(branchrule)) == 0);
3058 }
static SCIP_RETCODE addVarToMasterbranch(SCIP *scip, SCIP_VAR *mastervar, GCG_BRANCHDATA *branchdata, SCIP_Bool *added)
SCIP_RETCODE GCGconsIntegralorigAddBranchrule(SCIP *scip, SCIP_BRANCHRULE *branchrule)
static SCIP_DECL_BRANCHCOPY(branchCopyGeneric)
int GCGconsMasterbranchGetNChildconss(SCIP_CONS *cons)
SCIP_Bool GCGisMasterSetCovering(SCIP *scip)
Definition: relax_gcg.c:4131
int GCGgetBlockRepresentative(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:3941
SCIP_BRANCHRULE * GCGconsMasterbranchGetBranchrule(SCIP_CONS *cons)
GCG_COMPSEQUENCE * GCGbranchGenericBranchdataGetConsS(GCG_BRANCHDATA *branchdata)
GCG_COMPSENSE
static SCIP_Real GetMedian(SCIP *scip, SCIP_Real *array, int arraysize, SCIP_Real min)
static SCIP_RETCODE InitIndexSet(SCIP *scip, SCIP_VAR **F, int Fsize, SCIP_VAR ***IndexSet, int *IndexSetSize)
#define branchFreeGeneric
static GCG_DECL_BRANCHACTIVEMASTER(branchActiveMasterGeneric)
GCG interface methods.
static SCIP_RETCODE Separate(SCIP *scip, SCIP_VAR **F, int Fsize, SCIP_VAR **IndexSet, int IndexSetSize, GCG_COMPSEQUENCE *S, int Ssize, GCG_RECORD *record)
static SCIP_DECL_EVENTEXITSOL(eventExitsolGenericbranchvaradd)
static SCIP_RETCODE InducedLexicographicSort(SCIP *scip, GCG_STRIP **array, int arraysize, GCG_COMPSEQUENCE **C, int NBoundsequences, int *sequencesizes)
GCG_COMPSEQUENCE * consS
#define BRANCHRULE_MAXBOUNDDIST
static SCIP_RETCODE addToRecord(SCIP *scip, GCG_RECORD *record, GCG_COMPSEQUENCE *S, int Ssize)
static SCIP_RETCODE ChooseSeparateMethod(SCIP *scip, SCIP_VAR **F, int Fsize, GCG_COMPSEQUENCE **S, int *Ssize, GCG_COMPSEQUENCE **C, int Csize, int *CompSizes, int blocknr, SCIP_BRANCHRULE *branchrule, SCIP_RESULT *result, int **checkedblocks, int *ncheckedblocks, GCG_STRIP ****checkedblockssortstrips, int **checkedblocksnsortstrips)
SCIP_Bool GCGisMasterVarInBlock(SCIP_VAR *mastervar, int block)
Definition: gcgvar.c:984
int * sequencesizes
SCIP_CONS * GCGconsMasterbranchGetActiveCons(SCIP *scip)
#define branchInitsolGeneric
static GCG_DECL_BRANCHDATADELETE(branchDataDeleteGeneric)
static SCIP_DECL_BRANCHINIT(branchInitGeneric)
GCG_COMPSEQUENCE ** C
SCIP_Bool GCGisMasterSetPartitioning(SCIP *scip)
Definition: relax_gcg.c:4150
static SCIP_Bool pruneChildNodeByDominanceGeneric(SCIP *scip, SCIP_Real lhs, GCG_COMPSEQUENCE *childS, int childSsize, SCIP_CONS *masterbranchcons, int childBlocknr)
SCIP * GCGgetMasterprob(SCIP *scip)
Definition: relax_gcg.c:3838
constraint handler for the integrality constraint
SCIP_Bool GCGvarIsMaster(SCIP_VAR *var)
Definition: gcgvar.c:148
sorting functions, adapted from SCIP&#39;s sorttpl to include userdata
SCIP_SOL * GCGrelaxGetCurrentOrigSol(SCIP *scip)
Definition: relax_gcg.c:4093
SCIP_CONS * GCGconsMasterbranchGetParentcons(SCIP_CONS *cons)
GCG_COMPSEQUENCE ** C
int GCGgetNPricingprobs(SCIP *scip)
Definition: relax_gcg.c:3897
SCIP_CONS * GCGbranchGenericBranchdataGetMastercons(GCG_BRANCHDATA *branchdata)
static GCG_DECL_BRANCHDEACTIVEMASTER(branchDeactiveMasterGeneric)
SCIP_CONS * GCGconsMasterbranchGetChildcons(SCIP_CONS *cons, int childnr)
EXTERN void GCGsortPtr(void **ptrarray, GCG_DECL_SORTPTRCOMP((*ptrcomp)), void *userdata, int len)
static SCIP_RETCODE Explore(SCIP *scip, GCG_COMPSEQUENCE **C, int Csize, int *sequencesizes, int p, SCIP_VAR **F, int Fsize, SCIP_VAR **IndexSet, int IndexSetSize, GCG_COMPSEQUENCE **S, int *Ssize, GCG_RECORD *record)
SCIP_Bool GCGisBranchruleGeneric(SCIP_BRANCHRULE *branchrule)
#define BRANCHRULE_NAME
SCIP_CONS * mastercons
#define BRANCHRULE_MAXDEPTH
int GCGbranchGenericBranchdataGetConsblocknr(GCG_BRANCHDATA *branchdata)
static SCIP_DECL_BRANCHEXECLP(branchExeclpGeneric)
static SCIP_RETCODE initNodeBranchdata(SCIP *scip, GCG_BRANCHDATA **nodebranchdata, int blocknr)
SCIP_Bool GCGmasterVarIsArtificial(SCIP_VAR *var)
Definition: gcgvar.c:831
static GCG_DECL_SORTPTRCOMP(ptrcomp)
GCG relaxator.
static SCIP_Real getGeneratorEntry(SCIP_VAR *mastervar, SCIP_VAR *origvar)
GCG variable pricer.
static SCIP_RETCODE createBranchingCons(SCIP *scip, SCIP_NODE *node, GCG_BRANCHDATA *branchdata)
SCIP_Real * GCGmasterVarGetOrigvals(SCIP_VAR *var)
Definition: gcgvar.c:888
int GCGvarGetBlock(SCIP_VAR *var)
Definition: gcgvar.c:936
static SCIP_DECL_BRANCHEXECEXT(branchExecextGeneric)
#define EVENTHDLR_DESC
int * sequencesizes
static SCIP_RETCODE ChoseS(SCIP *scip, GCG_RECORD **record, GCG_COMPSEQUENCE **S, int *Ssize)
static SCIP_DECL_BRANCHEXECPS(branchExecpsGeneric)
static SCIP_RETCODE LexicographicSort(SCIP *scip, GCG_STRIP **array, int arraysize)
static SCIP_RETCODE createDirectBranchingCons(SCIP *scip, SCIP_NODE *node, GCG_BRANCHDATA *branchdata)
SCIP * GCGmasterGetOrigprob(SCIP *scip)
SCIP_Bool GCGrelaxIsOrigSolFeasible(SCIP *scip)
Definition: relax_gcg.c:4112
#define branchExitsolGeneric
static SCIP_RETCODE partition(SCIP *scip, SCIP_VAR **J, int *Jsize, SCIP_Longint *priority, SCIP_VAR **F, int Fsize, SCIP_VAR **origvar, SCIP_Real *median)
static SCIP_DECL_EVENTINITSOL(eventInitsolGenericbranchvaradd)
SCIP_VAR * mastervar
SCIP_RETCODE GCGbranchGenericInitbranch(SCIP *masterscip, SCIP_BRANCHRULE *branchrule, SCIP_RESULT *result, int **checkedblocks, int *ncheckedblocks, GCG_STRIP ****checkedblockssortstrips, int **checkedblocksnsortstrips)
type definitions for branching rules in GCG projects
SCIP_RETCODE GCGbranchGenericCreateBranchdata(SCIP *scip, GCG_BRANCHDATA **branchdata)
static GCG_DECL_BRANCHPROPMASTER(branchPropMasterGeneric)
SCIP_Bool GCGisMaster(SCIP *scip)
Definition: misc.c:650
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)
int GCGbranchGenericBranchdataGetConsSsize(GCG_BRANCHDATA *branchdata)
SCIP_CONS * cons
Definition: branch_orig.c:74
constraint handler for storing the branching decisions at each node of the tree
static SCIP_Bool checkchildconsS(SCIP *scip, SCIP_Real lhs, GCG_COMPSEQUENCE *childS, int childSsize, SCIP_CONS *parentcons, int childBlocknr)
GCG_BRANCHDATA * GCGconsMasterbranchGetBranchdata(SCIP_CONS *cons)
static SCIP_DECL_EVENTEXEC(eventExecGenericbranchvaradd)
int GCGmasterVarGetNOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:846
static SCIP_RETCODE createChildNodesGeneric(SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_COMPSEQUENCE *S, int Ssize, int blocknr, SCIP_CONS *masterbranchcons, SCIP_RESULT *result)
static int computeNewSequence(int Csize, int p, SCIP_VAR *origvar, int *sequencesizes, GCG_COMPSEQUENCE **C, GCG_COMPSEQUENCE **CopyC, int *newsequencesizes, GCG_COMPSENSE sense)
#define branchExitGeneric
SCIP_VAR * origvar
Definition: branch_orig.c:68
SCIP_RETCODE GCGrelaxIncludeBranchrule(SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_DECL_BRANCHACTIVEMASTER((*branchactivemaster)), GCG_DECL_BRANCHDEACTIVEMASTER((*branchdeactivemaster)), GCG_DECL_BRANCHPROPMASTER((*branchpropmaster)), GCG_DECL_BRANCHMASTERSOLVED((*branchmastersolved)), GCG_DECL_BRANCHDATADELETE((*branchdatadelete)))
Definition: relax_gcg.c:3451
SCIP_RETCODE GCGpricerExistRays(SCIP *scip, SCIP_Bool *exist)
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
#define BRANCHRULE_PRIORITY
SCIP_RETCODE SCIPincludeBranchruleGeneric(SCIP *scip)
GCG_COMPSEQUENCE ** record
static double computeAlpha(SCIP *scip, int Fsize, GCG_COMPSENSE isense, double ivalue, SCIP_VAR *origvar, SCIP_VAR **F)
SCIP_VAR ** GCGoriginalVarGetMastervars(SCIP_VAR *var)
Definition: gcgvar.c:561
static SCIP_RETCODE branchDirectlyOnMastervar(SCIP *scip, SCIP_VAR *mastervar, SCIP_BRANCHRULE *branchrule)
#define EVENTHDLR_NAME
SCIP * scip
#define BRANCHRULE_DESC
SCIP_Bool GCGmasterVarIsLinking(SCIP_VAR *var)
Definition: gcgvar.c:793
static int ILOcomp(SCIP *scip, SCIP_VAR *mastervar1, SCIP_VAR *mastervar2, GCG_COMPSEQUENCE **C, int NBoundsequences, int *sequencesizes, int p)
static SCIP_DECL_SORTPTRCOMP(ptrilocomp)
static SCIP_RETCODE GCGincludeMasterCopyPlugins(SCIP *scip)
int GCGgetNIdenticalBlocks(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:3966