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