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 enfosuccess;
236  SCIP_Bool lperror;
237  SCIP_Bool cutoff;
238  SCIP_Bool backtracked;
239  SCIP_Bool backtrack;
240  SCIP_Bool onlylpbranchcands;
241 
242  int nlpcands;
243  int lpsolvefreq;
244 
245  assert(scip != NULL);
246  assert(heur != NULL);
247  assert(result != NULL);
248  assert(worksol != NULL);
249 
250  *result = SCIP_DELAYED;
251 
252  /* do not call heuristic in node that was already detected to be infeasible */
253  if( nodeinfeasible )
254  return SCIP_OKAY;
255 
256  /* only call heuristic, if an optimal LP solution is at hand */
258  return SCIP_OKAY;
259 
260  /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
261  if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) )
262  return SCIP_OKAY;
263 
264  /* only call heuristic, if the LP solution is basic (which allows fast resolve in diving) */
265  if( !SCIPisLPSolBasic(scip) )
266  return SCIP_OKAY;
267 
268  /* don't dive two times at the same node */
269  if( SCIPgetLastDivenode(scip) == SCIPgetNNodes(scip) && SCIPgetDepth(scip) > 0 )
270  return SCIP_OKAY;
271 
272  *result = SCIP_DIDNOTRUN;
273 
274  /* only try to dive, if we are in the correct part of the tree, given by minreldepth and maxreldepth */
275  depth = SCIPgetDepth(scip);
276  maxdepth = SCIPgetMaxDepth(scip);
277  maxdepth = MAX(maxdepth, 30);
278  if( depth < SCIPdivesetGetMinRelDepth(diveset) * maxdepth || depth > SCIPdivesetGetMaxRelDepth(diveset) * maxdepth )
279  return SCIP_OKAY;
280 
281  /* calculate the maximal number of LP iterations until heuristic is aborted */
282  nlpiterations = SCIPgetNNodeLPIterations(scip);
283  ncalls = SCIPdivesetGetNCalls(diveset);
284  oldsolsuccess = SCIPdivesetGetSolSuccess(diveset);
285 
286  /*todo another factor of 10, REALLY? */
287  maxnlpiterations = (SCIP_Longint)((1.0 + 10*(oldsolsuccess+1.0)/(ncalls+1.0)) * SCIPdivesetGetMaxLPIterQuot(diveset) * nlpiterations);
288  maxnlpiterations += SCIPdivesetGetMaxLPIterOffset(diveset);
289 
290  /* don't try to dive, if we took too many LP iterations during diving */
291  if( SCIPdivesetGetNLPIterations(diveset) >= maxnlpiterations )
292  return SCIP_OKAY;
293 
294  /* allow at least a certain number of LP iterations in this dive */
295  if( SCIPdivesetGetNLPIterations(diveset) + MINLPITER > maxnlpiterations )
296  maxnlpiterations = SCIPdivesetGetNLPIterations(diveset) + MINLPITER;
297 
298  /* these constraint handlers are required for polishing an LP relaxation solution beyond rounding */
299  indconshdlr = SCIPfindConshdlr(scip, "indicator");
300  sos1conshdlr = SCIPfindConshdlr(scip, "SOS1");
301 
302  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, &lpcandsfrac, &nlpcands, NULL, NULL) );
303 
304  onlylpbranchcands = SCIPdivesetUseOnlyLPBranchcands(diveset);
305  /* don't try to dive, if there are no diving candidates */
306  if( onlylpbranchcands && nlpcands == 0 )
307  return SCIP_OKAY;
308 
309  /* calculate the objective search bound */
310  if( SCIPgetNSolsFound(scip) == 0 )
311  {
312  ubquot = SCIPdivesetGetUbQuotNoSol(diveset);
313  avgquot = SCIPdivesetGetAvgQuotNoSol(diveset);
314  }
315  else
316  {
317  ubquot = SCIPdivesetGetUbQuot(diveset);
318  avgquot = SCIPdivesetGetAvgQuot(diveset);
319  }
320 
321  if( ubquot > 0.0 )
322  searchubbound = SCIPgetLowerbound(scip) + ubquot * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
323  else
324  searchubbound = SCIPinfinity(scip);
325 
326  if( avgquot > 0.0 )
327  searchavgbound = SCIPgetLowerbound(scip) + avgquot * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
328  else
329  searchavgbound = SCIPinfinity(scip);
330 
331  searchbound = MIN(searchubbound, searchavgbound);
332 
333  if( SCIPisObjIntegral(scip) )
334  searchbound = SCIPceil(scip, searchbound);
335 
336  /* calculate the maximal diving depth: 10 * min{number of integer variables, max depth} */
337  maxdivedepth = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
338  if ( sos1conshdlr != NULL )
339  maxdivedepth += SCIPgetNSOS1Vars(sos1conshdlr);
340  maxdivedepth = MIN(maxdivedepth, maxdepth);
341  maxdivedepth *= 10;
342 
343  *result = SCIP_DIDNOTFIND;
344 
345  /* start probing mode */
346  SCIP_CALL( SCIPstartProbing(scip) );
347 
348  /* enables collection of variable statistics during probing */
349  SCIPenableVarHistory(scip);
350 
351  SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") executing %s heuristic: depth=%d, %d fractionals, dualbound=%g, avgbound=%g, cutoffbound=%g, searchbound=%g\n",
352  SCIPgetNNodes(scip), SCIPheurGetName(heur), SCIPgetDepth(scip), nlpcands, SCIPgetDualbound(scip), SCIPgetAvgDualbound(scip),
353  SCIPretransformObj(scip, SCIPgetCutoffbound(scip)), SCIPretransformObj(scip, searchbound));
354 
355 
356  /* allocate buffer storage for previous candidates and their branching values for pseudo cost updates */
357  lpsolvefreq = SCIPdivesetGetLPSolveFreq(diveset);
358  previouscandssize = MAX(1, lpsolvefreq);
359  SCIP_CALL( SCIPallocBufferArray(scip, &previouscands, previouscandssize) );
360  SCIP_CALL( SCIPallocBufferArray(scip, &previousvals, previouscandssize) );
361 
362  /* keep some statistics */
363  lperror = FALSE;
364  cutoff = FALSE;
365  lastlpdepth = -1;
366  startndivecands = nlpcands;
367  totalnbacktracks = 0;
368  totalnprobingnodes = 0;
369  oldnsolsfound = SCIPgetNSolsFound(scip);
370  oldnbestsolsfound = SCIPgetNBestSolsFound(scip);
371 
372  /* link the working solution to the dive set */
373  SCIPdivesetSetWorkSolution(diveset, worksol);
374 
375  if( onlylpbranchcands )
376  {
377  SCIP_CALL( SCIPallocBufferArray(scip, &lpcandsscores, nlpcands) );
378  SCIP_CALL( SCIPallocBufferArray(scip, &lpcandroundup, nlpcands) );
379 
380  lpcandsscoressize = nlpcands;
381  }
382  else
383  {
384  lpcandroundup = NULL;
385  lpcandsscores = NULL;
386  lpcandsscoressize = 0;
387  }
388 
389  enfosuccess = TRUE;
390 
391  /* LP loop; every time a new LP was solved, conditions are checked
392  * dive as long we are in the given objective, depth and iteration limits and fractional variables exist, but
393  * - if possible, we dive at least with the depth 10
394  * - if the number of fractional variables decreased at least with 1 variable per 2 dive depths, we continue diving
395  */
396  while( !lperror && !cutoff && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL && enfosuccess
397  && (SCIPgetProbingDepth(scip) < 10
398  || nlpcands <= startndivecands - SCIPgetProbingDepth(scip) / 2
399  || (SCIPgetProbingDepth(scip) < maxdivedepth && SCIPdivesetGetNLPIterations(diveset) < maxnlpiterations && SCIPgetLPObjval(scip) < searchbound))
400  && !SCIPisStopped(scip) )
401  {
402  SCIP_Real lastlpobjval;
403  int c;
404  SCIP_Bool allroundable;
405  SCIP_Bool infeasible;
406  int prevcandsinsertidx;
407 
408  /* remember the last LP depth */
409  assert(lastlpdepth < SCIPgetProbingDepth(scip));
410  lastlpdepth = SCIPgetProbingDepth(scip);
411  domreds = 0;
412 
413  SCIPdebugMsg(scip, "%s heuristic continues diving at depth %d, %d candidates left\n",
414  SCIPdivesetGetName(diveset), lastlpdepth, nlpcands);
415 
416 
417  /* loop over candidates and determine if they are roundable */
418  allroundable = TRUE;
419  c = 0;
420  while( allroundable && c < nlpcands )
421  {
422  if( SCIPvarMayRoundDown(lpcands[c]) || SCIPvarMayRoundUp(lpcands[c]) )
423  allroundable = TRUE;
424  else
425  allroundable = FALSE;
426  ++c;
427  }
428 
429  /* if all candidates are roundable, try to round the solution */
430  if( allroundable )
431  {
432  success = FALSE;
433 
434  /* working solution must be linked to LP solution */
435  SCIP_CALL( SCIPlinkLPSol(scip, worksol) );
436  /* create solution from diving LP and try to round it */
437  SCIP_CALL( SCIProundSol(scip, worksol, &success) );
438 
439  /* adjust SOS1 constraints */
440  if( success && sos1conshdlr != NULL )
441  {
442  SCIP_Bool changed;
443  SCIP_CALL( SCIPmakeSOS1sFeasible(scip, sos1conshdlr, worksol, &changed, &success) );
444  }
445 
446  /* succesfully rounded solutions are tried for primal feasibility */
447  if( success )
448  {
449  SCIP_Bool changed = FALSE;
450  SCIPdebugMsg(scip, "%s found roundable primal solution: obj=%g\n", SCIPdivesetGetName(diveset), SCIPgetSolOrigObj(scip, worksol));
451 
452  /* adjust indicator constraints */
453  if( indconshdlr != NULL )
454  {
455  SCIP_CALL( SCIPmakeIndicatorsFeasible(scip, indconshdlr, worksol, &changed) );
456  }
457 
458  success = FALSE;
459  /* try to add solution to SCIP */
460  SCIP_CALL( SCIPtrySol(scip, worksol, FALSE, FALSE, FALSE, FALSE, changed, &success) );
461 
462  /* check, if solution was feasible and good enough */
463  if( success )
464  {
465  SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
466  *result = SCIP_FOUNDSOL;
467 
468  /* the rounded solution found above led to a cutoff of the node LP solution */
470  {
471  cutoff = TRUE;
472  break;
473  }
474  }
475  }
476  }
477 
478  /* working solution must be linked to LP solution */
479  assert(SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL);
480  lastlpobjval = SCIPgetLPObjval(scip);
481  SCIP_CALL( SCIPlinkLPSol(scip, worksol) );
482 
483  /* in case we do not solve LP's at every probing node, we must explicitly store the solution values by unlinking the
484  * solution, otherwise, the working solution may contain wrong entries, if, e.g., a backtrack occurred after an
485  * intermediate LP resolve
486  */
487  if( lpsolvefreq != 1 )
488  {
489  SCIP_CALL( SCIPunlinkSol(scip, worksol) );
490  }
491 
492 
493  /* ensure array sizes for the diving on the fractional variables */
494  if( onlylpbranchcands && nlpcands > lpcandsscoressize )
495  {
496  assert(nlpcands > 0);
497  assert(lpcandsscores != NULL);
498  assert(lpcandroundup != NULL);
499 
500  SCIP_CALL( SCIPreallocBufferArray(scip, &lpcandsscores, nlpcands) );
501  SCIP_CALL( SCIPreallocBufferArray(scip, &lpcandroundup, nlpcands) );
502 
503  lpcandsscoressize = nlpcands;
504  }
505 
506 
507  enfosuccess = FALSE;
508  /* select the next diving action by selecting appropriate dive bound changes for the preferred and alternative child */
509  SCIP_CALL( selectNextDiving(scip, diveset, worksol, onlylpbranchcands, SCIPgetProbingDepth(scip) == lastlpdepth,
510  lpcands, lpcandssol, lpcandsfrac, lpcandsscores, lpcandroundup, &nviollpcands, nlpcands,
511  &enfosuccess, &infeasible) );
512 
513  /* if we did not succeed finding an enforcement, the solution is potentially feasible and we break immediately */
514  if( ! enfosuccess )
515  break;
516 
517  prevcandsinsertidx = -1;
518 
519  /* start propagating candidate variables
520  * - until the desired targetdepth is reached,
521  * - or there is no further candidate variable left because of intermediate bound changes,
522  * - or a cutoff is detected
523  */
524  do
525  {
526  SCIP_VAR* bdchgvar;
527  SCIP_Real bdchgvalue;
528  SCIP_Longint localdomreds;
529  SCIP_BRANCHDIR bdchgdir;
530  int nbdchanges;
531 
532  /* ensure that a new candidate was successfully determined (usually at the end of the previous loop iteration) */
533  assert(enfosuccess);
534  bdchgvar = NULL;
535  bdchgvalue = SCIP_INVALID;
536  bdchgdir = SCIP_BRANCHDIR_AUTO;
537 
538  backtracked = FALSE;
539  do
540  {
541  int d;
542  SCIP_VAR** bdchgvars;
543  SCIP_BRANCHDIR* bdchgdirs;
544  SCIP_Real* bdchgvals;
545 
546  nbdchanges = 0;
547  /* get the bound change information stored in the dive set */
548  SCIPgetDiveBoundChangeData(scip, &bdchgvars, &bdchgdirs, &bdchgvals, &nbdchanges, !backtracked);
549 
550  assert(nbdchanges > 0);
551  assert(bdchgvars != NULL);
552  assert(bdchgdirs != NULL);
553  assert(bdchgvals != NULL);
554 
555  /* return if we reached the depth limit */
556  if( SCIP_MAXTREEDEPTH <= SCIPgetDepth(scip) )
557  {
558  SCIPdebugMsg(scip, "depth limit reached, we stop diving immediately.\n");
559  goto TERMINATE;
560  }
561 
562  /* dive deeper into the tree */
563  SCIP_CALL( SCIPnewProbingNode(scip) );
564  ++totalnprobingnodes;
565 
566  /* apply all suggested domain changes of the variables */
567  for( d = 0; d < nbdchanges; ++d )
568  {
569  SCIP_Real lblocal;
570  SCIP_Real ublocal;
571  SCIP_Bool infeasbdchange;
572 
573  /* get the next bound change data: variable, direction, and value */
574  bdchgvar = bdchgvars[d];
575  bdchgvalue = bdchgvals[d];
576  bdchgdir = bdchgdirs[d];
577 
578  assert(bdchgvar != NULL);
579  lblocal = SCIPvarGetLbLocal(bdchgvar);
580  ublocal = SCIPvarGetUbLocal(bdchgvar);
581 
582 
583  SCIPdebugMsg(scip, " dive %d/%d, LP iter %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ": var <%s>, oldbounds=[%g,%g],",
584  SCIPgetProbingDepth(scip), maxdivedepth, SCIPdivesetGetNLPIterations(diveset), maxnlpiterations,
585  SCIPvarGetName(bdchgvar), lblocal, ublocal);
586 
587  infeasbdchange = FALSE;
588  /* tighten the lower and/or upper bound depending on the bound change type */
589  switch( bdchgdir )
590  {
592  /* test if bound change is possible, otherwise propagation might have deduced the same
593  * bound already or numerical troubles might have occurred */
594  if( SCIPisFeasLE(scip, bdchgvalue, lblocal) || SCIPisFeasGT(scip, bdchgvalue, ublocal) )
595  infeasbdchange = TRUE;
596  else
597  {
598  /* round variable up */
599  SCIP_CALL( SCIPchgVarLbProbing(scip, bdchgvar, bdchgvalue) );
600  }
601  break;
603  /* test if bound change is possible, otherwise propagation might have deduced the same
604  * bound already or numerical troubles might have occurred */
605  if( SCIPisFeasGE(scip, bdchgvalue, ublocal) || SCIPisFeasLT(scip, bdchgvalue, lblocal) )
606  infeasbdchange = TRUE;
607  else
608  {
609  /* round variable down */
610  SCIP_CALL( SCIPchgVarUbProbing(scip, bdchgvar, bdchgvalue) );
611  }
612  break;
614  /* test if bound change is possible, otherwise propagation might have deduced the same
615  * bound already or numerical troubles might have occurred */
616  if( SCIPisFeasLT(scip, bdchgvalue, lblocal) || SCIPisFeasGT(scip, bdchgvalue, ublocal) ||
617  (SCIPisFeasEQ(scip, lblocal, ublocal) && nbdchanges < 2) )
618  infeasbdchange = TRUE;
619  else
620  {
621  /* fix variable to the bound change value */
622  if( SCIPisFeasLT(scip, lblocal, bdchgvalue) )
623  {
624  SCIP_CALL( SCIPchgVarLbProbing(scip, bdchgvar, bdchgvalue) );
625  }
626  if( SCIPisFeasGT(scip, ublocal, bdchgvalue) )
627  {
628  SCIP_CALL( SCIPchgVarUbProbing(scip, bdchgvar, bdchgvalue) );
629  }
630  }
631  break;
632  case SCIP_BRANCHDIR_AUTO:
633  default:
634  SCIPerrorMessage("Error: Unsupported bound change direction <%d> specified for diving, aborting\n",bdchgdirs[d]);
635  SCIPABORT();
636  return SCIP_INVALIDDATA; /*lint !e527*/
637  }
638  /* if the variable domain has been shrunk in the meantime, numerical troubles may have
639  * occured or variable was fixed by propagation while backtracking => Abort diving!
640  */
641  if( infeasbdchange )
642  {
643  SCIPdebugMsg(scip, "\nSelected variable <%s> domain already [%g,%g] as least as tight as desired bound change, diving aborted \n",
644  SCIPvarGetName(bdchgvar), SCIPvarGetLbLocal(bdchgvar), SCIPvarGetUbLocal(bdchgvar));
645  cutoff = TRUE;
646  break;
647  }
648 
649  SCIPdebugMsg(scip, "newbounds=[%g,%g]\n", SCIPvarGetLbLocal(bdchgvar), SCIPvarGetUbLocal(bdchgvar));
650  }
651  /* break loop immediately if we detected a cutoff */
652  if( cutoff )
653  break;
654 
655  /* apply domain propagation */
656  localdomreds = 0;
657  SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, &localdomreds) );
658 
659  /* add the number of bound changes we applied by ourselves after propagation, otherwise the counter would have been reset */
660  localdomreds += nbdchanges;
661 
662  /* resolve the diving LP if the diving resolve frequency is reached or a sufficient number of intermediate bound changes
663  * was reached
664  */
665  if( ! cutoff
666  && ((lpsolvefreq > 0 && ((SCIPgetProbingDepth(scip) - lastlpdepth) % lpsolvefreq) == 0)
667  || (domreds + localdomreds > SCIPdivesetGetLPResolveDomChgQuot(diveset) * SCIPgetNVars(scip))
668  || (onlylpbranchcands && nviollpcands > (int)(SCIPdivesetGetLPResolveDomChgQuot(diveset) * nlpcands))) )
669  {
670  SCIP_CALL( solveLP(scip, diveset, maxnlpiterations, &lperror, &cutoff) );
671 
672  /* lp errors lead to early termination */
673  if( lperror )
674  {
675  cutoff = TRUE;
676  break;
677  }
678  }
679 
680  /* perform backtracking if a cutoff was detected */
681  if( cutoff && !backtracked && SCIPdivesetUseBacktrack(diveset) )
682  {
683  SCIPdebugMsg(scip, " *** cutoff detected at level %d - backtracking\n", SCIPgetProbingDepth(scip));
685  ++totalnbacktracks;
686  backtracked = TRUE;
687  backtrack = TRUE;
688  cutoff = FALSE;
689  }
690  else
691  backtrack = FALSE;
692  }
693  while( backtrack );
694 
695  /* we add the domain reductions from the last evaluated node */
696  domreds += localdomreds; /*lint !e771 lint thinks localdomreds has not been initialized */
697 
698  /* store candidate for pseudo cost update and choose next candidate only if no cutoff was detected */
699  if( ! cutoff )
700  {
701  if( nbdchanges == 1 && (bdchgdir == SCIP_BRANCHDIR_UPWARDS || bdchgdir == SCIP_BRANCHDIR_DOWNWARDS) )
702  {
703  ++prevcandsinsertidx;
704  assert(prevcandsinsertidx <= SCIPgetProbingDepth(scip) - lastlpdepth - 1);
705  assert(SCIPgetProbingDepth(scip) > 0);
706  assert(bdchgvar != NULL);
707  assert(bdchgvalue != SCIP_INVALID); /*lint !e777 doesn't like comparing floats for equality */
708 
709  /* extend array in case of a dynamic, domain change based LP resolve strategy */
710  if( prevcandsinsertidx >= previouscandssize )
711  {
712  previouscandssize *= 2;
713  SCIP_CALL( SCIPreallocBufferArray(scip, &previouscands, previouscandssize) );
714  SCIP_CALL( SCIPreallocBufferArray(scip, &previousvals, previouscandssize) );
715  }
716  assert(previouscandssize > prevcandsinsertidx);
717 
718  /* store candidate for pseudo cost update */
719  previouscands[prevcandsinsertidx] = bdchgvar;
720  previousvals[prevcandsinsertidx] = bdchgvalue;
721  }
722 
723  /* choose next candidate variable and resolve the LP if none is found. */
725  {
726  assert(SCIPgetProbingDepth(scip) > lastlpdepth);
727  enfosuccess = FALSE;
728 
729  /* select the next diving action */
730  SCIP_CALL( selectNextDiving(scip, diveset, worksol, onlylpbranchcands, SCIPgetProbingDepth(scip) == lastlpdepth,
731  lpcands, lpcandssol, lpcandsfrac, lpcandsscores, lpcandroundup, &nviollpcands, nlpcands,
732  &enfosuccess, &infeasible) );
733 
734 
735  /* in case of an unsuccesful candidate search, we solve the node LP */
736  if( !enfosuccess )
737  {
738  SCIP_CALL( solveLP(scip, diveset, maxnlpiterations, &lperror, &cutoff) );
739 
740  /* check for an LP error and terminate in this case, cutoffs lead to termination anyway */
741  if( lperror )
742  cutoff = TRUE;
743 
744  /* enfosuccess must be set to TRUE for entering the main LP loop again */
745  enfosuccess = TRUE;
746  }
747  }
748  }
749  }
750  while( !cutoff && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_NOTSOLVED );
751 
752  assert(cutoff || lperror || SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_NOTSOLVED);
753 
756 
757 
758  /* check new LP candidates and use the LP Objective gain to update pseudo cost information */
759  if( ! cutoff && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
760  {
761  int v;
762  SCIP_Real gain;
763 
764  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, NULL, &nlpcands, NULL, NULL) );
765 
766  /* distribute the gain equally over all variables that we rounded since the last LP */
767  gain = SCIPgetLPObjval(scip) - lastlpobjval;
768  gain = MAX(gain, 0.0);
769  gain /= (1.0 * (SCIPgetProbingDepth(scip) - lastlpdepth));
770 
771  /* loop over previously fixed candidates and share gain improvement */
772  for( v = 0; v <= prevcandsinsertidx; ++v )
773  {
774  SCIP_VAR* cand = previouscands[v];
775  SCIP_Real val = previousvals[v];
776  SCIP_Real solval = SCIPgetSolVal(scip, worksol, cand);
777 
778  /* todo: should the gain be shared with a smaller weight, instead of dividing the gain itself? */
779  /* it may happen that a variable had an integral solution value beforehand, e.g., for indicator variables */
780  if( ! SCIPisZero(scip, val - solval) )
781  {
782  SCIP_CALL( SCIPupdateVarPseudocost(scip, cand, val - solval, gain, 1.0) );
783  }
784  }
785  }
786  else
787  nlpcands = 0;
788  SCIPdebugMsg(scip, " -> lpsolstat=%d, objval=%g/%g, nfrac=%d\n", SCIPgetLPSolstat(scip), SCIPgetLPObjval(scip), searchbound, nlpcands);
789  }
790 
791  success = FALSE;
792  /* check if a solution has been found */
793  if( !enfosuccess && !lperror && !cutoff && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
794  {
795  /* create solution from diving LP */
796  SCIP_CALL( SCIPlinkLPSol(scip, worksol) );
797  SCIPdebugMsg(scip, "%s found primal solution: obj=%g\n", SCIPdivesetGetName(diveset), SCIPgetSolOrigObj(scip, worksol));
798 
799  /* try to add solution to SCIP */
800  SCIP_CALL( SCIPtrySol(scip, worksol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
801 
802  /* check, if solution was feasible and good enough */
803  if( success )
804  {
805  SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
806  *result = SCIP_FOUNDSOL;
807  }
808  }
809 
810  SCIPupdateDivesetStats(scip, diveset, totalnprobingnodes, totalnbacktracks, SCIPgetNSolsFound(scip) - oldnsolsfound,
811  SCIPgetNBestSolsFound(scip) - oldnbestsolsfound, success);
812 
813  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",
814  SCIPgetNNodes(scip), SCIPdivesetGetName(diveset), nlpcands, SCIPgetProbingDepth(scip), maxdivedepth, SCIPdivesetGetNLPIterations(diveset), maxnlpiterations,
815  SCIPretransformObj(scip, SCIPgetLPObjval(scip)), SCIPretransformObj(scip, searchbound), SCIPgetLPSolstat(scip), cutoff);
816 
817  TERMINATE:
818  /* end probing mode */
819  SCIP_CALL( SCIPendProbing(scip) );
820 
822 
823  if( onlylpbranchcands )
824  {
825  SCIPfreeBufferArray(scip, &lpcandroundup);
826  SCIPfreeBufferArray(scip, &lpcandsscores);
827  }
828  SCIPfreeBufferArray(scip, &previousvals);
829  SCIPfreeBufferArray(scip, &previouscands);
830 
831  return SCIP_OKAY;
832 }
833 
834 
835 /** creates the rows of the subproblem */
836 static
838  SCIP* scip, /**< original SCIP data structure */
839  SCIP* subscip, /**< SCIP data structure for the subproblem */
840  SCIP_HASHMAP* varmap /**< a hashmap to store the mapping of source variables to the corresponding
841  * target variables */
842  )
843 {
844  SCIP_ROW** rows; /* original scip rows */
845  SCIP_CONS* cons; /* new constraint */
846  SCIP_VAR** consvars; /* new constraint's variables */
847  SCIP_COL** cols; /* original row's columns */
848 
849  SCIP_Real constant; /* constant added to the row */
850  SCIP_Real lhs; /* left hand side of the row */
851  SCIP_Real rhs; /* left right side of the row */
852  SCIP_Real* vals; /* variables' coefficient values of the row */
853 
854  int nrows;
855  int nnonz;
856  int i;
857  int j;
858 
859  /* get the rows and their number */
860  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
861 
862  /* copy all rows to linear constraints */
863  for( i = 0; i < nrows; i++ )
864  {
865  /* ignore rows that are only locally valid */
866  if( SCIProwIsLocal(rows[i]) )
867  continue;
868 
869  /* get the row's data */
870  constant = SCIProwGetConstant(rows[i]);
871  lhs = SCIProwGetLhs(rows[i]) - constant;
872  rhs = SCIProwGetRhs(rows[i]) - constant;
873  vals = SCIProwGetVals(rows[i]);
874  nnonz = SCIProwGetNNonz(rows[i]);
875  cols = SCIProwGetCols(rows[i]);
876 
877  assert(lhs <= rhs);
878 
879  /* allocate memory array to be filled with the corresponding subproblem variables */
880  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nnonz) );
881  for( j = 0; j < nnonz; j++ )
882  consvars[j] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, (SCIPcolGetVar(cols[j])));
883 
884  /* create a new linear constraint and add it to the subproblem */
885  SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, SCIProwGetName(rows[i]), nnonz, consvars, vals, lhs, rhs,
886  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
887  SCIP_CALL( SCIPaddCons(subscip, cons) );
888  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
889 
890  /* free temporary memory */
891  SCIPfreeBufferArray(scip, &consvars);
892  }
893 
894  return SCIP_OKAY;
895 }
896 
897 
898 /** get a sub-SCIP copy of the transformed problem */
900  SCIP* sourcescip, /**< source SCIP data structure */
901  SCIP* subscip, /**< sub-SCIP used by the heuristic */
902  SCIP_HASHMAP* varmap, /**< a hashmap to store the mapping of source variables to the corresponding
903  * target variables */
904  const char* suffix, /**< suffix for the problem name */
905  SCIP_VAR** fixedvars, /**< source variables whose copies should be fixed in the target SCIP environment, or NULL */
906  SCIP_Real* fixedvals, /**< array of fixing values for target SCIP variables, or NULL */
907  int nfixedvars, /**< number of source variables whose copies should be fixed in the target SCIP environment, or NULL */
908  SCIP_Bool uselprows, /**< should the linear relaxation of the problem defined by LP rows be copied? */
909  SCIP_Bool copycuts, /**< should cuts be copied (only if uselprows == FALSE) */
910  SCIP_Bool* success, /**< was the copying successful? */
911  SCIP_Bool* valid /**< pointer to store whether the copying was valid, or NULL */
912  )
913 {
914  assert(sourcescip != NULL);
915  assert(suffix != NULL);
916  assert(subscip != NULL);
917  assert(varmap != NULL);
918  assert(success != NULL);
919 
920  if( uselprows )
921  {
922  char probname[SCIP_MAXSTRLEN];
923 
924  /* copy all plugins */
926 
927  /* get name of the original problem and add the string "_crossoversub" */
928  (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s_%s", SCIPgetProbName(sourcescip), suffix);
929 
930  /* create the subproblem */
931  SCIP_CALL( SCIPcreateProb(subscip, probname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
932 
933  /* copy all variables */
934  SCIP_CALL( SCIPcopyVars(sourcescip, subscip, varmap, NULL, fixedvars, fixedvals, nfixedvars, TRUE) );
935 
936  /* create linear constraints from LP rows of the source problem */
937  SCIP_CALL( createRows(sourcescip, subscip, varmap) );
938  }
939  else
940  {
941  SCIP_CALL( SCIPcopyConsCompression(sourcescip, subscip, varmap, NULL, suffix, fixedvars, fixedvals, nfixedvars,
942  TRUE, FALSE, TRUE, valid) );
943 
944  if( copycuts )
945  {
946  /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
947  SCIP_CALL( SCIPcopyCuts(sourcescip, subscip, varmap, NULL, TRUE, NULL) );
948  }
949  }
950 
951  *success = TRUE;
952 
953  return SCIP_OKAY;
954 }
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:36128
int SCIPgetNIntVars(SCIP *scip)
Definition: scip.c:11721
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:37672
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46086
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip.c:35152
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip.c:41382
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46099
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6541
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip.c:35125
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:42499
#define SCIP_MAXSTRLEN
Definition: def.h:215
static SCIP_RETCODE createRows(SCIP *scip, SCIP *subscip, SCIP_HASHMAP *varmap)
Definition: heuristics.c:837
SCIP_Bool SCIPdivesetUseBacktrack(SCIP_DIVESET *diveset)
Definition: heur.c:539
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
Definition: scip.c:42664
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:9778
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:16232
SCIP_Real SCIPdivesetGetUbQuot(SCIP_DIVESET *diveset)
Definition: heur.c:523
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17222
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45803
int SCIPdivesetGetMaxLPIterOffset(SCIP_DIVESET *diveset)
Definition: heur.c:500
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:16370
SCIP_Real SCIPdivesetGetAvgQuotNoSol(SCIP_DIVESET *diveset)
Definition: heur.c:516
SCIP_RETCODE SCIPmakeSOS1sFeasible(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_Bool *changed, SCIP_Bool *success)
Definition: cons_sos1.c:10728
constraint handler for indicator constraints
int SCIPgetMaxDepth(SCIP *scip)
Definition: scip.c:42144
void SCIPgetDiveBoundChangeData(SCIP *scip, SCIP_VAR ***variables, SCIP_BRANCHDIR **directions, SCIP_Real **values, int *ndivebdchgs, SCIP_Bool preferred)
Definition: scip.c:36068
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46138
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:16311
#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:3843
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:45816
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:9340
int SCIPgetNSOS1Vars(SCIP_CONSHDLR *conshdlr)
Definition: cons_sos1.c:10626
#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:366
methods commonly used by primal heuristics
SCIP_Real SCIPgetAvgLowerbound(SCIP *scip)
Definition: scip.c:42280
SCIP_Longint SCIPdivesetGetNLPIterations(SCIP_DIVESET *diveset)
Definition: heur.c:462
SCIP_RETCODE SCIPaddDiveBoundChange(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir, SCIP_Real value, SCIP_Bool preferred)
Definition: scip.c:36042
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:35220
SCIP_Real SCIPdivesetGetMinRelDepth(SCIP_DIVESET *diveset)
Definition: heur.c:358
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2903
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:21937
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip.c:1260
#define SCIPdebugMsg
Definition: scip.h:451
SCIP_Bool SCIPdivesetUseOnlyLPBranchcands(SCIP_DIVESET *diveset)
Definition: heur.c:580
SCIP_Real SCIPdivesetGetMaxLPIterQuot(SCIP_DIVESET *diveset)
Definition: heur.c:492
const char * SCIPgetProbName(SCIP *scip)
Definition: scip.c:10724
SCIP_RETCODE SCIPupdateVarPseudocost(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition: scip.c:25559
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:39
void SCIPclearDiveBoundChanges(SCIP *scip)
Definition: scip.c:36095
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip.c:29262
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1181
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:12410
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45764
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip.c:35477
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:16420
SCIP_Real SCIPgetDualbound(SCIP *scip)
Definition: scip.c:42302
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:2332
SCIP_RETCODE SCIPcopyCuts(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, int *ncutsadded)
Definition: scip.c:3056
SCIP_Real SCIPdivesetGetAvgQuot(SCIP_DIVESET *diveset)
Definition: heur.c:531
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip.c:35187
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16552
#define NULL
Definition: lpi_spx1.cpp:137
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:35927
#define SCIP_CALL(x)
Definition: def.h:306
SCIP_Real SCIPgetLowerbound(SCIP *scip)
Definition: scip.c:42323
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46125
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip.c:35713
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46112
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:16321
SCIP_Real SCIPdivesetGetLPResolveDomChgQuot(SCIP_DIVESET *diveset)
Definition: heur.c:568
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:16257
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip.c:28769
SCIP_Longint SCIPgetLastDivenode(SCIP *scip)
Definition: scip.c:34969
SCIP_Longint SCIPgetNNodeLPIterations(SCIP *scip)
Definition: scip.c:41703
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21925
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:16267
#define SCIP_Bool
Definition: def.h:61
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:28854
SCIP_Real SCIPdivesetGetUbQuotNoSol(SCIP_DIVESET *diveset)
Definition: heur.c:508
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition: scip.c:39073
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:42094
#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:35980
void SCIPenableVarHistory(SCIP *scip)
Definition: scip.c:25520
#define MINLPITER
Definition: heuristics.c:31
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38090
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:39749
#define SCIP_MAXTREEDEPTH
Definition: def.h:242
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11676
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11631
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:42261
#define SCIP_REAL_MIN
Definition: def.h:137
void SCIPdivesetSetWorkSolution(SCIP_DIVESET *diveset, SCIP_SOL *sol)
Definition: heur.c:337
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:16277
SCIP_Bool SCIPisObjIntegral(SCIP *scip)
Definition: scip.c:11205
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip.c:28897
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16081
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip.c:27323
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip.c:38222
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:899
SCIP_Longint SCIPgetNBestSolsFound(SCIP *scip)
Definition: scip.c:42718
#define SCIP_Real
Definition: def.h:135
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
#define MIN(x, y)
Definition: memory.c:75
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:155
#define SCIP_Longint
Definition: def.h:120
SCIP_Longint SCIPdivesetGetSolSuccess(SCIP_DIVESET *diveset)
Definition: heur.c:374
SCIP_RETCODE SCIPunlinkSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:37836
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:45864
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45777
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17232
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip.c:35092
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:35902
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip.c:35055
public methods for primal heuristics
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip.c:29165
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
Definition: scip.c:45949
#define SCIP_DIVETYPE_INTEGRALITY
Definition: type_heur.h:45
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:41182
#define SCIPABORT()
Definition: def.h:278
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:35264
int SCIPdivesetGetNCalls(SCIP_DIVESET *diveset)
Definition: heur.c:382
void SCIPupdateDivesetStats(SCIP *scip, SCIP_DIVESET *diveset, int nprobingnodes, int nbacktracks, SCIP_Longint nsolsfound, SCIP_Longint nbestsolsfound, SCIP_Bool leavewassol)
Definition: scip.c:35940
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38007
default SCIP plugins
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:45937
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:547
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip.h:21929
const char * SCIPdivesetGetName(SCIP_DIVESET *diveset)
Definition: heur.c:348