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