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