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