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-2024 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file heuristics.c
26  * @ingroup OTHER_CFILES
27  * @brief methods commonly used by primal heuristics
28  * @author Gregor Hendel
29  */
30 
31 #include "scip/heuristics.h"
32 #include "scip/cons_linear.h"
33 #include "scip/scipdefplugins.h"
34 #include "scip/stat.h"
35 #include "scip/struct_scip.h"
36 
37 #include "scip/pub_heur.h"
38 
39 /* the indicator and SOS1 constraint handlers are included for the diving algorithm SCIPperformGenericDivingAlgorithm() */
40 #include "scip/cons_indicator.h"
41 #include "scip/cons_sos1.h"
42 
43 #define MINLPITER 10000 /**< minimal number of LP iterations allowed in each LP solving call */
44 
45 
46 /** solve probing LP */
47 static
49  SCIP* scip, /**< SCIP data structure */
50  SCIP_DIVESET* diveset, /**< diving settings */
51  SCIP_Longint maxnlpiterations, /**< maximum number of allowed LP iterations */
52  SCIP_DIVECONTEXT divecontext, /**< context for diving statistics */
53  SCIP_Bool* lperror, /**< pointer to store if an internal LP error occurred */
54  SCIP_Bool* cutoff /**< pointer to store whether the LP was infeasible */
55  )
56 {
57  int lpiterationlimit;
58  SCIP_RETCODE retstat;
59  SCIP_Longint nlpiterations;
60 
61  assert(lperror != NULL);
62  assert(cutoff != NULL);
63 
64  nlpiterations = SCIPgetNLPIterations(scip);
65 
66  /* allow at least MINLPITER more iterations so as not to run out of LP iterations during this solve */
67  lpiterationlimit = (int)(maxnlpiterations - SCIPdivesetGetNLPIterations(diveset, divecontext));
68  lpiterationlimit = MAX(lpiterationlimit, MINLPITER);
69 
70  retstat = SCIPsolveProbingLP(scip, lpiterationlimit, lperror, cutoff);
71 
72  /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
73  * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
74  */
75 #ifdef NDEBUG
76  if( retstat != SCIP_OKAY )
77  {
78  SCIPwarningMessage(scip, "Error while solving LP in %s diving heuristic; LP solve terminated with code <%d>.\n", SCIPdivesetGetName(diveset), retstat);
79  }
80 #else
81  SCIP_CALL( retstat );
82 #endif
83 
84  /* update iteration count */
85  SCIPupdateDivesetLPStats(scip, diveset, SCIPgetNLPIterations(scip) - nlpiterations, divecontext);
86 
87  return SCIP_OKAY;
88 }
89 
90 /** select the next variable and type of diving */
91 static
93  SCIP* scip, /**< SCIP data structure */
94  SCIP_DIVESET* diveset, /**< dive set */
95  SCIP_SOL* worksol, /**< current working solution */
96  SCIP_Bool onlylpbranchcands, /**< should only LP branching candidates be considered? */
97  SCIP_Bool storelpcandscores, /**< should the scores of the LP candidates be updated? */
98  SCIP_VAR** lpcands, /**< LP branching candidates, or NULL if not needed */
99  SCIP_Real * lpcandssol, /**< solution values LP branching candidates, or NULL if not needed */
100  SCIP_Real* lpcandsfrac, /**< fractionalities of LP branching candidates, or NULL if not needed*/
101  SCIP_Real* lpcandsscores, /**< array with LP branching candidate scores, or NULL */
102  SCIP_Bool* lpcandroundup, /**< array to remember whether the preferred branching direction is upwards */
103  int* nviollpcands, /**< pointer to store the number of LP candidates whose solution value already violates local bounds */
104  int nlpcands, /**< number of current LP cands */
105  SCIP_Bool* enfosuccess, /**< pointer to store whether a candidate was sucessfully found */
106  SCIP_Bool* infeasible /**< pointer to store whether the diving can be immediately aborted because it is infeasible */
107  )
108 {
109  assert(scip != NULL);
110  assert(worksol != NULL);
111  assert(!onlylpbranchcands || lpcandsscores != NULL);
112  assert(!onlylpbranchcands || lpcandroundup != NULL);
113  assert(enfosuccess != NULL);
114  assert(infeasible != NULL);
115  assert(nviollpcands != NULL);
116 
117  *nviollpcands = 0;
118  /* we use diving solution enforcement provided by the constraint handlers */
119  if( !onlylpbranchcands )
120  {
121  SCIP_CALL( SCIPgetDiveBoundChanges(scip, diveset, worksol, enfosuccess, infeasible) );
122  }
123  else
124  {
125  int c;
126  int bestcandidx;
127  SCIP_Real bestscore;
128  SCIP_Real score;
129 
130  bestscore = SCIP_REAL_MIN;
131  bestcandidx = -1;
132 
134 
135  /* search for the candidate that maximizes the dive set score function and whose solution value is still feasible */
136  for( c = 0; c < nlpcands; ++c )
137  {
138  assert(SCIPgetSolVal(scip, worksol, lpcands[c]) == lpcandssol[c]); /*lint !e777 doesn't like comparing floats for equality */
139 
140  /* scores are kept in arrays for faster reuse */
141  if( storelpcandscores )
142  {
143  SCIP_CALL( SCIPgetDivesetScore(scip, diveset, SCIP_DIVETYPE_INTEGRALITY, lpcands[c], lpcandssol[c],
144  lpcandsfrac[c], &lpcandsscores[c], &lpcandroundup[c]) );
145  }
146 
147  score = lpcandsscores[c];
148  /* update the best candidate if it has a higher score and a solution value which does not violate one of the local bounds */
149  if( SCIPisLE(scip, SCIPvarGetLbLocal(lpcands[c]), lpcandssol[c]) && SCIPisGE(scip, SCIPvarGetUbLocal(lpcands[c]), lpcandssol[c]) )
150  {
151  if( score > bestscore )
152  {
153  bestcandidx = c;
154  bestscore = score;
155  }
156  }
157  else
158  ++(*nviollpcands);
159  }
160 
161  /* there is no guarantee that a candidate is found since local bounds might render all solution values infeasible */
162  *enfosuccess = (bestcandidx >= 0);
163  if( *enfosuccess )
164  {
165  /* if we want to round up the best candidate, it is added as the preferred bound change */
166  SCIP_CALL( SCIPaddDiveBoundChange(scip, lpcands[bestcandidx], SCIP_BRANCHDIR_UPWARDS,
167  SCIPceil(scip, lpcandssol[bestcandidx]), lpcandroundup[bestcandidx]) );
168  SCIP_CALL( SCIPaddDiveBoundChange(scip, lpcands[bestcandidx], SCIP_BRANCHDIR_DOWNWARDS,
169  SCIPfloor(scip, lpcandssol[bestcandidx]), ! lpcandroundup[bestcandidx]) );
170  }
171  }
172  return SCIP_OKAY;
173 }
174 
175 /** return the LP iteration budget suggestion for this dive set */
176 static
178  SCIP* scip, /**< SCIP data structure */
179  SCIP_DIVESET* diveset, /**< dive set data structure */
180  SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
181  )
182 {
183  SCIP_Longint iterlimit;
184  /*todo another factor of 10, REALLY? */
185  iterlimit = (SCIP_Longint)((1.0 + 10*(SCIPdivesetGetNSols(diveset, divecontext)+1.0)/(SCIPdivesetGetNCalls(diveset, divecontext)+1.0)) * SCIPdivesetGetMaxLPIterQuot(diveset) * SCIPgetNNodeLPIterations(scip));
186  iterlimit += SCIPdivesetGetMaxLPIterOffset(diveset);
187  iterlimit -= SCIPdivesetGetNLPIterations(diveset, divecontext);
188 
189  return iterlimit;
190 }
191 
192 /** performs a diving within the limits of the @p diveset parameters
193  *
194  * This method performs a diving according to the settings defined by the diving settings @p diveset; Contrary to the
195  * name, SCIP enters probing mode (not diving mode) and dives along a path into the tree. Domain propagation
196  * is applied at every node in the tree, whereas probing LPs might be solved less frequently.
197  *
198  * Starting from the current LP solution, the algorithm selects candidates which maximize the
199  * score defined by the @p diveset and whose solution value has not yet been rendered infeasible by propagation,
200  * and propagates the bound change on this candidate.
201  *
202  * The algorithm iteratively selects the the next (unfixed) candidate in the list, until either enough domain changes
203  * or the resolve frequency of the LP trigger an LP resolve (and hence, the set of potential candidates changes),
204  * or the last node is proven to be infeasible. It optionally backtracks and tries the
205  * other branching direction.
206  *
207  * After the set of remaining candidates is empty or the targeted depth is reached, the node LP is
208  * solved, and the old candidates are replaced by the new LP candidates.
209  *
210  * @see heur_guideddiving.c for an example implementation of a dive set controlling the diving algorithm.
211  *
212  * @note the node from where the algorithm is called is checked for a basic LP solution. If the solution
213  * is non-basic, e.g., when barrier without crossover is used, the method returns without performing a dive.
214  *
215  * @note currently, when multiple diving heuristics call this method and solve an LP at the same node, only the first
216  * call will be executed, see SCIPgetLastDiveNode()
217  *
218  * @todo generalize method to work correctly with pseudo or external branching/diving candidates
219  */
221  SCIP* scip, /**< SCIP data structure */
222  SCIP_DIVESET* diveset, /**< settings for diving */
223  SCIP_SOL* worksol, /**< non-NULL working solution */
224  SCIP_HEUR* heur, /**< the calling primal heuristic */
225  SCIP_RESULT* result, /**< SCIP result pointer */
226  SCIP_Bool nodeinfeasible, /**< is the current node known to be infeasible? */
227  SCIP_Longint iterlim, /**< nonnegative iteration limit for the LP solves, or -1 for dynamic setting */
228  int nodelimit, /**< nonnegative probing node limit or -1 if no limit should be used */
229  SCIP_Real lpresolvedomchgquot, /**< percentage of immediate domain changes during probing to trigger LP resolve or -1
230  * if diveset specific default should be used */
231  SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
232  )
233 {
234  SCIP_CONSHDLR* indconshdlr; /* constraint handler for indicator constraints */
235  SCIP_CONSHDLR* sos1conshdlr; /* constraint handler for SOS1 constraints */
236  SCIP_VAR** lpcands;
237  SCIP_Real* lpcandssol;
238 
239  SCIP_VAR** previouscands;
240  SCIP_Real* lpcandsscores;
241  SCIP_Real* previousvals;
242  SCIP_Real* lpcandsfrac;
243  SCIP_Bool* lpcandroundup;
244  SCIP_Real searchubbound;
245  SCIP_Real searchavgbound;
246  SCIP_Real searchbound;
247  SCIP_Real ubquot;
248  SCIP_Real avgquot;
249  SCIP_Longint maxnlpiterations;
250  SCIP_Longint domreds;
251  int startndivecands;
252  int depth;
253  int maxdepth;
254  int maxdivedepth;
255  int totalnbacktracks;
256  int totalnprobingnodes;
257  int lastlpdepth;
258  int previouscandssize;
259  int lpcandsscoressize;
260  int nviollpcands;
261  SCIP_Longint oldnsolsfound;
262  SCIP_Longint oldnbestsolsfound;
263  SCIP_Longint oldnconflictsfound;
264 
265  SCIP_Bool success;
266  SCIP_Bool leafsol;
267  SCIP_Bool enfosuccess;
268  SCIP_Bool lperror;
269  SCIP_Bool cutoff;
270  SCIP_Bool backtracked;
271  SCIP_Bool backtrack;
272  SCIP_Bool onlylpbranchcands;
273 
274  int nlpcands;
275  int lpsolvefreq;
276 
277  assert(scip != NULL);
278  assert(heur != NULL);
279  assert(result != NULL);
280  assert(worksol != NULL);
281 
282  *result = SCIP_DELAYED;
283 
284  /* do not call heuristic in node that was already detected to be infeasible */
285  if( nodeinfeasible )
286  return SCIP_OKAY;
287 
288  /* only call heuristic, if an optimal LP solution is at hand */
290  return SCIP_OKAY;
291 
292  /* only call heuristic, if the LP solution is basic (which allows fast resolve in diving) */
293  if( !SCIPisLPSolBasic(scip) )
294  return SCIP_OKAY;
295 
296  /* when heuristic was called by scheduler, be less restrictive */
297  if( divecontext != SCIP_DIVECONTEXT_SCHEDULER )
298  {
299  /* don't dive two times at the same node */
300  if( SCIPgetLastDivenode(scip) == SCIPgetNNodes(scip) && SCIPgetDepth(scip) > 0 )
301  return SCIP_OKAY;
302 
303  /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
304  if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) )
305  return SCIP_OKAY;
306  }
307 
308  *result = SCIP_DIDNOTRUN;
309 
310  /* only try to dive, if we are in the correct part of the tree, given by minreldepth and maxreldepth */
311  depth = SCIPgetDepth(scip);
312  maxdepth = SCIPgetMaxDepth(scip);
313  maxdepth = MAX(maxdepth, 30);
314  if( divecontext != SCIP_DIVECONTEXT_SCHEDULER &&
315  (depth < SCIPdivesetGetMinRelDepth(diveset) * maxdepth || depth > SCIPdivesetGetMaxRelDepth(diveset) * maxdepth) )
316  {
317  return SCIP_OKAY;
318  }
319 
320  /* calculate the maximal number of LP iterations */
321  if( iterlim < 0 )
322  {
323  maxnlpiterations = SCIPdivesetGetNLPIterations(diveset, divecontext) + getDivesetIterLimit(scip, diveset, divecontext);
324  }
325  else
326  {
327  maxnlpiterations = SCIPdivesetGetNLPIterations(diveset, divecontext) + iterlim;
328  }
329 
330  /* don't try to dive, if we took too many LP iterations during diving */
331  if( SCIPdivesetGetNLPIterations(diveset, divecontext) >= maxnlpiterations )
332  return SCIP_OKAY;
333 
334  /* allow at least a certain number of LP iterations in this dive */
335  if( SCIPdivesetGetNLPIterations(diveset, divecontext) + MINLPITER > maxnlpiterations )
336  maxnlpiterations = SCIPdivesetGetNLPIterations(diveset, divecontext) + MINLPITER;
337 
338  /* these constraint handlers are required for polishing an LP relaxation solution beyond rounding */
339  indconshdlr = SCIPfindConshdlr(scip, "indicator");
340  sos1conshdlr = SCIPfindConshdlr(scip, "SOS1");
341 
342  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, &lpcandsfrac, &nlpcands, NULL, NULL) );
343 
344  onlylpbranchcands = SCIPdivesetUseOnlyLPBranchcands(diveset);
345  /* don't try to dive, if there are no diving candidates */
346  if( onlylpbranchcands && nlpcands == 0 )
347  return SCIP_OKAY;
348 
349  /* calculate the objective search bound */
350  if( SCIPgetNSolsFound(scip) == 0 )
351  {
352  ubquot = SCIPdivesetGetUbQuotNoSol(diveset);
353  avgquot = SCIPdivesetGetAvgQuotNoSol(diveset);
354  }
355  else
356  {
357  ubquot = SCIPdivesetGetUbQuot(diveset);
358  avgquot = SCIPdivesetGetAvgQuot(diveset);
359  }
360 
361  if( ubquot > 0.0 )
362  searchubbound = SCIPgetLowerbound(scip) + ubquot * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
363  else
364  searchubbound = SCIPinfinity(scip);
365 
366  if( avgquot > 0.0 )
367  searchavgbound = SCIPgetLowerbound(scip) + avgquot * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
368  else
369  searchavgbound = SCIPinfinity(scip);
370 
371  searchbound = MIN(searchubbound, searchavgbound);
372 
373  if( SCIPisObjIntegral(scip) )
374  searchbound = SCIPceil(scip, searchbound);
375 
376  /* calculate the maximal diving depth: 10 * min{number of integer variables, max depth}*/
377  maxdivedepth = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
378  if ( sos1conshdlr != NULL )
379  maxdivedepth += SCIPgetNSOS1Vars(sos1conshdlr);
380  maxdivedepth = MIN(maxdivedepth, maxdepth);
381  maxdivedepth *= 10;
382 
383  /* if lpresolvedomchgquot is not explicitly given (so -1), then use the default for the current diveset */
384  if( lpresolvedomchgquot < 0 )
385  lpresolvedomchgquot = SCIPdivesetGetLPResolveDomChgQuot(diveset);
386  assert(lpresolvedomchgquot > 0.0 && lpresolvedomchgquot <= 1.0);
387 
388  *result = SCIP_DIDNOTFIND;
389 
390  /* start probing mode */
391  SCIP_CALL( SCIPstartProbing(scip) );
392 
393  /* enables collection of variable statistics during probing */
394  SCIPenableVarHistory(scip);
395 
396  SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") executing %s heuristic: depth=%d, %d fractionals, dualbound=%g, avgbound=%g, cutoffbound=%g, searchbound=%g\n",
397  SCIPgetNNodes(scip), SCIPheurGetName(heur), SCIPgetDepth(scip), nlpcands, SCIPgetDualbound(scip), SCIPgetAvgDualbound(scip),
398  SCIPretransformObj(scip, SCIPgetCutoffbound(scip)), SCIPretransformObj(scip, searchbound));
399 
400  /* allocate buffer storage for previous candidates and their branching values for pseudo cost updates */
401  lpsolvefreq = SCIPdivesetGetLPSolveFreq(diveset);
402  previouscandssize = MAX(1, lpsolvefreq);
403  SCIP_CALL( SCIPallocBufferArray(scip, &previouscands, previouscandssize) );
404  SCIP_CALL( SCIPallocBufferArray(scip, &previousvals, previouscandssize) );
405 
406  /* keep some statistics */
407  lperror = FALSE;
408  cutoff = FALSE;
409  lastlpdepth = -1;
410  startndivecands = nlpcands;
411  totalnbacktracks = 0;
412  totalnprobingnodes = 0;
413  oldnsolsfound = SCIPgetNSolsFound(scip);
414  oldnbestsolsfound = SCIPgetNBestSolsFound(scip);
415  oldnconflictsfound = SCIPgetNConflictConssFound(scip);
416 
417  /* link the working solution to the dive set */
418  SCIPdivesetSetWorkSolution(diveset, worksol);
419 
420  if( onlylpbranchcands )
421  {
422  SCIP_CALL( SCIPallocBufferArray(scip, &lpcandsscores, nlpcands) );
423  SCIP_CALL( SCIPallocBufferArray(scip, &lpcandroundup, nlpcands) );
424 
425  lpcandsscoressize = nlpcands;
426  }
427  else
428  {
429  lpcandroundup = NULL;
430  lpcandsscores = NULL;
431  lpcandsscoressize = 0;
432  }
433 
434  enfosuccess = TRUE;
435  leafsol = FALSE;
436 
437  /* LP loop; every time a new LP was solved, conditions are checked
438  * dive as long we are in the given objective, depth and iteration limits and fractional variables exist, but
439  * - if possible, we dive at least with the depth 10
440  * - if the number of fractional variables decreased at least with 1 variable per 2 dive depths, we continue diving
441  */
442  while( !lperror && !cutoff && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL && enfosuccess
443  && ( nodelimit == -1 || totalnprobingnodes < nodelimit )
444  && (SCIPgetProbingDepth(scip) < 10
445  || nlpcands <= startndivecands - SCIPgetProbingDepth(scip) / 2
446  || (SCIPgetProbingDepth(scip) < maxdivedepth && SCIPdivesetGetNLPIterations(diveset, divecontext) < maxnlpiterations && SCIPgetLPObjval(scip) < searchbound))
447  && !SCIPisStopped(scip) )
448  {
449  SCIP_Real lastlpobjval;
450  int c;
451  SCIP_Bool allroundable;
452  SCIP_Bool infeasible;
453  int prevcandsinsertidx;
454 
455  /* remember the last LP depth */
456  assert(lastlpdepth < SCIPgetProbingDepth(scip));
457  lastlpdepth = SCIPgetProbingDepth(scip);
458  domreds = 0;
459 
460  SCIPdebugMsg(scip, "%s heuristic continues diving at depth %d, %d candidates left\n",
461  SCIPdivesetGetName(diveset), lastlpdepth, nlpcands);
462 
463  /* loop over candidates and determine if they are roundable */
464  allroundable = TRUE;
465  c = 0;
466  while( allroundable && c < nlpcands )
467  {
468  if( SCIPvarMayRoundDown(lpcands[c]) || SCIPvarMayRoundUp(lpcands[c]) )
469  allroundable = TRUE;
470  else
471  allroundable = FALSE;
472  ++c;
473  }
474 
475  /* if all candidates are roundable, try to round the solution */
476  if( allroundable )
477  {
478  success = FALSE;
479 
480  /* working solution must be linked to LP solution */
481  SCIP_CALL( SCIPlinkLPSol(scip, worksol) );
482  /* create solution from diving LP and try to round it */
483  SCIP_CALL( SCIProundSol(scip, worksol, &success) );
484 
485  /* adjust SOS1 constraints */
486  if( success && sos1conshdlr != NULL )
487  {
488  SCIP_Bool changed;
489  SCIP_CALL( SCIPmakeSOS1sFeasible(scip, sos1conshdlr, worksol, &changed, &success) );
490  }
491 
492  /* succesfully rounded solutions are tried for primal feasibility */
493  if( success )
494  {
495  SCIP_Bool changed = FALSE;
496  SCIPdebugMsg(scip, "%s found roundable primal solution: obj=%g\n", SCIPdivesetGetName(diveset), SCIPgetSolOrigObj(scip, worksol));
497 
498  /* adjust indicator constraints */
499  if( indconshdlr != NULL )
500  {
501  SCIP_CALL( SCIPmakeIndicatorsFeasible(scip, indconshdlr, worksol, &changed) );
502  }
503 
504  success = FALSE;
505 
506  /* try to add solution to SCIP */
507  SCIP_CALL( SCIPtrySol(scip, worksol, FALSE, FALSE, FALSE, FALSE, changed, &success) );
508 
509  /* check, if solution was feasible and good enough */
510  if( success )
511  {
512  SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
513  *result = SCIP_FOUNDSOL;
514  leafsol = (nlpcands == 0);
515 
516  /* the rounded solution found above led to a cutoff of the node LP solution */
518  {
519  cutoff = TRUE;
520  break;
521  }
522  }
523  }
524  }
525 
526  /* working solution must be linked to LP solution */
527  assert(SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL);
528  lastlpobjval = SCIPgetLPObjval(scip);
529  SCIP_CALL( SCIPlinkLPSol(scip, worksol) );
530 
531  /* we must explicitly store the solution values by unlinking the solution, otherwise,
532  * the working solution may contain wrong entries, if, e.g., a backtrack occurred after an
533  * intermediate LP resolve or the LP was resolved during conflict analysis.
534  */
535  SCIP_CALL( SCIPunlinkSol(scip, worksol) );
536 
537  /* ensure array sizes for the diving on the fractional variables */
538  if( onlylpbranchcands && nlpcands > lpcandsscoressize )
539  {
540  assert(nlpcands > 0);
541  assert(lpcandsscores != NULL);
542  assert(lpcandroundup != NULL);
543 
544  SCIP_CALL( SCIPreallocBufferArray(scip, &lpcandsscores, nlpcands) );
545  SCIP_CALL( SCIPreallocBufferArray(scip, &lpcandroundup, nlpcands) );
546 
547  lpcandsscoressize = nlpcands;
548  }
549 
550  enfosuccess = FALSE;
551  /* select the next diving action by selecting appropriate dive bound changes for the preferred and alternative child */
552  SCIP_CALL( selectNextDiving(scip, diveset, worksol, onlylpbranchcands, SCIPgetProbingDepth(scip) == lastlpdepth,
553  lpcands, lpcandssol, lpcandsfrac, lpcandsscores, lpcandroundup, &nviollpcands, nlpcands,
554  &enfosuccess, &infeasible) );
555 
556  /* if we did not succeed finding an enforcement, the solution is potentially feasible and we break immediately */
557  if( ! enfosuccess )
558  break;
559 
560  prevcandsinsertidx = -1;
561 
562  /* start propagating candidate variables
563  * - until the desired targetdepth is reached,
564  * - or there is no further candidate variable left because of intermediate bound changes,
565  * - or a cutoff is detected
566  */
567  do
568  {
569  SCIP_VAR* bdchgvar;
570  SCIP_Real bdchgvalue;
571  SCIP_Longint localdomreds;
572  SCIP_BRANCHDIR bdchgdir;
573  int nbdchanges;
574 
575  /* ensure that a new candidate was successfully determined (usually at the end of the previous loop iteration) */
576  assert(enfosuccess);
577  bdchgvar = NULL;
578  bdchgvalue = SCIP_INVALID;
579  bdchgdir = SCIP_BRANCHDIR_AUTO;
580 
581  backtracked = FALSE;
582  do
583  {
584  int d;
585  SCIP_VAR** bdchgvars;
586  SCIP_BRANCHDIR* bdchgdirs;
587  SCIP_Real* bdchgvals;
588 
589  nbdchanges = 0;
590  /* get the bound change information stored in the dive set */
591  SCIPgetDiveBoundChangeData(scip, &bdchgvars, &bdchgdirs, &bdchgvals, &nbdchanges, !backtracked);
592 
593  assert(nbdchanges > 0);
594  assert(bdchgvars != NULL);
595  assert(bdchgdirs != NULL);
596  assert(bdchgvals != NULL);
597 
598  /* return if we reached the depth limit */
599  if( SCIP_MAXTREEDEPTH <= SCIPgetDepth(scip) )
600  {
601  SCIPdebugMsg(scip, "depth limit reached, we stop diving immediately.\n");
602  goto TERMINATE;
603  }
604 
605  /* return if we reached the node limit */
606  if( nodelimit != -1 && totalnprobingnodes >= nodelimit )
607  {
608  SCIPdebugMsg(scip, "node limit reached, we stop diving immediately.\n");
609  goto TERMINATE;
610  }
611 
612  /* dive deeper into the tree */
613  SCIP_CALL( SCIPnewProbingNode(scip) );
614  ++totalnprobingnodes;
615 
616  /* apply all suggested domain changes of the variables */
617  for( d = 0; d < nbdchanges; ++d )
618  {
619  SCIP_Real lblocal;
620  SCIP_Real ublocal;
621  SCIP_Bool infeasbdchange;
622 
623  /* get the next bound change data: variable, direction, and value */
624  bdchgvar = bdchgvars[d];
625  bdchgvalue = bdchgvals[d];
626  bdchgdir = bdchgdirs[d];
627 
628  assert(bdchgvar != NULL);
629  lblocal = SCIPvarGetLbLocal(bdchgvar);
630  ublocal = SCIPvarGetUbLocal(bdchgvar);
631 
632  SCIPdebugMsg(scip, " dive %d/%d, LP iter %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ": var <%s>, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
633  SCIPgetProbingDepth(scip), maxdivedepth, SCIPdivesetGetNLPIterations(diveset, divecontext), maxnlpiterations,
634  SCIPvarGetName(bdchgvar),
635  lblocal, ublocal,
636  bdchgdir == SCIP_BRANCHDIR_DOWNWARDS ? lblocal : bdchgvalue,
637  bdchgdir == SCIP_BRANCHDIR_UPWARDS ? ublocal : bdchgvalue);
638 
639  infeasbdchange = FALSE;
640  /* tighten the lower and/or upper bound depending on the bound change type */
641  switch( bdchgdir )
642  {
644  /* test if bound change is possible, otherwise propagation might have deduced the same
645  * bound already or numerical troubles might have occurred */
646  if( SCIPisFeasLE(scip, bdchgvalue, lblocal) || SCIPisFeasGT(scip, bdchgvalue, ublocal) )
647  infeasbdchange = TRUE;
648  else
649  {
650  /* round variable up */
651  SCIP_CALL( SCIPchgVarLbProbing(scip, bdchgvar, bdchgvalue) );
652  }
653  break;
655  /* test if bound change is possible, otherwise propagation might have deduced the same
656  * bound already or numerical troubles might have occurred */
657  if( SCIPisFeasGE(scip, bdchgvalue, ublocal) || SCIPisFeasLT(scip, bdchgvalue, lblocal) )
658  infeasbdchange = TRUE;
659  else
660  {
661  /* round variable down */
662  SCIP_CALL( SCIPchgVarUbProbing(scip, bdchgvar, bdchgvalue) );
663  }
664  break;
666  /* test if bound change is possible, otherwise propagation might have deduced the same
667  * bound already or numerical troubles might have occurred */
668  if( SCIPisFeasLT(scip, bdchgvalue, lblocal) || SCIPisFeasGT(scip, bdchgvalue, ublocal) ||
669  (SCIPisFeasEQ(scip, lblocal, ublocal) && nbdchanges < 2) )
670  infeasbdchange = TRUE;
671  else
672  {
673  /* fix variable to the bound change value */
674  if( SCIPisFeasLT(scip, lblocal, bdchgvalue) )
675  {
676  SCIP_CALL( SCIPchgVarLbProbing(scip, bdchgvar, bdchgvalue) );
677  }
678  if( SCIPisFeasGT(scip, ublocal, bdchgvalue) )
679  {
680  SCIP_CALL( SCIPchgVarUbProbing(scip, bdchgvar, bdchgvalue) );
681  }
682  }
683  break;
684  case SCIP_BRANCHDIR_AUTO:
685  default:
686  SCIPerrorMessage("Error: Unsupported bound change direction <%d> specified for diving, aborting\n",bdchgdirs[d]);
687  SCIPABORT();
688  return SCIP_INVALIDDATA; /*lint !e527*/
689  }
690  /* if the variable domain has been shrunk in the meantime, numerical troubles may have
691  * occured or variable was fixed by propagation while backtracking => Abort diving!
692  */
693  if( infeasbdchange )
694  {
695  SCIPdebugMsg(scip, "\nSelected variable <%s> domain already [%g,%g] as least as tight as desired bound change, diving aborted \n",
696  SCIPvarGetName(bdchgvar), SCIPvarGetLbLocal(bdchgvar), SCIPvarGetUbLocal(bdchgvar));
697  cutoff = TRUE;
698  break;
699  }
700  }
701  /* break loop immediately if we detected a cutoff */
702  if( cutoff )
703  break;
704 
705  /* apply domain propagation */
706  localdomreds = 0;
707  SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, &localdomreds) );
708 
709  /* add the number of bound changes we applied by ourselves after propagation, otherwise the counter would have been reset */
710  localdomreds += nbdchanges;
711 
712  SCIPdebugMsg(scip, "domain reductions: %" SCIP_LONGINT_FORMAT " (total: %" SCIP_LONGINT_FORMAT ")\n",
713  localdomreds, domreds + localdomreds);
714 
715  /* resolve the diving LP if the diving resolve frequency is reached or a sufficient number of intermediate bound changes
716  * was reached
717  */
718  if( ! cutoff
719  && ((lpsolvefreq > 0 && ((SCIPgetProbingDepth(scip) - lastlpdepth) % lpsolvefreq) == 0)
720  || (domreds + localdomreds > SCIPdivesetGetLPResolveDomChgQuot(diveset) * SCIPgetNVars(scip))
721  || (onlylpbranchcands && nviollpcands > (int)(SCIPdivesetGetLPResolveDomChgQuot(diveset) * nlpcands))) )
722  {
723  SCIP_CALL( solveLP(scip, diveset, maxnlpiterations, divecontext, &lperror, &cutoff) );
724 
725  /* lp errors lead to early termination */
726  if( lperror )
727  {
728  cutoff = TRUE;
729  break;
730  }
731  }
732 
733  /* perform backtracking if a cutoff was detected */
734  if( cutoff && !backtracked && SCIPdivesetUseBacktrack(diveset) )
735  {
736  SCIPdebugMsg(scip, " *** cutoff detected at level %d - backtracking\n", SCIPgetProbingDepth(scip));
738  ++totalnbacktracks;
739  backtracked = TRUE;
740  backtrack = TRUE;
741  cutoff = FALSE;
742  }
743  else
744  backtrack = FALSE;
745  }
746  while( backtrack );
747 
748  /* we add the domain reductions from the last evaluated node */
749  domreds += localdomreds; /*lint !e771 lint thinks localdomreds has not been initialized */
750 
751  /* store candidate for pseudo cost update and choose next candidate only if no cutoff was detected */
752  if( ! cutoff )
753  {
754  if( nbdchanges == 1 && (bdchgdir == SCIP_BRANCHDIR_UPWARDS || bdchgdir == SCIP_BRANCHDIR_DOWNWARDS) )
755  {
756  ++prevcandsinsertidx;
757  assert(prevcandsinsertidx <= SCIPgetProbingDepth(scip) - lastlpdepth - 1);
758  assert(SCIPgetProbingDepth(scip) > 0);
759  assert(bdchgvar != NULL);
760  assert(bdchgvalue != SCIP_INVALID); /*lint !e777 doesn't like comparing floats for equality */
761 
762  /* extend array in case of a dynamic, domain change based LP resolve strategy */
763  if( prevcandsinsertidx >= previouscandssize )
764  {
765  previouscandssize *= 2;
766  SCIP_CALL( SCIPreallocBufferArray(scip, &previouscands, previouscandssize) );
767  SCIP_CALL( SCIPreallocBufferArray(scip, &previousvals, previouscandssize) );
768  }
769  assert(previouscandssize > prevcandsinsertidx);
770 
771  /* store candidate for pseudo cost update */
772  previouscands[prevcandsinsertidx] = bdchgvar;
773  previousvals[prevcandsinsertidx] = bdchgvalue;
774  }
775 
776  /* choose next candidate variable and resolve the LP if none is found. */
778  {
779  assert(SCIPgetProbingDepth(scip) > lastlpdepth);
780  enfosuccess = FALSE;
781 
782  /* select the next diving action */
783  SCIP_CALL( selectNextDiving(scip, diveset, worksol, onlylpbranchcands, SCIPgetProbingDepth(scip) == lastlpdepth,
784  lpcands, lpcandssol, lpcandsfrac, lpcandsscores, lpcandroundup, &nviollpcands, nlpcands,
785  &enfosuccess, &infeasible) );
786 
787  /* in case of an unsuccesful candidate search, we solve the node LP */
788  if( !enfosuccess )
789  {
790  SCIP_CALL( solveLP(scip, diveset, maxnlpiterations, divecontext, &lperror, &cutoff) );
791 
792  /* check for an LP error and terminate in this case, cutoffs lead to termination anyway */
793  if( lperror )
794  cutoff = TRUE;
795 
796  /* enfosuccess must be set to TRUE for entering the main LP loop again */
797  enfosuccess = TRUE;
798  }
799  }
800  }
801  }
802  while( !cutoff && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_NOTSOLVED );
803 
804  assert(cutoff || lperror || SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_NOTSOLVED);
805 
808 
809  /* check new LP candidates and use the LP Objective gain to update pseudo cost information */
810  if( ! cutoff && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
811  {
812  int v;
813  SCIP_Real gain;
814 
815  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, NULL, &nlpcands, NULL, NULL) );
816 
817  SCIPdebugMsg(scip, " -> lpsolstat=%d, objval=%g/%g, nfrac=%d\n", SCIPgetLPSolstat(scip), SCIPgetLPObjval(scip), searchbound, nlpcands);
818  /* distribute the gain equally over all variables that we rounded since the last LP */
819  gain = SCIPgetLPObjval(scip) - lastlpobjval;
820  gain = MAX(gain, 0.0);
821  gain /= (1.0 * (SCIPgetProbingDepth(scip) - lastlpdepth));
822 
823  /* loop over previously fixed candidates and share gain improvement */
824  for( v = 0; v <= prevcandsinsertidx; ++v )
825  {
826  SCIP_VAR* cand = previouscands[v];
827  SCIP_Real val = previousvals[v];
828  SCIP_Real solval = SCIPgetSolVal(scip, worksol, cand);
829 
830  /* todo: should the gain be shared with a smaller weight, instead of dividing the gain itself? */
831  /* it may happen that a variable had an integral solution value beforehand, e.g., for indicator variables */
832  if( ! SCIPisZero(scip, val - solval) )
833  {
834  SCIP_CALL( SCIPupdateVarPseudocost(scip, cand, val - solval, gain, 1.0) );
835  }
836  }
837  }
838  else
839  nlpcands = 0;
840  }
841 
842  success = FALSE;
843  /* check if a solution has been found */
844  if( !enfosuccess && !lperror && !cutoff && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
845  {
846  /* create solution from diving LP */
847  SCIP_CALL( SCIPlinkLPSol(scip, worksol) );
848  SCIPdebugMsg(scip, "%s found primal solution: obj=%g\n", SCIPdivesetGetName(diveset), SCIPgetSolOrigObj(scip, worksol));
849 
850  /* try to add solution to SCIP */
851  SCIP_CALL( SCIPtrySol(scip, worksol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
852 
853  /* check, if solution was feasible and good enough */
854  if( success )
855  {
856  SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
857  *result = SCIP_FOUNDSOL;
858  leafsol = TRUE;
859  }
860  }
861 
862  SCIPupdateDivesetStats(scip, diveset, totalnprobingnodes, totalnbacktracks, SCIPgetNSolsFound(scip) - oldnsolsfound,
863  SCIPgetNBestSolsFound(scip) - oldnbestsolsfound, SCIPgetNConflictConssFound(scip) - oldnconflictsfound, leafsol, divecontext);
864 
865  SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") finished %s diveset (%s heur): %d fractionals, dive %d/%d, LP iter %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ", objval=%g/%g, lpsolstat=%d, cutoff=%u\n",
866  SCIPgetNNodes(scip), SCIPdivesetGetName(diveset), SCIPheurGetName(heur), nlpcands, SCIPgetProbingDepth(scip), maxdivedepth, SCIPdivesetGetNLPIterations(diveset, divecontext), maxnlpiterations,
867  SCIPretransformObj(scip, SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL ? SCIPgetLPObjval(scip) : SCIPinfinity(scip)), SCIPretransformObj(scip, searchbound), SCIPgetLPSolstat(scip), cutoff);
868 
869  TERMINATE:
870  /* end probing mode */
871  SCIP_CALL( SCIPendProbing(scip) );
872 
874 
875  if( onlylpbranchcands )
876  {
877  SCIPfreeBufferArray(scip, &lpcandroundup);
878  SCIPfreeBufferArray(scip, &lpcandsscores);
879  }
880  SCIPfreeBufferArray(scip, &previousvals);
881  SCIPfreeBufferArray(scip, &previouscands);
882 
883  return SCIP_OKAY;
884 }
885 
886 
887 /** creates the rows of the subproblem */
888 static
890  SCIP* scip, /**< original SCIP data structure */
891  SCIP* subscip, /**< SCIP data structure for the subproblem */
892  SCIP_HASHMAP* varmap /**< a hashmap to store the mapping of source variables to the corresponding
893  * target variables */
894  )
895 {
896  SCIP_ROW** rows; /* original scip rows */
897  SCIP_CONS* cons; /* new constraint */
898  SCIP_VAR** consvars; /* new constraint's variables */
899  SCIP_COL** cols; /* original row's columns */
900 
901  SCIP_Real constant; /* constant added to the row */
902  SCIP_Real lhs; /* left hand side of the row */
903  SCIP_Real rhs; /* left right side of the row */
904  SCIP_Real* vals; /* variables' coefficient values of the row */
905 
906  int nrows;
907  int nnonz;
908  int i;
909  int j;
910 
911  /* get the rows and their number */
912  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
913 
914  /* copy all rows to linear constraints */
915  for( i = 0; i < nrows; i++ )
916  {
917  /* ignore rows that are only locally valid */
918  if( SCIProwIsLocal(rows[i]) )
919  continue;
920 
921  /* get the row's data */
922  constant = SCIProwGetConstant(rows[i]);
923  lhs = SCIProwGetLhs(rows[i]) - constant;
924  rhs = SCIProwGetRhs(rows[i]) - constant;
925  vals = SCIProwGetVals(rows[i]);
926  nnonz = SCIProwGetNNonz(rows[i]);
927  cols = SCIProwGetCols(rows[i]);
928 
929  assert(lhs <= rhs);
930 
931  /* allocate memory array to be filled with the corresponding subproblem variables */
932  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nnonz) );
933  for( j = 0; j < nnonz; j++ )
934  consvars[j] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, (SCIPcolGetVar(cols[j])));
935 
936  /* create a new linear constraint and add it to the subproblem */
937  SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, SCIProwGetName(rows[i]), nnonz, consvars, vals, lhs, rhs,
938  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
939  SCIP_CALL( SCIPaddCons(subscip, cons) );
940  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
941 
942  /* free temporary memory */
943  SCIPfreeBufferArray(scip, &consvars);
944  }
945 
946  return SCIP_OKAY;
947 }
948 
949 
950 /** get a sub-SCIP copy of the transformed problem */
952  SCIP* sourcescip, /**< source SCIP data structure */
953  SCIP* subscip, /**< sub-SCIP used by the heuristic */
954  SCIP_HASHMAP* varmap, /**< a hashmap to store the mapping of source variables to the corresponding
955  * target variables */
956  const char* suffix, /**< suffix for the problem name */
957  SCIP_VAR** fixedvars, /**< source variables whose copies should be fixed in the target SCIP environment, or NULL */
958  SCIP_Real* fixedvals, /**< array of fixing values for target SCIP variables, or NULL */
959  int nfixedvars, /**< number of source variables whose copies should be fixed in the target SCIP environment, or NULL */
960  SCIP_Bool uselprows, /**< should the linear relaxation of the problem defined by LP rows be copied? */
961  SCIP_Bool copycuts, /**< should cuts be copied (only if uselprows == FALSE) */
962  SCIP_Bool* success, /**< was the copying successful? */
963  SCIP_Bool* valid /**< pointer to store whether the copying was valid, or NULL */
964  )
965 {
966  assert(sourcescip != NULL);
967  assert(suffix != NULL);
968  assert(subscip != NULL);
969  assert(varmap != NULL);
970  assert(success != NULL);
971 
972  if( uselprows )
973  {
974  char probname[SCIP_MAXSTRLEN];
975 
976  /* copy all plugins */
978 
979  /* set name to the original problem name and possibly add a suffix */
980  (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s_%s", SCIPgetProbName(sourcescip), suffix);
981 
982  /* create the subproblem */
983  SCIP_CALL( SCIPcreateProb(subscip, probname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
984 
985  /* copy all variables */
986  SCIP_CALL( SCIPcopyVars(sourcescip, subscip, varmap, NULL, fixedvars, fixedvals, nfixedvars, TRUE) );
987 
988  /* copy parameter settings */
989  SCIP_CALL( SCIPcopyParamSettings(sourcescip, subscip) );
990 
991  /* create linear constraints from LP rows of the source problem */
992  SCIP_CALL( createRows(sourcescip, subscip, varmap) );
993  }
994  else
995  {
996  SCIP_CALL( SCIPcopyConsCompression(sourcescip, subscip, varmap, NULL, suffix, fixedvars, fixedvals, nfixedvars,
997  TRUE, FALSE, FALSE, TRUE, valid) );
998 
999  if( copycuts )
1000  {
1001  /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
1002  SCIP_CALL( SCIPcopyCuts(sourcescip, subscip, varmap, NULL, TRUE, NULL) );
1003  }
1004  }
1005 
1006  /* disable bound limits in subscip since objective might be changed */
1007  SCIP_CALL( SCIPsetRealParam(subscip, "limits/primal", SCIP_INVALID) );
1008  SCIP_CALL( SCIPsetRealParam(subscip, "limits/dual", SCIP_INVALID) );
1009 
1010  *success = TRUE;
1011 
1012  return SCIP_OKAY;
1013 }
1014 
1015 /** adds a trust region neighborhood constraint to the @p targetscip
1016  *
1017  * a trust region constraint measures the deviation from the current incumbent solution \f$x^*\f$ by an auxiliary
1018  * continuous variable \f$v \geq 0\f$:
1019  * \f[
1020  * \sum\limits_{j\in B} |x_j^* - x_j| = v
1021  * \f]
1022  * Only binary variables are taken into account. The deviation is penalized in the objective function using
1023  * a positive \p violpenalty.
1024  *
1025  * @note: the trust region constraint creates an auxiliary variable to penalize the deviation from
1026  * the current incumbent solution. This variable can afterwards be accessed using SCIPfindVar() by its name
1027  * 'trustregion_violationvar'
1028  */
1030  SCIP* sourcescip, /**< the data structure for the main SCIP instance */
1031  SCIP* targetscip, /**< SCIP data structure of the subproblem */
1032  SCIP_VAR** subvars, /**< variables of the subproblem, NULL entries are ignored */
1033  SCIP_Real violpenalty /**< the penalty for violating the trust region */
1034  )
1035 {
1036  SCIP_VAR* violvar;
1037  SCIP_CONS* trustregioncons;
1038  SCIP_VAR** consvars;
1039  SCIP_VAR** vars;
1040  SCIP_SOL* bestsol;
1041 
1042  int nvars;
1043  int nbinvars;
1044  int nconsvars;
1045  int i;
1046  SCIP_Real rhs;
1047  SCIP_Real* consvals;
1048  char name[SCIP_MAXSTRLEN];
1049 
1050  /* get the data of the variables and the best solution */
1051  SCIP_CALL( SCIPgetVarsData(sourcescip, &vars, &nvars, &nbinvars, NULL, NULL, NULL) );
1052  bestsol = SCIPgetBestSol(sourcescip);
1053  assert(bestsol != NULL);
1054  /* otherwise, this neighborhood would not be active in the first place */
1055  assert(nbinvars > 0);
1056 
1057  /* memory allocation */
1058  SCIP_CALL( SCIPallocBufferArray(sourcescip, &consvars, nbinvars + 1) );
1059  SCIP_CALL( SCIPallocBufferArray(sourcescip, &consvals, nbinvars + 1) );
1060  nconsvars = 0;
1061 
1062  /* set initial left and right hand sides of trust region constraint */
1063  rhs = 0.0;
1064 
1065  /* create the distance (to incumbent) function of the binary variables */
1066  for( i = 0; i < nbinvars; i++ )
1067  {
1068  SCIP_Real solval;
1069 
1070  if( subvars[i] == NULL )
1071  continue;
1072 
1073  solval = SCIPgetSolVal(sourcescip, bestsol, vars[i]);
1074  assert( SCIPisFeasIntegral(sourcescip,solval) );
1075 
1076  /* is variable i part of the binary support of bestsol? */
1077  if( SCIPisFeasEQ(sourcescip, solval, 1.0) )
1078  {
1079  consvals[nconsvars] = -1.0;
1080  rhs -= 1.0;
1081  }
1082  else
1083  consvals[nconsvars] = 1.0;
1084  consvars[nconsvars] = subvars[i];
1085  assert(SCIPvarGetType(consvars[nconsvars]) == SCIP_VARTYPE_BINARY);
1086  ++nconsvars;
1087  }
1088 
1089  /* adding the violation variable */
1090  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_trustregionviolvar", SCIPgetProbName(sourcescip));
1091  SCIP_CALL( SCIPcreateVarBasic(targetscip, &violvar, name, 0.0, SCIPinfinity(targetscip), violpenalty, SCIP_VARTYPE_CONTINUOUS) );
1092  SCIP_CALL( SCIPaddVar(targetscip, violvar) );
1093  consvars[nconsvars] = violvar;
1094  consvals[nconsvars] = -1.0;
1095  ++nconsvars;
1096 
1097  /* creates trustregion constraint and adds it to subscip */
1098  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_trustregioncons", SCIPgetProbName(sourcescip));
1099 
1100  SCIP_CALL( SCIPcreateConsLinear(targetscip, &trustregioncons, name, nconsvars, consvars, consvals,
1101  rhs, rhs, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
1102  SCIP_CALL( SCIPaddCons(targetscip, trustregioncons) );
1103  SCIP_CALL( SCIPreleaseCons(targetscip, &trustregioncons) );
1104 
1105  /* releasing the violation variable */
1106  SCIP_CALL( SCIPreleaseVar(targetscip, &violvar) );
1107 
1108  /* free local memory */
1109  SCIPfreeBufferArray(sourcescip, &consvals);
1110  SCIPfreeBufferArray(sourcescip, &consvars);
1111 
1112  return SCIP_OKAY;
1113 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:395
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2082
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:882
#define NULL
Definition: def.h:267
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip_probing.c:225
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip_probing.c:198
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
#define SCIP_MAXSTRLEN
Definition: def.h:288
static SCIP_RETCODE createRows(SCIP *scip, SCIP *subscip, SCIP_HASHMAP *varmap)
Definition: heuristics.c:889
SCIP_Bool SCIPdivesetUseBacktrack(SCIP_DIVESET *diveset)
Definition: heur.c:702
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:117
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:17213
SCIP_Real SCIPdivesetGetUbQuot(SCIP_DIVESET *diveset)
Definition: heur.c:686
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18135
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPdivesetGetMaxLPIterOffset(SCIP_DIVESET *diveset)
Definition: heur.c:663
SCIP_Longint SCIPdivesetGetNLPIterations(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:589
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17351
int SCIPdivesetGetNCalls(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:485
SCIP_Real SCIPdivesetGetAvgQuotNoSol(SCIP_DIVESET *diveset)
Definition: heur.c:679
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1247
SCIP_RETCODE SCIPmakeSOS1sFeasible(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_Bool *changed, SCIP_Bool *success)
Definition: cons_sos1.c:10991
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_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1866
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17292
#define FALSE
Definition: def.h:94
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
int SCIPgetNSOS1Vars(SCIP_CONSHDLR *conshdlr)
Definition: cons_sos1.c:10889
#define TRUE
Definition: def.h:93
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_Real SCIPdivesetGetMaxRelDepth(SCIP_DIVESET *diveset)
Definition: heur.c:463
methods commonly used by primal heuristics
SCIP_Real SCIPgetAvgLowerbound(SCIP *scip)
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition: scip_var.c:194
static SCIP_Longint getDivesetIterLimit(SCIP *scip, SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heuristics.c:177
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:301
SCIP_Real SCIPdivesetGetMinRelDepth(SCIP_DIVESET *diveset)
Definition: heur.c:455
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3261
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:603
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPcopyParamSettings(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:2564
SCIP_Bool SCIPdivesetUseOnlyLPBranchcands(SCIP_DIVESET *diveset)
Definition: heur.c:743
SCIP_Real SCIPdivesetGetMaxLPIterQuot(SCIP_DIVESET *diveset)
Definition: heur.c:655
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1067
SCIP_RETCODE SCIPupdateVarPseudocost(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition: scip_var.c:8779
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:48
void SCIPclearDiveBoundChanges(SCIP *scip)
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip_lp.c:667
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1453
#define SCIPerrorMessage
Definition: pub_message.h:64
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2770
SCIP_RETCODE SCIPaddTrustregionNeighborhoodConstraint(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **subvars, SCIP_Real violpenalty)
Definition: heuristics.c:1029
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:580
SCIP_Longint SCIPdivesetGetNSols(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:641
static SCIP_RETCODE solveLP(SCIP *scip, SCIP_DIVESET *diveset, SCIP_Longint maxnlpiterations, SCIP_DIVECONTEXT divecontext, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: heuristics.c:48
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:17401
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:1178
SCIP_RETCODE SCIPcopyCuts(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, int *ncutsadded)
Definition: scip_copy.c:2130
SCIP_Real SCIPdivesetGetAvgQuot(SCIP_DIVESET *diveset)
Definition: heur.c:694
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:260
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17420
SCIP_RETCODE SCIPperformGenericDivingAlgorithm(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Bool nodeinfeasible, SCIP_Longint iterlim, int nodelimit, SCIP_Real lpresolvedomchgquot, SCIP_DIVECONTEXT divecontext)
Definition: heuristics.c:220
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:92
#define SCIP_CALL(x)
Definition: def.h:380
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP main data structure.
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:820
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17302
SCIP_Real SCIPdivesetGetLPResolveDomChgQuot(SCIP_DIVESET *diveset)
Definition: heur.c:731
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:17238
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:83
SCIP_Longint SCIPgetLastDivenode(SCIP *scip)
Definition: scip_lp.c:2745
SCIP_Longint SCIPgetNNodeLPIterations(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_DIVECONTEXT divecontext)
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 threadsafe, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip_copy.c:2969
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:17248
#define SCIP_Bool
Definition: def.h:91
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
SCIP_Real SCIPdivesetGetUbQuotNoSol(SCIP_DIVESET *diveset)
Definition: heur.c:671
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition: scip_sol.c:2311
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
SCIP_RETCODE SCIPgetDiveBoundChanges(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *sol, SCIP_Bool *success, SCIP_Bool *infeasible)
#define MIN(x, y)
Definition: def.h:243
void SCIPenableVarHistory(SCIP *scip)
Definition: scip_var.c:8740
#define MINLPITER
Definition: heuristics.c:43
SCIP_Longint SCIPgetNConflictConssFound(SCIP *scip)
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1300
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:2954
#define SCIP_MAXTREEDEPTH
Definition: def.h:316
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
SCIP_Real SCIPgetAvgDualbound(SCIP *scip)
#define SCIP_REAL_MIN
Definition: def.h:175
void SCIPdivesetSetWorkSolution(SCIP_DIVESET *diveset, SCIP_SOL *sol)
Definition: heur.c:434
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:165
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:17258
SCIP_Bool SCIPisObjIntegral(SCIP *scip)
Definition: scip_prob.c:1562
void SCIPupdateDivesetLPStats(SCIP *scip, SCIP_DIVESET *diveset, SCIP_Longint niterstoadd, SCIP_DIVECONTEXT divecontext)
#define MAX(x, y)
Definition: def.h:239
enum SCIP_DiveContext SCIP_DIVECONTEXT
Definition: type_heur.h:73
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:247
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2169
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:17042
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1668
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip_sol.c:1432
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:951
SCIP_Longint SCIPgetNBestSolsFound(SCIP *scip)
#define SCIP_Real
Definition: def.h:173
internal methods for problem statistics
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:724
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:193
#define SCIP_Longint
Definition: def.h:158
SCIP_RETCODE SCIPunlinkSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1046
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17585
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:18145
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip_probing.c:165
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_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:119
public methods for primal heuristics
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:570
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
#define SCIP_DIVETYPE_INTEGRALITY
Definition: type_heur.h:60
SCIP_Longint SCIPgetNNodes(SCIP *scip)
#define SCIPABORT()
Definition: def.h:352
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:345
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
default SCIP plugins
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPvarMayRoundUp(SCIP_VAR *var)
Definition: var.c:3452
SCIP_Bool SCIPvarMayRoundDown(SCIP_VAR *var)
Definition: var.c:3441
int SCIPdivesetGetLPSolveFreq(SCIP_DIVESET *diveset)
Definition: heur.c:710
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:128
const char * SCIPdivesetGetName(SCIP_DIVESET *diveset)
Definition: heur.c:445