Scippy

SCIP

Solving Constraint Integer Programs

branch_pscost.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_pscost.c
26 * @ingroup DEFPLUGINS_BRANCH
27 * @brief pseudo costs branching rule
28 * @author Tobias Achterberg
29 * @author Stefan Vigerske
30 */
31
32/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33
35#include "scip/branch_pscost.h"
36#include "scip/pub_branch.h"
37#include "scip/pub_message.h"
38#include "scip/pub_misc.h"
39#include "scip/pub_misc_sort.h"
40#include "scip/pub_tree.h"
41#include "scip/pub_var.h"
42#include "scip/scip_branch.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"
48#include "scip/scip_sol.h"
49#include "scip/scip_tree.h"
50#include "scip/scip_var.h"
51#include <string.h>
52
53#define BRANCHRULE_NAME "pscost"
54#define BRANCHRULE_DESC "branching on pseudo cost values"
55#define BRANCHRULE_PRIORITY 2000
56#define BRANCHRULE_MAXDEPTH -1
57#define BRANCHRULE_MAXBOUNDDIST 1.0
58
59#define BRANCHRULE_STRATEGIES "dsuv" /**< possible pseudo cost multiplication strategies for branching on external candidates */
60#define BRANCHRULE_STRATEGY_DEFAULT 'u' /**< default pseudo cost multiplication strategy */
61#define BRANCHRULE_SCOREMINWEIGHT_DEFAULT 0.8 /**< default weight for minimum of scores of a branching candidate */
62#define BRANCHRULE_SCOREMAXWEIGHT_DEFAULT 1.3 /**< default weight for maximum of scores of a branching candidate */
63#define BRANCHRULE_SCORESUMWEIGHT_DEFAULT 0.1 /**< default weight for sum of scores of a branching candidate */
64#define BRANCHRULE_NCHILDREN_DEFAULT 2 /**< default number of children in n-ary branching */
65#define BRANCHRULE_NARYMAXDEPTH_DEFAULT -1 /**< default maximal depth where to do n-ary branching */
66#define BRANCHRULE_NARYMINWIDTH_DEFAULT 0.001 /**< default minimal domain width in children when doing n-ary branching */
67#define BRANCHRULE_NARYWIDTHFAC_DEFAULT 2.0 /**< default factor of domain width in n-ary branching */
68#define BRANCHRULE_RANDSEED_DEFAULT 47 /**< initial random seed */
69
70
71#define WEIGHTEDSCORING(data, min, max, sum) \
72 ((data)->scoreminweight * (min) + (data)->scoremaxweight * (max) + (data)->scoresumweight * (sum))
73
74/** branching rule data */
75struct SCIP_BranchruleData
76{
77 SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
78
79 char strategy; /**< strategy for computing score of external candidates */
80 SCIP_Real scoreminweight; /**< weight for minimum of scores of a branching candidate */
81 SCIP_Real scoremaxweight; /**< weight for maximum of scores of a branching candidate */
82 SCIP_Real scoresumweight; /**< weight for sum of scores of a branching candidate */
83
84 char updatestrategy; /**< strategy used to update pseudo costs of continuous variables */
85
86 int nchildren; /**< targeted number of children in n-ary branching */
87 int narymaxdepth; /**< maximal depth where to do n-ary branching, -1 to turn off */
88 SCIP_Real naryminwidth; /**< minimal domain width in children when doing n-ary branching, relative to global bounds */
89 SCIP_Real narywidthfactor; /**< factor of domain width in n-ary branching */
90};
91
92/*
93 * Local methods
94 */
95
96/** checks if a given branching candidate is better than a previous one and updates the best branching candidate accordingly */
97static
99 SCIP* scip, /**< SCIP data structure */
100 SCIP_BRANCHRULEDATA* branchruledata, /**< branching rule data */
101 SCIP_VAR** bestvar, /**< best branching candidate */
102 SCIP_Real* bestbrpoint, /**< branching point for best branching candidate */
103 SCIP_Real* bestscore, /**< score of best branching candidate */
104 SCIP_Real* bestrndscore, /**< random score of the best branching candidate */
105 SCIP_VAR* cand, /**< branching candidate to consider */
106 SCIP_Real candscoremin, /**< minimal score of branching candidate */
107 SCIP_Real candscoremax, /**< maximal score of branching candidate */
108 SCIP_Real candscoresum, /**< sum of scores of branching candidate */
109 SCIP_Real candrndscore, /**< random score of branching candidate */
110 SCIP_Real candsol /**< proposed branching point of branching candidate */
111 )
112{
113 SCIP_Real candbrpoint;
114 SCIP_Real branchscore;
115
116 SCIP_Real deltaminus;
117 SCIP_Real deltaplus;
118
119 SCIP_Real pscostdown;
120 SCIP_Real pscostup;
121
122 char strategy;
123
124 assert(scip != NULL);
125 assert(branchruledata != NULL);
126 assert(bestvar != NULL);
127 assert(bestbrpoint != NULL);
128 assert(bestscore != NULL);
129 assert(cand != NULL);
130
131 /* a branching variable candidate should either be an active problem variable or a multi-aggregated variable */
132 assert(SCIPvarIsActive(SCIPvarGetProbvar(cand)) ||
134
136 {
137 /* for a multi-aggregated variable, we call updateBestCandidate function recursively with all variables in the multi-aggregation */
138 SCIP_VAR** multvars;
139 int nmultvars;
140 int i;
141 SCIP_Bool success;
142 SCIP_Real multvarlb;
143 SCIP_Real multvarub;
144
145 cand = SCIPvarGetProbvar(cand);
146 multvars = SCIPvarGetMultaggrVars(cand);
147 nmultvars = SCIPvarGetMultaggrNVars(cand);
148
149 /* if we have a candidate branching point, then first register only aggregation variables
150 * for which we can compute a corresponding branching point too (see also comments below)
151 * if this fails, then register all (unfixed) aggregation variables, thereby forgetting about candsol
152 */
153 success = FALSE;
154 if( candsol != SCIP_INVALID ) /*lint !e777*/
155 {
156 SCIP_Real* multscalars;
157 SCIP_Real minact;
158 SCIP_Real maxact;
159 SCIP_Real aggrvarsol;
160 SCIP_Real aggrvarsol1;
161 SCIP_Real aggrvarsol2;
162
163 multscalars = SCIPvarGetMultaggrScalars(cand);
164
165 /* for computing the branching point, we need the current bounds of the multi-aggregated variable */
166 minact = SCIPcomputeVarLbLocal(scip, cand);
167 maxact = SCIPcomputeVarUbLocal(scip, cand);
168
169 for( i = 0; i < nmultvars; ++i )
170 {
171 /* skip fixed variables */
172 multvarlb = SCIPcomputeVarLbLocal(scip, multvars[i]);
173 multvarub = SCIPcomputeVarUbLocal(scip, multvars[i]);
174 if( SCIPisEQ(scip, multvarlb, multvarub) )
175 continue;
176
177 assert(multscalars != NULL);
178 assert(multscalars[i] != 0.0);
179
180 /* we cannot ensure that both the upper bound in the left node and the lower bound in the right node
181 * will be candsol by a clever choice for the branching point of multvars[i],
182 * but we can try to ensure that at least one of them will be at candsol
183 */
184 if( multscalars[i] > 0.0 )
185 {
186 /* cand >= candsol
187 * if multvars[i] >= (candsol - (maxact - multscalars[i] * ub(multvars[i]))) / multscalars[i]
188 * = (candsol - maxact) / multscalars[i] + ub(multvars[i])
189 */
190 aggrvarsol1 = (candsol - maxact) / multscalars[i] + multvarub;
191
192 /* cand <= candsol
193 * if multvars[i] <= (candsol - (minact - multscalar[i] * lb(multvars[i]))) / multscalars[i]
194 * = (candsol - minact) / multscalars[i] + lb(multvars[i])
195 */
196 aggrvarsol2 = (candsol - minact) / multscalars[i] + multvarlb;
197 }
198 else
199 {
200 /* cand >= candsol
201 * if multvars[i] <= (candsol - (maxact - multscalars[i] * lb(multvars[i]))) / multscalars[i]
202 * = (candsol - maxact) / multscalars[i] + lb(multvars[i])
203 */
204 aggrvarsol2 = (candsol - maxact) / multscalars[i] + multvarlb;
205
206 /* cand <= candsol
207 * if multvars[i] >= (candsol - (minact - multscalar[i] * ub(multvars[i]))) / multscalars[i]
208 * = (candsol - minact) / multscalars[i] + ub(multvars[i])
209 */
210 aggrvarsol1 = (candsol - minact) / multscalars[i] + multvarub;
211 }
212
213 /* by the above choice, aggrvarsol1 <= ub(multvars[i]) and aggrvarsol2 >= lb(multvars[i])
214 * if aggrvarsol1 <= lb(multvars[i]) or aggrvarsol2 >= ub(multvars[i]), then choose the other one
215 * if both are out of bounds, then give up
216 * if both are inside bounds, then choose the one closer to 0.0 (someone has better idea???)
217 */
218 if( SCIPisFeasLE(scip, aggrvarsol1, multvarlb) )
219 {
220 if( SCIPisFeasGE(scip, aggrvarsol2, multvarub) )
221 continue;
222 else
223 aggrvarsol = aggrvarsol2;
224 }
225 else
226 {
227 if( SCIPisFeasGE(scip, aggrvarsol2, multvarub) )
228 aggrvarsol = aggrvarsol1;
229 else
230 aggrvarsol = REALABS(aggrvarsol1) < REALABS(aggrvarsol2) ? aggrvarsol1 : aggrvarsol2;
231 }
232 success = TRUE;
233
234 SCIP_CALL( updateBestCandidate(scip, branchruledata, bestvar, bestbrpoint, bestscore, bestrndscore,
235 multvars[i], candscoremin, candscoremax, candscoresum, candrndscore, aggrvarsol) );
236 }
237 }
238
239 if( !success )
240 for( i = 0; i < nmultvars; ++i )
241 {
242 /* skip fixed variables */
243 multvarlb = SCIPcomputeVarLbLocal(scip, multvars[i]);
244 multvarub = SCIPcomputeVarUbLocal(scip, multvars[i]);
245 if( SCIPisEQ(scip, multvarlb, multvarub) )
246 continue;
247
248 SCIP_CALL( updateBestCandidate(scip, branchruledata, bestvar, bestbrpoint, bestscore, bestrndscore,
249 multvars[i], candscoremin, candscoremax, candscoresum, candrndscore, SCIP_INVALID) );
250 }
251
252 assert(*bestvar != NULL); /* if all variables were fixed, something is strange */
253
254 return SCIP_OKAY;
255 }
256
257 /* select branching point for this variable */
258 candbrpoint = SCIPgetBranchingPoint(scip, cand, candsol);
259 assert(candbrpoint >= SCIPvarGetLbLocal(cand));
260 assert(candbrpoint <= SCIPvarGetUbLocal(cand));
261
262 /* we cannot branch on a huge value for a discrete variable, because we simply cannot enumerate such huge integer values in floating point
263 * arithmetics
264 */
265 if( SCIPvarGetType(cand) != SCIP_VARTYPE_CONTINUOUS && (SCIPisHugeValue(scip, candbrpoint) || SCIPisHugeValue(scip, -candbrpoint)) )
266 return SCIP_OKAY;
267
268 assert(SCIPvarGetType(cand) == SCIP_VARTYPE_CONTINUOUS || !SCIPisIntegral(scip, candbrpoint));
269
271 strategy = (branchruledata->strategy == 'u' ? branchruledata->updatestrategy : branchruledata->strategy);
272 else
273 strategy = (branchruledata->strategy == 'u' ? 'l' : branchruledata->strategy);
274
275 switch( strategy )
276 {
277 case 'l':
278 if( SCIPisInfinity(scip, SCIPgetSolVal(scip, NULL, cand)) || SCIPgetSolVal(scip, NULL, cand) <= SCIPadjustedVarUb(scip, cand, candbrpoint) )
279 deltaminus = 0.0;
280 else
281 deltaminus = SCIPgetSolVal(scip, NULL, cand) - SCIPadjustedVarUb(scip, cand, candbrpoint);
282 if( SCIPisInfinity(scip, -SCIPgetSolVal(scip, NULL, cand)) || SCIPgetSolVal(scip, NULL, cand) >= SCIPadjustedVarLb(scip, cand, candbrpoint) )
283 deltaplus = 0.0;
284 else
285 deltaplus = SCIPadjustedVarLb(scip, cand, candbrpoint) - SCIPgetSolVal(scip, NULL, cand);
286 break;
287
288 case 'd':
290 deltaminus = SCIPisInfinity(scip, candscoremax) ? SCIPinfinity(scip) : WEIGHTEDSCORING(branchruledata, candscoremin, candscoremax, candscoresum);
291 else
292 deltaminus = SCIPadjustedVarUb(scip, cand, candbrpoint) - SCIPvarGetLbLocal(cand);
293
295 deltaplus = SCIPisInfinity(scip, candscoremax) ? SCIPinfinity(scip) : WEIGHTEDSCORING(branchruledata, candscoremin, candscoremax, candscoresum);
296 else
297 deltaplus = SCIPvarGetUbLocal(cand) - SCIPadjustedVarLb(scip, cand, candbrpoint);
298 break;
299
300 case 's':
302 deltaplus = SCIPisInfinity(scip, candscoremax) ? SCIPinfinity(scip) : WEIGHTEDSCORING(branchruledata, candscoremin, candscoremax, candscoresum);
303 else
304 deltaplus = SCIPadjustedVarUb(scip, cand, candbrpoint) - SCIPvarGetLbLocal(cand);
305
307 deltaminus = SCIPisInfinity(scip, candscoremax) ? SCIPinfinity(scip) : WEIGHTEDSCORING(branchruledata, candscoremin, candscoremax, candscoresum);
308 else
309 deltaminus = SCIPvarGetUbLocal(cand) - SCIPadjustedVarLb(scip, cand, candbrpoint);
310 break;
311
312 case 'v':
313 deltaplus = SCIPisInfinity(scip, candscoremax) ? SCIPinfinity(scip) : WEIGHTEDSCORING(branchruledata, candscoremin, candscoremax, candscoresum);
314 deltaminus = deltaplus;
315 break;
316
317 default :
318 SCIPerrorMessage("branching strategy %c unknown\n", strategy);
319 SCIPABORT();
320 return SCIP_INVALIDDATA; /*lint !e527*/
321 }
322
323 if( SCIPisInfinity(scip, deltaminus) || SCIPisInfinity(scip, deltaplus) )
324 {
325 branchscore = SCIPinfinity(scip);
326 }
327 else
328 {
329 pscostdown = SCIPgetVarPseudocostVal(scip, cand, -deltaminus);
330 pscostup = SCIPgetVarPseudocostVal(scip, cand, deltaplus);
331 branchscore = SCIPgetBranchScore(scip, cand, pscostdown, pscostup);
332 assert(!SCIPisNegative(scip, branchscore));
333 }
334 SCIPdebugMsg(scip, "branching score variable <%s>[%g,%g] = %g; wscore = %g; type=%d bestbrscore=%g\n",
335 SCIPvarGetName(cand), SCIPvarGetLbLocal(cand), SCIPvarGetUbLocal(cand), branchscore, WEIGHTEDSCORING(branchruledata, candscoremin, candscoremax, candscoresum),
336 SCIPvarGetType(cand), *bestscore);
337
338 if( SCIPisInfinity(scip, branchscore) )
339 branchscore = 0.9*SCIPinfinity(scip);
340
341 if( SCIPisSumGT(scip, branchscore, *bestscore) )
342 {
343 (*bestscore) = branchscore;
344 (*bestrndscore) = candrndscore;
345 (*bestvar) = cand;
346 (*bestbrpoint) = candbrpoint;
347 return SCIP_OKAY;
348 }
349
350 /* if score of candidate is worse than bestscore, stay with best candidate */
351 if( !SCIPisSumEQ(scip, branchscore, *bestscore) )
352 return SCIP_OKAY;
353
355 {
356 /* best candidate is unbounded -> we prefer to branch on it */
358 SCIPrandomGetReal(branchruledata->randnumgen, 0.0, 1.0) <= 0.5
359 )
360 {
361 /* but if the new candidate is also unbounded (thus as good as best candidate),
362 * then switch to the candidate with 50% probability to reduce performance variability
363 */
364 (*bestscore) = branchscore;
365 (*bestrndscore) = candrndscore;
366 (*bestvar) = cand;
367 (*bestbrpoint) = candbrpoint;
368 }
369
370 return SCIP_OKAY;
371 }
372
373 /* best candidate has a finite lower or upper bound -> consider taking the other candidate */
374
377 {
378 /* both candidates are unbounded, but one side may be finite (for bestcand we know there is one)
379 * take the candidate with the larger bound on the bounded side (hope that this avoids branching on always the same variable)
380 * this will also prefer unbounded variables over bounded ones
381 */
382 if( SCIPvarGetUbLocal(cand) > SCIPvarGetUbLocal(*bestvar) || SCIPvarGetLbLocal(cand) < SCIPvarGetLbLocal(*bestvar) )
383 {
384 /* cand is better than bestvar */
385 (*bestscore) = branchscore;
386 (*bestrndscore) = candrndscore;
387 (*bestvar) = cand;
388 (*bestbrpoint) = candbrpoint;
389 return SCIP_OKAY;
390 }
391
392 if( SCIPvarGetUbLocal(*bestvar) > SCIPvarGetUbLocal(cand) || SCIPvarGetLbLocal(*bestvar) < SCIPvarGetLbLocal(cand) )
393 {
394 /* bestvar is better than cand */
395 return SCIP_OKAY;
396 }
397
398 /* both are equally good */
399 }
400
401 if( SCIPvarGetType(*bestvar) == SCIPvarGetType(cand) )
402 {
403 /* if both have the same type, take the one with larger relative diameter */
405 {
406 /* cand has larger diameter than bestvar*/
407 (*bestscore) = branchscore;
408 (*bestrndscore) = candrndscore;
409 (*bestvar) = cand;
410 (*bestbrpoint) = candbrpoint;
411 return SCIP_OKAY;
412 }
413
415 {
416 /* bestvar has larger diameter than cand */
417 return SCIP_OKAY;
418 }
419 }
420
421 /* take the one with better type ("more discrete") */
422 if( SCIPvarGetType(*bestvar) > SCIPvarGetType(cand) )
423 {
424 /* cand is more discrete than bestvar */
425 (*bestscore) = branchscore;
426 (*bestrndscore) = candrndscore;
427 (*bestvar) = cand;
428 (*bestbrpoint) = candbrpoint;
429 return SCIP_OKAY;
430 }
431 if( SCIPvarGetType(*bestvar) < SCIPvarGetType(cand) )
432 {
433 /* bestvar is more discrete than cand */
434 return SCIP_OKAY;
435 }
436
437 /* cand seems to be as good as the currently best one (bestvar); use the random score as a final tie-breaker */
438 if( candrndscore >= (*bestrndscore) )
439 {
440 (*bestscore) = branchscore;
441 (*bestrndscore) = candrndscore;
442 (*bestvar) = cand;
443 (*bestbrpoint) = candbrpoint;
444 }
445
446 return SCIP_OKAY;
447}
448
449/** selects the branching variable from given candidate array */
450static
452 SCIP* scip, /**< SCIP data structure */
453 SCIP_BRANCHRULE* branchrule, /**< branching rule */
454 SCIP_VAR** cands, /**< array of branching candidates */
455 SCIP_Real* candssol, /**< array of candidate solution values */
456 SCIP_Real* candsscore, /**< array of candidate scores */
457 int ncands, /**< the number of candidates */
458 SCIP_VAR** brvar, /**< pointer to store the selected branching candidate or NULL if none */
459 SCIP_Real* brpoint /**< pointer to store branching point of selected branching variable */
460 )
461{ /*lint --e{850}*/
462 SCIP_BRANCHRULEDATA* branchruledata;
463
464 SCIP_VAR* cand;
465 SCIP_Real candsol;
466
467 SCIP_Real bestbranchscore;
468 SCIP_Real bestrndscore;
469
470 SCIP_Real scoremin;
471 SCIP_Real scoresum;
472 SCIP_Real scoremax;
473
474 SCIP_VAR** candssorted;
475 int* candsorigidx;
476
477 int i;
478 int j;
479
480 assert(brvar != NULL);
481 assert(brpoint != NULL);
482
483 (*brvar) = NULL;
484 (*brpoint) = SCIP_INVALID;
485
486 if( ncands == 0 )
487 return SCIP_OKAY;
488
489 branchruledata = SCIPbranchruleGetData(branchrule);
490 assert(branchruledata != NULL);
491
492 /* sort branching candidates (in a copy), such that same variables are on consecutive positions */
493 SCIP_CALL( SCIPduplicateBufferArray(scip, &candssorted, cands, ncands) );
494 SCIP_CALL( SCIPallocBufferArray(scip, &candsorigidx, ncands) );
495 for( i = 0; i < ncands; ++i )
496 candsorigidx[i] = i;
497
498 SCIPsortPtrInt((void**)candssorted, candsorigidx, SCIPvarComp, ncands);
499
500 bestbranchscore = -1.0;
501 bestrndscore = -1.0;
502
503 for( i = 0; i < ncands; ++i )
504 {
505 cand = candssorted[i];
506
507 /* there should be no fixed branching candidates */
508 assert(!SCIPisEQ(scip, SCIPvarGetLbLocal(cand), SCIPvarGetUbLocal(cand)));
509
510 /* compute min, sum, and max of all registered scores for this variables
511 * set candsol to a valid value, if someone registered one */
512 scoremin = candsscore[candsorigidx[i]];
513 scoresum = scoremin;
514 scoremax = scoremin;
515 candsol = candssol[candsorigidx[i]];
516 for( j = i+1 ; j < ncands && SCIPvarCompare(candssorted[j], cand) == 0; ++j )
517 {
518 assert(candsscore[candsorigidx[j]] >= 0.0);
519 scoresum += candsscore[candsorigidx[j]];
520 if( candsscore[candsorigidx[j]] < scoremin )
521 scoremin = candsscore[candsorigidx[j]];
522 else if( candsscore[candsorigidx[j]] > scoremax )
523 scoremax = candsscore[candsorigidx[j]];
524
525 /* @todo if there are two valid externcandssol available for the same variable, should we take the one closer to the middle of the domain? */
526 if( SCIPisInfinity(scip, REALABS(candsol)) )
527 candsol = candssol[candsorigidx[j]];
528 }
529 /* set i to last occurrence of cand in candssorted (instead of first one as before), so in next round we look at another variable */
530 i = j-1;
531 assert(candssorted[i] == cand);
532
533 /* check if new candidate is better than previous candidate (if any) */
534 SCIP_CALL( updateBestCandidate(scip, branchruledata, brvar, brpoint, &bestbranchscore, &bestrndscore, cand,
535 scoremin, scoremax, scoresum, SCIPrandomGetReal(branchruledata->randnumgen, 0.0, 1.0), candsol) );
536 }
537
538 /* there were candidates, but no variable was selected; this can only happen if the branching points are huge values
539 * for all non-continuous variables on which we cannot branch
540 * @todo delay the node?
541 */
542 if( (*brvar) == NULL )
543 {
544 SCIPerrorMessage("no branching could be created: all external candidates have huge bounds\n");
545 return SCIP_BRANCHERROR; /*lint !e527*/
546 }
547
548 /* free buffer arrays */
549 SCIPfreeBufferArray(scip, &candsorigidx);
550 SCIPfreeBufferArray(scip, &candssorted);
551
552 return SCIP_OKAY;
553}
554
555/*
556 * Callback methods
557 */
558
559/** copy method for branchrule plugins (called when SCIP copies plugins) */
560static
561SCIP_DECL_BRANCHCOPY(branchCopyPscost)
562{ /*lint --e{715}*/
563 assert(scip != NULL);
564 assert(branchrule != NULL);
565 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
566
567 /* call inclusion method of branchrule */
569
570 return SCIP_OKAY;
571}
572
573/** destructor of branching rule to free user data (called when SCIP is exiting) */
574static
575SCIP_DECL_BRANCHFREE(branchFreePscost)
576{ /*lint --e{715}*/
577 SCIP_BRANCHRULEDATA* branchruledata;
578
579 /* get branching rule data */
580 branchruledata = SCIPbranchruleGetData(branchrule);
581 assert(branchruledata != NULL);
582
583 /* free random number generator */
584 SCIPfreeRandom(scip, &branchruledata->randnumgen);
585
586 /* free branching rule data */
587 SCIPfreeBlockMemory(scip, &branchruledata);
588 SCIPbranchruleSetData(branchrule, NULL);
589
590 return SCIP_OKAY;
591}
592
593/** initialization method of branching rule (called after problem was transformed) */
594static
595SCIP_DECL_BRANCHINIT(branchInitPscost)
596{ /*lint --e{715}*/
597 SCIP_BRANCHRULEDATA* branchruledata;
598
599 /* initialize branching rule data */
600 branchruledata = SCIPbranchruleGetData(branchrule);
601 assert(branchruledata != NULL);
602
603 SCIPsetRandomSeed(scip, branchruledata->randnumgen, BRANCHRULE_RANDSEED_DEFAULT);
604
605 return SCIP_OKAY;
606}
607
608/** branching execution method for fractional LP solutions */
609static
610SCIP_DECL_BRANCHEXECLP(branchExeclpPscost)
611{ /*lint --e{715}*/
612 SCIP_VAR** lpcands;
613 SCIP_Real* lpcandssol;
614 SCIP_Real bestscore;
615 SCIP_Real bestrootdiff;
616 int nlpcands;
617 int bestcand;
618 int c;
619
620 assert(branchrule != NULL);
621 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
622 assert(scip != NULL);
623 assert(result != NULL);
624
625 SCIPdebugMsg(scip, "Execlp method of pscost branching\n");
626
627 /* get branching candidates */
628 SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, NULL, NULL, &nlpcands, NULL) );
629 assert(nlpcands > 0);
630
631 bestcand = -1;
632 bestscore = -SCIPinfinity(scip);
633 bestrootdiff = 0.0;
634 for( c = 0; c < nlpcands; ++c )
635 {
636 SCIP_Real score;
637 SCIP_Real rootsolval;
638 SCIP_Real rootdiff;
639
640 score = SCIPgetVarPseudocostScore(scip, lpcands[c], lpcandssol[c]);
641 rootsolval = SCIPvarGetRootSol(lpcands[c]);
642 rootdiff = REALABS(lpcandssol[c] - rootsolval);
643 if( SCIPisSumGT(scip, score, bestscore) || (SCIPisSumEQ(scip, score, bestscore) && rootdiff > bestrootdiff) )
644 {
645 bestcand = c;
646 bestscore = score;
647 bestrootdiff = rootdiff;
648 }
649 }
650 assert(0 <= bestcand && bestcand < nlpcands);
651 assert(!SCIPisFeasIntegral(scip, lpcandssol[bestcand]));
652 assert(!SCIPisFeasIntegral(scip, SCIPvarGetSol(lpcands[bestcand], TRUE)));
653
654 /* perform the branching */
655 SCIPdebugMsg(scip, " -> %d cands, selected cand %d: variable <%s> (solval=%g, score=%g)\n",
656 nlpcands, bestcand, SCIPvarGetName(lpcands[bestcand]), lpcandssol[bestcand], bestscore);
657
658 /* perform the branching */
659 SCIP_CALL( SCIPbranchVar(scip, lpcands[bestcand], NULL, NULL, NULL) );
660 *result = SCIP_BRANCHED;
661
662 return SCIP_OKAY;
663}
664
665
666/** branching execution method for external candidates */
667static
668SCIP_DECL_BRANCHEXECEXT(branchExecextPscost)
669{ /*lint --e{715}*/
670 SCIP_BRANCHRULEDATA* branchruledata;
671 SCIP_VAR** externcands;
672 SCIP_Real* externcandssol;
673 SCIP_Real* externcandsscore;
674 int nprioexterncands;
675 SCIP_VAR* brvar;
676 SCIP_Real brpoint;
677 int nchildren;
678
679 assert(branchrule != NULL);
680 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
681 assert(scip != NULL);
682 assert(result != NULL);
683
684 branchruledata = SCIPbranchruleGetData(branchrule);
685 assert(branchruledata != NULL);
686
687 SCIPdebugMsg(scip, "Execext method of pscost branching\n");
688
689 /* get branching candidates */
690 SCIP_CALL( SCIPgetExternBranchCands(scip, &externcands, &externcandssol, &externcandsscore, NULL, &nprioexterncands, NULL, NULL, NULL) );
691 assert(nprioexterncands > 0);
692
693 /* get current update strategy for pseudo costs, if our multiplier rule is 'u' */
694 if( branchruledata->strategy == 'u' )
695 {
696 SCIP_CALL( SCIPgetCharParam(scip, "branching/lpgainnormalize", &branchruledata->updatestrategy) );
697 }
698
699 /* select branching variable */
700 SCIP_CALL( selectBranchVar(scip, branchrule, externcands, externcandssol, externcandsscore, nprioexterncands, &brvar, &brpoint) );
701
702 if( brvar == NULL )
703 {
704 /* can happen if all candidates were non-continous variables with huge bounds */
705 *result = SCIP_DIDNOTFIND;
706 return SCIP_OKAY;
707 }
708
709 assert(SCIPvarIsActive(SCIPvarGetProbvar(brvar)));
710
711 SCIPdebugMsg(scip, "branching on variable <%s>: new intervals: [%g, %g] and [%g, %g]\n",
712 SCIPvarGetName(brvar), SCIPvarGetLbLocal(brvar), SCIPadjustedVarUb(scip, brvar, brpoint), SCIPadjustedVarLb(scip, brvar, brpoint), SCIPvarGetUbLocal(brvar));
713
714 if( branchruledata->nchildren > 2 && SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) <= branchruledata->narymaxdepth )
715 {
716 /* do n-ary branching */
717 SCIP_Real minwidth;
718
719 minwidth = 0.0;
721 minwidth = branchruledata->naryminwidth * (SCIPvarGetUbGlobal(brvar) - SCIPvarGetLbGlobal(brvar));
722
723 SCIP_CALL( SCIPbranchVarValNary(scip, brvar, brpoint, branchruledata->nchildren, minwidth, branchruledata->narywidthfactor, &nchildren) );
724 }
725 else
726 {
727 /* do binary branching */
728 SCIP_CALL( SCIPbranchVarValNary(scip, brvar, brpoint, 2, 0.0, 1.0, &nchildren) );
729 }
730
731 if( nchildren > 1 )
732 {
733 *result = SCIP_BRANCHED;
734 }
735 else
736 {
737 /* if there are no children, then variable should have been fixed by SCIPbranchVarVal */
738 assert(SCIPisEQ(scip, SCIPvarGetLbLocal(brvar), SCIPvarGetUbLocal(brvar)));
739 *result = SCIP_REDUCEDDOM;
740 }
741
742 return SCIP_OKAY;
743}
744
745
746/*
747 * branching specific interface methods
748 */
749
750/** creates the pseudo cost branching rule and includes it in SCIP */
752 SCIP* scip /**< SCIP data structure */
753 )
754{
755 SCIP_BRANCHRULEDATA* branchruledata;
756 SCIP_BRANCHRULE* branchrule;
757
758 /* create pscost branching rule data */
759 SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
760
761 /* include allfullstrong branching rule */
764
765 assert(branchrule != NULL);
766 /* create a random number generator */
767 SCIP_CALL( SCIPcreateRandom(scip, &branchruledata->randnumgen,
769
770 /* set non-fundamental callbacks via specific setter functions*/
771 SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyPscost) );
772 SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreePscost) );
773 SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitPscost) );
774 SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpPscost) );
775 SCIP_CALL( SCIPsetBranchruleExecExt(scip, branchrule, branchExecextPscost) );
776
777 SCIP_CALL( SCIPaddCharParam(scip, "branching/" BRANCHRULE_NAME "/strategy",
778 "strategy for utilizing pseudo-costs of external branching candidates (multiply as in pseudo costs 'u'pdate rule, or by 'd'omain reduction, or by domain reduction of 's'ibling, or by 'v'ariable score)",
779 &branchruledata->strategy, FALSE, BRANCHRULE_STRATEGY_DEFAULT, BRANCHRULE_STRATEGIES, NULL, NULL) );
780
781 SCIP_CALL( SCIPaddRealParam(scip, "branching/" BRANCHRULE_NAME "/minscoreweight",
782 "weight for minimum of scores of a branching candidate when building weighted sum of min/max/sum of scores",
783 &branchruledata->scoreminweight, TRUE, BRANCHRULE_SCOREMINWEIGHT_DEFAULT, -SCIPinfinity(scip), SCIPinfinity(scip), NULL, NULL) );
784
785 SCIP_CALL( SCIPaddRealParam(scip, "branching/" BRANCHRULE_NAME "/maxscoreweight",
786 "weight for maximum of scores of a branching candidate when building weighted sum of min/max/sum of scores",
787 &branchruledata->scoremaxweight, TRUE, BRANCHRULE_SCOREMAXWEIGHT_DEFAULT, -SCIPinfinity(scip), SCIPinfinity(scip), NULL, NULL) );
788
789 SCIP_CALL( SCIPaddRealParam(scip, "branching/" BRANCHRULE_NAME "/sumscoreweight",
790 "weight for sum of scores of a branching candidate when building weighted sum of min/max/sum of scores",
791 &branchruledata->scoresumweight, TRUE, BRANCHRULE_SCORESUMWEIGHT_DEFAULT, -SCIPinfinity(scip), SCIPinfinity(scip), NULL, NULL) );
792
793 SCIP_CALL( SCIPaddIntParam(scip, "branching/" BRANCHRULE_NAME "/nchildren",
794 "number of children to create in n-ary branching",
795 &branchruledata->nchildren, FALSE, BRANCHRULE_NCHILDREN_DEFAULT, 2, INT_MAX, NULL, NULL) );
796
797 SCIP_CALL( SCIPaddIntParam(scip, "branching/" BRANCHRULE_NAME "/narymaxdepth",
798 "maximal depth where to do n-ary branching, -1 to turn off",
799 &branchruledata->narymaxdepth, FALSE, BRANCHRULE_NARYMAXDEPTH_DEFAULT, -1, INT_MAX, NULL, NULL) );
800
801 SCIP_CALL( SCIPaddRealParam(scip, "branching/" BRANCHRULE_NAME "/naryminwidth",
802 "minimal domain width in children when doing n-ary branching, relative to global bounds",
803 &branchruledata->naryminwidth, FALSE, BRANCHRULE_NARYMINWIDTH_DEFAULT, 0.0, 1.0, NULL, NULL) );
804
805 SCIP_CALL( SCIPaddRealParam(scip, "branching/" BRANCHRULE_NAME "/narywidthfactor",
806 "factor of domain width in n-ary branching when creating nodes with increasing distance from branching value",
807 &branchruledata->narywidthfactor, FALSE, BRANCHRULE_NARYWIDTHFAC_DEFAULT, 1.0, SCIP_REAL_MAX, NULL, NULL) );
808
809 return SCIP_OKAY;
810}
811
812/** selects a branching variable, due to pseudo cost, from the given candidate array and returns this variable together
813 * with a branching point */
815 SCIP* scip, /**< SCIP data structure */
816 SCIP_VAR** branchcands, /**< branching candidates */
817 SCIP_Real* branchcandssol, /**< solution value for the branching candidates */
818 SCIP_Real* branchcandsscore, /**< array of candidate scores */
819 int nbranchcands, /**< number of branching candidates */
820 SCIP_VAR** var, /**< pointer to store the variable to branch on, or NULL if none */
821 SCIP_Real* brpoint /**< pointer to store the branching point for the branching variable, will be fractional for a discrete variable */
822 )
823{
824 SCIP_BRANCHRULE* branchrule;
825
826 assert(scip != NULL);
827
828 /* find branching rule */
830 assert(branchrule != NULL);
831
832 /* select branching variable */
833 SCIP_CALL( selectBranchVar(scip, branchrule, branchcands, branchcandssol, branchcandsscore, nbranchcands, var, brpoint) );
834
835 return SCIP_OKAY;
836}
#define BRANCHRULE_DESC
Definition: branch_pscost.c:54
static SCIP_DECL_BRANCHFREE(branchFreePscost)
static SCIP_DECL_BRANCHEXECLP(branchExeclpPscost)
#define BRANCHRULE_NCHILDREN_DEFAULT
Definition: branch_pscost.c:64
#define BRANCHRULE_PRIORITY
Definition: branch_pscost.c:55
static SCIP_DECL_BRANCHEXECEXT(branchExecextPscost)
#define BRANCHRULE_NARYMAXDEPTH_DEFAULT
Definition: branch_pscost.c:65
static SCIP_RETCODE selectBranchVar(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR **cands, SCIP_Real *candssol, SCIP_Real *candsscore, int ncands, SCIP_VAR **brvar, SCIP_Real *brpoint)
static SCIP_DECL_BRANCHINIT(branchInitPscost)
#define BRANCHRULE_NAME
Definition: branch_pscost.c:53
#define BRANCHRULE_SCOREMAXWEIGHT_DEFAULT
Definition: branch_pscost.c:62
static SCIP_RETCODE updateBestCandidate(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR **bestvar, SCIP_Real *bestbrpoint, SCIP_Real *bestscore, SCIP_Real *bestrndscore, SCIP_VAR *cand, SCIP_Real candscoremin, SCIP_Real candscoremax, SCIP_Real candscoresum, SCIP_Real candrndscore, SCIP_Real candsol)
Definition: branch_pscost.c:98
#define BRANCHRULE_RANDSEED_DEFAULT
Definition: branch_pscost.c:68
#define BRANCHRULE_NARYMINWIDTH_DEFAULT
Definition: branch_pscost.c:66
#define WEIGHTEDSCORING(data, min, max, sum)
Definition: branch_pscost.c:71
#define BRANCHRULE_NARYWIDTHFAC_DEFAULT
Definition: branch_pscost.c:67
#define BRANCHRULE_SCOREMINWEIGHT_DEFAULT
Definition: branch_pscost.c:61
#define BRANCHRULE_SCORESUMWEIGHT_DEFAULT
Definition: branch_pscost.c:63
static SCIP_DECL_BRANCHCOPY(branchCopyPscost)
#define BRANCHRULE_STRATEGY_DEFAULT
Definition: branch_pscost.c:60
#define BRANCHRULE_STRATEGIES
Definition: branch_pscost.c:59
#define BRANCHRULE_MAXDEPTH
Definition: branch_pscost.c:56
#define BRANCHRULE_MAXBOUNDDIST
Definition: branch_pscost.c:57
pseudo costs branching rule
#define NULL
Definition: def.h:267
#define SCIP_REAL_MAX
Definition: def.h:174
#define SCIP_INVALID
Definition: def.h:193
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIPABORT()
Definition: def.h:346
#define REALABS(x)
Definition: def.h:197
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_RETCODE SCIPselectBranchVarPscost(SCIP *scip, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsscore, int nbranchcands, SCIP_VAR **var, SCIP_Real *brpoint)
SCIP_RETCODE SCIPincludeBranchrulePscost(SCIP *scip)
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition: misc.c:11184
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:167
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 SCIPgetCharParam(SCIP *scip, const char *name, char *value)
Definition: scip_param.c:326
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: scip_branch.c:265
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:249
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:297
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:153
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 SCIPgetExternBranchCands(SCIP *scip, SCIP_VAR ***externcands, SCIP_Real **externcandssol, SCIP_Real **externcandsscore, int *nexterncands, int *nprioexterncands, int *nprioexternbins, int *nprioexternints, int *nprioexternimpls)
Definition: scip_branch.c:511
SCIP_Real SCIPgetBranchingPoint(SCIP *scip, SCIP_VAR *var, SCIP_Real suggestion)
Definition: scip_branch.c:897
SCIP_RETCODE SCIPbranchVarValNary(SCIP *scip, SCIP_VAR *var, SCIP_Real val, int n, SCIP_Real minwidth, SCIP_Real widthfactor, int *nchildren)
Definition: scip_branch.c:1189
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
SCIP_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: scip_branch.c:849
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7503
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisHugeValue(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisSumEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisSumGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:91
SCIP_Real SCIPvarGetSol(SCIP_VAR *var, SCIP_Bool getlpval)
Definition: var.c:13257
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17748
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17538
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition: var.c:12218
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_Real SCIPadjustedVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real ub)
Definition: scip_var.c:4645
SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
Definition: var.c:13350
SCIP_Real SCIPgetVarPseudocostVal(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta)
Definition: scip_var.c:8814
SCIP_Real SCIPadjustedVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real lb)
Definition: scip_var.c:4613
SCIP_VAR ** SCIPvarGetMultaggrVars(SCIP_VAR *var)
Definition: var.c:17858
int SCIPvarGetMultaggrNVars(SCIP_VAR *var)
Definition: var.c:17846
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
SCIP_Real SCIPcomputeVarLbLocal(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:6505
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
int SCIPvarCompare(SCIP_VAR *var1, SCIP_VAR *var2)
Definition: var.c:11942
SCIP_Real SCIPcomputeVarUbLocal(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:6526
SCIP_Real SCIPgetVarPseudocostScore(SCIP *scip, SCIP_VAR *var, SCIP_Real solval)
Definition: scip_var.c:9103
SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var)
Definition: var.c:17870
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
void SCIPsetRandomSeed(SCIP *scip, SCIP_RANDNUMGEN *randnumgen, unsigned int seed)
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10130
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
void SCIPsortPtrInt(void **ptrarray, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
memory allocation routines
public methods for branching rules
public methods for message output
#define SCIPerrorMessage
Definition: pub_message.h:64
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for branch and bound tree
public methods for problem variables
public methods for branching rule plugins and branching
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for random numbers
public methods for solutions
public methods for the branch-and-bound tree
public methods for SCIP variables
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:57
@ SCIP_REDUCEDDOM
Definition: type_result.h:51
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_BRANCHED
Definition: type_result.h:54
@ SCIP_BRANCHERROR
Definition: type_retcode.h:60
@ SCIP_INVALIDDATA
Definition: type_retcode.h:52
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:71
@ SCIP_VARSTATUS_MULTAGGR
Definition: type_var.h:54