Scippy

GCG

Branch-and-Price & Column Generation for Everyone

branch_orig.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* GCG --- Generic Column Generation */
5 /* a Dantzig-Wolfe decomposition based extension */
6 /* of the branch-cut-and-price framework */
7 /* SCIP --- Solving Constraint Integer Programs */
8 /* */
9 /* Copyright (C) 2010-2021 Operations Research, RWTH Aachen University */
10 /* Zuse Institute Berlin (ZIB) */
11 /* */
12 /* This program is free software; you can redistribute it and/or */
13 /* modify it under the terms of the GNU Lesser General Public License */
14 /* as published by the Free Software Foundation; either version 3 */
15 /* of the License, or (at your option) any later version. */
16 /* */
17 /* This program is distributed in the hope that it will be useful, */
18 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
19 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
20 /* GNU Lesser General Public License for more details. */
21 /* */
22 /* You should have received a copy of the GNU Lesser General Public License */
23 /* along with this program; if not, write to the Free Software */
24 /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
25 /* */
26 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
27 
28 /**@file branch_orig.c
29  * @brief branching rule for the original problem in GCG
30  * @author Gerald Gamrath
31  * @author Marcel Schmickerath
32  * @author Christian Puchert
33  * @author Jonas Witt
34  * @author Oliver Gaul
35  */
36 
37 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
38 /*#define SCIP_DEBUG*/
39 #include <assert.h>
40 #include <string.h>
41 
42 #include "branch_orig.h"
43 #include "gcg.h"
44 #include "branch_relpsprob.h"
45 #include "branch_bpstrong.h"
46 #include "cons_integralorig.h"
47 #include "cons_masterbranch.h"
48 #include "cons_origbranch.h"
49 #include "relax_gcg.h"
50 #include "pricer_gcg.h"
51 #include "type_branchgcg.h"
52 
53 #include "scip/cons_linear.h"
54 
55 
56 #define BRANCHRULE_NAME "orig"
57 #define BRANCHRULE_DESC "branching for the original program in generic column generation"
58 #define BRANCHRULE_PRIORITY 100
59 #define BRANCHRULE_MAXDEPTH -1
60 #define BRANCHRULE_MAXBOUNDDIST 1.0
61 
62 #define DEFAULT_ENFORCEBYCONS FALSE
63 #define DEFAULT_USEPSEUDO TRUE
64 #define DEFAULT_MOSTFRAC FALSE
65 #define DEFAULT_USERANDOM FALSE
66 #define DEFAULT_USEPSSTRONG FALSE
67 
68 /* strong branching */
69 #define DEFAULT_USESTRONG FALSE
70 
71 #define DEFAULT_MINPHASE0OUTCANDS 10
72 #define DEFAULT_MAXPHASE0OUTCANDS 50
73 #define DEFAULT_MAXPHASE0OUTCANDSFRAC 0.7
74 #define DEFAULT_PHASE1GAPWEIGHT 0.25
75 
76 #define DEFAULT_MINPHASE1OUTCANDS 3
77 #define DEFAULT_MAXPHASE1OUTCANDS 20
78 #define DEFAULT_MAXPHASE1OUTCANDSFRAC 0.7
79 #define DEFAULT_PHASE2GAPWEIGHT 1
80 /**/
81 
82 
83 /** branching rule data */
85 {
86  SCIP_Bool enforcebycons; /**< should bounds on variables be enforced by constraints(TRUE) or by
87  * bounds(FALSE) */
88  SCIP_Bool usepseudocosts; /**< should pseudocosts be used to determine the variable on which the
89  * branching is performed? */
90  SCIP_Bool mostfrac; /**< should branching be performed on the most fractional variable?
91  * (only if usepseudocosts = FALSE) */
92  SCIP_Bool userandom; /**< should the variable on which the branching is performed be
93  * selected randomly? (only if usepseudocosts = mostfrac = FALSE) */
94  SCIP_Bool usepsstrong; /**< should strong branching with propagation be used to determine the
95  * variable on which the branching is performed?
96  * (only if usepseudocosts = mostfrac = random = FALSE)*/
97  SCIP_Bool usestrong; /**< should strong branching be used to determine the variable on which
98  * the branching is performed? */
99 };
100 
101 /** branching data for branching decisions */
102 struct GCG_BranchData
103 {
104  SCIP_VAR* origvar; /**< original variable on which the branching is done */
105  GCG_BOUNDTYPE boundtype; /**< type of the new bound of original variable */
106  SCIP_Real newbound; /**< new lower/upper bound of the original variable */
107  SCIP_Real oldbound; /**< old lower/upper bound of the pricing variable */
108  SCIP_Real oldvalue; /**< old value of the original variable */
109  SCIP_Real olddualbound; /**< dual bound before the branching was performed */
110  SCIP_CONS* cons; /**< constraint that enforces the branching restriction in the original
111  * problem, or NULL if this is done by variable bounds */
112 };
113 
114 /* returns TRUE iff
115  * iter = 0 and branchcand is an integer variable belonging to a unique block with fractional value, or
116  * iter = 1 and branchcand is an integer variable that belongs to no block but was directly transferred to the
117  * master problem and which has a fractional value in the current solution
118  */
119 static
121  SCIP* scip,
122  SCIP_VAR* branchcand,
123  int iter
124 )
125 {
126  assert(GCGvarIsOriginal(branchcand));
127  /* continue if variable belongs to a block in second iteration*/
128  if (iter == 0)
129  {
130  /* variable belongs to no block */
131  if (GCGvarGetBlock(branchcand) == -1)
132  return FALSE;
133 
134  /* block is not unique (non-linking variables) */
135  if (!GCGoriginalVarIsLinking(branchcand) && GCGgetNIdenticalBlocks(scip, GCGvarGetBlock(branchcand)) != 1)
136  return FALSE;
137 
138  /* check that blocks of linking variable are unique */
139  if (GCGoriginalVarIsLinking(branchcand))
140  {
141  int nvarblocks;
142  int *varblocks;
143  SCIP_Bool unique;
144  int j;
145 
146  nvarblocks = GCGlinkingVarGetNBlocks(branchcand);
147  SCIP_CALL(SCIPallocBufferArray(scip, &varblocks, nvarblocks));
148  SCIP_CALL(GCGlinkingVarGetBlocks(branchcand, nvarblocks, varblocks));
149 
150  unique = TRUE;
151  for (j = 0; j < nvarblocks; ++j)
152  if (GCGgetNIdenticalBlocks(scip, varblocks[j]) != 1)
153  unique = FALSE;
154 
155  SCIPfreeBufferArray(scip, &varblocks);
156 
157  if (!unique)
158  return FALSE;
159  }
160  /* candidate is valid in first iteration */
161  return TRUE;
162 
163  }
164  else /* iter == 1 */
165  {
166  if (GCGvarGetBlock(branchcand) != -1)
167  return FALSE;
168 
169  /* candidate is valid in second iteration */
170  return TRUE;
171  }
172  return FALSE;
173 }
174 
175 /** branches on a integer variable x
176  * if solution value x' is fractional, two child nodes will be created
177  * (x <= floor(x'), x >= ceil(x')),
178  * if solution value is integral, the bounds of x are finite, then two child nodes will be created
179  * (x <= x", x >= x"+1 with x" = floor((lb + ub)/2)),
180  * otherwise (up to) three child nodes will be created
181  * (x <= x'-1, x == x', x >= x'+1)
182  * if solution value is equal to one of the bounds and the other bound is infinite, only two child nodes
183  * will be created (the third one would be infeasible anyway)
184  */
185 static
186 SCIP_RETCODE branchVar(
187  SCIP* scip, /**< SCIP data structure */
188  SCIP_BRANCHRULE* branchrule, /**< pointer to the original variable branching rule */
189  SCIP_VAR* branchvar, /**< variable to branch on */
190  SCIP_Real solval, /**< value of the variable in the current solution */
191  SCIP_Bool upinf, /**< have we seen during strong branching that the upbranch is
192  * infeasible? */
193  SCIP_Bool downinf /**< have we seen during strong branching that the downbranch is
194  * infeasible? */
195  )
196 {
197  /* data for b&b child creation */
198  SCIP* masterscip;
199  SCIP_Real downub;
200  SCIP_Real fixval;
201  SCIP_Real uplb;
202 
203  SCIP_BRANCHRULEDATA* branchruledata;
204 
205  branchruledata = SCIPbranchruleGetData(branchrule);
206  assert(branchruledata != NULL);
207 
208  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
209 
210  assert(scip != NULL);
211  assert(branchrule != NULL);
212  assert(branchvar != NULL);
213 
214  /* get master problem */
215  masterscip = GCGgetMasterprob(scip);
216  assert(masterscip != NULL);
217 
218  downub = SCIP_INVALID;
219  fixval = SCIP_INVALID;
220  uplb = SCIP_INVALID;
221 
222  if( SCIPisFeasIntegral(scip, solval) )
223  {
224  SCIP_Real lb;
225  SCIP_Real ub;
226 
227  lb = SCIPvarGetLbLocal(branchvar);
228  ub = SCIPvarGetUbLocal(branchvar);
229 
230  /* if there was no explicit value given for branching, the variable has a finite domain and the current LP/pseudo
231  * solution is one of the bounds, we branch in the center of the domain */
232  if( !SCIPisInfinity(scip, -lb) && !SCIPisInfinity(scip, ub) )
233  {
234  SCIP_Real center;
235 
236  /* create child nodes with x <= x", and x >= x"+1 with x" = floor((lb + ub)/2);
237  * if x" is integral, make the interval smaller in the child in which the current solution x'
238  * is still feasible
239  */
240  center = (ub + lb) / 2.0;
241  if( solval <= center )
242  {
243  downub = SCIPfeasFloor(scip, center);
244  uplb = downub + 1.0;
245  }
246  else
247  {
248  uplb = SCIPfeasCeil(scip, center);
249  downub = uplb - 1.0;
250  }
251  }
252  else
253  {
254  /* create child nodes with x <= x'-1, x = x', and x >= x'+1 */
255  assert(SCIPisEQ(scip, SCIPfeasCeil(scip, solval), SCIPfeasFloor(scip, solval)));
256 
257  fixval = solval;
258 
259  /* create child node with x <= x'-1, if this would be feasible */
260  if( SCIPisFeasGE(scip, fixval-1.0, lb) )
261  downub = fixval - 1.0;
262 
263  /* create child node with x >= x'+1, if this would be feasible */
264  if( SCIPisFeasLE(scip, fixval+1.0, ub) )
265  uplb = fixval + 1.0;
266  }
267  SCIPdebugMessage("integral branch on variable <%s> with value %g, priority %d (current lower bound: %g)\n",
268  SCIPvarGetName(branchvar), solval, SCIPvarGetBranchPriority(branchvar),
269  SCIPgetLocalLowerbound(GCGgetMasterprob(scip)));
270  }
271  else
272  {
273  /* create child nodes with x <= floor(x'), and x >= ceil(x') */
274  downub = SCIPfeasFloor(scip, solval);
275  uplb = downub + 1.0;
276  assert( SCIPisEQ(scip, SCIPfeasCeil(scip, solval), uplb) );
277  }
278 
279  if( uplb != SCIP_INVALID && !upinf ) /*lint !e777*/
280  {
281  SCIP_CONS* cons;
282  SCIP_NODE* child;
283  SCIP_CONS** origbranchconss;
284  GCG_BRANCHDATA* branchdata;
285  char name[SCIP_MAXSTRLEN];
286 
287  int norigbranchconss;
288  int maxorigbranchconss;
289 
290  origbranchconss = NULL;
291  norigbranchconss = 0;
292  maxorigbranchconss = 0;
293 
294  /* create child node x >= uplb */
295  SCIP_CALL( SCIPcreateChild(masterscip, &child, 0.0, SCIPgetLocalTransEstimate(masterscip)) );
296 
297  SCIP_CALL( SCIPallocBlockMemory(scip, &branchdata) );
298 
299  branchdata->origvar = branchvar;
300  branchdata->oldvalue = solval;
301  branchdata->olddualbound = SCIPgetLocalLowerbound(masterscip);
302  branchdata->boundtype = GCG_BOUNDTYPE_LOWER;
303  branchdata->newbound = uplb;
304  branchdata->oldbound = SCIPvarGetLbLocal(branchvar);
305 
306  SCIPdebugMessage(" -> creating child: <%s> >= %g\n",
307  SCIPvarGetName(branchvar), uplb);
308 
309  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s %s %f", SCIPvarGetName(branchdata->origvar),
310  ">=", branchdata->newbound);
311 
312  if( branchruledata->enforcebycons )
313  {
314  /* enforce new bounds by linear constraints */
315  SCIP_CONS* consup;
316 
317  SCIPdebugMessage("enforced by cons\n");
318 
319  norigbranchconss = 1;
320  maxorigbranchconss = SCIPcalcMemGrowSize(scip, 1);
321  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &origbranchconss, maxorigbranchconss) );
322 
323  /* create corresponding constraints */
324  SCIP_CALL( SCIPcreateConsLinear(scip, &consup, name, 0, NULL, NULL,
325  SCIPceil(scip, solval), SCIPinfinity(scip),
326  TRUE, TRUE, TRUE, TRUE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE) );
327 
328  SCIP_CALL( SCIPaddCoefLinear(scip, consup, branchvar, 1.0) );
329 
330  origbranchconss[0] = consup;
331  branchdata->cons = consup;
332  }
333  else
334  branchdata->cons = NULL;
335 
336  /* create and add the masterbranch constraint */
337  SCIP_CALL( GCGcreateConsMasterbranch(masterscip, &cons, name, child,
338  GCGconsMasterbranchGetActiveCons(masterscip), branchrule, branchdata, origbranchconss, norigbranchconss,
339  maxorigbranchconss) );
340  SCIP_CALL( SCIPaddConsNode(masterscip, child, cons, NULL) );
341  }
342 
343  if( downub != SCIP_INVALID && !downinf ) /*lint !e777*/
344  {
345  SCIP_CONS* cons;
346  SCIP_NODE* child;
347  SCIP_CONS** origbranchconss;
348  GCG_BRANCHDATA* branchdata;
349  char name[SCIP_MAXSTRLEN];
350 
351  int norigbranchconss;
352  int maxorigbranchconss;
353 
354  origbranchconss = NULL;
355  norigbranchconss = 0;
356  maxorigbranchconss = 0;
357 
358  /* create child node x <= downub */
359  SCIP_CALL( SCIPcreateChild(masterscip, &child, 0.0, SCIPgetLocalTransEstimate(masterscip)) );
360 
361  SCIP_CALL( SCIPallocBlockMemory(scip, &branchdata) );
362 
363  branchdata->origvar = branchvar;
364  branchdata->oldvalue = solval;
365  branchdata->olddualbound = SCIPgetLocalLowerbound(masterscip);
366  branchdata->boundtype = GCG_BOUNDTYPE_UPPER;
367  branchdata->newbound = downub;
368  branchdata->oldbound = SCIPvarGetUbLocal(branchvar);
369 
370  SCIPdebugMessage(" -> creating child: <%s> <= %g\n",
371  SCIPvarGetName(branchvar), downub);
372 
373  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s %s %f", SCIPvarGetName(branchdata->origvar),
374  "<=", branchdata->newbound);
375 
376  /* enforce branching decision by a constraint rather than by bound changes */
377  if( branchruledata->enforcebycons )
378  {
379  /* enforce new bounds by linear constraints */
380  SCIP_CONS* consdown;
381 
382  norigbranchconss = 1;
383  maxorigbranchconss = SCIPcalcMemGrowSize(scip, 1);
384  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &origbranchconss, maxorigbranchconss) );
385 
386  /* create corresponding constraints */
387  SCIP_CALL( SCIPcreateConsLinear(scip, &consdown, name, 0, NULL, NULL,
388  -1.0 * SCIPinfinity(scip), SCIPfloor(scip, solval),
389  TRUE, TRUE, TRUE, TRUE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE) );
390  SCIP_CALL( SCIPaddCoefLinear(scip, consdown, branchvar, 1.0) );
391 
392  origbranchconss[0] = consdown;
393  branchdata->cons = consdown;
394  }
395  else
396  branchdata->cons = NULL;
397 
398  /* create and add the masterbranch constraint */
399  SCIP_CALL( GCGcreateConsMasterbranch(masterscip, &cons, name, child,
400  GCGconsMasterbranchGetActiveCons(masterscip), branchrule, branchdata, origbranchconss, norigbranchconss,
401  maxorigbranchconss) );
402  SCIP_CALL( SCIPaddConsNode(masterscip, child, cons, NULL) );
403  }
404 
405  if( fixval != SCIP_INVALID ) /*lint !e777*/
406  {
407  SCIP_CONS* cons;
408  SCIP_NODE* child;
409  SCIP_CONS** origbranchconss;
410  GCG_BRANCHDATA* branchdata;
411  char name[SCIP_MAXSTRLEN];
412 
413  int norigbranchconss;
414  int maxorigbranchconss;
415 
416  origbranchconss = NULL;
417  norigbranchconss = 0;
418  maxorigbranchconss = 0;
419 
420  /* create child node x = fixval */
421  SCIP_CALL( SCIPcreateChild(masterscip, &child, 0.0, SCIPgetLocalTransEstimate(masterscip)) );
422 
423  SCIP_CALL( SCIPallocBlockMemory(scip, &branchdata) );
424 
425  branchdata->origvar = branchvar;
426  branchdata->oldvalue = solval;
427  branchdata->olddualbound = SCIPgetLocalLowerbound(masterscip);
428  branchdata->boundtype = GCG_BOUNDTYPE_FIXED;
429  branchdata->newbound = fixval;
430  branchdata->oldbound = SCIPvarGetUbLocal(branchvar);
431 
432  SCIPdebugMessage(" -> creating child: <%s> == %g\n",
433  SCIPvarGetName(branchvar), fixval);
434 
435  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s %s %f", SCIPvarGetName(branchdata->origvar),
436  "==", branchdata->newbound);
437 
438  /* enforce branching decision by a constraint rather than by bound changes */
439  if( branchruledata->enforcebycons )
440  {
441  /* enforce new bounds by linear constraints */
442  SCIP_CONS* consfix;
443 
444  norigbranchconss = 1;
445  maxorigbranchconss = SCIPcalcMemGrowSize(scip, 1);
446  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &origbranchconss, maxorigbranchconss) );
447 
448  /* create corresponding constraints */
449  SCIP_CALL( SCIPcreateConsLinear(scip, &consfix, name, 0, NULL, NULL,
450  fixval, fixval, TRUE, TRUE, TRUE, TRUE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE) );
451  SCIP_CALL( SCIPaddCoefLinear(scip, consfix, branchvar, 1.0) );
452 
453  origbranchconss[0] = consfix;
454  branchdata->cons = consfix;
455  }
456  else
457  branchdata->cons = NULL;
458 
459  /* create and add the masterbranch constraint */
460  SCIP_CALL( GCGcreateConsMasterbranch(masterscip, &cons, name, child,
461  GCGconsMasterbranchGetActiveCons(masterscip), branchrule, branchdata, origbranchconss, norigbranchconss,
462  maxorigbranchconss) );
463  SCIP_CALL( SCIPaddConsNode(masterscip, child, cons, NULL) );
464  }
465 
466  return SCIP_OKAY;
467 }
468 
469 /* Evaluates the given variable based on a score function of choice. Higher scores are given to better
470  * variables.
471  */
472 static SCIP_Real score_function(
473  SCIP *scip,
474  SCIP_BRANCHRULE* branchrule, /* pointer to the original variable branching rule */
475  SCIP_VAR *var, /* var to be scored */
476  SCIP_Real solval, /* the var's current solution value */
477  SCIP_Real *score /* stores the computed score */
478 )
479 {
480  SCIP_BRANCHRULEDATA* branchruledata;
481  branchruledata = SCIPbranchruleGetData(branchrule);
482  assert(branchruledata != NULL);
483 
484  /* define score functions and calculate score for all variables for sorting dependent on used heuristic */
485  if( branchruledata->usepseudocosts )
486  {
487  *score = SCIPgetVarPseudocostScore(scip, var, solval);
488  }
489  else
490  {
491  if( !branchruledata->mostfrac )
492  return 1;
493 
494  *score = solval - SCIPfloor(scip, solval);
495  *score = MIN(*score, 1.0 - *score);
496  }
497 
498  return SCIP_OKAY;
499 }
500 
501 /** branching method for relaxation solutions */
502 static
503 SCIP_RETCODE branchExtern(
504  SCIP* scip, /**< SCIP data structure */
505  SCIP_BRANCHRULE* branchrule, /**< pointer to the original variable branching rule */
506  SCIP_RESULT* result /**< pointer to store the result of the branching call */
507  )
508 {
509  SCIP* masterscip;
510  SCIP_BRANCHRULEDATA* branchruledata;
511 
512  /* branching candidates */
513  SCIP_VAR** branchcands;
514  SCIP_Real* branchcandssol;
515  int nbranchcands;
516  int npriobranchcands;
517 
518  SCIP_Bool upinf;
519  SCIP_Bool downinf;
520 
521  /* values for choosing the variable to branch on */
522  SCIP_VAR* branchvar;
523  SCIP_Real solval;
524 
525  SCIP_Real maxscore;
526  SCIP_Real score;
527 
528  assert(branchrule != NULL);
529  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
530  assert(scip != NULL);
531  assert(result != NULL);
532  assert(SCIPisRelaxSolValid(scip));
533 
534  branchruledata = SCIPbranchruleGetData(branchrule);
535  assert(branchruledata != NULL);
536 
537  *result = SCIP_DIDNOTRUN;
538 
539  /* get master problem */
540  masterscip = GCGgetMasterprob(scip);
541  assert(masterscip != NULL);
542 
543  /* get the branching candidates */
544  SCIP_CALL( SCIPgetExternBranchCands(scip, &branchcands, &branchcandssol, NULL, &nbranchcands,
545  &npriobranchcands, NULL, NULL, NULL) );
546 
547  branchvar = NULL;
548  solval = 0.0;
549 
550  upinf = FALSE;
551  downinf = FALSE;
552 
553  maxscore = -1.0;
554 
555  if( !branchruledata->usestrong )
556  {
557  if( branchruledata->usepseudocosts || branchruledata->mostfrac || branchruledata->userandom )
558  {
559  /* iter = 0: integer variables belonging to a unique block with fractional value,
560  * iter = 1: we did not find enough variables to branch on so far, so we look for integer variables that
561  * belong to no block
562  * but were directly transferred to the master problem and which have a fractional value in the current
563  * solution
564  */
565  for( int iter = 0; iter <= 1 && branchvar == NULL; iter++ )
566  {
567  for( int i = 0; i < npriobranchcands; i++ )
568  {
569  if( !getUniqueBlockFlagForIter(scip, branchcands[i], iter) )
570  continue;
571 
572  if( !branchruledata->userandom )
573  {
574  SCIP_CALL( score_function(scip, branchrule, branchcands[i], branchcandssol[i], &score) );
575 
576  if( score > maxscore )
577  {
578  maxscore = score;
579  branchvar = branchcands[i];
580  solval = branchcandssol[i];
581  }
582  }
583  else
584  {
585  branchvar = branchcands[i];
586  solval = branchcandssol[i];
587  break;
588  }
589  }
590  }
591  }
592  else if( branchruledata->usepsstrong )
593  {
594  SCIP_CALL( SCIPgetRelpsprobBranchVar(masterscip, branchcands, branchcandssol, npriobranchcands,
595  npriobranchcands, result, &branchvar) );
596  assert(branchvar != NULL || *result == SCIP_CUTOFF);
597  assert(*result == SCIP_DIDNOTRUN || *result == SCIP_CUTOFF);
598 
599  if( *result == SCIP_CUTOFF )
600  return SCIP_OKAY;
601 
602  solval = SCIPgetRelaxSolVal(scip, branchvar);
603  }
604 
605 
606  }
607  else
608  {
609  SCIP_CALL( GCGbranchSelectCandidateStrongBranchingOrig(scip, branchrule, &branchvar, &upinf, &downinf, result,
610  &branchruledata->usestrong) );
611  }
612 
613  if( upinf && downinf )
614  return SCIP_OKAY;
615 
616  if( branchvar == NULL )
617  {
618  SCIPdebugMessage("Original branching rule could not find a variable to branch on!\n");
619  return SCIP_OKAY;
620  }
621 
622  assert(!(upinf && downinf));
623 
624  SCIPdebugMessage("Original branching rule selected variable %s%s\n",
625  SCIPvarGetName(branchvar), (upinf || downinf)? ", which is infeasible in one direction" : "");
626 
627  SCIP_CALL( branchVar(scip, branchrule, branchvar, solval, upinf, downinf) );
628  *result = SCIP_BRANCHED;
629 
630  return SCIP_OKAY;
631 }
632 
633 /*
634  * Callback methods for enforcing branching constraints
635  */
636 
637 #define branchDeactiveMasterOrig NULL
638 #define branchPropMasterOrig NULL
639 
640 /** callback activation method */
641 static
642 GCG_DECL_BRANCHACTIVEMASTER(branchActiveMasterOrig)
643 {
644  SCIP* origscip;
645  SCIP_CONS* mastercons;
646 
647  assert(scip != NULL);
648  assert(branchdata != NULL);
649 
650  /* branching restrictions are enforced by variable bounds, this is done automatically, so we can abort here */
651  if( branchdata->cons == NULL )
652  return SCIP_OKAY;
653 
654  assert(branchdata->origvar != NULL);
655 
656  origscip = GCGmasterGetOrigprob(scip);
657  assert(origscip != NULL);
658 
659  SCIPdebugMessage("branchActiveMasterOrig: %s %s %f\n", SCIPvarGetName(branchdata->origvar),
660  ( branchdata->boundtype == GCG_BOUNDTYPE_LOWER ?
661  ">=" : branchdata->boundtype == GCG_BOUNDTYPE_UPPER ? "<=" : "==" ), branchdata->newbound);
662 
663  /* transform constraint to the master variable space */
664  SCIP_CALL( GCGrelaxTransOrigToMasterCons(origscip, branchdata->cons, &mastercons) );
665  assert(mastercons != NULL);
666 
667  /* add constraint to the master problem */
668  SCIP_CALL( SCIPaddConsNode(scip, SCIPgetCurrentNode(scip), mastercons, NULL) );
669 
670  /* constraint was added locally to the node where it is needed, so we do not need to care about this
671  * at the next activation of the node and can set the constraint pointer to NULL */
672  SCIP_CALL( SCIPreleaseCons(scip, &branchdata->cons) );
673  branchdata->cons = NULL;
674 
675  return SCIP_OKAY;
676 }
677 
678 /** callback solved method */
679 static
680 GCG_DECL_BRANCHMASTERSOLVED(branchMasterSolvedOrig)
681 {
682  assert(scip != NULL);
683  assert(GCGisOriginal(scip));
684  assert(branchdata != NULL);
685  assert(branchdata->origvar != NULL);
686 
687  SCIPdebugMessage("branchMasterSolvedOrig: %s %s %f\n", SCIPvarGetName(branchdata->origvar),
688  ( branchdata->boundtype == GCG_BOUNDTYPE_LOWER ?
689  ">=" : branchdata->boundtype == GCG_BOUNDTYPE_UPPER ? "<=" : "==" ), branchdata->newbound);
690 
691  if( !SCIPisInfinity(scip, newlowerbound) && SCIPgetStage(GCGgetMasterprob(scip)) == SCIP_STAGE_SOLVING
692  && SCIPisRelaxSolValid(GCGgetMasterprob(scip)) )
693  {
694  SCIP_CALL( SCIPupdateVarPseudocost(scip, branchdata->origvar,
695  SCIPgetRelaxSolVal(scip, branchdata->origvar) - branchdata->oldvalue,
696  newlowerbound - branchdata->olddualbound, 1.0) );
697  }
698 
699  return SCIP_OKAY;
700 }
701 
702 /** callback deletion method for branching data */
703 static
704 GCG_DECL_BRANCHDATADELETE(branchDataDeleteOrig)
705 {
706  assert(scip != NULL);
707  assert(branchdata != NULL);
708 
709  if( *branchdata == NULL )
710  return SCIP_OKAY;
711 
712  SCIPdebugMessage("branchDataDeleteOrig: %s %s %f\n", SCIPvarGetName((*branchdata)->origvar),
713  ( (*branchdata)->boundtype == GCG_BOUNDTYPE_LOWER ?
714  ">=" : (*branchdata)->boundtype == GCG_BOUNDTYPE_UPPER ? "<=" : "==" ),
715  (*branchdata)->newbound);
716 
717  /* release constraint */
718  if( (*branchdata)->cons != NULL )
719  {
720  SCIP_CALL( SCIPreleaseCons(scip, &(*branchdata)->cons) );
721  (*branchdata)->cons = NULL;
722  }
723 
724  SCIPfreeBlockMemoryNull(scip, branchdata);
725  *branchdata = NULL;
726 
727  return SCIP_OKAY;
728 }
729 
730 static
731 SCIP_DECL_BRANCHFREE(branchFreeOrig)
732 { /*lint --e{715}*/
733  SCIP_BRANCHRULEDATA* branchruledata;
734 
735  branchruledata = SCIPbranchruleGetData(branchrule);
736 
737  SCIPfreeBlockMemory(scip, &branchruledata);
738  SCIPbranchruleSetData(branchrule, NULL);
739 
740  return SCIP_OKAY;
741 }
742 
743 /*
744  * Callback methods
745  */
746 
747 /** branching execution method for fractional LP solutions */
748 static
749 SCIP_DECL_BRANCHEXECLP(branchExeclpOrig)
750 { /*lint --e{715}*/
751  SCIP* origscip;
752 
753  //SCIPdebugMessage("Execlp method of orig branching\n");
754 
755  /* get original problem */
756  origscip = GCGmasterGetOrigprob(scip);
757  assert(origscip != NULL);
758 
759  if( GCGcurrentNodeIsGeneric(scip) )
760  {
761  SCIPdebugMessage("Not executing orig branching, node was branched by generic branchrule\n");
762  *result = SCIP_DIDNOTRUN;
763  return SCIP_OKAY;
764  }
765 
766  /* if the transferred master solution is feasible, the current node is solved to optimality and can be pruned */
767  if( GCGrelaxIsOrigSolFeasible(origscip) )
768  {
769  *result = SCIP_DIDNOTFIND;
770  SCIPdebugMessage("solution was feasible, node can be cut off!");
771  }
772 
773  if( SCIPgetNExternBranchCands(origscip) > 0 )
774  {
775  assert(SCIPisRelaxSolValid(origscip));
776  SCIP_CALL( branchExtern(origscip, branchrule, result) );
777  }
778 
779  return SCIP_OKAY;
780 }
781 
782 /** branching execution method for relaxation solutions */
783 static
784 SCIP_DECL_BRANCHEXECEXT(branchExecextOrig)
785 { /*lint --e{715}*/
786  SCIP* origscip;
787 
788  SCIPdebugMessage("Execext method of orig branching\n");
789 
790  /* get original problem */
791  origscip = GCGmasterGetOrigprob(scip);
792  assert(origscip != NULL);
793 
794  if( GCGcurrentNodeIsGeneric(scip) )
795  {
796  SCIPdebugMessage("Not executing orig branching, node was branched by generic branchrule\n");
797  *result = SCIP_DIDNOTRUN;
798  return SCIP_OKAY;
799  }
800 
801  /* if the transferred master solution is feasible, the current node is solved to optimality and can be pruned */
802  if( GCGrelaxIsOrigSolFeasible(origscip) )
803  {
804  *result = SCIP_DIDNOTFIND;
805  SCIPdebugMessage("solution was feasible, node can be cut off!");
806  }
807  SCIP_CALL( branchExtern(origscip, branchrule, result) );
808 
809  return SCIP_OKAY;
810 }
811 
812 /** initialization method of branching rule (called after problem was transformed) */
813 static
814 SCIP_DECL_BRANCHINIT(branchInitOrig)
815 {
816  SCIP* origprob;
817 
818  origprob = GCGmasterGetOrigprob(scip);
819  assert(branchrule != NULL);
820  assert(origprob != NULL);
821 
822  SCIPdebugMessage("Init orig branching rule\n");
823 
824  SCIP_CALL( GCGrelaxIncludeBranchrule( origprob, branchrule, branchActiveMasterOrig,
825  branchDeactiveMasterOrig, branchPropMasterOrig, branchMasterSolvedOrig, branchDataDeleteOrig) );
826 
827  return SCIP_OKAY;
828 }
829 
830 /** branching execution method for not completely fixed pseudo solutions */
831 static
832 SCIP_DECL_BRANCHEXECPS(branchExecpsOrig)
833 { /*lint --e{715}*/
834  int i;
835  SCIP* origscip;
836 
837  /* branching candidates */
838  SCIP_VAR** branchcands;
839  int nbranchcands;
840  int npriobranchcands;
841 
842  /* values for choosing the variable to branch on */
843  SCIP_VAR* branchvar;
844  SCIP_Real solval;
845  SCIP_Real lb;
846  SCIP_Real ub;
847 
848  assert(branchrule != NULL);
849  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
850  assert(scip != NULL);
851  assert(result != NULL);
852 
853  SCIPdebugMessage("EXECPS orig branching rule\n");
854 
855  /* get original problem */
856  origscip = GCGmasterGetOrigprob(scip);
857  assert(origscip != NULL);
858 
859  if( GCGcurrentNodeIsGeneric(scip) )
860  {
861  SCIPdebugMessage("Not executing orig branching, node was branched by generic branchrule\n");
862  *result = SCIP_DIDNOTRUN;
863  return SCIP_OKAY;
864  }
865 
866  SCIPdebugMessage("Execps method of orig branching\n");
867 
868  *result = SCIP_DIDNOTRUN;
869  if( SCIPgetStage(scip) > SCIP_STAGE_SOLVING )
870  return SCIP_OKAY;
871 
872  /* get the branching candidates */
873  SCIP_CALL( SCIPgetPseudoBranchCands(origscip, &branchcands, &nbranchcands, &npriobranchcands) );
874 
875  branchvar = NULL;
876  solval = 0.0;
877 
878  /* branch on an integer variable belonging to a unique block with fractional value */
879  for( i = 0; i < npriobranchcands; i++ )
880  {
881  assert(GCGvarIsOriginal(branchcands[i]));
882 
883  /* variable belongs to no block or the block is not unique */
884  if( GCGvarGetBlock(branchcands[i]) <= -1 || GCGgetNIdenticalBlocks(origscip,
885  GCGvarGetBlock(branchcands[i])) != 1 )
886  continue;
887 
888  branchvar = branchcands[i];
889  lb = SCIPvarGetLbLocal(branchvar);
890  ub = SCIPvarGetUbLocal(branchvar);
891 
892  assert(ub - lb > 0.8);
893 
894  /* if the bounds of the branching variable x are finite, then the solution value
895  * is floor((lb + ub)/2)) + 0.5,
896  * otherwise the solution value is set to a finite bound
897  * if no finite bound exists, the solution value is set to 0.
898  */
899  if( !SCIPisInfinity(origscip, ub) && !SCIPisInfinity(origscip, -lb) )
900  solval = SCIPfeasFloor(scip, (ub + lb) / 2.0) + 0.5;
901  else if( !SCIPisInfinity(origscip, -lb) )
902  solval = lb;
903  else if( !SCIPisInfinity(origscip, ub) )
904  solval = ub;
905  else
906  solval = 0.0;
907 
908  break;
909  }
910 
911  /* we did not find a variable to branch on so far, so we look for an unfixed linking variable or an integer variable
912  * that belongs to no block but was directly transferred to the master problem
913  */
914  if( branchvar == NULL )
915  {
916  for( i = 0; i < npriobranchcands; i++ )
917  {
918  assert(GCGvarIsOriginal(branchcands[i]));
919 
920  /* continue if variable belongs to a block */
921  if( GCGvarGetBlock(branchcands[i]) > -1 )
922  continue;
923 
924  /* check that blocks of linking variable are unique */
925  if( GCGoriginalVarIsLinking(branchcands[i]) )
926  {
927  int nvarblocks;
928  int* varblocks;
929  SCIP_Bool unique;
930  int j;
931 
932  nvarblocks = GCGlinkingVarGetNBlocks(branchcands[i]);
933  SCIP_CALL( SCIPallocBufferArray(origscip, &varblocks, nvarblocks) );
934  SCIP_CALL( GCGlinkingVarGetBlocks(branchcands[i], nvarblocks, varblocks) );
935 
936  unique = TRUE;
937  for( j = 0; j < nvarblocks; ++j )
938  if( GCGgetNIdenticalBlocks(origscip, varblocks[j]) != 1 )
939  unique = FALSE;
940 
941  SCIPfreeBufferArray(origscip, &varblocks);
942 
943  if( !unique )
944  continue;
945  }
946 
947  branchvar = branchcands[i];
948  lb = SCIPvarGetLbLocal(branchvar);
949  ub = SCIPvarGetUbLocal(branchvar);
950 
951  assert(ub - lb > 0.8);
952 
953  /* if the bounds of the branching variable x are finite, then the solution value
954  * is floor((lb + ub)/2)) + 0.5,
955  * otherwise the solution value is set to a finite bound
956  * if no finite bound exists, the solution value is set to 0.
957  */
958  if( !SCIPisInfinity(origscip, ub) && !SCIPisInfinity(origscip, -lb) )
959  solval = SCIPfeasFloor(scip, (ub + lb) / 2.0) + 0.5;
960  else if( !SCIPisInfinity(origscip, -lb) )
961  solval = lb;
962  else if( !SCIPisInfinity(origscip, ub) )
963  solval = ub;
964  else
965  solval = 0.0;
966 
967  break;
968  }
969  }
970 
971  if( branchvar == NULL )
972  {
973  SCIPdebugMessage("Original branching rule could not find a variable to branch on!\n");
974  return SCIP_OKAY;
975  }
976 
977  assert(branchvar != NULL);
978 
979  SCIP_CALL( branchVar(origscip, branchrule, branchvar, solval, FALSE, FALSE) );
980 
981  *result = SCIP_BRANCHED;
982 
983  return SCIP_OKAY;
984 }
985 
986 
987 
988 /*
989  * branching specific interface methods
990  */
991 
992 /** creates the branching on original variable branching rule and includes it in SCIP */
994  SCIP* scip /**< SCIP data structure */
995  )
996 {
997  SCIP* origscip;
998  SCIP_BRANCHRULE* branchrule;
999  SCIP_BRANCHRULEDATA* branchruledata;
1000 
1001  SCIPdebugMessage("Include orig branching rule\n");
1002 
1003  /* get original problem */
1004  origscip = GCGmasterGetOrigprob(scip);
1005  assert(origscip != NULL);
1006 
1007  /* alloc branching rule data */
1008  SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
1009 
1010  /* include branching rule */
1011  SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
1012  BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
1013  assert(branchrule != NULL);
1014 
1015  /* set non fundamental callbacks via setter functions */
1016  SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitOrig) );
1017  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpOrig) );
1018  SCIP_CALL( SCIPsetBranchruleExecExt(scip, branchrule, branchExecextOrig) );
1019  SCIP_CALL( SCIPsetBranchruleExecPs(scip, branchrule, branchExecpsOrig) );
1020  SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeOrig) );
1021 
1022  /* add original variable branching rule parameters */
1023 
1024  SCIP_CALL( SCIPaddBoolParam(origscip, "branching/orig/enforcebycons",
1025  "should bounds on variables be enforced by constraints(TRUE) or by bounds(FALSE)",
1026  &branchruledata->enforcebycons, FALSE, DEFAULT_ENFORCEBYCONS, NULL, NULL) );
1027 
1028  SCIP_CALL( SCIPaddBoolParam(origscip, "branching/orig/usepseudocosts",
1029  "should pseudocosts be used to determine the variable on which the branching is performed?",
1030  &branchruledata->usepseudocosts, FALSE, DEFAULT_USEPSEUDO, NULL, NULL) );
1031 
1032  SCIP_CALL( SCIPaddBoolParam(origscip, "branching/orig/mostfrac",
1033  "should branching be performed on the most fractional variable? (only if usepseudocosts = FALSE)",
1034  &branchruledata->mostfrac, FALSE, DEFAULT_MOSTFRAC, NULL, NULL) );
1035 
1036  SCIP_CALL( SCIPaddBoolParam(origscip, "branching/orig/userandom",
1037  "should the variable on which the branching is performed be selected randomly? (only if usepseudocosts = mostfrac = FALSE)",
1038  &branchruledata->usepseudocosts, FALSE, DEFAULT_USEPSEUDO, NULL, NULL) );
1039 
1040  SCIP_CALL( SCIPaddBoolParam(origscip, "branching/orig/usepsstrong",
1041  "should strong branching with propagation be used to determine the variable on which the branching is performed? (only if usepseudocosts = mostfrac = random = FALSE)",
1042  &branchruledata->usepsstrong, FALSE, DEFAULT_USEPSSTRONG, NULL, NULL) );
1043 
1044  SCIP_CALL( SCIPaddBoolParam(origscip, "branching/orig/usestrong",
1045  "should strong branching be used to determine the variable on which the branching is performed?",
1046  &branchruledata->usestrong, FALSE, DEFAULT_USESTRONG, NULL, NULL) );
1047 
1048  /* strong branching */
1049  SCIP_CALL( SCIPaddIntParam(origscip, "branching/orig/minphase0outcands",
1050  "minimum number of output candidates from phase 0 during strong branching",
1051  NULL, FALSE, DEFAULT_MINPHASE0OUTCANDS, 1, INT_MAX, NULL, NULL) );
1052 
1053  SCIP_CALL( SCIPaddIntParam(origscip, "branching/orig/maxphase0outcands",
1054  "maximum number of output candidates from phase 0 during strong branching",
1055  NULL, FALSE, DEFAULT_MAXPHASE0OUTCANDS, 1, INT_MAX, NULL, NULL) );
1056 
1057  SCIP_CALL( SCIPaddRealParam(origscip, "branching/orig/maxphase0outcandsfrac",
1058  "maximum number of output candidates from phase 0 as fraction of total cands during strong branching",
1059  NULL, FALSE, DEFAULT_MAXPHASE0OUTCANDSFRAC, 0, 1, NULL, NULL) );
1060 
1061  SCIP_CALL( SCIPaddRealParam(origscip, "branching/orig/phase1gapweight",
1062  "how much impact should the node gap have on the number of precisely evaluated candidates in phase 1 during strong branching?",
1063  NULL, FALSE, DEFAULT_PHASE1GAPWEIGHT, 0, 1, NULL, NULL) );
1064 
1065  SCIP_CALL( SCIPaddIntParam(origscip, "branching/orig/minphase1outcands",
1066  "minimum number of output candidates from phase 1 during strong branching",
1067  NULL, FALSE, DEFAULT_MINPHASE1OUTCANDS, 1, INT_MAX, NULL, NULL) );
1068 
1069  SCIP_CALL( SCIPaddIntParam(origscip, "branching/orig/maxphase1outcands",
1070  "maximum number of output candidates from phase 1 during strong branching",
1071  NULL, FALSE, DEFAULT_MAXPHASE1OUTCANDS, 1, INT_MAX, NULL, NULL) );
1072 
1073  SCIP_CALL( SCIPaddRealParam(origscip, "branching/orig/maxphase1outcandsfrac",
1074  "maximum number of output candidates from phase 1 as fraction of phase 1 cands during strong branching",
1075  NULL, FALSE, DEFAULT_MAXPHASE1OUTCANDSFRAC, 0, 1, NULL, NULL) );
1076 
1077  SCIP_CALL( SCIPaddRealParam(origscip, "branching/orig/phase2gapweight",
1078  "how much impact should the node gap have on the number of precisely evaluated candidates in phase 2 during strong branching?",
1079  NULL, FALSE, DEFAULT_PHASE2GAPWEIGHT, 0, 1, NULL, NULL) );
1080 
1081  /* notify cons_integralorig about the original variable branching rule */
1082  SCIP_CALL( GCGconsIntegralorigAddBranchrule(scip, branchrule) );
1083 
1084  return SCIP_OKAY;
1085 }
1086 
1087 /** get the original variable on which the branching was performed */
1089  GCG_BRANCHDATA* branchdata /**< branching data */
1090  )
1091 {
1092  assert(branchdata != NULL);
1093 
1094  return branchdata->origvar;
1095 }
1096 
1097 /** get the type of the new bound which resulted of the performed branching */
1099  GCG_BRANCHDATA* branchdata /**< branching data */
1100  )
1101 {
1102  assert(branchdata != NULL);
1103 
1104  return branchdata->boundtype;
1105 }
1106 
1107 /** get the new bound which resulted of the performed branching */
1109  GCG_BRANCHDATA* branchdata /**< branching data */
1110  )
1111 {
1112  assert(branchdata != NULL);
1113 
1114  return branchdata->newbound;
1115 }
1116 
1117 /** updates extern branching candidates before branching */
1119  SCIP* scip /**< SCIP data structure */
1120 )
1121 {
1122  SCIP_VAR** origvars;
1123  int norigvars;
1124  int i;
1125 
1126  assert(GCGisOriginal(scip));
1127 
1128  origvars = SCIPgetVars(scip);
1129  norigvars = SCIPgetNVars(scip);
1130  assert(origvars != NULL);
1131 
1132  SCIPclearExternBranchCands(scip);
1133 
1134  /* store branching candidates */
1135  for( i = 0; i < norigvars; i++ )
1136  {
1137  if( SCIPvarGetType(origvars[i]) <= SCIP_VARTYPE_INTEGER && !SCIPisFeasIntegral(scip,
1138  SCIPgetRelaxSolVal(scip, origvars[i])) )
1139  {
1140  assert(!SCIPisEQ(scip, SCIPvarGetLbLocal(origvars[i]), SCIPvarGetUbLocal(origvars[i])));
1141 
1142  SCIP_CALL( SCIPaddExternBranchCand(scip, origvars[i], SCIPgetRelaxSolVal(scip,
1143  origvars[i]) - SCIPfloor(scip, SCIPgetRelaxSolVal(scip, origvars[i])),
1144  SCIPgetRelaxSolVal(scip, origvars[i])) );
1145  }
1146  }
1147  SCIPdebugMessage("updated relaxation branching candidates\n");
1148 
1149  return SCIP_OKAY;
1150 }
type definitions for branching rules in GCG projects
SCIP_CONS * cons
Definition: branch_orig.c:110
#define BRANCHRULE_DESC
Definition: branch_orig.c:57
SCIP_Real oldbound
Definition: branch_orig.c:107
GCG interface methods.
#define DEFAULT_USESTRONG
Definition: branch_orig.c:69
SCIP_Bool GCGrelaxIsOrigSolFeasible(SCIP *scip)
Definition: relax_gcg.c:4202
SCIP_Real olddualbound
Definition: branch_orig.c:109
SCIP_VAR * GCGbranchOrigGetOrigvar(GCG_BRANCHDATA *branchdata)
Definition: branch_orig.c:1088
SCIP_VAR * origvar
Definition: branch_orig.c:104
SCIP_RETCODE GCGcreateConsMasterbranch(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_NODE *node, SCIP_CONS *parentcons, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata, SCIP_CONS **origbranchconss, int norigbranchconss, int maxorigbranchconss)
static SCIP_DECL_BRANCHINIT(branchInitOrig)
Definition: branch_orig.c:814
SCIP_Bool userandom
Definition: branch_orig.c:92
static SCIP_Bool getUniqueBlockFlagForIter(SCIP *scip, SCIP_VAR *branchcand, int iter)
Definition: branch_orig.c:120
int GCGvarGetBlock(SCIP_VAR *var)
Definition: gcgvar.c:1033
int GCGlinkingVarGetNBlocks(SCIP_VAR *var)
Definition: gcgvar.c:493
SCIP_RETCODE GCGrelaxTransOrigToMasterCons(SCIP *scip, SCIP_CONS *cons, SCIP_CONS **transcons)
Definition: relax_gcg.c:3789
@ GCG_BOUNDTYPE_LOWER
#define DEFAULT_MOSTFRAC
Definition: branch_orig.c:64
#define DEFAULT_USEPSEUDO
Definition: branch_orig.c:63
static GCG_DECL_BRANCHMASTERSOLVED(branchMasterSolvedOrig)
Definition: branch_orig.c:680
branching rule for original problem in GCG
static SCIP_Real score_function(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR *var, SCIP_Real solval, SCIP_Real *score)
Definition: branch_orig.c:472
SCIP_Bool GCGvarIsOriginal(SCIP_VAR *var)
Definition: gcgvar.c:166
GCG variable pricer.
SCIP_RETCODE SCIPgetRelpsprobBranchVar(SCIP *scip, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, int nbranchcands, int nvars, SCIP_RESULT *result, SCIP_VAR **branchvar)
#define DEFAULT_MAXPHASE1OUTCANDSFRAC
Definition: branch_orig.c:78
SCIP * GCGgetMasterprob(SCIP *scip)
Definition: relax_gcg.c:3920
constraint handler for the integrality constraint
#define DEFAULT_MINPHASE1OUTCANDS
Definition: branch_orig.c:76
#define DEFAULT_USEPSSTRONG
Definition: branch_orig.c:66
constraint handler for storing the branching decisions at each node of the tree
SCIP_Real newbound
Definition: branch_orig.c:106
#define BRANCHRULE_NAME
Definition: branch_orig.c:56
GCG_BOUNDTYPE boundtype
Definition: branch_orig.c:105
static GCG_DECL_BRANCHACTIVEMASTER(branchActiveMasterOrig)
Definition: branch_orig.c:642
SCIP_Bool GCGcurrentNodeIsGeneric(SCIP *scip)
constraint handler for storing the branching decisions at each node of the tree
static SCIP_DECL_BRANCHEXECEXT(branchExecextOrig)
Definition: branch_orig.c:784
SCIP_Real oldvalue
Definition: branch_orig.c:108
SCIP_Bool GCGisOriginal(SCIP *scip)
Definition: misc.c:665
int GCGgetNIdenticalBlocks(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:4053
#define BRANCHRULE_MAXDEPTH
Definition: branch_orig.c:59
#define DEFAULT_MINPHASE0OUTCANDS
Definition: branch_orig.c:71
SCIP_Real GCGbranchOrigGetNewbound(GCG_BRANCHDATA *branchdata)
Definition: branch_orig.c:1108
#define DEFAULT_MAXPHASE0OUTCANDS
Definition: branch_orig.c:72
SCIP * GCGmasterGetOrigprob(SCIP *scip)
GCG_BOUNDTYPE GCGbranchOrigGetBoundtype(GCG_BRANCHDATA *branchdata)
Definition: branch_orig.c:1098
#define BRANCHRULE_PRIORITY
Definition: branch_orig.c:58
static SCIP_DECL_BRANCHFREE(branchFreeOrig)
Definition: branch_orig.c:731
SCIP_RETCODE SCIPincludeBranchruleOrig(SCIP *scip)
Definition: branch_orig.c:993
GCG relaxator.
static SCIP_DECL_BRANCHEXECPS(branchExecpsOrig)
Definition: branch_orig.c:832
SCIP_CONS * GCGconsMasterbranchGetActiveCons(SCIP *scip)
#define DEFAULT_PHASE2GAPWEIGHT
Definition: branch_orig.c:79
#define DEFAULT_PHASE1GAPWEIGHT
Definition: branch_orig.c:74
static SCIP_RETCODE branchVar(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR *branchvar, SCIP_Real solval, SCIP_Bool upinf, SCIP_Bool downinf)
Definition: branch_orig.c:186
static SCIP_DECL_BRANCHEXECLP(branchExeclpOrig)
Definition: branch_orig.c:749
SCIP_Bool enforcebycons
Definition: branch_orig.c:86
enum GCG_BoundType GCG_BOUNDTYPE
SCIP_Bool usestrong
Definition: branch_orig.c:97
SCIP_Bool GCGoriginalVarIsLinking(SCIP_VAR *var)
Definition: gcgvar.c:182
#define DEFAULT_MAXPHASE0OUTCANDSFRAC
Definition: branch_orig.c:73
SCIP_RETCODE GCGbranchOrigUpdateExternBranchcands(SCIP *scip)
Definition: branch_orig.c:1118
#define DEFAULT_ENFORCEBYCONS
Definition: branch_orig.c:62
@ GCG_BOUNDTYPE_UPPER
#define BRANCHRULE_MAXBOUNDDIST
Definition: branch_orig.c:60
#define branchPropMasterOrig
Definition: branch_orig.c:638
generic branch and price strong branching as described in Pecin, D., Pessoa, A., Poggi,...
static GCG_DECL_BRANCHDATADELETE(branchDataDeleteOrig)
Definition: branch_orig.c:704
static SCIP_RETCODE branchExtern(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_RESULT *result)
Definition: branch_orig.c:503
SCIP_RETCODE GCGbranchSelectCandidateStrongBranchingOrig(SCIP *scip, SCIP_BRANCHRULE *origbranchrule, SCIP_VAR **branchvar, SCIP_Bool *upinf, SCIP_Bool *downinf, SCIP_RESULT *result, SCIP_Bool *stillusestrong)
reliable pseudo costs branching rule
#define DEFAULT_MAXPHASE1OUTCANDS
Definition: branch_orig.c:77
SCIP_Bool usepsstrong
Definition: branch_orig.c:94
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:3545
SCIP_RETCODE GCGlinkingVarGetBlocks(SCIP_VAR *var, int nblocks, int *blocks)
Definition: gcgvar.c:450
#define branchDeactiveMasterOrig
Definition: branch_orig.c:637
@ GCG_BOUNDTYPE_FIXED
SCIP_RETCODE GCGconsIntegralorigAddBranchrule(SCIP *scip, SCIP_BRANCHRULE *branchrule)