Scippy

SCIP

Solving Constraint Integer Programs

branch_cloud.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file branch_cloud.c
17  * @brief cloud branching rule
18  * @author Timo Berthold
19  * @author Domenico Salvagnin
20  *
21  * Branching rule based on muliple optimal solutions to the current LP relaxation. See@n
22  * Cloud Branching@n
23  * Timo Berthold and Domenico Salvagnin@n
24  * Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR 2013, LNCS 7874@n
25  * Preliminary version available as <a href="http://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1730">ZIB-Report 13-01</a>.
26  */
27 
28 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
29 
30 #include <assert.h>
31 #include <string.h>
32 
33 #include "scip/branch_cloud.h"
34 #include "scip/branch_fullstrong.h"
36 
37 
38 #define BRANCHRULE_NAME "cloud"
39 #define BRANCHRULE_DESC "branching rule that considers several alternative LP optima"
40 #define BRANCHRULE_PRIORITY 0
41 #define BRANCHRULE_MAXDEPTH -1
42 #define BRANCHRULE_MAXBOUNDDIST 1.0
43 
44 #define DEFAULT_USECLOUD TRUE /**< should a cloud of points be used? */
45 #define DEFAULT_USEUNION FALSE /**< should the union of candidates be used? */
46 #define DEFAULT_MAXPOINTS -1 /**< maximum number of points for the cloud (-1 means no limit) */
47 #define DEFAULT_MINSUCCESSRATE 0.0 /**< minimum success rate for the cloud */
48 #define DEFAULT_MINSUCCESSUNION 0.0 /**< minimum success rate for the union */
49 #define DEFAULT_MAXDEPTHUNION 65000 /**< maximum depth for the union */
50 #define DEFAULT_ONLYF2 FALSE /**< should only F2 be used? */
51 
52 /*
53  * Data structures
54  */
55 
56 /** branching rule data */
57 struct SCIP_BranchruleData
58 {
59  int lastcand; /**< last evaluated candidate of last branching rule execution */
60  SCIP_Bool usecloud; /**< should a cloud of points be used? */
61  SCIP_Bool useunion; /**< should the union of candidates be used? */
62  SCIP_Bool onlyF2; /**< should only F2 be used? */
63  int maxpoints; /**< maximum number of points for the cloud (-1 means no limit) */
64  SCIP_Real minsuccessrate; /**< minimum success rate for the cloud */
65  SCIP_Real minsuccessunion; /**< minimum success rate for the union */
66  SCIP_CLOCK* cloudclock; /**< clock for cloud diving */
67  SCIP_Bool* skipdown; /**< should down branch be skiped? */
68  SCIP_Bool* skipup; /**< should up branch be skiped? */
69  int ntried; /**< number of times the cloud was tried */
70  int ntriedunions; /**< number of times the cloud was tried */
71  int nuseful; /**< number of times the cloud was useful (at least one LP skipped) */
72  int nusefulunions; /**< number of times the union was useful (took candidate from new list) */
73  int ncloudpoints; /**< sum of cloud points taken over all nodes with at least two poitns in cloud */
74  int nsavedlps; /**< sum of saved LPs taken over all nodes with at least two points in cloud */
75  int maxdepthunion; /**< maximum depth for the union */
76  int skipsize; /**< size of skipdown and skipup array */
77 };
78 
79 /*
80  * Callback methods of branching rule
81  */
82 
83 /** destructor of branching rule to free user data (called when SCIP is exiting) */
84 static
85 SCIP_DECL_BRANCHFREE(branchFreeCloud)
86 { /*lint --e{715}*/
87  SCIP_BRANCHRULEDATA* branchruledata;
88 
89  /* free branching rule data */
90  branchruledata = SCIPbranchruleGetData(branchrule);
91 
92  if( branchruledata->cloudclock != NULL)
93  {
95  int ntried;
96  int nuseful;
97  int ncloudpoints;
98  int nsavedlps;
99 
100  ntried = branchruledata->ntried;
101  nuseful = branchruledata->nuseful;
102  ncloudpoints = branchruledata->ncloudpoints;
103  nsavedlps = branchruledata->nsavedlps;
104 
105  SCIPstatisticMessage("time spent diving in cloud branching: %g\n", SCIPgetClockTime(scip, branchruledata->cloudclock));
106  SCIPstatisticMessage("cloud branching tried: %6d found cloud: %6d \n", ntried, nuseful);
107  SCIPstatisticMessage("cloud used points: %6d saved LPs: %6d \n", ncloudpoints, nsavedlps);
108  SCIPstatisticMessage("cloud success rates useful/tried: %8.6g points/useful: %8.6g saved/useful: %8.6g \n",
109  ntried == 0 ? -1 : (SCIP_Real)nuseful / ntried, nuseful == 0 ? -1 : (SCIP_Real)ncloudpoints / nuseful, nuseful == 0 ? -1 : (SCIP_Real)nsavedlps / nuseful);
110  )
111 
112  SCIP_CALL( SCIPfreeClock(scip, &(branchruledata->cloudclock)) );
113  }
114 
115  SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->skipdown, branchruledata->skipsize);
116  SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->skipup, branchruledata->skipsize);
117 
118  SCIPfreeBlockMemory(scip, &branchruledata);
119  SCIPbranchruleSetData(branchrule, NULL);
120 
121  return SCIP_OKAY;
122 }
123 
124 
125 /** initialization method of branching rule (called after problem was transformed) */
126 static
127 SCIP_DECL_BRANCHINIT(branchInitCloud)
128 { /*lint --e{715}*/
129  SCIP_BRANCHRULEDATA* branchruledata;
130 
131  /* initialize branching rule data */
132  branchruledata = SCIPbranchruleGetData(branchrule);
133  branchruledata->lastcand = 0;
134  branchruledata->nuseful = 0;
135  branchruledata->nusefulunions = 0;
136  branchruledata->ntried = 0;
137  branchruledata->ntriedunions = 0;
138  branchruledata->ncloudpoints = 0;
139  branchruledata->nsavedlps = 0;
140 
141  if( branchruledata->cloudclock != NULL)
142  {
143  SCIP_CALL( SCIPresetClock(scip, branchruledata->cloudclock) );
144  }
145 
146  return SCIP_OKAY;
147 }
148 
149 /** branching execution method for fractional LP solutions */
150 static
151 SCIP_DECL_BRANCHEXECLP(branchExeclpCloud)
152 { /*lint --e{715}*/
153  SCIP_BRANCHRULEDATA* branchruledata;
154 
155  SCIP_VAR** lpcands;
156  SCIP_VAR** lpcandscopy;
157 
158  SCIP_VAR** vars;
159  SCIP_ROW** lprows;
160  SCIP_Real* lpcandsfrac;
161  SCIP_Real* lpcandssol;
162  SCIP_Real* lpcandsfraccopy;
163  SCIP_Real* lpcandssolcopy;
164  SCIP_Real* lpcandsmin;
165  SCIP_Real* lpcandsmax;
166  SCIP_Real* newlpcandsmin;
167  SCIP_Real* newlpcandsmax;
168 
169  SCIP_Real bestdown;
170  SCIP_Real bestup;
171  SCIP_Real bestscore;
172  SCIP_Real provedbound;
173 
174  SCIP_Bool bestdownvalid;
175  SCIP_Bool bestupvalid;
176  SCIP_Bool newpoint;
177  SCIP_Bool lperror;
178 
179  int nlpcands;
180  int npriolpcands;
181  int nvars;
182  int bestcand;
183  int nlprows;
184  int i;
185  int counter;
186  int ncomplete;
187  int ndiscvars;
188 
189  assert(branchrule != NULL);
190  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
191  assert(scip != NULL);
192  assert(result != NULL);
193 
194  if( !SCIPisLPSolBasic(scip) )
195  return SCIP_OKAY;
196 
197  SCIPdebugMsg(scip, "Execlp method of " BRANCHRULE_NAME " branching\n");
198 
199  /* get problem variables and LP row data */
200  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
202  nlprows = SCIPgetNLPRows(scip);
203  lprows = SCIPgetLPRows(scip);
204 
205  /* get branching candidates */
206  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, &lpcandsfrac, &nlpcands, &npriolpcands, NULL) );
207  nlpcands = SCIPgetNLPBranchCands(scip);
208  assert(nlpcands > 0);
209 
210  /* get branching rule data */
211  branchruledata = SCIPbranchruleGetData(branchrule);
212  assert(branchruledata != NULL);
213 
214  /* allocate skipping arrays on first call */
215  if( branchruledata->skipdown == NULL )
216  {
217  assert(branchruledata->skipup == NULL);
218 
219  branchruledata->skipsize = nvars;
220  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipdown, branchruledata->skipsize) );
221  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipup, branchruledata->skipsize) );
222  }
223 
224  /* reset skipping arrays to zero */
225  BMSclearMemoryArray(branchruledata->skipdown, branchruledata->skipsize);
226  BMSclearMemoryArray(branchruledata->skipup, branchruledata->skipsize);
227 
228  /* allocate required data structures */
229  SCIP_CALL( SCIPallocBufferArray(scip, &lpcandsmin, nlpcands) );
230  SCIP_CALL( SCIPallocBufferArray(scip, &lpcandsmax, nlpcands) );
231  SCIP_CALL( SCIPallocBufferArray(scip, &lpcandscopy, nlpcands) );
232  SCIP_CALL( SCIPallocBufferArray(scip, &lpcandsfraccopy, nlpcands) );
233  SCIP_CALL( SCIPallocBufferArray(scip, &lpcandssolcopy, nlpcands) );
234  newlpcandsmin = NULL;
235  newlpcandsmax = NULL;
236  if( branchruledata->useunion && SCIPgetDepth(scip) < branchruledata->maxdepthunion && !branchruledata->onlyF2)
237  {
238  SCIP_CALL( SCIPallocBufferArray(scip, &newlpcandsmin, ndiscvars) );
239  SCIP_CALL( SCIPallocBufferArray(scip, &newlpcandsmax, ndiscvars) );
240  }
241  BMScopyMemoryArray(lpcandsmin, lpcandssol, nlpcands);
242  BMScopyMemoryArray(lpcandsmax, lpcandssol, nlpcands);
243  BMScopyMemoryArray(lpcandssolcopy, lpcandssol, nlpcands);
244  BMScopyMemoryArray(lpcandsfraccopy, lpcandsfrac, nlpcands);
245  BMScopyMemoryArray(lpcandscopy, lpcands, nlpcands);
246 
247  SCIP_CALL( SCIPstartClock(scip, branchruledata->cloudclock) );
248  branchruledata->ntried++;
249 
250  /* start diving to calculate the solution cloud */
252 
253  /* fix variables with nonzero reduced costs to reduce LP to the optimal face */
254  for( i = 0; i < nvars; ++i )
255  {
256  SCIP_Real solval;
257  solval = SCIPgetSolVal(scip, NULL, vars[i]);
258 
259  if( !SCIPisFeasZero(scip, SCIPgetVarRedcost(scip, vars[i])) )
260  {
261  SCIP_CALL( SCIPchgVarLbDive(scip, vars[i], solval) );
262  SCIP_CALL( SCIPchgVarUbDive(scip, vars[i], solval) );
263  }
264  else if( SCIPvarGetType(vars[i]) == SCIP_VARTYPE_INTEGER && !SCIPisIntegral(scip, solval) )
265  {
266  SCIP_CALL( SCIPchgVarLbDive(scip, vars[i], SCIPfloor(scip, solval)) );
267  SCIP_CALL( SCIPchgVarUbDive(scip, vars[i], SCIPceil(scip, solval)) );
268  }
269 
270  SCIP_CALL( SCIPchgVarObjDive(scip, vars[i], 0.0) );
271  }
272 
273  /* fix LP rows with nonzero dual solution to reduce LP to the optimal face */
274  for( i = 0; i < nlprows; ++i )
275  {
276  SCIP_Real dualsol;
277  dualsol = SCIProwGetDualsol(lprows[i]);
278  if( !SCIPisZero(scip, dualsol) )
279  {
280  if( dualsol > 0 && SCIPisFeasEQ(scip, SCIProwGetLhs(lprows[i]), SCIPgetRowActivity(scip,lprows[i])) )
281  {
282  SCIP_CALL( SCIPchgRowRhsDive(scip, lprows[i], SCIProwGetLhs(lprows[i])) );
283  }
284  else if( dualsol < 0 && SCIPisFeasEQ(scip, SCIProwGetRhs(lprows[i]), SCIPgetRowActivity(scip,lprows[i])) )
285  {
286  SCIP_CALL( SCIPchgRowLhsDive(scip, lprows[i], SCIProwGetRhs(lprows[i])) );
287  }
288  }
289  }
290 
291  newpoint = TRUE;
292  counter = 0;
293 
294  if( branchruledata->useunion && !branchruledata->onlyF2 && SCIPgetDepth(scip) < branchruledata->maxdepthunion )
295  {
296  /* update cloud intervals for candidates that have been integral in original LP, but have been fractional in previous cloud points */
297  for( i = 0; i < ndiscvars; ++i)
298  {
299  SCIP_Real solval;
300  solval = SCIPgetSolVal(scip, NULL, vars[i]);
301 
302  assert(newlpcandsmin != NULL);
303  assert(newlpcandsmax != NULL);
304 
305  newlpcandsmin[i] = solval;
306  newlpcandsmax[i] = solval;
307  }
308  }
309 
310  /* loop that generates new cloud point */
311  while( newpoint && branchruledata->usecloud )
312  {
313 #ifdef NDEBUG
314  SCIP_RETCODE retcode;
315 #endif
316 
317  /* apply feasibility pump objective function to fractional variables */
318  for( i = 0; i < nlpcands; ++i )
319  {
320  SCIP_Real frac;
321  frac = SCIPfrac(scip, SCIPgetSolVal(scip, NULL, lpcandscopy[i]));
322 
323  if( !SCIPisZero(scip, frac) && !SCIPisIntegral(scip, lpcandsmin[i]) && !SCIPisIntegral(scip, lpcandsmax[i]) )
324  {
325  if( frac < 0.5 )
326  {
327  SCIP_CALL( SCIPchgVarObjDive(scip, vars[i], 1.0) );
328  }
329  else
330  {
331  SCIP_CALL( SCIPchgVarObjDive(scip, vars[i], -1.0) );
332  }
333  }
334  }
335 
336  /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
337  * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
338  */
339 #ifdef NDEBUG
340  retcode = SCIPsolveDiveLP(scip, -1, &lperror, NULL);
341  if( retcode != SCIP_OKAY )
342  {
343  SCIPwarningMessage(scip, "Error while solving LP in " BRANCHRULE_NAME "; LP solve terminated with code <%d>\n",retcode);
344  }
345 #else
346  SCIP_CALL( SCIPsolveDiveLP(scip, -1, &lperror, NULL) );
347 #endif
348 
349  if( lperror || SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
350  break;
351 
352  /* check if a solution has been found */
353  if( SCIPgetNLPBranchCands(scip) == 0 )
354  {
355  SCIP_Bool success;
356  SCIP_SOL* sol;
357 
358  /* create solution from diving LP */
359  SCIP_CALL( SCIPcreateSol(scip, &sol, NULL) );
360  SCIP_CALL( SCIPlinkLPSol(scip, sol) );
361  SCIPdebugMsg(scip, "cloud branching found primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, sol));
362 
363  /* try to add solution to SCIP */
364  SCIP_CALL( SCIPtrySolFree(scip, &sol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
365 
366  /* check, if solution was feasible and good enough */
367  if( success )
368  {
369  SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
371  *result = SCIP_CUTOFF;
372  goto TERMINATE;
373  }
374  }
375 
376  /* update cloud intervals for candidates that have been fractional in original LP */
377  newpoint = FALSE;
378  for( i = 0; i < nlpcands; ++i)
379  {
380  SCIP_Real solval;
381  solval = SCIPgetSolVal(scip, NULL, lpcandscopy[i]);
382 
383  if( SCIPisFeasIntegral(scip,solval) && !SCIPisFeasIntegral(scip, lpcandsmin[i]) && !SCIPisFeasIntegral(scip, lpcandsmax[i]) )
384  newpoint = TRUE;
385 
386  lpcandsmin[i] = MIN(lpcandsmin[i], solval);
387  lpcandsmax[i] = MAX(lpcandsmax[i], solval);
388  }
389 
390  if( branchruledata->useunion && !branchruledata->onlyF2 && SCIPgetDepth(scip) < branchruledata->maxdepthunion )
391  {
392  /* update cloud intervals for candidates that have been integral in original LP, but have been fractional in previous cloud points */
393  for( i = 0; i < ndiscvars; ++i)
394  {
395  SCIP_Real solval;
396  solval = SCIPgetSolVal(scip, NULL, vars[i]);
397 
398  assert(newlpcandsmin != NULL);
399  assert(newlpcandsmax != NULL);
400 
401  newlpcandsmin[i] = MIN(newlpcandsmin[i], solval);
402  newlpcandsmax[i] = MAX(newlpcandsmax[i], solval);
403  }
404  }
405 
406  if( newpoint )
407  counter++;
408 
409  if( branchruledata->maxpoints != -1 && counter >= branchruledata->maxpoints )
410  break;
411  }
412 
413  SCIPdebugMsg(scip, "considered %d additional points in the cloud\n",counter);
414 
415 
416  /* terminate the diving */
418 
419  SCIP_CALL( SCIPstopClock(scip, branchruledata->cloudclock) );
420  ncomplete = nlpcands;
421 
422  if( counter > 0 )
423  {
424  branchruledata->ncloudpoints += (counter+1);
425  branchruledata->nuseful++;
426 
427  counter = 0;
428 
429  /* sort all variables for which both bounds are fractional to the front */
430  for( i = 0; i < nlpcands; ++i)
431  {
432  if( !SCIPisFeasIntegral(scip, lpcandsmin[i]) && !SCIPisFeasIntegral(scip, lpcandsmax[i]) )
433  {
434  assert(counter <= i);
435  lpcandscopy[counter] = lpcandscopy[i];
436  lpcandssolcopy[counter] = lpcandssolcopy[i];
437  lpcandsfraccopy[counter] = lpcandsfraccopy[i];
438  counter++;
439  }
440  }
441 
442  /* should only be in that if condition when at least one bound could be made integral */
443  assert(nlpcands - counter > 0);
444 
445  ncomplete = counter;
446 
447  /* filter all variables for which exactly one interval bound is fractional */
448  for( i = 0; i < nlpcands && !branchruledata->onlyF2; ++i)
449  {
450  if( SCIPisFeasIntegral(scip, lpcandsmin[i]) != SCIPisFeasIntegral(scip, lpcandsmax[i]) )
451  {
452  assert(counter < nlpcands);
453  lpcandscopy[counter] = lpcandscopy[i];
454  lpcandssolcopy[counter] = lpcandssolcopy[i];
455  lpcandsfraccopy[counter] = lpcandsfraccopy[i];
456 
457  if( SCIPisFeasIntegral(scip, lpcandsmin[i]) )
458  branchruledata->skipdown[counter] = TRUE;
459  if( SCIPisFeasIntegral(scip, lpcandsmax[i]) )
460  branchruledata->skipup[counter] = TRUE;
461  assert(branchruledata->skipdown[counter] != branchruledata->skipup[counter]);
462 
463  counter++;
464  }
465  }
466 
467  SCIPdebugMsg(scip, "can fully skip %d/%d strong branching candidates\n", nlpcands - counter, nlpcands);
468  SCIPdebugMsg(scip, "can half skip %d/%d strong branching candidates\n", counter - ncomplete, nlpcands);
469  }
470  else
471  counter = nlpcands;
472 
473  /* if cloud sampling was not successful enough, disable it */
474  if( branchruledata->usecloud &&
475  branchruledata->ntried > 100 &&
476  (SCIP_Real)branchruledata->nuseful / branchruledata->ntried < branchruledata->minsuccessrate )
477  {
478  SCIPdebugMsg(scip, "Disabling cloud branching (not effective)\n");
479  branchruledata->usecloud = FALSE;
480  }
481 
482  if( branchruledata->onlyF2 )
483  counter = MAX(counter,1);
484 
485  /* the second counter should maybe be replaced at some point */
486  SCIP_CALL( SCIPselectVarStrongBranching(scip, lpcandscopy, lpcandssolcopy, lpcandsfraccopy, branchruledata->skipdown,
487  branchruledata->skipup, counter, counter, ncomplete, &branchruledata->lastcand, 0, FALSE, FALSE,
488  &bestcand, &bestdown, &bestup, &bestscore, &bestdownvalid, &bestupvalid, &provedbound, result) );
489 
490  if( branchruledata->lastcand <= ncomplete )
491  {
492  SCIPdebugMsg(scip, "saved %d of %d LPs\n", 2*(nlpcands - ncomplete), 2*nlpcands);
493  branchruledata->nsavedlps += 2*(nlpcands - ncomplete);
494  }
495  else
496  {
497  SCIPdebugMsg(scip, "saved %d of %d LPs\n", 2*(nlpcands - counter)+counter - ncomplete, 2*nlpcands);
498  branchruledata->nsavedlps += 2*(nlpcands - counter)+counter - ncomplete;
499  }
500 
501  /* perform the branching */
502  if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM && *result != SCIP_CONSADDED && counter > 0 )
503  {
504  SCIP_NODE* downchild;
505  SCIP_NODE* upchild;
506  SCIP_VAR* var;
507  SCIP_Bool allcolsinlp;
508  SCIP_Bool exactsolve;
509  SCIP_Bool newselected;
510 
511  assert(*result == SCIP_DIDNOTRUN);
512  assert(0 <= bestcand && bestcand < nlpcands);
513  assert(SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip)));
514 
515  var = lpcandscopy[bestcand];
516  newselected = FALSE;
517 
518  /* if there are new candidates variables, also try them */
519  if( branchruledata->useunion && !branchruledata->onlyF2 && SCIPgetDepth(scip) < branchruledata->maxdepthunion && branchruledata->lastcand > ncomplete )
520  {
521  SCIP_VAR** newlpcands;
522 
523  counter = 0;
524  /* reset skipping arrays to zero */
525  BMSclearMemoryArray(branchruledata->skipdown, branchruledata->skipsize);
526  BMSclearMemoryArray(branchruledata->skipup, branchruledata->skipsize);
527 
528  SCIP_CALL( SCIPallocBufferArray(scip, &newlpcands, ndiscvars) );
529 
530  /* get new LP candidates with one fractional bound */
531  for( i = 0; i < ndiscvars; ++i)
532  {
533  if( !SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, NULL, vars[i])) )
534  continue;
535 
536  assert(newlpcandsmin != NULL);
537  assert(newlpcandsmax != NULL);
538 
539  if( SCIPisFeasIntegral(scip, newlpcandsmin[i]) != SCIPisFeasIntegral(scip, newlpcandsmax[i]) )
540  {
541  newlpcands[counter] = vars[i];
542 
543  if( SCIPisFeasIntegral(scip, newlpcandsmin[i]) )
544  branchruledata->skipdown[counter] = TRUE;
545  if( SCIPisFeasIntegral(scip, newlpcandsmax[i]) )
546  branchruledata->skipup[counter] = TRUE;
547  assert(branchruledata->skipdown[counter] != branchruledata->skipup[counter]);
548 
549  counter++;
550  }
551  }
552 
553  /* when there are new candidates, also try these */
554  if( counter > 0 )
555  {
556  SCIP_Real newdown;
557  SCIP_Real newup;
558  SCIP_Real newscore;
559  int newcand;
560  SCIP_Bool newdownvalid;
561  SCIP_Bool newupvalid;
562  SCIP_Real newbound;
563 
564  branchruledata->ntriedunions++;
565  newscore = -SCIPinfinity(scip);
566  SCIP_CALL( SCIPselectVarPseudoStrongBranching(scip, newlpcands, branchruledata->skipdown, branchruledata->skipup, counter, counter,
567  &newcand, &newdown, &newup, &newscore, &newdownvalid, &newupvalid, &newbound, result) );
568 
569  if( *result == SCIP_CUTOFF || *result == SCIP_REDUCEDDOM || *result == SCIP_CONSADDED )
570  {
571  SCIPfreeBufferArray(scip, &newlpcands);
572  goto TERMINATE;
573  }
574 
575  if( newscore > bestscore )
576  {
577  bestcand = newcand;
578  var = newlpcands[newcand];
579  bestdown = newdown;
580  bestup = newup;
581  bestdownvalid = newdownvalid;
582  bestupvalid = newupvalid;
583  bestscore = newscore;
584  newselected = TRUE;
585  branchruledata->nusefulunions++;
586  }
587  }
588  /* free temporary array for new union candidates */
589  SCIPfreeBufferArray(scip, &newlpcands);
590  }
591 
592  /* perform the branching */
593  if( !newselected )
594  {
595  SCIPdebugMsg(scip, " -> %d candidates, selected candidate %d: variable <%s> (solval=%g, down=%g, up=%g, score=%g)\n",
596  counter, bestcand, SCIPvarGetName(var), lpcandssolcopy[bestcand], bestdown, bestup, bestscore);
597  }
598  else
599  {
600  SCIPdebugMsg(scip, " -> selected from %d new candidates, candidate %d: variable <%s> (down=%g, up=%g, score=%g)\n",
601  counter, bestcand, SCIPvarGetName(var), bestdown, bestup, bestscore);
602  }
603 
604  assert(!SCIPisFeasIntegral(scip, SCIPvarGetSol(lpcands[bestcand], TRUE)));
605 
606  SCIP_CALL( SCIPbranchVar(scip, var, &downchild, NULL, &upchild) );
607  assert(downchild != NULL);
608  assert(upchild != NULL);
609 
610  /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
611  * for cutting off sub problems and improving lower bounds of children
612  */
613  exactsolve = SCIPisExactSolve(scip);
614 
615  /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
616  allcolsinlp = SCIPallColsInLP(scip);
617 
618  /* update the lower bounds in the children */
619  if( allcolsinlp && !exactsolve )
620  {
621  SCIP_CALL( SCIPupdateNodeLowerbound(scip, downchild, bestdownvalid ? MAX(bestdown, provedbound) : provedbound) );
622  SCIP_CALL( SCIPupdateNodeLowerbound(scip, upchild, bestupvalid ? MAX(bestup, provedbound) : provedbound) );
623  }
624  SCIPdebugMsg(scip, " -> down child's lowerbound: %g\n", SCIPnodeGetLowerbound(downchild));
625  SCIPdebugMsg(scip, " -> up child's lowerbound: %g\n", SCIPnodeGetLowerbound(upchild));
626 
627  *result = SCIP_BRANCHED;
628  }
629 
630  TERMINATE:
631  if( branchruledata->useunion && !branchruledata->onlyF2 && SCIPgetDepth(scip) < branchruledata->maxdepthunion )
632  {
633  SCIPfreeBufferArray(scip, &newlpcandsmax);
634  SCIPfreeBufferArray(scip, &newlpcandsmin);
635  }
636  SCIPfreeBufferArray(scip, &lpcandscopy);
637  SCIPfreeBufferArray(scip, &lpcandssolcopy);
638  SCIPfreeBufferArray(scip, &lpcandsfraccopy);
639  SCIPfreeBufferArray(scip, &lpcandsmax);
640  SCIPfreeBufferArray(scip, &lpcandsmin);
641 
642  /* if union usage was not successful enough, disable it */
643  if( branchruledata->useunion &&
644  branchruledata->ntriedunions > 10 &&
645  (SCIP_Real)branchruledata->nusefulunions / branchruledata->ntriedunions < branchruledata->minsuccessunion )
646  {
647  SCIPdebugMsg(scip, "Disabling union usage (not effective)\n");
648  branchruledata->useunion = FALSE;
649  }
650 
651  return SCIP_OKAY;
652 }
653 
654 /*
655  * branching rule specific interface methods
656  */
657 
658 /** creates the cloud branching rule and includes it in SCIP */
660  SCIP* scip /**< SCIP data structure */
661  )
662 {
663  SCIP_BRANCHRULEDATA* branchruledata;
664  SCIP_BRANCHRULE* branchrule;
665 
666  /* create cloud branching rule data */
667  SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
668  branchruledata->lastcand = 0;
669  branchruledata->skipsize = 0;
670  branchruledata->skipup = NULL;
671  branchruledata->skipdown = NULL;
672  SCIP_CALL( SCIPcreateClock(scip, &(branchruledata->cloudclock)) );
673 
674  /* include branching rule */
675  branchrule = NULL;
677  BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
678  assert(branchrule != NULL);
679 
680  /* set non-fundamental callbacks via setter functions */
681  SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeCloud) );
682  SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitCloud) );
683  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpCloud) );
684 
685  /* add cloud branching rule parameters */
687  "branching/" BRANCHRULE_NAME "/usecloud",
688  "should a cloud of points be used?",
689  &branchruledata->usecloud, FALSE, DEFAULT_USECLOUD, NULL, NULL) );
691  "branching/" BRANCHRULE_NAME "/onlyF2",
692  "should only F2 be used?",
693  &branchruledata->onlyF2, FALSE, DEFAULT_ONLYF2, NULL, NULL) );
695  "branching/" BRANCHRULE_NAME "/useunion",
696  "should the union of candidates be used?",
697  &branchruledata->useunion, FALSE, DEFAULT_USEUNION, NULL, NULL) );
699  "branching/" BRANCHRULE_NAME "/maxpoints",
700  "maximum number of points for the cloud (-1 means no limit)",
701  &branchruledata->maxpoints, FALSE, DEFAULT_MAXPOINTS, -1, INT_MAX, NULL, NULL) );
703  "branching/" BRANCHRULE_NAME "/minsuccessrate",
704  "minimum success rate for the cloud",
705  &branchruledata->minsuccessrate, FALSE, DEFAULT_MINSUCCESSRATE, 0.0, 1.0, NULL, NULL) );
707  "branching/" BRANCHRULE_NAME "/minsuccessunion",
708  "minimum success rate for the union",
709  &branchruledata->minsuccessunion, FALSE, DEFAULT_MINSUCCESSUNION, 0.0, 1.0, NULL, NULL) );
711  "branching/" BRANCHRULE_NAME "/maxdepthunion",
712  "maximum depth for the union",
713  &branchruledata->maxdepthunion, FALSE, DEFAULT_MAXDEPTHUNION, 0, 65000, NULL, NULL) );
714 
715  return SCIP_OKAY;
716 }
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip.c:36995
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
Definition: scip.c:29669
int SCIPgetNIntVars(SCIP *scip)
Definition: scip.c:11896
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:47357
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38570
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1810
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22587
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47292
#define DEFAULT_USECLOUD
Definition: branch_cloud.c:44
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:43447
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7360
SCIP_Real SCIPgetVarRedcost(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:19375
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:43
SCIP_RETCODE SCIPstopClock(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip.c:46109
SCIP_Real SCIPvarGetSol(SCIP_VAR *var, SCIP_Bool getlpval)
Definition: var.c:12665
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip.c:9139
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11680
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:16481
#define FALSE
Definition: def.h:64
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_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47022
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define DEFAULT_MAXPOINTS
Definition: branch_cloud.c:46
#define SCIPstatisticMessage
Definition: pub_message.h:104
SCIP_RETCODE SCIPchgVarLbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:35439
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
static SCIP_DECL_BRANCHINIT(branchInitCloud)
Definition: branch_cloud.c:127
SCIP_RETCODE SCIPincludeBranchruleBasic(SCIP *scip, SCIP_BRANCHRULE **branchruleptr, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_BRANCHRULEDATA *branchruledata)
Definition: scip.c:9086
SCIP_RETCODE SCIPfreeClock(SCIP *scip, SCIP_CLOCK **clck)
Definition: scip.c:46058
#define DEFAULT_MAXDEPTHUNION
Definition: branch_cloud.c:49
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
#define BRANCHRULE_PRIORITY
Definition: branch_cloud.c:40
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip.c:37028
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip.c:1267
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
Definition: lp.c:16501
#define SCIPdebugMsg
Definition: scip.h:455
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4265
#define BRANCHRULE_NAME
Definition: branch_cloud.c:38
#define DEFAULT_USEUNION
Definition: branch_cloud.c:45
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip.c:9221
static SCIP_DECL_BRANCHEXECLP(branchExeclpCloud)
Definition: branch_cloud.c:151
#define DEFAULT_MINSUCCESSUNION
Definition: branch_cloud.c:48
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip.c:29731
SCIP_RETCODE SCIPchgRowLhsDive(SCIP *scip, SCIP_ROW *row, SCIP_Real newlhs)
Definition: scip.c:35542
cloud branching rule
SCIP_RETCODE SCIPcreateClock(SCIP *scip, SCIP_CLOCK **clck)
Definition: scip.c:46007
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip.c:37604
SCIP_RETCODE SCIPsolveDiveLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip.c:35698
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46970
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
int SCIPgetNLPRows(SCIP *scip)
Definition: scip.c:29690
#define SCIP_CALL(x)
Definition: def.h:350
#define BRANCHRULE_MAXBOUNDDIST
Definition: branch_cloud.c:42
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:16491
SCIP_RETCODE SCIPincludeBranchruleCloud(SCIP *scip)
Definition: branch_cloud.c:659
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
full strong LP branching rule
#define BRANCHRULE_MAXDEPTH
Definition: branch_cloud.c:41
#define DEFAULT_MINSUCCESSRATE
Definition: branch_cloud.c:47
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:29287
SCIP_Real SCIPgetClockTime(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip.c:46241
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:43039
SCIP_RETCODE SCIPupdateNodeLowerbound(SCIP *scip, SCIP_NODE *node, SCIP_Real newbound)
Definition: scip.c:13574
SCIP_RETCODE SCIPchgVarUbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:35471
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1820
#define MAX(x, y)
Definition: tclique_def.h:75
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip.c:40788
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:116
#define DEFAULT_ONLYF2
Definition: branch_cloud.c:50
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38988
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11851
static SCIP_DECL_BRANCHFREE(branchFreeCloud)
Definition: branch_cloud.c:85
all variables full strong LP branching rule
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:47106
SCIP_RETCODE SCIPchgVarObjDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip.c:35398
SCIP_RETCODE SCIPresetClock(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip.c:46075
#define SCIPstatistic(x)
Definition: pub_message.h:101
#define SCIP_Real
Definition: def.h:149
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1932
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: scip.c:9155
SCIP_Bool SCIPallColsInLP(SCIP *scip)
Definition: scip.c:29713
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
Definition: scip.c:47179
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16827
SCIP_RETCODE SCIPstartDive(SCIP *scip)
Definition: scip.c:35262
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:47070
#define BRANCHRULE_DESC
Definition: branch_cloud.c:39
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip.h:22605
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:47393
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:112
SCIP_RETCODE SCIPendDive(SCIP *scip)
Definition: scip.c:35311
SCIP_RETCODE SCIPselectVarPseudoStrongBranching(SCIP *scip, SCIP_VAR **pseudocands, SCIP_Bool *skipdown, SCIP_Bool *skipup, int npseudocands, int npriopseudocands, int *bestpseudocand, SCIP_Real *bestdown, SCIP_Real *bestup, SCIP_Real *bestscore, SCIP_Bool *bestdownvalid, SCIP_Bool *bestupvalid, SCIP_Real *provedbound, SCIP_RESULT *result)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
Definition: scip.c:47155
SCIP_RETCODE SCIPchgRowRhsDive(SCIP *scip, SCIP_ROW *row, SCIP_Real newrhs)
Definition: scip.c:35575
SCIP_RETCODE SCIPstartClock(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip.c:46092
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38905
SCIP_Bool SCIPisExactSolve(SCIP *scip)
Definition: scip.c:1032
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4321
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:47143
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4239
SCIP_Real SCIPgetRowActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:31065
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37872