Scippy

SCIP

Solving Constraint Integer Programs

heuristics.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-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heuristics.c
17  * @brief methods commonly used by primal heuristics
18  * @author Gregor Hendel
19  */
20 
21 #include "scip/heuristics.h"
22 #include "scip/cons_linear.h"
23 #include "scip/scipdefplugins.h"
24 
25 #include "pub_heur.h"
26 
27 /* the indicator and SOS1 constraint handlers are included for the diving algorithm SCIPperformGenericDivingAlgorithm() */
28 #include "scip/cons_indicator.h"
29 #include "scip/cons_sos1.h"
30 
31 #define MINLPITER 10000 /**< minimal number of LP iterations allowed in each LP solving call */
32 
33 
34 /** solve probing LP */
35 static
37  SCIP* scip, /**< SCIP data structure */
38  SCIP_DIVESET* diveset, /**< diving settings */
39  SCIP_Longint maxnlpiterations, /**< maximum number of allowed LP iterations */
40  SCIP_Bool* lperror, /**< pointer to store if an internal LP error occurred */
41  SCIP_Bool* cutoff /**< pointer to store whether the LP was infeasible */
42  )
43 {
44  int lpiterationlimit;
45  SCIP_RETCODE retstat;
46  SCIP_Longint nlpiterations;
47 
48  assert(lperror != NULL);
49  assert(cutoff != NULL);
50 
51  nlpiterations = SCIPgetNLPIterations(scip);
52 
53  /* allow at least MINLPITER more iterations */
54  lpiterationlimit = (int)(maxnlpiterations - SCIPdivesetGetNLPIterations(diveset));
55  lpiterationlimit = MAX(lpiterationlimit, MINLPITER);
56 
57  retstat = SCIPsolveProbingLP(scip, lpiterationlimit, lperror, cutoff);
58 
59  /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
60  * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
61  */
62 #ifdef NDEBUG
63  if( retstat != SCIP_OKAY )
64  {
65  SCIPwarningMessage(scip, "Error while solving LP in %s diving heuristic; LP solve terminated with code <%d>.\n", SCIPdivesetGetName(diveset), retstat);
66  }
67 #else
68  SCIP_CALL( retstat );
69 #endif
70 
71  /* update iteration count */
72  SCIPupdateDivesetLPStats(scip, diveset, SCIPgetNLPIterations(scip) - nlpiterations);
73 
74  return SCIP_OKAY;
75 }
76 
77 /** select the next variable and type of diving */
78 static
80  SCIP* scip, /**< SCIP data structure */
81  SCIP_DIVESET* diveset, /**< dive set */
82  SCIP_SOL* worksol, /**< current working solution */
83  SCIP_Bool onlylpbranchcands, /**< should only LP branching candidates be considered? */
84  SCIP_Bool storelpcandscores, /**< should the scores of the LP candidates be updated? */
85  SCIP_VAR** lpcands, /**< LP branching candidates, or NULL if not needed */
86  SCIP_Real * lpcandssol, /**< solution values LP branching candidates, or NULL if not needed */
87  SCIP_Real* lpcandsfrac, /**< fractionalities of LP branching candidates, or NULL if not needed*/
88  SCIP_Real* lpcandsscores, /**< array with LP branching candidate scores, or NULL */
89  SCIP_Bool* lpcandroundup, /**< array to remember whether the preferred branching direction is upwards */
90  int* nviollpcands, /**< pointer to store the number of LP candidates whose solution value already violates local bounds */
91  int nlpcands, /**< number of current LP cands */
92  SCIP_Bool* enfosuccess, /**< pointer to store whether a candidate was sucessfully found */
93  SCIP_Bool* infeasible /**< pointer to store whether the diving can be immediately aborted because it is infeasible */
94  )
95 {
96  assert(scip != NULL);
97  assert(worksol != NULL);
98  assert(!onlylpbranchcands || lpcandsscores != NULL);
99  assert(!onlylpbranchcands || lpcandroundup != NULL);
100  assert(enfosuccess != NULL);
101  assert(infeasible != NULL);
102  assert(nviollpcands != NULL);
103 
104  *nviollpcands = 0;
105  /* we use diving solution enforcement provided by the constraint handlers */
106  if( !onlylpbranchcands )
107  {
108  SCIP_CALL( SCIPgetDiveBoundChanges(scip, diveset, worksol, enfosuccess, infeasible) );
109  }
110  else
111  {
112  int c;
113  int bestcandidx;
114  SCIP_Real bestscore;
115  SCIP_Real score;
116 
117  bestscore = SCIP_REAL_MIN;
118  bestcandidx = -1;
119 
121 
122  /* search for the candidate that maximizes the dive set score function and whose solution value is still feasible */
123  for( c = 0; c < nlpcands; ++c )
124  {
125  assert(SCIPgetSolVal(scip, worksol, lpcands[c]) == lpcandssol[c]); /*lint !e777 doesn't like comparing floats for equality */
126 
127  /* scores are kept in arrays for faster reuse */
128  if( storelpcandscores )
129  {
130  SCIP_CALL( SCIPgetDivesetScore(scip, diveset, SCIP_DIVETYPE_INTEGRALITY, lpcands[c], lpcandssol[c],
131  lpcandsfrac[c], &lpcandsscores[c], &lpcandroundup[c]) );
132  }
133 
134  score = lpcandsscores[c];
135  /* update the best candidate if it has a higher score and a solution value which does not violate one of the local bounds */
136  if( SCIPisLE(scip, SCIPvarGetLbLocal(lpcands[c]), lpcandssol[c]) && SCIPisGE(scip, SCIPvarGetUbLocal(lpcands[c]), lpcandssol[c]) )
137  {
138  if( score > bestscore )
139  {
140  bestcandidx = c;
141  bestscore = score;
142  }
143  }
144  else
145  ++(*nviollpcands);
146  }
147 
148  /* there is no guarantee that a candidate is found since local bounds might render all solution values infeasible */
149  *enfosuccess = (bestcandidx >= 0);
150  if( *enfosuccess )
151  {
152  /* if we want to round up the best candidate, it is added as the preferred bound change */
153  SCIP_CALL( SCIPaddDiveBoundChange(scip, lpcands[bestcandidx], SCIP_BRANCHDIR_UPWARDS,
154  SCIPceil(scip, lpcandssol[bestcandidx]), lpcandroundup[bestcandidx]) );
155  SCIP_CALL( SCIPaddDiveBoundChange(scip, lpcands[bestcandidx], SCIP_BRANCHDIR_DOWNWARDS,
156  SCIPfloor(scip, lpcandssol[bestcandidx]), ! lpcandroundup[bestcandidx]) );
157  }
158  }
159  return SCIP_OKAY;
160 }
161 
162 
163 
164 /** performs a diving within the limits of the diveset parameters
165  *
166  * This method performs a diving according to the settings defined by the diving settings @p diveset; Contrary to the
167  * name, SCIP enters probing mode (not diving mode) and dives along a path into the tree. Domain propagation
168  * is applied at every node in the tree, whereas probing LPs might be solved less frequently.
169  *
170  * Starting from the current LP solution, the algorithm selects candidates which maximize the
171  * score defined by the @p diveset and whose solution value has not yet been rendered infeasible by propagation,
172  * and propagates the bound change on this candidate.
173  *
174  * The algorithm iteratively selects the the next (unfixed) candidate in the list, until either enough domain changes
175  * or the resolve frequency of the LP trigger an LP resolve (and hence, the set of potential candidates changes),
176  * or the last node is proven to be infeasible. It optionally backtracks and tries the
177  * other branching direction.
178  *
179  * After the set of remaining candidates is empty or the targeted depth is reached, the node LP is
180  * solved, and the old candidates are replaced by the new LP candidates.
181  *
182  * @see heur_guideddiving.c for an example implementation of a dive set controlling the diving algorithm.
183  *
184  * @note the node from where the algorithm is called is checked for a basic LP solution. If the solution
185  * is non-basic, e.g., when barrier without crossover is used, the method returns without performing a dive.
186  *
187  * @note currently, when multiple diving heuristics call this method and solve an LP at the same node, only the first
188  * call will be executed, @see SCIPgetLastDiveNode()
189  *
190  * @todo generalize method to work correctly with pseudo or external branching/diving candidates
191  */
193  SCIP* scip, /**< SCIP data structure */
194  SCIP_DIVESET* diveset, /**< settings for diving */
195  SCIP_SOL* worksol, /**< non-NULL working solution */
196  SCIP_HEUR* heur, /**< the calling primal heuristic */
197  SCIP_RESULT* result, /**< SCIP result pointer */
198  SCIP_Bool nodeinfeasible /**< is the current node known to be infeasible? */
199  )
200 {
201  SCIP_CONSHDLR* indconshdlr; /* constraint handler for indicator constraints */
202  SCIP_CONSHDLR* sos1conshdlr; /* constraint handler for SOS1 constraints */
203  SCIP_VAR** lpcands;
204  SCIP_Real* lpcandssol;
205 
206  SCIP_VAR** previouscands;
207  SCIP_Real* lpcandsscores;
208  SCIP_Real* previousvals;
209  SCIP_Real* lpcandsfrac;
210  SCIP_Bool* lpcandroundup;
211  SCIP_Real searchubbound;
212  SCIP_Real searchavgbound;
213  SCIP_Real searchbound;
214  SCIP_Real ubquot;
215  SCIP_Real avgquot;
216  SCIP_Longint ncalls;
217  SCIP_Longint oldsolsuccess;
218  SCIP_Longint nlpiterations;
219  SCIP_Longint maxnlpiterations;
220  SCIP_Longint domreds;
221  int startndivecands;
222  int depth;
223  int maxdepth;
224  int maxdivedepth;
225  int totalnbacktracks;
226  int totalnprobingnodes;
227  int lastlpdepth;
228  int previouscandssize;
229  int lpcandsscoressize;
230  int nviollpcands;
231  SCIP_Longint oldnsolsfound;
232  SCIP_Longint oldnbestsolsfound;
233 
234  SCIP_Bool success;
235  SCIP_Bool leafsol;
236  SCIP_Bool enfosuccess;
237  SCIP_Bool lperror;
238  SCIP_Bool cutoff;
239  SCIP_Bool backtracked;
240  SCIP_Bool backtrack;
241  SCIP_Bool onlylpbranchcands;
242 
243  int nlpcands;
244  int lpsolvefreq;
245 
246  assert(scip != NULL);
247  assert(heur != NULL);
248  assert(result != NULL);
249  assert(worksol != NULL);
250 
251  *result = SCIP_DELAYED;
252 
253  /* do not call heuristic in node that was already detected to be infeasible */
254  if( nodeinfeasible )
255  return SCIP_OKAY;
256 
257  /* only call heuristic, if an optimal LP solution is at hand */
259  return SCIP_OKAY;
260 
261  /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
262  if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) )
263  return SCIP_OKAY;
264 
265  /* only call heuristic, if the LP solution is basic (which allows fast resolve in diving) */
266  if( !SCIPisLPSolBasic(scip) )
267  return SCIP_OKAY;
268 
269  /* don't dive two times at the same node */
270  if( SCIPgetLastDivenode(scip) == SCIPgetNNodes(scip) && SCIPgetDepth(scip) > 0 )
271  return SCIP_OKAY;
272 
273  *result = SCIP_DIDNOTRUN;
274 
275  /* only try to dive, if we are in the correct part of the tree, given by minreldepth and maxreldepth */
276  depth = SCIPgetDepth(scip);
277  maxdepth = SCIPgetMaxDepth(scip);
278  maxdepth = MAX(maxdepth, 30);
279  if( depth < SCIPdivesetGetMinRelDepth(diveset) * maxdepth || depth > SCIPdivesetGetMaxRelDepth(diveset) * maxdepth )
280  return SCIP_OKAY;
281 
282  /* calculate the maximal number of LP iterations until heuristic is aborted */
283  nlpiterations = SCIPgetNNodeLPIterations(scip);
284  ncalls = SCIPdivesetGetNCalls(diveset);
285  oldsolsuccess = SCIPdivesetGetSolSuccess(diveset);
286 
287  /*todo another factor of 10, REALLY? */
288  maxnlpiterations = (SCIP_Longint)((1.0 + 10*(oldsolsuccess+1.0)/(ncalls+1.0)) * SCIPdivesetGetMaxLPIterQuot(diveset) * nlpiterations);
289  maxnlpiterations += SCIPdivesetGetMaxLPIterOffset(diveset);
290 
291  /* don't try to dive, if we took too many LP iterations during diving */
292  if( SCIPdivesetGetNLPIterations(diveset) >= maxnlpiterations )
293  return SCIP_OKAY;
294 
295  /* allow at least a certain number of LP iterations in this dive */
296  if( SCIPdivesetGetNLPIterations(diveset) + MINLPITER > maxnlpiterations )
297  maxnlpiterations = SCIPdivesetGetNLPIterations(diveset) + MINLPITER;
298 
299  /* these constraint handlers are required for polishing an LP relaxation solution beyond rounding */
300  indconshdlr = SCIPfindConshdlr(scip, "indicator");
301  sos1conshdlr = SCIPfindConshdlr(scip, "SOS1");
302 
303  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, &lpcandsfrac, &nlpcands, NULL, NULL) );
304 
305  onlylpbranchcands = SCIPdivesetUseOnlyLPBranchcands(diveset);
306  /* don't try to dive, if there are no diving candidates */
307  if( onlylpbranchcands && nlpcands == 0 )
308  return SCIP_OKAY;
309 
310  /* calculate the objective search bound */
311  if( SCIPgetNSolsFound(scip) == 0 )
312  {
313  ubquot = SCIPdivesetGetUbQuotNoSol(diveset);
314  avgquot = SCIPdivesetGetAvgQuotNoSol(diveset);
315  }
316  else
317  {
318  ubquot = SCIPdivesetGetUbQuot(diveset);
319  avgquot = SCIPdivesetGetAvgQuot(diveset);
320  }
321 
322  if( ubquot > 0.0 )
323  searchubbound = SCIPgetLowerbound(scip) + ubquot * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
324  else
325  searchubbound = SCIPinfinity(scip);
326 
327  if( avgquot > 0.0 )
328  searchavgbound = SCIPgetLowerbound(scip) + avgquot * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
329  else
330  searchavgbound = SCIPinfinity(scip);
331 
332  searchbound = MIN(searchubbound, searchavgbound);
333 
334  if( SCIPisObjIntegral(scip) )
335  searchbound = SCIPceil(scip, searchbound);
336 
337  /* calculate the maximal diving depth: 10 * min{number of integer variables, max depth} */
338  maxdivedepth = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
339  if ( sos1conshdlr != NULL )
340  maxdivedepth += SCIPgetNSOS1Vars(sos1conshdlr);
341  maxdivedepth = MIN(maxdivedepth, maxdepth);
342  maxdivedepth *= 10;
343 
344  *result = SCIP_DIDNOTFIND;
345 
346  /* start probing mode */
347  SCIP_CALL( SCIPstartProbing(scip) );
348 
349  /* enables collection of variable statistics during probing */
350  SCIPenableVarHistory(scip);
351 
352  SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") executing %s heuristic: depth=%d, %d fractionals, dualbound=%g, avgbound=%g, cutoffbound=%g, searchbound=%g\n",
353  SCIPgetNNodes(scip), SCIPheurGetName(heur), SCIPgetDepth(scip), nlpcands, SCIPgetDualbound(scip), SCIPgetAvgDualbound(scip),
354  SCIPretransformObj(scip, SCIPgetCutoffbound(scip)), SCIPretransformObj(scip, searchbound));
355 
356 
357  /* allocate buffer storage for previous candidates and their branching values for pseudo cost updates */
358  lpsolvefreq = SCIPdivesetGetLPSolveFreq(diveset);
359  previouscandssize = MAX(1, lpsolvefreq);
360  SCIP_CALL( SCIPallocBufferArray(scip, &previouscands, previouscandssize) );
361  SCIP_CALL( SCIPallocBufferArray(scip, &previousvals, previouscandssize) );
362 
363  /* keep some statistics */
364  lperror = FALSE;
365  cutoff = FALSE;
366  lastlpdepth = -1;
367  startndivecands = nlpcands;
368  totalnbacktracks = 0;
369  totalnprobingnodes = 0;
370  oldnsolsfound = SCIPgetNSolsFound(scip);
371  oldnbestsolsfound = SCIPgetNBestSolsFound(scip);
372 
373  /* link the working solution to the dive set */
374  SCIPdivesetSetWorkSolution(diveset, worksol);
375 
376  if( onlylpbranchcands )
377  {
378  SCIP_CALL( SCIPallocBufferArray(scip, &lpcandsscores, nlpcands) );
379  SCIP_CALL( SCIPallocBufferArray(scip, &lpcandroundup, nlpcands) );
380 
381  lpcandsscoressize = nlpcands;
382  }
383  else
384  {
385  lpcandroundup = NULL;
386  lpcandsscores = NULL;
387  lpcandsscoressize = 0;
388  }
389 
390  enfosuccess = TRUE;
391  leafsol = FALSE;
392 
393  /* LP loop; every time a new LP was solved, conditions are checked
394  * dive as long we are in the given objective, depth and iteration limits and fractional variables exist, but
395  * - if possible, we dive at least with the depth 10
396  * - if the number of fractional variables decreased at least with 1 variable per 2 dive depths, we continue diving
397  */
398  while( !lperror && !cutoff && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL && enfosuccess
399  && (SCIPgetProbingDepth(scip) < 10
400  || nlpcands <= startndivecands - SCIPgetProbingDepth(scip) / 2
401  || (SCIPgetProbingDepth(scip) < maxdivedepth && SCIPdivesetGetNLPIterations(diveset) < maxnlpiterations && SCIPgetLPObjval(scip) < searchbound))
402  && !SCIPisStopped(scip) )
403  {
404  SCIP_Real lastlpobjval;
405  int c;
406  SCIP_Bool allroundable;
407  SCIP_Bool infeasible;
408  int prevcandsinsertidx;
409 
410  /* remember the last LP depth */
411  assert(lastlpdepth < SCIPgetProbingDepth(scip));
412  lastlpdepth = SCIPgetProbingDepth(scip);
413  domreds = 0;
414 
415  SCIPdebugMsg(scip, "%s heuristic continues diving at depth %d, %d candidates left\n",
416  SCIPdivesetGetName(diveset), lastlpdepth, nlpcands);
417 
418 
419  /* loop over candidates and determine if they are roundable */
420  allroundable = TRUE;
421  c = 0;
422  while( allroundable && c < nlpcands )
423  {
424  if( SCIPvarMayRoundDown(lpcands[c]) || SCIPvarMayRoundUp(lpcands[c]) )
425  allroundable = TRUE;
426  else
427  allroundable = FALSE;
428  ++c;
429  }
430 
431  /* if all candidates are roundable, try to round the solution */
432  if( allroundable )
433  {
434  success = FALSE;
435 
436  /* working solution must be linked to LP solution */
437  SCIP_CALL( SCIPlinkLPSol(scip, worksol) );
438  /* create solution from diving LP and try to round it */
439  SCIP_CALL( SCIProundSol(scip, worksol, &success) );
440 
441  /* adjust SOS1 constraints */
442  if( success && sos1conshdlr != NULL )
443  {
444  SCIP_Bool changed;
445  SCIP_CALL( SCIPmakeSOS1sFeasible(scip, sos1conshdlr, worksol, &changed, &success) );
446  }
447 
448  /* succesfully rounded solutions are tried for primal feasibility */
449  if( success )
450  {
451  SCIP_Bool changed = FALSE;
452  SCIPdebugMsg(scip, "%s found roundable primal solution: obj=%g\n", SCIPdivesetGetName(diveset), SCIPgetSolOrigObj(scip, worksol));
453 
454  /* adjust indicator constraints */
455  if( indconshdlr != NULL )
456  {
457  SCIP_CALL( SCIPmakeIndicatorsFeasible(scip, indconshdlr, worksol, &changed) );
458  }
459 
460  success = FALSE;
461  /* try to add solution to SCIP */
462  SCIP_CALL( SCIPtrySol(scip, worksol, FALSE, FALSE, FALSE, FALSE, changed, &success) );
463 
464  /* check, if solution was feasible and good enough */
465  if( success )
466  {
467  SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
468  *result = SCIP_FOUNDSOL;
469  leafsol = (nlpcands == 0);
470 
471  /* the rounded solution found above led to a cutoff of the node LP solution */
473  {
474  cutoff = TRUE;
475  break;
476  }
477  }
478  }
479  }
480 
481  /* working solution must be linked to LP solution */
482  assert(SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL);
483  lastlpobjval = SCIPgetLPObjval(scip);
484  SCIP_CALL( SCIPlinkLPSol(scip, worksol) );
485 
486  /* in case we do not solve LP's at every probing node, we must explicitly store the solution values by unlinking the
487  * solution, otherwise, the working solution may contain wrong entries, if, e.g., a backtrack occurred after an
488  * intermediate LP resolve
489  */
490  if( lpsolvefreq != 1 )
491  {
492  SCIP_CALL( SCIPunlinkSol(scip, worksol) );
493  }
494 
495 
496  /* ensure array sizes for the diving on the fractional variables */
497  if( onlylpbranchcands && nlpcands > lpcandsscoressize )
498  {
499  assert(nlpcands > 0);
500  assert(lpcandsscores != NULL);
501  assert(lpcandroundup != NULL);
502 
503  SCIP_CALL( SCIPreallocBufferArray(scip, &lpcandsscores, nlpcands) );
504  SCIP_CALL( SCIPreallocBufferArray(scip, &lpcandroundup, nlpcands) );
505 
506  lpcandsscoressize = nlpcands;
507  }
508 
509 
510  enfosuccess = FALSE;
511  /* select the next diving action by selecting appropriate dive bound changes for the preferred and alternative child */
512  SCIP_CALL( selectNextDiving(scip, diveset, worksol, onlylpbranchcands, SCIPgetProbingDepth(scip) == lastlpdepth,
513  lpcands, lpcandssol, lpcandsfrac, lpcandsscores, lpcandroundup, &nviollpcands, nlpcands,
514  &enfosuccess, &infeasible) );
515 
516  /* if we did not succeed finding an enforcement, the solution is potentially feasible and we break immediately */
517  if( ! enfosuccess )
518  break;
519 
520  prevcandsinsertidx = -1;
521 
522  /* start propagating candidate variables
523  * - until the desired targetdepth is reached,
524  * - or there is no further candidate variable left because of intermediate bound changes,
525  * - or a cutoff is detected
526  */
527  do
528  {
529  SCIP_VAR* bdchgvar;
530  SCIP_Real bdchgvalue;
531  SCIP_Longint localdomreds;
532  SCIP_BRANCHDIR bdchgdir;
533  int nbdchanges;
534 
535  /* ensure that a new candidate was successfully determined (usually at the end of the previous loop iteration) */
536  assert(enfosuccess);
537  bdchgvar = NULL;
538  bdchgvalue = SCIP_INVALID;
539  bdchgdir = SCIP_BRANCHDIR_AUTO;
540 
541  backtracked = FALSE;
542  do
543  {
544  int d;
545  SCIP_VAR** bdchgvars;
546  SCIP_BRANCHDIR* bdchgdirs;
547  SCIP_Real* bdchgvals;
548 
549  nbdchanges = 0;
550  /* get the bound change information stored in the dive set */
551  SCIPgetDiveBoundChangeData(scip, &bdchgvars, &bdchgdirs, &bdchgvals, &nbdchanges, !backtracked);
552 
553  assert(nbdchanges > 0);
554  assert(bdchgvars != NULL);
555  assert(bdchgdirs != NULL);
556  assert(bdchgvals != NULL);
557 
558  /* return if we reached the depth limit */
559  if( SCIP_MAXTREEDEPTH <= SCIPgetDepth(scip) )
560  {
561  SCIPdebugMsg(scip, "depth limit reached, we stop diving immediately.\n");
562  goto TERMINATE;
563  }
564 
565  /* dive deeper into the tree */
566  SCIP_CALL( SCIPnewProbingNode(scip) );
567  ++totalnprobingnodes;
568 
569  /* apply all suggested domain changes of the variables */
570  for( d = 0; d < nbdchanges; ++d )
571  {
572  SCIP_Real lblocal;
573  SCIP_Real ublocal;
574  SCIP_Bool infeasbdchange;
575 
576  /* get the next bound change data: variable, direction, and value */
577  bdchgvar = bdchgvars[d];
578  bdchgvalue = bdchgvals[d];
579  bdchgdir = bdchgdirs[d];
580 
581  assert(bdchgvar != NULL);
582  lblocal = SCIPvarGetLbLocal(bdchgvar);
583  ublocal = SCIPvarGetUbLocal(bdchgvar);
584 
585 
586  SCIPdebugMsg(scip, " dive %d/%d, LP iter %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ": var <%s>, oldbounds=[%g,%g],",
587  SCIPgetProbingDepth(scip), maxdivedepth, SCIPdivesetGetNLPIterations(diveset), maxnlpiterations,
588  SCIPvarGetName(bdchgvar), lblocal, ublocal);
589 
590  infeasbdchange = FALSE;
591  /* tighten the lower and/or upper bound depending on the bound change type */
592  switch( bdchgdir )
593  {
595  /* test if bound change is possible, otherwise propagation might have deduced the same
596  * bound already or numerical troubles might have occurred */
597  if( SCIPisFeasLE(scip, bdchgvalue, lblocal) || SCIPisFeasGT(scip, bdchgvalue, ublocal) )
598  infeasbdchange = TRUE;
599  else
600  {
601  /* round variable up */
602  SCIP_CALL( SCIPchgVarLbProbing(scip, bdchgvar, bdchgvalue) );
603  }
604  break;
606  /* test if bound change is possible, otherwise propagation might have deduced the same
607  * bound already or numerical troubles might have occurred */
608  if( SCIPisFeasGE(scip, bdchgvalue, ublocal) || SCIPisFeasLT(scip, bdchgvalue, lblocal) )
609  infeasbdchange = TRUE;
610  else
611  {
612  /* round variable down */
613  SCIP_CALL( SCIPchgVarUbProbing(scip, bdchgvar, bdchgvalue) );
614  }
615  break;
617  /* test if bound change is possible, otherwise propagation might have deduced the same
618  * bound already or numerical troubles might have occurred */
619  if( SCIPisFeasLT(scip, bdchgvalue, lblocal) || SCIPisFeasGT(scip, bdchgvalue, ublocal) ||
620  (SCIPisFeasEQ(scip, lblocal, ublocal) && nbdchanges < 2) )
621  infeasbdchange = TRUE;
622  else
623  {
624  /* fix variable to the bound change value */
625  if( SCIPisFeasLT(scip, lblocal, bdchgvalue) )
626  {
627  SCIP_CALL( SCIPchgVarLbProbing(scip, bdchgvar, bdchgvalue) );
628  }
629  if( SCIPisFeasGT(scip, ublocal, bdchgvalue) )
630  {
631  SCIP_CALL( SCIPchgVarUbProbing(scip, bdchgvar, bdchgvalue) );
632  }
633  }
634  break;
635  case SCIP_BRANCHDIR_AUTO:
636  default:
637  SCIPerrorMessage("Error: Unsupported bound change direction <%d> specified for diving, aborting\n",bdchgdirs[d]);
638  SCIPABORT();
639  return SCIP_INVALIDDATA; /*lint !e527*/
640  }
641  /* if the variable domain has been shrunk in the meantime, numerical troubles may have
642  * occured or variable was fixed by propagation while backtracking => Abort diving!
643  */
644  if( infeasbdchange )
645  {
646  SCIPdebugMsg(scip, "\nSelected variable <%s> domain already [%g,%g] as least as tight as desired bound change, diving aborted \n",
647  SCIPvarGetName(bdchgvar), SCIPvarGetLbLocal(bdchgvar), SCIPvarGetUbLocal(bdchgvar));
648  cutoff = TRUE;
649  break;
650  }
651 
652  SCIPdebugMsg(scip, "newbounds=[%g,%g]\n", SCIPvarGetLbLocal(bdchgvar), SCIPvarGetUbLocal(bdchgvar));
653  }
654  /* break loop immediately if we detected a cutoff */
655  if( cutoff )
656  break;
657 
658  /* apply domain propagation */
659  localdomreds = 0;
660  SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, &localdomreds) );
661 
662  /* add the number of bound changes we applied by ourselves after propagation, otherwise the counter would have been reset */
663  localdomreds += nbdchanges;
664 
665  /* resolve the diving LP if the diving resolve frequency is reached or a sufficient number of intermediate bound changes
666  * was reached
667  */
668  if( ! cutoff
669  && ((lpsolvefreq > 0 && ((SCIPgetProbingDepth(scip) - lastlpdepth) % lpsolvefreq) == 0)
670  || (domreds + localdomreds > SCIPdivesetGetLPResolveDomChgQuot(diveset) * SCIPgetNVars(scip))
671  || (onlylpbranchcands && nviollpcands > (int)(SCIPdivesetGetLPResolveDomChgQuot(diveset) * nlpcands))) )
672  {
673  SCIP_CALL( solveLP(scip, diveset, maxnlpiterations, &lperror, &cutoff) );
674 
675  /* lp errors lead to early termination */
676  if( lperror )
677  {
678  cutoff = TRUE;
679  break;
680  }
681  }
682 
683  /* perform backtracking if a cutoff was detected */
684  if( cutoff && !backtracked && SCIPdivesetUseBacktrack(diveset) )
685  {
686  SCIPdebugMsg(scip, " *** cutoff detected at level %d - backtracking\n", SCIPgetProbingDepth(scip));
688  ++totalnbacktracks;
689  backtracked = TRUE;
690  backtrack = TRUE;
691  cutoff = FALSE;
692  }
693  else
694  backtrack = FALSE;
695  }
696  while( backtrack );
697 
698  /* we add the domain reductions from the last evaluated node */
699  domreds += localdomreds; /*lint !e771 lint thinks localdomreds has not been initialized */
700 
701  /* store candidate for pseudo cost update and choose next candidate only if no cutoff was detected */
702  if( ! cutoff )
703  {
704  if( nbdchanges == 1 && (bdchgdir == SCIP_BRANCHDIR_UPWARDS || bdchgdir == SCIP_BRANCHDIR_DOWNWARDS) )
705  {
706  ++prevcandsinsertidx;
707  assert(prevcandsinsertidx <= SCIPgetProbingDepth(scip) - lastlpdepth - 1);
708  assert(SCIPgetProbingDepth(scip) > 0);
709  assert(bdchgvar != NULL);
710  assert(bdchgvalue != SCIP_INVALID); /*lint !e777 doesn't like comparing floats for equality */
711 
712  /* extend array in case of a dynamic, domain change based LP resolve strategy */
713  if( prevcandsinsertidx >= previouscandssize )
714  {
715  previouscandssize *= 2;
716  SCIP_CALL( SCIPreallocBufferArray(scip, &previouscands, previouscandssize) );
717  SCIP_CALL( SCIPreallocBufferArray(scip, &previousvals, previouscandssize) );
718  }
719  assert(previouscandssize > prevcandsinsertidx);
720 
721  /* store candidate for pseudo cost update */
722  previouscands[prevcandsinsertidx] = bdchgvar;
723  previousvals[prevcandsinsertidx] = bdchgvalue;
724  }
725 
726  /* choose next candidate variable and resolve the LP if none is found. */
728  {
729  assert(SCIPgetProbingDepth(scip) > lastlpdepth);
730  enfosuccess = FALSE;
731 
732  /* select the next diving action */
733  SCIP_CALL( selectNextDiving(scip, diveset, worksol, onlylpbranchcands, SCIPgetProbingDepth(scip) == lastlpdepth,
734  lpcands, lpcandssol, lpcandsfrac, lpcandsscores, lpcandroundup, &nviollpcands, nlpcands,
735  &enfosuccess, &infeasible) );
736 
737 
738  /* in case of an unsuccesful candidate search, we solve the node LP */
739  if( !enfosuccess )
740  {
741  SCIP_CALL( solveLP(scip, diveset, maxnlpiterations, &lperror, &cutoff) );
742 
743  /* check for an LP error and terminate in this case, cutoffs lead to termination anyway */
744  if( lperror )
745  cutoff = TRUE;
746 
747  /* enfosuccess must be set to TRUE for entering the main LP loop again */
748  enfosuccess = TRUE;
749  }
750  }
751  }
752  }
753  while( !cutoff && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_NOTSOLVED );
754 
755  assert(cutoff || lperror || SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_NOTSOLVED);
756 
759 
760 
761  /* check new LP candidates and use the LP Objective gain to update pseudo cost information */
762  if( ! cutoff && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
763  {
764  int v;
765  SCIP_Real gain;
766 
767  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, NULL, &nlpcands, NULL, NULL) );
768 
769  SCIPdebugMsg(scip, " -> lpsolstat=%d, objval=%g/%g, nfrac=%d\n", SCIPgetLPSolstat(scip), SCIPgetLPObjval(scip), searchbound, nlpcands);
770  /* distribute the gain equally over all variables that we rounded since the last LP */
771  gain = SCIPgetLPObjval(scip) - lastlpobjval;
772  gain = MAX(gain, 0.0);
773  gain /= (1.0 * (SCIPgetProbingDepth(scip) - lastlpdepth));
774 
775  /* loop over previously fixed candidates and share gain improvement */
776  for( v = 0; v <= prevcandsinsertidx; ++v )
777  {
778  SCIP_VAR* cand = previouscands[v];
779  SCIP_Real val = previousvals[v];
780  SCIP_Real solval = SCIPgetSolVal(scip, worksol, cand);
781 
782  /* todo: should the gain be shared with a smaller weight, instead of dividing the gain itself? */
783  /* it may happen that a variable had an integral solution value beforehand, e.g., for indicator variables */
784  if( ! SCIPisZero(scip, val - solval) )
785  {
786  SCIP_CALL( SCIPupdateVarPseudocost(scip, cand, val - solval, gain, 1.0) );
787  }
788  }
789  }
790  else
791  nlpcands = 0;
792  }
793 
794  success = FALSE;
795  /* check if a solution has been found */
796  if( !enfosuccess && !lperror && !cutoff && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
797  {
798  /* create solution from diving LP */
799  SCIP_CALL( SCIPlinkLPSol(scip, worksol) );
800  SCIPdebugMsg(scip, "%s found primal solution: obj=%g\n", SCIPdivesetGetName(diveset), SCIPgetSolOrigObj(scip, worksol));
801 
802  /* try to add solution to SCIP */
803  SCIP_CALL( SCIPtrySol(scip, worksol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
804 
805  /* check, if solution was feasible and good enough */
806  if( success )
807  {
808  SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
809  *result = SCIP_FOUNDSOL;
810  leafsol = TRUE;
811  }
812  }
813 
814  SCIPupdateDivesetStats(scip, diveset, totalnprobingnodes, totalnbacktracks, SCIPgetNSolsFound(scip) - oldnsolsfound,
815  SCIPgetNBestSolsFound(scip) - oldnbestsolsfound, leafsol);
816 
817  SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") finished %s heuristic: %d fractionals, dive %d/%d, LP iter %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ", objval=%g/%g, lpsolstat=%d, cutoff=%u\n",
818  SCIPgetNNodes(scip), SCIPdivesetGetName(diveset), nlpcands, SCIPgetProbingDepth(scip), maxdivedepth, SCIPdivesetGetNLPIterations(diveset), maxnlpiterations,
819  SCIPretransformObj(scip, SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL ? SCIPgetLPObjval(scip) : SCIPinfinity(scip)), SCIPretransformObj(scip, searchbound), SCIPgetLPSolstat(scip), cutoff);
820 
821  TERMINATE:
822  /* end probing mode */
823  SCIP_CALL( SCIPendProbing(scip) );
824 
825  SCIPdivesetSetWorkSolution(diveset, NULL);
826 
827  if( onlylpbranchcands )
828  {
829  SCIPfreeBufferArray(scip, &lpcandroundup);
830  SCIPfreeBufferArray(scip, &lpcandsscores);
831  }
832  SCIPfreeBufferArray(scip, &previousvals);
833  SCIPfreeBufferArray(scip, &previouscands);
834 
835  return SCIP_OKAY;
836 }
837 
838 
839 /** creates the rows of the subproblem */
840 static
842  SCIP* scip, /**< original SCIP data structure */
843  SCIP* subscip, /**< SCIP data structure for the subproblem */
844  SCIP_HASHMAP* varmap /**< a hashmap to store the mapping of source variables to the corresponding
845  * target variables */
846  )
847 {
848  SCIP_ROW** rows; /* original scip rows */
849  SCIP_CONS* cons; /* new constraint */
850  SCIP_VAR** consvars; /* new constraint's variables */
851  SCIP_COL** cols; /* original row's columns */
852 
853  SCIP_Real constant; /* constant added to the row */
854  SCIP_Real lhs; /* left hand side of the row */
855  SCIP_Real rhs; /* left right side of the row */
856  SCIP_Real* vals; /* variables' coefficient values of the row */
857 
858  int nrows;
859  int nnonz;
860  int i;
861  int j;
862 
863  /* get the rows and their number */
864  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
865 
866  /* copy all rows to linear constraints */
867  for( i = 0; i < nrows; i++ )
868  {
869  /* ignore rows that are only locally valid */
870  if( SCIProwIsLocal(rows[i]) )
871  continue;
872 
873  /* get the row's data */
874  constant = SCIProwGetConstant(rows[i]);
875  lhs = SCIProwGetLhs(rows[i]) - constant;
876  rhs = SCIProwGetRhs(rows[i]) - constant;
877  vals = SCIProwGetVals(rows[i]);
878  nnonz = SCIProwGetNNonz(rows[i]);
879  cols = SCIProwGetCols(rows[i]);
880 
881  assert(lhs <= rhs);
882 
883  /* allocate memory array to be filled with the corresponding subproblem variables */
884  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nnonz) );
885  for( j = 0; j < nnonz; j++ )
886  consvars[j] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, (SCIPcolGetVar(cols[j])));
887 
888  /* create a new linear constraint and add it to the subproblem */
889  SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, SCIProwGetName(rows[i]), nnonz, consvars, vals, lhs, rhs,
890  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
891  SCIP_CALL( SCIPaddCons(subscip, cons) );
892  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
893 
894  /* free temporary memory */
895  SCIPfreeBufferArray(scip, &consvars);
896  }
897 
898  return SCIP_OKAY;
899 }
900 
901 
902 /** get a sub-SCIP copy of the transformed problem */
904  SCIP* sourcescip, /**< source SCIP data structure */
905  SCIP* subscip, /**< sub-SCIP used by the heuristic */
906  SCIP_HASHMAP* varmap, /**< a hashmap to store the mapping of source variables to the corresponding
907  * target variables */
908  const char* suffix, /**< suffix for the problem name */
909  SCIP_VAR** fixedvars, /**< source variables whose copies should be fixed in the target SCIP environment, or NULL */
910  SCIP_Real* fixedvals, /**< array of fixing values for target SCIP variables, or NULL */
911  int nfixedvars, /**< number of source variables whose copies should be fixed in the target SCIP environment, or NULL */
912  SCIP_Bool uselprows, /**< should the linear relaxation of the problem defined by LP rows be copied? */
913  SCIP_Bool copycuts, /**< should cuts be copied (only if uselprows == FALSE) */
914  SCIP_Bool* success, /**< was the copying successful? */
915  SCIP_Bool* valid /**< pointer to store whether the copying was valid, or NULL */
916  )
917 {
918  assert(sourcescip != NULL);
919  assert(suffix != NULL);
920  assert(subscip != NULL);
921  assert(varmap != NULL);
922  assert(success != NULL);
923 
924  if( uselprows )
925  {
926  char probname[SCIP_MAXSTRLEN];
927 
928  /* copy all plugins */
930 
931  /* get name of the original problem and add the string "_crossoversub" */
932  (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s_%s", SCIPgetProbName(sourcescip), suffix);
933 
934  /* create the subproblem */
935  SCIP_CALL( SCIPcreateProb(subscip, probname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
936 
937  /* copy all variables */
938  SCIP_CALL( SCIPcopyVars(sourcescip, subscip, varmap, NULL, fixedvars, fixedvals, nfixedvars, TRUE) );
939 
940  /* create linear constraints from LP rows of the source problem */
941  SCIP_CALL( createRows(sourcescip, subscip, varmap) );
942  }
943  else
944  {
945  SCIP_CALL( SCIPcopyConsCompression(sourcescip, subscip, varmap, NULL, suffix, fixedvars, fixedvals, nfixedvars,
946  TRUE, FALSE, TRUE, valid) );
947 
948  if( copycuts )
949  {
950  /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
951  SCIP_CALL( SCIPcopyCuts(sourcescip, subscip, varmap, NULL, TRUE, NULL) );
952  }
953  }
954 
955  *success = TRUE;
956 
957  return SCIP_OKAY;
958 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip.c:36995
int SCIPgetNIntVars(SCIP *scip)
Definition: scip.c:11896
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38570
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47292
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip.c:35958
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip.c:42327
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47305
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6604
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip.c:35931
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:43447
#define SCIP_MAXSTRLEN
Definition: def.h:259
static SCIP_RETCODE createRows(SCIP *scip, SCIP *subscip, SCIP_HASHMAP *varmap)
Definition: heuristics.c:841
SCIP_Bool SCIPdivesetUseBacktrack(SCIP_DIVESET *diveset)
Definition: heur.c:553
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
Definition: scip.c:43613
SCIP_RETCODE SCIPcreateProb(SCIP *scip, const char *name, SCIP_DECL_PROBDELORIG((*probdelorig)), SCIP_DECL_PROBTRANS((*probtrans)), SCIP_DECL_PROBDELTRANS((*probdeltrans)), SCIP_DECL_PROBINITSOL((*probinitsol)), SCIP_DECL_PROBEXITSOL((*probexitsol)), SCIP_DECL_PROBCOPY((*probcopy)), SCIP_PROBDATA *probdata)
Definition: scip.c:9936
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:16402
SCIP_Real SCIPdivesetGetUbQuot(SCIP_DIVESET *diveset)
Definition: heur.c:537
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17332
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47009
int SCIPdivesetGetMaxLPIterOffset(SCIP_DIVESET *diveset)
Definition: heur.c:514
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:16540
SCIP_Real SCIPdivesetGetAvgQuotNoSol(SCIP_DIVESET *diveset)
Definition: heur.c:530
SCIP_RETCODE SCIPmakeSOS1sFeasible(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_Bool *changed, SCIP_Bool *success)
Definition: cons_sos1.c:10746
constraint handler for indicator constraints
int SCIPgetMaxDepth(SCIP *scip)
Definition: scip.c:43089
void SCIPgetDiveBoundChangeData(SCIP *scip, SCIP_VAR ***variables, SCIP_BRANCHDIR **directions, SCIP_Real **values, int *ndivebdchgs, SCIP_Bool preferred)
Definition: scip.c:36935
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47344
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:16481
#define FALSE
Definition: def.h:64
SCIP_RETCODE SCIPcopyConsCompression(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip.c:3884
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47022
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10011
int SCIPgetNSOS1Vars(SCIP_CONSHDLR *conshdlr)
Definition: cons_sos1.c:10644
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_Real SCIPdivesetGetMaxRelDepth(SCIP_DIVESET *diveset)
Definition: heur.c:369
methods commonly used by primal heuristics
SCIP_Real SCIPgetAvgLowerbound(SCIP *scip)
Definition: scip.c:43228
SCIP_Longint SCIPdivesetGetNLPIterations(SCIP_DIVESET *diveset)
Definition: heur.c:465
SCIP_RETCODE SCIPaddDiveBoundChange(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir, SCIP_Real value, SCIP_Bool preferred)
Definition: scip.c:36909
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:36034
SCIP_Real SCIPdivesetGetMinRelDepth(SCIP_DIVESET *diveset)
Definition: heur.c:361
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2931
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip.c:1267
#define SCIPdebugMsg
Definition: scip.h:455
SCIP_Bool SCIPdivesetUseOnlyLPBranchcands(SCIP_DIVESET *diveset)
Definition: heur.c:594
SCIP_Real SCIPdivesetGetMaxLPIterQuot(SCIP_DIVESET *diveset)
Definition: heur.c:506
const char * SCIPgetProbName(SCIP *scip)
Definition: scip.c:10885
SCIP_RETCODE SCIPupdateVarPseudocost(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition: scip.c:25991
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:39
void SCIPclearDiveBoundChanges(SCIP *scip)
Definition: scip.c:36962
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip.c:29731
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1198
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:12585
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46970
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip.c:36308
static SCIP_RETCODE solveLP(SCIP *scip, SCIP_DIVESET *diveset, SCIP_Longint maxnlpiterations, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: heuristics.c:36
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:16590
SCIP_Real SCIPgetDualbound(SCIP *scip)
Definition: scip.c:43250
SCIP_RETCODE SCIPcopyVars(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool global)
Definition: scip.c:2341
SCIP_RETCODE SCIPcopyCuts(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, int *ncutsadded)
Definition: scip.c:3065
SCIP_Real SCIPdivesetGetAvgQuot(SCIP_DIVESET *diveset)
Definition: heur.c:545
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip.c:35993
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
static SCIP_RETCODE selectNextDiving(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_Bool onlylpbranchcands, SCIP_Bool storelpcandscores, SCIP_VAR **lpcands, SCIP_Real *lpcandssol, SCIP_Real *lpcandsfrac, SCIP_Real *lpcandsscores, SCIP_Bool *lpcandroundup, int *nviollpcands, int nlpcands, SCIP_Bool *enfosuccess, SCIP_Bool *infeasible)
Definition: heuristics.c:79
void SCIPupdateDivesetLPStats(SCIP *scip, SCIP_DIVESET *diveset, SCIP_Longint niterstoadd)
Definition: scip.c:36794
#define SCIP_CALL(x)
Definition: def.h:350
SCIP_Real SCIPgetLowerbound(SCIP *scip)
Definition: scip.c:43271
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47331
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip.c:36544
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47318
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:16491
SCIP_Real SCIPdivesetGetLPResolveDomChgQuot(SCIP_DIVESET *diveset)
Definition: heur.c:582
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:16427
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip.c:29202
SCIP_Longint SCIPgetLastDivenode(SCIP *scip)
Definition: scip.c:35766
SCIP_Longint SCIPgetNNodeLPIterations(SCIP *scip)
Definition: scip.c:42648
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:16437
#define SCIP_Bool
Definition: def.h:61
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:29287
SCIP_Real SCIPdivesetGetUbQuotNoSol(SCIP_DIVESET *diveset)
Definition: heur.c:522
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition: scip.c:40018
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:43039
#define MAX(x, y)
Definition: tclique_def.h:75
SCIP_RETCODE SCIPgetDiveBoundChanges(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *sol, SCIP_Bool *success, SCIP_Bool *infeasible)
Definition: scip.c:36847
void SCIPenableVarHistory(SCIP *scip)
Definition: scip.c:25952
#define MINLPITER
Definition: heuristics.c:31
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38988
Constraint handler for linear constraints in their most general form, .
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip.c:40694
#define SCIP_MAXTREEDEPTH
Definition: def.h:286
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11851
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11806
SCIP_RETCODE SCIPperformGenericDivingAlgorithm(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Bool nodeinfeasible)
Definition: heuristics.c:192
SCIP_Real SCIPgetAvgDualbound(SCIP *scip)
Definition: scip.c:43209
#define SCIP_REAL_MIN
Definition: def.h:151
void SCIPdivesetSetWorkSolution(SCIP_DIVESET *diveset, SCIP_SOL *sol)
Definition: heur.c:340
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:16447
SCIP_Bool SCIPisObjIntegral(SCIP *scip)
Definition: scip.c:11380
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip.c:29366
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16251
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip.c:27755
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip.c:39120
SCIP_RETCODE SCIPcopyLargeNeighborhoodSearch(SCIP *sourcescip, SCIP *subscip, SCIP_HASHMAP *varmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool uselprows, SCIP_Bool copycuts, SCIP_Bool *success, SCIP_Bool *valid)
Definition: heuristics.c:903
SCIP_Longint SCIPgetNBestSolsFound(SCIP *scip)
Definition: scip.c:43667
#define SCIP_Real
Definition: def.h:149
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1145
constraint handler for SOS type 1 constraints
SCIP_RETCODE SCIPmakeIndicatorsFeasible(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_Bool *changed)
#define SCIP_INVALID
Definition: def.h:169
#define SCIP_Longint
Definition: def.h:134
SCIP_Longint SCIPdivesetGetSolSuccess(SCIP_DIVESET *diveset)
Definition: heur.c:377
SCIP_RETCODE SCIPunlinkSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38734
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:47070
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46983
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17342
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip.c:35898
SCIP_RETCODE SCIPgetDivesetScore(SCIP *scip, SCIP_DIVESET *diveset, SCIP_DIVETYPE divetype, SCIP_VAR *divecand, SCIP_Real divecandsol, SCIP_Real divecandfrac, SCIP_Real *candscore, SCIP_Bool *roundup)
Definition: scip.c:36769
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip.c:35852
public methods for primal heuristics
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip.c:29634
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
Definition: scip.c:47155
#define SCIP_DIVETYPE_INTEGRALITY
Definition: type_heur.h:45
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:42127
#define SCIPABORT()
Definition: def.h:322
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:36078
int SCIPdivesetGetNCalls(SCIP_DIVESET *diveset)
Definition: heur.c:385
void SCIPupdateDivesetStats(SCIP *scip, SCIP_DIVESET *diveset, int nprobingnodes, int nbacktracks, SCIP_Longint nsolsfound, SCIP_Longint nbestsolsfound, SCIP_Bool leavewassol)
Definition: scip.c:36807
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38905
default SCIP plugins
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:47143
SCIP_Bool SCIPvarMayRoundUp(SCIP_VAR *var)
Definition: var.c:3280
SCIP_Bool SCIPvarMayRoundDown(SCIP_VAR *var)
Definition: var.c:3272
int SCIPdivesetGetLPSolveFreq(SCIP_DIVESET *diveset)
Definition: heur.c:561
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip.h:22624
const char * SCIPdivesetGetName(SCIP_DIVESET *diveset)
Definition: heur.c:351