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