branch_relpsprob.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* GCG --- Generic Column Generation */
5 /* a Dantzig-Wolfe decomposition based extension */
6 /* of the branch-cut-and-price framework */
7 /* SCIP --- Solving Constraint Integer Programs */
8 /* */
9 /* Copyright (C) 2010-2018 Operations Research, RWTH Aachen University */
10 /* Zuse Institute Berlin (ZIB) */
11 /* */
12 /* This program is free software; you can redistribute it and/or */
13 /* modify it under the terms of the GNU Lesser General Public License */
14 /* as published by the Free Software Foundation; either version 3 */
15 /* of the License, or (at your option) any later version. */
16 /* */
17 /* This program is distributed in the hope that it will be useful, */
18 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
19 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
20 /* GNU Lesser General Public License for more details. */
21 /* */
22 /* You should have received a copy of the GNU Lesser General Public License */
23 /* along with this program; if not, write to the Free Software */
24 /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
25 /* */
26 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
27 
43 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
44 /* #define SCIP_DEBUG */
45 #include <assert.h>
46 #include <string.h>
47 
48 #include "branch_relpsprob.h"
49 #include "relax_gcg.h"
50 #include "cons_integralorig.h"
51 #include "pricer_gcg.h"
52 #include "gcg.h"
53 
54 #include "scip/nodesel_estimate.h"
55 #include "scip/nodesel_hybridestim.h"
56 #include "scip/nodesel_restartdfs.h"
57 #include "scip/branch_allfullstrong.h"
58 #include "scip/branch_fullstrong.h"
59 #include "scip/branch_inference.h"
60 #include "scip/branch_mostinf.h"
61 #include "scip/branch_leastinf.h"
62 #include "scip/branch_pscost.h"
63 #include "scip/branch_random.h"
64 #include "scip/branch_relpscost.h"
65 #include "scip/nodesel_bfs.h"
66 #include "scip/nodesel_dfs.h"
67 
68 
69 #define BRANCHRULE_NAME "relpsprob"
70 #define BRANCHRULE_DESC "generalized reliability branching using probing"
71 #define BRANCHRULE_PRIORITY -100
72 #define BRANCHRULE_MAXDEPTH -1
73 #define BRANCHRULE_MAXBOUNDDIST 1.0
74 
75 #define DEFAULT_CONFLICTWEIGHT 0.01
76 #define DEFAULT_CONFLENGTHWEIGHT 0.0001
77 #define DEFAULT_INFERENCEWEIGHT 0.1
78 #define DEFAULT_CUTOFFWEIGHT 0.0001
79 #define DEFAULT_PSCOSTWEIGHT 1.0
80 #define DEFAULT_MINRELIABLE 1.0
81 #define DEFAULT_MAXRELIABLE 8.0
82 #define DEFAULT_ITERQUOT 0.5
83 #define DEFAULT_ITEROFS 100000
84 #define DEFAULT_MAXLOOKAHEAD 8
85 #define DEFAULT_INITCAND 100
86 #define DEFAULT_MAXBDCHGS 20
87 #define DEFAULT_MINBDCHGS 1
88 #define DEFAULT_USELP TRUE
89 #define DEFAULT_RELIABILITY 0.8
91 #define HASHSIZE_VARS 131101
95 struct SCIP_BranchruleData
96 {
97  SCIP_Real conflictweight;
98  SCIP_Real conflengthweight;
99  SCIP_Real inferenceweight;
100  SCIP_Real cutoffweight;
101  SCIP_Real pscostweight;
102  SCIP_Real minreliable;
103  SCIP_Real maxreliable;
104  SCIP_Real iterquot;
105  SCIP_Longint nlpiterations;
106  int iterofs;
108  int initcand;
109  int maxbdchgs;
110  int minbdchgs;
111  SCIP_Bool uselp;
114  SCIP_Real reliability;
118  int nprobings;
119  SCIP_HASHMAP* varhashmap;
122  int nvars;
123 };
124 
126 struct BdchgData
127 {
128  SCIP_HASHMAP* varhashmap;
129  SCIP_Real* lbchgs;
130  SCIP_Real* ubchgs;
131  SCIP_Bool* infroundings;
132  int nvars;
133 };
134 typedef struct BdchgData BDCHGDATA;
135 
136 
137 /*
138  * local methods
139  */
140 
141 /* creates bound change data structure:
142  * all variables are put into a hashmap and arrays containig current lower and upper bounds are created
143  */
144 static
145 SCIP_RETCODE createBdchgData(
146  SCIP* scip,
147  BDCHGDATA** bdchgdata,
148  SCIP_VAR** vars,
149  int nvars
150  )
151 {
152 
153  int i;
154 
155  assert(scip != NULL);
156  assert(*bdchgdata == NULL);
157 
158  /* get memory for bound change data structure */
159  SCIP_CALL( SCIPallocBuffer(scip, bdchgdata) );
160 
161  /* create hash map */
162  SCIP_CALL( SCIPhashmapCreate(&(*bdchgdata)->varhashmap, SCIPblkmem(scip), HASHSIZE_VARS) );
163 
164  /* get all variables */
165  SCIP_CALL( SCIPallocBufferArray(scip, &(*bdchgdata)->lbchgs, nvars) );
166  SCIP_CALL( SCIPallocBufferArray(scip, &(*bdchgdata)->ubchgs, nvars) );
167  SCIP_CALL( SCIPallocBufferArray(scip, &(*bdchgdata)->infroundings, nvars) );
168  (*bdchgdata)->nvars = nvars;
169 
170  /* store current local bounds and capture variables */
171  for( i = 0; i < nvars; ++i )
172  {
173  SCIP_CALL( SCIPhashmapInsert((*bdchgdata)->varhashmap, vars[i], (void*) (size_t)i) );
174 
175  (*bdchgdata)->lbchgs[i] = SCIPfeasCeil(scip, SCIPvarGetLbLocal(vars[i]));
176  (*bdchgdata)->ubchgs[i] = SCIPfeasFloor(scip, SCIPvarGetUbLocal(vars[i]));
177  (*bdchgdata)->infroundings[i] = FALSE;
178  }
179 
180  return SCIP_OKAY;
181 }
182 
184 static
185 SCIP_RETCODE freeBdchgData(
186  SCIP* scip,
187  BDCHGDATA* bdchgdata
188  )
189 {
190 
191  assert(scip != NULL);
192  assert(bdchgdata != NULL);
193 
194  /* free arrays & hashmap */
195  SCIPfreeBufferArray(scip, &bdchgdata->infroundings);
196  SCIPfreeBufferArray(scip, &bdchgdata->ubchgs);
197  SCIPfreeBufferArray(scip, &bdchgdata->lbchgs);
198 
199  SCIPhashmapFree(&(bdchgdata->varhashmap));
200 
201  /* free memory for bound change data structure */
202  SCIPfreeBuffer(scip, &bdchgdata);
203 
204  return SCIP_OKAY;
205 }
206 
207 
209 static
210 SCIP_RETCODE addBdchg(
211  SCIP* scip,
212  BDCHGDATA* bdchgdata,
213  SCIP_VAR* var,
214  SCIP_Real newbound,
215  SCIP_BOUNDTYPE boundtype,
216  SCIP_Bool infrounding,
217  int* nbdchgs,
218  SCIP_Bool* infeasible
219  )
220 {
221  int nvars;
222  int pos;
223 
224  assert(scip != NULL);
225  assert(bdchgdata != NULL);
226  assert(bdchgdata->varhashmap != NULL);
227  assert(bdchgdata->lbchgs != NULL);
228  assert(bdchgdata->ubchgs != NULL);
229  assert(var != NULL);
230 
231  nvars = bdchgdata->nvars;
232 
233  if( infeasible != NULL )
234  *infeasible = FALSE;
235 
236  /* if variable is not in hashmap insert it and increase array sizes */
237  if( !SCIPhashmapExists(bdchgdata->varhashmap, var) )
238  {
239  SCIP_CALL( SCIPhashmapInsert(bdchgdata->varhashmap, var, (void*) (size_t)nvars) );
240  SCIP_CALL( SCIPreallocBufferArray(scip, &bdchgdata->lbchgs, nvars + 1) );
241  SCIP_CALL( SCIPreallocBufferArray(scip, &bdchgdata->ubchgs, nvars + 1) );
242 
243  bdchgdata->lbchgs[nvars] = SCIPfeasCeil(scip, SCIPvarGetLbLocal(var));
244  bdchgdata->ubchgs[nvars] = SCIPfeasFloor(scip, SCIPvarGetUbLocal(var));
245  (bdchgdata->nvars)++;
246 
247  assert(SCIPhashmapExists(bdchgdata->varhashmap, var)
248  && (int)(size_t) SCIPhashmapGetImage(bdchgdata->varhashmap, var) == nvars); /*lint !e507*/
249 
250  }
251 
252  /* get position of this variable */
253  pos = (int)(size_t) SCIPhashmapGetImage(bdchgdata->varhashmap, var); /*lint !e507*/
254 
255  if( infrounding )
256  {
257  bdchgdata->infroundings[pos] = TRUE;
258  }
259 
260  /* update bounds if necessary */
261  if( boundtype == SCIP_BOUNDTYPE_LOWER )
262  {
263  if( bdchgdata->lbchgs[pos] < newbound )
264  {
265  bdchgdata->lbchgs[pos] = newbound;
266  (*nbdchgs)++;
267  }
268 
269  if( (infeasible != NULL) && (newbound > bdchgdata->ubchgs[pos]) )
270  {
271  *infeasible = TRUE;
272  }
273 
274  }
275  else
276  {
277  if( newbound < bdchgdata->ubchgs[pos] )
278  {
279  bdchgdata->ubchgs[pos] = newbound;
280  (*nbdchgs)++;
281  }
282  if( (infeasible != NULL) && (newbound < bdchgdata->lbchgs[pos]) )
283  {
284  *infeasible = TRUE;
285  }
286  }
287 
288  return SCIP_OKAY;
289 }
290 
291 
292 
294 static
295 SCIP_RETCODE applyBdchgs(
296  SCIP* scip,
297  BDCHGDATA* bdchgdata,
298  SCIP_NODE* node
299  )
300 {
301  SCIP_VAR** vars;
302 
303  int nintvars;
304  int nbinvars;
305  int nvars;
306  int nbdchgs;
307  int i;
308 
309  assert(scip != NULL);
310  assert(bdchgdata != NULL);
311 
312  SCIPdebugMessage("apply bound changes\n");
313 
314  nbdchgs = 0;
315 
316  /* get all variables */
317  SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
318  nvars = nbinvars + nintvars;
319  assert(vars != NULL);
320 
321  /* get variable image in hashmap and update bounds if better ones found */
322  for( i = 0; i < nvars; ++i )
323  {
324  if( SCIPhashmapExists(bdchgdata->varhashmap, vars[i]) )
325  {
326  int pos;
327  pos = (int)(size_t)SCIPhashmapGetImage(bdchgdata->varhashmap, vars[i]); /*lint !e507*/
328 
329  /* update lower bounds */
330  if( SCIPisFeasGT(scip, (bdchgdata->lbchgs)[pos], SCIPvarGetLbLocal(vars[i])) )
331  {
332  SCIPdebugMessage("branch_relpsprob: update lower bound of <%s> from %g to %g\n",
333  SCIPvarGetName(vars[i]), SCIPvarGetLbLocal(vars[i]), (bdchgdata->lbchgs)[pos]);
334  SCIP_CALL( SCIPchgVarLbNode(scip, node, vars[i], (bdchgdata->lbchgs)[pos]) );
335  ++nbdchgs;
336  }
337  /* update upper bounds */
338  if( SCIPisFeasLT(scip, (bdchgdata->ubchgs)[pos], SCIPvarGetUbLocal(vars[i])) )
339  {
340  SCIPdebugMessage("branch_relpsprob: update upper bound of <%s> from %g to %g\n",
341  SCIPvarGetName(vars[i]), SCIPvarGetUbLocal(vars[i]), (bdchgdata->ubchgs)[pos]);
342 
343  SCIP_CALL( SCIPchgVarUbNode(scip, node, vars[i], (bdchgdata->ubchgs)[pos]) );
344  ++nbdchgs;
345  }
346  }
347  }
348 
349  SCIPdebugMessage("applied %d bound changes\n", nbdchgs);
350  return SCIP_OKAY;
351 }
352 
353 
355 static
356 SCIP_Real calcScore(
357  SCIP* scip,
358  SCIP_BRANCHRULEDATA* branchruledata,
359  SCIP_Real conflictscore,
360  SCIP_Real avgconflictscore,
361  SCIP_Real conflengthscore,
362  SCIP_Real avgconflengthscore,
363  SCIP_Real inferencescore,
364  SCIP_Real avginferencescore,
365  SCIP_Real cutoffscore,
366  SCIP_Real avgcutoffscore,
367  SCIP_Real pscostscore,
368  SCIP_Real avgpscostscore,
369  SCIP_Real frac
370  )
371 {
372  SCIP_Real score;
373 
374  assert(branchruledata != NULL);
375  /* assert(0.0 < frac && frac < 1.0); */
376 
377  score = branchruledata->conflictweight * (1.0 - 1.0/(1.0+conflictscore/avgconflictscore))
378  + branchruledata->conflengthweight * (1.0 - 1.0/(1.0+conflengthscore/avgconflengthscore))
379  + branchruledata->inferenceweight * (1.0 - 1.0/(1.0+inferencescore/avginferencescore))
380  + branchruledata->cutoffweight * (1.0 - 1.0/(1.0+cutoffscore/avgcutoffscore))
381  + branchruledata->pscostweight * (1.0 - 1.0/(1.0+pscostscore/avgpscostscore));
382 
383  /* values close to integral are possible and are adjusted to small non-zero values */
384  if( frac < 0.00000001 || frac > 0.999999 )
385  frac = 0.0001;
386  if( MIN(frac, 1.0 - frac) < 10.0*SCIPfeastol(scip) )
387  score *= 1e-6;
388 
389  return score;
390 }
391 
392 
393 /* calculates variable bounds for an up-branch and a down-branch, supposig a LP or pseudo solution is given */
394 static
395 SCIP_RETCODE calculateBounds(
396  SCIP* scip,
397  SCIP_VAR* branchvar,
398  SCIP_Real* downlb,
399  SCIP_Real* downub,
400  SCIP_Real* uplb,
401  SCIP_Real* upub
402  )
403 {
404  SCIP_Real varsol;
405  SCIP_Real lbdown;
406  SCIP_Real ubdown;
407  SCIP_Real lbup;
408  SCIP_Real ubup;
409 
410  SCIP_Real lblocal;
411  SCIP_Real ublocal;
412 
413  assert(scip != NULL);
414  assert(branchvar != NULL);
415 
416  varsol = SCIPgetVarSol(scip, branchvar);
417 
418  lblocal = SCIPfeasCeil(scip, SCIPvarGetLbLocal(branchvar));
419  ublocal = SCIPfeasFloor(scip, SCIPvarGetUbLocal(branchvar));
420 
421  /* calculate bounds in down branch */
422  lbdown = lblocal;
423 
424  /* in down branch: new upper bound is at most local upper bound - 1 */
425  ubdown = SCIPfeasFloor(scip, varsol) ;
426  if( SCIPisEQ(scip, ubdown, ublocal) )
427  ubdown -= 1.0;
428 
429  assert(lbdown <= ubdown);
430 
431  /* calculate bounds in up branch */
432  ubup = ublocal;
433 
434  /* in right branch: new lower bound is at least local lower bound + 1 */
435  lbup = SCIPfeasCeil(scip, varsol);
436  if( SCIPisEQ(scip, lbup, lblocal) )
437  lbup += 1.0;
438 
439  assert(SCIPisLE(scip, lbup, ubup));
440 
441  /* ensure that both branches partition the domain */
442  if( SCIPisEQ(scip, lbup, ubdown) )
443  {
444  SCIP_Real middle = SCIPfloor(scip, lblocal/2 + ublocal/2);
445 
446  if( SCIPisLE(scip, lbup, middle) )
447  ubdown -= 1.0;
448  else
449  lbup += 1.0;
450  }
451 
452  /* ensure a real partition of the domain */
453  assert(SCIPisLT(scip, ubdown, lbup));
454  assert(SCIPisLE(scip, lbdown, ubdown));
455  assert(SCIPisLE(scip, lbup, ubup));
456 
457  /* set return values */
458  if( downlb != NULL )
459  *downlb = lbdown;
460  if( downub != NULL )
461  *downub = ubdown;
462  if( uplb != NULL )
463  *uplb = lbup;
464  if( upub != NULL )
465  *upub = ubup;
466 
467  return SCIP_OKAY;
468 }
469 
470 
472 static
473 SCIP_RETCODE applyProbing(
474  SCIP* scip,
475  SCIP_VAR** vars,
476  int nvars,
477  SCIP_VAR* probingvar,
478  SCIP_Bool probingdir,
479  SCIP_Bool solvelp,
480  SCIP_Longint* nlpiterations,
481  SCIP_Real* proplbs,
482  SCIP_Real* propubs,
483  SCIP_Real* lpobjvalue,
484  SCIP_Bool* lpsolved,
485  SCIP_Bool* lperror,
487  SCIP_Bool* cutoff
488  )
489 {
490  SCIP* masterscip;
491 
492  /* SCIP_Real varsol; */
493  SCIP_Real leftlbprobing;
494  SCIP_Real leftubprobing;
495  SCIP_Real rightlbprobing;
496  SCIP_Real rightubprobing;
497 
498  leftubprobing = -1.0;
499  leftlbprobing = -1.0;
500  rightlbprobing = -1.0;
501  rightubprobing = -1.0;
502 
503  assert(proplbs != NULL);
504  assert(propubs != NULL);
505  assert(cutoff != NULL);
506  assert(SCIPvarGetLbLocal(probingvar) - 0.5 < SCIPvarGetUbLocal(probingvar));
507  assert(SCIPisFeasIntegral(scip, SCIPvarGetLbLocal(probingvar)));
508  assert(SCIPisFeasIntegral(scip, SCIPvarGetUbLocal(probingvar)));
509 
510  assert(!solvelp || (lpsolved!=NULL && lpobjvalue!=NULL && lperror!=NULL));
511 
512  /* get SCIP data structure of master problem */
513  masterscip = GCGgetMasterprob(scip);
514  assert(masterscip != NULL);
515 
516  /* varsol = SCIPgetRelaxSolVal(scip, probingvar); */
517 
518  if( probingdir == FALSE )
519  {
520 
521  SCIP_CALL( calculateBounds(scip, probingvar,
522  &leftlbprobing, &leftubprobing, NULL, NULL) );
523  }
524  else
525  {
526  SCIP_CALL( calculateBounds(scip, probingvar,
527  NULL, NULL, &rightlbprobing, &rightubprobing) );
528  }
529 
530  SCIPdebugMessage("applying probing on variable <%s> == %u [%g,%g] (nlocks=%d/%d, impls=%d/%d, clqs=%d/%d)\n",
531  SCIPvarGetName(probingvar), probingdir,
532  probingdir ? rightlbprobing : leftlbprobing, probingdir ? rightubprobing : leftubprobing,
533  SCIPvarGetNLocksDown(probingvar), SCIPvarGetNLocksUp(probingvar),
534  SCIPvarGetNImpls(probingvar, FALSE), SCIPvarGetNImpls(probingvar, TRUE),
535  SCIPvarGetNCliques(probingvar, FALSE), SCIPvarGetNCliques(probingvar, TRUE));
536 
537  /* start probing mode */
538  SCIP_CALL( GCGrelaxStartProbing(scip, NULL) );
539  SCIP_CALL( GCGrelaxNewProbingnodeOrig(scip) );
540 
541  *lpsolved = FALSE;
542  *lperror = FALSE;
543 
544  /* change variable bounds for the probing directions*/
545  if( probingdir == FALSE )
546  {
547  SCIP_CALL( SCIPchgVarUbProbing(scip, probingvar, leftubprobing) );
548  }
549  else
550  {
551  SCIP_CALL( SCIPchgVarLbProbing(scip, probingvar, rightlbprobing) );
552  }
553 
554  /* apply propagation */
555  if( !(*cutoff) )
556  {
557  SCIP_CALL( SCIPpropagateProbing(scip, -1, cutoff, NULL) );
558  }
559 
560  /* evaluate propagation */
561  if( !(*cutoff) )
562  {
563  int i;
564 
565  for( i = 0; i < nvars; ++i )
566  {
567  proplbs[i] = SCIPvarGetLbLocal(vars[i]);
568  propubs[i] = SCIPvarGetUbLocal(vars[i]);
569  }
570  }
571 
572  /* if parameter is set, we want to use the outcome of the LP relaxation */
573  if( !(*cutoff) && solvelp )
574  {
575  *nlpiterations -= SCIPgetNLPIterations(masterscip);
576 
578  SCIP_CALL( GCGrelaxNewProbingnodeMaster(scip) );
579  SCIP_CALL( GCGrelaxPerformProbingWithPricing(scip, -1, nlpiterations, NULL,
580  lpobjvalue, lpsolved, lperror, cutoff) );
581  }
582 
583  /* exit probing mode */
584  SCIP_CALL( GCGrelaxEndProbing(scip) );
585 
586  SCIPdebugMessage("probing results in cutoff/lpsolved/lpobj: %s / %s / %g\n",
587  *cutoff?"cutoff":"no cutoff", *lpsolved?"lpsolved":"lp not solved", *lpobjvalue);
588 
589  return SCIP_OKAY;
590 }
591 
592 
594 static
595 SCIP_RETCODE getVarProbingbranch(
596  SCIP* scip,
597  SCIP_VAR* probingvar,
598  BDCHGDATA* bdchgdata,
599  SCIP_Bool solvelp,
600  SCIP_Longint* nlpiterations,
601  SCIP_Real* down,
602  SCIP_Real* up,
603  SCIP_Bool* downvalid,
605  SCIP_Bool* upvalid,
607  SCIP_Bool* downinf,
608  SCIP_Bool* upinf,
609  SCIP_Bool* lperror,
611  int* nbdchgs
612  )
613 {
614  /* data for variables and bdchg arrays */
615  SCIP_VAR** probvars;
616  SCIP_VAR** vars;
617  int nvars;
618  int nintvars;
619  int nbinvars;
620 
621  SCIP_Real* leftproplbs;
622  SCIP_Real* leftpropubs;
623  SCIP_Real* rightproplbs;
624  SCIP_Real* rightpropubs;
625 
626  SCIP_Real leftlpbound;
627  SCIP_Real rightlpbound;
628  SCIP_Bool leftlpsolved;
629  SCIP_Bool rightlpsolved;
630  SCIP_Bool leftlperror;
631  SCIP_Bool rightlperror;
632  SCIP_Bool leftcutoff;
633  SCIP_Bool rightcutoff;
634  SCIP_Bool cutoff;
635  int i;
636  int j;
637 
638  assert(lperror != NULL);
639 
640  if( downvalid != NULL )
641  *downvalid = FALSE;
642  if( upvalid != NULL )
643  *upvalid = FALSE;
644  if( downinf != NULL )
645  *downinf = FALSE;
646  if( upinf != NULL )
647  *upinf = FALSE;
648 
649  if( SCIPisStopped(scip) )
650  {
651  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
652  " (%.1fs) probing aborted: solving stopped\n", SCIPgetSolvingTime(scip));
653  return SCIP_OKAY;
654  }
655 
656  /* get all variables to store branching deductions of variable bounds */
657  /* get all variables and store them in array 'vars' */
658  SCIP_CALL( SCIPgetVarsData(scip, &probvars, NULL, &nbinvars, &nintvars, NULL, NULL) );
659  nvars = nbinvars + nintvars; /* continuous variables are not considered here */
660 
661  SCIP_CALL( SCIPduplicateMemoryArray(scip, &vars, probvars, nvars) );
662 
663  /* capture variables to make sure the variables are not deleted */
664  for( i = 0; i < nvars; ++i )
665  {
666  SCIP_CALL( SCIPcaptureVar(scip, vars[i]) );
667  }
668 
669  /* get temporary memory for storing probing results */
670  SCIP_CALL( SCIPallocBufferArray(scip, &leftproplbs, nvars) );
671  SCIP_CALL( SCIPallocBufferArray(scip, &leftpropubs, nvars) );
672  SCIP_CALL( SCIPallocBufferArray(scip, &rightproplbs, nvars) );
673  SCIP_CALL( SCIPallocBufferArray(scip, &rightpropubs, nvars) );
674 
675  /* for each binary variable, probe fixing the variable to left and right */
676  cutoff = FALSE;
677  leftcutoff = FALSE;
678  rightcutoff = FALSE;
679 
680  /* better assume we don't have an error (fixes clang warning)*/
681  leftlperror = FALSE;
682  rightlperror = FALSE;
683 
684  /* better assume we don't have solved the lp (fixes clang warning)*/
685  leftlpsolved = FALSE;
686  rightlpsolved = FALSE;
687 
688 
689  /* left branch: apply probing for setting ub to LP solution value */
690  SCIP_CALL( applyProbing(scip, vars, nvars, probingvar, FALSE, solvelp, nlpiterations,
691  leftproplbs, leftpropubs,
692  &leftlpbound, &leftlpsolved, &leftlperror, &leftcutoff) );
693 
694  if( leftcutoff )
695  {
696  SCIP_Real newbound;
697 
698  SCIP_CALL( calculateBounds(scip, probingvar, NULL, NULL, &newbound, NULL) );
699 
700  /* lower bound can be updated */
701  SCIPdebugMessage("change lower bound of probing variable <%s> from %g to %g, nlocks=(%d/%d)\n",
702  SCIPvarGetName(probingvar), SCIPvarGetLbLocal(probingvar), newbound,
703  SCIPvarGetNLocksDown(probingvar), SCIPvarGetNLocksUp(probingvar));
704 
705  SCIP_CALL( addBdchg(scip, bdchgdata, probingvar, newbound, SCIP_BOUNDTYPE_LOWER, TRUE, nbdchgs, &cutoff) );
706  }
707 
708  if( !cutoff )
709  {
710  /* right branch: apply probing for setting lb to LP solution value */
711  SCIP_CALL( applyProbing(scip, vars, nvars, probingvar, TRUE, solvelp, nlpiterations,
712  rightproplbs, rightpropubs,
713  &rightlpbound, &rightlpsolved, &rightlperror, &rightcutoff) );
714 
715  if( rightcutoff )
716  {
717  SCIP_Real newbound;
718 
719  SCIP_CALL( calculateBounds(scip, probingvar, NULL, &newbound, NULL, NULL) );
720 
721  /* upper bound can be updated */
722  SCIPdebugMessage("change probing variable <%s> upper bound from %g to %g, nlocks=(%d/%d)\n",
723  SCIPvarGetName(probingvar), SCIPvarGetUbLocal(probingvar), newbound,
724  SCIPvarGetNLocksDown(probingvar), SCIPvarGetNLocksUp(probingvar));
725 
726  SCIP_CALL( addBdchg(scip, bdchgdata, probingvar, newbound, SCIP_BOUNDTYPE_UPPER, TRUE, nbdchgs, &cutoff) );
727  }
728  }
729 
730  /* set return value of lperror */
731  cutoff = cutoff || (leftcutoff && rightcutoff);
732  *lperror = leftlperror || rightlperror;
733 
734 
735  /* analyze probing deductions */
736 
737  /* 1. dualbounds */
738  if( leftlpsolved )
739  *down = leftlpbound;
740  if( rightlpsolved )
741  *up = rightlpbound; /*lint !e644*/
742 
743  /* 2. update bounds */
744  for( j = 0; j < nvars && !cutoff; ++j )
745  {
746  SCIP_Real newlb;
747  SCIP_Real newub;
748 
749  if( vars[j] == probingvar )
750  continue;
751 
752  /* new bounds of the variable is the union of the propagated bounds of the left and right case */
753  newlb = MIN(leftproplbs[j], rightproplbs[j]);
754  newub = MAX(leftpropubs[j], rightpropubs[j]);
755 
756  /* check for fixed variables */
757  if( SCIPisFeasEQ(scip, newlb, newub) )
758  {
759  /* in both probings, variable j is deduced to a fixed value */
760  SCIP_CALL( addBdchg(scip, bdchgdata, vars[j], newlb, SCIP_BOUNDTYPE_LOWER, FALSE, nbdchgs, &cutoff) );
761  SCIP_CALL( addBdchg(scip, bdchgdata, vars[j], newub, SCIP_BOUNDTYPE_UPPER, FALSE, nbdchgs, &cutoff) );
762  continue;
763  }
764  else
765  {
766  SCIP_Real oldlb;
767  SCIP_Real oldub;
768 
769  assert(SCIPvarGetType(vars[j]) == SCIP_VARTYPE_BINARY || SCIPvarGetType(vars[j]) == SCIP_VARTYPE_INTEGER);
770 
771  /* check for bound tightenings */
772  oldlb = SCIPvarGetLbLocal(vars[j]);
773  oldub = SCIPvarGetUbLocal(vars[j]);
774  if( SCIPisLbBetter(scip, newlb, oldlb, oldub) )
775  {
776  /* in both probings, variable j is deduced to be at least newlb: tighten lower bound */
777  SCIP_CALL( addBdchg(scip, bdchgdata, vars[j], newlb, SCIP_BOUNDTYPE_LOWER, FALSE, nbdchgs, &cutoff) );
778  }
779  if( SCIPisUbBetter(scip, newub, oldlb, oldub) && !cutoff )
780  {
781  /* in both probings, variable j is deduced to be at most newub: tighten upper bound */
782  SCIP_CALL( addBdchg(scip, bdchgdata, vars[j], newub, SCIP_BOUNDTYPE_UPPER, FALSE, nbdchgs, &cutoff) );
783  }
784 
785  }
786 
787  } /* end check for deductions */
788 
789  /* set correct return values */
790  if( down != NULL && leftlpsolved )
791  *down = leftlpbound;
792  if( up != NULL && rightlpsolved )
793  *up = rightlpbound;
794  if( downvalid != NULL && leftlpsolved )
795  *downvalid = TRUE;
796  if( downvalid != NULL && !leftlpsolved )
797  *downvalid = FALSE;
798  if( upvalid != NULL && rightlpsolved )
799  *upvalid = TRUE;
800  if( upvalid != NULL && !rightlpsolved )
801  *upvalid = FALSE;
802  if( downinf != NULL )
803  *downinf = leftcutoff;
804  if( upinf != NULL )
805  *upinf = rightcutoff;
806 
807  if( cutoff )
808  {
809  if( downinf != NULL )
810  *downinf = cutoff;
811  if( upinf != NULL )
812  *upinf = cutoff;
813  }
814 
815  /* free temporary memory */
816  SCIPfreeBufferArray(scip, &rightpropubs);
817  SCIPfreeBufferArray(scip, &rightproplbs);
818  SCIPfreeBufferArray(scip, &leftpropubs);
819  SCIPfreeBufferArray(scip, &leftproplbs);
820 
821  /* release variables */
822  for( i = 0; i < nvars; ++i )
823  {
824  SCIP_CALL( SCIPreleaseVar(scip, &vars[i]) );
825  }
826  SCIPfreeMemoryArray(scip, &vars);
827 
828 
829  return SCIP_OKAY;
830 }
831 
832 
833 
834 
836 static
837 SCIP_RETCODE addBranchcandsToData(
838  SCIP* scip,
839  SCIP_BRANCHRULE* branchrule,
840  SCIP_VAR** branchcands,
841  int nbranchcands
842  )
843 {
844 
845  SCIP_BRANCHRULEDATA* branchruledata;
846  int j;
847 
848 
849  /* get branching rule data */
850  branchruledata = SCIPbranchruleGetData(branchrule);
851  assert(branchruledata != NULL);
852 
853  if( branchruledata->nvars == 0 )
854  { /* no variables known before, reinitialized hashmap and variable info storage */
855 
856  /* create hash map */
857  assert(branchruledata->varhashmap == NULL);
858  SCIP_CALL( SCIPhashmapCreate(&(branchruledata->varhashmap), SCIPblkmem(scip), HASHSIZE_VARS) );
859 
860  SCIP_CALL( SCIPallocMemoryArray(scip, &branchruledata->nvarprobings, nbranchcands) );
861  SCIP_CALL( SCIPallocMemoryArray(scip, &branchruledata->nvarbranchings, nbranchcands) );
862  branchruledata->nvars = nbranchcands;
863 
864  /* store each variable in hashmap and initialize array entries */
865  for( j = 0; j < nbranchcands; ++j )
866  {
867  SCIP_CALL( SCIPhashmapInsert(branchruledata->varhashmap, branchcands[j], (void*) (size_t)j) );
868  branchruledata->nvarprobings[j] = 0;
869  branchruledata->nvarbranchings[j] = 0;
870  }
871  }
872  else /* possibly new variables need to be added */
873  {
874 
875  /* if var is not in hashmap, insert it */
876  for( j = 0; j < nbranchcands; ++j )
877  {
878  SCIP_VAR* var;
879  int nvars;
880 
881  var = branchcands[j];
882  assert(var != NULL);
883  nvars = branchruledata->nvars;
884 
885  /* if variable is not in hashmap insert it and increase array sizes */
886  if( !SCIPhashmapExists(branchruledata->varhashmap, var) )
887  {
888  SCIP_CALL( SCIPhashmapInsert(branchruledata->varhashmap, var, (void*) (size_t)nvars) );
889  SCIP_CALL( SCIPreallocMemoryArray(scip, &branchruledata->nvarprobings, (size_t)nvars + 1) );
890  SCIP_CALL( SCIPreallocMemoryArray(scip, &branchruledata->nvarbranchings, (size_t)nvars + 1) );
891 
892  branchruledata->nvarprobings[nvars] = 0;
893  branchruledata->nvarbranchings[nvars] = 0;
894 
895  assert(SCIPhashmapExists(branchruledata->varhashmap, var)
896  && (int)(size_t) SCIPhashmapGetImage(branchruledata->varhashmap, var) == nvars); /*lint !e507*/
897 
898  ++(branchruledata->nvars);
899  }
900 
901  }
902  }
903 
904  return SCIP_OKAY;
905 }
906 
908 static
909 SCIP_RETCODE incNVarBranchings(
910  SCIP* scip,
911  SCIP_BRANCHRULE* branchrule,
912  SCIP_VAR* var
913  )
914 {
915  SCIP_BRANCHRULEDATA* branchruledata;
916  int pos;
917 
918  assert(scip != NULL);
919  assert(branchrule != NULL);
920  assert(var != NULL);
921 
922  /* get branching rule data */
923  branchruledata = SCIPbranchruleGetData(branchrule);
924  assert(branchruledata != NULL);
925 
926  assert(SCIPhashmapExists(branchruledata->varhashmap, var) );
927 
928  pos = (int)(size_t) SCIPhashmapGetImage(branchruledata->varhashmap, var); /*lint !e507*/
929  (branchruledata->nvarbranchings[pos])++;
930 
931  (branchruledata->nbranchings)++;
932 
933  return SCIP_OKAY;
934 }
935 
937 static
938 SCIP_RETCODE incNVarProbings(
939  SCIP* scip,
940  SCIP_BRANCHRULE* branchrule,
941  SCIP_VAR* var
942  )
943 {
944  SCIP_BRANCHRULEDATA* branchruledata;
945  int pos;
946 
947  assert(scip != NULL);
948  assert(branchrule != NULL);
949  assert(var != NULL);
950 
951  /* get branching rule data */
952  branchruledata = SCIPbranchruleGetData(branchrule);
953  assert(branchruledata != NULL);
954 
955  assert(SCIPhashmapExists(branchruledata->varhashmap, var) );
956 
957  pos = (int)(size_t) SCIPhashmapGetImage(branchruledata->varhashmap, var); /*lint !e507*/
958  (branchruledata->nvarprobings[pos])++;
959 
960  (branchruledata->nprobings)++;
961 
962  return SCIP_OKAY;
963 }
964 
965 
967 static
968 SCIP_RETCODE execRelpsprob(
969  SCIP* scip,
970  SCIP_BRANCHRULE* branchrule,
971  SCIP_VAR** branchcands,
972  SCIP_Real* branchcandssol,
973  int nbranchcands,
974  int nvars,
975  SCIP_RESULT* result,
976  SCIP_VAR** branchvar
977  )
978 {
979  SCIP* masterscip;
980  SCIP_BRANCHRULEDATA* branchruledata;
981  BDCHGDATA* bdchgdata;
982  SCIP_Real lpobjval;
983 #ifndef NDEBUG
984  SCIP_Real cutoffbound;
985 #endif
986  SCIP_Real provedbound;
987 #ifdef SCIP_DEBUG
988  SCIP_Bool bestisstrongbranch = FALSE;
989 #endif
990  int bestcand = -1;
991 
992  *result = SCIP_DIDNOTRUN;
993 
994  SCIPdebugMessage("execrelpsprob method called\n relpsprob\n relpsprob\n relpsprob\n relpsprob\n relpsprob\n relpsprob\n relpsprob\n relpsprob\n");
995 
996  /* get SCIP pointer of master problem */
997  masterscip = GCGgetMasterprob(scip);
998  assert(masterscip != NULL);
999 
1000  /* get branching rule data */
1001  branchruledata = SCIPbranchruleGetData(branchrule);
1002  assert(branchruledata != NULL);
1003 
1004  /* add all branching candidates into branchruledata if not yet inserted */
1005  SCIP_CALL( addBranchcandsToData(scip, branchrule, branchcands, nbranchcands) );
1006 
1007  bdchgdata = NULL;
1008  /* create data structure for bound change infos */
1009  SCIP_CALL( createBdchgData(scip, &bdchgdata, branchcands, nvars) );
1010  assert(bdchgdata != NULL);
1011 
1012  /* get current LP objective bound of the local sub problem and global cutoff bound */
1013  lpobjval = SCIPgetLocalLowerbound(scip);
1014 #ifndef NDEBUG
1015  cutoffbound = SCIPgetCutoffbound(scip);
1016 #endif
1017  provedbound = lpobjval;
1018 
1019  if( nbranchcands == 1 )
1020  {
1021  /* only one candidate: nothing has to be done */
1022  bestcand = 0;
1023  }
1024  else
1025  {
1026  SCIP_Real* initcandscores;
1027  int* initcands;
1028  int maxninitcands;
1029  int nbdchgs;
1030  SCIP_Real avgconflictscore;
1031  SCIP_Real avgconflengthscore;
1032  SCIP_Real avginferencescore;
1033  SCIP_Real avgcutoffscore;
1034  SCIP_Real avgpscostscore;
1035  SCIP_Real bestpsscore;
1036  SCIP_Real bestsbscore;
1037  SCIP_Real bestuninitsbscore;
1038  SCIP_Real bestsbfracscore;
1039  SCIP_Real bestsbdomainscore;
1040  int ninfprobings;
1041  int maxbdchgs;
1042  int bestpscand;
1043  int bestsbcand;
1044  int i;
1045  int j;
1046  int c;
1047  int ninitcands = 0;
1048 
1049  /* get average conflict, inference, and pseudocost scores */
1050  avgconflictscore = SCIPgetAvgConflictScore(scip);
1051  avgconflictscore = MAX(avgconflictscore, 0.1);
1052  avgconflengthscore = SCIPgetAvgConflictlengthScore(scip);
1053  avgconflengthscore = MAX(avgconflengthscore, 0.1);
1054  avginferencescore = SCIPgetAvgInferenceScore(scip);
1055  avginferencescore = MAX(avginferencescore, 0.1);
1056  avgcutoffscore = SCIPgetAvgCutoffScore(scip);
1057  avgcutoffscore = MAX(avgcutoffscore, 0.1);
1058  avgpscostscore = SCIPgetAvgPseudocostScore(scip);
1059  avgpscostscore = MAX(avgpscostscore, 0.1);
1060 
1061  /* get maximal number of candidates to initialize with strong branching; if the current solutions is not basic,
1062  * we cannot apply the simplex algorithm and therefore don't initialize any candidates
1063  */
1064  maxninitcands = MIN(nbranchcands, branchruledata->initcand);
1065 
1066  if( !SCIPisLPSolBasic(masterscip) )
1067  {
1068  maxninitcands = 0;
1069  SCIPdebugMessage("solution is not basic\n");
1070  }
1071 
1072  SCIPdebugMessage("maxninitcands = %d\n", maxninitcands);
1073 
1074  /* get buffer for storing the unreliable candidates */
1075  SCIP_CALL( SCIPallocBufferArray(scip, &initcands, maxninitcands+1) ); /* allocate one additional slot for convenience */
1076  SCIP_CALL( SCIPallocBufferArray(scip, &initcandscores, maxninitcands+1) );
1077 
1078  /* initialize bound change arrays */
1079  nbdchgs = 0;
1080  maxbdchgs = branchruledata->maxbdchgs;
1081 
1082  ninfprobings = 0;
1083 
1084 
1085  /* search for the best pseudo cost candidate, while remembering unreliable candidates in a sorted buffer */
1086  bestpscand = -1;
1087  bestpsscore = -SCIPinfinity(scip);
1088  for( c = 0; c < nbranchcands; ++c )
1089  {
1090  SCIP_Real conflictscore;
1091  SCIP_Real conflengthscore;
1092  SCIP_Real inferencescore;
1093  SCIP_Real cutoffscore;
1094  SCIP_Real pscostscore;
1095  SCIP_Real score;
1096 
1097  assert(branchcands[c] != NULL);
1098 
1099  /* get conflict, inference, cutoff, and pseudo cost scores for candidate */
1100  conflictscore = SCIPgetVarConflictScore(scip, branchcands[c]);
1101  conflengthscore = SCIPgetVarConflictlengthScore(scip, branchcands[c]);
1102  inferencescore = SCIPgetVarAvgInferenceScore(scip, branchcands[c]);
1103  cutoffscore = SCIPgetVarAvgCutoffScore(scip, branchcands[c]);
1104  pscostscore = SCIPgetVarPseudocostScore(scip, branchcands[c], branchcandssol[c]);
1105 
1106 
1107  /* combine the four score values */
1108  score = calcScore(scip, branchruledata, conflictscore, avgconflictscore, conflengthscore, avgconflengthscore,
1109  inferencescore, avginferencescore, cutoffscore, avgcutoffscore, pscostscore, avgpscostscore,
1110  branchcandssol[c] - SCIPfloor(scip, branchcandssol[c]));
1111 
1112  /* pseudo cost of variable is not reliable: insert candidate in initcands buffer */
1113  for( j = ninitcands; j > 0 && score > initcandscores[j-1]; --j )
1114  {
1115  initcands[j] = initcands[j-1];
1116  initcandscores[j] = initcandscores[j-1];
1117  }
1118 
1119  initcands[j] = c;
1120  initcandscores[j] = score;
1121  ninitcands++;
1122  ninitcands = MIN(ninitcands, maxninitcands);
1123  }
1124 
1125  /* initialize unreliable candidates with probing,
1126  * search best strong branching candidate
1127  */
1128  SCIPdebugMessage("ninitcands = %d\n", ninitcands);
1129 
1130  bestsbcand = -1;
1131  bestsbscore = -SCIPinfinity(scip);
1132  bestsbfracscore = -SCIPinfinity(scip);
1133  bestsbdomainscore = -SCIPinfinity(scip);
1134  for( i = 0; i < ninitcands; ++i )
1135  {
1136  SCIP_Real down;
1137  SCIP_Real up;
1138  SCIP_Real downgain;
1139  SCIP_Real upgain;
1140  SCIP_Bool downvalid;
1141  SCIP_Bool upvalid;
1142  SCIP_Bool lperror;
1143  SCIP_Bool downinf;
1144  SCIP_Bool upinf;
1145 
1146  lperror = FALSE;
1147  up = 0.;
1148  down = 0.;
1149 
1150  /* get candidate number to initialize */
1151  c = initcands[i];
1152 
1153  SCIPdebugMessage("init pseudo cost (%g/%g) of <%s> with bounds [%g,%g] at %g (score:%g)\n",
1154  SCIPgetVarPseudocostCountCurrentRun(scip, branchcands[c], SCIP_BRANCHDIR_DOWNWARDS),
1155  SCIPgetVarPseudocostCountCurrentRun(scip, branchcands[c], SCIP_BRANCHDIR_UPWARDS),
1156  SCIPvarGetName(branchcands[c]), SCIPvarGetLbLocal(branchcands[c]), SCIPvarGetUbLocal(branchcands[c]),
1157  branchcandssol[c], initcandscores[i]);
1158 
1159  /* try branching on this variable (propagation + lp solving (pricing) ) */
1160  SCIP_CALL( getVarProbingbranch(scip, branchcands[c], bdchgdata, branchruledata->uselp, &branchruledata->nlpiterations,
1161  &down, &up, &downvalid, &upvalid, &downinf, &upinf, &lperror, &nbdchgs) );
1162 
1163  branchruledata->nprobingnodes++;
1164  branchruledata->nprobingnodes++;
1165  SCIP_CALL( incNVarProbings(scip, branchrule, branchcands[c]) );
1166 
1167  /* check for an error in strong branching */
1168  if( lperror )
1169  {
1170  if( !SCIPisStopped(scip) )
1171  {
1172  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
1173  "(node %"SCIP_LONGINT_FORMAT") error in strong branching call for variable <%s> with solution %g\n",
1174  SCIPgetNNodes(scip), SCIPvarGetName(branchcands[c]), branchcandssol[c]);
1175  }
1176  break;
1177  }
1178 
1179 
1180  if( SCIPisStopped(scip) )
1181  {
1182  break;
1183  }
1184 
1185  /* check if there are infeasible roundings */
1186  if( downinf && upinf )
1187  {
1188  /* both roundings are infeasible -> node is infeasible */
1189  SCIPdebugMessage(" -> variable <%s> is infeasible in both directions\n",
1190  SCIPvarGetName(branchcands[c]));
1191 
1192  *result = SCIP_CUTOFF;
1193  break; /* terminate initialization loop, because node is infeasible */
1194  }
1195 
1196 
1197  /* evaluate strong branching */
1198  down = MAX(down, lpobjval);
1199  up = MAX(up, lpobjval);
1200  downgain = down - lpobjval;
1201  upgain = up - lpobjval;
1202  assert(!downvalid || downinf == SCIPisGE(scip, down, cutoffbound));
1203  assert(!upvalid || upinf == SCIPisGE(scip, up, cutoffbound));
1204 
1205  /* the minimal lower bound of both children is a proved lower bound of the current subtree */
1206  if( downvalid && upvalid )
1207  {
1208  SCIP_Real minbound;
1209 
1210  minbound = MIN(down, up);
1211  provedbound = MAX(provedbound, minbound);
1212  }
1213 
1214 
1215  /* terminate initialization loop, if enough roundings are performed */
1216  if( maxbdchgs >= 0 && nbdchgs >= maxbdchgs )
1217  break;
1218 
1219  /* case one rounding is infeasible is regarded in method SCIPgetVarProbingbranch */
1220  if( downinf || upinf )
1221  {
1222  branchruledata->ninfprobings++;
1223  ninfprobings++;
1224  }
1225 
1226  /* if both roundings are valid, update scores */
1227  if( !downinf && !upinf )
1228  {
1229  SCIP_Real frac;
1230  SCIP_Real conflictscore;
1231  SCIP_Real conflengthscore;
1232  SCIP_Real inferencescore;
1233  SCIP_Real cutoffscore;
1234  SCIP_Real pscostscore;
1235  SCIP_Real score;
1236 
1237  frac = branchcandssol[c] - SCIPfloor(scip, branchcandssol[c]);
1238 
1239  /* check for a better score */
1240  conflictscore = SCIPgetVarConflictScore(scip, branchcands[c]);
1241  conflengthscore = SCIPgetVarConflictlengthScore(scip, branchcands[c]);
1242  inferencescore = SCIPgetVarAvgInferenceScore(scip, branchcands[c]);
1243  cutoffscore = SCIPgetVarAvgCutoffScore(scip, branchcands[c]);
1244  pscostscore = SCIPgetBranchScore(scip, branchcands[c], downgain, upgain);
1245  score = calcScore(scip, branchruledata, conflictscore, avgconflictscore, conflengthscore, avgconflengthscore,
1246  inferencescore, avginferencescore, cutoffscore, avgcutoffscore, pscostscore, avgpscostscore, frac);
1247 
1248  if( SCIPisSumGE(scip, score, bestsbscore) )
1249  {
1250  SCIP_Real fracscore;
1251  SCIP_Real domainscore;
1252 
1253  fracscore = MIN(frac, 1.0 - frac);
1254  domainscore = -(SCIPvarGetUbLocal(branchcands[c]) - SCIPvarGetLbLocal(branchcands[c]));
1255  if( SCIPisSumGT(scip, score, bestsbscore )
1256  || SCIPisSumGT(scip, fracscore, bestsbfracscore)
1257  || (SCIPisSumGE(scip, fracscore, bestsbfracscore) && domainscore > bestsbdomainscore) )
1258  {
1259  bestsbcand = c;
1260  bestsbscore = score;
1261  bestsbfracscore = fracscore;
1262  bestsbdomainscore = domainscore;
1263  }
1264  }
1265 
1266  /* update pseudo cost values */
1267  assert(!SCIPisFeasNegative(scip, frac));
1268  SCIP_CALL( SCIPupdateVarPseudocost(scip, branchcands[c], 0.0-frac, downgain, 1.0) );
1269  SCIP_CALL( SCIPupdateVarPseudocost(scip, branchcands[c], 1.0-frac, upgain, 1.0) );
1270 
1271  SCIPdebugMessage(" -> variable <%s> (solval=%g, down=%g (%+g), up=%g (%+g), score=%g/ %g/%g %g/%g -> %g)\n",
1272  SCIPvarGetName(branchcands[c]), branchcandssol[c], down, downgain, up, upgain,
1273  pscostscore, conflictscore, conflengthscore, inferencescore, cutoffscore, score);
1274 
1275  }
1276  }
1277 #ifdef SCIP_DEBUG
1278  if( bestsbcand >= 0 )
1279  {
1280  SCIPdebugMessage(" -> best: <%s> (%g / %g / %g)\n",
1281  SCIPvarGetName(branchcands[bestsbcand]), bestsbscore, bestsbfracscore, bestsbdomainscore);
1282  }
1283 #endif
1284  if( bestsbcand >= 0 )
1285  {
1286  SCIPdebugMessage(" -> best: <%s> (%g / %g / %g)\n",
1287  SCIPvarGetName(branchcands[bestsbcand]), bestsbscore, bestsbfracscore, bestsbdomainscore);
1288  }
1289 
1290  /* get the score of the best uninitialized strong branching candidate */
1291  if( i < ninitcands )
1292  bestuninitsbscore = initcandscores[i];
1293  else
1294  bestuninitsbscore = -SCIPinfinity(scip);
1295 
1296  /* if the best pseudo cost candidate is better than the best uninitialized strong branching candidate,
1297  * compare it to the best initialized strong branching candidate
1298  */
1299  if( bestpsscore > bestuninitsbscore && SCIPisSumGT(scip, bestpsscore, bestsbscore) )
1300  {
1301  bestcand = bestpscand;
1302 #ifdef SCIP_DEBUG
1303  bestisstrongbranch = FALSE;
1304 #endif
1305  }
1306  else if( bestsbcand >= 0 )
1307  {
1308  bestcand = bestsbcand;
1309 #ifdef SCIP_DEBUG
1310  bestisstrongbranch = TRUE;
1311 #endif
1312  }
1313  else
1314  {
1315  /* no candidate was initialized, and the best score is the one of the first candidate in the initialization
1316  * queue
1317  */
1318  assert(ninitcands >= 1);
1319  bestcand = initcands[0];
1320 #ifdef SCIP_DEBUG
1321  bestisstrongbranch = FALSE;
1322 #endif
1323  }
1324 
1325  /* apply domain reductions */
1326  if( (nbdchgs >= branchruledata->minbdchgs || ninfprobings >= 5 )
1327  && *result != SCIP_CUTOFF && !SCIPisStopped(scip) )
1328  {
1329  SCIP_CALL( applyBdchgs(scip, bdchgdata, SCIPgetCurrentNode(scip)) );
1330  branchruledata->nresolvesminbdchgs++;
1331  *result = SCIP_REDUCEDDOM; /* why was this commented out?? */
1332  }
1333 
1334  /* free buffer for the unreliable candidates */
1335  SCIPfreeBufferArray(scip, &initcandscores);
1336  SCIPfreeBufferArray(scip, &initcands);
1337  }
1338 
1339  /* if no domain could be reduced, create the branching */
1340  if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM
1341  && *result != SCIP_CONSADDED && !SCIPisStopped(scip) )
1342  {
1343  assert(*result == SCIP_DIDNOTRUN);
1344  assert(0 <= bestcand && bestcand < nbranchcands);
1345  assert(SCIPisLT(scip, provedbound, cutoffbound));
1346 
1347 #ifdef SCIP_DEBUG
1348  SCIPdebugMessage(" -> best: <%s> (strongbranch = %ud)\n", SCIPvarGetName(branchcands[bestcand]), bestisstrongbranch);
1349 #endif
1350  *branchvar = branchcands[bestcand];
1351  SCIP_CALL( incNVarBranchings(scip, branchrule, *branchvar) );
1352  }
1353 
1354  /* free data structure for bound change infos */
1355  SCIP_CALL( freeBdchgData(scip, bdchgdata) );
1356 
1357  return SCIP_OKAY;
1358 }
1359 
1360 
1361 /*
1362  * Callback methods
1363  */
1364 
1366 static
1367 SCIP_DECL_BRANCHFREE(branchFreeRelpsprob)
1368 { /*lint --e{715}*/
1369  SCIP_BRANCHRULEDATA* branchruledata;
1370 
1371  /* free branching rule data */
1372  branchruledata = SCIPbranchruleGetData(branchrule);
1373 
1374  SCIPdebugMessage("**needed in total %d probing nodes\n", branchruledata->nprobingnodes);
1375 
1376  SCIPfreeMemory(scip, &branchruledata);
1377  SCIPbranchruleSetData(branchrule, NULL);
1378 
1379  return SCIP_OKAY;
1380 }
1381 
1382 
1384 static
1385 SCIP_DECL_BRANCHINITSOL(branchInitsolRelpsprob)
1386 { /*lint --e{715}*/
1387  SCIP_BRANCHRULEDATA* branchruledata;
1388 
1389  /* free branching rule data */
1390  branchruledata = SCIPbranchruleGetData(branchrule);
1391 
1392  branchruledata->nprobingnodes = 0;
1393  branchruledata->nlpiterations = 0;
1394 
1395  branchruledata->nprobings = 0;
1396  branchruledata->nbranchings = 0;
1397  branchruledata->ninfprobings = 0;
1398  branchruledata->nresolvesminbdchgs = 0;
1399  branchruledata->nresolvesinfcands = 0;
1400 
1401  branchruledata->varhashmap = NULL;
1402  branchruledata->nvarbranchings = NULL;
1403  branchruledata->nvarprobings = NULL;
1404  branchruledata->nvars = 0;
1405 
1406  return SCIP_OKAY;
1407 }
1408 
1410 static
1411 SCIP_DECL_BRANCHEXITSOL(branchExitsolRelpsprob)
1412 { /*lint --e{715}*/
1413  SCIP_BRANCHRULEDATA* branchruledata;
1414 
1415  /* free branching rule data */
1416  branchruledata = SCIPbranchruleGetData(branchrule);
1417 
1418  SCIPdebugMessage("**in total: nprobings = %d; part of it are ninfprobings = %d\n",
1419  branchruledata->nprobings, branchruledata->ninfprobings );
1420 
1421  SCIPdebugMessage("**nbranchings = %d, nresolvesinfcands = %d, nresolvesminbdchgs = %d\n",
1422  branchruledata->nbranchings, branchruledata->nresolvesinfcands, branchruledata->nresolvesminbdchgs );
1423 
1424 
1425  /* free arrays for variables & hashmap */
1426  SCIPfreeMemoryArrayNull(scip, &branchruledata->nvarprobings);
1427  SCIPfreeMemoryArrayNull(scip, &branchruledata->nvarbranchings);
1428  branchruledata->nvars = 0;
1429 
1430  if( branchruledata->varhashmap != NULL )
1431  {
1432  SCIPhashmapFree(&(branchruledata->varhashmap));
1433  }
1434 
1435  return SCIP_OKAY;
1436 }
1437 
1438 
1439 /*
1440  * branching specific interface methods
1441  */
1442 
1445  SCIP* scip
1446  )
1447 {
1448  SCIP* origscip;
1449  SCIP_BRANCHRULE* branchrule;
1450  SCIP_BRANCHRULEDATA* branchruledata;
1451 
1452  /* get original problem */
1453  origscip = GCGmasterGetOrigprob(scip);
1454  assert(origscip != NULL);
1455 
1456  /* create relpsprob branching rule data */
1457  SCIP_CALL( SCIPallocMemory(scip, &branchruledata) );
1458 
1459  /* include branching rule */
1460  SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
1461  BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
1462  assert(branchrule != NULL);
1463 
1464  /* set non fundamental callbacks via setter functions */
1465  SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeRelpsprob) );
1466  SCIP_CALL( SCIPsetBranchruleInitsol(scip, branchrule, branchInitsolRelpsprob) );
1467  SCIP_CALL( SCIPsetBranchruleExitsol(scip, branchrule, branchExitsolRelpsprob) );
1468 
1469  /* relpsprob branching rule parameters */
1470  SCIP_CALL( SCIPaddRealParam(origscip,
1471  "branching/relpsprob/conflictweight",
1472  "weight in score calculations for conflict score",
1473  &branchruledata->conflictweight, TRUE, DEFAULT_CONFLICTWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
1474  SCIP_CALL( SCIPaddRealParam(origscip,
1475  "branching/relpsprob/conflictlengthweight",
1476  "weight in score calculations for conflict length score",
1477  &branchruledata->conflengthweight, TRUE, DEFAULT_CONFLENGTHWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
1478  SCIP_CALL( SCIPaddRealParam(origscip,
1479  "branching/relpsprob/inferenceweight",
1480  "weight in score calculations for inference score",
1481  &branchruledata->inferenceweight, TRUE, DEFAULT_INFERENCEWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
1482  SCIP_CALL( SCIPaddRealParam(origscip,
1483  "branching/relpsprob/cutoffweight",
1484  "weight in score calculations for cutoff score",
1485  &branchruledata->cutoffweight, TRUE, DEFAULT_CUTOFFWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
1486  SCIP_CALL( SCIPaddRealParam(origscip,
1487  "branching/relpsprob/pscostweight",
1488  "weight in score calculations for pseudo cost score",
1489  &branchruledata->pscostweight, TRUE, DEFAULT_PSCOSTWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
1490  SCIP_CALL( SCIPaddRealParam(origscip,
1491  "branching/relpsprob/minreliable",
1492  "minimal value for minimum pseudo cost size to regard pseudo cost value as reliable",
1493  &branchruledata->minreliable, TRUE, DEFAULT_MINRELIABLE, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1494  SCIP_CALL( SCIPaddRealParam(origscip,
1495  "branching/relpsprob/maxreliable",
1496  "maximal value for minimum pseudo cost size to regard pseudo cost value as reliable",
1497  &branchruledata->maxreliable, TRUE, DEFAULT_MAXRELIABLE, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1498  SCIP_CALL( SCIPaddRealParam(origscip,
1499  "branching/relpsprob/iterquot",
1500  "maximal fraction of branching LP iterations compared to node relaxation LP iterations",
1501  &branchruledata->iterquot, FALSE, DEFAULT_ITERQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1502  SCIP_CALL( SCIPaddIntParam(origscip,
1503  "branching/relpsprob/iterofs",
1504  "additional number of allowed LP iterations",
1505  &branchruledata->iterofs, FALSE, DEFAULT_ITEROFS, 0, INT_MAX, NULL, NULL) );
1506  SCIP_CALL( SCIPaddIntParam(origscip,
1507  "branching/relpsprob/maxlookahead",
1508  "maximal number of further variables evaluated without better score",
1509  &branchruledata->maxlookahead, TRUE, DEFAULT_MAXLOOKAHEAD, 1, INT_MAX, NULL, NULL) );
1510  SCIP_CALL( SCIPaddIntParam(origscip,
1511  "branching/relpsprob/initcand",
1512  "maximal number of candidates initialized with strong branching per node",
1513  &branchruledata->initcand, FALSE, DEFAULT_INITCAND, 0, INT_MAX, NULL, NULL) );
1514  SCIP_CALL( SCIPaddIntParam(origscip,
1515  "branching/relpsprob/maxbdchgs",
1516  "maximal number of bound tightenings before the node is immediately reevaluated (-1: unlimited)",
1517  &branchruledata->maxbdchgs, TRUE, DEFAULT_MAXBDCHGS, -1, INT_MAX, NULL, NULL) );
1518  SCIP_CALL( SCIPaddIntParam(origscip,
1519  "branching/relpsprob/minbdchgs",
1520  "minimal number of bound tightenings before bound changes are applied",
1521  &branchruledata->minbdchgs, TRUE, DEFAULT_MINBDCHGS, 1, INT_MAX, NULL, NULL) );
1522  SCIP_CALL( SCIPaddBoolParam(origscip,
1523  "branching/relpsprob/uselp",
1524  "shall the LP be solved during probing? (TRUE)",
1525  &branchruledata->uselp, FALSE, DEFAULT_USELP, NULL, NULL) );
1526  SCIP_CALL( SCIPaddRealParam(origscip,
1527  "branching/relpsprob/reliability",
1528  "reliability value for probing",
1529  &branchruledata->reliability, FALSE, DEFAULT_RELIABILITY, 0.0, 1.0, NULL, NULL) );
1530 
1531  /* notify cons_integralorig about the original variable branching rule */
1532  SCIP_CALL( GCGconsIntegralorigAddBranchrule(scip, branchrule) );
1533 
1534  return SCIP_OKAY;
1535 }
1536 
1539  SCIP* scip,
1540  SCIP_VAR** branchcands,
1541  SCIP_Real* branchcandssol,
1542  int nbranchcands,
1543  int nvars,
1544  SCIP_RESULT* result,
1545  SCIP_VAR** branchvar
1546  )
1547 {
1548  SCIP_BRANCHRULE* branchrule;
1549  SCIP* origscip;
1550 
1551  assert(scip != NULL);
1552  assert(result != NULL);
1553 
1554  /* find branching rule */
1555  branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME);
1556  assert(branchrule != NULL);
1557  origscip = GCGmasterGetOrigprob(scip);
1558  assert(origscip != NULL);
1559 
1560  /* execute branching rule */
1561  SCIP_CALL( execRelpsprob(origscip, branchrule, branchcands, branchcandssol, nbranchcands, nvars, result, branchvar) );
1562 
1563  return SCIP_OKAY;
1564 }
SCIP_RETCODE GCGconsIntegralorigAddBranchrule(SCIP *scip, SCIP_BRANCHRULE *branchrule)
#define DEFAULT_ITERQUOT
static SCIP_RETCODE getVarProbingbranch(SCIP *scip, SCIP_VAR *probingvar, BDCHGDATA *bdchgdata, SCIP_Bool solvelp, SCIP_Longint *nlpiterations, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, SCIP_Bool *downinf, SCIP_Bool *upinf, SCIP_Bool *lperror, int *nbdchgs)
#define DEFAULT_MAXRELIABLE
static SCIP_RETCODE incNVarProbings(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR *var)
SCIP_RETCODE SCIPincludeBranchruleRelpsprob(SCIP *scip)
#define BRANCHRULE_DESC
#define BRANCHRULE_NAME
GCG interface methods.
static SCIP_DECL_BRANCHEXITSOL(branchExitsolRelpsprob)
#define DEFAULT_MAXBDCHGS
static SCIP_RETCODE execRelpsprob(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, int nbranchcands, int nvars, SCIP_RESULT *result, SCIP_VAR **branchvar)
static SCIP_DECL_BRANCHFREE(branchFreeRelpsprob)
SCIP_Real * lbchgs
#define BRANCHRULE_MAXBOUNDDIST
#define BRANCHRULE_MAXDEPTH
#define DEFAULT_ITEROFS
SCIP * GCGgetMasterprob(SCIP *scip)
Definition: relax_gcg.c:3838
constraint handler for the integrality constraint
#define DEFAULT_CONFLENGTHWEIGHT
static SCIP_RETCODE addBdchg(SCIP *scip, BDCHGDATA *bdchgdata, SCIP_VAR *var, SCIP_Real newbound, SCIP_BOUNDTYPE boundtype, SCIP_Bool infrounding, int *nbdchgs, SCIP_Bool *infeasible)
static SCIP_RETCODE applyProbing(SCIP *scip, SCIP_VAR **vars, int nvars, SCIP_VAR *probingvar, SCIP_Bool probingdir, SCIP_Bool solvelp, SCIP_Longint *nlpiterations, SCIP_Real *proplbs, SCIP_Real *propubs, SCIP_Real *lpobjvalue, SCIP_Bool *lpsolved, SCIP_Bool *lperror, SCIP_Bool *cutoff)
#define DEFAULT_MINRELIABLE
#define HASHSIZE_VARS
#define DEFAULT_CUTOFFWEIGHT
static SCIP_Real calcScore(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_Real conflictscore, SCIP_Real avgconflictscore, SCIP_Real conflengthscore, SCIP_Real avgconflengthscore, SCIP_Real inferencescore, SCIP_Real avginferencescore, SCIP_Real cutoffscore, SCIP_Real avgcutoffscore, SCIP_Real pscostscore, SCIP_Real avgpscostscore, SCIP_Real frac)
SCIP_RETCODE GCGrelaxPerformProbingWithPricing(SCIP *scip, int maxpricerounds, SCIP_Longint *nlpiterations, int *npricerounds, SCIP_Real *lpobjvalue, SCIP_Bool *lpsolved, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: relax_gcg.c:4492
#define DEFAULT_RELIABILITY
static SCIP_RETCODE calculateBounds(SCIP *scip, SCIP_VAR *branchvar, SCIP_Real *downlb, SCIP_Real *downub, SCIP_Real *uplb, SCIP_Real *upub)
static SCIP_RETCODE createBdchgData(SCIP *scip, BDCHGDATA **bdchgdata, SCIP_VAR **vars, int nvars)
GCG relaxator.
GCG variable pricer.
static SCIP_DECL_BRANCHINITSOL(branchInitsolRelpsprob)
#define DEFAULT_USELP
static SCIP_RETCODE addBranchcandsToData(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR **branchcands, int nbranchcands)
SCIP * GCGmasterGetOrigprob(SCIP *scip)
SCIP_RETCODE GCGrelaxStartProbing(SCIP *scip, SCIP_HEUR *probingheur)
Definition: relax_gcg.c:4174
#define DEFAULT_CONFLICTWEIGHT
SCIP_RETCODE GCGrelaxNewProbingnodeOrig(SCIP *scip)
Definition: relax_gcg.c:4241
SCIP_Bool * infroundings
#define DEFAULT_PSCOSTWEIGHT
SCIP_HASHMAP * varhashmap
SCIP_HASHMAP * varhashmap
#define BRANCHRULE_PRIORITY
#define DEFAULT_INFERENCEWEIGHT
reliable pseudo costs branching rule
static SCIP_RETCODE freeBdchgData(SCIP *scip, BDCHGDATA *bdchgdata)
SCIP_Longint nlpiterations
#define DEFAULT_MINBDCHGS
SCIP_RETCODE SCIPgetRelpsprobBranchVar(SCIP *scip, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, int nbranchcands, int nvars, SCIP_RESULT *result, SCIP_VAR **branchvar)
static SCIP_RETCODE applyBdchgs(SCIP *scip, BDCHGDATA *bdchgdata, SCIP_NODE *node)
SCIP_Real * ubchgs
SCIP_RETCODE GCGrelaxEndProbing(SCIP *scip)
Definition: relax_gcg.c:4512
#define DEFAULT_INITCAND
static SCIP_RETCODE incNVarBranchings(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR *var)
SCIP_RETCODE GCGrelaxNewProbingnodeMaster(SCIP *scip)
Definition: relax_gcg.c:4288
#define DEFAULT_MAXLOOKAHEAD