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-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
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
42#include "scip/branch_cloud.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"
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 */
84struct 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) */
111static
112SCIP_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) */
153static
154SCIP_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 */
177static
178SCIP_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) );
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;
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 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)
all variables full strong LP branching rule
#define BRANCHRULE_DESC
Definition: branch_cloud.c:66
static SCIP_DECL_BRANCHINIT(branchInitCloud)
Definition: branch_cloud.c:154
#define BRANCHRULE_PRIORITY
Definition: branch_cloud.c:67
#define DEFAULT_MAXPOINTS
Definition: branch_cloud.c:73
#define DEFAULT_MINSUCCESSUNION
Definition: branch_cloud.c:75
#define DEFAULT_USEUNION
Definition: branch_cloud.c:72
#define BRANCHRULE_NAME
Definition: branch_cloud.c:65
#define DEFAULT_MAXDEPTHUNION
Definition: branch_cloud.c:76
static SCIP_DECL_BRANCHEXECLP(branchExeclpCloud)
Definition: branch_cloud.c:178
#define DEFAULT_ONLYF2
Definition: branch_cloud.c:77
#define DEFAULT_MINSUCCESSRATE
Definition: branch_cloud.c:74
static SCIP_DECL_BRANCHFREE(branchFreeCloud)
Definition: branch_cloud.c:112
#define DEFAULT_USECLOUD
Definition: branch_cloud.c:71
#define BRANCHRULE_MAXDEPTH
Definition: branch_cloud.c:68
#define BRANCHRULE_MAXBOUNDDIST
Definition: branch_cloud.c:69
cloud branching rule
full strong LP branching rule
#define NULL
Definition: def.h:267
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_RETCODE SCIPselectVarStrongBranching(SCIP *scip, SCIP_VAR **lpcands, SCIP_Real *lpcandssol, SCIP_Real *lpcandsfrac, SCIP_Bool *skipdown, SCIP_Bool *skipup, int nlpcands, int npriolpcands, int ncomplete, int *start, int maxproprounds, SCIP_Bool probingbounds, SCIP_Bool forcestrongbranch, int *bestcand, SCIP_Real *bestdown, SCIP_Real *bestup, SCIP_Real *bestscore, SCIP_Bool *bestdownvalid, SCIP_Bool *bestupvalid, SCIP_Real *provedbound, SCIP_RESULT *result)
SCIP_RETCODE SCIPincludeBranchruleCloud(SCIP *scip)
Definition: branch_cloud.c:685
SCIP_Bool SCIPisExactSolve(SCIP *scip)
Definition: scip_general.c:611
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2082
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1866
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
SCIP_RETCODE SCIPupdateNodeLowerbound(SCIP *scip, SCIP_NODE *node, SCIP_Real newbound)
Definition: scip_prob.c:3757
#define SCIPdebugMsg
Definition: scip_message.h:78
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
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
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_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_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:249
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
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1971
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1849
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:169
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: scip_branch.c:185
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1859
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_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1050
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:428
SCIP_RETCODE SCIPchgVarLbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_lp.c:2419
SCIP_RETCODE SCIPchgVarUbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_lp.c:2451
SCIP_RETCODE SCIPchgRowLhsDive(SCIP *scip, SCIP_ROW *row, SCIP_Real newlhs)
Definition: scip_lp.c:2522
SCIP_RETCODE SCIPchgRowRhsDive(SCIP *scip, SCIP_ROW *row, SCIP_Real newrhs)
Definition: scip_lp.c:2555
SCIP_RETCODE SCIPstartDive(SCIP *scip)
Definition: scip_lp.c:2242
SCIP_RETCODE SCIPchgVarObjDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip_lp.c:2378
SCIP_RETCODE SCIPsolveDiveLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_lp.c:2678
SCIP_RETCODE SCIPendDive(SCIP *scip)
Definition: scip_lp.c:2291
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
Definition: scip_lp.c:605
int SCIPgetNLPRows(SCIP *scip)
Definition: scip_lp.c:626
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
SCIP_Bool SCIPallColsInLP(SCIP *scip)
Definition: scip_lp.c:649
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip_lp.c:667
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7513
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17292
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17302
SCIP_Real SCIPgetRowActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:2104
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
Definition: lp.c:17312
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:184
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:3050
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:882
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1300
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_RETCODE SCIPcreateClock(SCIP *scip, SCIP_CLOCK **clck)
Definition: scip_timing.c:76
SCIP_RETCODE SCIPresetClock(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip_timing.c:144
SCIP_RETCODE SCIPstopClock(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip_timing.c:178
SCIP_RETCODE SCIPfreeClock(SCIP *scip, SCIP_CLOCK **clck)
Definition: scip_timing.c:127
SCIP_Real SCIPgetClockTime(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip_timing.c:319
SCIP_RETCODE SCIPstartClock(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip_timing.c:161
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
SCIP_Real SCIPvarGetSol(SCIP_VAR *var, SCIP_Bool getlpval)
Definition: var.c:13257
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_Real SCIPgetVarRedcost(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1864
memory allocation routines
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:134
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
public methods for branching rules
public methods for LP management
public methods for message output
#define SCIPstatisticMessage
Definition: pub_message.h:123
#define SCIPstatistic(x)
Definition: pub_message.h:120
public methods for branch and bound tree
public methods for problem variables
public methods for branching rule plugins and branching
general public methods
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for solutions
public methods for querying solving statistics
public methods for timing
public methods for the branch-and-bound tree
public methods for SCIP variables
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:57
@ SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:43
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_REDUCEDDOM
Definition: type_result.h:51
@ SCIP_CONSADDED
Definition: type_result.h:52
@ SCIP_BRANCHED
Definition: type_result.h:54
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_VARTYPE_INTEGER
Definition: type_var.h:63