Scippy

GCG

Branch-and-Price & Column Generation for Everyone

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-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_ryanfoster.c
29  * @brief branching rule for original problem in GCG implementing the Ryan and Foster branching scheme
30  * @author Gerald Gamrath
31  * @author Oliver Gaul
32  */
33 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 /*#define SCIP_DEBUG*/
36 #include <assert.h>
37 #include <string.h>
38 
39 #include "branch_ryanfoster.h"
40 #include "branch_bpstrong.h"
41 #include "gcg.h"
42 #include "relax_gcg.h"
43 #include "cons_masterbranch.h"
44 #include "cons_origbranch.h"
45 #include "scip/nodesel_bfs.h"
46 #include "scip/nodesel_dfs.h"
47 #include "scip/nodesel_estimate.h"
48 #include "scip/nodesel_hybridestim.h"
49 #include "scip/nodesel_restartdfs.h"
50 #include "scip/branch_allfullstrong.h"
51 #include "scip/branch_fullstrong.h"
52 #include "scip/branch_inference.h"
53 #include "scip/branch_mostinf.h"
54 #include "scip/branch_leastinf.h"
55 #include "scip/branch_pscost.h"
56 #include "scip/branch_random.h"
57 #include "scip/branch_relpscost.h"
58 #include "pricer_gcg.h"
59 #include "scip/cons_varbound.h"
60 #include "type_branchgcg.h"
61 
62 #define BRANCHRULE_NAME "ryanfoster"
63 #define BRANCHRULE_DESC "ryan and foster branching in generic column generation"
64 #define BRANCHRULE_PRIORITY 10
65 #define BRANCHRULE_MAXDEPTH -1
66 #define BRANCHRULE_MAXBOUNDDIST 1.0
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 data for branching decisions */
84 struct GCG_BranchData
85 {
86  SCIP_VAR* var1; /**< first original variable on which the branching is done */
87  SCIP_VAR* var2; /**< second original variable on which the branching is done */
88  SCIP_Bool same; /**< should each master var contain either both or none of the vars? */
89  int blocknr; /**< number of the block in which branching was performed */
90  SCIP_CONS* pricecons; /**< constraint enforcing the branching restriction in the pricing problem */
91 };
92 
93 
94 
95 /*
96  * Callback methods for enforcing branching constraints
97  */
98 
99 
100 /** copy method for master branching rule */
101 static
102 SCIP_DECL_BRANCHCOPY(branchCopyRyanfoster)
103 {
104  assert(branchrule != NULL);
105  assert(scip != NULL);
106  SCIPdebugMessage("pricer copy called.\n");
107 
108  return SCIP_OKAY;
109 }
110 
111 
112 /** callback activation method */
113 static
114 GCG_DECL_BRANCHACTIVEMASTER(branchActiveMasterRyanfoster)
115 {
116  SCIP* origscip;
117  SCIP* pricingscip;
118 
119  assert(scip != NULL);
120  assert(branchdata != NULL);
121  assert(branchdata->var1 != NULL);
122  assert(branchdata->var2 != NULL);
123 
124  origscip = GCGmasterGetOrigprob(scip);
125  assert(origscip != NULL);
126 
127  pricingscip = GCGgetPricingprob(origscip, branchdata->blocknr);
128  assert(pricingscip != NULL);
129 
130  SCIPdebugMessage("branchActiveMasterRyanfoster: %s(%s, %s)\n", ( branchdata->same ? "same" : "differ" ),
131  SCIPvarGetName(branchdata->var1), SCIPvarGetName(branchdata->var2));
132 
133  assert(GCGvarIsOriginal(branchdata->var1));
134  /** @todo it is not clear if linking variables interfere with ryan foster branching */
135  assert(GCGvarGetBlock(branchdata->var1) == branchdata->blocknr);
136 
137  assert(GCGvarIsOriginal(branchdata->var2));
138  assert(GCGvarGetBlock(branchdata->var2) == branchdata->blocknr);
139 
140  /* create corresponding constraint in the pricing problem, if not yet created */
141  if( branchdata->pricecons == NULL )
142  {
143  char name[SCIP_MAXSTRLEN];
144 
145  if( branchdata->same )
146  {
147  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "same(%s,%s)", SCIPvarGetName(branchdata->var1), SCIPvarGetName(branchdata->var2));
148 
149  SCIP_CALL( SCIPcreateConsVarbound(pricingscip,
150  &(branchdata->pricecons), name, GCGoriginalVarGetPricingVar(branchdata->var1),
151  GCGoriginalVarGetPricingVar(branchdata->var2), -1.0, 0.0, 0.0,
152  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
153  }
154  else
155  {
156  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "differ(%s,%s)", SCIPvarGetName(branchdata->var1), SCIPvarGetName(branchdata->var2));
157 
158  SCIP_CALL( SCIPcreateConsVarbound(pricingscip,
159  &(branchdata->pricecons), name, GCGoriginalVarGetPricingVar(branchdata->var1),
160  GCGoriginalVarGetPricingVar(branchdata->var2), 1.0, -SCIPinfinity(scip), 1.0,
161  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
162  }
163  }
164  /* add constraint to the pricing problem that enforces the branching decision */
165  SCIP_CALL( SCIPaddCons(pricingscip, branchdata->pricecons) );
166 
167  return SCIP_OKAY;
168 }
169 
170 /** callback deactivation method */
171 static
172 GCG_DECL_BRANCHDEACTIVEMASTER(branchDeactiveMasterRyanfoster)
173 {
174  SCIP* origscip;
175  SCIP* pricingscip;
176 
177  assert(scip != NULL);
178  assert(branchdata != NULL);
179  assert(branchdata->var1 != NULL);
180  assert(branchdata->var2 != NULL);
181  assert(branchdata->pricecons != NULL);
182 
183  origscip = GCGmasterGetOrigprob(scip);
184  assert(origscip != NULL);
185 
186  pricingscip = GCGgetPricingprob(origscip, branchdata->blocknr);
187  assert(pricingscip != NULL);
188 
189  SCIPdebugMessage("branchDeactiveMasterRyanfoster: %s(%s, %s)\n", ( branchdata->same ? "same" : "differ" ),
190  SCIPvarGetName(branchdata->var1), SCIPvarGetName(branchdata->var2));
191 
192  /* remove constraint from the pricing problem that enforces the branching decision */
193  assert(branchdata->pricecons != NULL);
194  SCIP_CALL( SCIPdelCons(pricingscip, branchdata->pricecons) );
195 
196  return SCIP_OKAY;
197 }
198 
199 /** callback propagation method */
200 static
201 GCG_DECL_BRANCHPROPMASTER(branchPropMasterRyanfoster)
202 {
203  SCIP_VAR** vars;
204  SCIP_Real val1;
205  SCIP_Real val2;
206  int nvars;
207  int propcount;
208  int i;
209  int j;
210 
211  assert(scip != NULL);
212  assert(branchdata != NULL);
213  assert(branchdata->var1 != NULL);
214  assert(branchdata->var2 != NULL);
215  assert(branchdata->pricecons != NULL);
216 
217  assert(GCGmasterGetOrigprob(scip) != NULL);
218 
219  SCIPdebugMessage("branchPropMasterRyanfoster: %s(%s, %s)\n", ( branchdata->same ? "same" : "differ" ),
220  SCIPvarGetName(branchdata->var1), SCIPvarGetName(branchdata->var2));
221 
222  *result = SCIP_DIDNOTFIND;
223 
224  propcount = 0;
225 
226  vars = SCIPgetVars(scip);
227  nvars = SCIPgetNVars(scip);
228 
229  /* iterate over all master variables */
230  for( i = 0; i < nvars; i++ )
231  {
232  int norigvars;
233  SCIP_Real* origvals;
234  SCIP_VAR** origvars;
235 
236  origvars = GCGmasterVarGetOrigvars(vars[i]);
237  origvals = GCGmasterVarGetOrigvals(vars[i]);
238  norigvars = GCGmasterVarGetNOrigvars(vars[i]);
239 
240  /* only look at variables not fixed to 0 */
241  if( !SCIPisFeasZero(scip, SCIPvarGetUbLocal(vars[i])) )
242  {
243  assert(GCGvarIsMaster(vars[i]));
244 
245  /* if variable belongs to a different block than the branching restriction, we do not have to look at it */
246  if( branchdata->blocknr != GCGvarGetBlock(vars[i]) )
247  continue;
248 
249  /* save the values of the original variables for the current master variable */
250  val1 = 0.0;
251  val2 = 0.0;
252  for( j = 0; j < norigvars; j++ )
253  {
254  if( origvars[j] == branchdata->var1 )
255  {
256  val1 = origvals[j];
257  continue;
258  }
259  if( origvars[j] == branchdata->var2 )
260  {
261  val2 = origvals[j];
262  }
263  }
264 
265  /* if branching enforces that both original vars are either both contained or none of them is contained
266  * and the current master variable has different values for both of them, fix the variable to 0 */
267  if( branchdata->same && !SCIPisEQ(scip, val1, val2) )
268  {
269  SCIP_CALL( SCIPchgVarUb(scip, vars[i], 0.0) );
270  propcount++;
271  }
272  /* if branching enforces that both original vars must be in different mastervars, fix all
273  * master variables to 0 that contain both */
274  if( !branchdata->same && SCIPisEQ(scip, val1, 1.0) && SCIPisEQ(scip, val2, 1.0) )
275  {
276  SCIP_CALL( SCIPchgVarUb(scip, vars[i], 0.0) );
277  propcount++;
278  }
279  }
280  }
281 
282  SCIPdebugMessage("Finished propagation of branching decision constraint: %s(%s, %s), %d vars fixed.\n",
283  ( branchdata->same ? "same" : "differ" ), SCIPvarGetName(branchdata->var1), SCIPvarGetName(branchdata->var2), propcount);
284 
285  if( propcount > 0 )
286  {
287  *result = SCIP_REDUCEDDOM;
288  }
289 
290  return SCIP_OKAY;
291 }
292 
293 /** callback deletion method for branching data*/
294 static
295 GCG_DECL_BRANCHDATADELETE(branchDataDeleteRyanfoster)
296 {
297  assert(scip != NULL);
298  assert(branchdata != NULL);
299 
300  SCIPdebugMessage("branchDataDeleteRyanfoster: %s(%s, %s)\n", ( (*branchdata)->same ? "same" : "differ" ),
301  SCIPvarGetName((*branchdata)->var1), SCIPvarGetName((*branchdata)->var2));
302 
303  /* release constraint that enforces the branching decision */
304  if( (*branchdata)->pricecons != NULL )
305  {
306  SCIP_CALL( SCIPreleaseCons(GCGgetPricingprob(scip, (*branchdata)->blocknr),
307  &(*branchdata)->pricecons) );
308  }
309 
310  SCIPfreeBlockMemory(scip, branchdata);
311  *branchdata = NULL;
312 
313  return SCIP_OKAY;
314 }
315 
316 /*
317  * Callback methods
318  */
319 
320 /** for the two given original variables, create two Ryan&Foster branching nodes, one for same, one for differ */
321 static
323  SCIP* scip, /**< SCIP data structure */
324  SCIP_BRANCHRULE* branchrule, /**< branching rule */
325  SCIP_VAR* ovar1, /**< first original variable */
326  SCIP_VAR* ovar2, /**< second original variable */
327  int blocknr, /**< number of the pricing block */
328  SCIP_Bool sameinf, /**< is the samebranch known to be infeasible? */
329  SCIP_Bool differinf /**< is the differbranch known to be infeasible? */
330  )
331 {
332  SCIP* masterscip;
333  SCIP_VAR* pricingvar1;
334  SCIP_VAR* pricingvar2;
335  GCG_BRANCHDATA* branchsamedata;
336  GCG_BRANCHDATA* branchdifferdata;
337  char samename[SCIP_MAXSTRLEN];
338  char differname[SCIP_MAXSTRLEN];
339 
340  SCIP_VAR** origvars1;
341  SCIP_VAR** origvars2;
342  int norigvars1;
343  int maxorigvars1;
344  int v;
345 
346  SCIP_NODE* child1;
347  SCIP_NODE* child2;
348  SCIP_CONS* cons1;
349  SCIP_CONS* cons2;
350  SCIP_CONS** origbranchconss1;
351  SCIP_CONS** origbranchconss2;
352 
353 
354  assert(scip != NULL);
355  assert(branchrule != NULL);
356  assert(ovar1 != NULL);
357  assert(ovar2 != NULL);
358  assert(GCGvarIsOriginal(ovar1));
359  assert(GCGvarIsOriginal(ovar2));
360 
361  origbranchconss1 = NULL;
362  origbranchconss2 = NULL;
363 
364  masterscip = GCGgetMasterprob(scip);
365  assert(masterscip != NULL);
366 
367  SCIPdebugMessage("Ryanfoster branching rule: branch on original variables %s and %s!\n",
368  SCIPvarGetName(ovar1), SCIPvarGetName(ovar2));
369 
370  /* for cons_masterbranch */
371 
372  if(!sameinf)
373  {
374  /* create child-node of the current node in the b&b-tree */
375  SCIP_CALL( SCIPcreateChild(masterscip, &child1, 0.0, SCIPgetLocalTransEstimate(masterscip)) );
376 
377  /* allocate branchdata and store information */
378  SCIP_CALL( SCIPallocBlockMemory(scip, &branchsamedata) );
379  branchsamedata->var1 = ovar1;
380  branchsamedata->var2 = ovar2;
381  branchsamedata->same = TRUE;
382  branchsamedata->blocknr = blocknr;
383  branchsamedata->pricecons = NULL;
384 
385  /* define name for origbranch constraints */
386  (void) SCIPsnprintf(samename, SCIP_MAXSTRLEN, "same(%s,%s)", SCIPvarGetName(branchsamedata->var1),
387  SCIPvarGetName(branchsamedata->var2));
388  }
389 
390  if(!differinf)
391  {
392  /* create child-node of the current node in the b&b-tree */
393  SCIP_CALL( SCIPcreateChild(masterscip, &child2, 0.0, SCIPgetLocalTransEstimate(masterscip)) );
394 
395  /* allocate branchdata and store information */
396  SCIP_CALL( SCIPallocBlockMemory(scip, &branchdifferdata) );
397  branchdifferdata->var1 = ovar1;
398  branchdifferdata->var2 = ovar2;
399  branchdifferdata->same = FALSE;
400  branchdifferdata->blocknr = blocknr;
401  branchdifferdata->pricecons = NULL;
402 
403  /* define name for origbranch constraints */
404  (void) SCIPsnprintf(differname, SCIP_MAXSTRLEN, "differ(%s,%s)", SCIPvarGetName(branchsamedata->var1),
405  SCIPvarGetName(branchsamedata->var2));
406  }
407 
408  pricingvar1 = GCGoriginalVarGetPricingVar( !differinf? branchdifferdata->var1 : branchsamedata->var1 );
409  pricingvar2 = GCGoriginalVarGetPricingVar( !differinf? branchdifferdata->var2 : branchsamedata->var2 );
410  assert(GCGvarIsPricing(pricingvar1));
411  assert(GCGvarIsPricing(pricingvar2));
412  assert(GCGvarGetBlock(pricingvar1) == GCGvarGetBlock(pricingvar2));
413  assert(GCGpricingVarGetNOrigvars(pricingvar1) == GCGpricingVarGetNOrigvars(pricingvar2));
414 
415  norigvars1 = GCGpricingVarGetNOrigvars(pricingvar1);
416  assert(norigvars1 == GCGpricingVarGetNOrigvars(pricingvar2));
417 
418  origvars1 = GCGpricingVarGetOrigvars(pricingvar1);
419  origvars2 = GCGpricingVarGetOrigvars(pricingvar2);
420 
421  if( norigvars1 > 0 )
422  {
423  maxorigvars1 = SCIPcalcMemGrowSize(masterscip, norigvars1);
424  if(!sameinf)
425  SCIP_CALL( SCIPallocBlockMemoryArray(masterscip, &origbranchconss1, maxorigvars1) );
426  if(!differinf)
427  SCIP_CALL( SCIPallocBlockMemoryArray(masterscip, &origbranchconss2, maxorigvars1) );
428  }
429  else
430  {
431  maxorigvars1 = 0;
432  }
433 
434  /* add branching decision as varbound constraints to original problem */
435  for( v = 0; v < norigvars1; v++ )
436  {
437  SCIP_CONS* origcons;
438  SCIP_CONS* origcons2;
439 
440  assert(GCGvarGetBlock(origvars1[v]) == GCGvarGetBlock(origvars2[v]));
441  assert(origbranchconss1 != NULL || sameinf );
442  assert(origbranchconss2 != NULL || differinf );
443 
444  /* create constraint for same-child */
445  if( !sameinf )
446  {
447  SCIP_CALL( SCIPcreateConsVarbound(scip, &origcons, samename, origvars1[v], origvars2[v],
448  -1.0, 0.0, 0.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
449 
450  origbranchconss1[v] = origcons;
451  }
452 
453  /* create constraint for differ-child */
454  if( !differinf )
455  {
456  SCIP_CALL( SCIPcreateConsVarbound(scip, &origcons2, differname, origvars1[v], origvars2[v],
457  1.0, -SCIPinfinity(scip), 1.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
458 
459  origbranchconss2[v] = origcons2;
460  }
461  }
462 
463  if( !sameinf )
464  {
465  /* create and add the masterbranch constraints */
466  SCIP_CALL( GCGcreateConsMasterbranch(masterscip, &cons1, samename, child1,
467  GCGconsMasterbranchGetActiveCons(masterscip), branchrule, branchsamedata, origbranchconss1, norigvars1,
468  maxorigvars1) );
469 
470  SCIP_CALL( SCIPaddConsNode(masterscip, child1, cons1, NULL) );
471 
472  /* release constraints */
473  SCIP_CALL( SCIPreleaseCons(masterscip, &cons1) );
474  }
475 
476  if( !differinf )
477  {
478  /* create and add the masterbranch constraints */
479  SCIP_CALL( GCGcreateConsMasterbranch(masterscip, &cons2, differname, child2,
480  GCGconsMasterbranchGetActiveCons(masterscip), branchrule, branchdifferdata, origbranchconss2, norigvars1,
481  maxorigvars1) );
482 
483  SCIP_CALL( SCIPaddConsNode(masterscip, child2, cons2, NULL) );
484 
485  /* release constraints */
486  SCIP_CALL( SCIPreleaseCons(masterscip, &cons2) );
487  }
488  return SCIP_OKAY;
489 }
490 
491 /** branching execution method for fractional LP solutions */
492 static
493 SCIP_DECL_BRANCHEXECLP(branchExeclpRyanfoster)
494 { /*lint --e{715}*/
495  SCIP* origscip;
496  SCIP_Bool feasible;
497 
498  SCIP_VAR** branchcands;
499  int nbranchcands;
500 
501  int v1;
502 
503  SCIP_VAR* mvar1;
504  SCIP_VAR* ovar1;
505  SCIP_VAR* ovar2;
506 
507  SCIP_Bool usestrong;
508 
509  SCIP_VAR** ovar1s;
510  SCIP_VAR** ovar2s;
511  int *nspricingblock;
512  int npairs;
513  SCIP_Bool duplicate;
514  SCIP_Bool stillusestrong;
515 
516  int pricingblock;
517  SCIP_Bool sameinf;
518  SCIP_Bool differinf;
519 
520  assert(branchrule != NULL);
521  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
522  assert(scip != NULL);
523  assert(result != NULL);
524 
525  SCIPdebugMessage("Execrel method of ryanfoster branching\n");
526 
527  origscip = GCGmasterGetOrigprob(scip);
528  assert(origscip != NULL);
529 
530  *result = SCIP_DIDNOTRUN;
531 
532  sameinf = FALSE;
533  differinf = FALSE;
534 
535  /* do not perform Ryan & Foster branching if we have neither a set partitioning nor a set covering structure */
536  if( !GCGisMasterSetCovering(origscip) && !GCGisMasterSetPartitioning(origscip) )
537  {
538  SCIPdebugMessage("Not executing Ryan&Foster branching, master is neither set covering nor set partitioning\n");
539  return SCIP_OKAY;
540  }
541 
542  if( GCGcurrentNodeIsGeneric(scip) )
543  {
544  SCIPdebugMessage("Not executing Ryan&Foster branching, node was branched by generic branchrule\n");
545  return SCIP_OKAY;
546  }
547 
548  if( GCGrelaxIsOrigSolFeasible(origscip) )
549  {
550  SCIPdebugMessage("node cut off, since origsol was feasible, solval = %f\n",
551  SCIPgetSolOrigObj(origscip, GCGrelaxGetCurrentOrigSol(origscip)));
552 
553  *result = SCIP_DIDNOTFIND;
554 
555  return SCIP_OKAY;
556  }
557 
558  /* the current original solution is not integral, now we have to branch;
559  * first, get the master problem and all variables of the master problem
560  */
561  SCIP_CALL( SCIPgetLPBranchCands(scip, &branchcands, NULL, NULL, &nbranchcands, NULL, NULL) );
562 
563  SCIP_CALL( SCIPgetBoolParam(origscip, "branching/ryanfoster/usestrong", &usestrong) );
564 
565  if( usestrong )
566  {
567  npairs = 0;
568  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &ovar1s, 0) );
569  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &ovar2s, 0) );
570  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &nspricingblock, 0) );
571  }
572 
573  /* now search for two (fractional) columns mvar1, mvar2 in the master and 2 original variables ovar1, ovar2
574  * s.t. mvar1 contains both ovar1 and ovar2 and mvar2 contains ovar1, but not ovar2
575  */
576  ovar1 = NULL;
577  ovar2 = NULL;
578  mvar1 = NULL;
579  feasible = FALSE;
580 
581  /* select first fractional column (mvar1) */
582  for( v1 = 0; v1 < nbranchcands && !feasible; v1++ )
583  {
584  int o1;
585  int j;
586 
587  SCIP_VAR** origvars1;
588  int norigvars1;
589  SCIP_VAR* mvar2 = NULL;
590 
591  mvar1 = branchcands[v1];
592  assert(GCGvarIsMaster(mvar1));
593 
594  origvars1 = GCGmasterVarGetOrigvars(mvar1);
595  norigvars1 = GCGmasterVarGetNOrigvars(mvar1);
596 
597  /* select first original variable ovar1, that should be contained in both master variables */
598  for( o1 = 0; o1 < norigvars1 && !feasible; o1++ )
599  {
600  int v2;
601 
602  ovar1 = origvars1[o1];
603  /* if we deal with a trivial variable, skip it */
604  if( SCIPisZero(origscip, GCGmasterVarGetOrigvals(mvar1)[o1]) || GCGoriginalVarGetNCoefs(ovar1) == 0 )
605  continue;
606 
607  /* mvar1 contains ovar1, look for mvar2 which constains ovar1, too */
608  for( v2 = v1+1; v2 < nbranchcands && !feasible; v2++ )
609  {
610  SCIP_VAR** origvars2;
611  int norigvars2;
612  int o2;
613  SCIP_Bool contained = FALSE;
614 
615  mvar2 = branchcands[v2];
616  assert(GCGvarIsMaster(mvar2));
617 
618  origvars2 = GCGmasterVarGetOrigvars(mvar2);
619  norigvars2 = GCGmasterVarGetNOrigvars(mvar2);
620 
621  /* check whether ovar1 is contained in mvar2, too */
622  for( j = 0; j < norigvars2; j++ )
623  {
624  /* if we deal with a trivial variable, skip it */
625  if( SCIPisZero(origscip, GCGmasterVarGetOrigvals(mvar2)[j]) ||
626  GCGoriginalVarGetNCoefs(origvars2[j]) == 0 )
627  continue;
628 
629  if( origvars2[j] == ovar1 )
630  {
631  contained = TRUE;
632  break;
633  }
634  }
635 
636  /* mvar2 does not contain ovar1, so look for another mvar2 */
637  if( !contained )
638  continue;
639 
640  /* mvar2 also contains ovar1, now look for ovar2 contained in mvar1, but not in mvar2 */
641  for( o2 = 0; o2 < norigvars1; o2++ )
642  {
643  /* if we deal with a trivial variable, skip it */
644  if( !SCIPisZero(origscip, GCGmasterVarGetOrigvals(mvar1)[o2]) ||
645  GCGoriginalVarGetNCoefs(origvars1[o2]) == 0 )
646  continue;
647 
648  ovar2 = origvars1[o2];
649  if( ovar2 == ovar1 )
650  continue;
651 
652  /* check whether ovar2 is contained in mvar2, too */
653  contained = FALSE;
654  for( j = 0; j < norigvars2; j++ )
655  {
656  /* if we deal with a trivial variable, skip it */
657  if( !SCIPisZero(origscip, GCGmasterVarGetOrigvals(mvar2)[j]) )
658  continue;
659 
660  if( origvars2[j] == ovar2 )
661  {
662  contained = TRUE;
663  break;
664  }
665  }
666 
667  /* ovar2 should be contained in mvar1 but not in mvar2, so look for another ovar2,
668  * if the current one is contained in mvar2
669  */
670  if( contained )
671  continue;
672 
673  /* if we arrive here, ovar2 is contained in mvar1 but not in mvar2, so everything is fine */
674  if( !usestrong )
675  {
676  feasible = TRUE;
677  break;
678  }
679  else
680  {
681  /* we need to check first whether we already found this pair */
682  duplicate = FALSE;
683  for( int z=0; z<npairs; z++ )
684  {
685  if( ovar1s[z] == ovar1 && ovar2s[z] == ovar2 )
686  {
687  duplicate = TRUE;
688  break;
689  }
690  }
691 
692  if( !duplicate )
693  {
694  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &ovar1s, npairs, npairs+1) );
695  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &ovar2s, npairs, npairs+1) );
696  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &nspricingblock, npairs, npairs+1) );
697 
698  ovar1s[npairs] = ovar1;
699  ovar2s[npairs] = ovar2;
700  nspricingblock[npairs] = GCGvarGetBlock(mvar1);
701 
702  npairs++;
703  }
704  }
705  }
706 
707  /* we did not find an ovar2 contained in mvar1, but not in mvar2,
708  * now look for one contained in mvar2, but not in mvar1
709  */
710  if( !feasible )
711  {
712  for( o2 = 0; o2 < norigvars2; o2++ )
713  {
714  /* if we deal with a trivial variable, skip it */
715  if( SCIPisZero(origscip, GCGmasterVarGetOrigvals(mvar2)[o2]) ||
716  GCGoriginalVarGetNCoefs(origvars2[o2]) == 0 )
717  continue;
718 
719  ovar2 = origvars2[o2];
720 
721  if( ovar2 == ovar1 )
722  continue;
723 
724  contained = FALSE;
725  for( j = 0; j < norigvars1; j++ )
726  {
727  /* if we deal with a trivial variable, skip it */
728  if( SCIPisZero(origscip, GCGmasterVarGetOrigvals(mvar1)[j]) ||
729  GCGoriginalVarGetNCoefs(origvars1[j]) == 0 )
730  continue;
731  if( origvars1[j] == ovar2 )
732  {
733  contained = TRUE;
734  break;
735  }
736  }
737 
738  /* ovar2 should be contained in mvar2 but not in mvar1, so look for another ovar2,
739  * if the current one is contained in mvar1
740  */
741  if( contained )
742  continue;
743 
744  /* if we arrive here, ovar2 is contained in mvar2 but not in mvar1, so everything is fine */
745  if( !usestrong )
746  {
747  feasible = TRUE;
748  break;
749  }
750  else
751  {
752  /* we need to check first whether we already found this pair */
753  duplicate = FALSE;
754  for( int z=0; z<npairs; z++ )
755  {
756  if( ovar1s[z] == ovar1 && ovar2s[z] == ovar2 )
757  {
758  duplicate = TRUE;
759  break;
760  }
761  }
762 
763  if( !duplicate )
764  {
765  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &ovar1s, npairs, npairs+1) );
766  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &ovar2s, npairs, npairs+1) );
767  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &nspricingblock, npairs, npairs+1) );
768 
769  ovar1s[npairs] = ovar1;
770  ovar2s[npairs] = ovar2;
771  nspricingblock[npairs] = GCGvarGetBlock(mvar1);
772 
773  npairs++;
774  }
775  }
776  }
777  }
778  }
779  }
780  }
781 
782  if( usestrong )
783  {
784  if( npairs>0 )
785  {
786  GCGbranchSelectCandidateStrongBranchingRyanfoster(origscip, branchrule, ovar1s, ovar2s, nspricingblock,
787  npairs, &ovar1, &ovar2, &pricingblock, &sameinf, &differinf,
788  result, &stillusestrong);
789 
790  SCIPfreeBlockMemoryArray(scip, &ovar1s, npairs);
791  SCIPfreeBlockMemoryArray(scip, &ovar2s, npairs);
792  SCIPfreeBlockMemoryArray(scip, &nspricingblock, npairs);
793  if( !stillusestrong )
794  {
795  SCIPsetBoolParam(origscip, "branching/ryanfoster/usestrong", FALSE);
796  }
797  }
798  }
799 
800  if( !feasible && ( !usestrong || npairs==0 ) )
801  {
802  SCIPdebugMessage("Ryanfoster branching rule could not find variables to branch on!\n");
803  return SCIP_OKAY;
804  }
805 
806  /* create the two child nodes in the branch-and-bound tree */
807  SCIP_CALL( createChildNodesRyanfoster(origscip, branchrule, ovar1, ovar2, GCGvarGetBlock(mvar1), sameinf,
808  differinf) );
809 
810  *result = SCIP_BRANCHED;
811 
812  return SCIP_OKAY;
813 }
814 
815 /** branching execution method for relaxation solutions */
816 static
817 SCIP_DECL_BRANCHEXECEXT(branchExecextRyanfoster)
818 { /*lint --e{715}*/
819 
820  *result = SCIP_DIDNOTRUN;
821 
822  return SCIP_OKAY;
823 
824 }
825 
826 /** branching execution method for not completely fixed pseudo solutions */
827 static
828 SCIP_DECL_BRANCHEXECPS(branchExecpsRyanfoster)
829 { /*lint --e{715}*/
830  SCIP_CONS** origbranchconss;
831  GCG_BRANCHDATA* branchdata;
832  SCIP_VAR** branchcands;
833  SCIP_VAR* ovar1;
834  SCIP_VAR* ovar2;
835  SCIP_Bool feasible;
836  int norigbranchconss;
837  int nbranchcands;
838  int o1;
839  int o2;
840  int c;
841 
842  SCIP* origscip;
843 
844  assert(branchrule != NULL);
845  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
846  assert(scip != NULL);
847  assert(result != NULL);
848 
849  SCIPdebugMessage("Execps method of ryanfoster branching\n");
850 
851  origscip = GCGmasterGetOrigprob(scip);
852  assert(origscip != NULL);
853 
854 
855  *result = SCIP_DIDNOTRUN;
856 
857  /* do not perform Ryan & Foster branching if we have neither a set partitioning nor a set covering structure */
858  if( !GCGisMasterSetCovering(origscip) || !GCGisMasterSetPartitioning(origscip) )
859  {
860  SCIPdebugMessage("Not executing Ryanfoster branching, master is neither set covering nor set partitioning\n");
861  return SCIP_OKAY;
862  }
863 
864  if( GCGcurrentNodeIsGeneric(scip) )
865  {
866  SCIPdebugMessage("Not executing Ryanfoster branching, node was branched by generic branchrule\n");
867  return SCIP_OKAY;
868  }
869 
870  /* get unfixed variables and stack of active origbranchconss */
871  SCIP_CALL( SCIPgetPseudoBranchCands(origscip, &branchcands, NULL, &nbranchcands) );
872  GCGconsOrigbranchGetStack(origscip, &origbranchconss, &norigbranchconss);
873 
874  ovar1 = NULL;
875  ovar2 = NULL;
876  feasible = FALSE;
877 
878  /* select first original variable ovar1 */
879  for( o1 = 0; o1 < nbranchcands && !feasible; ++o1 )
880  {
881  ovar1 = branchcands[o1];
882 
883  /* select second original variable o2 */
884  for( o2 = o1 + 1; o2 < nbranchcands; ++o2 )
885  {
886  ovar2 = branchcands[o2];
887 
888  assert(ovar2 != ovar1);
889 
890  /* check whether we already branched on this combination of variables */
891  for( c = 0; c < norigbranchconss; ++c )
892  {
893  if( GCGconsOrigbranchGetBranchrule(origbranchconss[c]) == branchrule )
894  continue;
895 
896  branchdata = GCGconsOrigbranchGetBranchdata(origbranchconss[c]);
897 
898  if( (branchdata->var1 == ovar1 && branchdata->var2 == ovar2 )
899  || (branchdata->var1 == ovar2 && branchdata->var2 == ovar1) )
900  {
901  break;
902  }
903  }
904 
905  /* we did not break, so there is no active origbranch constraint with both variables */
906  if( c == norigbranchconss )
907  {
908  feasible = TRUE;
909  break;
910  }
911  }
912  }
913 
914  if( !feasible )
915  {
916  SCIPdebugMessage("Ryanfoster branching rule could not find variables to branch on!\n");
917  return SCIP_OKAY;
918  }
919 
920  /* create the two child nodes in the branch-and-bound tree */
921  SCIP_CALL( createChildNodesRyanfoster(origscip, branchrule, ovar1, ovar2, GCGvarGetBlock(ovar1), FALSE, FALSE) );
922 
923  *result = SCIP_BRANCHED;
924 
925  return SCIP_OKAY;
926 }
927 
928 /** initialization method of branching rule (called after problem was transformed) */
929 static
930 SCIP_DECL_BRANCHINIT(branchInitRyanfoster)
931 {
932  SCIP* origprob;
933 
934  origprob = GCGmasterGetOrigprob(scip);
935  assert(branchrule != NULL);
936  assert(origprob != NULL);
937 
938  SCIP_CALL( GCGrelaxIncludeBranchrule(origprob, branchrule, branchActiveMasterRyanfoster,
939  branchDeactiveMasterRyanfoster, branchPropMasterRyanfoster, NULL, branchDataDeleteRyanfoster) );
940 
941  return SCIP_OKAY;
942 }
943 
944 
945 
946 /* define not used callback as NULL*/
947 #define branchFreeRyanfoster NULL
948 #define branchExitRyanfoster NULL
949 #define branchInitsolRyanfoster NULL
950 #define branchExitsolRyanfoster NULL
951 
952 
953 /*
954  * branching specific interface methods
955  */
956 
957 /** creates the Ryan-Foster LP braching rule and includes it in SCIP */
959  SCIP* scip /**< SCIP data structure */
960  )
961 {
962  SCIP_BRANCHRULEDATA* branchruledata;
963 
964  /* create branching rule data */
965  branchruledata = NULL;
966 
967  /* include branching rule */
968  SCIP_CALL( SCIPincludeBranchrule(scip, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
969  BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchCopyRyanfoster,
971  branchExitsolRyanfoster, branchExeclpRyanfoster, branchExecextRyanfoster, branchExecpsRyanfoster,
972  branchruledata) );
973 
974  SCIP_CALL( SCIPaddBoolParam(GCGmasterGetOrigprob(scip), "branching/ryanfoster/usestrong",
975  "should strong branching be used to determine the variables on which the branching is performed?",
976  NULL, FALSE, DEFAULT_USESTRONG, NULL, NULL) );
977 
978  /* strong branching */
979  SCIP_CALL( SCIPaddIntParam(GCGmasterGetOrigprob(scip), "branching/ryanfoster/minphase0outcands",
980  "minimum number of output candidates from phase 0 during strong branching",
981  NULL, FALSE, DEFAULT_MINPHASE0OUTCANDS, 1, INT_MAX, NULL, NULL) );
982 
983  SCIP_CALL( SCIPaddIntParam(GCGmasterGetOrigprob(scip), "branching/ryanfoster/maxphase0outcands",
984  "maximum number of output candidates from phase 0 during strong branching",
985  NULL, FALSE, DEFAULT_MAXPHASE0OUTCANDS, 1, INT_MAX, NULL, NULL) );
986 
987  SCIP_CALL( SCIPaddRealParam(GCGmasterGetOrigprob(scip), "branching/ryanfoster/maxphase0outcandsfrac",
988  "maximum number of output candidates from phase 0 as fraction of total cands during strong branching",
989  NULL, FALSE, DEFAULT_MAXPHASE0OUTCANDSFRAC, 0, 1, NULL, NULL) );
990 
991  SCIP_CALL( SCIPaddRealParam(GCGmasterGetOrigprob(scip), "branching/ryanfoster/phase1gapweight",
992  "how much impact should the node gap have on the number of precisely evaluated candidates in phase 1 during strong branching?",
993  NULL, FALSE, DEFAULT_PHASE1GAPWEIGHT, 0, 1, NULL, NULL) );
994 
995  SCIP_CALL( SCIPaddIntParam(GCGmasterGetOrigprob(scip), "branching/ryanfoster/minphase1outcands",
996  "minimum number of output candidates from phase 1 during strong branching",
997  NULL, FALSE, DEFAULT_MINPHASE1OUTCANDS, 1, INT_MAX, NULL, NULL) );
998 
999  SCIP_CALL( SCIPaddIntParam(GCGmasterGetOrigprob(scip), "branching/ryanfoster/maxphase1outcands",
1000  "maximum number of output candidates from phase 1 during strong branching",
1001  NULL, FALSE, DEFAULT_MAXPHASE1OUTCANDS, 1, INT_MAX, NULL, NULL) );
1002 
1003  SCIP_CALL( SCIPaddRealParam(GCGmasterGetOrigprob(scip), "branching/ryanfoster/maxphase1outcandsfrac",
1004  "maximum number of output candidates from phase 1 as fraction of phase 1 cands during strong branching",
1005  NULL, FALSE, DEFAULT_MAXPHASE1OUTCANDSFRAC, 0, 1, NULL, NULL) );
1006 
1007  SCIP_CALL( SCIPaddRealParam(GCGmasterGetOrigprob(scip), "branching/ryanfoster/phase2gapweight",
1008  "how much impact should the node gap have on the number of precisely evaluated candidates in phase 2 during strong branching?",
1009  NULL, FALSE, DEFAULT_PHASE2GAPWEIGHT, 0, 1, NULL, NULL) );
1010 
1011  return SCIP_OKAY;
1012 }
type definitions for branching rules in GCG projects
#define BRANCHRULE_NAME
int GCGmasterVarGetNOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:886
GCG interface methods.
GCG_BRANCHDATA * GCGconsOrigbranchGetBranchdata(SCIP_CONS *cons)
SCIP_Bool GCGvarIsMaster(SCIP_VAR *var)
Definition: gcgvar.c:150
int GCGoriginalVarGetNCoefs(SCIP_VAR *var)
Definition: gcgvar.c:641
SCIP_Bool GCGrelaxIsOrigSolFeasible(SCIP *scip)
Definition: relax_gcg.c:4202
#define branchFreeRyanfoster
#define DEFAULT_USESTRONG
#define DEFAULT_PHASE2GAPWEIGHT
static SCIP_DECL_BRANCHEXECPS(branchExecpsRyanfoster)
static SCIP_RETCODE createChildNodesRyanfoster(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR *ovar1, SCIP_VAR *ovar2, int blocknr, SCIP_Bool sameinf, SCIP_Bool differinf)
#define DEFAULT_MINPHASE0OUTCANDS
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)
branching rule for original problem in GCG implementing the Ryan and Foster branching scheme
#define branchInitsolRyanfoster
SCIP_VAR ** GCGmasterVarGetOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:908
SCIP_Real * GCGmasterVarGetOrigvals(SCIP_VAR *var)
Definition: gcgvar.c:932
int GCGvarGetBlock(SCIP_VAR *var)
Definition: gcgvar.c:1033
SCIP_Bool GCGvarIsPricing(SCIP_VAR *var)
Definition: gcgvar.c:134
SCIP * GCGgetPricingprob(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:3939
#define DEFAULT_MAXPHASE0OUTCANDS
SCIP_VAR * GCGoriginalVarGetPricingVar(SCIP_VAR *var)
Definition: gcgvar.c:216
SCIP_Bool GCGvarIsOriginal(SCIP_VAR *var)
Definition: gcgvar.c:166
GCG variable pricer.
#define BRANCHRULE_MAXDEPTH
#define DEFAULT_MAXPHASE0OUTCANDSFRAC
static SCIP_DECL_BRANCHEXECLP(branchExeclpRyanfoster)
static GCG_DECL_BRANCHDATADELETE(branchDataDeleteRyanfoster)
#define BRANCHRULE_PRIORITY
#define DEFAULT_MAXPHASE1OUTCANDSFRAC
SCIP * GCGgetMasterprob(SCIP *scip)
Definition: relax_gcg.c:3920
#define DEFAULT_MINPHASE1OUTCANDS
SCIP_BRANCHRULE * GCGconsOrigbranchGetBranchrule(SCIP_CONS *cons)
constraint handler for storing the branching decisions at each node of the tree
static SCIP_DECL_BRANCHINIT(branchInitRyanfoster)
int GCGpricingVarGetNOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:997
SCIP_Bool GCGcurrentNodeIsGeneric(SCIP *scip)
static GCG_DECL_BRANCHACTIVEMASTER(branchActiveMasterRyanfoster)
constraint handler for storing the branching decisions at each node of the tree
static SCIP_DECL_BRANCHEXECEXT(branchExecextRyanfoster)
#define DEFAULT_PHASE1GAPWEIGHT
SCIP * GCGmasterGetOrigprob(SCIP *scip)
#define branchExitsolRyanfoster
SCIP_SOL * GCGrelaxGetCurrentOrigSol(SCIP *scip)
Definition: relax_gcg.c:4183
void GCGconsOrigbranchGetStack(SCIP *scip, SCIP_CONS ***stack, int *nstackelements)
GCG relaxator.
SCIP_CONS * GCGconsMasterbranchGetActiveCons(SCIP *scip)
SCIP_VAR ** GCGpricingVarGetOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:1015
static GCG_DECL_BRANCHPROPMASTER(branchPropMasterRyanfoster)
#define BRANCHRULE_DESC
static SCIP_DECL_BRANCHCOPY(branchCopyRyanfoster)
generic branch and price strong branching as described in Pecin, D., Pessoa, A., Poggi,...
SCIP_Bool GCGisMasterSetPartitioning(SCIP *scip)
Definition: relax_gcg.c:4240
SCIP_RETCODE GCGbranchSelectCandidateStrongBranchingRyanfoster(SCIP *scip, SCIP_BRANCHRULE *rfbranchrule, SCIP_VAR **ovar1s, SCIP_VAR **ovar2s, int *nspricingblock, int npairs, SCIP_VAR **ovar1, SCIP_VAR **ovar2, int *pricingblock, SCIP_Bool *sameinf, SCIP_Bool *differinf, SCIP_RESULT *result, SCIP_Bool *stillusestrong)
#define BRANCHRULE_MAXBOUNDDIST
static GCG_DECL_BRANCHDEACTIVEMASTER(branchDeactiveMasterRyanfoster)
SCIP_CONS * pricecons
SCIP_Bool GCGisMasterSetCovering(SCIP *scip)
Definition: relax_gcg.c:4221
#define branchExitRyanfoster
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
#define DEFAULT_MAXPHASE1OUTCANDS
SCIP_RETCODE SCIPincludeBranchruleRyanfoster(SCIP *scip)