Scippy

SCIP

Solving Constraint Integer Programs

branch_multaggr.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 /**@file branch_multaggr.c
16  * @brief fullstrong branching on fractional and multi-aggregated variables
17  * @author Anna Melchiori
18  * @author Gerald Gamrath
19  *
20  * This branching rule uses all fractional binary and integer variables as candidates,
21  * as well as fractional multiaggregated binary and integer variables. Although not
22  * directly contained in the presolved problem anymore, the multi-aggregation provides
23  * an affine linear sum of integer variables, on which branching can be performed.
24  *
25  * For more details, see
26  * G.Gamrath, A.Melchiori, T.Berthold, A.M.Gleixner, D.Salvagnin: Branching on Multi-aggregated Variables
27  * (http://dx.doi.org/10.1007/978-3-319-18008-3_10)
28  */
29 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
30 
31 #include <assert.h>
32 #include <string.h>
33 
34 #include "scip/branch_multaggr.h"
35 #include "scip/branch_fullstrong.h"
36 #include "scip/cons_linear.h"
37 #include "scip/var.h"
38 #include "scip/set.h"
39 #include "scip/pub_tree.h"
40 #include "scip/struct_scip.h"
41 #include "scip/clock.h"
42 
43 #define BRANCHRULE_NAME "multaggr"
44 #define BRANCHRULE_DESC "fullstrong branching on fractional and multi-aggregated variables"
45 #define BRANCHRULE_PRIORITY 0
46 #define BRANCHRULE_MAXDEPTH -1
47 #define BRANCHRULE_MAXBOUNDDIST 1.0
48 
49 
50 #define DEFAULT_REEVALAGE 0LL /**< number of intermediate LPs solved to trigger reevaluation of strong branching
51  * value for a variable that was already evaluated at the current node */
52 #define DEFAULT_MAXPROPROUNDS 0 /**< maximum number of propagation rounds to be performed during multaggr branching
53  * before solving the LP (-1: no limit, -2: parameter settings) */
54 #define DEFAULT_PROBINGBOUNDS TRUE /**< should valid bounds be identified in a probing-like fashion during multi-aggr
55  * branching (only with propagation)? */
56 
57 /*
58  * Data structures
59  */
60 
61 /** branching rule data */
62 struct SCIP_BranchruleData
63 {
64  SCIP_Longint reevalage; /**< number of intermediate LPs solved to trigger reevaluation of strong branching
65  * value for a variable that was already evaluated at the current node */
66  SCIP_Bool probingbounds; /**< should valid bounds be identified in a probing-like fashion during strong
67  * branching (only with propagation)? */
68  int lastcand; /**< last evaluated candidate of last branching rule execution */
69  int maxproprounds; /**< maximum number of propagation rounds to be performed during strong branching
70  * before solving the LP (-1: no limit, -2: parameter settings) */
71  int skipsize; /**< size of skipdown and skipup array */
72  SCIP_Bool* skipdown; /**< should be branching on down child be skipped? */
73  SCIP_Bool* skipup; /**< should be branching on up child be skipped? */
74 #ifdef SCIP_STATISTIC
75  SCIP_CLOCK* clckstrongbr; /**< clock to store the time spent inside the strong branching function on fractional variables */
76  SCIP_CLOCK* clckmultaggrbr; /**< clock to store the time spent inside the strong branching function on multi-aggragated variables */
77  SCIP_Real* ratioggain; /**< for each occurence of a branching on a multi-aggregated variable we store the ratio of the gain that
78  * we would have obtained branching on the best fractional variable over the gain obtained
79  * branching on the current multi-aggregated variable */
80  SCIP_Real ameanratio; /**< arithmetic mean of the ratioggain array */
81  SCIP_Bool noupdate; /**< pointer to store if the probing LP has not been solved so we do not want to
82  * update statistics */
83  int firstmultaggrdepth; /**< depth of the first branching on a multi-aggregated variable */
84  int rundepth; /**< the run of the first multi-aggregated branching */
85  int nmultaggrbranch; /**< number of branchings on multi-aggregated variables */
86  int nfracbranch; /**< number of branchings on fractional variables */
87  int nEscore; /**< number of times that the bestscore over all multi-aggregated variables is equal to the best
88  * fractional variables score and thus we do not branch on the multi-aggregate variable */
89  int nmultaggrcutoff; /**< number of cutoffs detected during the probing mode on multi-aggregated variables */
90  int nmultaggrconsadd; /**< number of times that a probing constraint of a multi-aggregated variable has been
91  * added to the original problem */
92  int nfractcutoff; /**< number of cutoffs detected during strong branching on fractional variables */
93  int nfractconsadd; /**< number of times that during strong branching on fractional variables a constraint has been
94  * added to the original problem or a variables domain has been reduced */
95  int nmultaggrvars; /**< number of multi-aggregated variables in the problem of the last run */
96  int nrun; /**< number of restarts */
97  int size; /**< size of the provided array to store the ratio gain */
98  int nstrongbrcall; /**< number of times that the selectVarstrongBranching function has been called */
99  int nmultaggrbrcall; /**< number of times that the selectVarMultAggrBranching function has been called */
100  int totallpcands; /**< total number of observed lpcands over all selectVarstrongBranching function calls */
101  int totalmultaggrcands; /**< total number of observed multi-aggregregated candidates over all selectVarMultAggrBranching
102  * function calls */
103 #endif
104 };
105 
106 
107 /*
108  * Local methods
109  */
110 
111 /* this function ensures that the allocated memory is enough to store statistics data */
112 #ifdef SCIP_STATISTIC
113 static
114 SCIP_RETCODE ensureArraySize(
115  SCIP* scip, /**< original SCIP data structure */
116  SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */
117  )
118 {
119  assert(scip != NULL);
120  assert(branchruledata != NULL);
121  assert(branchruledata->ratioggain != NULL);
122  assert(branchruledata->nmultaggrbranch >= 0);
123  assert(branchruledata->size >= 0);
124 
125  /* check whether the size of the array is big enough; reallocate memory if needed */
126  if( branchruledata->nmultaggrbranch + 1 > branchruledata->size )
127  {
128  int newsize = SCIPcalcMemGrowSize(scip, branchruledata->nmultaggrbranch + 1);
129  assert(newsize >= branchruledata->nmultaggrbranch + 1);
130  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &branchruledata->ratioggain, branchruledata->size, newsize) );
131  branchruledata->size = newsize;
132  }
133  return SCIP_OKAY;
134 }
135 #endif
136 
137 /* this function gives us the best candidate for branching among the multi-aggregated variables of the problem
138  * and the best fractional integer variable already selected by strong branching
139 */
140 static
142  SCIP* scip, /**< original SCIP data structure */
143  SCIP_VAR** bestcand, /**< the best candidate variable selected by strong branching */
144  SCIP_Real* bestscore, /**< score of the best branching candidate */
145  SCIP_Real* bestsol, /**< solution value of the best branching candidate */
146  SCIP_Real* bestdown, /**< objective value of the down node when branching on bestcand */
147  SCIP_Real* bestup, /**< objective value of the up node when branching on bestcand */
148  SCIP_Bool* bestdownvalid, /**< is bestdown a valid dual bound for the down branch? */
149  SCIP_Bool* bestupvalid, /**< is bestup a valid dual bound for the up branch? */
150  SCIP_Real* provedbound, /**< proved dual bound for the current subtree */
151  SCIP_Real* estimatedown, /**< pointer to store the down child nodes estimate */
152  SCIP_Real* estimateup, /**< pointer to store the up child nodes estimate */
153 #ifdef SCIP_STATISTIC
154  SCIP_Real* bestmultaggrscore, /**< pointer to store the multi aggregated score */
155 #endif
156  SCIP_RESULT* result /**< pointer to store results of branching */
157  )
158 {
159  SCIP_VAR** fixvars;
160  SCIP_CONS* probingconsdown;
161  SCIP_CONS* probingconsup;
162  SCIP_NODE* node;
163  SCIP_Real* fixvarssols;
164  SCIP_Real fixvarssol;
165  SCIP_Real lpobjval;
166  SCIP_Bool exactsolve;
167  SCIP_Bool allcolsinlp;
168  SCIP_Bool downnodeinf = FALSE;
169  SCIP_Bool startprobing = TRUE;
170  SCIP_Bool endprobing = FALSE;
171  int nfixvars;
172  int i;
173  int j;
174  int k;
175 
176  /* import branchrule data for statistics */
177 #ifdef SCIP_STATISTIC
178  SCIP_BRANCHRULE* branchrule;
179  SCIP_BRANCHRULEDATA* branchruledata;
180 
181  branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME);
182  assert(branchrule != NULL);
183 
184  branchruledata = SCIPbranchruleGetData(branchrule);
185  assert(branchruledata != NULL);
186 #endif
187 
188  assert(scip != NULL);
189  assert(bestcand != NULL);
190  assert(bestscore != NULL);
191 
192  /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
193  * for cutting off sub problems and improving lower bounds of children
194  */
195  exactsolve = SCIPisExactSolve(scip);
196 
197  /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
198  allcolsinlp = SCIPallColsInLP(scip);
199 
200  /* get fixed variables */
201  fixvars = SCIPgetFixedVars(scip);
202  nfixvars = SCIPgetNFixedVars(scip);
203  SCIPdebugMsg(scip, " fractional variable: <%s> with value: %f is selected by strong branching\n", SCIPvarGetName(*bestcand), *bestsol);
204 
205  /* check if we would exceed the depth limit */
206  if( SCIP_MAXTREEDEPTH <= SCIPgetDepth(scip) )
207  {
208  SCIPdebugMsg(scip, "cannot perform probing in selectVarMultAggrBranching, depth limit reached.\n");
209  *result = SCIP_DIDNOTRUN;
210  return SCIP_OKAY;
211  }
212 
213  if( nfixvars != 0 )
214  {
215  assert(fixvars != NULL);
216 
217  SCIP_CALL( SCIPallocBufferArray(scip, &fixvarssols, nfixvars) );
218  lpobjval = SCIPgetLPObjval(scip);
219 
220  /* store the values of the fixed variables at the current optimal solution */
221  for( i = 0; i < nfixvars; i++ )
222  {
223  assert(fixvars[i] != NULL);
224  fixvarssols[i] = SCIPvarGetLPSol(fixvars[i]);
225  }
226 
227  for( i = 0; i < nfixvars; i++ )
228  {
229  assert(fixvars[i] != NULL);
230 
231  /* only integer and binary multi-aggregated variables are potential branching candidates */
232  if( SCIPvarGetStatus(fixvars[i]) == SCIP_VARSTATUS_MULTAGGR && (SCIPvarGetType(fixvars[i]) == SCIP_VARTYPE_INTEGER ||
233  SCIPvarGetType(fixvars[i]) == SCIP_VARTYPE_BINARY) )
234  {
235  fixvarssol = fixvarssols[i];
236 
237  /* start probing mode for the fractional multi-aggregated variable */
238  if( !SCIPisFeasIntegral(scip, fixvarssol) )
239  {
240  SCIP_VAR** downvars = NULL;
241  SCIP_VAR** upvars = NULL;
242  SCIP_Real* downvarssols = NULL;
243  SCIP_Real* upvarssols = NULL;
244  SCIP_LPSOLSTAT solstatdown;
245  SCIP_LPSOLSTAT solstatup;
246  SCIP_Real downobjval;
247  SCIP_Real upobjval;
248  SCIP_Real estimateprobdown = 0.0;
249  SCIP_Real estimateprobup = 0.0;
250  SCIP_Bool downinf;
251  SCIP_Bool upinf;
252  SCIP_Bool lperror;
253  int ndownvars;
254  int nupvars;
255 
256  /* start the probing mode if this is the first entrance */
257  if( startprobing )
258  {
259  SCIP_CALL( SCIPstartProbing(scip) );
260  startprobing = FALSE;
261  endprobing = TRUE;
262 
263  SCIPdebugMsg(scip, "PROBING MODE:\n");
264  }
265 
266  SCIPdebugMsg(scip, " multi-aggregated variable: <%s> with value: %f\n", SCIPvarGetName(fixvars[i]), fixvarssol);
267 
268  SCIPstatistic(branchruledata->totalmultaggrcands += 1);
269 
270  /* create the multi-aggregated rounded down constraint */
271  SCIP_CALL( SCIPcreateConsLinear(scip, &probingconsdown, "probingconsdown", SCIPvarGetMultaggrNVars(fixvars[i]),
272  SCIPvarGetMultaggrVars(fixvars[i]), SCIPvarGetMultaggrScalars(fixvars[i]), -SCIPinfinity(scip),
273  SCIPfeasFloor(scip, fixvarssol) - SCIPvarGetMultaggrConstant(fixvars[i]), TRUE, TRUE, FALSE, FALSE,
274  TRUE, TRUE, FALSE, FALSE, FALSE, TRUE) );
275  assert(probingconsdown != NULL);
276 
277  /* create the down child probing node */
278  SCIP_CALL( SCIPnewProbingNode(scip) );
279  node = SCIPgetCurrentNode(scip);
280  assert(node != NULL);
281 
282  SCIP_CALL( SCIPaddConsNode(scip, node, probingconsdown, NULL) );
283  SCIP_CALL( SCIPreleaseCons(scip, &probingconsdown) );
284 
285 #ifdef PRINTNODECONS
286  SCIPdebugMsg(scip, " created down probing node with constraint:\n");
287  SCIP_CALL( SCIPprintCons(scip, probingconsdown, NULL) );
288  SCIPinfoMessage(scip, NULL, "\n");
289 #endif
290 
291  /* solve the down child probing node */
292  SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, &downinf) );
293  solstatdown = SCIPgetLPSolstat(scip);
294  lperror = lperror || (solstatdown == SCIP_LPSOLSTAT_NOTSOLVED && downinf == 0) || (solstatdown == SCIP_LPSOLSTAT_ITERLIMIT) ||
295  (solstatdown == SCIP_LPSOLSTAT_TIMELIMIT);
296  assert(solstatdown != SCIP_LPSOLSTAT_UNBOUNDEDRAY);
297 
298  /* break the branching rule if an error occurred, problem was not solved, iteration or time limit was reached */
299  if( lperror )
300  {
301  SCIPdebugMsg(scip, "error solving down node probing LP: status=%d\n", solstatdown);
302  SCIPstatistic(branchruledata->noupdate = TRUE);
303  break;
304  }
305 
306  downobjval = SCIPgetLPObjval(scip);
307  downinf = downinf || SCIPisGE(scip, downobjval, SCIPgetCutoffbound(scip));
308  assert(((solstatdown != SCIP_LPSOLSTAT_INFEASIBLE) && (solstatdown != SCIP_LPSOLSTAT_OBJLIMIT)) || downinf);
309 
310  if( !downinf )
311  {
312  /* when an optimal solution has been found calculate down child's estimate based on pseudo costs */
313  /* estimate = lowerbound + sum(min{f_j * pscdown_j, (1-f_j) * pscup_j}) */
314  estimateprobdown = SCIPnodeGetLowerbound(node);
315  SCIP_CALL( SCIPgetLPBranchCands(scip, &downvars, &downvarssols, NULL, &ndownvars, NULL, NULL) );
316 
317  for( j = 0 ; j < ndownvars; j++ )
318  {
319  SCIP_Real estimateincr;
320  SCIP_Real pscdown;
321  SCIP_Real pscup;
322 
323  assert(downvars != NULL);
324  assert(downvars[j] != NULL);
325 
326  pscdown = SCIPvarGetPseudocost(downvars[j], scip->stat, SCIPsetFeasFloor(scip->set, downvarssols[j]) - downvarssols[j]);
327  pscup = SCIPvarGetPseudocost(downvars[j], scip->stat, SCIPsetFeasCeil(scip->set, downvarssols[j]) - downvarssols[j]);
328  estimateincr = MIN(pscdown, pscup);
329 
330  estimateprobdown += estimateincr;
331  }
332  }
333  SCIP_CALL( SCIPbacktrackProbing(scip, 0) );
334 
335  /* create the multi-aggregated rounded up constraint */
336  SCIP_CALL( SCIPcreateConsLinear(scip, &probingconsup, "probingconsup", SCIPvarGetMultaggrNVars(fixvars[i]), SCIPvarGetMultaggrVars(fixvars[i]),
337  SCIPvarGetMultaggrScalars(fixvars[i]), SCIPfeasCeil(scip, fixvarssol) - SCIPvarGetMultaggrConstant(fixvars[i]), SCIPinfinity(scip),
339  assert(probingconsup != NULL);
340 
341  /* create the up child probing node */
342  SCIP_CALL( SCIPnewProbingNode(scip) );
343  node = SCIPgetCurrentNode(scip);
344 
345  SCIP_CALL( SCIPaddConsNode(scip, node, probingconsup, NULL) );
346  SCIP_CALL( SCIPreleaseCons(scip, &probingconsup) );
347 
348 #ifdef PRINTNODECONS
349  SCIPdebugMsg(scip, " created up probing node with constraint:\n");
350  SCIP_CALL( SCIPprintCons(scip, probingconsup, NULL) );
351  SCIPinfoMessage(scip, NULL, "\n");
352 #endif
353  /* solve the up child probing node */
354  SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, &upinf) );
355  solstatup = SCIPgetLPSolstat(scip);
356  lperror = lperror || (solstatup == SCIP_LPSOLSTAT_NOTSOLVED && upinf == 0) || (solstatup == SCIP_LPSOLSTAT_ITERLIMIT) ||
357  (solstatup == SCIP_LPSOLSTAT_TIMELIMIT);
358  assert(solstatup != SCIP_LPSOLSTAT_UNBOUNDEDRAY);
359 
360  /* break the branching rule if an error occurred, problem was not solved, iteration or time limit was reached */
361  if( lperror )
362  {
363  SCIPdebugMsg(scip, "error solving up node probing LP: status=%d\n", solstatup);
364  SCIPstatistic(branchruledata->noupdate = TRUE);
365  break;
366  }
367 
368  upobjval = SCIPgetLPObjval(scip);
369  upinf = upinf || SCIPisGE(scip, upobjval, SCIPgetCutoffbound(scip));
370  assert(((solstatup != SCIP_LPSOLSTAT_INFEASIBLE) && (solstatup != SCIP_LPSOLSTAT_OBJLIMIT)) || upinf);
371 
372  SCIPdebugMsg(scip, " down node objval: %g up node objval: %g\n", downobjval, upobjval);
373 
374  if( !upinf )
375  {
376  /* when an optimal solution has been found calculate up child's estimate based on pseudo costs */
377  /* estimate = lowerbound + sum(min{f_j * pscdown_j, (1-f_j) * pscup_j}) */
378  estimateprobup = SCIPnodeGetLowerbound(node);
379  SCIP_CALL( SCIPgetLPBranchCands(scip, &upvars, &upvarssols, NULL, &nupvars, NULL, NULL) );
380 
381  for( k = 0 ; k < nupvars; k++ )
382  {
383  SCIP_Real estimateincr;
384  SCIP_Real pscdown;
385  SCIP_Real pscup;
386 
387  assert(upvars != NULL);
388  assert(upvars[k] != NULL);
389 
390  pscdown = SCIPvarGetPseudocost(upvars[k], scip->stat, SCIPsetFeasFloor(scip->set, upvarssols[k]) - upvarssols[k]);
391  pscup = SCIPvarGetPseudocost(upvars[k], scip->stat, SCIPsetFeasCeil(scip->set, upvarssols[k]) - upvarssols[k]);
392  estimateincr = MIN(pscdown, pscup);
393  estimateprobup += estimateincr;
394  }
395  }
396  SCIP_CALL( SCIPbacktrackProbing(scip, 0) );
397 
398  /* check whether the children nodes are solved to optimality and give a valid new lower bound or not */
399  if( downinf || upinf )
400  {
401  /* check if the LP is a valid relaxation and we can then collect new information */
402  if( allcolsinlp )
403  {
404  /* cut off the node either when both children are infeasible or the objective limit was reached;
405  * if only one child is feasible with LP value smaller than objective limit, add the corresponding
406  * constraint to the problem and break the branching rule in order to solve the updated LP
407  */
408  if( downinf && upinf )
409  {
410  SCIPdebugMsg(scip, "node can be cut off due to strong branching on multi-aggregated variable <%s>\n",
411  SCIPvarGetName(fixvars[i]));
412  SCIPstatistic(branchruledata->nmultaggrcutoff += 1);
413 
414  *result = SCIP_CUTOFF;
415  break;
416  }
417  else
418  {
419  assert(!lperror);
420 
421  if( downinf )
422  downnodeinf = TRUE;
423 
424  SCIPdebugMsg(scip, "%s child of multi-aggregated variable <%s> is infeasible\n",
425  downinf ? "down" : "up", SCIPvarGetName(fixvars[i]) );
426  SCIPstatistic(branchruledata->nmultaggrconsadd += 1);
427 
428  *result = SCIP_CONSADDED;
429  break;
430  }
431  }
432  }
433  else
434  {
435  /* if both children are solved to optimality and they both give a new valid bound, calculate the score of the
436  * multi-aggregated variable
437  */
438  SCIP_Real downgain;
439  SCIP_Real upgain;
440  SCIP_Real down;
441  SCIP_Real up;
442  SCIP_Real score;
443  SCIP_Real minbound;
444 
445  assert(!downinf);
446  assert(!upinf);
447  assert(!lperror);
448 
449  SCIPdebugMsg(scip, " both probing nodes are valid while branching on multi-aggregated variable: <%s>\n ", SCIPvarGetName(fixvars[i]));
450 
451  down = MAX(downobjval, lpobjval);
452  up = MAX(upobjval, lpobjval);
453  downgain = down - lpobjval;
454  upgain = up - lpobjval;
455  score = SCIPgetBranchScore(scip, NULL, downgain, upgain);
456 
457  if( allcolsinlp && !exactsolve )
458  {
459  /* the minimal lower bound of both children is a proved lower bound of the current subtree */
460  minbound = MIN(downobjval, upobjval);
461  *provedbound = MAX(*provedbound, minbound);
462  }
463 
465  if( score > *bestmultaggrscore )
466  *bestmultaggrscore = score;
467  );
468 
469  /* update the best branching candidate and all its values if a strictly greater score has been found */
470  if( score > *bestscore )
471  {
473  if( branchruledata->nmultaggrbranch == 0 )
474  {
475  branchruledata->rundepth = SCIPgetNRuns(scip);
476  branchruledata->firstmultaggrdepth = SCIPgetFocusDepth(scip);
477  }
478  )
479 
480  SCIPdebugMsg(scip, " <%s> is a better candidate for branching\n", SCIPvarGetName(fixvars[i]));
481 
482  *bestscore = MAX(score, *bestscore);
483  *bestcand = fixvars[i];
484  *bestsol = fixvarssol;
485  *bestdown = downobjval;
486  *bestup = upobjval;
487  *bestdownvalid = TRUE;
488  *bestupvalid = TRUE;
489  *estimatedown = estimateprobdown;
490  *estimateup = estimateprobup;
491  }
492  assert(bestscore != NULL);
493  assert(bestcand != NULL);
494  assert(bestup != NULL);
495  assert(bestdown != NULL);
496  }
497  }
498  }
499  }
500 
501  /* end probing mode */
502  if( endprobing )
503  {
504  SCIP_CALL( SCIPendProbing(scip) );
505  }
506 
507  SCIPdebugMsg(scip, "\n");
508 
509  /* one of the child nodes was infeasible, add the other constraint to the current node */
510  if( *result == SCIP_CONSADDED )
511  {
512  node = SCIPgetCurrentNode(scip);
513  if( downnodeinf )
514  {
515  SCIP_CALL( SCIPcreateConsLinear(scip, &probingconsup, "infconsup", SCIPvarGetMultaggrNVars(fixvars[i]),
516  SCIPvarGetMultaggrVars(fixvars[i]), SCIPvarGetMultaggrScalars(fixvars[i]),
517  SCIPfeasCeil(scip, fixvarssols[i]) - SCIPvarGetMultaggrConstant(fixvars[i]), SCIPinfinity(scip),
519  assert(probingconsup != NULL);
520  SCIP_CALL( SCIPaddConsNode(scip, node, probingconsup, NULL) );
521  SCIPdebugMsg(scip, " <%s> new valid constraint has been added to the original problem\n", SCIPconsGetName(probingconsup));
522  SCIP_CALL( SCIPreleaseCons(scip, &probingconsup) );
523  }
524  else
525  {
526  SCIP_CALL( SCIPcreateConsLinear(scip, &probingconsdown, "infconsdown", SCIPvarGetMultaggrNVars(fixvars[i]),
527  SCIPvarGetMultaggrVars(fixvars[i]), SCIPvarGetMultaggrScalars(fixvars[i]), - SCIPinfinity(scip),
528  SCIPfeasFloor(scip, fixvarssols[i]) - SCIPvarGetMultaggrConstant(fixvars[i]), TRUE, TRUE, FALSE, FALSE,
529  TRUE, TRUE, FALSE, FALSE, FALSE, TRUE) );
530  assert(probingconsdown != NULL);
531  SCIP_CALL( SCIPaddConsNode(scip, node, probingconsdown, NULL) );
532  SCIPdebugMsg(scip, " <%s> new valid constraint has been added to the original problem\n", SCIPconsGetName(probingconsdown));
533  SCIP_CALL( SCIPreleaseCons(scip, &probingconsdown) );
534  }
535  }
536  SCIPfreeBufferArray(scip, &fixvarssols);
537  }
538  return SCIP_OKAY;
539 }
540 
541 
542 /*
543  * Callback methods of branching rule
544  */
545 
546 /** copy method for branchrule plugins (called when SCIP copies plugins) */
547 static
548 SCIP_DECL_BRANCHCOPY(branchCopyMultAggr)
549 { /*lint --e{715}*/
550  assert(scip != NULL);
551  assert(branchrule != NULL);
552  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
553 
554  /* call inclusion method of branchrule */
556 
557  return SCIP_OKAY;
558 }
559 
560 /** destructor of branching rule to free user data (called when SCIP is exiting) */
561 static
562 SCIP_DECL_BRANCHFREE(branchFreeMultAggr)
563 { /*lint --e{715}*/
564  SCIP_BRANCHRULEDATA* branchruledata;
566  /* free branching rule data */
567  branchruledata = SCIPbranchruleGetData(branchrule);
568  assert(branchruledata != NULL);
569 
570  SCIPstatistic(SCIPfreeBlockMemoryArrayNull(scip , &branchruledata->ratioggain, branchruledata->size));
571  SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->skipdown, branchruledata->skipsize);
572  SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->skipup, branchruledata->skipsize);
573 
574  SCIPfreeBlockMemory(scip, &branchruledata);
575  SCIPbranchruleSetData(branchrule, NULL);
576 
577  return SCIP_OKAY;
578 }
579 
580 /** initialization method of branching rule (called after problem was transformed) */
581 static
582 SCIP_DECL_BRANCHINIT(branchInitMultAggr)
583 { /*lint --e{715}*/
584  SCIP_BRANCHRULEDATA* branchruledata;
586  branchruledata = SCIPbranchruleGetData(branchrule);
587  assert(branchruledata != NULL);
588 
589  branchruledata->lastcand = 0;
591  branchruledata->firstmultaggrdepth = 0;
592  branchruledata->nmultaggrbranch = 0;
593  branchruledata->nfracbranch = 0;
594  branchruledata->nEscore = 0;
595  branchruledata->nmultaggrcutoff = 0;
596  branchruledata->nmultaggrconsadd = 0;
597  branchruledata->nfractcutoff = 0;
598  branchruledata->nfractconsadd = 0;
599  branchruledata->nrun = 0;
600  branchruledata->size = 100;
601  branchruledata->ameanratio = 0.0;
602  branchruledata->noupdate = FALSE;
603  branchruledata->clckstrongbr = NULL;
604  branchruledata->clckmultaggrbr = NULL;
605  branchruledata->nstrongbrcall = 0;
606  branchruledata->nmultaggrbrcall = 0;
607  branchruledata->totalmultaggrcands = 0;
608  branchruledata->totallpcands = 0;
609  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->ratioggain, branchruledata->size) );
610  BMSclearMemoryArray(branchruledata->ratioggain, branchruledata->size);
611  SCIP_CALL( SCIPcreateClock(scip, &branchruledata->clckstrongbr) );
612  SCIP_CALL( SCIPcreateClock(scip, &branchruledata->clckmultaggrbr) );
613  )
614  return SCIP_OKAY;
615 }
616 
617 /** deinitialization method of branching rule (called before transformed problem is freed) */
618 static
619 SCIP_DECL_BRANCHEXIT(branchExitMultAggr)
620 { /*lint --e{715}*/
621  SCIP_BRANCHRULEDATA* branchruledata;
622  SCIPstatistic(int j = 0);
623 
624  /* initialize branching rule data */
625  branchruledata = SCIPbranchruleGetData(branchrule);
626  assert(branchruledata != NULL);
627  assert((branchruledata->skipdown != NULL) == (branchruledata->skipup != NULL));
628 
629  /* print statistics */
632  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Multi-aggregated branching stats : \n");
633  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " nmultaggrvars : %d (last run)\n",
634  branchruledata->nmultaggrvars);
635  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " firstmultaggrbranchdepth : %d (in run %d)\n",
636  branchruledata->firstmultaggrdepth,
637  branchruledata->rundepth);
638  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " nmultaggrbranch : %d (tot %d)\n",
639  branchruledata->nmultaggrbranch, branchruledata->nmultaggrbranch + branchruledata->nfracbranch);
640  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " nmultaggrcutoff : %d\n", branchruledata->nmultaggrcutoff);
641  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " nmultaggrconsadd : %d\n", branchruledata->nmultaggrconsadd);
642  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " nfractcutoff : %d\n", branchruledata->nfractcutoff);
643  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " nfractconsadd : %d\n", branchruledata->nfractconsadd);
644  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " nEscore : %d\n", branchruledata->nEscore);
645 
646  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " Branching Time : \n");
647  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " nstrongbrcall : %d\n", branchruledata->nstrongbrcall);
648  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " totalstrongbrtime : %g\n",
649  SCIPgetClockTime(scip, branchruledata->clckstrongbr));
650  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " totallpcands : %d\n", branchruledata->totallpcands);
651 
652  if( branchruledata->totallpcands != 0 )
653  {
654  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " averagetimestrongbr : %g\n",
655  SCIPgetClockTime(scip, branchruledata->clckstrongbr) / branchruledata->totallpcands);
656  }
657  else
658  {
659  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " averagetimestrongbr : %s\n", "--");
660  }
661 
662  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " nmultaggrbrcall : %d\n", branchruledata->nmultaggrbrcall);
663  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " totalmultaggrbrtime : %g\n",
664  SCIPgetClockTime(scip, branchruledata->clckmultaggrbr));
665  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " totalmultaggrcands : %d\n", branchruledata->totalmultaggrcands);
666 
667  if( branchruledata->totalmultaggrcands != 0 )
668  {
669  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " averagetimemultaggrbr : %g\n",
670  SCIPgetClockTime(scip, branchruledata->clckmultaggrbr) / branchruledata->totalmultaggrcands);
671  }
672  else
673  {
674  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " averagetimemultaggrbr : %s\n", "--");
675  }
676 
677  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " Ratioggain :\n");
678  if( branchruledata->nmultaggrbranch != 0 )
679  {
680  for( j = 0; j < branchruledata->nmultaggrbranch; j++ )
681  {
682  branchruledata->ameanratio += branchruledata->ratioggain[j];
683  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " %g", branchruledata->ratioggain[j]);
684  }
685 
687  branchruledata->ameanratio = branchruledata->ameanratio / branchruledata->nmultaggrbranch;
689  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " ameanratio : %4.2f\n", branchruledata->ameanratio);
690  }
691  else
692  {
693  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " ameanratio : %s\n", "--");
694  }
695 
697 
698  /* free arrays */
699  if( branchruledata->ratioggain != NULL )
700  {
701  SCIPfreeMemoryArray(scip, &branchruledata->ratioggain);
702  branchruledata->ratioggain = NULL;
703  }
704  SCIP_CALL( SCIPfreeClock(scip, &branchruledata->clckstrongbr) );
705  SCIP_CALL( SCIPfreeClock(scip, &branchruledata->clckmultaggrbr) );
706  )
707  if( branchruledata->skipdown != NULL )
708  {
709  SCIPfreeBlockMemoryArray(scip, &branchruledata->skipup, branchruledata->skipsize);
710  SCIPfreeBlockMemoryArray(scip, &branchruledata->skipdown, branchruledata->skipsize);
711  branchruledata->skipdown = NULL;
712  branchruledata->skipup = NULL;
713  branchruledata->skipsize = 0;
714  }
715  return SCIP_OKAY;
716 }
717 
718 /** branching execution method for fractional LP solutions */
719 static
720 SCIP_DECL_BRANCHEXECLP(branchExeclpMultAggr)
721 { /*lint --e{715}*/
722 
723  SCIP_BRANCHRULEDATA* branchruledata;
724  SCIP_VAR** lpcands;
725  SCIP_VAR** tmplpcands;
726  SCIP_Real* lpcandssol;
727  SCIP_Real* lpcandsfrac;
728  SCIP_Real* tmplpcandssol;
729  SCIP_Real* tmplpcandsfrac;
730  SCIP_NODE* downchild;
731  SCIP_NODE* upchild;
732  SCIP_Real bestup;
733  SCIP_Real bestdown;
734  SCIP_Real bestscore;
735  SCIP_Real provedbound;
736  SCIP_Real estimatedown = 0.0;
737  SCIP_Real estimateup = 0.0;
738  SCIP_Bool bestdownvalid;
739  SCIP_Bool bestupvalid;
740  SCIP_Longint oldreevalage;
741  int bestcandpos;
742  int nlpcands;
743  int npriolpcands;
745  SCIP_Real lpobjval;
746  SCIP_Bool reoptimize;
747  )
748 
749  assert(branchrule != NULL);
750  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
751  assert(scip != NULL);
752  assert(result != NULL);
753 
754  SCIPdebugMsg(scip, "Execlp method of mult-aggreg branching\n ");
755  *result = SCIP_DIDNOTRUN;
756 
757  /* get branching rule data */
758  branchruledata = SCIPbranchruleGetData(branchrule);
759  assert(branchruledata != NULL);
760 
761  SCIP_CALL( SCIPgetLongintParam(scip, "branching/fullstrong/reevalage", &oldreevalage) );
762  SCIP_CALL( SCIPsetLongintParam(scip, "branching/fullstrong/reevalage", branchruledata->reevalage) );
763 
764  /* get the lpobjval and the number of multi aggregated variables of the problem as a statistic counter */
766  reoptimize = FALSE;
767  lpobjval = SCIPgetLPObjval(scip);
768 
769  if( SCIPgetNRuns(scip) != branchruledata->nrun )
770  {
771  SCIP_VAR** fixvars = NULL;
772  int nfixvars;
773  int i;
774 
775  branchruledata->nmultaggrvars = 0;
776  fixvars = SCIPgetFixedVars(scip);
777  nfixvars = SCIPgetNFixedVars(scip);
778 
779  if( nfixvars != 0 )
780  {
781  for( i = 0; i < nfixvars; i++ )
782  {
783  if( SCIPvarGetStatus(fixvars[i]) == SCIP_VARSTATUS_MULTAGGR && (SCIPvarGetType(fixvars[i]) == SCIP_VARTYPE_INTEGER ||
784  SCIPvarGetType(fixvars[i]) == SCIP_VARTYPE_BINARY) )
785  {
786  branchruledata->nmultaggrvars += 1;
787  }
788  }
789  }
790  branchruledata->nrun = SCIPgetNRuns(scip);
791  }
792  )
793 
794  /* get all branching candidates */
795  SCIP_CALL( SCIPgetLPBranchCands(scip, &tmplpcands, &tmplpcandssol, &tmplpcandsfrac, &nlpcands, &npriolpcands, NULL) );
796  assert(nlpcands > 0);
797  assert(npriolpcands > 0);
798 
799  /* copy LP branching candidates and solution values, because they will be updated w.r.t. the strong branching LP
800  * solution
801  */
802  SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcands, tmplpcands, nlpcands) );
803  SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcandssol, tmplpcandssol, nlpcands) );
804  SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcandsfrac, tmplpcandsfrac, nlpcands) );
805 
806  if( branchruledata->skipdown == NULL )
807  {
808  assert(branchruledata->skipup == NULL);
809 
810  branchruledata->skipsize = SCIPgetNVars(scip);
811  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipdown, branchruledata->skipsize) );
812  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipup, branchruledata->skipsize) );
813  BMSclearMemoryArray(branchruledata->skipdown, branchruledata->skipsize);
814  BMSclearMemoryArray(branchruledata->skipup, branchruledata->skipsize);
815  }
816 
817  /* start the clock to get the time spent inside the function */
819  SCIP_CALL( SCIPstartClock(scip, branchruledata->clckstrongbr) );
820  );
821 
822  /* compute strong branching among the array of fractional variables in order to get the best one */
823  SCIP_CALL( SCIPselectVarStrongBranching(scip, lpcands, lpcandssol, lpcandsfrac, branchruledata->skipdown,
824  branchruledata->skipup, nlpcands, npriolpcands, nlpcands, &branchruledata->lastcand, allowaddcons,
825  branchruledata->maxproprounds, branchruledata->probingbounds, TRUE,
826  &bestcandpos, &bestdown, &bestup, &bestscore, &bestdownvalid, &bestupvalid, &provedbound, result) );
827 
829  SCIP_CALL( SCIPstopClock(scip, branchruledata->clckstrongbr) );
830  branchruledata->totallpcands += SCIPgetNLPBranchCands(scip);
831  branchruledata->nstrongbrcall += 1;
832  )
833 
834  if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM && *result != SCIP_CONSADDED )
835  {
836  SCIP_VAR* bestcand = lpcands[bestcandpos];
837  SCIP_Real bestsol = lpcandssol[bestcandpos];
838  SCIPstatistic( SCIP_Real bestmultaggrscore = -SCIPinfinity(scip); )
839 
841  SCIP_Real fdowngain = 0.0;
842  SCIP_Real fupgain = 0.0;
843 
844  /* reoptimize is set to true if strong branching on fractional variables did not explicitly evaluate the objective
845  * values of the probing child nodes and thus we do not have updated information
846  */
847  if( SCIPisLT(scip, SCIPgetVarStrongbranchLPAge(scip, bestcand), branchruledata->reevalage)
848  || branchruledata->maxproprounds != 0 )
849  reoptimize = TRUE;
850 
851  /* store values needed for the ratioggain statistic */
852  if( !reoptimize )
853  {
854  SCIP_Real fdown;
855  SCIP_Real fup;
856 
857  fdown = MAX(bestdown, lpobjval);
858  fup = MAX(bestup, lpobjval);
859  fdowngain = fdown - lpobjval;
860  fupgain = fup - lpobjval;
861  }
862 
863  /* start and then stop the clock to get the time spent inside the function */
864  SCIP_CALL( SCIPstartClock(scip, branchruledata->clckmultaggrbr) );
865  )
866 
867  /* compute strong branching among the multi-aggregated variables and the best fractional variable */
868 #ifdef SCIP_STATISTIC
869  SCIP_CALL( selectVarMultAggrBranching(scip, &bestcand, &bestscore, &bestsol, &bestdown, &bestup, &bestdownvalid, &bestupvalid, &provedbound,
870  &estimatedown, &estimateup, &bestmultaggrscore, result) );
871 #else
872  SCIP_CALL( selectVarMultAggrBranching(scip, &bestcand, &bestscore, &bestsol, &bestdown, &bestup, &bestdownvalid, &bestupvalid, &provedbound,
873  &estimatedown, &estimateup, result) );
874 #endif
876  SCIP_CALL( SCIPstopClock(scip, branchruledata->clckmultaggrbr) );
877  branchruledata->nmultaggrbrcall += 1;
878  )
879 
880  if( *result != SCIP_CUTOFF && *result != SCIP_CONSADDED )
881  {
883  if( !(branchruledata->noupdate) )
884  {
885  if( SCIPisEQ(scip, bestmultaggrscore, bestscore) )
886  branchruledata->nEscore += 1;
887  }
888  )
889 
890  assert(bestcand != NULL);
891  SCIPdebugMsg(scip, "BRANCHING MODE:\n");
892 
893  /* perform branching on the best found candidate */
894  if( SCIPvarGetStatus(bestcand) == SCIP_VARSTATUS_MULTAGGR )
895  {
896  SCIP_CONS* multaggrconsdown;
897  SCIP_CONS* multaggrconsup;
898 
900  if( !(branchruledata->noupdate) )
901  {
902  branchruledata->nmultaggrbranch += 1;
903 
904  if( !reoptimize )
905  {
906  SCIP_Real gfractbranch;
907  SCIP_Real gmultaggrbranch;
908  SCIP_Real downgain;
909  SCIP_Real upgain;
910  SCIP_Real down;
911  SCIP_Real up;
912  int nmultaggrbranch;
913 
914  down = MAX(bestdown, lpobjval);
915  up = MAX(bestup, lpobjval);
916  downgain = down - lpobjval;
917  upgain = up - lpobjval;
918 
919  SCIP_CALL( ensureArraySize(scip, branchruledata) );
920 
921  gfractbranch= SQRT(MAX(fdowngain,1e-06) * MAX(fupgain,1e-06));
922  gmultaggrbranch = SQRT(MAX(downgain,1e-06) * MAX(upgain,1e-06));
923 
924  nmultaggrbranch = branchruledata->nmultaggrbranch;
925 
926  if( gmultaggrbranch == 0.0 )
927  {
928  branchruledata->ratioggain[nmultaggrbranch - 1] = 1;
929  }
930  else
931  {
932  branchruledata->ratioggain[nmultaggrbranch - 1] = gfractbranch / gmultaggrbranch;
933  }
934  }
935  }
936  )
937 
938  /* create the multi-aggregated constraints rounded up and down */
939  SCIP_CALL( SCIPcreateConsLinear(scip, &multaggrconsdown, "consdown", SCIPvarGetMultaggrNVars(bestcand),
940  SCIPvarGetMultaggrVars(bestcand), SCIPvarGetMultaggrScalars(bestcand), - SCIPinfinity(scip),
941  SCIPfeasFloor(scip, bestsol) - SCIPvarGetMultaggrConstant(bestcand),
943 
944  SCIP_CALL( SCIPcreateConsLinear(scip, &multaggrconsup, "consup", SCIPvarGetMultaggrNVars(bestcand),
946  SCIPfeasCeil(scip, bestsol) - SCIPvarGetMultaggrConstant(bestcand), SCIPinfinity(scip),
948 
949  /* create the child nodes */
950  SCIP_CALL( SCIPcreateChild(scip, &downchild, 1.0, estimatedown) );
951  SCIPdebugMsg(scip, " down node: lowerbound %f estimate %f\n", SCIPnodeGetLowerbound(downchild), SCIPnodeGetEstimate(downchild));
952 
953  SCIP_CALL( SCIPcreateChild(scip, &upchild, 1.0, estimateup) );
954  SCIPdebugMsg(scip, " up node: lowerbound %f estimate %f\n", SCIPnodeGetLowerbound(upchild), SCIPnodeGetEstimate(upchild));
955 
956  assert(downchild != NULL);
957  assert(upchild != NULL);
958 
959  SCIP_CALL( SCIPaddConsNode(scip, downchild, multaggrconsdown, NULL) );
960  SCIP_CALL( SCIPaddConsNode(scip, upchild, multaggrconsup, NULL) );
961 
962 #ifdef PRINTNODECONS
963  SCIPdebugMsg(scip, "branching at node %lld\n", SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
964 
965  SCIPdebugMsg(scip, "created child node %lld with constraint:\n", SCIPnodeGetNumber(downchild));
966  SCIP_CALL( SCIPprintCons(scip, multaggrconsdown, NULL) );
967  SCIPinfoMessage(scip, NULL, "\n");
968 
969  SCIPdebugMsg(scip, "created child node %lld with constraint:\n", SCIPnodeGetNumber(upchild));
970  SCIP_CALL( SCIPprintCons(scip, multaggrconsup, NULL) );
971  SCIPinfoMessage(scip, NULL, "\n");
972 #endif
973 
974  /* relase constraints */
975  SCIP_CALL( SCIPreleaseCons(scip, &multaggrconsdown) );
976  SCIP_CALL( SCIPreleaseCons(scip, &multaggrconsup) );
977 
978  SCIPdebugMsg(scip, "BRANCHED on multi-aggregated variable <%s>\n", SCIPvarGetName(bestcand));
979 
980  *result = SCIP_BRANCHED;
981  }
982  else
983  {
985  if( !(branchruledata->noupdate) )
986  branchruledata->nfracbranch += 1
987  );
988 
989  assert(*result == SCIP_DIDNOTRUN);
990  assert(SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip)));
991 
992  SCIP_CALL( SCIPbranchVarVal(scip, bestcand, bestsol, &downchild, NULL, &upchild) );
993 
994  assert(downchild != NULL);
995  assert(upchild != NULL);
996 
997  SCIPdebugMsg(scip, "BRANCHED on fractional variable <%s>\n", SCIPvarGetName(bestcand));
998 
999  *result = SCIP_BRANCHED;
1000  }
1001 
1002  /* update the lower bounds in the children; we must not do this if columns are missing in the LP
1003  * (e.g., because we are doing branch-and-price) or the problem should be solved exactly
1004  */
1005  if( SCIPallColsInLP(scip) && !SCIPisExactSolve(scip) )
1006  {
1007  SCIP_CALL( SCIPupdateNodeLowerbound(scip, downchild, bestdownvalid ? MAX(bestdown, provedbound) : provedbound) );
1008  SCIP_CALL( SCIPupdateNodeLowerbound(scip, upchild, bestupvalid ? MAX(bestup, provedbound) : provedbound) );
1009  }
1010  SCIPdebugMsg(scip, " -> down child's lowerbound: %g\n", SCIPnodeGetLowerbound(downchild));
1011  SCIPdebugMsg(scip, " -> up child's lowerbound: %g\n", SCIPnodeGetLowerbound(upchild));
1012  }
1013  }
1014  else
1015  {
1016  SCIPdebugMsg(scip, "strong branching breaks\n" );
1017 
1018  SCIPstatistic(
1019  if( *result == SCIP_CUTOFF )
1020  {
1021  branchruledata->nfractcutoff += 1;
1022  }
1023  else
1024  {
1025  branchruledata->nfractconsadd += 1;
1026  }
1027  )
1028  }
1029 
1030  SCIPfreeBufferArray(scip, &lpcandsfrac);
1031  SCIPfreeBufferArray(scip, &lpcandssol);
1032  SCIPfreeBufferArray(scip, &lpcands);
1033 
1034  SCIP_CALL( SCIPsetLongintParam(scip, "branching/fullstrong/reevalage", oldreevalage) );
1035 
1036  return SCIP_OKAY;
1037 }
1038 
1039 /*
1040  * branching rule specific interface methods
1041  */
1042 
1043 /** creates the multi-aggregated branching rule and includes it in SCIP */
1045  SCIP* scip /**< SCIP data structure */
1046  )
1048  SCIP_BRANCHRULEDATA* branchruledata;
1049  SCIP_BRANCHRULE* branchrule;
1050 
1051  /* create multaggr branching rule data */
1052  SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
1053  branchruledata->lastcand = 0;
1054  branchruledata->skipsize = 0;
1055  branchruledata->skipup = NULL;
1056  branchruledata->skipdown = NULL;
1057  SCIPstatistic(branchruledata->ratioggain = NULL);
1058 
1059  /* include branching rule */
1061  BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
1062 
1063  assert(branchrule != NULL);
1064 
1065  /* set non fundamental callbacks via setter functions */
1066  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyMultAggr) );
1067  SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeMultAggr) );
1068  SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitMultAggr) );
1069  SCIP_CALL( SCIPsetBranchruleExit(scip, branchrule, branchExitMultAggr) );
1070  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpMultAggr) );
1071 
1072  /* multi-aggregated branching rule parameters */
1074  "branching/multaggr/reevalage",
1075  "number of intermediate LPs solved to trigger reevaluation of strong branching value for a variable that was already evaluated at the current node",
1076  &branchruledata->reevalage, TRUE, DEFAULT_REEVALAGE, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1077  SCIP_CALL( SCIPaddIntParam(scip,
1078  "branching/multaggr/maxproprounds",
1079  "maximum number of propagation rounds to be performed during multaggr branching before solving the LP (-1: no limit, -2: parameter settings)",
1080  &branchruledata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -2, INT_MAX, NULL, NULL) );
1082  "branching/multaggr/probingbounds",
1083  "should valid bounds be identified in a probing-like fashion during multaggr branching (only with propagation)?",
1084  &branchruledata->probingbounds, TRUE, DEFAULT_PROBINGBOUNDS, NULL, NULL) );
1085 
1086  return SCIP_OKAY;
1087 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip.c:36301
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21975
SCIP_STAT * stat
Definition: struct_scip.h:69
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip.h:21964
static SCIP_DECL_BRANCHFREE(branchFreeMultAggr)
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1780
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21958
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip.c:40680
SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var)
Definition: var.c:16961
public methods for branch and bound tree
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip.c:35291
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:42726
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7192
internal methods for clocks and timing issues
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip.c:45835
SCIP_VAR ** SCIPvarGetMultaggrVars(SCIP_VAR *var)
Definition: var.c:16949
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46037
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:43
#define DEFAULT_REEVALAGE
SCIP_RETCODE SCIPstopClock(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip.c:45180
SCIP_RETCODE SCIPsetBranchruleExit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXIT((*branchexit)))
Definition: scip.c:9121
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip.c:9089
#define FALSE
Definition: def.h:64
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4265
#define BRANCHRULE_MAXDEPTH
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:46050
#define TRUE
Definition: def.h:63
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip.c:9073
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip.c:9219
static SCIP_DECL_BRANCHEXIT(branchExitMultAggr)
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21973
#define DEFAULT_MAXPROPROUNDS
SCIP_RETCODE SCIPincludeBranchruleBasic(SCIP *scip, SCIP_BRANCHRULE **branchruleptr, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_BRANCHRULEDATA *branchruledata)
Definition: scip.c:9036
#define DEFAULT_PROBINGBOUNDS
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip.h:21999
SCIP_RETCODE SCIPfreeClock(SCIP *scip, SCIP_CLOCK **clck)
Definition: scip.c:45129
#define SCIP_LONGINT_MAX
Definition: def.h:131
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22003
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition: type_lp.h:42
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21956
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip.c:36334
#define SCIPdebugMsg
Definition: scip.h:451
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4237
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip.c:1336
static SCIP_RETCODE selectVarMultAggrBranching(SCIP *scip, SCIP_VAR **bestcand, SCIP_Real *bestscore, SCIP_Real *bestsol, SCIP_Real *bestdown, SCIP_Real *bestup, SCIP_Bool *bestdownvalid, SCIP_Bool *bestupvalid, SCIP_Real *provedbound, SCIP_Real *estimatedown, SCIP_Real *estimateup, SCIP_RESULT *result)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip.c:46457
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:46445
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip.c:9171
SCIP_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: scip.c:36756
int SCIPgetNFixedVars(SCIP *scip)
Definition: scip.c:11997
#define BRANCHRULE_NAME
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7172
SCIP_VAR ** SCIPgetFixedVars(SCIP *scip)
Definition: scip.c:11954
SCIP_Real SCIPvarGetPseudocost(SCIP_VAR *var, SCIP_STAT *stat, SCIP_Real solvaldelta)
Definition: var.c:13780
SCIP_RETCODE SCIPcreateClock(SCIP *scip, SCIP_CLOCK **clck)
Definition: scip.c:45078
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45998
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:7881
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip.c:35326
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16555
SCIP_Real SCIPsetFeasCeil(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6093
#define NULL
Definition: lpi_spx1.cpp:137
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:17543
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip.c:36877
internal methods for global SCIP settings
#define SCIP_CALL(x)
Definition: def.h:316
SCIP main data structure.
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip.c:35886
SCIP_Real SCIPvarGetMultaggrConstant(SCIP_VAR *var)
Definition: var.c:16973
SCIP_RETCODE SCIPbranchVarVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip.c:36986
SCIP_Longint SCIPgetVarStrongbranchLPAge(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:21284
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip.c:1353
SCIP_RETCODE SCIPgetLongintParam(SCIP *scip, const char *name, SCIP_Longint *value)
Definition: scip.c:4442
#define BRANCHRULE_MAXBOUNDDIST
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
Definition: scip.c:13009
internal methods for problem variables
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21991
full strong LP branching rule
fullstrong branching on fractional and multi-aggregated variables
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:28948
static SCIP_DECL_BRANCHINIT(branchInitMultAggr)
SCIP_Real SCIPgetClockTime(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip.c:45312
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:42321
SCIP_RETCODE SCIPupdateNodeLowerbound(SCIP *scip, SCIP_NODE *node, SCIP_Real newbound)
Definition: scip.c:13443
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1790
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip.c:28746
#define MAX(x, y)
Definition: tclique_def.h:75
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip.h:21940
int SCIPgetNRuns(SCIP *scip)
Definition: scip.c:41326
Constraint handler for linear constraints in their most general form, .
int SCIPvarGetMultaggrNVars(SCIP_VAR *var)
Definition: var.c:16937
#define SCIP_MAXTREEDEPTH
Definition: def.h:252
#define BRANCHRULE_DESC
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11680
SCIP_Real SCIPnodeGetEstimate(SCIP_NODE *node)
Definition: tree.c:7202
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_Real SCIPsetFeasFloor(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6082
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip.c:29027
SCIP_RETCODE SCIPincludeBranchruleMultAggr(SCIP *scip)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip.c:27417
SCIP_SET * set
Definition: struct_scip.h:62
SCIP_RETCODE SCIPselectVarStrongBranching(SCIP *scip, SCIP_VAR **lpcands, SCIP_Real *lpcandssol, SCIP_Real *lpcandsfrac, SCIP_Bool *skipdown, SCIP_Bool *skipup, int nlpcands, int npriolpcands, int ncomplete, int *start, SCIP_Bool allowaddcons, int maxproprounds, SCIP_Bool probingbounds, SCIP_Bool forcestrongbranch, int *bestcand, SCIP_Real *bestdown, SCIP_Real *bestup, SCIP_Real *bestscore, SCIP_Bool *bestdownvalid, SCIP_Bool *bestupvalid, SCIP_Real *provedbound, SCIP_RESULT *result)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16674
#define SCIPstatistic(x)
Definition: pub_message.h:101
static SCIP_DECL_BRANCHCOPY(branchCopyMultAggr)
#define SCIP_Real
Definition: def.h:145
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1902
#define MIN(x, y)
Definition: memory.c:75
static SCIP_DECL_BRANCHEXECLP(branchExeclpMultAggr)
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: scip.c:9105
#define BRANCHRULE_PRIORITY
#define SCIP_Longint
Definition: def.h:130
SCIP_Bool SCIPallColsInLP(SCIP *scip)
Definition: scip.c:29374
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16720
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip.h:21976
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip.c:35231
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:46421
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip.c:35185
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:89
SCIP_RETCODE SCIPstartClock(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip.c:45163
SCIP_Bool SCIPisExactSolve(SCIP *scip)
Definition: scip.c:1025
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip.c:4718
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4211