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-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 /* #define SCIP_DEBUG */
38 #include <assert.h>
39 #include <string.h>
40 
41 #include "branch_orig.h"
42 #include "gcg.h"
43 #include "branch_relpsprob.h"
44 #include "cons_integralorig.h"
45 #include "cons_masterbranch.h"
46 #include "cons_origbranch.h"
47 #include "relax_gcg.h"
48 #include "pricer_gcg.h"
49 #include "type_branchgcg.h"
50 
51 #include "scip/cons_linear.h"
52 
53 
54 #define BRANCHRULE_NAME "orig"
55 #define BRANCHRULE_DESC "branching for the original program in generic column generation"
56 #define BRANCHRULE_PRIORITY 100
57 #define BRANCHRULE_MAXDEPTH -1
58 #define BRANCHRULE_MAXBOUNDDIST 1.0
59 
60 #define DEFAULT_ENFORCEBYCONS FALSE
61 #define DEFAULT_MOSTFRAC FALSE
62 #define DEFAULT_USEPSEUDO TRUE
63 #define DEFAULT_USEPSSTRONG FALSE
64 
66 struct GCG_BranchData
67 {
68  SCIP_VAR* origvar;
70  SCIP_Real newbound;
71  SCIP_Real oldbound;
72  SCIP_Real oldvalue;
73  SCIP_Real olddualbound;
74  SCIP_CONS* cons;
76 };
77 
88 static
89 SCIP_RETCODE branchVar(
90  SCIP* scip,
91  SCIP_BRANCHRULE* branchrule,
92  SCIP_VAR* branchvar,
93  SCIP_Real solval
94  )
95 {
96  /* data for b&b child creation */
97  SCIP* masterscip;
98  SCIP_Real downub;
99  SCIP_Real fixval;
100  SCIP_Real uplb;
101 
102  /* parameter data */
103  SCIP_Bool enforcebycons;
104 
105  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
106  assert(scip != NULL);
107  assert(branchrule != NULL);
108  assert(branchvar != NULL);
109 
110  /* get master problem */
111  masterscip = GCGgetMasterprob(scip);
112  assert(masterscip != NULL);
113 
114  downub = SCIP_INVALID;
115  fixval = SCIP_INVALID;
116  uplb = SCIP_INVALID;
117 
118  /* get values of parameters */
119  SCIP_CALL( SCIPgetBoolParam(scip, "branching/orig/enforcebycons", &enforcebycons) );
120 
121  if( SCIPisFeasIntegral(scip, solval) )
122  {
123  SCIP_Real lb;
124  SCIP_Real ub;
125 
126  lb = SCIPvarGetLbLocal(branchvar);
127  ub = SCIPvarGetUbLocal(branchvar);
128 
129  /* if there was no explicit value given for branching, the variable has a finite domain and the current LP/pseudo
130  * solution is one of the bounds, we branch in the center of the domain */
131  if( !SCIPisInfinity(scip, -lb) && !SCIPisInfinity(scip, ub) )
132  {
133  SCIP_Real center;
134 
135  /* create child nodes with x <= x", and x >= x"+1 with x" = floor((lb + ub)/2);
136  * if x" is integral, make the interval smaller in the child in which the current solution x'
137  * is still feasible
138  */
139  center = (ub + lb) / 2.0;
140  if( solval <= center )
141  {
142  downub = SCIPfeasFloor(scip, center);
143  uplb = downub + 1.0;
144  }
145  else
146  {
147  uplb = SCIPfeasCeil(scip, center);
148  downub = uplb - 1.0;
149  }
150  }
151  else
152  {
153  /* create child nodes with x <= x'-1, x = x', and x >= x'+1 */
154  assert(SCIPisEQ(scip, SCIPfeasCeil(scip, solval), SCIPfeasFloor(scip, solval)));
155 
156  fixval = solval;
157 
158  /* create child node with x <= x'-1, if this would be feasible */
159  if( SCIPisFeasGE(scip, fixval-1.0, lb) )
160  downub = fixval - 1.0;
161 
162  /* create child node with x >= x'+1, if this would be feasible */
163  if( SCIPisFeasLE(scip, fixval+1.0, ub) )
164  uplb = fixval + 1.0;
165  }
166  SCIPdebugMessage("integral branch on variable <%s> with value %g, priority %d (current lower bound: %g)\n",
167  SCIPvarGetName(branchvar), solval, SCIPvarGetBranchPriority(branchvar), SCIPgetLocalLowerbound(GCGgetMasterprob(scip)));
168  }
169  else
170  {
171  /* create child nodes with x <= floor(x'), and x >= ceil(x') */
172  downub = SCIPfeasFloor(scip, solval);
173  uplb = downub + 1.0;
174  assert( SCIPisEQ(scip, SCIPfeasCeil(scip, solval), uplb) );
175  SCIPdebugMessage("fractional branch on variable <%s> with value %g, root value %g, priority %d (current lower bound: %g)\n",
176  SCIPvarGetName(branchvar), solval, SCIPvarGetRootSol(branchvar), SCIPvarGetBranchPriority(branchvar), SCIPgetLocalLowerbound(GCGgetMasterprob(scip)));
177  }
178 
179  SCIPdebugMessage("Branching on var %s with value %g in current solution\n", SCIPvarGetName(branchvar), solval);
180 
181 
182  if( uplb != SCIP_INVALID ) /*lint !e777*/
183  {
184  SCIP_CONS* cons;
185  SCIP_NODE* child;
186  SCIP_CONS** origbranchconss;
187  GCG_BRANCHDATA* branchdata;
188  char name[SCIP_MAXSTRLEN];
189 
190  int norigbranchconss;
191 
192  origbranchconss = NULL;
193  norigbranchconss = 0;
194 
195  /* create child node x >= uplb */
196  SCIP_CALL( SCIPcreateChild(masterscip, &child, 0.0, SCIPgetLocalTransEstimate(masterscip)) );
197 
198  SCIP_CALL( SCIPallocBlockMemory(scip, &branchdata) );
199 
200  branchdata->origvar = branchvar;
201  branchdata->oldvalue = solval;
202  branchdata->olddualbound = SCIPgetLocalLowerbound(masterscip);
203  branchdata->boundtype = GCG_BOUNDTYPE_LOWER;
204  branchdata->newbound = uplb;
205  branchdata->oldbound = SCIPvarGetLbLocal(branchvar);
206 
207  SCIPdebugMessage(" -> creating child: <%s> >= %g\n",
208  SCIPvarGetName(branchvar), uplb);
209 
210  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s %s %f", SCIPvarGetName(branchdata->origvar),
211  ">=", branchdata->newbound);
212 
213  if( enforcebycons )
214  {
215  /* enforce new bounds by linear constraints */
216  SCIP_CONS* consup;
217 
218  SCIPdebugMessage("enforced by cons\n");
219 
220  norigbranchconss = 1;
221  SCIP_CALL( SCIPallocMemoryArray(scip, &origbranchconss, norigbranchconss) );
222  BMSclearMemoryArray(origbranchconss, norigbranchconss);
223 
224  /* create corresponding constraints */
225  SCIP_CALL( SCIPcreateConsLinear(scip, &consup, name, 0, NULL, NULL,
226  SCIPceil(scip, solval), SCIPinfinity(scip),
227  TRUE, TRUE, TRUE, TRUE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE) );
228 
229  SCIP_CALL( SCIPaddCoefLinear(scip, consup, branchvar, 1.0) );
230 
231  origbranchconss[0] = consup;
232  branchdata->cons = consup;
233  }
234  else
235  branchdata->cons = NULL;
236 
237  /* create and add the masterbranch constraint */
238  SCIP_CALL( GCGcreateConsMasterbranch(masterscip, &cons, name, child,
239  GCGconsMasterbranchGetActiveCons(masterscip), branchrule, branchdata, origbranchconss, norigbranchconss) );
240  SCIP_CALL( SCIPaddConsNode(masterscip, child, cons, NULL) );
241  }
242 
243  if( downub != SCIP_INVALID ) /*lint !e777*/
244  {
245  SCIP_CONS* cons;
246  SCIP_NODE* child;
247  SCIP_CONS** origbranchconss;
248  GCG_BRANCHDATA* branchdata;
249  char name[SCIP_MAXSTRLEN];
250 
251  int norigbranchconss;
252 
253  origbranchconss = NULL;
254  norigbranchconss = 0;
255 
256  /* create child node x <= downub */
257  SCIP_CALL( SCIPcreateChild(masterscip, &child, 0.0, SCIPgetLocalTransEstimate(masterscip)) );
258 
259  SCIP_CALL( SCIPallocBlockMemory(scip, &branchdata) );
260 
261  branchdata->origvar = branchvar;
262  branchdata->oldvalue = solval;
263  branchdata->olddualbound = SCIPgetLocalLowerbound(masterscip);
264  branchdata->boundtype = GCG_BOUNDTYPE_UPPER;
265  branchdata->newbound = downub;
266  branchdata->oldbound = SCIPvarGetUbLocal(branchvar);
267 
268  SCIPdebugMessage(" -> creating child: <%s> <= %g\n",
269  SCIPvarGetName(branchvar), downub);
270 
271  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s %s %f", SCIPvarGetName(branchdata->origvar),
272  "<=", branchdata->newbound);
273 
274  /* enforce branching decision by a constraint rather than by bound changes */
275  if( enforcebycons )
276  {
277  /* enforce new bounds by linear constraints */
278  SCIP_CONS* consdown;
279 
280  norigbranchconss = 1;
281  SCIP_CALL( SCIPallocMemoryArray(scip, &origbranchconss, norigbranchconss) );
282  BMSclearMemoryArray(origbranchconss, norigbranchconss);
283 
284  /* create corresponding constraints */
285  SCIP_CALL( SCIPcreateConsLinear(scip, &consdown, name, 0, NULL, NULL,
286  -1.0 * SCIPinfinity(scip), SCIPfloor(scip, solval),
287  TRUE, TRUE, TRUE, TRUE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE) );
288  SCIP_CALL( SCIPaddCoefLinear(scip, consdown, branchvar, 1.0) );
289 
290  origbranchconss[0] = consdown;
291  branchdata->cons = consdown;
292  }
293  else
294  branchdata->cons = NULL;
295 
296  /* create and add the masterbranch constraint */
297  SCIP_CALL( GCGcreateConsMasterbranch(masterscip, &cons, name, child,
298  GCGconsMasterbranchGetActiveCons(masterscip), branchrule, branchdata, origbranchconss, norigbranchconss) );
299  SCIP_CALL( SCIPaddConsNode(masterscip, child, cons, NULL) );
300  }
301 
302  if( fixval != SCIP_INVALID ) /*lint !e777*/
303  {
304  SCIP_CONS* cons;
305  SCIP_NODE* child;
306  SCIP_CONS** origbranchconss;
307  GCG_BRANCHDATA* branchdata;
308  char name[SCIP_MAXSTRLEN];
309 
310  int norigbranchconss;
311 
312  origbranchconss = NULL;
313  norigbranchconss = 0;
314 
315  /* create child node x = fixval */
316  SCIP_CALL( SCIPcreateChild(masterscip, &child, 0.0, SCIPgetLocalTransEstimate(masterscip)) );
317 
318  SCIP_CALL( SCIPallocBlockMemory(scip, &branchdata) );
319 
320  branchdata->origvar = branchvar;
321  branchdata->oldvalue = solval;
322  branchdata->olddualbound = SCIPgetLocalLowerbound(masterscip);
323  branchdata->boundtype = GCG_BOUNDTYPE_FIXED;
324  branchdata->newbound = fixval;
325  branchdata->oldbound = SCIPvarGetUbLocal(branchvar);
326 
327  SCIPdebugMessage(" -> creating child: <%s> == %g\n",
328  SCIPvarGetName(branchvar), fixval);
329 
330  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s %s %f", SCIPvarGetName(branchdata->origvar),
331  "==", branchdata->newbound);
332 
333  /* enforce branching decision by a constraint rather than by bound changes */
334  if( enforcebycons )
335  {
336  /* enforce new bounds by linear constraints */
337  SCIP_CONS* consfix;
338 
339  norigbranchconss = 1;
340  SCIP_CALL( SCIPallocMemoryArray(scip, &origbranchconss, norigbranchconss) );
341  BMSclearMemoryArray(origbranchconss, norigbranchconss);
342 
343  /* create corresponding constraints */
344  SCIP_CALL( SCIPcreateConsLinear(scip, &consfix, name, 0, NULL, NULL,
345  fixval, fixval, TRUE, TRUE, TRUE, TRUE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE) );
346  SCIP_CALL( SCIPaddCoefLinear(scip, consfix, branchvar, 1.0) );
347 
348  origbranchconss[0] = consfix;
349  branchdata->cons = consfix;
350  }
351  else
352  branchdata->cons = NULL;
353 
354  /* create and add the masterbranch constraint */
355  SCIP_CALL( GCGcreateConsMasterbranch(masterscip, &cons, name, child,
356  GCGconsMasterbranchGetActiveCons(masterscip), branchrule, branchdata, origbranchconss, norigbranchconss) );
357  SCIP_CALL( SCIPaddConsNode(masterscip, child, cons, NULL) );
358  }
359 
360  return SCIP_OKAY;
361 }
362 
363 
365 static
366 SCIP_RETCODE branchExtern(
367  SCIP* scip,
368  SCIP_BRANCHRULE* branchrule,
369  SCIP_RESULT* result
370  )
371 {
372  SCIP* masterscip;
373  int i;
374 
375  /* parameter data */
376  SCIP_Bool mostfrac;
377  SCIP_Bool usepseudocosts;
378  SCIP_Bool usepsstrong;
379 
380  /* branching candidates */
381  SCIP_VAR** branchcands;
382  SCIP_Real* branchcandssol;
383  int nbranchcands;
384  int npriobranchcands;
385 
386  /* values for choosing the variable to branch on */
387  SCIP_VAR* branchvar;
388  SCIP_Real solval;
389  SCIP_Real maxfrac;
390  SCIP_Real frac;
391  SCIP_Real maxpsscore;
392 
393  assert(branchrule != NULL);
394  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
395  assert(scip != NULL);
396  assert(result != NULL);
397  assert(SCIPisRelaxSolValid(scip));
398 
399  *result = SCIP_DIDNOTRUN;
400 
401  /* get master problem */
402  masterscip = GCGgetMasterprob(scip);
403  assert(masterscip != NULL);
404 
405  /* get values of parameters */
406  SCIP_CALL( SCIPgetBoolParam(scip, "branching/orig/mostfrac", &mostfrac) );
407  SCIP_CALL( SCIPgetBoolParam(scip, "branching/orig/usepseudocosts", &usepseudocosts) );
408  SCIP_CALL( SCIPgetBoolParam(scip, "branching/orig/usepsstrong", &usepsstrong) );
409 
410  /* get the branching candidates */
411  SCIP_CALL( SCIPgetExternBranchCands(scip, &branchcands, &branchcandssol, NULL, &nbranchcands,
412  &npriobranchcands, NULL, NULL, NULL) );
413 
414  branchvar = NULL;
415  solval = 0.0;
416 
417  maxfrac = 0.0;
418  maxpsscore = -1.0;
419 
420  if( usepsstrong )
421  {
422  SCIP_CALL( SCIPgetRelpsprobBranchVar(masterscip, branchcands, branchcandssol, npriobranchcands,
423  npriobranchcands, result, &branchvar) );
424  assert(branchvar != NULL || *result == SCIP_CUTOFF);
425  assert(*result == SCIP_DIDNOTRUN || *result == SCIP_CUTOFF);
426 
427  if( *result == SCIP_CUTOFF )
428  return SCIP_OKAY;
429 
430  solval = SCIPgetRelaxSolVal(scip, branchvar);
431  }
432 
433  /* branch on an integer variable belonging to a unique block with fractional value */
434  if( branchvar == NULL )
435  for( i = 0; i < npriobranchcands; i++ )
436  {
437  assert(GCGvarIsOriginal(branchcands[i]));
438 
439  /* variable belongs to no block */
440  if( GCGvarGetBlock(branchcands[i]) == -1 )
441  continue;
442 
443  /* block is not unique (non-linking variables) */
444  if( !GCGoriginalVarIsLinking(branchcands[i]) && GCGgetNIdenticalBlocks(scip, GCGvarGetBlock(branchcands[i])) != 1 )
445  continue;
446 
447  /* check that blocks of linking variable are unique */
448  if( GCGoriginalVarIsLinking(branchcands[i]) )
449  {
450  int nvarblocks;
451  int* varblocks;
452  SCIP_Bool unique;
453  int j;
454 
455  nvarblocks = GCGlinkingVarGetNBlocks(branchcands[i]);
456  SCIP_CALL( SCIPallocBufferArray(scip, &varblocks, nvarblocks) );
457  SCIP_CALL( GCGlinkingVarGetBlocks(branchcands[i], nvarblocks, varblocks) );
458 
459  unique = TRUE;
460  for( j = 0; j < nvarblocks; ++j )
461  if( GCGgetNIdenticalBlocks(scip, varblocks[j]) != 1 )
462  unique = FALSE;
463 
464  SCIPfreeBufferArray(scip, &varblocks);
465 
466  if( !unique )
467  continue;
468  }
469 
470  /* use pseudocost variable selection rule */
471  if( usepseudocosts )
472  {
473  /* select the variable, if its pseudocost are higher than the ones of the currently saved variable */
474  if( SCIPgetVarPseudocostScore(scip, branchcands[i], branchcandssol[i]) > maxpsscore )
475  {
476  branchvar = branchcands[i];
477  solval = SCIPgetRelaxSolVal(scip, branchcands[i]);
478  maxpsscore = SCIPgetVarPseudocostScore(scip, branchcands[i], branchcandssol[i]);
479  }
480  }
481  /* use most fractional variable selection rule */
482  else
483  {
484  /* compute the fractionality */
485  frac = branchcandssol[i] - SCIPfloor(scip, branchcandssol[i]);
486  frac = MIN(frac, 1.0 - frac);
487  assert(frac > 0);
488 
489  /* fractionality is higher than that of the current highest fractionality */
490  if( frac >= maxfrac )
491  {
492  SCIPdebugMessage("Var %s has fractional value in current solution: %f\n", SCIPvarGetName(branchcands[i]), branchcandssol[i]);
493  solval = SCIPgetRelaxSolVal(scip, branchcands[i]);
494  branchvar = branchcands[i];
495  /* if we do not look for the most fractional variable, but for the first fractional variable,
496  * we can stop here since we found a variable to branch on */
497  if( !mostfrac )
498  break;
499  }
500  }
501  }
502 
503  /* we did not find a variable to branch on so far, so we look for an integer variable that belongs to no block
504  * but was directly transferred to the master problem and which has fractional value in the current solution */
505  if( branchvar == NULL )
506  {
507  for( i = 0; i < npriobranchcands; i++ )
508  {
509  assert(GCGvarIsOriginal(branchcands[i]));
510 
511  /* continue if variable belongs to a block */
512  if( GCGvarGetBlock(branchcands[i]) != -1 )
513  continue;
514 
515  /* use pseudocost variable selection rule */
516  if( usepseudocosts )
517  {
518  if( SCIPgetVarPseudocostScore(scip, branchcands[i], branchcandssol[i]) > maxpsscore )
519  {
520  branchvar = branchcands[i];
521  solval = SCIPgetRelaxSolVal(scip, branchcands[i]);
522  maxpsscore = SCIPgetVarPseudocostScore(scip, branchcands[i], branchcandssol[i]);
523  }
524  }
525  /* use most fractional variable selection rule */
526  else
527  {
528  /* compute fractionality */
529  frac = branchcandssol[i] - SCIPfloor(scip, branchcandssol[i]);
530  frac = MIN(frac, 1.0 - frac);
531  assert(frac > 0);
532 
533  if( frac >= maxfrac )
534  {
535  SCIPdebugMessage("Var %s has fractional value in current solution: %f\n",
536  SCIPvarGetName(branchcands[i]), branchcandssol[i]);
537  solval = SCIPgetRelaxSolVal(scip, branchcands[i]);
538  branchvar = branchcands[i];
539  /* if we do not look for the most fractional variable, but for the first fractional variable,
540  * we stop here since we found a variable to branch on */
541  if( !mostfrac )
542  break;
543  }
544  }
545  }
546  }
547 
548  if( branchvar == NULL )
549  {
550  SCIPdebugMessage("Original branching rule could not find a variable to branch on!\n");
551  return SCIP_OKAY;
552  }
553 
554  assert(branchvar != NULL);
555 
556  SCIP_CALL( branchVar(scip, branchrule, branchvar, solval) );
557 
558  *result = SCIP_BRANCHED;
559 
560  return SCIP_OKAY;
561 }
562 
563 
564 /*
565  * Callback methods for enforcing branching constraints
566  */
567 
568 #define branchDeactiveMasterOrig NULL
569 #define branchPropMasterOrig NULL
570 
572 static
573 GCG_DECL_BRANCHACTIVEMASTER(branchActiveMasterOrig)
574 {
575  SCIP* origscip;
576  SCIP_CONS* mastercons;
577 
578  assert(scip != NULL);
579  assert(branchdata != NULL);
580 
581  /* branching restrictions are enforced by variable bounds, this is done automatically, so we can abort here */
582  if( branchdata->cons == NULL )
583  return SCIP_OKAY;
584 
585  assert(branchdata->origvar != NULL);
586 
587  origscip = GCGmasterGetOrigprob(scip);
588  assert(origscip != NULL);
589 
590  SCIPdebugMessage("branchActiveMasterOrig: %s %s %f\n", SCIPvarGetName(branchdata->origvar),
591  ( branchdata->boundtype == GCG_BOUNDTYPE_LOWER ? ">=" : branchdata->boundtype == GCG_BOUNDTYPE_UPPER ? "<=" : "==" ), branchdata->newbound);
592 
593  /* transform constraint to the master variable space */
594  SCIP_CALL( GCGrelaxTransOrigToMasterCons(origscip, branchdata->cons, &mastercons) );
595  assert(mastercons != NULL);
596 
597  /* add constraint to the master problem */
598  SCIP_CALL( SCIPaddConsNode(scip, SCIPgetCurrentNode(scip), mastercons, NULL) );
599 
600  /* constraint was added locally to the node where it is needed, so we do not need to care about this
601  * at the next activation of the node and can set the constraint pointer to NULL */
602  SCIP_CALL( SCIPreleaseCons(scip, &branchdata->cons) );
603  branchdata->cons = NULL;
604 
605  return SCIP_OKAY;
606 }
607 
609 static
610 GCG_DECL_BRANCHMASTERSOLVED(branchMasterSolvedOrig)
611 {
612  assert(scip != NULL);
613  assert(GCGisOriginal(scip));
614  assert(branchdata != NULL);
615  assert(branchdata->origvar != NULL);
616 
617  SCIPdebugMessage("branchMasterSolvedOrig: %s %s %f\n", SCIPvarGetName(branchdata->origvar),
618  ( branchdata->boundtype == GCG_BOUNDTYPE_LOWER ? ">=" : branchdata->boundtype == GCG_BOUNDTYPE_UPPER ? "<=" : "==" ), branchdata->newbound);
619 
620  if( !SCIPisInfinity(scip, newlowerbound) && SCIPgetStage(GCGgetMasterprob(scip)) == SCIP_STAGE_SOLVING
621  && SCIPisRelaxSolValid(GCGgetMasterprob(scip)) )
622  {
623  SCIP_CALL( SCIPupdateVarPseudocost(scip, branchdata->origvar,
624  SCIPgetRelaxSolVal(scip, branchdata->origvar) - branchdata->oldvalue,
625  newlowerbound - branchdata->olddualbound, 1.0) );
626  }
627 
628  return SCIP_OKAY;
629 }
630 
632 static
633 GCG_DECL_BRANCHDATADELETE(branchDataDeleteOrig)
634 {
635  assert(scip != NULL);
636  assert(branchdata != NULL);
637 
638  if( *branchdata == NULL )
639  return SCIP_OKAY;
640 
641  SCIPdebugMessage("branchDataDeleteOrig: %s %s %f\n", SCIPvarGetName((*branchdata)->origvar),
642  ( (*branchdata)->boundtype == GCG_BOUNDTYPE_LOWER ? ">=" : (*branchdata)->boundtype == GCG_BOUNDTYPE_UPPER ? "<=" : "==" ),
643  (*branchdata)->newbound);
644 
645  /* release constraint */
646  if( (*branchdata)->cons != NULL )
647  {
648  SCIP_CALL( SCIPreleaseCons(scip, &(*branchdata)->cons) );
649  (*branchdata)->cons = NULL;
650  }
651 
652  SCIPfreeBlockMemoryNull(scip, branchdata);
653  *branchdata = NULL;
654 
655  return SCIP_OKAY;
656 }
657 
658 /*
659  * Callback methods
660  */
661 
663 static
664 SCIP_DECL_BRANCHEXECLP(branchExeclpOrig)
665 { /*lint --e{715}*/
666  SCIP* origscip;
667 
668  SCIPdebugMessage("Execlp method of orig branching\n");
669 
670  /* get original problem */
671  origscip = GCGmasterGetOrigprob(scip);
672  assert(origscip != NULL);
673 
675  {
676  SCIPdebugMessage("Not executing orig branching, node was branched by generic branchrule\n");
677  *result = SCIP_DIDNOTRUN;
678  return SCIP_OKAY;
679  }
680 
681  /* if the transferred master solution is feasible, the current node is solved to optimality and can be pruned */
682  if( GCGrelaxIsOrigSolFeasible(origscip) )
683  {
684  *result = SCIP_DIDNOTFIND;
685  SCIPdebugMessage("solution was feasible, node can be cut off!");
686  }
687 
688  if( SCIPgetNExternBranchCands(origscip) > 0 )
689  {
690  assert(SCIPisRelaxSolValid(origscip));
691  SCIP_CALL( branchExtern(origscip, branchrule, result) );
692  }
693 
694  return SCIP_OKAY;
695 }
696 
698 static
699 SCIP_DECL_BRANCHEXECEXT(branchExecextOrig)
700 { /*lint --e{715}*/
701  SCIP* origscip;
702 
703  SCIPdebugMessage("Execext method of orig branching\n");
704 
705  /* get original problem */
706  origscip = GCGmasterGetOrigprob(scip);
707  assert(origscip != NULL);
708 
710  {
711  SCIPdebugMessage("Not executing orig branching, node was branched by generic branchrule\n");
712  *result = SCIP_DIDNOTRUN;
713  return SCIP_OKAY;
714  }
715 
716  /* if the transferred master solution is feasible, the current node is solved to optimality and can be pruned */
717  if( GCGrelaxIsOrigSolFeasible(origscip) )
718  {
719  *result = SCIP_DIDNOTFIND;
720  SCIPdebugMessage("solution was feasible, node can be cut off!");
721  }
722  SCIP_CALL( branchExtern(origscip, branchrule, result) );
723 
724  return SCIP_OKAY;
725 }
726 
728 static
729 SCIP_DECL_BRANCHINIT(branchInitOrig)
730 {
731  SCIP* origprob;
732 
733  origprob = GCGmasterGetOrigprob(scip);
734  assert(branchrule != NULL);
735  assert(origprob != NULL);
736 
737  SCIP_CALL( GCGrelaxIncludeBranchrule( origprob, branchrule, branchActiveMasterOrig,
738  branchDeactiveMasterOrig, branchPropMasterOrig, branchMasterSolvedOrig, branchDataDeleteOrig) );
739 
740  return SCIP_OKAY;
741 }
742 
744 static
745 SCIP_DECL_BRANCHEXECPS(branchExecpsOrig)
746 { /*lint --e{715}*/
747  int i;
748  SCIP* origscip;
749 
750  /* branching candidates */
751  SCIP_VAR** branchcands;
752  int nbranchcands;
753  int npriobranchcands;
754 
755  /* values for choosing the variable to branch on */
756  SCIP_VAR* branchvar;
757  SCIP_Real solval;
758  SCIP_Real lb;
759  SCIP_Real ub;
760 
761  assert(branchrule != NULL);
762  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
763  assert(scip != NULL);
764  assert(result != NULL);
765 
766  /* get original problem */
767  origscip = GCGmasterGetOrigprob(scip);
768  assert(origscip != NULL);
769 
771  {
772  SCIPdebugMessage("Not executing orig branching, node was branched by generic branchrule\n");
773  *result = SCIP_DIDNOTRUN;
774  return SCIP_OKAY;
775  }
776 
777  SCIPdebugMessage("Execps method of orig branching\n");
778 
779  *result = SCIP_DIDNOTRUN;
780  if( SCIPgetStage(scip) > SCIP_STAGE_SOLVING )
781  return SCIP_OKAY;
782 
783  /* get the branching candidates */
784  SCIP_CALL( SCIPgetPseudoBranchCands(origscip, &branchcands, &nbranchcands, &npriobranchcands) );
785 
786  branchvar = NULL;
787  solval = 0.0;
788 
789  /* branch on an integer variable belonging to a unique block with fractional value */
790  for( i = 0; i < npriobranchcands; i++ )
791  {
792  assert(GCGvarIsOriginal(branchcands[i]));
793 
794  /* variable belongs to no block or the block is not unique */
795  if( GCGvarGetBlock(branchcands[i]) <= -1 || GCGgetNIdenticalBlocks(origscip, GCGvarGetBlock(branchcands[i])) != 1 )
796  continue;
797 
798  branchvar = branchcands[i];
799  lb = SCIPvarGetLbLocal(branchvar);
800  ub = SCIPvarGetUbLocal(branchvar);
801 
802  assert(ub - lb > 0.8);
803 
804  /* if the bounds of the branching variable x are finite, then the solution value
805  * is floor((lb + ub)/2)) + 0.5,
806  * otherwise the solution value is set to a finite bound
807  * if no finite bound exists, the solution value is set to 0.
808  */
809  if( !SCIPisInfinity(origscip, ub) && !SCIPisInfinity(origscip, -lb) )
810  solval = SCIPfeasFloor(scip, (ub + lb) / 2.0) + 0.5;
811  else if( !SCIPisInfinity(origscip, -lb) )
812  solval = lb;
813  else if( !SCIPisInfinity(origscip, ub) )
814  solval = ub;
815  else
816  solval = 0.0;
817 
818  break;
819  }
820 
821  /* we did not find a variable to branch on so far, so we look for an unfixed linking variable or an integer variable
822  * that belongs to no block but was directly transferred to the master problem
823  */
824  if( branchvar == NULL )
825  {
826  for( i = 0; i < npriobranchcands; i++ )
827  {
828  assert(GCGvarIsOriginal(branchcands[i]));
829 
830  /* continue if variable belongs to a block */
831  if( GCGvarGetBlock(branchcands[i]) > -1 )
832  continue;
833 
834  /* check that blocks of linking variable are unique */
835  if( GCGoriginalVarIsLinking(branchcands[i]) )
836  {
837  int nvarblocks;
838  int* varblocks;
839  SCIP_Bool unique;
840  int j;
841 
842  nvarblocks = GCGlinkingVarGetNBlocks(branchcands[i]);
843  SCIP_CALL( SCIPallocBufferArray(origscip, &varblocks, nvarblocks) );
844  SCIP_CALL( GCGlinkingVarGetBlocks(branchcands[i], nvarblocks, varblocks) );
845 
846  unique = TRUE;
847  for( j = 0; j < nvarblocks; ++j )
848  if( GCGgetNIdenticalBlocks(origscip, varblocks[j]) != 1 )
849  unique = FALSE;
850 
851  SCIPfreeBufferArray(origscip, &varblocks);
852 
853  if( !unique )
854  continue;
855  }
856 
857  branchvar = branchcands[i];
858  lb = SCIPvarGetLbLocal(branchvar);
859  ub = SCIPvarGetUbLocal(branchvar);
860 
861  assert(ub - lb > 0.8);
862 
863  /* if the bounds of the branching variable x are finite, then the solution value
864  * is floor((lb + ub)/2)) + 0.5,
865  * otherwise the solution value is set to a finite bound
866  * if no finite bound exists, the solution value is set to 0.
867  */
868  if( !SCIPisInfinity(origscip, ub) && !SCIPisInfinity(origscip, -lb) )
869  solval = SCIPfeasFloor(scip, (ub + lb) / 2.0) + 0.5;
870  else if( !SCIPisInfinity(origscip, -lb) )
871  solval = lb;
872  else if( !SCIPisInfinity(origscip, ub) )
873  solval = ub;
874  else
875  solval = 0.0;
876 
877  break;
878  }
879  }
880 
881  if( branchvar == NULL )
882  {
883  SCIPdebugMessage("Original branching rule could not find a variable to branch on!\n");
884  return SCIP_OKAY;
885  }
886 
887  assert(branchvar != NULL);
888 
889  SCIP_CALL( branchVar(origscip, branchrule, branchvar, solval) );
890 
891  *result = SCIP_BRANCHED;
892 
893  return SCIP_OKAY;
894 }
895 
896 
897 
898 /*
899  * branching specific interface methods
900  */
901 
904  SCIP* scip
905  )
906 {
907  SCIP* origscip;
908  SCIP_BRANCHRULE* branchrule;
909 
910  /* get original problem */
911  origscip = GCGmasterGetOrigprob(scip);
912  assert(origscip != NULL);
913 
914  /* include branching rule */
915  SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
917  assert(branchrule != NULL);
918 
919  /* set non fundamental callbacks via setter functions */
920  SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitOrig) );
921  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpOrig) );
922  SCIP_CALL( SCIPsetBranchruleExecExt(scip, branchrule, branchExecextOrig) );
923  SCIP_CALL( SCIPsetBranchruleExecPs(scip, branchrule, branchExecpsOrig) );
924 
925  /* add original variable branching rule parameters */
926 
927  SCIP_CALL( SCIPaddBoolParam(origscip, "branching/orig/enforcebycons",
928  "should bounds on variables be enforced by constraints(TRUE) or by bounds(FALSE)",
929  NULL, FALSE, DEFAULT_ENFORCEBYCONS, NULL, NULL) );
930 
931  SCIP_CALL( SCIPaddBoolParam(origscip, "branching/orig/mostfrac",
932  "should branching be performed on the most fractional variable instead of the first variable?",
933  NULL, FALSE, DEFAULT_MOSTFRAC, NULL, NULL) );
934 
935  SCIP_CALL( SCIPaddBoolParam(origscip, "branching/orig/usepseudocosts",
936  "should pseudocosts be used to determine the variable on which the branching is performed?",
937  NULL, FALSE, DEFAULT_USEPSEUDO, NULL, NULL) );
938 
939  SCIP_CALL( SCIPaddBoolParam(origscip, "branching/orig/usepsstrong",
940  "should strong branching with propagation be used to determine the variable on which the branching is performed?",
941  NULL, FALSE, DEFAULT_USEPSSTRONG, NULL, NULL) );
942 
943  /* notify cons_integralorig about the original variable branching rule */
944  SCIP_CALL( GCGconsIntegralorigAddBranchrule(scip, branchrule) );
945 
946  return SCIP_OKAY;
947 }
948 
951  GCG_BRANCHDATA* branchdata
952  )
953 {
954  assert(branchdata != NULL);
955 
956  return branchdata->origvar;
957 }
958 
961  GCG_BRANCHDATA* branchdata
962  )
963 {
964  assert(branchdata != NULL);
965 
966  return branchdata->boundtype;
967 }
968 
971  GCG_BRANCHDATA* branchdata
972  )
973 {
974  assert(branchdata != NULL);
975 
976  return branchdata->newbound;
977 }
978 
981  SCIP* scip
982 )
983 {
984  SCIP_VAR** origvars;
985  int norigvars;
986  int i;
987 
988  assert(GCGisOriginal(scip));
989 
990  origvars = SCIPgetVars(scip);
991  norigvars = SCIPgetNVars(scip);
992  assert(origvars != NULL);
993 
994  SCIPclearExternBranchCands(scip);
995 
996  /* store branching candidates */
997  for( i = 0; i < norigvars; i++ )
998  {
999  if( SCIPvarGetType(origvars[i]) <= SCIP_VARTYPE_INTEGER && !SCIPisFeasIntegral(scip, SCIPgetRelaxSolVal(scip, origvars[i])) )
1000  {
1001  assert(!SCIPisEQ(scip, SCIPvarGetLbLocal(origvars[i]), SCIPvarGetUbLocal(origvars[i])));
1002 
1003  SCIP_CALL( SCIPaddExternBranchCand(scip, origvars[i], SCIPgetRelaxSolVal(scip,
1004  origvars[i]) - SCIPfloor(scip, SCIPgetRelaxSolVal(scip, origvars[i])),
1005  SCIPgetRelaxSolVal(scip, origvars[i])) );
1006  }
1007  }
1008  SCIPdebugMessage("updated relaxation branching candidates\n");
1009 
1010  return SCIP_OKAY;
1011 }
SCIP_RETCODE GCGconsIntegralorigAddBranchrule(SCIP *scip, SCIP_BRANCHRULE *branchrule)
SCIP_Bool GCGvarIsOriginal(SCIP_VAR *var)
Definition: gcgvar.c:162
static SCIP_RETCODE branchExtern(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_RESULT *result)
Definition: branch_orig.c:366
branching rule for original problem in GCG
#define DEFAULT_USEPSEUDO
Definition: branch_orig.c:62
GCG interface methods.
SCIP_Real oldvalue
Definition: branch_orig.c:72
static GCG_DECL_BRANCHMASTERSOLVED(branchMasterSolvedOrig)
Definition: branch_orig.c:610
SCIP_CONS * GCGconsMasterbranchGetActiveCons(SCIP *scip)
SCIP_VAR * GCGbranchOrigGetOrigvar(GCG_BRANCHDATA *branchdata)
Definition: branch_orig.c:950
SCIP * GCGgetMasterprob(SCIP *scip)
Definition: relax_gcg.c:3838
SCIP_Real oldbound
Definition: branch_orig.c:71
constraint handler for the integrality constraint
static SCIP_DECL_BRANCHINIT(branchInitOrig)
Definition: branch_orig.c:729
static SCIP_DECL_BRANCHEXECEXT(branchExecextOrig)
Definition: branch_orig.c:699
#define DEFAULT_USEPSSTRONG
Definition: branch_orig.c:63
enum GCG_BoundType GCG_BOUNDTYPE
#define BRANCHRULE_NAME
Definition: branch_orig.c:54
SCIP_Real GCGbranchOrigGetNewbound(GCG_BRANCHDATA *branchdata)
Definition: branch_orig.c:970
SCIP_RETCODE GCGrelaxTransOrigToMasterCons(SCIP *scip, SCIP_CONS *cons, SCIP_CONS **transcons)
Definition: relax_gcg.c:3695
#define DEFAULT_MOSTFRAC
Definition: branch_orig.c:61
SCIP_CONS * mastercons
#define BRANCHRULE_MAXDEPTH
Definition: branch_orig.c:57
int GCGlinkingVarGetNBlocks(SCIP_VAR *var)
Definition: gcgvar.c:473
#define BRANCHRULE_PRIORITY
Definition: branch_orig.c:56
GCG_BOUNDTYPE boundtype
Definition: branch_orig.c:69
GCG relaxator.
static SCIP_DECL_BRANCHEXECPS(branchExecpsOrig)
Definition: branch_orig.c:745
SCIP_Bool GCGoriginalVarIsLinking(SCIP_VAR *var)
Definition: gcgvar.c:176
GCG variable pricer.
int GCGvarGetBlock(SCIP_VAR *var)
Definition: gcgvar.c:936
static SCIP_RETCODE branchVar(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR *branchvar, SCIP_Real solval)
Definition: branch_orig.c:89
static GCG_DECL_BRANCHACTIVEMASTER(branchActiveMasterOrig)
Definition: branch_orig.c:573
SCIP_Bool GCGcurrentNodeIsGeneric(SCIP *scip)
SCIP_RETCODE GCGbranchOrigUpdateExternBranchcands(SCIP *scip)
Definition: branch_orig.c:980
SCIP * GCGmasterGetOrigprob(SCIP *scip)
#define DEFAULT_ENFORCEBYCONS
Definition: branch_orig.c:60
SCIP_Bool GCGrelaxIsOrigSolFeasible(SCIP *scip)
Definition: relax_gcg.c:4112
#define BRANCHRULE_MAXBOUNDDIST
Definition: branch_orig.c:58
GCG_BOUNDTYPE GCGbranchOrigGetBoundtype(GCG_BRANCHDATA *branchdata)
Definition: branch_orig.c:960
SCIP_RETCODE GCGlinkingVarGetBlocks(SCIP_VAR *var, int nblocks, int *blocks)
Definition: gcgvar.c:431
static GCG_DECL_BRANCHDATADELETE(branchDataDeleteOrig)
Definition: branch_orig.c:633
type definitions for branching rules in GCG projects
SCIP_Bool GCGisOriginal(SCIP *scip)
Definition: misc.c:641
SCIP_RETCODE GCGcreateConsMasterbranch(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_NODE *node, SCIP_CONS *parentcons, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata, SCIP_CONS **origbranchconss, int norigbranchconss)
SCIP_CONS * cons
Definition: branch_orig.c:74
constraint handler for storing the branching decisions at each node of the tree
#define branchPropMasterOrig
Definition: branch_orig.c:569
SCIP_Real newbound
Definition: branch_orig.c:70
#define branchDeactiveMasterOrig
Definition: branch_orig.c:568
SCIP_Real olddualbound
Definition: branch_orig.c:73
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 SCIPincludeBranchruleOrig(SCIP *scip)
Definition: branch_orig.c:903
constraint handler for storing the branching decisions at each node of the tree
reliable pseudo costs branching rule
SCIP_RETCODE SCIPgetRelpsprobBranchVar(SCIP *scip, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, int nbranchcands, int nvars, SCIP_RESULT *result, SCIP_VAR **branchvar)
static SCIP_DECL_BRANCHEXECLP(branchExeclpOrig)
Definition: branch_orig.c:664
#define BRANCHRULE_DESC
Definition: branch_orig.c:55
int GCGgetNIdenticalBlocks(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:3966