branch_ryanfoster.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 
33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34 
35 #include <assert.h>
36 #include <string.h>
37 
38 #include "branch_ryanfoster.h"
39 #include "gcg.h"
40 #include "relax_gcg.h"
41 #include "cons_masterbranch.h"
42 #include "cons_origbranch.h"
43 #include "scip/nodesel_bfs.h"
44 #include "scip/nodesel_dfs.h"
45 #include "scip/nodesel_estimate.h"
46 #include "scip/nodesel_hybridestim.h"
47 #include "scip/nodesel_restartdfs.h"
48 #include "scip/branch_allfullstrong.h"
49 #include "scip/branch_fullstrong.h"
50 #include "scip/branch_inference.h"
51 #include "scip/branch_mostinf.h"
52 #include "scip/branch_leastinf.h"
53 #include "scip/branch_pscost.h"
54 #include "scip/branch_random.h"
55 #include "scip/branch_relpscost.h"
56 #include "pricer_gcg.h"
57 #include "scip/cons_varbound.h"
58 #include "type_branchgcg.h"
59 
60 #define BRANCHRULE_NAME "ryanfoster"
61 #define BRANCHRULE_DESC "ryan and foster branching in generic column generation"
62 #define BRANCHRULE_PRIORITY 10
63 #define BRANCHRULE_MAXDEPTH -1
64 #define BRANCHRULE_MAXBOUNDDIST 1.0
65 
66 
68 struct GCG_BranchData
69 {
70  SCIP_VAR* var1;
71  SCIP_VAR* var2;
72  SCIP_Bool same;
73  int blocknr;
74  SCIP_CONS* pricecons;
75 };
76 
77 
78 
79 /*
80  * Callback methods for enforcing branching constraints
81  */
82 
83 
85 static
86 SCIP_DECL_BRANCHCOPY(branchCopyRyanfoster)
87 {
88  assert(branchrule != NULL);
89  assert(scip != NULL);
90  SCIPdebugMessage("pricer copy called.\n");
91 
92  return SCIP_OKAY;
93 }
94 
95 
97 static
98 GCG_DECL_BRANCHACTIVEMASTER(branchActiveMasterRyanfoster)
99 {
100  SCIP* origscip;
101  SCIP* pricingscip;
102 
103  assert(scip != NULL);
104  assert(branchdata != NULL);
105  assert(branchdata->var1 != NULL);
106  assert(branchdata->var2 != NULL);
107 
108  origscip = GCGmasterGetOrigprob(scip);
109  assert(origscip != NULL);
110 
111  pricingscip = GCGgetPricingprob(origscip, branchdata->blocknr);
112  assert(pricingscip != NULL);
113 
114  SCIPdebugMessage("branchActiveMasterRyanfoster: %s(%s, %s)\n", ( branchdata->same ? "same" : "differ" ),
115  SCIPvarGetName(branchdata->var1), SCIPvarGetName(branchdata->var2));
116 
117  assert(GCGvarIsOriginal(branchdata->var1));
119  assert(GCGvarGetBlock(branchdata->var1) == branchdata->blocknr);
120 
121  assert(GCGvarIsOriginal(branchdata->var2));
122  assert(GCGvarGetBlock(branchdata->var2) == branchdata->blocknr);
123 
124  /* create corresponding constraint in the pricing problem, if not yet created */
125  if( branchdata->pricecons == NULL )
126  {
127  char name[SCIP_MAXSTRLEN];
128 
129  if( branchdata->same )
130  {
131  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "same(%s, %s)", SCIPvarGetName(branchdata->var1), SCIPvarGetName(branchdata->var2));
132 
133  SCIP_CALL( SCIPcreateConsVarbound(pricingscip,
134  &(branchdata->pricecons), name, GCGoriginalVarGetPricingVar(branchdata->var1),
135  GCGoriginalVarGetPricingVar(branchdata->var2), -1.0, 0.0, 0.0,
136  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
137  }
138  else
139  {
140  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "differ(%s, %s)", SCIPvarGetName(branchdata->var1), SCIPvarGetName(branchdata->var2));
141 
142  SCIP_CALL( SCIPcreateConsVarbound(pricingscip,
143  &(branchdata->pricecons), name, GCGoriginalVarGetPricingVar(branchdata->var1),
144  GCGoriginalVarGetPricingVar(branchdata->var2), 1.0, -SCIPinfinity(scip), 1.0,
145  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
146  }
147  }
148  /* add constraint to the pricing problem that enforces the branching decision */
149  SCIP_CALL( SCIPaddCons(pricingscip, branchdata->pricecons) );
150 
151  return SCIP_OKAY;
152 }
153 
155 static
156 GCG_DECL_BRANCHDEACTIVEMASTER(branchDeactiveMasterRyanfoster)
157 {
158  SCIP* origscip;
159  SCIP* pricingscip;
160 
161  assert(scip != NULL);
162  assert(branchdata != NULL);
163  assert(branchdata->var1 != NULL);
164  assert(branchdata->var2 != NULL);
165  assert(branchdata->pricecons != NULL);
166 
167  origscip = GCGmasterGetOrigprob(scip);
168  assert(origscip != NULL);
169 
170  pricingscip = GCGgetPricingprob(origscip, branchdata->blocknr);
171  assert(pricingscip != NULL);
172 
173  SCIPdebugMessage("branchDeactiveMasterRyanfoster: %s(%s, %s)\n", ( branchdata->same ? "same" : "differ" ),
174  SCIPvarGetName(branchdata->var1), SCIPvarGetName(branchdata->var2));
175 
176  /* remove constraint from the pricing problem that enforces the branching decision */
177  assert(branchdata->pricecons != NULL);
178  SCIP_CALL( SCIPdelCons(pricingscip, branchdata->pricecons) );
179 
180  return SCIP_OKAY;
181 }
182 
184 static
185 GCG_DECL_BRANCHPROPMASTER(branchPropMasterRyanfoster)
186 {
187  SCIP_VAR** vars;
188  SCIP_Real val1;
189  SCIP_Real val2;
190  int nvars;
191  int propcount;
192  int i;
193  int j;
194 
195  assert(scip != NULL);
196  assert(branchdata != NULL);
197  assert(branchdata->var1 != NULL);
198  assert(branchdata->var2 != NULL);
199  assert(branchdata->pricecons != NULL);
200 
201  assert(GCGmasterGetOrigprob(scip) != NULL);
202 
203  SCIPdebugMessage("branchPropMasterRyanfoster: %s(%s, %s)\n", ( branchdata->same ? "same" : "differ" ),
204  SCIPvarGetName(branchdata->var1), SCIPvarGetName(branchdata->var2));
205 
206  *result = SCIP_DIDNOTFIND;
207 
208  propcount = 0;
209 
210  vars = SCIPgetVars(scip);
211  nvars = SCIPgetNVars(scip);
212 
213  /* iterate over all master variables */
214  for( i = 0; i < nvars; i++ )
215  {
216  int norigvars;
217  SCIP_Real* origvals;
218  SCIP_VAR** origvars;
219 
220  origvars = GCGmasterVarGetOrigvars(vars[i]);
221  origvals = GCGmasterVarGetOrigvals(vars[i]);
222  norigvars = GCGmasterVarGetNOrigvars(vars[i]);
223 
224  /* only look at variables not fixed to 0 */
225  if( !SCIPisFeasZero(scip, SCIPvarGetUbLocal(vars[i])) )
226  {
227  assert(GCGvarIsMaster(vars[i]));
228 
229  /* if variable belongs to a different block than the branching restriction, we do not have to look at it */
230  if( branchdata->blocknr != GCGvarGetBlock(vars[i]) )
231  continue;
232 
233  /* save the values of the original variables for the current master variable */
234  val1 = 0.0;
235  val2 = 0.0;
236  for( j = 0; j < norigvars; j++ )
237  {
238  if( origvars[j] == branchdata->var1 )
239  {
240  val1 = origvals[j];
241  continue;
242  }
243  if( origvars[j] == branchdata->var2 )
244  {
245  val2 = origvals[j];
246  }
247  }
248 
249  /* if branching enforces that both original vars are either both contained or none of them is contained
250  * and the current master variable has different values for both of them, fix the variable to 0 */
251  if( branchdata->same && !SCIPisEQ(scip, val1, val2) )
252  {
253  SCIP_CALL( SCIPchgVarUb(scip, vars[i], 0.0) );
254  propcount++;
255  }
256  /* if branching enforces that both original vars must be in different mastervars, fix all
257  * master variables to 0 that contain both */
258  if( !branchdata->same && SCIPisEQ(scip, val1, 1.0) && SCIPisEQ(scip, val2, 1.0) )
259  {
260  SCIP_CALL( SCIPchgVarUb(scip, vars[i], 0.0) );
261  propcount++;
262  }
263  }
264  }
265 
266  SCIPdebugMessage("Finished propagation of branching decision constraint: %s(%s, %s), %d vars fixed.\n",
267  ( branchdata->same ? "same" : "differ" ), SCIPvarGetName(branchdata->var1), SCIPvarGetName(branchdata->var2), propcount);
268 
269  if( propcount > 0 )
270  {
271  *result = SCIP_REDUCEDDOM;
272  }
273 
274  return SCIP_OKAY;
275 }
276 
278 static
279 GCG_DECL_BRANCHDATADELETE(branchDataDeleteRyanfoster)
280 {
281  assert(scip != NULL);
282  assert(branchdata != NULL);
283 
284  SCIPdebugMessage("branchDataDeleteRyanfoster: %s(%s, %s)\n", ( (*branchdata)->same ? "same" : "differ" ),
285  SCIPvarGetName((*branchdata)->var1), SCIPvarGetName((*branchdata)->var2));
286 
287  /* release constraint that enforces the branching decision */
288  if( (*branchdata)->pricecons != NULL )
289  {
290  SCIP_CALL( SCIPreleaseCons(GCGgetPricingprob(scip, (*branchdata)->blocknr),
291  &(*branchdata)->pricecons) );
292  }
293 
294  SCIPfreeBlockMemory(scip, branchdata);
295  *branchdata = NULL;
296 
297  return SCIP_OKAY;
298 }
299 
300 /*
301  * Callback methods
302  */
303 
305 static
307  SCIP* scip,
308  SCIP_BRANCHRULE* branchrule,
309  SCIP_VAR* ovar1,
310  SCIP_VAR* ovar2,
311  int blocknr
312  )
313 {
314  SCIP* masterscip;
315  SCIP_VAR* pricingvar1;
316  SCIP_VAR* pricingvar2;
317  GCG_BRANCHDATA* branchsamedata;
318  GCG_BRANCHDATA* branchdifferdata;
319  char samename[SCIP_MAXSTRLEN];
320  char differname[SCIP_MAXSTRLEN];
321 
322  SCIP_VAR** origvars1;
323  SCIP_VAR** origvars2;
324  int norigvars1;
325  int v;
326 
327  SCIP_NODE* child1;
328  SCIP_NODE* child2;
329  SCIP_CONS* cons1;
330  SCIP_CONS* cons2;
331  SCIP_CONS** origbranchconss1;
332  SCIP_CONS** origbranchconss2;
333 
334 
335  assert(scip != NULL);
336  assert(branchrule != NULL);
337  assert(ovar1 != NULL);
338  assert(ovar2 != NULL);
339  assert(GCGvarIsOriginal(ovar1));
340  assert(GCGvarIsOriginal(ovar2));
341 
342  origbranchconss1 = NULL;
343  origbranchconss2 = NULL;
344 
345  masterscip = GCGgetMasterprob(scip);
346  assert(masterscip != NULL);
347 
348  SCIPdebugMessage("Ryanfoster branching rule: branch on original variables %s and %s!\n",
349  SCIPvarGetName(ovar1), SCIPvarGetName(ovar2));
350 
351  /* for cons_masterbranch */
352 
353  /* create two child-nodes of the current node in the b&b-tree */
354  SCIP_CALL( SCIPcreateChild(masterscip, &child1, 0.0, SCIPgetLocalTransEstimate(masterscip)) );
355  SCIP_CALL( SCIPcreateChild(masterscip, &child2, 0.0, SCIPgetLocalTransEstimate(masterscip)) );
356 
357  /* allocate branchdata for same child and store information */
358  SCIP_CALL( SCIPallocBlockMemory(scip, &branchsamedata) );
359  branchsamedata->var1 = ovar1;
360  branchsamedata->var2 = ovar2;
361  branchsamedata->same = TRUE;
362  branchsamedata->blocknr = blocknr;
363  branchsamedata->pricecons = NULL;
364 
365  /* allocate branchdata for differ child and store information */
366  SCIP_CALL( SCIPallocBlockMemory(scip, &branchdifferdata) );
367  branchdifferdata->var1 = ovar1;
368  branchdifferdata->var2 = ovar2;
369  branchdifferdata->same = FALSE;
370  branchdifferdata->blocknr = blocknr;
371  branchdifferdata->pricecons = NULL;
372 
373  /* define names for origbranch constraints */
374  (void) SCIPsnprintf(samename, SCIP_MAXSTRLEN, "same(%s, %s)", SCIPvarGetName(branchsamedata->var1),
375  SCIPvarGetName(branchsamedata->var2));
376 
377  (void) SCIPsnprintf(differname, SCIP_MAXSTRLEN, "differ(%s, %s)", SCIPvarGetName(branchsamedata->var1),
378  SCIPvarGetName(branchsamedata->var2));
379 
380  pricingvar1 = GCGoriginalVarGetPricingVar(branchdifferdata->var1);
381  pricingvar2 = GCGoriginalVarGetPricingVar(branchdifferdata->var2);
382  assert(GCGvarIsPricing(pricingvar1));
383  assert(GCGvarIsPricing(pricingvar2));
384  assert(GCGvarGetBlock(pricingvar1) == GCGvarGetBlock(pricingvar2));
385  assert(GCGpricingVarGetNOrigvars(pricingvar1) == GCGpricingVarGetNOrigvars(pricingvar2));
386 
387  norigvars1 = GCGpricingVarGetNOrigvars(pricingvar1);
388  assert(norigvars1 == GCGpricingVarGetNOrigvars(pricingvar2));
389 
390  origvars1 = GCGpricingVarGetOrigvars(pricingvar1);
391  origvars2 = GCGpricingVarGetOrigvars(pricingvar2);
392 
393  if( norigvars1 > 0 )
394  {
395  SCIP_CALL( SCIPallocMemoryArray(scip, &origbranchconss1, norigvars1) );
396  BMSclearMemoryArray(origbranchconss1, norigvars1);
397  SCIP_CALL( SCIPallocMemoryArray(scip, &origbranchconss2, norigvars1) );
398  BMSclearMemoryArray(origbranchconss2, norigvars1);
399  }
400 
401  /* add branching decision as varbound constraints to original problem */
402  for( v = 0; v < norigvars1; v++ )
403  {
404  SCIP_CONS* origcons;
405  SCIP_CONS* origcons2;
406 
407  assert(GCGvarGetBlock(origvars1[v]) == GCGvarGetBlock(origvars2[v]));
408  assert(origbranchconss1 != NULL);
409  assert(origbranchconss2 != NULL);
410 
411  /* create constraint for same-child */
412  SCIP_CALL( SCIPcreateConsVarbound(scip, &origcons, samename, origvars1[v], origvars2[v],
413  -1.0, 0.0, 0.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
414 
415  origbranchconss1[v] = origcons;
416 
417  /* create constraint for differ-child */
418  SCIP_CALL( SCIPcreateConsVarbound(scip, &origcons2, differname, origvars1[v], origvars2[v],
419  1.0, -SCIPinfinity(scip), 1.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
420 
421  origbranchconss2[v] = origcons2;
422  }
423 
424  /* create and add the masterbranch constraints */
425  SCIP_CALL( GCGcreateConsMasterbranch(masterscip, &cons1, samename, child1,
426  GCGconsMasterbranchGetActiveCons(masterscip), branchrule, branchsamedata, origbranchconss1, norigvars1) );
427  SCIP_CALL( GCGcreateConsMasterbranch(masterscip, &cons2, differname, child2,
428  GCGconsMasterbranchGetActiveCons(masterscip), branchrule, branchdifferdata, origbranchconss2, norigvars1) );
429  SCIP_CALL( SCIPaddConsNode(masterscip, child1, cons1, NULL) );
430  SCIP_CALL( SCIPaddConsNode(masterscip, child2, cons2, NULL) );
431 
432  /* release constraints */
433  SCIP_CALL( SCIPreleaseCons(masterscip, &cons1) );
434  SCIP_CALL( SCIPreleaseCons(masterscip, &cons2) );
435  return SCIP_OKAY;
436 }
437 
439 static
440 SCIP_DECL_BRANCHEXECLP(branchExeclpRyanfoster)
441 { /*lint --e{715}*/
442  SCIP* origscip;
443  SCIP_Bool feasible;
444 
445  SCIP_VAR** branchcands;
446  int nbranchcands;
447 
448  int v1;
449 
450  SCIP_VAR* mvar1;
451  SCIP_VAR* ovar1;
452  SCIP_VAR* ovar2;
453 
454  assert(branchrule != NULL);
455  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
456  assert(scip != NULL);
457  assert(result != NULL);
458 
459  SCIPdebugMessage("Execrel method of ryanfoster branching\n");
460 
461  origscip = GCGmasterGetOrigprob(scip);
462  assert(origscip != NULL);
463 
464  *result = SCIP_DIDNOTRUN;
465 
466  /* do not perform Ryan & Foster branching if we have neither a set partitioning nor a set covering structure */
467  if( !GCGisMasterSetCovering(origscip) && !GCGisMasterSetPartitioning(origscip) )
468  {
469  SCIPdebugMessage("Not executing Ryan&Foster branching, master is neither set covering nor set partitioning\n");
470  return SCIP_OKAY;
471  }
472 
474  {
475  SCIPdebugMessage("Not executing Ryan&Foster branching, node was branched by generic branchrule\n");
476  return SCIP_OKAY;
477  }
478 
479  if( GCGrelaxIsOrigSolFeasible(origscip) )
480  {
481  SCIPdebugMessage("node cut off, since origsol was feasible, solval = %f\n",
482  SCIPgetSolOrigObj(origscip, GCGrelaxGetCurrentOrigSol(origscip)));
483 
484  *result = SCIP_DIDNOTFIND;
485 
486  return SCIP_OKAY;
487  }
488 
489  /* the current original solution is not integral, now we have to branch;
490  * first, get the master problem and all variables of the master problem
491  */
492  SCIP_CALL( SCIPgetLPBranchCands(scip, &branchcands, NULL, NULL, &nbranchcands, NULL, NULL) );
493 
494  /* now search for two (fractional) columns mvar1, mvar2 in the master and 2 original variables ovar1, ovar2
495  * s.t. mvar1 contains both ovar1 and ovar2 and mvar2 contains ovar1, but not ovar2
496  */
497  ovar1 = NULL;
498  ovar2 = NULL;
499  mvar1 = NULL;
500  feasible = FALSE;
501 
502  /* select first fractional column (mvar1) */
503  for( v1 = 0; v1 < nbranchcands && !feasible; v1++ )
504  {
505  int o1;
506  int j;
507 
508  SCIP_VAR** origvars1;
509  int norigvars1;
510  SCIP_VAR* mvar2 = NULL;
511 
512  mvar1 = branchcands[v1];
513  assert(GCGvarIsMaster(mvar1));
514 
515  origvars1 = GCGmasterVarGetOrigvars(mvar1);
516  norigvars1 = GCGmasterVarGetNOrigvars(mvar1);
517 
518  /* select first original variable ovar1, that should be contained in both master variables */
519  for( o1 = 0; o1 < norigvars1 && !feasible; o1++ )
520  {
521  int v2;
522 
523  ovar1 = origvars1[o1];
524  /* if we deal with a trivial variable, skip it */
525  if( SCIPisZero(origscip, GCGmasterVarGetOrigvals(mvar1)[o1]) || GCGoriginalVarGetNCoefs(ovar1) == 0 )
526  continue;
527 
528  /* mvar1 contains ovar1, look for mvar2 which constains ovar1, too */
529  for( v2 = v1+1; v2 < nbranchcands && !feasible; v2++ )
530  {
531  SCIP_VAR** origvars2;
532  int norigvars2;
533  int o2;
534  SCIP_Bool contained = FALSE;
535 
536  mvar2 = branchcands[v2];
537  assert(GCGvarIsMaster(mvar2));
538 
539  origvars2 = GCGmasterVarGetOrigvars(mvar2);
540  norigvars2 = GCGmasterVarGetNOrigvars(mvar2);
541 
542  /* check whether ovar1 is contained in mvar2, too */
543  for( j = 0; j < norigvars2; j++ )
544  {
545  /* if we deal with a trivial variable, skip it */
546  if( SCIPisZero(origscip, GCGmasterVarGetOrigvals(mvar2)[j]) || GCGoriginalVarGetNCoefs(origvars2[j]) == 0 )
547  continue;
548 
549  if( origvars2[j] == ovar1 )
550  {
551  contained = TRUE;
552  break;
553  }
554  }
555 
556  /* mvar2 does not contain ovar1, so look for another mvar2 */
557  if( !contained )
558  continue;
559 
560  /* mvar2 also contains ovar1, now look for ovar2 contained in mvar1, but not in mvar2 */
561  for( o2 = 0; o2 < norigvars1; o2++ )
562  {
563  /* if we deal with a trivial variable, skip it */
564  if( !SCIPisZero(origscip, GCGmasterVarGetOrigvals(mvar1)[o2]) || GCGoriginalVarGetNCoefs(origvars1[o2]) == 0 )
565  continue;
566 
567  ovar2 = origvars1[o2];
568  if( ovar2 == ovar1 )
569  continue;
570 
571  /* check whether ovar2 is contained in mvar2, too */
572  contained = FALSE;
573  for( j = 0; j < norigvars2; j++ )
574  {
575  /* if we deal with a trivial variable, skip it */
576  if( !SCIPisZero(origscip, GCGmasterVarGetOrigvals(mvar2)[j]) )
577  continue;
578 
579  if( origvars2[j] == ovar2 )
580  {
581  contained = TRUE;
582  break;
583  }
584  }
585 
586  /* ovar2 should be contained in mvar1 but not in mvar2, so look for another ovar2,
587  * if the current one is contained in mvar2
588  */
589  if( contained )
590  continue;
591 
592  /* if we arrive here, ovar2 is contained in mvar1 but not in mvar2, so everything is fine */
593  feasible = TRUE;
594  break;
595  }
596 
597  /* we did not find an ovar2 contained in mvar1, but not in mvar2,
598  * now look for one contained in mvar2, but not in mvar1
599  */
600  if( !feasible )
601  {
602  for( o2 = 0; o2 < norigvars2; o2++ )
603  {
604  /* if we deal with a trivial variable, skip it */
605  if( SCIPisZero(origscip, GCGmasterVarGetOrigvals(mvar2)[o2]) || GCGoriginalVarGetNCoefs(origvars2[o2]) == 0 )
606  continue;
607 
608  ovar2 = origvars2[o2];
609 
610  if( ovar2 == ovar1 )
611  continue;
612 
613  contained = FALSE;
614  for( j = 0; j < norigvars1; j++ )
615  {
616  /* if we deal with a trivial variable, skip it */
617  if( SCIPisZero(origscip, GCGmasterVarGetOrigvals(mvar1)[j]) || GCGoriginalVarGetNCoefs(origvars1[j]) == 0 )
618  continue;
619  if( origvars1[j] == ovar2 )
620  {
621  contained = TRUE;
622  break;
623  }
624  }
625 
626  /* ovar2 should be contained in mvar2 but not in mvar1, so look for another ovar2,
627  * if the current one is contained in mvar1
628  */
629  if( contained )
630  continue;
631 
632  /* if we arrive here, ovar2 is contained in mvar2 but not in mvar1, so everything is fine */
633  feasible = TRUE;
634  break;
635  }
636  }
637  }
638  }
639  }
640 
641  if( !feasible )
642  {
643  SCIPdebugMessage("Ryanfoster branching rule could not find variables to branch on!\n");
644  return SCIP_OKAY;
645  }
646 
647  /* create the two child nodes in the branch-and-bound tree */
648  SCIP_CALL( createChildNodesRyanfoster(origscip, branchrule, ovar1, ovar2, GCGvarGetBlock(mvar1)) );
649 
650  *result = SCIP_BRANCHED;
651 
652  return SCIP_OKAY;
653 }
654 
656 static
657 SCIP_DECL_BRANCHEXECEXT(branchExecextRyanfoster)
658 { /*lint --e{715}*/
659 
660  *result = SCIP_DIDNOTRUN;
661 
662  return SCIP_OKAY;
663 
664 }
665 
667 static
668 SCIP_DECL_BRANCHEXECPS(branchExecpsRyanfoster)
669 { /*lint --e{715}*/
670  SCIP_CONS** origbranchconss;
671  GCG_BRANCHDATA* branchdata;
672  SCIP_VAR** branchcands;
673  SCIP_VAR* ovar1;
674  SCIP_VAR* ovar2;
675  SCIP_Bool feasible;
676  int norigbranchconss;
677  int nbranchcands;
678  int o1;
679  int o2;
680  int c;
681 
682  SCIP* origscip;
683 
684  assert(branchrule != NULL);
685  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
686  assert(scip != NULL);
687  assert(result != NULL);
688 
689  SCIPdebugMessage("Execps method of ryanfoster branching\n");
690 
691  origscip = GCGmasterGetOrigprob(scip);
692  assert(origscip != NULL);
693 
694 
695  *result = SCIP_DIDNOTRUN;
696 
697  /* do not perform Ryan & Foster branching if we have neither a set partitioning nor a set covering structure */
698  if( !GCGisMasterSetCovering(origscip) || !GCGisMasterSetPartitioning(origscip) )
699  {
700  SCIPdebugMessage("Not executing Ryanfoster branching, master is neither set covering nor set partitioning\n");
701  return SCIP_OKAY;
702  }
703 
705  {
706  SCIPdebugMessage("Not executing Ryanfoster branching, node was branched by generic branchrule\n");
707  return SCIP_OKAY;
708  }
709 
710  /* get unfixed variables and stack of active origbranchconss */
711  SCIP_CALL( SCIPgetPseudoBranchCands(origscip, &branchcands, NULL, &nbranchcands) );
712  GCGconsOrigbranchGetStack(origscip, &origbranchconss, &norigbranchconss);
713 
714  ovar1 = NULL;
715  ovar2 = NULL;
716  feasible = FALSE;
717 
718  /* select first original variable ovar1 */
719  for( o1 = 0; o1 < nbranchcands && !feasible; ++o1 )
720  {
721  ovar1 = branchcands[o1];
722 
723  /* select second original variable o2 */
724  for( o2 = o1 + 1; o2 < nbranchcands; ++o2 )
725  {
726  ovar2 = branchcands[o2];
727 
728  assert(ovar2 != ovar1);
729 
730  /* check whether we already branched on this combination of variables */
731  for( c = 0; c < norigbranchconss; ++c )
732  {
733  if( GCGconsOrigbranchGetBranchrule(origbranchconss[c]) == branchrule )
734  continue;
735 
736  branchdata = GCGconsOrigbranchGetBranchdata(origbranchconss[c]);
737 
738  if( (branchdata->var1 == ovar1 && branchdata->var2 == ovar2 )
739  || (branchdata->var1 == ovar2 && branchdata->var2 == ovar1) )
740  {
741  break;
742  }
743  }
744 
745  /* we did not break, so there is no active origbranch constraint with both variables */
746  if( c == norigbranchconss )
747  {
748  feasible = TRUE;
749  break;
750  }
751  }
752  }
753 
754  if( !feasible )
755  {
756  SCIPdebugMessage("Ryanfoster branching rule could not find variables to branch on!\n");
757  return SCIP_OKAY;
758  }
759 
760  /* create the two child nodes in the branch-and-bound tree */
761  SCIP_CALL( createChildNodesRyanfoster(origscip, branchrule, ovar1, ovar2, GCGvarGetBlock(ovar1)) );
762 
763  *result = SCIP_BRANCHED;
764 
765  return SCIP_OKAY;
766 }
767 
769 static
770 SCIP_DECL_BRANCHINIT(branchInitRyanfoster)
771 {
772  SCIP* origprob;
773 
774  origprob = GCGmasterGetOrigprob(scip);
775  assert(branchrule != NULL);
776  assert(origprob != NULL);
777 
778  SCIP_CALL( GCGrelaxIncludeBranchrule(origprob, branchrule, branchActiveMasterRyanfoster,
779  branchDeactiveMasterRyanfoster, branchPropMasterRyanfoster, NULL, branchDataDeleteRyanfoster) );
780 
781  return SCIP_OKAY;
782 }
783 
784 
785 
786 /* define not used callback as NULL*/
787 #define branchFreeRyanfoster NULL
788 #define branchExitRyanfoster NULL
789 #define branchInitsolRyanfoster NULL
790 #define branchExitsolRyanfoster NULL
791 
792 
793 /*
794  * branching specific interface methods
795  */
796 
799  SCIP* scip
800  )
801 {
802  SCIP_BRANCHRULEDATA* branchruledata;
803 
804  /* create branching rule data */
805  branchruledata = NULL;
806 
807  /* include branching rule */
808  SCIP_CALL( SCIPincludeBranchrule(scip, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
809  BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchCopyRyanfoster,
811  branchExitsolRyanfoster, branchExeclpRyanfoster, branchExecextRyanfoster, branchExecpsRyanfoster,
812  branchruledata) );
813 
814  return SCIP_OKAY;
815 }
static SCIP_DECL_BRANCHCOPY(branchCopyRyanfoster)
SCIP_Bool GCGisMasterSetCovering(SCIP *scip)
Definition: relax_gcg.c:4131
GCG_BRANCHDATA * GCGconsOrigbranchGetBranchdata(SCIP_CONS *cons)
#define BRANCHRULE_NAME
SCIP_Bool GCGvarIsOriginal(SCIP_VAR *var)
Definition: gcgvar.c:162
static SCIP_DECL_BRANCHEXECPS(branchExecpsRyanfoster)
static GCG_DECL_BRANCHDEACTIVEMASTER(branchDeactiveMasterRyanfoster)
#define BRANCHRULE_PRIORITY
GCG interface methods.
#define BRANCHRULE_MAXDEPTH
SCIP * GCGgetPricingprob(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:3857
static SCIP_DECL_BRANCHEXECLP(branchExeclpRyanfoster)
SCIP_CONS * GCGconsMasterbranchGetActiveCons(SCIP *scip)
static SCIP_RETCODE createChildNodesRyanfoster(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR *ovar1, SCIP_VAR *ovar2, int blocknr)
SCIP_Bool GCGisMasterSetPartitioning(SCIP *scip)
Definition: relax_gcg.c:4150
SCIP * GCGgetMasterprob(SCIP *scip)
Definition: relax_gcg.c:3838
SCIP_Bool GCGvarIsMaster(SCIP_VAR *var)
Definition: gcgvar.c:148
int GCGoriginalVarGetNCoefs(SCIP_VAR *var)
Definition: gcgvar.c:609
SCIP_SOL * GCGrelaxGetCurrentOrigSol(SCIP *scip)
Definition: relax_gcg.c:4093
#define BRANCHRULE_DESC
static SCIP_DECL_BRANCHINIT(branchInitRyanfoster)
SCIP_BRANCHRULE * GCGconsOrigbranchGetBranchrule(SCIP_CONS *cons)
SCIP_VAR ** GCGpricingVarGetOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:920
#define BRANCHRULE_MAXBOUNDDIST
static SCIP_DECL_BRANCHEXECEXT(branchExecextRyanfoster)
GCG relaxator.
SCIP_CONS * pricecons
GCG variable pricer.
SCIP_Real * GCGmasterVarGetOrigvals(SCIP_VAR *var)
Definition: gcgvar.c:888
int GCGvarGetBlock(SCIP_VAR *var)
Definition: gcgvar.c:936
static GCG_DECL_BRANCHPROPMASTER(branchPropMasterRyanfoster)
static GCG_DECL_BRANCHDATADELETE(branchDataDeleteRyanfoster)
#define branchInitsolRyanfoster
SCIP_Bool GCGcurrentNodeIsGeneric(SCIP *scip)
SCIP * GCGmasterGetOrigprob(SCIP *scip)
SCIP_Bool GCGrelaxIsOrigSolFeasible(SCIP *scip)
Definition: relax_gcg.c:4112
SCIP_Bool GCGvarIsPricing(SCIP_VAR *var)
Definition: gcgvar.c:133
type definitions for branching rules in GCG projects
static GCG_DECL_BRANCHACTIVEMASTER(branchActiveMasterRyanfoster)
int GCGpricingVarGetNOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:904
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)
branching rule for original problem in GCG implementing the Ryan and Foster branching scheme ...
constraint handler for storing the branching decisions at each node of the tree
int GCGmasterVarGetNOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:846
void GCGconsOrigbranchGetStack(SCIP *scip, SCIP_CONS ***stack, int *nstackelements)
SCIP_RETCODE SCIPincludeBranchruleRyanfoster(SCIP *scip)
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
constraint handler for storing the branching decisions at each node of the tree
#define branchFreeRyanfoster
SCIP_VAR ** GCGmasterVarGetOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:866
#define branchExitRyanfoster
SCIP_VAR * GCGoriginalVarGetPricingVar(SCIP_VAR *var)
Definition: gcgvar.c:206
#define branchExitsolRyanfoster