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