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